Abstract
Unsupervised decision trees are valuable for providing interpretable clustering, yet traditional methods often rely on a sub-optimal two-step process: clustering followed by tree-based explanation. This paper introduces Kauri, an end-to-end unsupervised decision tree that directly optimizes a kernel KMeans objective. By utilizing a "kernel stock" formulation, Kauri avoids the need for explicit centroid calculations, enabling robust clustering in high-dimensional kernel spaces. Experimental results demonstrate that Kauri produces shallower, more interpretable trees with superior performance on non-linear datasets compared to state-of-the-art baselines.
Introduction
Decision trees are widely regarded as the gold standard for explainable AI due to their intuitive, hierarchical logic. While highly successful in supervised learning, their application to unsupervised clustering remains challenging. Most existing "unsupervised trees" employ a disjointed two-step approach: first, a standard algorithm like KMeans identifies clusters, and second, a decision tree is trained to predict these cluster labels.
This methodology is inherently inefficient; the tree merely approximates another algorithm's output rather than discovering the optimal data structure itself. Furthermore, standard clustering algorithms often struggle with high-dimensional "kernel" spaces where calculating centroids is computationally difficult or impossible. Kauri addresses these issues by integrating the clustering objective directly into the tree-building process.
Methods: The Kernel Stock Trick
The core innovation of Kauri (KMeans as unsupervised reward ideal) is a mathematical rephrasing of the Kernel KMeans objective. Standard KMeans relies on calculating distances to a centroid, which is problematic in abstract Hilbert spaces. Kauri utilizes the "kernel trick" to rephrase the objective to depend solely on the similarity between pairs of points within a cluster, a metric the authors term kernel stock ($\sigma$).
By leveraging kernel stock, Kauri can evaluate split quality without defining cluster centers. This allows for a greedy growth strategy where the algorithm tests feature thresholds to maximize "gains"—such as creating new clusters or reallocating data between existing ones—ensuring the tree structure is optimized for clustering quality from the root to the leaves. This approach also naturally avoids the "empty cluster" problem common in iterative Kernel KMeans.
Experimental Results
Kauri was benchmarked against state-of-the-art models like ExKMC and KMeans+DT across a variety of datasets, ranging from classic benchmarks (Iris, Wine) to high-dimensional protein data and synthetic non-linear challenges (Chainlink, Lsun).
Key Findings
- Simplicity and Interpretability: Kauri consistently produced shallower trees (lower Weighted Average Depth/WAES) than "cluster-then-explain" baselines while maintaining or improving clustering accuracy (Adjusted Rand Index).
- Non-Linear Superiority: The model significantly outperformed competitors when using non-linear kernels (e.g., RBF). On the "Lsun" dataset, Kauri achieved an ARI of 0.98, compared to 0.81 for the baseline.
- Handling Diagonal Boundaries: While axis-aligned trees typically struggle with diagonal separations, Kauri’s direct optimization allows it to find more efficient "staircase" approximations, as shown in synthetic tests with varying angles ($\theta$).
- Qualitative Success: In real-world tests on US Congressional voting records, Kauri automatically identified clusters mapping to political affiliations with 84% accuracy using only a few interpretable voting rules.
Discussion and Future Work
While Kauri offers a significant step forward for interpretable clustering, it currently relies on a greedy search that may occasionally settle in local optima. Additionally, the model is limited to axis-aligned splits. Future research will explore the use of oblique trees—splits based on linear combinations of multiple features—to further enhance performance on complex datasets. Despite these areas for growth, Kauri demonstrates that end-to-end optimization is a powerful and viable path for unsupervised decision trees.
Summary updated