[1]ZHAO Xiaoxiao,ZHOU Zhiping.A semi-supervised spectral clustering algorithm combined with sparse representation and constraint propagation[J].CAAI Transactions on Intelligent Systems,2018,13(5):855-863.[doi:10.11992/tis.201703013]
Copy

A semi-supervised spectral clustering algorithm combined with sparse representation and constraint propagation

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 13 Number of periods: 2018 5 Page number: 855-863 Column: 学术论文—机器学习 Public date: 2018-09-05
Title:
A semi-supervised spectral clustering algorithm combined with sparse representation and constraint propagation
Author(s):
ZHAO Xiaoxiao;  ZHOU Zhiping
Engineering Research Center of Internet of Things Technology Applications Ministry of Education, Jiangnan University, Wuxi 214122, China
Keywords:
data mining; cluster analysis; spectral clustering; semi-supervised learning; sparse representation; constraint propagation
CLC:
TP18
DOI:
10.11992/tis.201703013
Abstract:
The semi-supervised spectral clustering algorithm does not deal with large-scale datasets effectively and does not fully utilize the constraint information because it does not consider the constraint propagation. To address these drawbacks, this paper proposes a semi-supervised spectral clustering algorithm that combines sparse representation and constraint propagation. The algorithm first generates the constraint matrix according to the constraint information, introduces it into the spectral clustering, and then constructs a sparse representation matrix by taking the data points in the constrained sets as the landmarks to approximate the graph similarity matrix, thereby revising the constrained spectral clustering model. Meanwhile, the connected region is generated according to the similarity matrix of the landmark data points, and the neighboring nodes are dynamically adjusted in each connected region. The clustering accuracy is further improved using the constraint propagation. Experimental results show that the proposed method is more efficient than constrained spectral clustering algorithms, and their accuracy levels are similar. Moreover, its clustering accuracy exceeds those of the fast spectral clustering algorithms.
References:
[1] VON Luxburg U. A tutorial on spectral clustering[J]. Statistics and computing, 2007, 17(4):395-416.
[2] SHI Jianbo, MALIK J. Normalized cuts and image segmentation[J]. IEEE transactions on pattern analysis and machine intelligence, 2000, 22(8):888-905.
[3] HU Han, FENG Jianjiang, YU Chuan, et al. Multi-class constrained normalized cut with hard, soft, unary and pairwise priors and its applications to object segmentation[J]. IEEE transactions on image processing, 2013, 22(11):4328-4340.
[4] 刘建伟, 刘媛, 罗雄麟. 半监督学习方法[J]. 计算机学报, 2015, 38(8):1592-1617 LIU Jianwei, LIU Yuan, LUO Xionglin. semi-supervised learning methods[J]. Chinese journal of computers, 2015, 38(8):1592-1617
[5] ALUSH A, FRIEDMAN A, Goldberger J. Pairwise clustering based on the mutual-information criterion[J]. Neurocomputing, 2016, 182:284-293.
[6] FORESTIER G, WEMMERT C. Semi-supervised learning using multiple clusterings with limited labeled data[J]. Information sciences, 2016, 361-362:48-65.
[7] KAMVAR S D, KLEIN D, MANNING C D. Spectral learning[C]//Proceedings of the 18th International Joint Conference on Artificial Intelligence. Acapulco, Mexico, 2003:561-566.
[8] 蒋伟进, 许宇晖, 王欣. 基于谱图和成对约束的主动半监督聚类算法[J]. 控制与决策, 2013, 28(6):904-908 JIANG Weijin, XU Yuhui, WANG Xin. Active semi-supervised clustering algorithm based-on pair-wise constraints[J]. Control and decision, 2013, 28(6):904-908
[9] DING Shifei, JIA Hongjie, ZHANG Liwen, et al. Research of semi-supervised spectral clustering algorithm based on pairwise constraints[J]. Neural computing and applications, 2014, 24(1):211-219.
[10] CUCURINGU M, KOUTIS I, CHAWLA S, et al. Simple and scalable constrained clustering:a generalized spectral method[C]//Proceedings of the 19th International Conference on Artificial Intelligence and Statistics. Cadiz, Spain, 2016:445-454.
[11] WANG Xiang, QIAN Buyue, DAVIDSON I. On constrained spectral clustering and its applications[J]. Data mining and knowledge discovery, 2014, 28(1):1-30.
[12] YU Zhiwen, LUO Peinan, YOU J, et al. Incremental semi-supervised clustering ensemble for high dimensional data clustering[J]. IEEE transactions on knowledge and data engineering, 2016, 28(3):701-714.
[13] LU Zhiwu, PENG Yuxin. Exhaustive and efficient constraint propagation:a graph-based learning approach and its applications[J]. International journal of computer vision, 2013, 103(3):306-325.
[14] CAI Deng, CHEN Xinlei. Large scale spectral clustering via landmark-based sparse representation[J]. IEEE transactions on cybernetics, 2015, 45(8):1669-1680.
[15] SEMERTZIDIS T, RAFAILIDIS D, STRINTZIS M G, et al. Large-scale spectral clustering based on pairwise constraints[J]. Information processing and management, 2015, 51(5):616-624.
Similar References:

Memo

-

Last Update: 2018-10-25

Copyright © CAAI Transactions on Intelligent Systems