Clustering via Dimension Extension and Pseudo-inverse Transformation

Abstract

Partitional clustering has a major drawback in that once some data have been divided into wrong clusters, they cannot be easily adjusted into the correct one, namely the initialization problem that plagues the k-means algorithm. This paper presents a novel approach which incorporates Dimension Extension and Pseudo-Inverse Transformation (DEPIT) to realize data clustering. Unlike k-means algorithm, DEPIT needs not pre-specify the number of clusters k, centroids locations are updated and redundant centroids eliminated automatically during iterative training process. The essence of DEPIT is that clustering is performed by pseudo-inverse transforming the input data such that each data point is represented by a linear combination of bases with extended dimension, with each basis corresponding to a centroid and its coefficient representing the closeness between the data point and the basis. Issue of clustering validation is also addressed in this paper. First, Principal Component Analysis is applied to detect if there exists a dominated dimension, if so, the original input data will be rotated by a certain angle w.r.t. a defined center of mass, and the resulting data undergo another run of iterative training process. After plural runs of rotation and iterative process, the labeled results from various runs are compared, a data point labeled to a centroid more times than others will be labeled to the class indexed by that wining centroid.