X-means: Extending K-means with Efficient Estimation of the Number of Clusters

Dan PellegAndrew Moore

article2000ICML2,908 citations

Proposes the X-means algorithm, an extension of K-means that automatically determines the number of clusters using local Bayesian Information Criterion tests accelerated by multiresolution kd-trees to achieve superior clustering quality and major speedups on large datasets.

Listen

Clustering large datasets requires choosing in advance how many groups to form, a step that standard K-means leaves to the user and that becomes impractical for big or high-volume data. The X-means work set out to remove that requirement by building an algorithm that both finds a suitable number of clusters and places them efficiently while still producing results at least as good as conventional K-means.

The authors start from an already-accelerated version of K-means that stores summary statistics in a kd-tree and uses geometric tests to avoid checking every point against every center. They then add a structure-improvement step that repeatedly splits each current center into two local candidates, runs a short two-center refinement inside the parent region only, and accepts or rejects the split according to the Bayesian Information Criterion. The process repeats, increasing the number of centers only where the data support it, until an upper limit supplied by the user is reached. Experiments used both synthetic Gaussian mixtures with known true cluster counts and real astronomical catalogs containing hundreds of thousands of galaxies.

X-means recovered cluster counts within roughly 15 percent of the true value on synthetic data and produced lower distortion and higher BIC scores than K-means given the correct count in advance. On the same hardware it ran about twice as fast as repeated accelerated K-means trials over a comparable range of K values; on a 330,000-point galaxy set the speed-up reached roughly thirty-fold relative to naïve repeated K-means. In the Sloan Digital Sky Survey sample the method returned an average cluster size of about 470 objects with far smaller run-to-run variation than the baseline approach.

These results matter because they let analysts apply clustering to millions of records without exhaustive trial-and-error searches for K and without sacrificing statistical quality. The method therefore supports timely exploration of large scientific or operational datasets where the right number of groups is not known beforehand.

The authors note that the same local-decision framework can be extended to other model-selection criteria such as AIC and to mixture-model fitting beyond hard K-means assignments; both directions are already under study. The main limitations are that the current implementation assumes spherical clusters of equal variance and has been demonstrated only up to four dimensions, so users facing strongly non-spherical or very high-dimensional data should validate results on representative subsets before scaling.

Carnegie Mellon University bayesian methods correlation analysis estimation method X-means clustering estimation of the number of clusters K-means clustering

Pelleg et al (2000).pdf

Paper: An Efficient k-Means Clustering Algorithm: Analysis and Implementation, Tapas Kanungo et al. (2002). Reading this efficient exact implementation of k-means clustering provides the foundational nearest-center algorithms and pruning techniques built upon by X-means.

No sufficiently relevant recommendations were found.

Cover for X-means: Extending K-means with Efficient Estimation of the Number of Clusters

Abstract

Despite its popularity for general clustering, K-means suffers three major shortcomings; it scales poorly computationally, the number of clusters K has to be supplied by the user, and the search is prone to local minima. We propose solutions for the first two problems, and a partial remedy for the third. Building on prior work for algorithmic acceleration that is not based on approximation, we introduce a new algorithm that efficiently, searches the space of cluster locations and number of clusters to optimize the Bayesian Information Criterion (BIC) or the Akaike Information Criterion (AIC) measure. The innovations include two new ways of exploiting cached sufficient statistics and a new very efficient test that in one K-means sweep selects the most promising subset of classes for refinement. This gives rise to a fast, statistically founded algorithm that outputs both the number of classes and their parameters. Experiments show this technique reveals the true number of classes in the underlying distribution, and that it is much faster than repeatedly using accelerated K-means for different values of K.

Topics

bayesian methods correlation analysis estimation method k-means algorithm clustering methods user information

Keywords

X-means clustering estimation of the number of clusters K-means clustering

1. Introduction
2. Definitions
3. Estimation of $K$
3.1 Model Searching
3.2 BIC Scoring
3.3 Acceleration
4. Experimental Results
5. Conclusion
Acknowledgements
References

Knowls

