Spectral Clustering of Categorical and Mixed-type Data via Extra Graph Nodes
This provides an incremental improvement for data mining tasks involving mixed or categorical data, offering a more natural and efficient clustering approach.
The paper tackles clustering of categorical and mixed-type data by proposing a spectral clustering method that adds extra nodes for categories, avoiding preprocessing and leading to a linear-time algorithm for categorical-only data. It shows competitive performance and runtime compared to other methods.
Clustering data objects into homogeneous groups is one of the most important tasks in data mining. Spectral clustering is arguably one of the most important algorithms for clustering, as it is appealing for its theoretical soundness and is adaptable to many real-world data settings. For example, mixed data, where the data is composed of numerical and categorical features, is typically handled via numerical discretization, dummy coding, or similarity computation that takes into account both data types. This paper explores a more natural way to incorporate both numerical and categorical information into the spectral clustering algorithm, avoiding the need for data preprocessing or the use of sophisticated similarity functions. We propose adding extra nodes corresponding to the different categories the data may belong to and show that it leads to an interpretable clustering objective function. Furthermore, we demonstrate that this simple framework leads to a linear-time spectral clustering algorithm for categorical-only data. Finally, we compare the performance of our algorithms against other related methods and show that it provides a competitive alternative to them in terms of performance and runtime.