Fast Spectral Clustering Based on Anchor Point Extraction with Bisecting k-means

doi:10.3778/j.issn.1002-8331.2205-0036

Abstract

Abstract: Spectral clustering（SC） has received increasing attention due to its effectiveness in unsupervised learning. However, due to its high computational complexity, it is not suitable for processing large-scale data. In recent years, many anchor points graph-based methods have been proposed to accelerate large-scale spectral clustering. However, the anchor points selected by these methods usually cannot well reflect the information of the original data, which leads to the degradation of clustering performance. To overcome these shortcomings, a fast spectral clustering algorithm based on anchor point extraction with bisecting [k]-means（FCAPBK） is proposed. The method uses bisecting [k]-means to select some representative anchor points from the original data, then constructs a multi-layer kernel-free similarity graph based on anchor points, and constructs a hierarchical bipartite graphs through the similar relationship between the anchor points and the sample. Finally, experiments are carried out on five benchmark datasets, and the results show that the FCAPBK method can obtain good clustering performance in a short time.

Key words: bisecting k-means, bipartite graphs, anchor points, spectral clustering

摘要： 光谱聚类（spectral clustering，SC）由于在无监督学习中的有效性而受到越来越多的关注。然而其计算复杂度高，不适用于处理大规模数据。近年来提出了许多基于锚点图方法来加速大规模光谱聚类，然而这些方法选取的锚点通常不能很好地体现原始数据的信息，从而导致聚类性能下降。为克服这些缺陷，提出了一种二分[k]-means锚点提取的快速谱聚类算法（fast spectral clustering algorithm based on anchor point extraction with bisecting [k]-means，FCAPBK）。该方法利用二分[k]-means从原始数据中选取一些具有代表性的锚点，构建基于锚点的多层无核相似图；然后通过锚点与样本间的相似关系构造层次二部图。最后在5个基准数据集上分别进行实验验证，结果表明FCAPBK方法能够在较短的时间内获得良好的聚类性能。

关键词: 二分k-means, 二部图, 锚点图, 谱聚类

LUO Xinglong, HE Xingshi, YANG Xinshe. Fast Spectral Clustering Based on Anchor Point Extraction with Bisecting k-means[J]. Computer Engineering and Applications, 2023, 59(16): 74-81.

罗兴隆, 贺兴时, 杨新社. 二分k-means锚点提取的快速谱聚类[J]. 计算机工程与应用, 2023, 59(16): 74-81.

References

