决策树的基本思想是“分而治之”，通过对样本的属性进行划分来实现分类的一种机器学习算法。

我们人类进行分类的依据一般是该样本所具备的属性值。例如在判别一个样本是否为猫时，可依据样本的耳朵形状（尖头、圆头）、脸型（圆、不圆）、胡须（有、没有）等特征。我们可以先看耳朵形状，如果是尖头，我们再看脸型，如果是圆形，则我们再看是否有胡须，如果有胡须，则得出最后结论：这是一只猫。

决策树算法的思想与之类似，不同的属性值会导向不同的结果。一颗决策树通常具有一个根节点，若干内部节点和叶子节点。根节点和内部节点执行上述属性测试，叶子节点代表样本的分类结果。样本从根节点开始，依据属性值唯一地确定一条测试序列，最终达到叶子节点，得到分类结果。决策树应用于上述对猫的二分类问题的示意图为：

决策树的训练

决策树的训练目的是为了产生泛化能力强的决策树，训练过程就是不断依据属性值对样本进行划分，直到达到停止条件，此时每个叶子节点均对应一个划分后的样本集合，将该样本集合中占比最大的类作为预测结果。训练伪代码如下：

停止条件

决策树的停止条件可分为两类，一类是由于样本无法划分导致的停止，另一类是人为设定的停止条件。

1. 对于前者，在训练过程中有三种情况样本无需或不能划分，决策树可停止：

   • 所有样本均属于同一类，无需划分，预测结果即为该类。

   • 所有样本的属性值均相同，无需划分，将其中占比最大的类别作为预测结果。

   • 训练集样本中没有待考虑属性的值，由于样本中不具备该属性，无法依据属性值对样本进行划分，因此将该属性的划分结果设置为和已有划分一致。例如在对猫进行二分类时，体重是属性之一，但当前手头并没有训练集中每个样本的体重，因此体重对是否为猫的影响无法考虑，对体重属性的测试结果保持和父节点一致。

2. 人为设定的停止条件包括：

   • 决策树的最大深度，即叶子节点距根节点的最大距离。

   • 依据属性来划分样本所带来的纯度增益小于阈值。

   • 集合中样本量低于阈值，没必要对该集合进一步划分。

属性选择

所选择的属性数目和属性种类会影响决策树的泛化能力。从属性数目来说，考虑的属性数目越多，决策树的分类效果越精确，但面向新样本的分类泛化性可能较弱；从属性种类来看，选择的属性与类别关联性越强，对于提升决策树的泛化性越有利。决策树训练的重点在于如何选择对分类更有利的属性，目的是保证划分后的结果具有更高的纯度，即决策树分支节点所包含的样本尽可能属于同一类，不同属性值对应的样本类别尽可能无重叠。

信息增益

为了衡量划分后样本的纯度，ID3决策树引入信息熵和信息增益的概念。

信息熵是度量样本集合纯度的指标，假定样本集合$D$中含有$\left|\mathcal Y\right|$类样本，第$k$类样本所占比例为$p_k$，则$D$的信息熵定义如下，其值越小纯度越高。

$$\mathrm{Ent}(D)=-\sum_{k=1}^{|\mathcal Y|}p_k\log_2p_k$$

假定属性$a$有$V$个可能的取值$\{a^1,a^2,\cdots,a^V\}$，依据该属性将样本集合$D$划分为$V$个集合$D^1,D^2,\cdots,D^V$，每个集合$D^v$。划分前后的信息熵之差即信息增益：

$$\mathrm{Gain}(D,a)=\mathrm{Ent}(D)-\sum_{v=1}^V\frac{|D^v|}{|D|}\mathrm{Ent}(D^v)$$

划分后的信息熵采用各集合样本量加权平均的方式来计算。

信息增益$\mathrm{Gain}(D,a)$越大，则说明使用属性$a$划分后样本的“纯度”越高。因此样本的属性选择表达为：

$$a_*=\arg\max_{a\in A}\mathrm{Gain}(D,a)$$

在应用于二分类任务时，样本集合$D$中两类样本的概率可表示为$p_1$和$p_2=1-p_1$，因此信息熵为：

