计算机工程与应用 ›› 2017, Vol. 53 ›› Issue (15): 222-226.DOI: 10.3778/j.issn.1002-8331.1601-0047

• 图形图像处理 • 上一篇    下一篇

基于谱特征和图分割的图聚类算法

高  阳1,李昌华1,李智杰1,2,崔欢欢1   

  1. 1.西安建筑科技大学 信息与控制工程学院,西安 710055
    2.西安建筑科技大学 建筑学院,西安 710055
  • 出版日期:2017-08-01 发布日期:2017-08-14

Graph clustering algorithm based on spectrum and graph partition

GAO Yang1, LI Changhua1, LI Zhijie1,2, CUI Huanhuan1   

  1. 1.College of Information & Control Engineering, Xi’an University of Architecture and Technology, Xi’an 710055, China
    2.College of Architecture, Xi’an University of Architecture and Technology, Xi’an 710055, China
  • Online:2017-08-01 Published:2017-08-14

摘要: 为了对图数据库中的结构化数据有效的聚类分析,首先对不同的图数据样本进行特征的深度挖掘,构造了包含节点间连接层次关系的关联度矩阵,与拉普拉斯矩阵结合共同完成谱特征分析;然后利用高斯核函数进行相似度矩阵的构建,将相似度归一化到0到1的范围内便于后期处理;最后结合图分割与k-means算法将相似度矩阵进行k分割,得到k个聚类。经过大量分析实验表明,改进的拉普拉斯矩阵对样本内部结构有更为精细的划分,提高了前期样本处理效果。最小比率割算法在保证精度的前提下,将NP难的问题转化为多项式时间内解决的问题,提高了算法的效率。

关键词: 谱特征分解, 图分割, 相似度矩阵, 图聚类

Abstract:

In order to analyze the structured data in database with valid clustering, the algorithm firstly mines the depth data characteristics of different graph sample, and constructs the association matrix including connection relations and nodes with hierarchy, completes the analysis of spectral characteristics combined with the Laplace matrix. Secondly, it uses the Gaussian kernel to build the similarity matrix, to facilitate post-processing the value of similarity matrix normalized in the range of 0-1. Finally, it combines k-means with graph partitioning algorithm to make the data k-partition, then gets k cluster of the database. The experimental results demonstrate that the improved Laplace has finer division of the internal structure in matrix, and improves the pre-process results of the sample. The minimum rate cut algorithm ensures the accuracy of the premise, and turns the NP-hard problem into a polynomial time to solve the problems and improve algorithm efficiency.

Key words: spectral decomposition, graph segmentation, similarity matrix, graph clustering