A heuristic k-means clustering algorithm by kernel pca

Abstract

K-means clustering utilizes an iterative procedure that converges to local minima. This local minimum is highly sensitive to the selected initial partition for the K-means clustering. To overcome this difficulty, we present a heuristic K-means clustering algorithm based on a scheme for selecting a suboptimal initial partition. The selected initial partition is estimated by applying dynamic programming in a nonlinear principal direction. In other words, an optimal partition of data samples in the kernel principal direction is selected as the initial partition for the K-means clustering. Experiment results show that the proposed algorithm outperforms the PCA based K-means clustering algorithm and the kd-tree based K-means clustering algorithm respectively.