A testing-based approach to assess the clusterability of categorical
  data
Lianyu Hu Junjie Dong Mudi Jiang Yan Liu Zengyou He
The objective of clusterability evaluation is to check whether a clustering
structure exists within the data set. As a crucial yet often-overlooked issue
in cluster analysis, it is essential to conduct such a test before applying any
clustering algorithm. If a data set is unclusterable, any subsequent clustering
analysis would not yield valid results. Despite its importance, the majority of
existing studies focus on numerical data, leaving the clusterability evaluation
issue for categorical data as an open problem. Here we present TestCat, a
testing-based approach to assess the clusterability of categorical data in
terms of an analytical $p$-value. The key idea underlying TestCat is that
clusterable categorical data possess many strongly correlated attribute pairs
and hence the sum of chi-squared statistics of all attribute pairs is employed
as the test statistic for $p$-value calculation. We apply our method to a set
of benchmark categorical data sets, showing that TestCat outperforms those
solutions based on existing clusterability evaluation methods for numeric data.
To the best of our knowledge, our work provides the first way to effectively
recognize the clusterability of categorical data in a statistically sound
manner.