IDEAS home Printed from https://ideas.repec.org/a/plo/pone00/0227788.html
   My bibliography  Save this article

Blind method for discovering number of clusters in multidimensional datasets by regression on linkage hierarchies generated from random data

Author

Listed:
  • Osbert C Zalay

Abstract

Determining intrinsic number of clusters in a multidimensional dataset is a commonly encountered problem in exploratory data analysis. Unsupervised clustering algorithms often rely on specification of cluster number as an input parameter. However, this is typically not known a priori. Many methods have been proposed to estimate cluster number, including statistical and information-theoretic approaches such as the gap statistic, but these methods are not always reliable when applied to non-normally distributed datasets containing outliers or noise. In this study, I propose a novel method called hierarchical linkage regression, which uses regression to estimate the intrinsic number of clusters in a multidimensional dataset. The method operates on the hypothesis that the organization of data into clusters can be inferred from the hierarchy generated by partitioning the dataset, and therefore does not directly depend on the specific values of the data or their distribution, but on their relative ranking within the partitioned set. Moreover, the technique does not require empirical data to train on, but can use synthetic data generated from random distributions to fit regression coefficients. The trained hierarchical linkage regression model is able to infer cluster number in test datasets of varying complexity and differing distributions, for image, text and numeric data, using the same regression model without retraining. The method performs favourably against other cluster number estimation techniques, and is also robust to parameter changes, as demonstrated by sensitivity analysis. The apparent robustness and generalizability of hierarchical linkage regression make it a promising tool for unsupervised exploratory data analysis and discovery.

