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

What to Do When K-Means Clustering Fails: A Simple yet Principled Alternative Algorithm

Author

Listed:
  • Yordan P Raykov
  • Alexis Boukouvalas
  • Fahd Baig
  • Max A Little

Abstract

The K-means algorithm is one of the most popular clustering algorithms in current use as it is relatively fast yet simple to understand and deploy in practice. Nevertheless, its use entails certain restrictive assumptions about the data, the negative consequences of which are not always immediately apparent, as we demonstrate. While more flexible algorithms have been developed, their widespread use has been hindered by their computational and technical complexity. Motivated by these considerations, we present a flexible alternative to K-means that relaxes most of the assumptions, whilst remaining almost as fast and simple. This novel algorithm which we call MAP-DP (maximum a-posteriori Dirichlet process mixtures), is statistically rigorous as it is based on nonparametric Bayesian Dirichlet process mixture modeling. This approach allows us to overcome most of the limitations imposed by K-means. The number of clusters K is estimated from the data instead of being fixed a-priori as in K-means. In addition, while K-means is restricted to continuous data, the MAP-DP framework can be applied to many kinds of data, for example, binary, count or ordinal data. Also, it can efficiently separate outliers from the data. This additional flexibility does not incur a significant computational overhead compared to K-means with MAP-DP convergence typically achieved in the order of seconds for many practical problems. Finally, in contrast to K-means, since the algorithm is based on an underlying statistical model, the MAP-DP framework can deal with missing data and enables model testing such as cross validation in a principled way. We demonstrate the simplicity and effectiveness of this algorithm on the health informatics problem of clinical sub-typing in a cluster of diseases known as parkinsonism.

