基于二部图的双聚类可视分析 (Interactive Visual Co-Cluster Analysis of Bipartite Graphs)

二部图(Bipartite Graph)是图论中的一种模型,图的顶点集V可以分割成两个互不相交的子集,图中每条边两端的顶点都属于不同的两个子集,并且同一个子集中的顶点不相邻。二部图出现在不少实际情况中,例如研究者和研究课题可以看做是两个不相交的子集,而研究者和研究课题间可以形成联系;议员与议案之间也存在类似的关系。双聚类(Co-Clustering)可以对二部图的两个子集同时进行聚类。

基于二部图的双聚类有实际的意义。例如,通过对研究者和研究课题进行双聚类,我们可以分析哪些研究者在研究相似的课题,也可以分析哪些课题之间具有较强的相关性。

这篇论文介绍了一种可视分析系统,通过结合邻接矩阵和树图的可视形式来帮助用户分析二部图中的聚类。

图1 系统流程概览

图1展示了该系统的分析流程。首先对数据集进行双聚类分析。在双聚类分析中,作者提出了一种半监督的双聚类方法,用户可以人为地将一些点对设为”相似的”,系统利用一种度量学习方法将用户的标注数据体现在最后的双聚类算法中。在得到数据的聚类结果后,系统会将数据转换为可视化元素(矩阵、树图、连线等),并进行空间布局,最后形成可视化界面。用户在可视化界面中进行交互探索,同时也可以对数据进行标注,来增强半监督算法。

图2 系统界面

图2是可视化系统界面,主要的可视化元素集中在视图A中,作者利用邻接矩阵和树图的形式来展示聚类内的元素关系,利用连线展示不同聚类之间的联系,连线的粗细可以表现出两个聚类之间的相关程度。图中,每一个聚类可以用邻接矩阵或树图来展示。

将节点的聚类转换成邻接矩阵可以分为两步,如图3所示。首先,我们可以将聚类内的节点提取出来,转换为一个节点之间的无向完全图,如图3(b),图中每条边的权重可以用两个节点间相同的邻居节点数量来表示。之后,将图3(b)中的图转换成邻接矩阵,方格的颜色表示了两个节点之间边的权重。为了类内节点之间的凝聚性,矩阵的行列通过重排列来更好地展示节点的聚类特性。

节点聚类还可以转换为树图形式表示,如图2中的A4所示。树图可以利用更小地空间展示聚类内元素的属性分布(例如议员的党派分布)。在树图的布局时,首先利用节点的类别属性或是数值属性的区间段作为类别作为第一层布局依据划分区域,之后在每个子区域内再根据节点的某个属性值进行第二层布局。

 

图3 将二部图中的节点聚类转换成邻接矩阵表示形式

此外,系统还利用TableLens的形式来展示数据的所有属性(如图2(C))。

在用户交互方面,系统支持用户通过鼠标移动来查看节点的详细信息,用户也可以在邻接矩阵和树图的表现形式之间互相切换。用户也可以合并多个聚类,或拆分一个聚类,来对聚类结果进行调整,用户也可以手动指定一些相似的节点作为聚类算法的限制条件,并可以重新运行半监督的双聚类算法来得到更符合用户预期的聚类结果。

作者利用该系统分析了美国2012年参议院的议案投票数据。数据中包括140个议案和100位参议员,议员和他所支持的议案间有连线,数据集中共有6962条连边。

图2即是该数据的可视化结果。图2A的上半部分为议案,下半部分为议员。我们可以清楚地看到,议员的聚类可以明显地分为两个部分,他们分别代表着民主党和共和党的议员。而议案也可以分为被民主党支持、被共和党支持、被两党共同支持的三个大的类别。

我们可以从议员的聚类中发现一些有意思的现象。图2A中的M1聚类里主要都是民主党的议员,但却混入了一位共和党议员Scott Brown。通过观察他所支持的议案,我们发现他在一定程度上与民主党的议员相一致。在M3中,我们如果按照议员的地区来进行排列(如图4),可以发现同地区的议员在支持的议案上有极大的相似性。


4 来自同地区的共和党议员在支持的议案上有极大相似性

此外,我们也可以将半监督双聚类分析应用到该数据上。我们手动地将所有的共和党议员设为一个聚类。在重新运行聚类算法后,我们会发现新的聚类中除了包含所有的共和党议员之外,还包含了3为民主党议员Claire McCaskill, Jay Rockefeller, Ben Nelson通过搜索他们相关的新闻报道后,我们发现这三位都在一定程度上与共和党有类似的政见。

综上所言,这篇论文首先提出了一种基于半监督的双聚类算法,同时实现了一个用于分析二部图聚类的可视分析系统,该系统可以帮助用户更好地分析二部图中两个部分之间的关系、聚类之间的关系以及聚类内的属性特征。

 

参考文献:

[1] Panpan Xu, Nan Cao, Huamin Qu, John Stasko. Interactive Visual Co-Cluster Analysis of Bipartite Graphs. IEEE Transactions on Visualization and Computer Graphics, 2016, 22, pp.32-39

评论关闭。