Knowl 1 — X-means Clustering Algorithm
algorithm
The X-means algorithm automatically estimates the number of clusters $K$ within a user-specified range $[K_{\min}, K_{\max}]$ while simultaneously estimating cluster parameters. It iteratively alternates between optimizing centroid locations for a fixed $K$ and testing whether individual clusters should be split into two.
Input: Dataset $D \subset \mathbb{R}^M$ , minimum cluster count $K_{\min}$ , maximum cluster count $K_{\max}$
Output: Best centroid configuration $\mathcal{C}^*$ and estimated number of clusters $K^*$
$K \leftarrow K_{\min}$
Initialize centroid set $\mathcal{C} = \{\mu_1, \dots, \mu_K\}$ randomly or via seeding
$\mathcal{C}^* \leftarrow \mathcal{C}$
$\text{best\_score} \leftarrow -\infty$
while $K \le K_{\max}$ do
     $\mathcal{C} \leftarrow \text{Improve-Params}(\mathcal{C}, D)$ // Run conventional K-means to convergence
     $\text{current\_score} \leftarrow \text{BIC}(\mathcal{C}, D)$
    if $\text{current\_score} > \text{best\_score}$ then
         $\text{best\_score} \leftarrow \text{current\_score}$
         $\mathcal{C}^* \leftarrow \mathcal{C}$
    end if
     $\mathcal{C}_{\text{new}} \leftarrow \emptyset$
    for each centroid $\mu_j \in \mathcal{C}$ do
         $\{\mu_{j,1}, \mu_{j,2}\} \leftarrow \text{Improve-Structure}(\mu_j, D_j)$ // Local 2-means and BIC comparison
         $\mathcal{C}_{\text{new}} \leftarrow \mathcal{C}_{\text{new}} \cup \{\mu_{j,1}, \mu_{j,2}\}$ if split accepted else $\mathcal{C}_{\text{new}} \cup \{\mu_j\}$
    end for
    if $|\mathcal{C}_{\text{new}}| == |\mathcal{C}|$ or $|\mathcal{C}_{\text{new}}| > K_{\max}$ then
        break
    end if
     $\mathcal{C} \leftarrow \mathcal{C}_{\text{new}}$
     $K \leftarrow |\mathcal{C}|$
end while
return $\mathcal{C}^*$
Knowl 2 — Local Centroid Splitting and Model Selection
model/method
In the Improve-Structure step of X-means, each parent centroid $\mu_j$ currently owning a subset of points $D_j \subseteq D$ is tested for splitting into two children $\mu_{j,1}$ and $\mu_{j,2}$ :
1. Two candidate child centroids are instantiated by displacing $\mu_j$ along a randomly oriented vector by a distance proportional to the geometric size of the region $D_j$ in opposite directions.
2. A local 2-means clustering algorithm is executed exclusively on the subset $D_j$ until the positions of $\mu_{j,1}$ and $\mu_{j,2}$ converge.
3. A local Bayesian Information Criterion (BIC) test is performed comparing the single parent model ( $k=1$ ) against the two-children model ( $k=2$ ) on the subset $D_j$ .
4. If $\text{BIC}(k=2) > \text{BIC}(k=1)$ , the split is accepted and the parent centroid is replaced by the two child centroids. Otherwise, the split is rejected and the parent centroid is retained.
This localized decision structure explores up to $2^K$ possible split configurations in parallel per global iteration while isolating local cluster structure decisions.
Knowl 3 — Bayesian Information Criterion (BIC) for Spherical Gaussian Clustering
equation
Under the assumption that data points are generated by $K$ identical spherical Gaussian distributions with isotropic variance $\sigma^2$ , the Bayesian Information Criterion (BIC) for model $M_j$ on dataset $D$ with $|D| = R$ in $M$ dimensions is:

$\text{BIC}(M_j) = \hat{l}_j(D) - \frac{p_j}{2} \log R$

where $\hat{l}_j(D)$ is the log-likelihood of the data at the maximum likelihood estimate, and $p_j$ is the number of free parameters. The maximum likelihood estimate of the isotropic variance $\hat{\sigma}^2$ over the entire dataset partitioned into $K$ clusters with centroids $\mu_{(i)}$ assigned to point $x_i$ is:

