članak: 1 od 1  
Computer Science and Information Systems / ComSIS
2011, vol. 8, br. 4, str. 1143-1157
jezik rada: engleski
članak
doi:10.2298/CSIS110415064L
An improved spectral clustering algorithm based on local neighbors in kernel space
(naslov ne postoji na srpskom)
Liu Xinyuea, Yong Xingb, Lin Hongfeic
aSchool of Computer Science and Technology, Dalian University of Technology, Dalian, China + School of Software, Dalian University of Technology, Dalian, China
bSchool of Software, Dalian University of Technology, Dalian, China
cSchool of Computer Science and Technology, Dalian University of Technology, Dalian, China

e-adresa: xyliu@dlut.edu.cn

Sažetak

(ne postoji na srpskom)
Similarity matrix is critical to the performance of spectral clustering. Mercer kernels have become popular largely due to its successes in applying kernel methods such as kernel PCA. A novel spectral clustering method is proposed based on local neighborhood in kernel space (SC-LNK), which assumes that each data point can be linearly reconstructed from its neighbors. The SC-LNK algorithm tries to project the data to a feature space by the Mercer kernel, and then learn a sparse matrix using linear reconstruction as the similarity graph for spectral clustering. Experiments have been performed on synthetic and real world data sets and have shown that spectral clustering based on linear reconstruction in kernel space outperforms the conventional spectral clustering and the other two algorithms, especially in real world data sets.

Ključne reči

spectral clustering; kernel space; local neighbors; linear reconstruction

Reference

Asuncion, A., Newman, D. (2007) UCI machine learning repository. http://www.ics.uci.edu/~mlearn /ML Repository.html

KoBSON

Ben-Hur, A., Horn, D., Siegelmann, H., Vapnik, V. (2002) Support vector clustering. Journal of Machine Learning Research, vol. 2, str. 137

de Coste, D. (2001) Visualizing Mercel kernel feature spaces via kernelized locally linear embedding. u: International conference on neural information processing (VIII), ICONIP-01, proceedings

KoBSON

Girolami, M. (2002) Mercer kernel-based clustering in feature space. IEEE Transactions on Neural Networks, vol. 13, br. 3. 780-784

Gong, Y., Chen, C. (2008) Locality spectral clustering. Advances in Artificial Intelligence, 2008, str. 348-354

Hagen, L., Kahng, B. (1992) New spectral methods for ratio cut partitioning and clustering. IEEE Transactions on computer aided design, vol. 11, br. 9

Jianbo, S., Yu, S., Shi, J. (2003) Multiclass spectral clustering. u: International conference on computer vision, Citeseer, str. 313-319

Jordan, F., Bach, F. (2004) Learning spectral clustering. u: Advances in neural information processing systems (XVI), 2003 conference, proceedings, The MIT Press, vol. 16, 305

Li, Z., Liu, J., Tang, X. (2009) Constrained clustering via spectral regularization. u: Computer vision and pattern recognition, str. 421-428

CrossRefMathSciNetKoBSON1

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

Meila, M., Shi, J. (2001) A random walks view of spectral segmentation. u: AI and statistics, AISTATS, vol. 2001

Ng, A., Jordan, M., Weiss, Y. (2001) On spectral clustering: Analysis and an algorithm. u: Advances in neural information processing systems (IX), conference proceeding, str. 849-856

KoBSON

Ozertem, U., Erdogmus, D., Jenssen, R. (2008) Mean shift spectral clustering. Pattern Recognition, vol. 41, br. 6, 1924-1938

KoBSON

Rand, W. (1971) Objective criteria for the evaluation of clustering methods. Journal of the American Statistical association, 846-850

CrossRefPubMedKoBSON2

Roweis, S.T., Saul, L.K. (2000) Nonlinear dimensionality reduction by locally linear embedding. Science, 290(5500): 2323-6

1

Scholkopf, B., Smola, A.J., Muller, K.R. (1997) Kernel principal component analysis. u: Proceedings of International Conference on Artificial Neural Networks, str. 583

CrossRefKoBSON2

Shi, J., Malik, J. (2000) Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8): 888-905

KoBSON

Strehl, A., Ghosh, J. (2003) Cluster ensembles-a knowledge reuse framework for combining multiple partitions. Journal of Machine Learning Research, vol. 3, 583-617

KoBSON

Wang, F., Zhang, C. (2007) Label propagation through linear neighborhoods. IEEE Transactions on Knowledge and Data Engineering, 55-67

Wang, X., Davidson, I. (2010) Active spectral clustering. u: IEEE international conference on data mining, str. 561-568

KoBSON

Xia, T., Cao, J., Zhang, Y., Li, J. (2009) On defining affinity graph for spectral clustering through ranking on manifolds. Neurocomputing, vol. 72, br. 13-15, 3203-3211

1

Zelnik-Manor, L., Perona, P. (2004) Self-tuning spectral clustering. Advances in neural information processing systems, vol. 17, br. 1601-1608, str. 16

KoBSON

Zhang, X., Li, J., Yu, H. (2010) Local density adaptive similarity measurement for spectral clustering. Pattern Recognition Letters

1

Zhou, D., Bousquet, O., Lal, T., Weston, J., Schölkopf, B. (2004) Learning with local and global consistency. u: Advances in neural information processing systems (XVI), 2003 conference, proceedings, str. 595-602