Clustering is a fundamental unsupervised learning task, yet standard methods like $k$-means often produce "black box" results that are difficult for humans to interpret. This paper, presented at AAAI-22, introduces a novel framework for explainable clustering by identifying a minimal set of outlier points whose removal allows the remaining data to be perfectly partitioned by a simple threshold decision tree. We provide a comprehensive theoretical analysis, including complexity proofs and efficient algorithms for finding these explanations.
The Explainable Clustering Problem
In many high-stakes domains, understanding why a data point belongs to a specific cluster is as important as the assignment itself. Standard clustering algorithms partition data based on complex multi-dimensional distances, making visualization nearly impossible in high-dimensional spaces. This work addresses the challenge of post-modeling explanation: given an existing clustering, how can we find a simple, human-readable rule-set that describes it?
The researchers build upon the concept of threshold trees—decision trees where each internal node splits the data based on a single feature threshold. While forcing a clustering to fit such a tree typically increases the "cost" (e.g., the sum of squared distances), this paper proposes a different metric: explainability as robustness.
As shown in the figure above, a standard clustering (a) may have boundaries that do not align with feature axes. By identifying a small number of "messy" points ($s$), the remaining data can be partitioned using axis-aligned cuts (b), which are inherently more interpretable.
Methodology and Algorithms
The core contribution is the Clustering Explanation model. The goal is to find the minimum number of points $s$ to remove such that the remaining dataset is perfectly representable by a $k$-leaf threshold tree.
The authors propose several algorithmic strategies to solve this optimization problem:
- Greedy Approximation: A polynomial-time algorithm that provides a $(k-1)$-approximation for the number of outliers to be removed.
- Dynamic Programming: A sophisticated DP scheme that uses axis-aligned bounding boxes to find exact solutions.
- Data Reduction (Kernelization): A technique to prune the dataset down to a "kernel" of at most $2(s+1)dk$ essential points. They show that if an explanation exists for this small subset, it exists for the whole dataset. This relies on the insight that only the points with the most extreme coordinates in each cluster (the "boundary" points) really matter for defining the threshold cuts.
Key Results and Complexity Analysis
The paper provides a comprehensive map of the computational landscape for explainable clustering:
- Testing vs. Optimizing: The authors prove that checking if a clustering is already explainable can be done in polynomial time. However, finding the minimum number of points to remove to make it explainable is NP-hard.
- Fixed-Parameter Tractability: They showed that if the number of clusters ($k$) and dimensions ($d$) are small, the problem can be solved efficiently even for very large datasets ($n$).
- Lower Bounds: Using the Exponential Time Hypothesis (ETH), they proved that we cannot expect to find an optimal explainable clustering in $f(k) \cdot n^{o(k)}$ time—meaning as the number of clusters grows, the problem becomes exponentially harder.
- Algorithm Efficiency: They improved the known bounds for finding optimal explainable clusterings to $n^{2d} \cdot (dn)^{O(1)}$, making it feasible for low-dimensional data.
Conclusion
By framing explainability as an outlier detection problem, this research provides a practical path toward transparent unsupervised learning. While high-dimensional data remains a challenge due to the $n^{2d}$ dependency in exact algorithms, the proposed approximation and kernelization techniques offer scalable ways to generate human-readable explanations for complex clusterings. Future work may focus on improving the approximation factor or developing heuristics for real-world, high-dimensional datasets.
Summary updated