基于约束优化传播的改进大规模数据半监督式谱聚类算法

Constrain optimal propagation-based improved semi-supervised spectral clustering algorithm for large-scale data

针对传统谱聚类算法在聚类过程中所出现的高计算复杂度、噪声敏感,以及聚类簇形态偏斜等问题,结合当前大规模数据聚类的特点与需求,建立基于约束优化传播的改进大规模数据半监督式谱聚类模型。该模型利用先验成对点约束信息构建微型相似性矩阵,在此基础上采用Gabow算法提取该微型相似性矩阵所对应连通图的各强连通分支,继而提出面向各强连通分支的新型约束优化传播算法以获取整个数据集的点对相似度,最后通过奇异值分解并运用加速K-means算法获得大规模数据的聚类结果。在多个标准测试数据集上的实验表明,相比于该领域其他前期研究成果,该聚类模型具有更高的聚类准确率和更低的计算复杂度,更适合大规模数据的聚类应用。

Focusing on the problem of high computational complexity,noise sensitivity and the shape deviation of cluster in the clustering process of traditional spectral clustering,and combining the characteristics with the need of current large-scale data clustering,this article established the semi-supervised of large-scale data model based on constrained optimal propagation.First,it constructed the micro similarity matrix by using prior dotted pair constraint information.On this basis,it used the Gabow algorithm to extract the micro similarity matrix corresponding connected graph of each strongly connected component.Then,it proposed a new constrained optimization propagation algorithm for each strongly connected component to obtained the similarity of the point of the whole data set.Finally,it could obtain the clustering results of large scale data by using the singular value decomposition and the accelerated K-means algorithm.Experiments on multiple standard testing data sets show that compared with other previous research results in this field,the proposed clustering model has higher clustering accuracy and lower computation complexity and is more suitable for large-scale data clustering applications.