VIBR: 通過MDL準則視覺化大規模二分關係資料（Visualizing Bipartite Relations at Scale with th...
對於兩個集合，如果一個集合中點和另一個結合中的點有連線，而集合內的點之間沒有連線，那麼這樣的資料稱為二分關係資料。通常這樣的資料通過圖模型來描述，這類特殊的圖稱為二分圖（圖1）。生活中存在大量這樣的二分關係資料，比如顧客購買商品，議員投票議案等。已有工作針對二分關係資料的分析仍停留在表現單個節點和邊，難以處理大規模的二分關係資料。本文介紹的工作[1]使用了最小描述長度準則（Minimum Description Length Principle）來對二分資料聚合，並且提出了基於鄰接連結串列形式的視覺化方法分析二分關係資料，相比於已有方法，該方法能夠更好的提供二分關係資料的概覽。
圖1 二分圖
如圖2所示，該工作的核心思想是將原有的資料通過一個Summary Graph和Corrections表示。Summary Graph由多個bi-clique組成，每個bi-clique中，節點和另一個集合中的節點是全連線關係。為了完全描述原有資料中的連線關係，需要對Summary Graph新增修正項。在Summary Graph中，節點2和c是連線的，然而他們在原有資料中並沒有連線，所以需要在Corrections中去除該連線。同樣，原有資料中1和d是連線的，然而在Summary Graph中並沒有體現出來，所以需要再Corrections新增該連線。Summary Graph提供了對原始資料的概覽。然而如何從原有資料中劃集合U、V獲得Summary Graph？
圖2 通過Summary Graph和Corrections表示原始資料
作者採用了MDL準則。對於一個數據，如果我們通過一個數學模型去描述它，那麼可以得到如下關係:
其中L是該資料的描述長度，L(M)是模型的描述長度，L(D|M)是基於模型對於資料的描述長度。一個最優的模型應該使得L的值最小。將這個原則應用到二分關係資料，可以得到如下關係：
其中L(S)是Summary Graph的描述長度，L(C)是Corrections的描述長度。P、Q分別是對集合U、V的聚類結果。進一步細化，可以得到如下的損失函式。第一項，第二項分別是Summary Graph中bi-clique的個數，Corrections連線的個數。第三、四項是正則項，避免產生大量的聚類數目。
為了求解最後的Summary Graph，作者首先提出了一種自底向上貪心演算法，把每個節點當成聚類，然後合併兩個聚類，它們合併後使得損失函式的值變得最小。這是一種列舉演算法，效率比較低。為了提高計算效率，作者提出先通過對聚類雜湊，計算聚類的相似性，合併聚類時候，列舉與當前聚類的最相似的類，當相似性低於閾值時，不再列舉。
圖3 基於鄰接連結串列形式的視覺化設計
在得到Summary Graph，作者提出了一種基於鄰接連結串列形式的視覺化形式。每一行代表集合P中的一個類，每個色塊代表結合Q的一個類，矩形塊的高度代表p1中的節點數量，矩形塊的寬度代表q1中的節點數量，色塊填充區域的高度代表p1和q1之間連邊的密度，每一行的色塊按照密度排列。這樣的視覺化形式可以提供一個緊湊佈局，並且支援對色塊的過濾操作（圖4）。
圖4 使用者可以通過多種方式對色塊過濾
作者以美國議會議員對法案的投票資料為例，說明系統分析流程。在檢視中部，分別是共和黨議員和民主黨議員對於法案投票結果的聚類結果。可以看出不同黨派議員對於法案有不同的投票偏好。使用者可以通過雙擊色塊（圖5-1），在矩陣細節檢視中，展現具體的議員法案投票結果（圖5-2），通過刷選矩陣檢視，可以顯示具體的法案。
圖5 針對美國議會議員法案投標結果的分析
總的來說，作者通過MDL準則提取大規模二分圖矩陣的結構，相比於傳統的二分聚類演算法，MDL準則更容易理解，並且更好支援使用者對於聚類結果的調整。
參考文獻：
[1] Gromit Yeuk-Yin Chan, Panpan Xu, Zeng Dai and Liu Ren. VIBR: Visualizing Bipartite Relations at Scale with the Minimum Description Length Principle. VAST 2018.