$\hat{\sigma}^2 = \frac{1}{R - K} \sum_{i=1}^{R} \|x_i - \mu_{(i)}\|^2$

The conditional log-likelihood evaluated on the subset $D_n$ containing $R_n = |D_n|$ points belonging to centroid $n$ is:

$\hat{l}(D_n) = -\frac{R_n}{2} \log(2\pi) - \frac{R_n \cdot M}{2} \log(\hat{\sigma}^2) - \frac{R_n - K}{2} + R_n \log R_n - R_n \log R$

The total number of free parameters $p_j$ for $K$ clusters in $M$ dimensions consists of $(K - 1)$ independent cluster probabilities, $M \cdot K$ centroid coordinates, and $1$ shared variance parameter:

$p_j = (K - 1) + M \cdot K + 1 = K(M + 1)$
Knowl 4 — KD-Tree Acceleration and Geometric Blacklisting
model/method
X-means accelerates both global $K$ -means and local split iterations by indexing the entire dataset in a multiresolution $kd$ -tree without introducing numerical approximations.

Each node in the $kd$ -tree represents a subset of points and stores its spatial bounding box, total point count $R_v$ , and the coordinate sum vector $\sum_{x \in v} x$ . When assigning points to centroids, a recursive traversal maintains a candidate list of centroids for each node. Centroids that are geometrically proven to be farther from every point in the node's bounding box than another candidate centroid are pruned ("blacklisted").

If the candidate list for a $kd$ -tree node reduces to a single dominant centroid, the traversal terminates at that node, and the centroid's sufficient statistics (point count and center-of-mass sum) are directly incremented by $R_v$ and $\sum_{x \in v} x$ . For local split operations (Improve-Structure), once a $kd$ -tree node is determined to be owned entirely by a single parent centroid, recursive assignment continues restricted solely to the two child candidates of that parent.
Knowl 5 — State Caching and Invariant Preservation Across Structure Refinements
model/method
To eliminate redundant computations during iterative model searches, X-means employs two state-caching mechanisms:
1. Write-Once Centroid Tracking and Node Contribution Caching: Centroid coordinates are stored in a write-once structure with unique integer identifiers. When a $kd$ -tree node's list of competing centroids does not change across iterations and those centroids have not moved, the cached contribution to their sufficient statistics is reused without re-traversing descendant nodes. Centroid comparison is performed in $O(1)$ time using a hash-table lookup of identifiers.
2. Zombie Centroid Caching: When a parent centroid's children are rejected during local testing, they are preserved in a "zombie" state. If the parent's location remains unchanged in subsequent iterations, the cached children and their local 2-means results are instantly recalled rather than recomputed from scratch.
Knowl 6 — Distortion and Cluster Estimation Accuracy on Synthetic Data
empirical result
On synthetic datasets generated from mixtures of 250 spherical Gaussians in 3 dimensions with sample sizes ranging from 75,000 to 125,000 points, X-means achieved lower average squared distortion per point (averaging approximately $0.00067$ to $0.00072$ ) than standard $K$ -means initialized with the true number of clusters $K = 250$ (which averaged $0.00078$ to $0.00083$ ). This occurs because X-means incrementally places new centroids in regions where existing clusters fail BIC tests rather than relying on a single global random initialization.

When identifying the true number of classes ( $K=100$ ) on 2-D datasets across sizes from 5,000 to 40,000 points, X-means consistently estimated between 88 and 92 clusters (within 15% of the true count). X-means tended to slightly underestimate $K$ and remained insensitive to dataset size $R$ , whereas grid-search $K$ -means using global BIC over-estimated $K$ (outputting 100 to 106 clusters) and scaled upward as $R$ increased.

Knowl 7 — Error in Cluster Count Estimation Across Varying True Classes

data/table

The following table compares the mean absolute error in the estimated number of clusters produced by grid-search $K$ -means (evaluating 20 equally spaced values up to $2K$ ) versus X-means (searching the range $[2, \dots, 2K]$ ) on 2-D synthetic datasets with sample sizes between 4,000 and 36,000 points:

