论文部分内容阅读
图聚类作为从海量数据中发现有用知识的技术引起了人们的广泛关注。目前的聚类方法多是在基于图拓扑结构或基于图节点属性方面进行研究,而在某些实际应用中需要同时考虑图节点的拓扑结构和属性关系。因此,现有的图聚类方法在处理此类应用时存在对象建模不准确、聚类结果不理想、算法执行效率低等问题,为了解决现有图聚类算法在实际应用中存在的问题,本文在以下几个方面进行研究:首先,针对现有图聚类方法在数据集合建模方面存在的问题,提出了一种属性加权图的图模型。在模型中,顶点表示数据对象,边表示数据对象间的关系,顶点属性表示数据对象的特征。根据数据对象间的紧密程度和各特征值对数据对象的不同重要程度,分别对结构边和顶点的相应属性设定的不同的权值。通过建模,可使属性加权图更真实地表现现实应用中数据对象的实际分布情况。其次,针对现有结构与属性图聚类方法中存在的问题,本文提出了一种基于结构-属性的高效SACA(Structural andAttributed ClusteringApproach)图聚类方法。1)提出了属性加权图模型。该模型通过对图中的边和属性设定不同的权值,更好地反映实际应用中实体对象的复杂关系。2)提出一种结构-属性的统一度量方法,用以测量图相似度,图聚类算法可以通过该度量方法对结构与属性的相似度进行计算。3)采用随机游走模型对图结构和属性的相似度进行处理,将节点间结构与属性关系转换为相应的相似度矩阵,利用相似度矩阵进行进一步的处理,提高了算法效率。4)结合图结构与属性关系及相似度矩阵,采用信息传递算法对图进行聚类,使同一簇中的各顶点在拓扑结构上是紧密相连,且各顶点的属性是同质的;不同簇之间的顶点之间的连接是的稀疏的,各顶点的属性是异质的。最后,通过实验对所提出的SACA图聚类算法进行了验证。通过对比不同聚类方法的聚类结果,表明本文的SACA图聚类算法在聚类效果和时间复杂度等性能上要优于现有的图聚类算法。