A Heuristic K-Means Clustering Algorithm by Kernel PCA (WP-P8)

Author(s) : Mantao Xu (University of Joensuu, Finland) Pasi Fränti (University of Joensuu, Finland)

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, i.e. the kernel principal component. 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.

Menu