Large-Scale Clustering Based on Data Compression

Xudong Ma

TL;DR

This paper introduces a distributed optimization framework for large-scale clustering by framing the task as a data compression problem. By proving that the duality gap of this non-convex problem vanishes as the dataset size grows, the author demonstrates that the Dantzig-Wolfe decomposition method can be effectively used to solve massive clustering tasks across multiple coordinated computers.

What Problem Does This Paper Address?

Standard clustering algorithms, particularly the state-of-the-art Expectation-Maximization (EM) for Gaussian Mixture Models, struggle with three major hurdles:

  1. Scalability: They often require the entire dataset to reside in a single machine's memory, which is impossible for terabyte- or petabyte-scale databases.
  2. Convergence Speed: EM is a first-order optimization method, meaning it can be agonizingly slow to converge on complex datasets.
  3. Numerical Stability: EM often fails or "blows up" when encountering singular covariance matrices (where data lies on a lower-dimensional subspace) or when the number of model components exceeds the actual number of clusters.

The author seeks a method that is mathematically rigorous, distributed by design, and robust against the numerical pitfalls of traditional statistical modeling.

Methods

The paper's approach is built on the principle that optimal clustering should induce optimal data compression.

  1. Objective Function: The problem is formulated as maximizing "classification gain," a metric from information theory. For Gaussian distributions, this translates to an objective function involving the entropy of cluster assignments and the log-determinants of cluster covariance matrices.
  2. Handling Non-Convexity: Clustering is inherently non-convex. Usually, this prevents the use of powerful decomposition techniques like Dantzig-Wolfe, which require zero duality gaps. However, the author provides a theoretical proof using Azuma’s Inequality showing that as the number of samples ($N$) approaches infinity, the duality gap vanishes.
  3. Dantzig-Wolfe Decomposition: This allows the global optimization problem to be broken down into small-scale sub-problems.
  4. Distributed Architecture: The system consists of several "database hosts" and one "center processor." Each host performs local computations on its own slice of data and sends only a small amount of summary information (parameters) back to the center, minimizing network traffic.

Datasets

The paper evaluates the algorithm using synthetic 2D datasets designed to test specific edge cases:

  • Overlapping Clusters: Two Gaussian clusters with the same mean but different orientations.
  • Singular Covariance Matrix: A scenario where one cluster's data is perfectly linear (singular matrix), a known "killer" for standard EM.
  • Different Means: Two clusters with distinct centers and different covariance structures.

While the paper discusses "large-scale" theory, the numerical experiments used a total of 2,048 data samples distributed across two hosts to demonstrate proof-of-concept.

Key Insights and Ideas

  • The "Large-Scale" Paradox: Counter-intuitively, the optimization problem becomes easier to solve optimally as it gets larger. The proof that the duality gap vanishes at scale is the "aha moment" that justifies using linear programming-style decomposition on a non-linear, non-convex clustering problem.
  • Compression as a Proxy: By viewing clustering through the lens of data compression, the author avoids some of the heuristic pitfalls of distance-based clustering (like k-means) and provides a clear information-theoretic objective.
  • Robustness to Singularity: By adding a tiny "white noise" term ($\sigma_n^2 I_D$) to the covariance matrices, the algorithm remains numerically stable even when data is perfectly correlated, without significantly degrading the clustering accuracy.

Key Results

  • Accuracy: On overlapping clusters, the algorithm achieved a misclassification rate of 5.32%. In the singular covariance matrix test, it achieved 1.71%, and with different means, 2.29%.
  • Stability: Unlike standard EM, the proposed algorithm did not encounter numerical difficulties or convergence failures when dealing with singular matrices.
  • Efficiency: The algorithm showed fast convergence of the unitary matrices ($A_i$) used to diagonalize the problem, suggesting it reaches a solution in fewer iterations than first-order methods.

Limitations and Future Work

  • Gaussian Assumption: The current formulation assumes data follows a mixture of Gaussians. While robust, it may not capture clusters with highly non-linear, manifold-like shapes (e.g., concentric circles).
  • Experimental Scale: While the theory is built for "Large-Scale" data, the numerical results are presented on relatively small synthetic sets (thousands of points). Testing on actual terabyte-scale real-world data would be the natural next step.
  • Hyperparameter Selection: The paper assumes the number of clusters ($J$) is known. Future work could integrate automated model selection to determine the optimal number of clusters during the optimization process.

Summary updated

BibTeX
@inproceedings{ma2011large,
  author = {Xudong Ma},
  title = {{Large-Scale Clustering Based on Data Compression}},
  booktitle = {ITNG},
  year = {2011},
  doi = {10.1109/itng.2011.98},
}
Figure