On the Persistence of Clustering Solutions and True Number of Clusters
  in a Dataset
  Typically clustering algorithms provide clustering solutions with
prespecified number of clusters. The lack of a priori knowledge on the true
number of underlying clusters in the dataset makes it important to have a
metric to compare the clustering solutions with different number of clusters.
This article quantifies a notion of persistence of clustering solutions that
enables comparing solutions with different number of clusters. The persistence
relates to the range of data-resolution scales over which a clustering solution
persists; it is quantified in terms of the maximum over two-norms of all the
associated cluster-covariance matrices. Thus we associate a persistence value
for each element in a set of clustering solutions with different number of
clusters. We show that the datasets where natural clusters are a priori known,
the clustering solutions that identify the natural clusters are most persistent
- in this way, this notion can be used to identify solutions with true number
of clusters. Detailed experiments on a variety of standard and synthetic
datasets demonstrate that the proposed persistence-based indicator outperforms
the existing approaches, such as, gap-statistic method, $X$-means, $G$-means,
$PG$-means, dip-means algorithms and information-theoretic method, in
accurately identifying the clustering solutions with true number of clusters.
Interestingly, our method can be explained in terms of the phase-transition
phenomenon in the deterministic annealing algorithm, where the number of
distinct cluster centers changes (bifurcates) with respect to an annealing
parameter.
