The Price of Explainability in Clustering

30 concepts14 papers1 proposal

Standard clustering algorithms like $k$-means and $k$-medians partition data by assigning each point to its nearest cluster center. While mathematically clean, this strategy produces cluster boundaries known as Voronoi diagrams. To explain why a specific data point belongs to a given cluster, a human must evaluate complex distance formulas across all dimensions simultaneously. In high-dimensional spaces, these boundaries become a black box.

To make clustering interpretable, a growing body of research focuses on explainable clustering. Instead of Voronoi cells, the data space is partitioned using an axis-aligned decision tree. Every split in the tree relies on a simple, human-readable threshold rule (e.g., "Is feature $X > 5$?"). Each leaf node represents a distinct cluster.

However, forcing cluster boundaries to align with coordinate axes introduces a fundamental dilemma: we sacrifice geometric flexibility. This sacrifice incurs a performance penalty known as the Price of Explainability (PoE)—the ratio of the cost of an explainable, tree-based clustering to the cost of an unconstrained, optimal clustering.


Geometric Intuition: Why Axis-Aligned Cuts Cost More

To understand why explainability costs anything at all, imagine a simple two-dimensional dataset with two cluster centers positioned diagonally from one another.

       Center B
          /
         /  <-- Ideal Oblique Boundary
        /
  Center A

The ideal, unconstrained boundary between these two centers is an oblique line running perpendicular to the vector connecting them. An unconstrained algorithm separates these groups perfectly with a single boundary.

An explainable clustering algorithm, however, is restricted to horizontal and vertical cuts. To approximate that diagonal line, a decision tree must construct a "staircase" pattern of alternating axis-parallel splits.

          |--- Center B
          |
     |----|
     |
-----| <-- Axis-Aligned Staircase Boundary
Center A

This restriction introduces two main problems:

  1. Misassignment Overhead: Data points located in the "corners" of the staircase are cut off from their true closest center and forced into a sub-optimal cluster, increasing the total distance metric.
  2. Capacity Constraints: As noted by Bandyapadhyay et al. and Hu et al., standard explainable clustering restricts the decision tree to exactly $k$ leaves to match the number of clusters. This constraint limits the algorithm's ability to build finer staircases to approximate complex boundaries.

The Divergent Costs of $k$-Medians and $k$-Means

The exact penalty we pay for explainability depends heavily on how we measure distance. The field has revealed a stark contrast between the $k$-medians objective (which minimizes linear distances) and the $k$-means objective (which minimizes squared distances).

Why $k$-Medians Costs Only Logarithmically More

For $k$-medians, the Price of Explainability is remarkably small. Early work by Moshkovitz et al. proved that a tree-based clustering could achieve a PoE independent of the data's dimensionality, establishing an initial upper bound of $O(k)$. This was later drastically improved to a near-optimal $O(\log k \log \log k)$ by Makarychev et al..

Recently, Gupta et al. settled the exact worst-case PoE for $k$-medians, proving it is precisely $1 + H_{k-1}$, where $H$ is the harmonic number (which scales tightly with $\ln k$).

To understand why this logarithmic bound is achievable, consider the randomized cutting strategies developed by the authors. In a simplified version of the optimal RandomCoordinateCut algorithm analyzed by Makarychev et al., the algorithm chooses a cutting plane uniformly at random within the bounding box of the cluster centers.

Because the $k$-medians objective scales linearly with distance, the probability that a random cut accidentally splits a data point away from its closest center is directly proportional to the distance between that point and its center. By recursively picking cuts that are likely to separate distant cluster centers while sparing tightly clustered data points, the expected added cost scales only logarithmically with the total number of clusters $k$.

Why $k$-Means Incurs a Higher Penalty

For $k$-means, the squared Euclidean distance metric amplifies the cost of mistakes. If an axis-aligned cut displaces a point even slightly further from its optimal center, squaring that distance penalizes the objective function severely.

Consequently, early frameworks faced a linear penalty proportional to $k$. Makarychev et al. and Gupta et al. successfully pushed the upper bound down to $O(k \ln \ln k)$. This confirms that while explainability for squared-distance objectives is fundamentally more expensive than for linear ones, the overhead can still be kept sub-linear relative to the number of clusters.


Algorithmic Paradigms for Building Explainable Trees

Researchers have developed several distinct strategies to construct these interpretable trees while minimizing the PoE.

Top-Down Greedy and Oblivious Partitioning

The foundational algorithm in this space is Iterative Mistake Minimization (IMM), introduced by Moshkovitz et al.. IMM first runs a standard unconstrained clustering to find optimal reference centers, then greedily selects axis-aligned cuts that separate these centers while minimizing the number of data points "mistakenly" separated from their target centers.

To improve efficiency, Gamlath et al. proposed oblivious algorithms. Instead of scanning the entire dataset to evaluate splits, these algorithms choose cuts by looking exclusively at the geometry of the cluster centers, achieving nearly-tight approximation bounds with extreme computational efficiency.

Balancing Tree Depth and Cost

In practice, a tree with $k$ leaves might still be too deep for a human to read if $k$ is large. To address this, Laber et al. developed the EXSHALLOW algorithm. It introduces a tunable hyperparameter, $\lambda$, allowing practitioners to explicitly trade off clustering quality against explanation conciseness:

$$\text{Total Cost} = \text{Clustering Cost} + \lambda \cdot \text{Tree Depth}$$

Continuous Optimization via Gradients

Traditional decision trees are constructed using greedy, non-differentiable splits (like CART). To bypass this limitation, Marton et al. developed GradTree. Rather than relying on top-down heuristics, GradTree uses a mathematical trick called the straight-through operator to route data through hard, axis-aligned splits while allowing the parameters of the entire tree to be optimized simultaneously via gradient descent. This preserves strict if-then interpretability while leveraging modern deep-learning optimization.


Hardness and Generalizations

The feasibility of explainable clustering depends heavily on the underlying objective function. Eduardo Sany Laber demonstrates that while objectives like $k$-means and $k$-medians admit near-optimal polynomial-time approximations, finding the absolute optimal explainable tree is NP-hard and generally hard to approximate.

Furthermore, some clustering objectives are fundamentally incompatible with explainability. For example, Laber et al. showed that maximum-spacing clustering—which tries to maximize the distance between different clusters—suffers a massive penalty under axis-aligned constraints, where the PoE can scale linearly with the number of data points rather than the number of clusters.

Despite these challenges, the core principles of bounding the price of explainability continue to expand into complex domains:

  • Kernel Methods: Fleissner et al. extended these theoretical boundaries to non-linear spaces, proving that powerful kernel-based clusterings can be successfully mapped back to interpretable decision trees with bounded performance losses.
  • Deep Learning: In computer vision and representation learning, Rymarczyk et al. adapted these concepts for Novel Class Discovery (ProtoNCD). By forcing deep networks to identify unseen categories using discrete, human-interpretable "prototypical parts" instead of abstract latent vectors, they demonstrate that the price of explainability can be managed even within deep neural architectures.

Key Foundational Work

Near-Optimal Algorithms for Explainable k-Medians and k-Means (2021) — contributed 7 concept elements to this direction.
On the price of explainability for some clustering problems (2021) — contributed 7 concept elements to this direction.
Explainable k-Means and k-Medians Clustering (2020) — contributed 2 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_price_of_explainability_abdebb74,
  title = {price of explainability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/price-of-explainability/rdr_abdebb74a99b4ee791c8c36f4ecb6eb2},
  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_price_of_explainability_abdebb74_v1,
  title = {price of explainability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/price-of-explainability/rdr_abdebb74a99b4ee791c8c36f4ecb6eb2/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