决策树（一）——原理篇

一、模型

分类决策树模型是一种基于特征对实例进行分类的树形结构。决策树由结点和有向边组成。结点有内部结点和叶结点两种类型，内部结点表示一个特征或属性，叶结点表示一个类。
可以将决策树看成一个if-then规则的集合。由决策树的根节点到叶结点的每一条路径构建一条规则；路径上内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。
也可以将决策树看作是定义在特征空间划分上的类的条件概率分布。将特征空间划分为互不相交的单元，决策树的一条路径对应于划分中的一个单元，决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。

二、策略

损失函数最小化/正则化的极大似然估计

三、算法

决策树学习的本质是从训练数据集中归纳出一组分类规则，旨在构建一个与训练数据拟合很好，并且复杂度小的决策树。
决策树学习步骤包括特征选择、决策树的生成和决策树的修建，常用算法有ID3、C4.5与CART。

ID3算法用信息增益来选择特征，相当于用极大似然法进行概率模型的选择，该算法只有树的生成，所以生成的树容易产生过拟合。
C4.5算法与ID3算法相似，进行了部分改进，在生成过程中用信息增益比来选择特征。
ID3算法（算法5.2）与C4.5算法（算法5.3）需通过剪枝算法（算法5.4）对已生成的决策树进行简化，解决过拟合问题。

CART(classification and regression tree,分类与回归树）是应用广泛的决策树学习方法，即可用于分类也可用于回归。CART假设决策树是二叉树，内部结点特征的取值为“是”和“否”，等价于递归地二分每个特征，将特征空间划分为有限个单元，并在这些单元上确定预测的概率分布。
CART算法由以下两步组成：
（1）决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大；
（2）决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。
通过CART算法生成决策树就是递归地构建二叉决策树的过程。对回归树用平方误差最小化准则（算法5.5），对分类树用基尼指数最小化准则（算法5.6），进行特征选择，生成二叉树。
CART剪枝算法（算法5.7）由两步组成：
（1）从生成算法产生的决策树$T_0$T0​底端开始不断剪枝，直到$T_0$T0​的根结点，形成一个子树序列；
（2）通过交叉验证法在独立的验证数据集上对子树序列进行测试，从中选择最优子树。

---

（一）特征选择

选取对训练数据具有分类能力的特征，使用信息增益最大、信息增益比最大或基尼指数最小作为特征选择的准则。
信息增益
熵：表示随机变量不确定性的度量。熵越大，随机变量的不确定性就越大。
设X是一个离散随机变量，其概率分布为$P(X=x_i)=p_i,i=1,2,...,n；$P(X=xi​)=pi​,i=1,2,...,n；则随机变量X的熵定义为$H(X)=-\sum\limits_{i=1}^np_ilogp_i$H(X)=−i=1∑n​pi​logpi​,其中的对数以2为底或以e为底。由定义可知，熵只依赖于X的概率分布，而与X的取值无关，所以也可将X的熵记作$H(p)$H(p),即$H(p)=-\sum\limits_{i=1}^np_ilogp_i$H(p)=−i=1∑n​pi​logpi​
条件熵：表示在已知随机变量X的条件下随机变量Y的不确定性。$H(Y|X)=\sum\limits_{i=1}^np_iH(Y|X=x_i)$H(Y∣X)=i=1∑n​pi​H(Y∣X=xi​)
信息增益：表示得知特征X的消息而使得类Y的信息的不确定性减少的程度。特征A对训练数据集D的信息增益定义为$g(D,A)=H(D)-H(D|A)\\ H(D)=-\sum\limits_{k=1}^K\frac{|C_k|}{|D|}log_2\frac{|C_k|}{|D|}\\ H(D|A)=\sum\limits_{i=1}^n\frac{|D_i|}{D}H(D_i)=-\sum\limits_{i=1}^n\frac{|D_i|}{|D|}\sum\limits_{k=1}^K\frac{|D_{ik}|}{|D_i|}log_2\frac{|D_{ik}|}{|D_i|}$g(D,A)=H(D)−H(D∣A)H(D)=−k=1∑K​∣D∣∣Ck​∣​log2​∣D∣∣Ck​∣​H(D∣A)=i=1∑n​D∣Di​∣​H(Di​)=−i=1∑n​∣D∣∣Di​∣​k=1∑K​∣Di​∣∣Dik​∣​log2​∣Di​∣∣Dik​∣​
其中，H(D)是数据集D的熵，H(D_i)是数据集$D_i$Di​的熵，H(D|A)是数据集D对特征A的条件熵。n是特征A取值的个数，K是类的个数。$D_i$Di​是D中特征A取第i个值的样本子集，$C_k$Ck​是D中属于第k类的样本子集。
决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

信息增益比
以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题，使用信息增益比可以校正这一问题。
特征A对训练数据集D的信息增益比定义为
$g_R(D,A)=\frac{g(D,A)}{H_A(D)}\\ H_A(D)=-\sum\limits_{i=1}^n\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|}$gR​(D,A)=HA​(D)g(D,A)​HA​(D)=−i=1∑n​∣D∣∣Di​∣​log2​∣D∣∣Di​∣​
其中，n是特征A取值的个数。
注意，$H(D|A$H(D∣A)是数据集D对特征A的条件熵，$H_A(D)$HA​(D)是数据集D关于特征A的值的熵。二者概念不同，前者为条件熵，后者为熵。

基尼指数
概率分布的基尼指数定义为
$Gini(p)=\sum\limits_{k=1}^Kp_k(1-p_k)=1-\sum\limits_{k=1}^Kp_k^2$Gini(p)=k=1∑K​pk​(1−pk​)=1−k=1∑K​pk2​
数据集D的基尼指数：表示集合D的不确定性。
$Gini(p)=1-\sum\limits_{k=1}^K(\frac{|C_k|}{|D|})^2$Gini(p)=1−k=1∑K​(∣D∣∣Ck​∣​)2
特征A条件下数据集D的基尼指数：表示经A=a分割后集合D的不确定性。
$Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)$Gini(D,A)=∣D∣∣D1​∣​Gini(D1​)+∣D∣∣D2​∣​Gini(D2​)
基尼指数值越大，样本集合的不确定性也就越大。

