Interpretable clustering via optimal multiway-split decision trees

• URL: http://arxiv.org/abs/2602.13586v1
• Date: Sat, 14 Feb 2026 04:08:52 GMT
• Title: Interpretable clustering via optimal multiway-split decision trees
• Authors: Hayato Suzuki, Shunnosuke Ikeda, Yuichi Takano,
• Abstract summary: We propose an interpretable clustering method based on optimal multiway-split decision trees.<n>A key feature of our method is the integration of a one-dimensional K-means algorithm for the discretization of continuous variables.<n>Our method yields multiway-split decision trees with concise decision rules while maintaining competitive performance across various evaluation metrics.
• Score: 1.8224668251608893
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Clustering serves as a vital tool for uncovering latent data structures, and achieving both high accuracy and interpretability is essential. To this end, existing methods typically construct binary decision trees by solving mixed-integer nonlinear optimization problems, often leading to significant computational costs and suboptimal solutions. Furthermore, binary decision trees frequently result in excessively deep structures, which makes them difficult to interpret. To mitigate these issues, we propose an interpretable clustering method based on optimal multiway-split decision trees, formulated as a 0-1 integer linear optimization problem. This reformulation renders the optimization problem more tractable compared to existing models. A key feature of our method is the integration of a one-dimensional K-means algorithm for the discretization of continuous variables, allowing for flexible and data-driven branching. Extensive numerical experiments on publicly available real-world datasets demonstrate that our method outperforms baseline methods in terms of clustering accuracy and interpretability. Our method yields multiway-split decision trees with concise decision rules while maintaining competitive performance across various evaluation metrics.

Related papers

• Divide and Learn: Multi-Objective Combinatorial Optimization at Scale [41.78439888126577]
  Multi-objective optimization seeks solutions over exponentially large discrete spaces.<n>We reformulate it as an online learning problem over a decomposed decision space, solving position-wise bandit subproblems.<n>On standard benchmarks, our method achieves 80--98% of specialized solvers performance.
  arXiv  Detail & Related papers  (2026-02-11T20:29:35Z)
• Generalized Optimal Classification Trees: A Mixed-Integer Programming Approach [17.725629133949955]
  Mixed-integer programming (MIP) offers a high degree of modeling flexibility.<n>We propose a MIP-based framework for learning optimal classification trees under nonlinear performance metrics.<n>We evaluate the proposed approach on 50 benchmark datasets.
  arXiv  Detail & Related papers  (2026-02-02T14:46:01Z)
• A novel gradient-based method for decision trees optimizing arbitrary differential loss functions [2.4861619769660637]
  This work introduces a novel method for constructing gradient-based decision trees that optimize arbitrary differentiable loss functions.<n>We demonstrate the method's applicability to classification, regression, and survival analysis tasks.<n>The implementation of the method is publicly available, providing a practical tool for researchers and practitioners.
  arXiv  Detail & Related papers  (2025-03-22T20:25:30Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  This paper studies first-order algorithms for solving fully composite optimization problems convex compact sets. We leverage the structure of the objective by handling differentiable and non-differentiable separately, linearizing only the smooth parts.
  arXiv  Detail & Related papers  (2023-02-24T18:41:48Z)
• Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces [54.58348769621782]
  Tree ensembles can be well-suited for black-box optimization tasks such as algorithm tuning and neural architecture search. Two well-known challenges in using tree ensembles for black-box optimization are (i) effectively quantifying model uncertainty for exploration and (ii) optimizing over the piece-wise constant acquisition function. Our framework performs as well as state-of-the-art methods for unconstrained black-box optimization over continuous/discrete features and outperforms competing methods for problems combining mixed-variable feature spaces and known input constraints.
  arXiv  Detail & Related papers  (2022-07-02T16:59:37Z)
• Quant-BnB: A Scalable Branch-and-Bound Method for Optimal Decision Trees with Continuous Features [5.663538370244174]
  We present a new discrete optimization method based on branch-and-bound (BnB) to obtain optimal decision trees. Our proposed algorithm Quant-BnB shows significant speedups compared to existing approaches for shallow optimal trees on various real datasets.
  arXiv  Detail & Related papers  (2022-06-23T17:19:29Z)
• Mixed-Integer Optimization with Constraint Learning [4.462264781248437]
  We establish a broad methodological foundation for mixed-integer optimization with learned constraints. We exploit the mixed-integer optimization-representability of many machine learning methods. We demonstrate the method in both World Food Programme planning and chemotherapy optimization.
  arXiv  Detail & Related papers  (2021-11-04T20:19:55Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  We propose a simple and efficient unsupervised feature selection method, by combining reconstruction error with $l_2,p$-norm regularization. We present an efficient optimization algorithm to solve the proposed unsupervised model, and analyse the convergence and computational complexity of the algorithm theoretically.
  arXiv  Detail & Related papers  (2020-12-29T04:08:38Z)
• Stochastic Optimization Forests [60.523606291705214]
  We show how to train forest decision policies by growing trees that choose splits to directly optimize the downstream decision quality, rather than splitting to improve prediction accuracy as in the standard random forest algorithm. We show that our approximate splitting criteria can reduce running time hundredfold, while achieving performance close to forest algorithms that exactly re-optimize for every candidate split.
  arXiv  Detail & Related papers  (2020-08-17T16:56:06Z)
• Generalized and Scalable Optimal Sparse Decision Trees [56.35541305670828]
  We present techniques that produce optimal decision trees over a variety of objectives. We also introduce a scalable algorithm that produces provably optimal results in the presence of continuous variables.
  arXiv  Detail & Related papers  (2020-06-15T19:00:11Z)
• Learning with Differentiable Perturbed Optimizers [54.351317101356614]
  We propose a systematic method to transform operations into operations that are differentiable and never locally constant. Our approach relies on perturbeds, and can be used readily together with existing solvers. We show how this framework can be connected to a family of losses developed in structured prediction, and give theoretical guarantees for their use in learning tasks.
  arXiv  Detail & Related papers  (2020-02-20T11:11:32Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.