Abstract: In real applications in pattern recognition and computer vison, high dimensional data always lie approximately on a low dimensional manifold. How to improve the performance of clustering algorithm on high dimensional data by using the manifold structure is a research hotspot in machine learning and data mining community. In this paper, a novel clustering algorithm called Nonlinear Discriminant K-means Clustering (NDisKmeans), which has taken the manifold structure of high dimensional into account, is proposed. By introducing the spectracl regularization technology, NDisKmeans first represents the desired low dimensional coordinates as linear combinations of smooth vectors predefined on the data manifold; then maximizes the ratio between inter-clusters scatter and total scatter to cluster the high dimensional data. A convergent iterative procedure is devised to solute the matrix of the combination coefficient and clustering assignment matrix. NDisKmeans overcomes the limilation of linear mapping of DisKmeans algorithm; therefore, it significantly improves the clustering performance. The systematic and extensive experiments on UCI and real world data sets have shown the effectiveness of the proposed NDisKmeans method.

Key words: clustering, manifold, K-means clustering, spectral regularization, spectral clustering

摘要： 为提高具有流形结构的高维数据的聚类性能，提出非线性判别K均值聚类算法(NDisKmeans)。该方法通过引入流形上的谱正则化技术，将数据的低维嵌入表示成数据流形上平滑函数的线性组合，然后通过最大化低维空间中聚类类间的散度与总体散度的比值，来实现对高维数据的聚类。还设计了一种收敛的迭代求解方法来求解最优组合系数矩阵和聚类赋值矩阵。NDisKmeans方法由于考虑了数据的流形结构，克服了判别K均值算法中线性映射的不足，从而提高了对高维数据聚类的性能。最后在数据集上的广泛实验表明，NDisKmeans方法能有效实现对高维数据的聚类。

关键词: 聚类, 流形, K均值聚类, 谱正则化, 谱聚类