决策树（decision tree）是一种基本的分类与回归方法。主要优点是模型具有可读性，分类速度快。决策树的学习通常包括三个步骤：特征选择、决策树的生成和决策树的剪枝。

1. 决策树的模型与学习

1.1 决策树模型

定义：决策树 分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点（node）和有向边（directed edge）组成。结点有两种类型：内部结点（internal node）和叶结点（leaf node）。内部结点表示一个特征或属性，叶结点表示一个类。

1.2 决策树与if-then规则

由决策树的根结点到叶结点的每一条路径构建一条规则：路径内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。
决策树的路径或其对应的if-then规则集合具有一个重要的性质：互斥并且完备。也就是说，每一个实例都被一条路径或一条规则所覆盖，而且只被一条路径或一条规则所覆盖。

1.3 决策树与条件概率分布

决策树还表示给定特征条件下类的条件概率分布，这一条件概率分布定义在特征空间的一个划分（partition）上，将特征空间划分为互不相交的单元（cell）或区域（region），并在每个单元定义一个类的概率分布就构成了一个条件概率分布。
决策树的一条路径对应于划分中的一个单元。决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。各叶结点（单元）上的条件概率往往偏向某一个类，即属于某一个类的概率较大。

1.4 决策树的学习

假设给定训练数据集 D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯   , ( x N , y N ) } D = \{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\} D={(x1​,y1​),(x2​,y2​),⋯,(xN​,yN​)}，其中,$x_i=(x_i^1,x_i^2,\cdots ,x_i^n{)}^T$为输入实例(特征向量),$n$为特征个数， y i ∈ { 1 , 2 , ⋯   , K } y_i \in \{1,2,\cdots,K\} yi​∈{1,2,⋯,K}为类标记,$i=1,2,\cdots ,N$，$N$为样本容量。
决策树学习的目标是根据给定的训练数据构建一个决策树模型，是它能够实例进行正确的分类。

决策树学习本质上是从训练数据中归纳出一组分类规则。能对训练数据进行正确分类的决策树可能有多个，也可能一个都没有。我们需要一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。

决策树学习用损失函数表示这一目标。决策树学习的损失函数通常是正则化的极大似然函数。决策树学习的策略是以损失函数为目标函数的最小化。

当损失函数确定以后，学习问题就变为在损失函数意义下选择最优决策树的问题。

决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程。该过程对应着特征空间的划分，也对应着决策树的构建。

• 开始，构建根节点，将所有训练数据都放在根节点。选择一个最优特征，按照该特征将训练数据分隔成子集，使得各个子集有一个在当前条件下最好的分类。
• 若这些子集已经能被基本正确分类，那么构建叶节点，将这些子集分到所对应的叶节点中去；
• 如果还有子集不能被基本正确分类，那么针对这些子集选择新的最优特征，继续对其进行分割，构建相应的节点。
• 如果递归地进行下去，直到所有训练数据子集都被基本正确分类，或没有适合的特征为止。这样就生成了一颗决策树。

以上方法生成的决策树可能对训练数据有很好的分类能力，但对未知的测试数据却未必有很好的分类能力，即可能发生过拟合现象。我们需要对已生成的树自下而上进行剪枝，将树变得更简单，从而使它具有更好的泛化能力。

如果特征数量很多，也可以在决策树学习开始的时候，对特征进行选择，只留下对训练数据有足够分类能力的特征。

可以看出，决策树学习算法包含特征选择、决策树的生成与决策树的剪枝过程。决策树学习常用的算法有ID3、C4.5与CART。

2. 特征选择

2.1 特征选择问题

特征选择在于选取对训练数据具有分类能力的特征。这样可以提高决策树学习的效率。如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的。通常特征选择的准则是信息增益或信息增益比。

2.2 信息增益

在信息论和概率统计中，熵（entropy）是表示随机变量不确定性的度量。设X是一个取有限个值得离散随机变量，其概率分布为：
$$P(X=x_i)=p_i,i=1,2,...,n$$
则随机变量X的熵定义为：
$$H(X)=-\sum _{i=1}^n{p}_i\log p_i$$
若$p_i=0$，则定义$0\log 0=0$。通常对数以2为底或以e为底（自然对数），这时熵的单位分别称作比特（bit）或者纳特（nat）。
由定义可知，熵只依赖于X的分布，而与X的取值无关，所以也可将X的熵记作$H(p)$，即
$$H(p)=-\sum _{i=1}^n{p}_i\log p_i$$
熵越大，随机变量的不确定性也就越大。从定义可验证：
$$0\le H(p)\le \log n$$
当随机变量只取两个值，例如1,0时，即的分布为：
$$P(X=1)=p,P(X=0)=1-p,0\le p\le 1$$
熵为：
$$H(p)=-p{\log }_{2}p-(1-p){\log }_2(1-p)$$
这时，熵$H(p)$随概率$p$的曲线如图所示

