Clustering Categorical Data: Soft Rounding k-modes

2022/10/18 by Gavva, Surya Teja, S., Karthik C., Punna, Sharath
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2210.09640

Abstract

Over the last three decades, researchers have intensively explored various clustering tools for categorical data analysis. Despite the proposal of various clustering algorithms, the classical k-modes algorithm remains a popular choice for unsupervised learning of categorical data. Surprisingly, our first insight is that in a natural generative block model, the k-modes algorithm performs poorly for a large range of parameters. We remedy this issue by proposing a soft rounding variant of the k-modes algorithm (SoftModes) and theoretically prove that our variant addresses the drawbacks of the k-modes algorithm in the generative model. Finally, we empirically verify that SoftModes performs well on both synthetic and real-world datasets.

Related

• Categorical data clustering: 25 years beyond K-modes
• Fast Clustering of Categorical Big Data
• Approximation Algorithms for K-Modes Clustering
• The K-modes algorithm for clustering
• K-Histograms: An Efficient Clustering Algorithm for Categorical Dataset