决策树

是什么

决策树学习是一种监督学习方法，用分类树或回归树作为预测模型^[1]。scikit-learn 把它描述为一种非参数（non-parametric）的监督学习方法，既可用于分类，也可用于回归^[2]。模型通过从数据特征中学习简单的决策规则来预测目标变量的取值，整棵树可以看作对目标的分段常数（piecewise constant）逼近^[2]。

树的每个内部节点对某个特征提一个问题，每条分支对应一个答案，每个叶子给出一个预测。从根到叶的一条路径就是一串「如果……那么……」的规则，因此一次预测的依据可以直接从树上读出来。

树是怎么长出来的

决策树按自顶向下的贪心递归划分（top-down greedy recursive partitioning）生长：每一步都挑出能把数据分得最好的那个划分^[1]。说「贪心」，是因为每个节点只顾眼前，不回头修改上层的选择；说「递归」，是因为一次划分之后，同样的过程会在每个子集里再重复一遍。

什么算「分得最好」，各家算法不同。CART 用基尼不纯度（Gini impurity），定义为 1 减去各类概率的平方和；当一个节点纯净，也就是落到该节点的训练样本全属同一类时，这个值为 0^[1]。ID3、C4.5 和 C5.0 用的是基于熵（entropy）的信息增益（information gain）^[1]。如果目标变量是数值而不是类别，回归树可以用方差下降作为划分标准^[1]。

举个小例子就清楚了。假设要用收入和已有负债两个特征预测借款人会不会按时还款。一开始所有申请人都混在根节点里；按收入划分能分开一部分人，按负债划分也许分得更干净。算法对每个候选划分分别算不纯度，留下让不纯度下降最多的那个。然后在每个分支里重复同样的动作：高收入那一组可能再按负债分一次，而低收入那一组已经大部分属于同一类，就不再分，直接成为叶子。最后每个人落在哪个叶子，就拿到哪个叶子的答案，同一叶子里的样本预测值完全相同，这就是「分段常数」的意思。

深度直接决定模型的样子。在 scikit-learn 中，树越深，决策规则越复杂，模型对训练数据拟合得越紧^[2]。深树能刻画更细的区分，也更容易把噪声当成规律，所以要用剪枝（pruning）来避免过拟合；不过有些算法并不需要剪枝，比如条件推断树（conditional inference tree）^[1]。

从哪来

几条脉络汇到了一起。CHAID（chi-squared automatic interaction detection）由 Kass 于 1980 年提出，允许一个节点上做多于两个分支，也就是一个节点可以分出好几组，而不只是两组^[1]。CART（classification and regression trees）由 Breiman 等人于 1984 年发表^[1]。Quinlan 于 1986 年提出 ID3，后来以 C4.5 作为它的后继，再往后是 C5.0^[1]。ID3 和 CART 是在 20 世纪 70 年代末到 80 年代初各自独立发明的^[1]。

用在哪里

决策树同时用于分类和回归任务^[2]。由于拟合出来的是可读的决策规则，当人们除了要一个预测结果、还想知道判断依据时，树就很好用。深度是最主要的旋钮：浅一些的树规则简单、容易解释，深一些的树规则复杂、拟合更紧^[2]。

局限

决策树的局限包括：训练数据稍有变化，树就可能明显不同（不稳定）；容易过拟合；以及寻找最优树的问题是 NP 完全的^[1]。最后一点意味着实际算法只能用贪心的方式一步步划分，无法保证得到全局最优的树。此外，信息增益对取值水平多的特征有偏好^[1]，因为水平越多，越容易在训练数据上把类别分开。