Local density-based similarity matrix construction for spectral clustering

被引：1

作者：

Wu, Jian ^{[1
]}

Cui, Zhi-Ming ^{[1
]}

Shi, Yu-Jie ^{[1
]}

Sheng, Sheng-Li ^{[2
]}

Gong, Sheng-Rong ^{[1
]}

机构：

[1] Institute of Intelligent Information Processing and Application, Soochow University

[2] Department of Computer Science, University of Central Arkansas

来源：

Tongxin Xuebao/Journal on Communications | 2013年 / 34卷 / 03期

关键词：

Edge betweenness; Local density; Similarity matrix; Spectral clustering; Undirected graph building;

D O I：

10.3969/j.issn.1000-436x.2013.03.003

中图分类号：

学科分类号：

摘要：

According to local and global consistency characteristics of sample data points' distribution, a spectral clustering algorithm using local density-based similarity matrix construction was proposed. Firstly, by analyzing distribution characteristics of sample data points, the definition of local density was given, sorting operation on sample point set from dense to sparse according to sample points' local density was did, and undirected graph in accordance with the designed connection strategy was constructed; then, on the basis of GN algorithm's thinking, a calculation method of weight matrix using edge betweenness was given, and similarity matrix of spectral clustering via data conversion was got; lastly, the class number by appearing position of the first eigengap maximum was determined, and the classification of sample point set in eigenvector space by means of classical clustering method was realized. By means of artificial simulative data set and UCI data set to carry out the experimental tests, results show that the proposed spectral algorithm has better clustering capability.

引用

页码：14 / 22

页数：8

共 16 条

[1]

Cristianini N., Shawe-Taylor J., Kandola J., Spectral kernel methods for clustering, Proceedings of the 13th Advances in Neural Information Processing Systems (NIPS 2001, pp. 649-655, (2001)

[2]

Ng A.Y., Jordan M.I., Weiss Y., On spectral clustering: Analysis and an algorithm, Proceedings of the 14th Advances in Neural Information Processing Systems (NIPS 2002), pp. 849-856, (2002)

[3]

Deng X.Z., Jiao L.C., Lu S., Spectral clustering ensemble applied to SAR image segmentation using nonnegative matrix factorization, Acta Electronica Sinica, 39, 12, pp. 2905-2909, (2011)

[4]

Ducournau A., Bretto A., Rital S., Et al., A reductive approach to hypergraph clustering: An application to image segmentation, Pattern Recognition, 45, 7, pp. 2788-2803, (2012)

[5]

Xu S., Lu Z.M., Gu G.C., Spectral clustering algorithms for document cluster ensemble problem, Journal on Communications, 31, 6, pp. 58-66, (2010)

[6]

Zhang T.P., Tang Y.Y., Fang B., Et al., Document clustering in correlation similarity measure space, IEEE Transactions on Knowledge and Data Engineering, 24, 6, pp. 1002-1013, (2012)

[7]

Luxburg U.V., A tutorial on spectral clustering, Statistics and Computing, 17, 4, pp. 395-416, (2007)

[8]

Li J.Y., Zhou J.G., Guan J.H., Et al., A survey of clustering algorithms based on spectra of graphs, CAAI Transactions on Intelligent Systems, 6, 5, pp. 405-414, (2011)

[9]

Wang L., Bo L.F., Jiao L.C., Density-sensitive spectral clustering, Acta Electronica Sinica, 35, 8, pp. 1577-1581, (2007)

[10]

Kong W.Z., Sun Z.H., Yang C., Et al., Automatic spectral clustering based on eigengap and orthogonal eigenvector, Acta Electronica Sinica, 38, 8, pp. 1880-1891, (2010)

← 1 2 →