Kernel KMeans clustering splits for end-to-end unsupervised decision trees

Louis Ohl, Pierre-Alexandre Mattei, Mickaël Leclercq, Arnaud Droit, Frédéric PreciosoarXiv 2024 · DOI · arXiv

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$).

Figure 1: Visualization of the kernel stock calculation across different split types and data partitions.

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).

Figure 4: Quantitative performance comparison (ARI and WAES) and synthetic analysis of diagonal boundary handling.

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

Abstract

Trees are convenient models for obtaining explainable predictions on relatively small datasets. Although there are many proposals for the end-to-end construction of such trees in supervised learning, learning a tree end-to-end for clustering without labels remains an open challenge. As most works focus on interpreting with trees the result of another clustering algorithm, we present here a novel end-to-end trained unsupervised binary tree for clustering: Kauri. This method performs a greedy maximisation of the kernel KMeans objective without requiring the definition of centroids. We compare this model on multiple datasets with recent unsupervised trees and show that Kauri performs identically when using a linear kernel. For other kernels, Kauri often outperforms the concatenation of kernel KMeans and a CART decision tree.
BibTeX
@misc{ohl2024kernel,
  author = {Louis Ohl and Pierre-Alexandre Mattei and Mickaël Leclercq and Arnaud Droit and Frédéric Precioso},
  title = {{Kernel KMeans clustering splits for end-to-end unsupervised decision trees}},
  year = {2024},
  eprint = {2402.12232},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2402.12232},
}
Figure