Adaptive Dimension Reduction for Clustering High Dimensional Data

It is well-known that for high dimensional data cluster-ing, standard algorithms such as EM and the K-means are often trapped in local minimum. Many initialization methods were proposed to tackle this problem, but with only limited success. In this paper we propose a new approach to resolve this problem by repeated dimen-sion reductions such that K-means or EM are performed only in very low dimensions. Cluster membership is uti-lized as a bridge between the reduced dimensional sub-space and the original space, providing exibility and ease of implementation. Clustering analysis performed on highly overlapped Gaussians, DNA gene expression pro les and internet newsgroups demonstrate the eec-tiveness of the proposed algorithm.