当$p=0$或$p=1$时$H(p)=0$，随机变量完全没有不确定性。当$p=0.5$时，$H(p)=1$ ，熵取最大值，随机变量不确定性最大。

条件熵(conditional entropy)$H(Y|X)$表示在已知随机变量$X$的条件下随机变量$Y$的不确定性。$H(Y|X)$定义为$X$给定条件下$Y$的条件概率分布的熵对$X$的数学期望
$$H(Y|X)=\sum _{i=1}^n{p}_{i}H(Y|X=x_i)$$
这里$p_i=P(X=x_i)，i=1,2,...,n$。

当熵和条件熵中的概率由极大似然估计得到时，所对应的熵与条件熵分别称为经验熵(empirical entropy)和经验条件熵(empirical conditional entropy)。此时，如果由0概率，则令$0\log 0=0$。

信息增益（information gain）表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。
定义（信息增益）：特征$A$对训练数据集$D$的信息增益$g(D,A)$定义为集合$D$的经验熵$H(D)$与特征$A$给定条件下$D$的经验条件熵$H(D|A)$之差，即
$$g(D,A)=H(D)-H(D|A)\text{\hspace{1em}(5.6)}$$

一般地，熵$H(Y)$与条件熵$H(Y|X)$之差称为互信息(mutual information)。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。
决策树学习应用信息增益准则选择特征：给定训练集$D$和特征$A$，经验熵$H(D)$表示对数据集$D$进行分类的不确定性。而经验条件熵$H(D|A)$表示在特征$A$给定的条件下对数据集$D$进行分类的不确定性。 那么它们的差，即信息增益，就表示由于特征$A$而使得对数据集$D$的分类的不确定性减少的程度。显然，信息增益依赖于特征，不同的特征往往具有不同的信息增益。信息增益大的特征具有更强的分类能力。

那么就得到根据信息增益准则的特征选择方法：对训练数据集(或子集)$D$，计算每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征。

算法（信息增益的算法）：
输入：训练数据集D和特征A;
输出：特征A对训练数据集D的信息增益$g(D,A)$。

2.3 信息增益比

以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。使用信息增益比（information gain ratio）可以对这一问题进行校正。
定义（信息增益比）：特征A对训练数据集D的信息增益比$g_R(D,A)$定义为其信息增益$g(D,A)$与训练数据集D关于特征A的值的熵$H_A(D)$之比，即：
$$g_R(D,A)=\frac{g(D,A)}{H_A(D)}$$
其中，$H_A(D)=-{\sum }_{i=1}^n\frac{|D_i|}{D}{\log }_2\frac{|D_i|}{D}$，n是特征A取值的个数。

3. 决策树的生成

3.1 ID3算法

ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。具体方法是：从根节点（root node）开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点；再对子结点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止，最后得到一个决策树。ID3相当于用极大似然法进行概率模型的选择。
算法（ID3算法）:
输入：训练数据集D，特征集A，阈值$\epsilon \epsilon$；
输出：决策树T
（1）若D中所有实例属于同一类$C_k$，则T为单节点树，并将类$C_k$作为该节点的类标记，返回T；
（2）若A为空集，则T为单节点树，并将D中实例数最大的类$C_k$作为该节点的类标记，返回T；
（3）否则，按上面介绍的算法计算A中各特征对D的信息增益，选择信息增益最大的特征$A_g$；
（4）如果$A_g$的信息增益小于阈值$\epsilon \epsilon$(设置阈值防止分的过细)，则置T为单节点树，并将D中实例数最大的类$C_k$作为该节点的类标记，返回T；
（5）否则，对$A_g$的每一可能值$a_i$，依$A_g=a_i$将D分割为若干非空子集$D_i$，将$D_i$中实例数最大的类作为标记，构建子节点，由节点及其子节点构成树T，返回T；
（6）对第i个子节点，以$D_i$为训练集，以 A − { A g } A - \{A_g\} A−{Ag​}为特征集，递归地调用步1~5，得到子树$T_i$，返回$T_i$​。

3.2 C4.5的生成算法

C4.5算法与ID3算法相比，在生成的过程中，用信息增益比来选择特征。
算法（C4.5的生成算法）

在这两个算法中通过设定阈值来控制生成的树的深度或宽度，这种做法称为预剪枝。还有一种做法是生成决策树以后，再进行剪枝，叫做后剪枝。

