Geometry and the Price of Explainable Clustering

15 concepts7 papers2 proposals

Standard clustering algorithms like $k$-means and $k$-medians partition data by minimizing geometric distances to a set of central points. While mathematically clean, this process yields complex, multi-dimensional Voronoi cells. For a human to understand why a specific data point belongs to a given cluster, they must evaluate a complex mathematical formula across every single feature simultaneously.

To make clustering "explainable by design," a growing body of research constrains cluster boundaries to be axis-aligned splits. This allows the final clustering model to be represented as a shallow decision tree. A human can inspect the tree and understand any cluster assignment through a sequence of simple, single-feature rules (e.g., "if Feature $A > 5$ and Feature $B \le 2$").

However, forcing cluster boundaries to conform to a rigid, axis-aligned grid introduces an inevitable penalty: the Price of Explainability (PoE). This is the ratio between the cost of an optimal explainable clustering (constrained by a decision tree) and the cost of an optimal unrestricted clustering. The core challenge in this field is understanding how this price scales with the number of clusters ($k$) and the dimensionality of the data ($d$).

Dimension-Independent Baselines

When we restrict ourselves to axis-aligned cuts, a natural worry is that high-dimensional datasets will suffer an exponential explosion in clustering cost. If every dimension requires its own set of cuts to isolate a cluster, the tree could grow dangerously deep, destroying both interpretability and accuracy.

In a foundational paper, Moshkovitz et al. proved that this explosion can be avoided. They introduced the Iterative Mistake Minimization (IMM) algorithm, demonstrating that it is possible to achieve approximation guarantees that are entirely independent of both the number of data points ($n$) and the dimensionality of the feature space ($d$). Instead, the performance bounds depend solely on the number of clusters ($k$).

To understand why dimension independence is possible, consider how we might cut space randomly. If we select coordinates to slice based on the distances between cluster centers, we can isolate clusters without needing to inspect every single dimension. Makarychev et al. proved that a simple randomized strategy called RandomCoordinateCut is mathematically optimal for explainable $k$-medians, achieving a competitive ratio of $2 \ln k + 2$.

The intuition behind this optimality is elegant: by choosing cuts randomly but proportionally to the spacing between clusters, the probability of slicing through a dense cluster of data points remains low. Because the overhead scales only with the number of clusters $k$, the interpretability of high-dimensional datasets does not degrade as the number of features increases.

The Low-Dimensional Advantage

While dimension-independent bounds protect us in high-dimensional settings, they can be overly pessimistic when the data lives in a low-dimensional space ($d \ll k$). If you are clustering data in two or three dimensions, a penalty that scales linearly or quadratically with the number of clusters $k$ is an overestimation of the actual cost.

To bridge this gap, Laber et al. shifted the analytical focus toward dimension-dependent bounds. The authors demonstrated that for objectives like $k$-medians, the price of explainability scales with the data dimension and the logarithm of the number of clusters ($\log k$), rather than linearly with $k$ itself.

Why does low dimensionality dramatically lower the price of explainability? In a low-dimensional space, the geometric constraints are much tighter, meaning that clusters cannot be arranged in complex, high-dimensional configurations that defy axis-aligned separation. You do not need a massive sequence of cuts to isolate a cluster; a few well-placed axis-aligned boxes can capture the data's natural structure without slicing through neighboring dense regions.

For instance, Hu et al. showed that in a two-dimensional space, the cost of using interpretable decision boundaries scales nearly logarithmically with $k$. This represents a massive efficiency gain over previous linear estimates, proving that the spatial constraints of low-dimensional settings naturally mitigate the interpretability tax. Recognizing this geometric advantage, Esfandiari et al. designed specialized algorithms for low-dimensional settings that achieve an $O(d \log^2 d)$ approximation ratio for $k$-medians, completely bypassing a heavy dependence on $k$ when $d$ is small.

Computational Hardness and Practical Heuristics

While the theoretical bounds for explainable clustering have become increasingly tight, finding the absolute best explainable tree remains a daunting computational challenge. Laber established that optimizing explainable clustering problems under common cost functions (such as $k$-means, $k$-medians, and $k$-centers) is APX-hard. This means that efficient, exact near-optimal solutions are mathematically unlikely to exist unless $P=NP$.

Because finding the exact optimal tree is hard, researchers focus on designing fast, greedy heuristics that still preserve these theoretical guarantees. For information-theoretic or entropy-based clustering, Laber et al. introduced the RATIO-GREEDY algorithm. By ensuring that the approximation guarantees depend solely on the number of clusters or dimensions rather than the dataset size, their approach maintains stable performance as data scales, running up to 55x faster than traditional methods.

On the geometric side, algorithms like Ex-Greedy, proposed by Laber et al., leverage low-dimensional insights to build decision trees that outperform unrestricted baselines in practical, real-world scenarios. By understanding whether a dataset's complexity is driven by its cluster count ($k$) or its dimensionality ($d$), practitioners can deploy algorithms that minimize the price of explainability, delivering models that are both statistically accurate and human-readable.

Key Foundational Work

Explainable k-Means and k-Medians Clustering (2020) — contributed 2 concept elements to this direction.
New results on information theoretic clustering (2019) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_dimension_dependent_explainability_cost_19a3b8ea,
  title = {dimension-dependent explainability cost},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/dimension-dependent-explainability-cost/rdr_19a3b8ea168343159c19db6f138b1c0d},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_dimension_dependent_explainability_cost_19a3b8ea_v1,
  title = {dimension-dependent explainability cost},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/dimension-dependent-explainability-cost/rdr_19a3b8ea168343159c19db6f138b1c0d/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake