基于K阈值的谱聚类算法

Spectral Clustering Algorithm Based on K-Threshold

摘要: 在传统的NJW谱聚类算法中，样本间的相似性度量由欧式距离和高斯核函数公共决定；而欧式距离是基于整个样本集合的，忽略了局部样本之间的关连；且高斯核函数的值也是通过多次实验获得，容易陷入局部最优使得聚类结果大受影响。针对以上问题，提出了一种新的谱聚类算法，算法引入K邻域、最短路径以及标准差的概念；重建样本间的相似性度量的参数，并且用样本标准差重新构建样本间的联系进而修正高斯核函数的值，使其更接近样本本身的特性。通过实验分析，该算法不但继承了谱聚类算法的收敛于全局的特性，适用于各种形状的数据，而且还克服了欧式距离和高斯核函数造成的相似性度量的局限，提高了算法准确率，增强聚类结果的可信度。

Abstract: In the traditional NJW spectral clustering algorithm, similarity measurement between samples is determined by Euclidean distance and Gaussian kernel function. Euclidean distance is based on the whole sample set, ignoring the correlation between local samples. Moreover, the value of Gaussian kernel function is also obtained through multiple experiments, which is easy to fall into local optimization and greatly affects the clustering results. Aiming at the above problems, a new spectral clustering algorithm is proposed, which introduces the concepts of K neighborhood, shortest path and standard deviation. The parameters of similarity measurement between samples are reconstructed, and the relationship between samples is reconstructed with sample standard deviation, so as to modify the value of Gaussian kernel function and make it closer to the characteristics of samples. Through the experimental analysis, the algorithm not only inherits the convergence of spectral clustering algorithm to the whole world, and is applicable to data of various shapes, but also overcomes the limitations of similarity measurement caused by Euclidean distance and Gaussian kernel function, improves the accuracy of the algorithm, and enhances the reliability of clustering results.