4. 决策树的剪枝

决策树生成算法递归地产生决策树，直到不能继续下去为止。这样产生的树往往对训练数据的分类很准确，但对未知的测试数据的分类却没有那么准确，即出现过拟合现象。 解决这个问题的办法是考虑降低决策树的复杂度，对已生成的决策树进行简化。

在决策树学习中将已生成的树进行简化的过程称为剪枝(pruning)。剪枝从已生成的树上裁掉一些子树或叶节点，并将其根节点或父节点作为新的叶节点，从而简化分类树模型。

决策树的剪枝往往通过极小化决策树整体的损失函数（loss function）来实现。
设树T的叶结点个数为|T|，t是树T的叶结点，该叶结点有$N_t$个样本点，其中k类的样本点有$N_{tk}$个，$k=1,2,...,K$，$H_t(T)$为叶结点t上的经验熵，$\alpha \ge 0$为参数，则决策树学习的损失函数可以定义为：
$$C_{\alpha }(T)=\sum _{t=1}^{|T|}{N}_t{H}_t(T)+\alpha |T|$$
其中经验熵为：
$$H_t(T)=-\sum _k\frac{N_{tk}}{N_t}\log \frac{N_{tk}}{N_t}$$
其中，$C(T)$表示模型对训练数据的预测误差，即模型与训练数据的拟合程度，当叶子节点的熵越小，也就是损失越小，代表混乱程度越低，分类的时候越好分；

$\mid T\mid$表示模型复杂度。当叶子节点数越大，说明决策树越复杂，泛化能力越差。较大的$\alpha$促使选择较简单的树。当$\alpha =0$意味着只考虑模型与训练数据的拟合程度，不考虑复杂度。

剪枝，就是当$\alpha$确定时，选择损失函数最小的模型。决策树生成算法学习局部的模型，而决策树剪枝学习整体的模型。

算法（树的剪枝算法）：
输入：生成算法陈胜的整个树T，参数$\alpha$
输出：修建后的子树$T_{\alpha }$
（1）计算每个结点的经验熵
（2）递归地从树的叶结点向上回缩。
（3）如果一组叶节点回缩到父节点之前和之后的整体树分别为$T_B$与$T_A$，对应的损失函数分别是$C_{\alpha }(T_B)$与$C_{\alpha }(T_A)$，若$C_{\alpha }(T_A)\le C_{\alpha }(T_B)$，则进行剪枝，将父节点变成新的叶节点;
（4）返回步骤2，直到不能继续为止，得到损失函数最小的子树$T_{\alpha }$
简单来说，就是如果减去某个分支，使该分支变成叶子节点，得到的新树对应的损失函数更小，那么就可以剪枝，否则不能剪枝。

5. CART算法

分类与回归树（classification and regression tree, CART）模型是应用广泛的决策树学习方法。既可以用于分类也可以用于回归。

它生成的决策树是一棵二叉树。上面介绍的ID3算法和C4.5算法中，如果其中一个特征有多个(大于两个)类别，那么就要分多个分支。但是CART算法不管有多少个类别，只分成两部分。

CART算法由以下两步组成：
（1）决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大；
（2）决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。

5.1 CART生成

决策树的生成就是递归地构建二叉决策树的过程。对回归树用平方误差最小化准则，对分类树用基尼指数（Gini index）最小化准则，进行特征选择，生成二叉树。

1. 回归树的生成

假设X和Y分别为输入和输出变量，并且Y是连续变量，给定数据集 D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , , . . . , ( x N , y N ) } D=\{(x_1,y_1),(x_2,y_2),,...,(x_N,y_N)\} D={(x1​,y1​),(x2​,y2​),,...,(xN​,yN​)}，考虑如何生成回归树。

一棵回归树对应着输入空间（即特征空间）的一个划分以及在划分的单元上的输出值。假设已将输入空间划为M个单元$R_1,R_2,...,R_M$，并且在每个单元$R_m$上有一个固定的输出值$c_m$，于是回归树模型可表示为
$$f(x)=\sum _{m=1}^M{c}_{m}I(x\in R_m)$$
当输入空间的划分确定时，可以用平方误差${\sum }_{x_i\in R_m}(y_i-f(x_i){)}^2$来表示回归树对训练数据的预测误差，用平方误差最小的准则求解每个单元上的最优输出值。