Suggested Citation

  • Osbert C Zalay, 2020. "Blind method for discovering number of clusters in multidimensional datasets by regression on linkage hierarchies generated from random data," PLOS ONE, Public Library of Science, vol. 15(1), pages 1-28, January.
  • Handle: RePEc:plo:pone00:0227788
    DOI: 10.1371/journal.pone.0227788
    as

    Download full text from publisher

    File URL: https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0227788
    Download Restriction: no

    File URL: https://journals.plos.org/plosone/article/file?id=10.1371/journal.pone.0227788&type=printable
    Download Restriction: no

    File URL: https://libkey.io/10.1371/journal.pone.0227788?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Robert Tibshirani & Guenther Walther & Trevor Hastie, 2001. "Estimating the number of clusters in a data set via the gap statistic," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 63(2), pages 411-423.
    2. Mathias Rossignol & Mathieu Lagrange & Arshia Cont, 2018. "Efficient similarity-based data clustering by optimal object to cluster reallocation," PLOS ONE, Public Library of Science, vol. 13(6), pages 1-22, June.
    3. Sugar, Catherine A. & James, Gareth M., 2003. "Finding the Number of Clusters in a Dataset: An Information-Theoretic Approach," Journal of the American Statistical Association, American Statistical Association, vol. 98, pages 750-763, January.
    4. Xianxue Yu & Guoxian Yu & Jun Wang, 2017. "Clustering cancer gene expression data by projective clustering ensemble," PLOS ONE, Public Library of Science, vol. 12(2), pages 1-21, February.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Li, Pai-Ling & Chiou, Jeng-Min, 2011. "Identifying cluster number for subspace projected functional data clustering," Computational Statistics & Data Analysis, Elsevier, vol. 55(6), pages 2090-2103, June.
    2. Yujia Li & Xiangrui Zeng & Chien‐Wei Lin & George C. Tseng, 2022. "Simultaneous estimation of cluster number and feature sparsity in high‐dimensional cluster analysis," Biometrics, The International Biometric Society, vol. 78(2), pages 574-585, June.
    3. J. Fernando Vera & Rodrigo Macías, 2021. "On the Behaviour of K-Means Clustering of a Dissimilarity Matrix by Means of Full Multidimensional Scaling," Psychometrika, Springer;The Psychometric Society, vol. 86(2), pages 489-513, June.
    4. Oliver Schaer & Nikolaos Kourentzes & Robert Fildes, 2022. "Predictive competitive intelligence with prerelease online search traffic," Production and Operations Management, Production and Operations Management Society, vol. 31(10), pages 3823-3839, October.
    5. Fang, Yixin & Wang, Junhui, 2011. "Penalized cluster analysis with applications to family data," Computational Statistics & Data Analysis, Elsevier, vol. 55(6), pages 2128-2136, June.
    6. Jonas M. B. Haslbeck & Dirk U. Wulff, 2020. "Estimating the number of clusters via a corrected clustering instability," Computational Statistics, Springer, vol. 35(4), pages 1879-1894, December.
    7. Athanasios Constantopoulos & John Yfantopoulos & Panos Xenos & Athanassios Vozikis, 2019. "Cluster shifts based on healthcare factors: The case of Greece in an OECD background 2009-2014," Advances in Management and Applied Economics, SCIENPRESS Ltd, vol. 9(6), pages 1-4.
    8. Peter Radchenko & Gourab Mukherjee, 2017. "Convex clustering via l 1 fusion penalization," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 79(5), pages 1527-1546, November.
    9. Yi Peng & Yong Zhang & Gang Kou & Yong Shi, 2012. "A Multicriteria Decision Making Approach for Estimating the Number of Clusters in a Data Set," PLOS ONE, Public Library of Science, vol. 7(7), pages 1-9, July.
    10. Z. Volkovich & Z. Barzily & G.-W. Weber & D. Toledano-Kitai & R. Avros, 2012. "An application of the minimal spanning tree approach to the cluster stability problem," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 20(1), pages 119-139, March.
    11. Julian Rossbroich & Jeffrey Durieux & Tom F. Wilderjans, 2022. "Model Selection Strategies for Determining the Optimal Number of Overlapping Clusters in Additive Overlapping Partitional Clustering," Journal of Classification, Springer;The Classification Society, vol. 39(2), pages 264-301, July.
    12. Gaynor, Sheila & Bair, Eric, 2017. "Identification of relevant subtypes via preweighted sparse clustering," Computational Statistics & Data Analysis, Elsevier, vol. 116(C), pages 139-154.
    13. Fischer, Aurélie, 2011. "On the number of groups in clustering," Statistics & Probability Letters, Elsevier, vol. 81(12), pages 1771-1781.
    14. Fang, Yixin & Wang, Junhui, 2012. "Selection of the number of clusters via the bootstrap method," Computational Statistics & Data Analysis, Elsevier, vol. 56(3), pages 468-477.
    15. Koltcov, Sergei, 2018. "Application of Rényi and Tsallis entropies to topic modeling optimization," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 512(C), pages 1192-1204.
    16. Jane L. Harvill & Priya Kohli & Nalini Ravishanker, 2017. "Clustering Nonlinear, Nonstationary Time Series Using BSLEX," Methodology and Computing in Applied Probability, Springer, vol. 19(3), pages 935-955, September.
    17. Tomislava Pavić Kramarić & Mirjana Pejić Bach & Ksenija Dumičić & Berislav Žmuk & Maja Mihelja Žaja, 2018. "Exploratory study of insurance companies in selected post-transition countries: non-hierarchical cluster analysis," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 26(3), pages 783-807, September.
    18. Z. Volkovich & D. Toledano-Kitai & G.-W. Weber, 2013. "Self-learning K-means clustering: a global optimization approach," Journal of Global Optimization, Springer, vol. 56(2), pages 219-232, June.
    19. J. Fernando Vera & Rodrigo Macías, 2017. "Variance-Based Cluster Selection Criteria in a K-Means Framework for One-Mode Dissimilarity Data," Psychometrika, Springer;The Psychometric Society, vol. 82(2), pages 275-294, June.
    20. Šárka Brodinová & Peter Filzmoser & Thomas Ortner & Christian Breiteneder & Maia Rohm, 2019. "Robust and sparse k-means clustering for high-dimensional data," Advances in Data Analysis and Classification, Springer;German Classification Society - Gesellschaft für Klassifikation (GfKl);Japanese Classification Society (JCS);Classification and Data Analysis Group of the Italian Statistical Society (CLADAG);International Federation of Classification Societies (IFCS), vol. 13(4), pages 905-932, December.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:plo:pone00:0227788. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: plosone (email available below). General contact details of provider: https://journals.plos.org/plosone/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.