基于局部密度构造相似矩阵的谱聚类算法  

Local density-based similarity matrix construction for spectral clustering

作　　者：吴健[1] 崔志明[1] 时玉杰[1] 盛胜利 龚声蓉[1] 

机构地区：[1]苏州大学智能信息处理及应用研究所,江苏苏州215006 [2]美国阿肯色中央大学计算机科学系,阿肯色州康威720350001

出　　处：《通信学报》2013年第3期14-22,共9页Journal on Communications

基　　金：国家自然科学基金资助项目(61003054;61170020;61170124)~~

摘　　要：依据样本数据点分布的局部和全局一致性特征,提出了一种基于局部密度构造相似矩阵的谱聚类算法。首先通过分析样本数据点的分布特性给出了局部密度定义,根据样本点的局部密度对样本点集由密到疏排序,并按照设计的连接策略构建无向图;然后以GN算法思想为参考,给出了一种基于边介数的权值矩阵计算方法,经过数据转换得到谱聚类相似矩阵;最后通过第一个极大本征间隙出现的位置来确定类个数,并利用经典聚类方法对特征向量空间中的数据点进行聚类。通过人工仿真数据集和UCI数据集进行测试,实验结果表明本文谱聚类算法具有较好的顽健性。According to local and global consistency characteristics of sample data points＇ distribution, a spectral clustering algorithm using local density-based similarity matrix construction was proposed. Firstly, by analyzing distribution characteristics of sample data points, the definition of local density was given, sorting operation on sample point set from dense to sparse according to sample points＇ local density was did, and undirected graph in accordance with the designed connection strategy was constructed; then, on the basis of GN algorithm＇s thinking, a calculation method of weight matrix using edge betweenness was given, and similarity matrix of spectral clustering via data conversion was got; lastly, the class number by appearing position of the first eigengap maximum was determined, and the classification of sample point set in eigenvector space by means of classical clustering method was realized. By means of artificial simulative data set and UCI data set to carry out the experimental tests, results show that the proposed spectral algorithm has better clustering capability.

关 键 词：谱聚类 相似矩阵 局部密度 无向图构建 边介数 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]