VIBR: 通过MDL准则可视化大规模二分关系数据(Visualizing Bipartite Relations at Scale with the Minimum Description Length Principle)

对于两个集合,如果一个集合中点和另一个结合中的点有连接,而集合内的点之间没有连接,那么这样的数据称为二分关系数据。通常这样的数据通过图模型来描述,这类特殊的图称为二分图(图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.

评论关闭。