Ckmeans.1d.dp: Optimal k-means Clustering in One Dimension by Dynamic Programming

Area of Science:

• Computer Science
• Statistics
• Data Mining

Background:

• The heuristic k-means algorithm is a widely adopted method for cluster analysis.
• However, k-means does not guarantee an optimal clustering solution.
• This limitation affects the reliability of clustering results in various applications.

Purpose of the Study:

• To develop a novel algorithm for optimal one-dimensional clustering.
• To address the sub-optimality issue inherent in heuristic clustering methods.
• To provide a computationally efficient and accurate clustering tool.

Main Methods:

• A dynamic programming approach was devised for one-dimensional clustering.
• The algorithm was implemented as an R package named Ckmeans.1d.dp.
• Performance was evaluated against the standard iterative k-means algorithm.

Main Results:

• The dynamic programming algorithm achieves provably optimal one-dimensional clustering.
• Ckmeans.1d.dp demonstrated superior optimality compared to k-means.
• The R package also showed a competitive runtime performance.

Conclusions:

• Dynamic programming offers a viable method for achieving optimal clustering.
• Ckmeans.1d.dp provides a superior alternative to k-means for one-dimensional data.
• The package enhances the accuracy and efficiency of cluster analysis.