The measurements show that for smaller numbers of true classes ( $K=50$ ), X-means achieves lower absolute error ( $3.00$ ) than grid-search $K$ -means ( $3.53$ ). For higher cluster densities ( $K=100$ and $K=150$ ), X-means exhibits larger under-estimation error because randomly generated neighboring Gaussian components overlap and are statistically modeled more parsimoniously as single clusters under the BIC penalty.

Knowl 8 — Computational Speedup and Scalability
empirical result
On synthetic datasets in 3 dimensions with 250 classes, X-means demonstrated superior computational scaling compared to iterated accelerated $K$ -means searching over multiple values of $K$ :
- Across dataset sizes from 5,000 to 40,000 points, X-means executed in approximately half the run-time of iterated $K$ -means (e.g., ~190 seconds vs. ~340 seconds at 40,000 points on a 233-MHz Pentium-2 processor).
- On a dataset containing over 330,000 data points, X-means completed in 238 seconds, whereas naive $K$ -means evaluating 10 candidate values of $K$ required 7,793 seconds, representing a 32-fold speedup.
- The speed advantage expands as the dataset size $R$ grows because localized 2-means tests and $kd$ -tree sufficient statistics eliminate redundant distance evaluations across distant clusters.
Knowl 9 — Application of X-means to Galaxy Redshift Clustering
empirical result
X-means was evaluated on observational astronomical datasets to discover characteristic galaxy cluster sizes:
- Sloan Digital Sky Survey (SDSS): On a dataset of approximately 800,000 sky objects partitioned into 18 spatial cells, X-means searched $K \in [R/1000, R/100]$ and estimated an average cluster size of $473 \pm 25.5$ objects, compared to $572 \pm 40.8$ objects for iterated $K$ -means. X-means clustered the full 800,000-point dataset into 4,000 resulting centroids in 4.5 hours on a 600-MHz DEC Alpha, whereas iterated $K$ -means exceeded double that run-time before hitting hard resource limits.
- Las Campanas Redshift Survey: When clustering galaxy coordinates with $K$ constrained between 50 and 500, X-means found solutions with BIC scores comparable to an optimized standard $K$ -means search over 10 candidate $K$ values while completing the search 8 times faster.
Knowl 10 — Theoretical and Computational Limitations of X-means
limitation
The X-means algorithm has two primary structural limitations:
1. Distributional Assumptions: The splitting score relies on identical spherical Gaussian distributions with isotropic covariance $\Sigma = \text{diag}(\sigma^2)$ and hard cluster assignments. If the true data clusters are non-spherical, elongated, or have heterogeneous variances, the BIC test can over-split natural clusters or select an inaccurate model structure.
2. Dimensionality Bottleneck of Spatial Trees: The exact geometric blacklisting acceleration depends on multiresolution $kd$ -trees. While exact and effective in low dimensions (empirically demonstrated up to 4 dimensions, with practical viability up to roughly 7 dimensions), $kd$ -tree spatial partitioning suffers from the curse of dimensionality, losing pruning efficiency in high-dimensional feature spaces.

Coverage note — No substantial contributed material was omitted. All core components of X-means—including the model search algorithm, local splitting procedure, BIC equation formulation, kd-tree acceleration, caching optimizations, synthetic and astronomical empirical results, and stated limitations—have been extracted.

References

