Research map / Learning theory and algorithms / Clustering
Explaining Kernel Clustering via Decision Trees
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Kernel IMM and two greedy refinements (Kernel ExKMC, Kernel Expand) that build axis-aligned or interval-based decision trees approximating kernel k-means, using surrogate Taylor and distance-based features for product kernels.
Problem
Interpretable clustering with decision trees that approximates kernel k-means partitions, which are nonlinear and not axis-aligned, while keeping approximation guarantees.
Approach
Kernelize the IMM decision-tree algorithm by running it on surrogate (interpretable) feature maps for product kernels, where each feature depends on a single coordinate, so threshold cuts on features map to (interval) cuts on input coordinates; also kernelize ExKMC and Expand to refine trees using only kernel evaluations.
Key results
- Kernel IMM admits worst-case price of explainability O(dk^2) for interpretable Taylor kernels (including Gaussian), with an extra factor d compared to O(k^2) for k-means IMM.
- Kernel ExKMC and Kernel Expand refinements mostly reach a price of explainability close to 1 on Pathbased and achieve Rand index comparable to kernel k-means on the benchmark datasets.
- Theory shows the Gaussian kernel admits no interpretable feature map and no monotonic feature map, motivating surrogate features and the interval-cut definition of interpretable trees.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Kernel IMM instead of k-means or IMM | Interpretable clustering · Pathbased, Aggregation, Flame, Iris, Wisconsin breast cancer | adjusted Rand index | Helped |
| Refine Kernel IMM with Kernel ExKMC or Kernel Expand by adding leaves | Kernel IMM · Pathbased, Aggregation, Flame, Iris, Wisconsin breast cancer | adjusted Rand index | Helped |
| Use Kernel ExKMC or Kernel Expand to refine Kernel IMM | Kernel IMM · Pathbased | price of explainability | Helped |
| Use Kernel IMM with surrogate features rather than explainable k-means | Interpretable clustering · Halfmoons | clustering quality | Helped |
Surprising findings
- Explainable k-means (and IMM) can be poor for non-linearly separable data such as halfmoons, while kernel IMM recovers the clusters.
- Kernel ExKMC and Expand on an empty tree admit no worst-case bounds; the price of explainability for some kernels (quadratic, epsilon-neighborhood) can be unbounded.
Limitations
- Worst-case guarantees for distance-based product kernels depend on data-dependent constants.
- Kernel ExKMC and Expand have no worst-case bounds when run on an empty tree and adding leaves reduces interpretability.
- Open question on which data conditions allow decision trees to agree with kernel k-means partitions.
Experimental setup
Datasets: Pathbased Aggregation Flame Iris Wisconsin breast cancer
Benchmarks: Pathbased Aggregation Flame Iris Wisconsin breast cancer
Metrics: price of explainability adjusted Rand index
Baselines: k-means IMM CART kernel k-means ExKMC Expand
Builds on: IMM (iterative mistake minimization) ExKMC Expand kernel k-means
Closest papers by meaning
- Explainable k-Means and k-Medians Clustering (ICML 2020 · similarity 0.90)
- How to Find a Good Explanation for Clustering? (AAAI 2022 · similarity 0.90)
- SpEx: A Spectral Approach to Explainable Clustering (NeurIPS 2025 · similarity 0.89)
- On the price of explainability for some clustering problems (ICML 2021 · similarity 0.88)
- Dynamic Algorithm for Explainable $k$-medians Clustering under $\ell_p$ Norm (NeurIPS 2025 · similarity 0.86)
- COKE: Core Kernel for More Efficient Approximation of Kernel Weights in Multiple Kernel Clustering (ICML 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.