Clustering is difficult only when it does not matter

Amit Daniely, Nati Linial, Michael E. SaksarXiv 2012 · OpenReview

Abstract

Numerous papers ask how difficult it is to cluster data. We suggest that the more relevant and interesting question is how difficult it is to cluster data sets that can be clustered well. While clustering objectives like $k$-means are NP-hard in the worst case, practitioners find clustering tasks tractable in reality. We introduce a theoretical framework of clustering in metric spaces revolving around a notion of "good clustering." We show that if a good clustering exists, it can often be found efficiently. Our conclusion is that contrary to popular belief, clustering should not be considered a hard task when the results are meaningful.

1. Introduction: The Disparity of Clustering

In the realm of computational complexity, clustering is often viewed through a pessimistic lens. Popular objective functions, such as $k$-means or $k$-medians, are known to be NP-hard to optimize. This suggests that finding the "best" partition of a dataset is fundamentally infeasible for large-scale problems. However, this theoretical barrier stands in stark contrast to the experience of practitioners, who successfully employ clustering algorithms across diverse fields every day.

This paper addresses this disparity by arguing that complexity theory focuses on the wrong question. Instead of asking how hard it is to optimize an arbitrary objective function on any possible dataset, we should ask: "How hard is it to find a meaningful clustering when one actually exists?" The authors propose that if a dataset is so unstructured that finding an optimal partition is computationally difficult, the resulting clusters are likely not meaningful. In essence, clustering is either easy or pointless.

2. A Formal Framework for "Good" Clustering

To bridge the gap between theory and practice, the authors introduce a formal definition of "good clustering" within finite metric spaces. This framework relies on two primary parameters:

  1. Mass ($\alpha$): This parameter defines the minimum fraction of points (probability mass) a cluster must contain. This constraint prevents trivial solutions where every individual point is treated as its own cluster.
  2. Separation ($\gamma$): This is a proximity parameter. A cluster is considered $(\alpha, \gamma)$-good if every point within the cluster is significantly closer (by a factor of $\gamma$) to its own cluster members than to any point outside the cluster.

By shifting the focus from global optimization (minimizing a sum of squares) to local proximity, the authors define clusters based on their internal stability. If every point "feels" much closer to its neighbors than to outsiders, the clustering structure is robust and, as the paper demonstrates, discoverable.

3. Algorithmic Regimes

The paper identifies two distinct algorithmic strategies based on the size of the clusters:

3.1 Large Clusters (High $\alpha$)

When clusters are relatively large, the authors utilize an exhaustive sampling approach. By taking a small random sample of the data, they demonstrate that the internal partitions of this sample can be used to construct a Voronoi diagram. With high probability, this diagram will closely approximate the true $(\alpha, \gamma)$-clustering of the entire dataset. This proves that for any fixed $\gamma > 1$ and $\alpha > 0$, there exists a polynomial-time algorithm to identify all "good" clusterings.

3.2 Small Clusters and Hierarchical Structure (Low $\alpha$)

When clusters are small, sampling becomes less reliable. However, the authors prove a structural property: for a separation factor $\gamma > 3$, "good" clusters must follow a simple hierarchical tree structure. Specifically, any two intersecting clusters must be nested (one contained within the other). This structural simplicity allows the use of dynamic programming to find the optimal partition efficiently, even when the number of clusters is large.

4. The Phase Transition of Hardness

One of the most significant contributions of the paper is the identification of a "hardness threshold." The authors demonstrate a sharp transition in computational complexity based on the separation parameter $\gamma$:

  • Tractable ($\gamma > 3$): Finding a partition into $(\alpha, \gamma)$-clusters is always efficient (polynomial time).
  • Intractable ($\gamma = 2.5$): The problem becomes NP-hard. This is proven via a reduction from the 3-Dimensional Matching problem using synthetic graph metrics.

This gap suggests that there is a specific level of "clarity" or "separation" required in data for it to be computationally tractable. When data is well-separated, the structure reveals itself easily; when it is ambiguous, the problem becomes computationally insurmountable.

5. Conclusion

The "Easy or Pointless" paradigm shifts the goal of clustering from optimizing a mathematical function to recovering hidden, meaningful structures. By proving that $(\alpha, \gamma)$-good clusterings can be found in polynomial time (for $\gamma > 3$), the authors provide a theoretical justification for why clustering works in practice despite worst-case complexity results.

While questions remain regarding the exact threshold between $\gamma = 2.5$ and $\gamma = 3$, and the potential for more efficient deterministic algorithms, this work establishes a solid theoretical basis for clustering. It suggests that the difficulty of clustering is not a fundamental barrier, but rather a symptom of attempting to find structure where none exists.

Summary updated

Abstract

Numerous papers ask how difficult it is to cluster data. We suggest that the more relevant and interesting question is how difficult it is to cluster data sets {\em that can be clustered well}. More generally, despite the ubiquity and the great importance of clustering, we still do not have a satisfactory mathematical theory of clustering. In order to properly understand clustering, it is clearly necessary to develop a solid theoretical basis for the area. For example, from the perspective of computational complexity theory the clustering problem seems very hard. Numerous papers introduce various criteria and numerical measures to quantify the quality of a given clustering. The resulting conclusions are pessimistic, since it is computationally difficult to find an optimal clustering of a given data set, if we go by any of these popular criteria. In contrast, the practitioners' perspective is much more optimistic. Our explanation for this disparity of opinions is that complexity theory concentrates on the worst case, whereas in reality we only care for data sets that can be clustered well. We introduce a theoretical framework of clustering in metric spaces that revolves around a notion of "good clustering". We show that if a good clustering exists, then in many cases it can be efficiently found. Our conclusion is that contrary to popular belief, clustering should not be considered a hard task.
BibTeX
@misc{daniely2012clustering,
  author = {Amit Daniely and Nati Linial and Michael E. Saks},
  title = {{Clustering is difficult only when it does not matter}},
  year = {2012},
  eprint = {1205.4891},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1205.4891},
}
Figure