Suggested Citation

  • Yordan P Raykov & Alexis Boukouvalas & Fahd Baig & Max A Little, 2016. "What to Do When K-Means Clustering Fails: A Simple yet Principled Alternative Algorithm," PLOS ONE, Public Library of Science, vol. 11(9), pages 1-28, September.
  • Handle: RePEc:plo:pone00:0162259
    DOI: 10.1371/journal.pone.0162259
    as

    Download full text from publisher

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

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

    File URL: https://libkey.io/10.1371/journal.pone.0162259?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. Geert Molenberghs & Caroline Beunckens & Cristina Sotto & Michael G. Kenward, 2008. "Every missingness not at random model has a missingness at random counterpart with equal fit," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 70(2), pages 371-388, April.
    2. Bouveyron, C. & Girard, S. & Schmid, C., 2007. "High-dimensional data clustering," Computational Statistics & Data Analysis, Elsevier, vol. 52(1), pages 502-519, September.
    3. Hong Gao & Katarzyna Bryc & Carlos D Bustamante, 2011. "On Identifying the Optimal Number of Population Clusters via the Deviance Information Criterion," PLOS ONE, Public Library of Science, vol. 6(6), pages 1-8, June.
    4. Teh, Yee Whye & Jordan, Michael I. & Beal, Matthew J. & Blei, David M., 2006. "Hierarchical Dirichlet Processes," Journal of the American Statistical Association, American Statistical Association, vol. 101, pages 1566-1581, December.
    5. Hui-Jun Yang & Young Eun Kim & Ji Young Yun & Han-Joon Kim & Beom Seok Jeon, 2014. "Identifying the Clusters within Nonmotor Manifestations in Early Parkinson's Disease by Using Unsupervised Cluster Analysis," PLOS ONE, Public Library of Science, vol. 9(3), pages 1-5, March.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Omer Ajmal & Shahzad Mumtaz & Humaira Arshad & Abdullah Soomro & Tariq Hussain & Razaz Waheeb Attar & Ahmed Alhomoud, 2024. "Enhanced Parameter Estimation of DENsity CLUstEring (DENCLUE) Using Differential Evolution," Mathematics, MDPI, vol. 12(17), pages 1-46, September.
    2. Olejniczak Tomasz, 2021. "Innovativeness of Senior Consumers’ Attitudes – An Attempt to Conduct Segmentation," Folia Oeconomica Stetinensia, Sciendo, vol. 21(1), pages 76-91, June.
    3. Seungwon Jung & Jaeuk Moon & Eenjun Hwang, 2020. "Cluster-Based Analysis of Infectious Disease Occurrences Using Tensor Decomposition: A Case Study of South Korea," IJERPH, MDPI, vol. 17(13), pages 1-19, July.
    4. Joaquín Pérez-Ortega & Nelva Nely Almanza-Ortega & David Romero, 2018. "Balancing effort and benefit of K-means clustering algorithms in Big Data realms," PLOS ONE, Public Library of Science, vol. 13(9), pages 1-19, September.
    5. Tan, Daniel & Suvarna, Manu & Shee Tan, Yee & Li, Jie & Wang, Xiaonan, 2021. "A three-step machine learning framework for energy profiling, activity state prediction and production estimation in smart process manufacturing," Applied Energy, Elsevier, vol. 291(C).
    6. Maksymilian Mądziel, 2024. "Modeling Exhaust Emissions in Older Vehicles in the Era of New Technologies," Energies, MDPI, vol. 17(19), pages 1-18, October.
    7. Mayra Z Rodriguez & Cesar H Comin & Dalcimar Casanova & Odemir M Bruno & Diego R Amancio & Luciano da F Costa & Francisco A Rodrigues, 2019. "Clustering algorithms: A comparative approach," PLOS ONE, Public Library of Science, vol. 14(1), pages 1-34, January.

    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. Yekun Qin & Shanminhui Yin & Fang Liu, 2024. "RETRACTED ARTICLE: Navigating Criminal Responsibility in the Digital Marketplace: Implications of Network-Neutral Help Behavior and Beyond-5G Networks in E-Commerce Transactions," Journal of the Knowledge Economy, Springer;Portland International Center for Management of Engineering and Technology (PICMET), vol. 15(3), pages 10667-10695, September.
    2. Michelle Dietzen & Haoran Zhai & Olivia Lucas & Oriol Pich & Christopher Barrington & Wei-Ting Lu & Sophia Ward & Yanping Guo & Robert E. Hynds & Simone Zaccaria & Charles Swanton & Nicholas McGranaha, 2024. "Replication timing alterations are associated with mutation acquisition during breast and lung cancer evolution," Nature Communications, Nature, vol. 15(1), pages 1-23, December.
    3. Redivo, Edoardo & Nguyen, Hien D. & Gupta, Mayetri, 2020. "Bayesian clustering of skewed and multimodal data using geometric skewed normal distributions," Computational Statistics & Data Analysis, Elsevier, vol. 152(C).
    4. Charles Bouveyron & Julien Jacques, 2011. "Model-based clustering of time series in group-specific functional subspaces," 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. 5(4), pages 281-300, December.
    5. Parvin Ahmadi & Iman Gholampour & Mahmoud Tabandeh, 2018. "Cluster-based sparse topical coding for topic mining and document clustering," 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. 12(3), pages 537-558, September.
    6. Jeffrey L. Furman & Florenta Teodoridis, 2020. "Automation, Research Technology, and Researchers’ Trajectories: Evidence from Computer Science and Electrical Engineering," Organization Science, INFORMS, vol. 31(2), pages 330-354, March.
    7. Shu-Ping Shi & Yong Song, 2012. "Identifying Speculative Bubbles with an Infinite Hidden Markov Model," Working Paper series 26_12, Rimini Centre for Economic Analysis.
    8. Jin, Xin & Maheu, John M. & Yang, Qiao, 2022. "Infinite Markov pooling of predictive distributions," Journal of Econometrics, Elsevier, vol. 228(2), pages 302-321.
    9. Gustaf Bellstam & Sanjai Bhagat & J. Anthony Cookson, 2021. "A Text-Based Analysis of Corporate Innovation," Management Science, INFORMS, vol. 67(7), pages 4004-4031, July.
    10. Shu Xu & Shelley A. Blozis, 2011. "Sensitivity Analysis of Mixed Models for Incomplete Longitudinal Data," Journal of Educational and Behavioral Statistics, , vol. 36(2), pages 237-256, April.
    11. Bian, Yuan & Yi, Grace Y. & He, Wenqing, 2024. "A unified framework of analyzing missing data and variable selection using regularized likelihood," Computational Statistics & Data Analysis, Elsevier, vol. 194(C).
    12. Hassan Akell & Farkhondeh-Alsadat Sajadi & Iraj Kazemi, 2023. "Construction of Jointly Distributed Random Samples Drawn from the Beta Two-Parameter Process," Methodology and Computing in Applied Probability, Springer, vol. 25(3), pages 1-12, September.
    13. Hongxia Yang & Aurelie Lozano, 2015. "Multi-relational learning via hierarchical nonparametric Bayesian collective matrix factorization," Journal of Applied Statistics, Taylor & Francis Journals, vol. 42(5), pages 1133-1147, May.
    14. Bauwens, Luc & Dufays, Arnaud & Rombouts, Jeroen V.K., 2014. "Marginal likelihood for Markov-switching and change-point GARCH models," Journal of Econometrics, Elsevier, vol. 178(P3), pages 508-522.
    15. Kott Phillip S. & Liao Dan, 2018. "Calibration Weighting for Nonresponse with Proxy Frame Variables (So that Unit Nonresponse Can Be Not Missing at Random)," Journal of Official Statistics, Sciendo, vol. 34(1), pages 107-120, March.
    16. Robert M. Dorazio & Bhramar Mukherjee & Li Zhang & Malay Ghosh & Howard L. Jelks & Frank Jordan, 2008. "Modeling Unobserved Sources of Heterogeneity in Animal Abundance Using a Dirichlet Process Prior," Biometrics, The International Biometric Society, vol. 64(2), pages 635-644, June.
    17. Jeong Hwan Kook & Michele Guindani & Linlin Zhang & Marina Vannucci, 2019. "NPBayes-fMRI: Non-parametric Bayesian General Linear Models for Single- and Multi-Subject fMRI Data," Statistics in Biosciences, Springer;International Chinese Statistical Association, vol. 11(1), pages 3-21, April.
    18. Yong Song, 2014. "Modelling Regime Switching And Structural Breaks With An Infinite Hidden Markov Model," Journal of Applied Econometrics, John Wiley & Sons, Ltd., vol. 29(5), pages 825-842, August.
    19. Lu Shaochuan, 2023. "Scalable Bayesian Multiple Changepoint Detection via Auxiliary Uniformisation," International Statistical Review, International Statistical Institute, vol. 91(1), pages 88-113, April.
    20. Marco Doretti & Sara Geneletti & Elena Stanghellini, 2018. "Missing Data: A Unified Taxonomy Guided by Conditional Independence," International Statistical Review, International Statistical Institute, vol. 86(2), pages 189-204, August.

    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:0162259. 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.