易知，单元$R_m$上的$c_m$的最优值${\hat{c}}_m$是$R_m$上的所有输入实例$x_i$对应的输出$y_i$的均值，即
$${\hat{c}}_m=ave(y_i|x_i\in R_m)$$
问题是怎样对输入空间进行划分。这里采用启发式的方法，选择第j个变量$x^{(j)}$和它取的值$s$作为切分变量（spliting variable）和切分点（spliting potting），并定义两个区域：
R 1 ( j , s ) = { x ∣ x ( j ) ≤ s } 和 R 2 ( j , s ) = { x ∣ x ( j ) > s } R_1(j, s)=\{x| x^{(j)}\le s\}和R_2(j, s)=\{x|x^{(j)}>s\} R1​(j,s)={x∣x(j)≤s}和R2​(j,s)={x∣x(j)>s}
然后寻找最优切分变量j和最优切分点s。具体地，求解
$$\underset{j,s}{\min }[\underset{c_1}{\min }\sum _{x_i\in R_1(j,s)}(y_i-c_1{)}^2+\underset{c_2}{\min }\sum _{x_i\in R_2(j,s)}(y_i-c_2{)}^2]$$
对固定输入变量j可以找到最优切分点s。
$${\hat{c}}_1=ave(y_i|x_i\in R_1(j,s))和{\hat{c}}_2=ave(y_i|x_i\in R_2(j,s))$$
遍历所有输入变量，找到最优的切分变量j，构成一个对(j, s)。依此将输入空间划分为两个趋于。接着，对每个区域重复上述划分过程。直到满足停止条件为止，这样就生成了一棵回归树。这样的回归树通常称为最小二乘回归树（least squares regression tree）。
算法（最小二乘回归树生成算法）：
输入：训练数据集D
输出：回归树$f(x)$
在训练数据集所在的输入空间中，递归地将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树；
（1）选择最优切分变量j 和切分点s, 求解：
$$\underset{j,s}{\min }[\underset{c_1}{\min }\sum _{x_i\in R_1(j,s)}(y_i-c_1{)}^2+\underset{c_2}{\min }\sum _{x_i\in R_2(j,s)}(y_i-c_2{)}^2]$$
遍历变量j, 对固定的切分变量j 扫描切分点s, 选择使上式达到最小值的对(j, s)。
（2）用选定的对(j, s)划分区域并决定响应的输出值：
R 1 ( j , s ) = { x ∣ x ( j ) ≤ s } 和 R 2 ( j , s ) = { x ∣ x ( j ) > s } R_1(j, s)=\{x| x^{(j)}\le s\}和R_2(j, s)=\{x|x^{(j)}>s\} R1​(j,s)={x∣x(j)≤s}和R2​(j,s)={x∣x(j)>s}
$${\hat{c}}_m=\frac{1}{N_m}\sum _{x_i\in R_m(j,s)}{y}_i,x\in R_m,m=1,2$$
（3）继续对两个子区域调用步骤（1）（2）。直到满足停止条件。
（4）将输入空间划分为M个区域$R_1,R_2,...,R_M$，生成决策树：
$$f(x)=\sum _{m=1}^M{\hat{c}}_{m}I(x\in R_m)$$

2. 分类树的生成
   分类树用基尼指数选择最优特征，同时决定该特征的最优二值切分点。
   定义（基尼指数）分类问题中。假设有$K$个类，样本点属于第$k$个类的概率为$p_k$，则概率分布的基尼指数定义为$$Gini(p)=\sum _{k=1}^K{p}_k(1-p_k)=1-\sum _{k=1}^K{p}_k^2\text{\hspace{1em}(5.12)}$$
   这里用到了${\sum }_{k=1}^K{p}_k=1$
   对于二类分类问题，若样本点属于第1个类的概率为p，则概率分布的基尼指数为
   $$Gini(p)=2p(1-p)$$
   对于给定的样本集合D，其基尼指数为
   $$Gini(D)=1-\sum _{k=1}^K(\frac{C_k}{D}{)}^2$$
   这里，$C_k$是D中属于第k类的样本子集，K是类的个数。

如果样本集合D根据特征A是否取某一可能值a被分割成$D_1$和$D_2$两部分，即
D 1 = { ( x , y ) ∈ D ∣ A ( x ) = a } , D 2 = D − D 1 D_1 = \{(x,y) \in D|A(x) = a\} ,D_2 = D - D_1 D1​={(x,y)∈D∣A(x)=a},D2​=D−D1​
则在特征A的条件下，集合D的基尼指数定义为
$$Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)\text{\hspace{1em}(5.15)}$$
基尼指数$Gini(D)$表示集合$D$的不确定性，基尼指数$Gini(D,A)$表示经$A=a$分割后集合$D$的不确定性。基尼指数越大，不确定性就越大。

