Revisiting DP-Means: fast scalable algorithms via parallelism and delayed cluster creation

Or Dinari, Oren FreifeldUAI 2022 · OpenReview

Abstract

DP-means, a nonparametric generalization of K-means, extends the latter to the case where the number of clusters is unknown. Unlike K-means, however, DP-means is hard to parallelize, a limitation hindering its usage in large-scale tasks. This work bridges this practicality gap by rendering the DP-means approach a viable, fast, and highly-scalable solution. First, we study the strengths and weaknesses of previous attempts to parallelize the DP-means algorithm. Next, we propose a new parallel algorithm, called PDC-DP-Means (Parallel Delayed Cluster DP-Means), based in part on delayed creation of clusters. Compared with DP-Means, PDC-DP-Means provides not only a major speedup but also performance gains. Finally, we propose two extensions of PDC-DP-Means: a hybrid with existing methods and a Mini-Batch setting. We verify the utility of the proposed methods on multiple datasets, showing they outperform other nonparametric methods like DBSCAN. Our highly-efficient code is available at https://github.com/BGU-CS-VIL/pdc-dp-means.

Introduction

Clustering is a cornerstone of data science, and K-means is its "weapon of choice" due to its incredible speed and ease of parallelization. However, K-means has a famous Achilles' heel: you must specify the number of clusters ($K$) upfront.

DP-means (Dirichlet Process means) solves this by automatically creating new clusters whenever a data point is further than a threshold $\lambda$ from all existing centers. While elegant, the original DP-means is inherently serial. Because a new cluster can be created at any moment during a single pass through the data, the distance calculations for point $N+1$ depend on whether point $N$ just spawned a new cluster. This "sequential bottleneck" prevents the use of high-performance linear algebra libraries (BLAS) and makes parallelization across multiple CPU cores extremely difficult.

Methodology: Parallel Delayed Cluster DP-Means

The authors propose a deceptively simple but powerful modification: Delayed Cluster Creation (DC).

Instead of creating a new cluster the instant a "far away" point is found, the algorithm completes a full assignment pass over the data. It tracks the single point that is furthest from any existing center. Only after the pass is finished—and if that maximum distance exceeds the threshold $\lambda$—is a single new cluster created.

Because the number of clusters remains constant during a single pass, the data can be split across multiple processors. This PDC-DP-Means (Parallel DC-DP-Means) allows the algorithm to use optimized matrix-matrix multiplications (via BLAS) to calculate distances, mimicking the efficiency of industrial-grade K-means implementations.

Comparison of clustering results under different ordering and algorithms.

To scale even further, the authors adapt the Mini-Batch approach. By performing updates on small random subsets of data, they achieve convergence orders of magnitude faster than the batch version.

Key Insights: Order Independence and Hardware Optimization

A critical insight is that original DP-means is sensitive to the order of data. A "bad" ordering can lead to "over-clustering" (creating too many redundant clusters). Because the delayed version always picks the most distant point to start a new cluster, it is naturally more robust and produces higher-quality clusters (measured by Normalized Mutual Information).

Furthermore, the primary reason K-means is fast isn't just the algorithm—it's that the algorithm allows computers to do math in bulk. By delaying cluster creation, the authors finally allow DP-means to leverage modern hardware through BLAS. While the delayed version might take more iterations to reach the final number of clusters, each iteration is so much faster that the total wall-clock time drops significantly.

Key Results

The performance gains are dramatic across synthetic and massive real-world datasets, including MNIST and ImageNet (up to 1.2 million images).

Cost function convergence over time for various DP-means algorithms.
  • Speed: On a 2D Gaussian dataset (1M points), the original DP-means took 865 seconds. PDC-DP-Means took only 3.55 seconds, and the MiniBatch version took just 1.07 seconds.
  • Scalability: For the full ImageNet1K dataset (1.2M points), the MiniBatch PDC-DP-Means clustered the entire set in just 12.9 seconds. Previous parallel attempts (like P-DP-Means) took over 7 minutes.
  • Quality: In almost all tests, PDC-DP-Means achieved higher Normalized Mutual Information (NMI) scores than previous DP-means variants, proving that the speedup doesn't come at the cost of accuracy.

Conclusion

While the "one cluster per iteration" rule can be a bottleneck for datasets requiring thousands of clusters, the authors mitigate this through a hybrid approach with DACE, which allows for multiple clusters to be created simultaneously in early stages.

PDC-DP-Means represents a significant step forward, providing a fast, scalable, and robust alternative for clustering without the need to guess 'K'. The code is publicly available on GitHub, making this a practical "drop-in" replacement for researchers currently struggling with K-means selection.

Summary updated

Abstract

DP-means, a nonparametric generalization of K-means, extends the latter to the case where the number of clusters is unknown. Unlike K-means, however, DP-means is hard to parallelize, a limitation hindering its usage in large-scale tasks. This work bridges this practicality gap by rendering the DP-means approach a viable, fast, and highly-scalable solution. First, we study the strengths and weaknesses of previous attempts to parallelize the DP-means algorithm. Next, we propose a new parallel algorithm, called PDC-DP-Means (Parallel Delayed Cluster DP-Means), based in part on delayed creation of clusters. Compared with DP-Means, PDC-DP-Means provides not only a major speedup but also performance gains. Finally, we propose two extensions of PDC-DP-Means. The first combines it with an existing method, leading to further speedups. The second extends PDC-DP-Means to a Mini-Batch setting (with an optional support for an online mode), allowing for another major speedup. We verify the utility of the proposed methods on multiple datasets. We also show that the proposed methods outperform other nonparametric methods (e.g., DBSCAN). Our highly-efficient code can be used to reproduce our experiments and is available at https://github.com/BGU-CS-VIL/pdc-dp-means
BibTeX
@inproceedings{dinari2022revisiting,
  author = {Or Dinari and Oren Freifeld},
  title = {{Revisiting DP-Means: fast scalable algorithms via parallelism and delayed cluster creation}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2022},
  url = {https://openreview.net/forum?id=9JN2lyUcGh},
}
Figure