@article{Srivastava_Baranwal_Salapaka_2019, title={On the Persistence of Clustering Solutions and True Number of Clusters in a Dataset}, volume={33}, url={https://ojs.aaai.org/index.php/AAAI/article/view/4431}, DOI={10.1609/aaai.v33i01.33015000}, abstractNote={<p>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 <em>persistence</em> of clustering solutions that enables comparing solutions with different number of clusters. The persistence relates to the range of dataresolution 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 <em>natural</em> 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 <em>true</em> 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, <em>X</em>-means, <em>G</em>means, <em>PG</em>-means, dip-means algorithms and informationtheoretic 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.</p>}, number={01}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Srivastava, Amber and Baranwal, Mayank and Salapaka, Srinivasa}, year={2019}, month={Jul.}, pages={5000-5007} }