Source-linked AI summary
Explainable $k$-Means and $k$-Medians Clustering
Sanjoy Dasgupta, Nave Frost, Michal Moshkovitz, Cyrus Rashtchian
TL;DR
The paper asks whether clustering can remain close to optimal while being explained by a small decision tree. It develops threshold-tree algorithms for unlabeled data and proves limitations alongside approximation guarantees for k-means and k-medians. For two clusters, one threshold cut gives a constant-factor approximation; for general k, the guarantees are O(k) for k-medians and O(k^2) for k-means.
Problem
Cluster assignments from standard algorithms can be hard to explain, while prior tree-based explainable clustering lacked theoretical guarantees against optimal k-means or k-medians.
Method
The paper uses unsupervised binary threshold trees with k leaves, where each internal node partitions data by thresholding one feature.
Results
For k = 2, a single threshold cut achieves a constant-factor approximation; for general k, the algorithm achieves O(k) for k-medians and O(k^2) for k-means.
Takeaways & Limitations
The results provide approximation guarantees for explainable unsupervised clustering and show that explainability can require an Ω(log k) cost increase in some instances.
Takeaways & Limitations
Any threshold tree with k leaves may require depth k −1, and standard top-down procedures such as ID3 may yield arbitrarily high cost.
Abstract
from arXiv · showhide
Clustering is a popular form of unsupervised learning for geometric data. Unfortunately, many clustering algorithms lead to cluster assignments that are hard to explain, partially because they depend on all the features of the data in a complicated way. To improve interpretability, we consider using a small decision tree to partition a data set into clusters, so that clusters can be characterized in a straightforward manner. We study this problem from a theoretical viewpoint, measuring cluster quality by the $k$-means and $k$-medians objectives: Must there exist a tree-induced clustering whose cost is comparable to that of the best unconstrained clustering, and if so, how can it be found? In terms of negative results, we show, first, that popular top-down decision tree algorithms may lead to clusterings with arbitrarily large cost, and second, that any tree-induced clustering must in general incur an $Ω(\log k)$ approximation factor compared to the optimal clustering. On the positive side, we design an efficient algorithm that produces explainable clusters using a tree with $k$ leaves. For two means/medians, we show that a single threshold cut suffices to achieve a constant factor approximation, and we give nearly-matching lower bounds. For general $k \geq 2$, our algorithm is an $O(k)$ approximation to the optimal $k$-medians and an $O(k^2)$ approximation to the optimal $k$-means. Prior to our work, no algorithms were known with provable guarantees independent of dimension and input size.
1 Introduction
The paper studies explainable clustering via small threshold trees, seeking concise cluster explanations without sacrificing k-means or k-medians quality. It establishes both fundamental limitations and efficient approximation guarantees.
- Problem formulation: Threshold trees assign points using single-feature thresholds, with k leaves representing k clusters and at most k −1 features along any assignment path.This makes each assignment explainable through the thresholds on its root-to-leaf path.
- Limitations: Ω(k) features may be necessary for bounded approximation, so a threshold tree may require depth k −1 in the worst case.The lower-bound construction shows that fewer features can yield arbitrarily worse cost than optimal clustering.
- Limitations: Standard supervised tree procedures such as ID3 can produce clusterings with arbitrarily high cost, making their splitting criteria unsuitable for low-cost clustering.The paper therefore develops different tree-construction algorithms.
- Contributions: For k = 2, one threshold cut gives a constant-factor approximation with a closely matching lower bound; for general k, the algorithm achieves O(k) for k-medians and O(k^2) for k-means.The general algorithm minimizes mistakes at each node and provides guarantees independent of dimension and input size.
- Research gap: Prior tree-based explainable clustering work was empirical and did not theoretically evaluate k-means or k-medians quality against the optimum.The paper addresses this gap with approximation guarantees for these objectives.
2 Preliminaries
The preliminaries define k-means and k-medians objectives and introduce threshold cuts and binary threshold trees as explainable cluster representations. They also state the approximation framework and motivating limitations of tree depth and greedy decision-tree methods.
- Clustering objectives: k-means and k-medians partition points into k subsets and minimize distances to cluster centers, using Euclidean and Manhattan distances, respectively.Optimal centers are means for k-means and medians for k-medians.
- Threshold cuts: A threshold cut partitions points by whether one feature is at most a threshold, producing two clusters.The cut is specified by a coordinate and a real-valued threshold.
- Threshold trees: A binary threshold tree applies feature-threshold cuts iteratively, with exactly k leaves corresponding to the k clusters.Such a tree uses at most k −1 features and allows assignments to be explained by root-to-leaf conditions.
- Approximation criterion: An a-approximation returns a threshold tree whose cost is at most a times the optimal k-medians or k-means cost.The optimum is denoted by opt.
- Motivating limitations: Some instances require all k −1 features and depth k −1, while standard decision-tree splitting can separate important points and cause arbitrarily worse cost.These examples motivate algorithms that choose splits based on clustering cost rather than standard supervised criteria.
3 Motivating Examples
These examples show that explainable clustering needs enough tree depth and that greedy top-down tree construction can be arbitrarily costly.
- Feature requirements: k −1 features are necessary in the worst case for a threshold tree to achieve an optimal clustering on a simple k-point data set.The data consist of k−1 standard basis vectors and the zero vector; shallower trees merge points despite zero optimal cost.
- Feature requirements: Trees with depth at most k −2 can have non-zero cost when the optimal k-medians/means cost is zero.Projecting onto any k−2 coordinates leaves at least two points indistinguishable.
- Greedy tree construction: Standard top-down decision-tree algorithms can produce clusterings with arbitrarily bad cost.The strategy first obtains cluster labels, then greedily fits a supervised tree to those labels.
- Greedy tree construction: ID3 returns cost Ω(v) as v →∞ on a three-cluster example, while the optimal clustering cost is independent of v.Its first entropy-minimizing split separates the two large clusters and separates the two outliers, forcing one outlier to share a leaf with a large cluster.
4 Two Clusters Using a Single Threshold Cut
For two clusters, the paper searches all single-feature threshold cuts and proves constant-factor guarantees, while matching constructions show that such cuts cannot generally be optimal.
- Algorithm: A single threshold cut is evaluated by scanning the sorted points for each feature and choosing the minimum-cost partition.There are n −1 nonempty threshold partitions per feature; dynamic programming improves the running time to O(nd^2 + nd log n).
- Theoretical guarantees: A threshold cut minimizing disagreements with an optimal clustering achieves at most twice the optimal 2-medians cost.The proof bounds threshold-clustering cost using the minimum number of changes between the cut and optimal clusters.
- Theoretical guarantees: A threshold cut minimizing disagreements with an optimal clustering achieves at most four times the optimal 2-means cost.The same change-count strategy yields the corresponding 2-means guarantee.
- Proof strategy: Hall’s theorem supplies disjoint cross-cluster pairs whose center-distance contributions strengthen the cost lower bound used in the analysis.Each change corresponds to a matched pair, improving the midpoint argument by a factor of two.
- Lower bounds: Optimal clustering is not generally realizable by one threshold cut, except in a small number of dimensions such as d = 1.Thus the constant-factor guarantees are not exact-representability results.
- Lower bounds: Lower bounds approach two for 2-medians and three for 2-means as dimension increases.The construction uses 2d points in two optimal clusters; any threshold cut separates at least one vector from its optimal center.
5 Threshold trees with k > 2 leaves
IMM constructs an explainable threshold tree with k leaves by iteratively minimizing split mistakes relative to reference cluster centers. Its guarantees depend on tree depth, yielding O(k) for k-medians and O(k^2) for k-means in the worst case.
- Algorithm: IMM starts from k reference centers, labels points by their closest center, and builds a top-down threshold tree to fit those labels.The reference centers may come from a constant-factor clustering algorithm or a domain-specific heuristic.
- Algorithm: O(kdn log n) is the deterministic running time after obtaining the initial centers.Dynamic programming avoids recomputing mistake counts for every candidate threshold, and the tree has k −1 internal nodes.
- Algorithm: Each split minimizes the number of points separated from their corresponding centers, then discards those mistakes before recursively processing the child nodes.The procedure terminates at homogeneous subsets and produces exactly k leaves.
- Approximation guarantees: O(H) is IMM’s k-medians approximation and O(Hk) is its k-means approximation for a tree of depth H.The analysis bounds k-medians cost using ℓ1 bounding-box diameters and k-means cost using squared ℓ2 diameters.
- Approximation guarantees: O(k) and O(k^2) are the worst-case approximation factors when the initial centers come from any O(1)-approximation algorithm.If the data permit salient features that identify clusters, the resulting tree may have depth O(log k).
- Lower bound: Ω(log k) is necessary in general for any threshold tree with k leaves under both k-medians and k-means.The lower bound complements IMM’s upper bounds and shows a general price for explainability.
6 Conclusion
The paper establishes approximation guarantees and limitations for explainable clustering using small threshold trees. It gives IMM for general k, proves an Ω(log k) lower bound, and identifies several directions for improving the bounds and extending the framework.
- Conclusion: IMM achieves O(H) approximation for k-medians and O(Hk) approximation for k-means when the threshold tree has depth H and k leaves.For two clusters, a single threshold cut has nearly matching upper and lower bounds.
- Open directions: Improving the upper and lower bounds for general k and characterizing data properties that enable accurate explainable clusters remain open problems.The paper specifically highlights well-separated data and extensions beyond k-means and k-medians.
- Open directions: The lower-bound construction has cluster diameter O(1), separation Ω(d), and hardness caused by randomness in the centers.For this construction, the Θ(log k) factor is tight because the algorithm’s tree depth is about log k.
- Conclusion: Ω(log k) is unavoidable for some data sets: every threshold tree with k leaves has at least this approximation gap for k-medians and k-means.The lower-bound construction uses clusters that are far apart but locally difficult to distinguish by threshold features.
A.1 The data set
The construction uses random binary codewords in dimension d to create well-separated centers while preserving many points under any small coordinate assignment.
- Construction: k random points in {±1}^d establish the dataset construction via the probabilistic method.The proof shows that all required properties hold with positive probability.
- Center properties: d/4 separates every pair of centers in at least d/4 coordinates.This is the second property of the constructed center set.
- Center properties: k(1/2^ℓ−ε) points share every assignment on any ℓ coordinates, for sufficiently small ℓ.The guarantee applies to every ℓ ≤ log k / 50 coordinate set and assignment.
- Tree behavior: d−k points associated with each codeword reach the same leaf in any threshold tree with at most k leaves.A root-to-leaf path uses at most k−1 features, leaving many points agreeing on those features.
- Cost consequence: 1/4 min(α, β)d lower-bounds the cost when points from two distinct codewords share a cluster.The bound holds for both ℓ1 cost and ℓ2 squared cost.
A.3 The threshold tree
The lower-bound argument shows that repeated features or insufficient tree depth force codewords to share clusters, producing high k-means and k-medians cost.
- Lower bound: d^2 ≫ log k · cost(opt) in the constructed case, ruling out an O(log k)-approximation.This establishes a stronger-than-logarithmic cost gap for the relevant tree structure.
- Repeated features: O(log k) approximation is impossible when a feature is reused on one root-to-leaf path.Repeated use makes at least one leaf unreachable by any codeword and forces two codewords into one cluster.
- Insufficient depth: Any threshold tree with a leaf below depth log k / 50 incurs high cost under both k-means and k-medians.The shallow leaf contains many codewords, whose associated points create a large cost contribution.
A.4 Proof of Theorem 5.9
The proof assumes a logarithmic-approximation tree and counts points separated from their codeword’s main cluster across successive levels to lower-bound its cost.
- Main clusters: Each codeword has a main cluster containing at least d−k associated points under the approximation assumption.Claims A.3 and A.4 imply that these points must remain grouped separately from other codewords.
- Mistake counting: Each threshold at level ℓ separates at least (1/2^ℓ−ε)k points from their corresponding main clusters.The statement holds for either threshold value, 0.5 or −0.5.
- Mistake counting: The mistakes caused by repeated feature tests are disjoint across the tree.This follows from Claim A.5 and allows the level-wise counts to be summed.
- Cost lower bound: 2^ℓ−1 nodes occur at each level through approximately log k / 50, yielding a cumulative lower bound on mistakes.The resulting count is then converted into a cost lower bound using Claim A.3.
A.5 IMM Upper Bound for this dataset
For this random-center dataset, the IMM algorithm constructs a shallow threshold tree by reducing the number of consistent centers at each split.
- Depth bound: O(log k) is the tree-depth guarantee established for IMM on the constructed dataset.The proof sketch gives a total depth of at most 6 log_2 k with high probability.
- Tightness: The upper bound for k-medians is tight up to its leading constant on this dataset.This comparison concerns the theorem’s k-medians guarantee.
- Depth bound: 6 log_2 k bounds the total IMM tree depth with high probability.After 3 log_2 k thresholds, the remaining depth is at most another 3 log_2 k.
- Tree construction: IMM avoids splitting on the same feature twice by choosing thresholds that reduce the number of centers in child nodes.Recursion stops when a leaf contains a single center.
- Probability argument: (e/ℓ)^ℓ bounds the probability that a fixed coordinate pattern is consistent with at least ℓ centers.A union bound over all 2^ℓ sign patterns makes this event vanish as k increases.
B Lower bounds for two clusters
The section constructs instances showing that any single threshold cut can be substantially worse than the optimal two-cluster solution for both 2-medians and 2-means.
- 2-medians lower bound: 2-medians lower bounds use a 2d-point construction with two clusters formed by Hamming-distance-one points around all-1 and all-−1 vectors.The construction has d points associated with each of the two reference vectors.
- 2-medians lower bound: 2-medians threshold cuts split the construction into clusters of sizes d−1 and d+1.Any threshold lies between −1 and 0 or between 0 and 1, and symmetry reduces the analysis to one case.
- 2-medians lower bound: (2 −1/d) is the resulting lower-bound approximation factor for 2-medians relative to the optimal clustering.The threshold-cut cost is at least 4d−2, while the optimal cost is at most 2d.
C Upper Bound Proof for 2-Means
The proof establishes that an optimal threshold cut for two-means has cost at most four times the optimal unconstrained clustering cost, using mismatched points and a matching argument.
- Upper bound: 4 is the 2-means approximation factor achieved by an appropriate threshold cut.The proof improves an initially obtainable 6-approximation to 4.
- Tightening the bound: Applying Claim 5.2 only once yields the 4-approximation, whereas applying it twice gives a non-tight 6-approximation.The proof directly accounts for the distance between mismatched points and their new centers in the harder case.
- Mismatch analysis: The proof measures threshold-cut disagreement using t points in the symmetric difference between the optimal clusters and the threshold partition.The mismatched set is separated into points originating from each optimal cluster.
- Matching argument: Halls theorem supplies a matching in which each changed point is paired with a counterpart, allowing optimal cost to charge the full distance between centers.This avoids the weaker midpoint argument, which captures only half of that cost.
D Efficient Implementation via Dynamic Programming for k = 2
For k = 2, the algorithms enumerate threshold cuts along every feature, update cluster costs efficiently, and return the minimum-cost threshold partition.
- Threshold search: The best possible threshold cut is found by evaluating every feature and threshold and selecting the minimum-cost partition.For each feature, points are sorted and all prefix–suffix splits are considered.
- 2-means implementation: O(nd^2 + nd log n) is the total runtime for the 2-means threshold algorithm.The procedure sorts by each feature and computes costs across candidate thresholds.
- Dynamic programming updates: The 2-medians algorithm maintains costs across adjacent thresholds by updating centers when a single vector changes clusters.Coordinate-wise arrays support efficient median updates.
- 2-medians implementation: O(nd^2 + nd log n) is also the total runtime for the 2-medians threshold algorithm.Median centers and threshold costs are updated as one vector moves between clusters.