A Batched Hartigan's -Means Clustering
Organizations: CrowdStrike · University of Maryland, Baltimore County · Syracuse University
Abstract
Hartigan's -means algorithm has theoretical advantages over the standard Lloyd's variant, which has become synonymous with "-means". Yet, Hartigan's algorithm is far slower in practice due to its inherently sequential calculations. We devise a Batched Hartigan's method that enables vectorized calculation by exploiting the triangle inequality to expose a set of parallel-safe updates and a smaller set of sequential updates. This makes Hartigan's method competitive with Lloyd's in execution speed for the first time.
Figures & tables
| Symbol | Domain | Meaning |
|---|---|---|
| Batch size (points per GEMM) | ||
| index set | Ordered set of selected point indices; positions are relabeled within the batch | |
| Centroid of cluster at batch start | ||
| Centroid of cluster after the -th item is processed | ||
| Size of cluster after the -th item | ||
| Precomputed (from GEMM) |
| Symbol | Meaning and detailed definition |
|---|---|
| Batch-start squared distance, drift bound, and Hartigan-cost bounds; § 4.1 | |
| Centroid and size of cluster after batch position ; § 4.1 | |
| Current and limiting batch sizes; § 4.3 | |
| Exponential moving average (EMA) state and batch-size inputs; § 4.3 | |
| Ordered selected point indices & their relabeled batch positions ; § 4.4 | |
| Cluster currently assigned to point ; § 4.4 |
| Dataset | Hartigan / Elkan | Batched / Elkan |
|---|---|---|
| Letter | ||
| MAGIC Gamma | ||
| Sepsis | ||
| Shuttle | ||
| Superconductivity | ||
| aloi |
| Dataset | Inertia ratio | At | |
|---|---|---|---|
| breast-cancer | 10 | 0.9504 | 128 |
| leukemia | 7,129 | 0.9134 | 16 |
| duke | 7,129 | 0.8201 | 4 |
| bibtex | 1,836 | 0.9639 | 4 |
| sector | 55,197 | 0.9866 | 256 |
| news20 | 62,061 | 0.9030 | 8 |
| Wall time (seconds) | |||
|---|---|---|---|
| Dataset | Batched | C++ | Lederman |
| phishing | 0.025 | 0.083 | 0.255 |
| MAGIC Gamma | 0.046 | 0.043 | 0.290 |
| Letter | 0.053 | 0.063 | 0.347 |
| Superconductivity | 0.031 | 0.289 | 0.547 |
| Shuttle | 0.192 | 0.170 | 0.248 |
| Wall time (seconds) | ||||
|---|---|---|---|---|
| Dataset | Lloyd | Elkan | Hamerly | Batched H. |
| phishing | 0.136 | 0.016 | 0.062 | 0.025 |
| MAGIC Gamma | 0.154 | 0.049 | 0.046 | 0.046 |
| Letter | 0.211 | 0.051 | 0.052 | 0.053 |
| Superconductivity | 0.215 | 0.018 | 0.088 | 0.031 |
| Shuttle | 0.135 | 0.029 | 0.051 | 0.192 |
Appendix figures & tables14 assets
Supplementary material from the paper’s appendix.
Appendix
| Point | Coordinates | Current cluster | |||
|---|---|---|---|---|---|
| 0.20 | 17.00 | 32.80 | |||
| 19.40 | 0.20 | 16.00 | |||
| 33.05 | 9.65 | 0.25 | |||
| 13.00 | 1.00 | 20.00 | |||
| 3.30 | 5.88 | 22.66 |
| Prior H. (C++) | Elkan | Batched H. (ours) | |
|---|---|---|---|
| 2 | ( – ) | ( – ) | ( – ) |
| 4 | ( – ) | ( – ) | ( – ) |
| 8 | ( – ) | ( – ) | ( – ) |
| 16 | ( – ) | ( – ) | ( – ) |
| 32 | ( – ) | ( – ) | ( – ) |
| 64 | ( – ) | ( – ) | ( – ) |
| Dataset | |||
|---|---|---|---|
| phishing | 68 | 752K | |
| MAGIC Gamma | 10 | 190K | |
| Letter | 16 | 320K | |
| Superconductivity | 81 | 1.7M | |
| Shuttle | 7 | 406K | |
| cod-rna | 8 | 476K |
| Dataset | Density | Inertia ratio | Runtime speedup | |||
|---|---|---|---|---|---|---|
| breast-cancer | 683 | 10 | 1.0000 | 128 | 0.9504 | |
| leukemia | 38 | 7,129 | 1.0000 | 16 | 0.9134 | |
| duke | 44 | 7,129 | 1.0000 | 4 | 0.8201 | |
| bibtex | 7,395 | 1,836 | 0.0374 | 4 | 0.9639 | |
| sector | 6,412 | 55,197 | 0.0030 | 256 | 0.9866 | |
| news20 | 15,935 | 62,061 | 0.0013 | 8 | 0.9030 |
| Dataset | Density | Direct | Refine | Overhead | |||
|---|---|---|---|---|---|---|---|
| breast-cancer | 683 | 10 | 1.0000 | 128 | 0.9504 | 0.9754 | 44.1% |
| leukemia | 38 | 7,129 | 1.0000 | 16 | 0.9134 | 0.9407 | 305.4% |
| duke | 44 | 7,129 | 1.0000 | 4 | 0.8201 | 0.9551 | 298.5% |
| bibtex | 7,395 | 1,836 | 0.0374 | 4 | 0.9639 | 0.9864 | 75.7% |
| sector | 6,412 | 55,197 | 0.0030 | 256 | 0.9866 | 0.9869 | 77.2% |
| news20 | 15,935 | 62,061 | 0.0013 | 8 | 0.9030 | 0.9305 | 493.8% |
| Dataset | No Build | No Par. | No Seq. | No Dyn. max | No Dyn. min | |
|---|---|---|---|---|---|---|
| phishing | 8 | 1.48 | 0.71 | 0.97 | 0.95 | 5.10 |
| 32 | 1.26 | 0.80 | 1.05 | 1.00 | 3.63 | |
| Letter | 8 | 1.86 | 0.69 | 0.95 | 0.98 | 6.26 |
| 32 | 1.58 | 0.80 | 0.87 | 0.89 | 5.94 | |
| 128 | 2.00 | 0.92 | 1.00 | 1.03 | 3.47 | |
| mnist | 8 | 1.55 | 0.93 | 1.32 | 1.00 | 2.73 |
| Dataset | % Parallel (full) | Seq. ops ratio | Iter. ratio | |
|---|---|---|---|---|
| phishing | 8 | 69.7% | 3.5 | 1.04 |
| 32 | 71.5% | 3.2 | 0.82 | |
| Letter | 8 | 80.4% | 5.2 | 1.00 |
| 32 | 86.4% | 7.4 | 0.95 | |
| 128 | 90.5% | 11.3 | 1.13 | |
| mnist | 8 | 87.7% | 8.3 | 1.00 |
| Parameter | Default | Swept | Median time ratio (range across datasets) | ||
|---|---|---|---|---|---|
| values | |||||
| 64 | 6, 64, 640 | 1.00 (0.99–1.02) | 1.00 | 1.00 (0.99–1.01) | |
| 4096 | 410, 4096, 40960 | 1.81 (0.65–2.75) | 1.00 | 1.08 (0.72–3.29) | |
| 0.1 | 0.01, 0.1, 1.0 | 1.00 (0.91–1.25) | 1.00 | 1.00 (0.96–1.02) | |
| 0.5 | 0.05, 0.5, 5.0 | 1.00 (0.82–1.44) | 1.00 | 1.00 (0.97–1.02) | |
Clustering
Clustering groups data points by shared structure, developing methods to discover, validate, and interpret groups across diverse data and constraints.
See all 370 papers