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

Area of Science:

• Machine Learning
• Data Mining
• Bayesian Statistics

Background:

• K-means is a popular clustering algorithm but has restrictive assumptions and limitations.
• Existing flexible algorithms are often computationally complex.
• There is a need for a clustering method that is both flexible and computationally efficient.

Purpose of the Study:

• To introduce a novel, flexible, and computationally efficient clustering algorithm as an alternative to K-means.
• To overcome the limitations of K-means, including its assumptions about data and fixed cluster numbers.
• To demonstrate the algorithm's effectiveness on a real-world health informatics problem.

Main Methods:

• Developed a new algorithm called maximum a-posteriori Dirichlet process mixtures (MAP-DP).
• Utilized nonparametric Bayesian Dirichlet process mixture modeling for statistical rigor.
• Applied the MAP-DP algorithm to the problem of clinical sub-typing in parkinsonism.

Main Results:

• MAP-DP relaxes K-means assumptions, allowing for data-driven cluster number estimation.
• The algorithm supports various data types (binary, count, ordinal) and efficiently handles outliers and missing data.
• MAP-DP demonstrates comparable speed to K-means, with convergence in seconds for practical problems.
• Effectiveness shown in clinical sub-typing for parkinsonism, highlighting its utility in health informatics.

Conclusions:

• MAP-DP provides a statistically rigorous, flexible, and efficient clustering solution.
• It overcomes key limitations of K-means, offering broader applicability and improved data handling.
• The algorithm is suitable for complex data analysis tasks, including those in health informatics.