下图显示了二类分类问题中基尼指数Gini§、熵（单位比特）之半$H(p)/2$和分类误差率的关系。横坐标表示概率p，纵坐标表示损失。可以看出基尼指数和熵之半的曲线很接近，都可以近似地代表分类误差率。

算法（CART生成算法）：
输入：训练数据集D， 停止计算的条件；
输出：CART决策树
根据训练数据集，从根节点开始，递归地对每个结点进行以下操作，构建二叉决策树：

5.2 CART剪枝

CART剪枝算法从”完全生长“的决策树的底端减去一些子树，使决策树变小（模型变简单）,从而能够对未知数据有更准确的预测。
CART剪枝算法由两步组成：首先从生成算法产生的决策树$T_0$底端开始不断剪枝，直到$T_0$的根节点，形成一个子树序列 { T 0 , T 1 , . . . , T n } \{T_0,T_1,...,T_n\} {T0​,T1​,...,Tn​}；然后通过交叉验证法在独立的验证数据集上对子树序列进行测试，从中选择最优子树。

1. 剪枝，形成一个子树序列
   在剪枝过程中，计算子树的损失函数$$C_{\alpha }(T)=C(T)+\alpha |T|$$，其中T为任意子树，C(T)为对训练数据的预测误差（如基尼指数）,$|T|$为子树的叶结点个数，$\alpha \ge 0$为参数，$C_{\alpha }(T)$为参数是$\alpha$时的子树T的整体损失。参数$\alpha$权衡训练数据的拟合程度与模型的复杂度。
   对固定的$\alpha$，一定存在使损失函数$C_{\alpha }(T)$最小的子树，将其表示为$T_{\alpha }$。$T_{\alpha }$在损失函数$C_{\alpha }(T)$最小的意义下是最优的。

2. 在剪枝得到的子树序列 { T 0 , T 1 , . . . , T n } \{T_0,T_1,...,T_n\} {T0​,T1​,...,Tn​}中通过交叉验证选取最优子树$T_{\alpha }$
   具体地，利用独立的验证数据集，测试子树序列$T_0,T_1,...,T_n$中各棵子树的平方误差或者基尼指数。平方误差或基尼指数最小的决策树被认为是最优的决策树。在子树序列中，每棵子树$T_0,T_1,...,T_n$都对应于一个参数${\alpha }_1,{\alpha }_2,...{\alpha }_n$，所以，当最优子树$T_k$确定时，对应的${\alpha }_k$也确定了，即得到最优决策树$T_{\alpha }$。
   算法（CART剪枝算法）
   输入：CART算法生成的决策树$T_0$
   输出：最优决策树$T_{\alpha }$
   （1）设$k=0,T=T_0$
   （2）设$\alpha =+\infty$
   （3）自下而上地对各内部结点t计算$C(T)$，$|T_t|$以及$g(t)=\frac{C(t)-C(T_t)}{|T_t-1|},\alpha =\min (\alpha ,g(t))$，这里，$T_t$表示以t为根节点的子树，$C(T_t)$是对训练数据的预测误差，$|T_t|$是$T_t$的叶结点个数。
   （4）对$g(t)=\alpha$的内部结点t进行剪枝，并对叶结点t以多数表决法决定其类，得到树T
   （5）设$k=k+1,{\alpha }_k=\alpha ,T_k=T$
   （6）如果$T_k$不是由根节点及两个叶结点构成的树，则回到步骤（3）;否则令$T_k=T_n$
   （7）采用交叉验证法在子树序列 { T 0 , T 1 , . . . , T n } \{T_0,T_1,...,T_n\} {T0​,T1​,...,Tn​}中选取最优子树$T_{\alpha }$。

总结

无论ID3，C4.5，CART都是选择一个最优的特征做分类决策，但大多数，分类决策不是由某一个特征决定，而是一组特征。这样得到的决策树更加准确，这种决策树叫多变量决策树(multi-variate decision tree)。在选择最优特征的时，多变量决策树不是选择某一个最优特征，而是选择一个最优的特征线性组合做决策。代表算法OC1。

决策树的优点：
（1）相比于神经网络之类的黑盒分类模型，决策树在逻辑上可以很好解释。
（2）既可以处理离散值也可以处理连续值。很多算法只是专注于离散值或者连续值。
（3）使用决策树预测的代价是O(log2m)。m为样本数。
（4）对于异常点的容错能力好，健壮性高。

使用决策树的缺点：
（1）决策树算法非常容易过拟合，导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。
（2）决策树会因为样本发生一点的改动，导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。
（3）如果某些特征的样本比例过大，生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。

参考资料

[1] 《统计学习方法》 李航
[2] 知乎：小小《统计学习方法》（第五章）决策树