一种新的属性图重叠聚类挖掘算法

摘 要： 属性图各节点附有的节点属性标签，为节点提供了更加丰富的信息，在数据挖掘应用，特别是数据聚类问题中如何有效利用这些丰富的信息，已经成为开展此类研究的研究目的。不同于传统图聚类，属性图上的聚类要同时考虑图的结构信息和节点的属性信息，因此如何平衡两者之间的关系，这是属性图聚类主要关注所在。目前已提出的属性图聚类算法，部分算法的效率很高，然而聚类质量较差，同时一些算法可以得到较好的聚类结构，然而算法消耗大量的系统资源，效率也较低。这些算法均没有考虑簇之间存在重叠的情况，这导致无法得到更高精度的聚类结构。因而提出一种属性图上的重叠聚类挖掘算法，实验表明，提出的算法可以得到更高的聚类精度，特别是可以提升聚类内部节点的属性相似度。

关键词：

中图分类号： TP301.6 文献标识码： A 文章编号：2095-2163（2012）05-0027-04

0 引 言

聚类是数据挖掘中的主要方法之一，其目的在于通过自动化方法发现大量数据中存在的聚集特性，以提取其中蕴含的潜在规律。很多数据都具有网络的形式（如人际关系网络、科研合作网络、万维网等），对这些数据可以运用图数据结构加以科学化、体系化的有效组织。采用传统的聚类方法，不能解决图上的节点间聚类，因此，对于在图上发现簇的图聚类问题，已经日益得到了来自研究人员的广泛而深入的关注。图聚类问题可以简单描述为：已知一个节点集合及节点间连边情况，如何发现那些具有连接结构上相似性的节点子集。一般来说，同簇的节点间的连接应该更稠密，同时，属于不同簇的节点之间的连接更稀疏。目前的工作虽然很多，但对于聚类这一模糊的概念，还没有一个统一的精确定义，关于聚类特性的形成机制，也处于探索和发展中。

属性图上的聚类问题是图聚类问题中的一个特例。属性图的定义为：节点间存在边的同时，每个节点或每条边（注：文中工作只考虑节点属性）拥有特有的属性标签。属性图上的聚类不仅要考虑到节点间结构上的相似性，同时还要考虑节点属性间的相似性，然而，由于节点间的连接和节点具有的属性这两者体现的是完全不同的信息，因此如何协调处理两者间的关系是一个难题。随着网络的发展和计算机采集、处理数据的能力不断提升，属性图的应用前景广阔，目前也已经开展了一部分研究工作。当前处理节点属性图聚类问题主要有两种方法：

（1）基于节点相似性的方法：主要思想是同时考虑节点的结构和属性来定义点对间的相似性，根据属性相似性为每个边分配权重，并将属性图聚类问题转化为带权图的聚类问题。文献？眼1？演将边的权重定义为端点间具有相同属性值的属性个数，之后在带权图上聚类；文献？眼2？演提出与文献？眼1？演类似的属性相似性度量，并扩展至属性具有连续值域的情况。上述工作均为人工定义结构和属性间的权重，方法的效率虽然很高，但聚类效果并不好，而且由于需要人工定义权重，对于不同应用背景图数据的可拓展性很差。文献？眼3？演首先假定节点和属性间的权重值以及多个属性间的权重值，再根据权重确定节点间的随机游走距离，即节点间的相似性，之后采用类似K-Mean的方法不断优化得到聚类各簇，同时根据每次迭代产生的簇确定下一轮迭代的属性权重。该方法的聚类质量提升较大，但在每次迭代中都要根据新的属性权重，重新计算点对之间的随机游走距离矩阵，效率低，资源消耗大。