A heuristic K-means clustering algorithm by kernel PCA

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 kemel 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.