What to Do When K-Means Clustering Fails: A Simple yet Principled Alternative Algorithm.
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.
School of Mathematics, Aston University, Birmingham, United Kingdom.
Yordan P
YP
Raykov
Molecular Sciences, University of Manchester, Manchester, United Kingdom.
Alexis
A
Boukouvalas
Nuffield Department of Clinical Neurosciences, Oxford University, Oxford, United Kingdom.
Fahd
F
Baig
School of Mathematics, Aston University, Birmingham, United Kingdom.|Media Lab, Massachusetts Institute of Technology, Cambridge, Massachusetts, United States of America.
Max A
MA
Little
Mol Inform. 2013 Jul;32(7):591-8
27481767
PLoS One. 2011;6(6):e21014
21738600
J Zhejiang Univ Sci B. 2011 Sep;12(9):694-703
21887844
J Neurol Neurosurg Psychiatry. 2005 Mar;76(3):343-8
15716523
Mov Disord. 2010 Jun 15;25(8):969-78
20535823
Parkinsonism Relat Disord. 2009 Jun;15(5):379-82
18977165
Mov Disord. 2007 Apr 30;22(6):904-5
17343272
Neural Comput. 2009 Apr;21(4):1145-72
19199394
Neurol Sci. 2002 Sep;23 Suppl 2:S77-8
12548352
Neurology. 1998 Feb;50(2):318 and 16 pages following
9484345
PLoS One. 2014 Mar 18;9(3):e91906
24643014