Spectral Clustering of Categorical and Mixed-type Data via Extra Graph
  Nodes
Dylan Soemitro Jeova Farias Sales Rocha Neto
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.