1.Bishop, C. M. (1995). Neural networks for pattern recognition. Oxford: Clarendon Press.
2.Bradley, P. S., & Fayyad, U. M. (1998). Refining initial points for K-Means clustering. Proceedings of the Fifteenth International Conference on Machine Learning (pp. 91–99). Morgan Kaufmann, San Francisco, CA.
3.Deng, K., & Moore, A. W. (1995). Multiresolution instance-based learning. Proceedings of the Twelfth International Joint Conference on Artificial Intelligence (pp. 1233–1239). San Francisco: Morgan Kaufmann.
4.Duda, R. O., & Hart, P. E. (1973). Pattern Classification and Scene Analysis. John Wiley & Sons.
5.Ester, M., Kriegel, H.-P., & Xu, X. (1995). A database interface for clustering in large spatial databases. Proceedings of First International Conference on Knowledge Discovery and Data Mining. Menlo Park: AAAI.
6.Kass, R., & Wasserman, L. (1995). A reference Bayesian test for nested hypotheses and its relationship to the Schwarz criterion. Journal of the American Statistical Association, 90, 773–795.
7.Las Campanas Redshift Survey (1998). http://manaslu.astro.utoronto.ca/~lin/lcrs.html.
8.Meila, M. (1999). Efficient Tree Learning. Doctoral dissertation, Massachusetts Institute of Technology, Department of Computer Science, Cambridge, MA.
9.Moore, A. W. (1999). Very fast mixture-model-based clustering using multiresolution kd-trees. Advances in Neural Information Processing Systems 10 (pp. 543–549). Morgan Kaufmann.
10.Ng, R. T., & Han, J. (1994). Efficient and effective clustering methods for spatial data mining. Proceedings of VLDB.
11.Pelleg, D., & Moore, A. (2000). Accelerating exact k-means with geometric reasoning (Technical Report CMU-CS-00-105). Carnegie Mellon University, Pittsburgh, PA. Also available from http://www.cs.cmu.edu/~dpelleg/.
12.The Sloan Digital Sky Survey (1998). www.sdss.org.
13.Wasserman, L., & Moore, A. Density Estimation with Accelerated, Exact, Mixture Models. In press.
14.Zhang, T., Ramakrishnan, R., & Livny, M. (1995). BIRCH: An efficient data clustering method for very large databases., Proceedings of ACM SIGMOD (pp. 103–114).

Citation

MLA

Pelleg, D., and A. Moore. “X-means: Extending K-means with Efficient Estimation of the Number of Clusters”. International Conference on Machine Learning, 2000, pp. 727–34, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.3377.

APA

Pelleg, D., & Moore, A. (2000). X-means: Extending K-means with Efficient Estimation of the Number of Clusters. International Conference on Machine Learning, 727–734. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.3377

Chicago

Pelleg, D., and A. Moore. 2000. “X-means: Extending K-means with Efficient Estimation of the Number of Clusters”. International Conference on Machine Learning, 727–34. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.3377.

Harvard

Pelleg, D. and Moore, A. (2000) “X-means: Extending K-means with Efficient Estimation of the Number of Clusters”, International Conference on Machine Learning, pp. 727–734. Available at: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.3377.

Vancouver

1. Pelleg D, Moore A (2000) X-means: Extending K-means with Efficient Estimation of the Number of Clusters. International Conference on Machine Learning 727–734

BibTeX

@article{pelleg2000means,
  title = {X-means: Extending K-means with Efficient Estimation of the Number of Clusters},
  author = {Pelleg, Dan and Moore, Andrew},
  year = {2000},
  journal = {International Conference on Machine Learning},
  pages = {727-734},
  url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.3377}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: Authors

True Classes	$K$ -means Error	X-means Error
50	$3.53 \pm 0.37$	$3.00 \pm 0.89$
100	$5.77 \pm 0.58$	$9.06 \pm 1.00$
150	$9.65 \pm 4.28$	$21.43 \pm 2.26$

X-means: Extending K-means with Efficient Estimation of the Number of Clusters

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — X-means Clustering Algorithm

Knowl 2 — Local Centroid Splitting and Model Selection

Knowl 3 — Bayesian Information Criterion (BIC) for Spherical Gaussian Clustering

Knowl 4 — KD-Tree Acceleration and Geometric Blacklisting

Knowl 5 — State Caching and Invariant Preservation Across Structure Refinements

Knowl 6 — Distortion and Cluster Estimation Accuracy on Synthetic Data

Knowl 7 — Error in Cluster Count Estimation Across Varying True Classes

Knowl 8 — Computational Speedup and Scalability

Knowl 9 — Application of X-means to Galaxy Redshift Clustering

Knowl 10 — Theoretical and Computational Limitations of X-means

References

Citation

BibTeX

Access the Paper