给定一个样本点的集合,聚类的一般目的是将它们分配给多个组(称为簇),使得同一组中的点彼此之间比在其他组中的点更相似。“点”可以是一些具有距离概念的实体集合,能够使得任何一对实体之间存在距离。在这种意义上,这样的“点”的例子包括具有适当距离度量的图中的顶点和欧氏空间中的点。当一组点被聚类,例如,a和b为组1中的点,而c和d为组2中的点时,我们希望a比c或d更类似b,而c更类似于d,而不是a或b等。我们有很多理由想要进行这样的操作。考虑一个名为Massive Online Shop的虚拟的在线购物服务。对他们来说,给用户提供一些推荐使得用户能够找到相关商品是非常有益处的。因为当这种情况发生时,他们的用户更有可能购买,从而使得卖家获得更多利润,并且顾客也能够获得更高的满意度。顾客在未来进行购物时就会认为Massive Online Shop是有帮助并且是值得信赖的,因为它有能力提出相关商品的建议。提供商品建议的一种方法便是使用聚类。如果网站上的顾客可以被分成簇,以便同一组中的人有相似的兴趣并且倾向于购买类似的产品,那么,举例来说,Massive Online Shop便可以尝试向购物者推荐某个商品,因为她所在的簇中的许多购物者购买了这个商品。也就是说,Massive Online Shop推测她也可能想要那个商品。聚类的其他应用可以在图像分割和压缩[4]、社交网络中的社区检测以及并行和分布式算法的设计[25]中找到。在前面的讨论中,我们描述了当所有给出的信息是点和它们之间的连边(或者关系、距离)时的聚类问题。然而,有时数据可以由其不同的方面来表示。例如,视频可以由它的音频部分以及它的图像帧部分来表示;网页可以由它们所包含的文本以及指向这些页面的链接的锚文本来表示,例如[3];节点(通常是人,但可能是动物,如[23]),在社交网络中除了可以由它们之间的直接联系表示(这些联系来自于好友关系、合作关系或其他这样的相互作用),可以由他们的偏好、人口统计和传记数据来表示。在这种情况下,我们说数据有多个视图。我们研究这种类型的数据的子集,称为属性图。当处理图或网络数据时,存在点之间的关系(由链接或边表示),明确地表征相似性或相异性。如果有关于节点的其他信息,从中我们可以推断出未明确表示或实现的关系,我们将该图称为属性图。由于这种数据的大量增长,近来这种聚类范式受到越来越多的关注。当我们试图在这种情况下进行聚类时,涌现出的一些问题包括如何有效地组合视图、如何处理大量数据,以及如何推断不同视图和属性的相对重要性。在这篇论文中,我们对所有这些问题进行了一定程度的探索。利用多个数据视图的一种方法是将所有的数据视图连接在一起,并像单视图情况一样使用表示每个节点的结果向量继续进行聚类[6]。然而,使用这种方法的算法忽略了数据的不同视图之间的复杂关联[32]。此外,他们没有考虑到不同的视图倾向于具有不同的统计特性[32]。其他一些方法使用结构和属性信息的间接组合来构造复合图,从而获得更好聚类结果。在这方面,一些方法(例如[36]和[6])采用了一些在聚类过程中更新图的边上的权重的规则,其他一些方法(例如[14]和[16])在聚类之前通过一些预定义的方法组合视图。这两种方法的缺点是显而易见的。虽然前者更具适应性,但由于边权重被调整以改善聚类结果,使得数据集强制产生聚类,在一些情况下可能会产生偏差。后者也容易错误地估计不同视图的相对重要性,可能导致比其他方式获得的结果更差。然而,寻求解决这个问题的方法往往偏向于第一个策略—因此必须在这两种方法之间进行权衡。多视图聚类采用的方法多种多样。因此,对于多视图聚类,现有算法可以分为不同的类别,这些分类原则都有一定的意义。Xu等[32]基于使用一致性原则的方法和使用互补性原则的方法来对这些算法进行分类。一致性原则基于这样一种观点,即数据的不同视图表示图中的相同隐层结构,并且在每个视图中存在的信息存在于其他视图中。因此,在基于这一原理的算法中,目标是最小化数据的不同视图之间的不一致。另一方面,互补原理是基于这样一种想法,即数据的不同视图可能包含未被数据的其他视图捕获的信息。因此,基于这一原理的算法的目标是通过提供视图中没有的信息来改进聚类。然而,我们注意到,大多数多视点聚类算法模糊了这两个原则之间的界限。这些算法通常试图对来自多个视图的数据进行聚类,以便得到比单视图聚类更好的效果,因为其他视图提供了附加信息。这是在保持每个节点的特征之间的同质性下完成的。多视图聚类算法,如在[6]中提出的鲁棒多视图k均值聚类(RMKMC)和后续提出的改进算法[33]在不同视图上学习权重,在聚类过程中增量地调整权重。这是为了说明一些视图可以更准确地表示我们想要发现的图的隐层结构。除了视图对聚类具有不同的重要性,视图内的各种属性也往往对当前的聚类问题具有不同的相关性。因此,可以通过属性筛选来筛选出较少相关的属性或相应地减少它们的贡献来获得更好的聚类。在这方面,克鲁兹等人[9]使用自组织映射[19]来决定哪些属性对于集群是重要的。在用Louvain方法[5]进行聚类之前,他们将同一簇(自组织映射)中的节点中的边缘的权重调整成一定的常数。Cai等[6]指出了k均值聚类算法的效率,并将其推广到多视图聚类问题。他们提出了一种称为鲁棒多视图k均值聚类(RMKMC)方法,适合大规模数据。他们的方法的创新是在算法优化中实现了类似于单视图k均值方法的计算复杂度。虽然该方法能够选择对集群应用程序很重要的视图,但它并不适合于数据维度高的情况下[33]。这是因为所有视图中的所有特征都假定为相关的。在这个前提下,[33]提出了一种替代的多视图k均值聚类算法,该算法引入了强制特征选择的参数。该算法以增加模型复杂度为代价,在聚类过程中过滤掉冗余特征或属性,从而产生更好的结果。其他作者(如[8]和[30])提出了使用加权参数α组合两个距离函数的方法。这样的方法的一个例子是[8]:d(i,j)= α · ds(i,j)+(1-α)· dA(i,j)其中i和j是两个节点,ds(i,j)是结构距离,而dA(i,j)是它们之间的属性距离。也有使用随机游走合并结构和属性信息的方法。这种方法的一个例子是SA-Cluster算法[36]。它通过为每个属性值对引入新的节点来生成增强图。例如,如果属性affiliation具有三个值faculty,student,和other,则将创建三个新节点,每个值分别为一个节点。所有具有相同属性值的节点都连接到表示该值的节点上。这样,共享一个属性的相同值的节点变得距离更近。[36]然后利用节点的邻域上的随机游走在新的图上获得距离度量。通过调整不同属性边(包括原始结构边)的不同权重,其算法控制了不同属性在聚类中的贡献。谱方法尽管比较简单,但在单视图聚类问题中的巨大影响力也使得其被应用于多视图聚类问题。例如,在假设数据的不同视图中的聚类应该一致的情况下,de Sa提出了一种算法,该算法通过对数据的每个视图形成图并连接相应视图来形成二分图,然后对组合二分图进行谱聚类[10]。我们提出了两种结合图的结构和属性信息的方法,并将它们与余弦相似性进行比较,这是一种广泛使用的相似性度量,用于将节点的属性值转换成节点对之间的相似性。这两种方法,平方余弦相似性和频率归一化属性相似度(在实验中也称为方法2和方法3),试图解释在真实图形数据中观察到的一些特性。频率归一化属性相似度确定了共享属性的相对重要性。其采用的思想是通过对稀有属性进行更多的加权,而对常见属性进行更少的加权。而平方余弦相似度放大了较大相似度的贡献,从而相应减少较弱连接对聚类的贡献。我们将这些方法与该任务广泛使用的余弦相似性进行了比较,并讨论了方法的相对优势和弱点。我们还把一种近似谱聚类算法从单视图聚类问题拓展到多视图聚类问题。使用[28]和[17]的结果,我们展示了如何将新的复合图嵌入到低维空间中。当一个节点被视为电阻网络时,一对节点之间的距离是它们之间的近似有效电阻。该算法的优点是能够处理比传统谱算法更大的图,而传统方法没有对数据进行采样以减小其数据大小或近似求解特征向量。为了在图中找到两个节点之间的有效电阻,我们将图看作是一个电阻网络,其中每个边具有与其重量的倒数相等的电阻。这意味着边的权重越大,其阻力越小，反之亦然。这就体现了具有较大权重的边比具有较小权重的边具有更强的相似性。两个节点之间的有效电阻定义了它们之间的距离[18]。这个距离的一个特性是,随着两个顶点之间的替代路径的数目增加,它会随之减小。例如,如果从节点a到节点b有三条路径,并且最短路径在它们之间通过,但是还有另外两条路径经过两组不同的顶点,那么a到b之间的测地线距离是1。然而有一种情况,其中a和b比另一对顶点更近,例如c和d,它们之间只有一条直接链边。换言之,即使在a和b之间的测地线距离与c和d之间相同,但是将a和b断比将c和d断开更困难。所以实现一个更好距离度量是有必要的,它能够通过实现a和b之间的距离小于c和d之间的距离来达到这个目的。有效电阻放在在给出节点之间的距离时考虑了两个顶点之间的可能的替代路径的影响。这是该度量的一个重要性质,它与图上的随机游走的关系已经被证明(例如在[12]中),并且是近似算法和基于k-medoids的方法的嵌入思想的核心。我们将近似算法的结果与来自Ng Jordan和Weiss[26]的频谱k均值算法的结果进行比较,并观察结果是否更好。特别地,在具有几千个节点的图中,使用相对较少的随机向量(小于顶点数的2%)来表示图,我们能够获得与基准算法实现的聚类效果近似的结果。最后,我们提出了一种基于k-medoids的算法,该算法使用一个距离度量将图的不同视图上的不同距离集成到一个距离度量中,然后使用该距离度量进行聚类。在结构视图中,我们使用有效电阻,而在属性视图中,我们使用平方余弦相似性或频率归一化属性相似度。然后,我们使用加权方案来重新加权两个视图的相似性,该加权方案考虑了在不同视图上获得的相似性的大小的差异实验结果表明,该方法对聚类有数百个节点小数据集是有效的。