Several recent publications report advances in training optimal decision
trees (ODT) using mixed-integer programs (MIP), due to algorithmic advances in
integer programming and a growing interest in addressing the inherent
suboptimality of heuristic approaches such as CART. In this paper, we propose a
novel MIP formulation, based on a 1-norm support vector machine model, to train
a multivariate ODT for classification problems. We provide cutting plane
techniques that tighten the linear relaxation of the MIP formulation, in order
to improve run times to reach optimality. Using 36 data-sets from the
University of California Irvine Machine Learning Repository, we demonstrate
that our formulation outperforms its counterparts in the literature by an
average of about 10% in terms of mean out-of-sample testing accuracy across the
data-sets. We provide a scalable framework to train multivariate ODT on large
data-sets by introducing a novel linear programming (LP) based data selection
method to choose a subset of the data for training. Our method is able to
routinely handle large data-sets with more than 7,000 sample points and
outperform heuristics methods and other MIP based techniques. We present
results on data-sets containing up to 245,000 samples. Existing MIP-based
methods do not scale well on training data-sets beyond 5,500 samples.

本文提出了一种新的基于支持向量机和 1 - 范数分多元决策树（ODT）训练的混合整数规划（MIP）公式，利用线性规划（LP）数据选择方法选择数据样本，实现了对大数据集的有效训练，并在包含 245,000 个样本的数据集上验证了该方法优于现有的启发式方法和其他基于 MIP 的技术的效果。

一种可扩展的基于 MIP 的学习最优多变量决策树方法

A Scalable MIP-based Method for Learning Optimal Multivariate Decision  Trees

We consider the problem of constructing optimal decision trees: given a
collection of tests which can disambiguate between a set of $m$ possible
diseases, each test having a cost, and the a-priori likelihood of the patient
having any particular disease, what is a good adaptive strategy to perform
these tests to minimize the expected cost to identify the disease? We settle
the approximability of this problem by giving a tight $O(\log m)$-approximation
algorithm. We also consider a more substantial generalization, the Adaptive TSP
problem. Given an underlying metric space, a random subset $S$ of cities is
drawn from a known distribution, but $S$ is initially unknown to us--we get
information about whether any city is in $S$ only when we visit the city in
question. What is a good adaptive way of visiting all the cities in the random
subset $S$ while minimizing the expected distance traveled? For this problem,
we give the first poly-logarithmic approximation, and show that this algorithm
is best possible unless we can improve the approximation guarantees for the
well-known group Steiner tree problem.

本文研究最优决策树，自适应 TSP 问题以及如何在度量空间中访问子集，并给出了多项式对数逼近算法。