---

（二）决策树的生成

通过计算信息增益或其他指标，从根节点开始递归地产生决策树。

---

（三）决策树的剪枝

生成的决策树可能存在过拟合问题，通过自下而上进行剪枝简化学到的决策树，使其具有更好的泛化能力。
决策树学习的损失函数定义为$C_\alpha(T)=C(T)+\alpha|T|\tag{*}$Cα​(T)=C(T)+α∣T∣(*)
$C(T)=\sum\limits_{t=1}^{|T|}N_tH_t(T)=-\sum\limits_{t=1}^{|T|}\sum\limits_{k=1}^KN_{tk}log\frac{N_{tk}}{N_t}$C(T)=t=1∑∣T∣​Nt​Ht​(T)=−t=1∑∣T∣​k=1∑K​Ntk​logNt​Ntk​​
其中，|T|为树T的叶结点个数，t是树T的叶结点，该叶结点有$N_t$Nt​个样本点，其中k类的样本点有$N_{tk}$Ntk​个，H(T)为叶结点t上的经验熵，$\alpha\geq0$α≥0为参数。
式$(*)$(∗)中，C(T)表示模型对训练数据的预测误差，即模型与训练数据的拟合程度；|T|表示模型复杂度。参数$\alpha$α用来权衡二者之间的影响。
当$\alpha$α较大时，模型较简单；当$\alpha$α较小时，模型较复杂；当$\alpha=0$α=0时，只考虑模型与训练数据的拟合程度，不考虑模型的复杂度。
决策树生成学习局部的模型，而决策树剪枝学习整体的模型。
式$(*)$(∗)定义的损失函数的极小化等价于正则化的极大似然估计，利用损失函数最小原则进行剪枝就是用正则化的极大似然估计进行模型选择。

参考文献
[1] 李航. 统计学习方法（第2版）. 北京：清华大学出版社，2017.