$$\mathrm{Ent}(D)=\mathrm{H}(p_1)=-p_1\log_2p_1-(1-p_1)\log_2(1-p_1)$$

函数图像如下：

可以看出，信息熵在两类别最混杂（$p_1=p_2=0.5$)的时候达到最大值，而在样本最纯净（$p_1=1$或$p_1=0$）时数值最小，因此可以描述集合的纯度。

增益率

信息增益对于可取值数目较多的属性有所偏好，例如样本编号，显然这种影响不利于提高决策树的泛化性能。C4.5决策树不直接使用信息增益，而使用增益率来选择最优属性。其表达式为：

$$\mathrm{Gain\_ratio}(D,a)=\frac{\mathrm{Gain(D,a)}}{\mathrm{IV}(a)}$$

其中：

$$\mathrm{IV}(a)=-\sum_{v=1}^V\frac{|D^v|}{|D|}\log_2\frac{|D^v|}{|D|}$$

成为属性$a$的固有值。而增益率对于可选数目较少的属性有所偏好，因此C4.5并不直接选用增益率最大的候选划分属性，而是先选择信息增益高于平均水平的属性，再从中选择增益率最高的。

基尼指数

CART决策树采用基尼指数来划分属性，数据集$D$的纯度可用基尼值表示为：

$$\mathrm{Gini}(D)=\sum_{k=1}^{|\mathcal Y|}\sum_{k'\ne k}p_kp_{k'}\\ =1-\sum_{k=1}^{|\mathcal Y|}p_k^2$$

属性$a$的基尼指数定义为：

$$\mathrm{Gini\_index}(D,a)=\sum_{v=1}^V\frac{|D^v|}{|D|}\mathrm{Gini}(D^v)$$

决策树的推广

原始决策树主要用于分类任务，且属性为离散值，后续研究将其推广至了连续值属性和回归任务的决策树。

连续值属性

在决策树中，根节点和内部节点依据属性的可能取值来将样本划分有限个集合，连续值属性可预先进行离散化。例如，某批样本存在取值为如下连续值的属性：

$$\begin{bmatrix} 7.2&8.8&15&9.2&8.4&7.6&11&10.2&18&20 \end{bmatrix}$$

可将该属性以$10$为界划分，由此作为决策树节点将样本划分为两部分，界限的选择也遵循信息增益最大的原则。假如划分前样本集合的两类样本占比$p_1=p_2=0.5$，以$8$为阈值进行划分时，其信息增益为：

$$\mathrm{H}(0.5)-\left(\frac2{10}\mathrm{H}\left(\frac22\right)+\frac8{10}\mathrm{H}\left(\frac38\right)\right)=0.24$$

回归决策树

回归任务中，由于样本预测结果为连续值，因此无法使用信息增益、增益率等依据各类样本在数据集合中的占比来衡量纯度的方法。因此ID3和C4.5决策树仅能用于分类任务，而CERT决策树可用于分类和回归任务。

CERT决策树与其余两类决策树的另一个不同之处在于，CERT决策树算法最终生成的为二叉树，而非多叉树。CERT对于连续值属性的处理与上文一致，通过选择最优切分点将样本划分为两部分，而对于离散值特征的处理则是采用one-hot形式。例如，对于取值为青年、中年、老年的年龄属性，ID3和C4.5决策树会将样本集合依据该属性划分为$3$部分，然后从可划分属性集中剔除年龄属性；而CERT则是将其拆分为是否为青年（是、否）、是否为中年、是否为老年这三个属性，即选择年龄属性的一个值（例如青年）作为节点，将样本划分为等于/不等于该值两部分，如下所示：

$$~[青年\ \cdots]\rightarrow [1\ 0\ 0\ \cdots]\\ ~[中年\ \cdots]\rightarrow [0\ 1\ 0\ \cdots]\\ ~[老年\ \cdots]\rightarrow [0\ 0\ 1\ \cdots]$$

划分样本后仅将该属性值从属性集合中剔除，而不将其余属性值剔除。