Parallelogram-mode: A novel clustering method for categorical data

Abstract

The need for clustering methods that treat the interpretability of clustering results as valuable as cluster correctness is particularly important in high-risk domains. The heterogeneous nature of categorical data makes its clustering results less interpretable than those for numerical data.  This challenge is amplified by the scarcity of works investigating the clustering of categorical data. Existing interpretable categorical data clustering algorithms do not optimise for scalability. In this paper, we address the scalability limitation by employing a vectorial approach to interpretable categorical data clustering that takes full advantage of the computational acceleration offered by modern computing hardware, such as GPUs. We formulate categorical data clustering as a rule-set search task that manipulates high-dimensional vector representations of entities in the input dataset. We propose an efficient and effective algorithm called “Coupling-Sorting-Branching” to solve the search task. This approach provides a scalable and fully interpretable method for clustering categorical data. Extensive experimental results across 14 real-world datasets demonstrate that our algorithm outperforms existing methods in cluster quality and explainability by producing IF-THEN rules.