A fast and effective partitional clustering algorithm for large categorical datasets using a k-means based approach

Partitional clustering algorithms represent an interesting issue in pattern recognition due to their high scalability and efficiency. The k-means, proposed since 1965, had shown great efficiency for numeric clustering but is unfortunately inadequate for categorical clustering. In 1998, the k-modes was proposed as an extension of the k-means to cluster categorical datasets. In this paper, a new categorical method based on partitions called Manhattan Frequency k-Means (MFk-M) is detailed. It aims to convert the initial categorical data into numeric values using the relative frequency of each modality in the attributes. The L1 (Manhattan distance) norm was also used as an evaluation distance measure to compute the distance between the observations and the centroids. Finally, an approximation is defined to evaluate each resulting partition during the execution of the algorithm to avoid trivial clusterings such as cluster death. Experimental analysis performed on real life datasets highlights the reduced complexity costs and high efficiency of our proposal when compared to the standard k-means and k-modes algorithms.