基于低密度分割密度敏感距离的谱聚类算法

Low Density Separation Density Sensitive Distance-based Spectral Clustering Algorithm

本文提出一种基于低密度分割密度敏感距离的谱聚类算法,该算法首先使用低密度分割密度敏感距离计算相似度矩阵,该距离测度通过指数函数和伸缩因子实现放大不同流形体数据间的距离和缩短同一流形体数据间距离的目的,从而有效反映数据分布的全局一致性和局部一致性特征.另外,算法通过增加相对密度敏感项来考虑数据的局部分布特征,从而有效避免孤立噪声和"桥"噪声的影响.文中最后给出了基于SC(Scattering criteria)指标的k近邻图k值选取办法和基于谱熵贡献率的特征向量选取方法.实验部分,讨论了参数选择对算法性能的影响并给出取值建议,通过与其他流行谱聚类算法聚类结果的对比分析,表明本文提出的基于低密度分割密度敏感距离的谱聚类算法聚类性能明显优于其他算法.

This paper proposes a low density separation density sensitive distance-based spectral clustering algorithm.First,the algorithm applies the low-density separation density sensitive distance to calculate the similarity matrix.By the exponential function and flexibility factor,we can achieve increasing the distance between different manifold data and decreasing the distance between the same manifold data,which can effectively reflect the global consistency and local consistency of data distribution.In addition,by adding relative density sensitive term to take into account the local distribution characteristics of the data,isolated noise and"bridge"noise are effectively avoided.Finally,we provide the method of selecting k-value of k nearest neighbor graph based on SC(Scattering criteria)index and the method of extracting eigenvector based on spectral entropy contribution rate.In the experimental part,the effect of parameter selection on the performance of the proposed technique is discussed and some suggestions about the determination of the parameters are given.Compared with the state-of-the-art spectral clustering algorithms,the analysis results demonstrate that the proposed low density separation density sensitive distance-based spectral clustering algorithm performs well on artificial and UCI benchmark datasets.