From Whole to Part: Reference-Based Representation for Clustering Categorical Data

Dissimilarity measures play a crucial role in clustering and, are directly related to the performance of clustering algorithms. However, effectively measuring the dissimilarity is not easy, especially for categorical data. The main difficulty of the dissimilarity measurement for categorical data is that its representation lacks a clear space structure. Therefore, the space structure-based representation has been proposed to provide the categorical data with a clear linear representation space. This representation improves the clustering performance obviously but only applies to small data sets because its dimensionality increases rapidly with the size of the data set. In this paper, we investigate the possibility of reducing the dimensionality of the space structure-based representation while maintaining the same representation ability. A lightweight representation scheme is proposed by taking a set of representative objects as the reference system (called the reference set) to position other objects in the Euclidean space. Moreover, a preclustering-based strategy is designed to select an appropriate reference set quickly. Finally, the representation scheme together with the k-means algorithm provides an efficient method to cluster the categorical data. The theoretical and the experimental analysis shows that the proposed method outperforms state-of-the-art methods in terms of both accuracy and efficiency.