[1] FAYYAD U，PIATETSKY-SHAPIRO G，SMYTH P.From data mining to knowledge discovery in databases[J].AI Magazine，1996，17（3）：37.
[2] JAIN A K，MURTY M N，FLYNN P J.Data clustering：a review[J].ACM Computing Surveys，1999，31（3）：264-323.
[3] HASTIE T，TIBSHIRANI R，FRIEDMAN J.The elements of statistical learning[M].New York：Springer Series in Statistics，2001.
[4] CHANG X，YANG Y.Semisupervised feature analysis by mining correlations among multiple tasks[J].IEEE Transactions on Neural Networks and Learning Systems，2016，28（10）：2294-2305.
[5] CHANG X，YU Y L，YANG Y，et al.Semantic pooling for complex event analysis in untrimmed videos[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2016，39（8）：1617-1632.
[6] WANG M，FU W，HAO S，et al.Learning on big graph：label inference and regularization with anchor hierarchy[J].IEEE Transactions on Knowledge and Data Engineering，2017，29（5）：1101-1114.
[7] GAO Q，MA L，LIU Y，et al.Angle 2DPCA：a new formulation for 2DPCA[J].IEEE Transactions on Cybernetics，2017，48（5）：1672-1678.
[8] GAO Q，XU S，CHEN F，et al.R1-2-DPCA and face recognition[J].IEEE Transactions on Cybernetics，2018，49（4）：1212-1223.
[9] NIE F，ZHU W，LI X.Unsupervised large graph embedding[C]//Proceedings of the 31st AAAI Conference on Artificial Intelligence，2017：2422-2428.
[10] LI Y，NIE F，HUANG H，et al.Large-scale multi-view spectral clustering via bipartite graph[C]//Proceedings of the 29th AAAI Conference on Artificial Intelligence，2015：2750-2756.
[11] ZHANG K，KWOK J T，PARVIN B.Prototype vector machine for large scale semi-supervised learning[C]//Proceedings of the 26th Annual International Conference on Machine Learning，2009：1233-1240.
[12] LIU W，HE J，CHANG S F.Large graph construction for scalable semi-supervised learning[C]//Proceedings of the 27th International Conference on Machine Learning，2010：679-686.
[13] WANG M，FU W，HAO S，et al.Scalable semi-supervised learning by efficient anchor graph regularization[J].IEEE Transactions on Knowledge and Data Engineering，2016，28（7）：1864-1877.
[14] FOWLKES C，BELONGIE S，CHUNG F，et al.Spectral grouping using the Nystrom method[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2004，26（2）：214-225.
[15] LI M，KWOK J T Y，LU B.Making large-scale Nystr?m approximation possible[C]//Proceedings of the 27th International Conference on Machine Learning，2010：631-638.
[16] SHINNOU H，SASAKI M.Spectral clustering for a large data set by reducing the similarity matrix size[C]//Proceedings of the 2008 International Conference on Language Resources and Evaluation，2008：201-204.
[17] YAN D，HUANG L，JORDAN M I.Fast approximate spectral clustering[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，Paris，2009：907-916.
[18] CHEN B，GAO B，LIU T Y，et al.Fast spectral clustering of data using sequential matrix compression[C]//Proceedings of the 17th European Conference on Machine Learning.Berlin，Heidelberg：Springer，2006：590-597.
[19] LIU T Y，YANG H Y，ZHENG X，et al.Fast large-scale spectral clustering by sequential shrinkage optimization[C]//Proceedings of the 29th European Conference on Information Retrieval.Berlin，Heidelberg：Springer，2007：319-330.
[20] NG A Y，JORDAN M I，WEISS Y.On spectral clustering：analysis and an algorithm[C]//Advances in Neural Information Processing Systems，2001：849-856.
[21] KANG Z，PENG C，CHENG Q，et al.Unified spectral clustering with optimal graph[C]//Proceedings of the 32nd AAAI Conference on Artificial Intelligence，2018.
[22] 左进，陈泽茂.基于改进K均值聚类的异常检测算法[J].计算机科学，2016，43（8）：258-261.
ZUO J，CHEN Z M.Anomaly detection algorithm based on improved k-means clustering[J].Computer Science，2016，43（8）：258-261.
[23] XIA S，PENG D，MENG D，et al.A fast adaptive k-means with no bounds[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2022，44（1）：87-99.
[24] DUAN Y，LIU Q，XIA S.An improved initialization center k-means clustering algorithm based on distance and density[C]//Proceedings of the 2nd International Conference on Advances in Materials，Machinery，Electronics，2018，1955：040046.
[25] DING Y，ZHAO Y，SHEN X，et al.Yinyang k-means：a drop-in replacement of the classic k-means with consistent speedup[C]//Proceedings of the 32nd International Conference on Machine Learning，2015：579-587.
[26] SILVA J D A，HRUSCHKA E R.Extending k-means based algorithms for evolving data streams with variable number of clustering[C]//2011 10th International Conference on Machine Learning and Applications and Workshops，2011，2：14-19.
[27] NIE F，WANG X，JORDAN M，et al.The constrained Laplacian rank algorithm for graph-based clustering[C]//Proceedings of the 30th AAAI Conference on Artificial Intelligence，2016：1969-1976.
[28] YANG X，YU W，WANG R，et al.Fast spectral clustering learning with hierarchical bipartite graph for large-scale data[J].Pattern Recognition Letters，2020，130：345-352.
[29] WANG R，NIE F，HONG R，et al.Fast and orthogonal locality preserving projections for dimensionality reduction[J].IEEE Transactions on Image Processing，2017，26（10）：5019-5030.
[30] ZHOU D，BOUSQUET O，LAL T，et al.Learning with local and global consistency[C]//Proceedings of the 16th International Conference on Neural Information Processing Systems，2003：321-328.
[31] CHEN W Y，SONG Y，BAI H，et al.Parallel spectral clustering in distributed systems[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，33（3）：568-586.
[32] ZHU W，NIE F，LI X.Fast spectral clustering with efficient large graph construction[C]//2017 IEEE International Conference on Acoustics，Speech and Signal Processing，2017：2492-2496.