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. 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.
    3. Bouveyron, C. & Girard, S. & Schmid, C., 2007. "High-dimensional data clustering," Computational Statistics & Data Analysis, Elsevier, vol. 52(1), pages 502-519, September.
    4. 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.
    5. 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.
    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. 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.
    3. 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).
    4. 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.
    5. Olejniczak Tomasz, 2021. "Innovativeness of Senior Consumers’ Attitudes – An Attempt to Conduct Segmentation," Folia Oeconomica Stetinensia, Sciendo, vol. 21(1), pages 76-91, June.
    6. 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.
    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. 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.
    2. 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).
    3. 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.
    4. Jin, Xin & Maheu, John M., 2016. "Bayesian semiparametric modeling of realized covariance matrices," Journal of Econometrics, Elsevier, vol. 192(1), pages 19-39.
    5. Joseph Ndong & Ted Soubdhan, 2022. "Extracting Statistical Properties of Solar and Photovoltaic Power Production for the Scope of Building a Sophisticated Forecasting Framework," Forecasting, MDPI, vol. 5(1), pages 1-21, December.
    6. Regad, L. & Guyon, F. & Maupetit, J. & Tufféry, P. & Camproux, A.C., 2008. "A Hidden Markov Model applied to the protein 3D structure analysis," Computational Statistics & Data Analysis, Elsevier, vol. 52(6), pages 3198-3207, February.
    7. Cathy Maugis & Gilles Celeux & Marie-Laure Martin-Magniette, 2009. "Variable Selection for Clustering with Gaussian Mixture Models," Biometrics, The International Biometric Society, vol. 65(3), pages 701-709, September.
    8. 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.
    9. Alessandro Casa & Andrea Cappozzo & Michael Fop, 2022. "Group-Wise Shrinkage Estimation in Penalized Model-Based Clustering," Journal of Classification, Springer;The Classification Society, vol. 39(3), pages 648-674, November.
    10. Brenden Bishop & Minjeong Jeon, 2016. "Book Review," Psychometrika, Springer;The Psychometric Society, vol. 81(4), pages 1164-1167, December.
    11. 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.
    12. Xin Jin & John M. Maheu & Qiao Yang, 2019. "Bayesian parametric and semiparametric factor models for large realized covariance matrices," Journal of Applied Econometrics, John Wiley & Sons, Ltd., vol. 34(5), pages 641-660, August.
    13. Csereklyei, Zsuzsanna & Anantharama, Nandini & Kallies, Anne, 2021. "Electricity market transitions in Australia: Evidence using model-based clustering," Energy Economics, Elsevier, vol. 103(C).
    14. 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.
    15. Lu Huang & Xiang Chen & Yi Zhang & Changtian Wang & Xiaoli Cao & Jiarun Liu, 2022. "Identification of topic evolution: network analytics with piecewise linear representation and word embedding," Scientometrics, Springer;Akadémiai Kiadó, vol. 127(9), pages 5353-5383, September.
    16. Gael M. Martin & David T. Frazier & Ruben Loaiza-Maya & Florian Huber & Gary Koop & John Maheu & Didier Nibbering & Anastasios Panagiotelis, 2023. "Bayesian Forecasting in the 21st Century: A Modern Review," Monash Econometrics and Business Statistics Working Papers 1/23, Monash University, Department of Econometrics and Business Statistics.
    17. Jin, Xin & Maheu, John M. & Yang, Qiao, 2022. "Infinite Markov pooling of predictive distributions," Journal of Econometrics, Elsevier, vol. 228(2), pages 302-321.
    18. Thomas R. W. Oliver & Lia Chappell & Rashesh Sanghvi & Lauren Deighton & Naser Ansari-Pour & Stefan C. Dentro & Matthew D. Young & Tim H. H. Coorens & Hyunchul Jung & Tim Butler & Matthew D. C. Nevill, 2022. "Clonal diversification and histogenesis of malignant germ cell tumours," Nature Communications, Nature, vol. 13(1), pages 1-12, December.
    19. 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.
    20. Morten Overgaard & Stefan Nygaard Hansen, 2021. "On the assumption of independent right censoring," Scandinavian Journal of Statistics, Danish Society for Theoretical Statistics;Finnish Statistical Society;Norwegian Statistical Association;Swedish Statistical Association, vol. 48(4), pages 1234-1255, 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: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.