基于共享近邻的成对约束谱聚类算法
|
摘要
谱聚类算法是基于谱图划分理论的一种机器学习算法,它能在任意形状的样本空间上聚类且收敛于全局最优解。但是传统的谱聚类算法很难正确发现密度相差比较大的簇,参数的选取要靠多次实验和个人经验。结合半监督聚类的思想,在给出一部分监督信息的前提下,提出了一种基于共享近邻的成对约束谱聚类算法(Pairwise Constrained Spectral Clustering Based on Shared Nearest Neighborhood,PCSC-SN)。PCSC-SN算法是用共享近邻去衡量数据对之间的相似性,用主动约束信息找到两个数据点之间的关系。在数据集UCI上做了一系列的实验,实验结果证明,与传统的聚类算法相比,PCSC-SN算法能够获得更好的聚类效果。
The spectral clustering algorithm is a machine learning algorithm based on the theory of spectral partitioning.It can cluster on any shape of the sample space and converge to the global optimal solution. However, the traditional spectral clustering algorithm is difficult to find out the large density difference clusters, the choice of parameters depends on multiple tests and personal experience. Combined with the idea of semi-supervised clustering, a pair of constrained spectral clustering algorithm based on shared neighbors(PCSC-SN)is proposed under the premise of giving some supervisory information. The PCSC-SN algorithm uses a shared neighbor to measure the similarity between data pairs, and uses the active constraint information to find the relationship between two data points. A series of experiments are done on the data set UCI. The experimental results show that this algorithm can obtain better clustering effect compared with the traditional clustering algorithm.
The spectral clustering algorithm is a machine learning algorithm based on the theory of spectral partitioning.It can cluster on any shape of the sample space and converge to the global optimal solution. However, the traditional spectral clustering algorithm is difficult to find out the large density difference clusters, the choice of parameters depends on multiple tests and personal experience. Combined with the idea of semi-supervised clustering, a pair of constrained spectral clustering algorithm based on shared neighbors(PCSC-SN)is proposed under the premise of giving some supervisory information. The PCSC-SN algorithm uses a shared neighbor to measure the similarity between data pairs, and uses the active constraint information to find the relationship between two data points. A series of experiments are done on the data set UCI. The experimental results show that this algorithm can obtain better clustering effect compared with the traditional clustering algorithm.
引文
[1]蔡晓妍,戴冠中,杨黎斌.谱聚类算法综述[J].计算机科学,2008,35(7):14-18.
[2]Shi J,Malik J.Normalized cuts and image segmentation[J].IEEE Transactions on Pattern Analysis&Machine Intelligence,2000,22(8):888-905.
[3]田铮,李小斌,句彦伟.谱聚类的扰动分析[J].中国科学:技术科学,2007,37(4):527-543.
[4]Wagstaff K,Cardie C.Clustering with instance-level constraints[C]//Seventeenth International Conference on Machine Learning,2000:1103-1110.
[5]Wang X,Davidson I.Flexible constrained spectral clustering[C]//ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2010:563-572.
[6]Baghshah M S,Afsari F,Shouraki S B,et al.Scalable semi-supervised clustering by spectral kernel learning[J].Pattern Recognition Letters,2014,45(8):161-171.
[7]Wagstaff K,Cardie C,Rogers S,et al.Constrained K-means clustering with background knowledge[C]//Eighteenth International Conference on Machine Learning,2001:577-584.
[8]Xiao Yu.Semi-supervised clustering based on affinity propagation algorithm[J].Journal of Software,2008,19(11):2803-2813.
[9]Graham E D,Heidelberg J F,Tully B J.BinSanity:unsupervised clustering of environmental microbial assemblies using coverage and affinity propagation[J].PeerJ,2017,5:e3035.
[10]Lee J M.Fast k-nearest neighbor searching in static objects[J].Wireless Personal Communications,2017,93:147-160.
[11]Li J Y,Zhou J,Guan J,et al.A survey of clustering algorithms based on spectra of graphs[J].CAAI Transactions on Intelligent Systems,2011,6(5):405-414.
[12]Yin Xuesong.Discriminative semi-supervised clustering analysis with pairwise constraints[J].Journal of Software,2008,19(11):2791-2802.
[13]Kamvar S D,Dan K,Manning C D.Spectral learning[C]//International Joint Conference of Artificial Intelligence,2003:561-566.
[14]Lu Z,Carreiraperpinan M A.Constrained spectral clustering through affinity propagation[C]//2008 IEEE Conference on Computer Vision and Pattern Recognition,2008:1-8.
[15]Coleman T,Saunderson J,Wirth A.Spectral clustering with inconsistent advice[C]//International Conference on Machine Learning,2008:152-159.
[16]Luxburg U.A tutorial on spectral clustering[J].Statistics and Computing,2007,17(4):395-416.
[17]Jia H J,Ding S F,Du M.Self-tuning p-spectral clustering based on shared nearest neighbors[J].Cognitive Computation,2015,7(5):622-632.
[2]Shi J,Malik J.Normalized cuts and image segmentation[J].IEEE Transactions on Pattern Analysis&Machine Intelligence,2000,22(8):888-905.
[3]田铮,李小斌,句彦伟.谱聚类的扰动分析[J].中国科学:技术科学,2007,37(4):527-543.
[4]Wagstaff K,Cardie C.Clustering with instance-level constraints[C]//Seventeenth International Conference on Machine Learning,2000:1103-1110.
[5]Wang X,Davidson I.Flexible constrained spectral clustering[C]//ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2010:563-572.
[6]Baghshah M S,Afsari F,Shouraki S B,et al.Scalable semi-supervised clustering by spectral kernel learning[J].Pattern Recognition Letters,2014,45(8):161-171.
[7]Wagstaff K,Cardie C,Rogers S,et al.Constrained K-means clustering with background knowledge[C]//Eighteenth International Conference on Machine Learning,2001:577-584.
[8]Xiao Yu.Semi-supervised clustering based on affinity propagation algorithm[J].Journal of Software,2008,19(11):2803-2813.
[9]Graham E D,Heidelberg J F,Tully B J.BinSanity:unsupervised clustering of environmental microbial assemblies using coverage and affinity propagation[J].PeerJ,2017,5:e3035.
[10]Lee J M.Fast k-nearest neighbor searching in static objects[J].Wireless Personal Communications,2017,93:147-160.
[11]Li J Y,Zhou J,Guan J,et al.A survey of clustering algorithms based on spectra of graphs[J].CAAI Transactions on Intelligent Systems,2011,6(5):405-414.
[12]Yin Xuesong.Discriminative semi-supervised clustering analysis with pairwise constraints[J].Journal of Software,2008,19(11):2791-2802.
[13]Kamvar S D,Dan K,Manning C D.Spectral learning[C]//International Joint Conference of Artificial Intelligence,2003:561-566.
[14]Lu Z,Carreiraperpinan M A.Constrained spectral clustering through affinity propagation[C]//2008 IEEE Conference on Computer Vision and Pattern Recognition,2008:1-8.
[15]Coleman T,Saunderson J,Wirth A.Spectral clustering with inconsistent advice[C]//International Conference on Machine Learning,2008:152-159.
[16]Luxburg U.A tutorial on spectral clustering[J].Statistics and Computing,2007,17(4):395-416.
[17]Jia H J,Ding S F,Du M.Self-tuning p-spectral clustering based on shared nearest neighbors[J].Cognitive Computation,2015,7(5):622-632.