决策树算法原理

一、决策树算法原理

1.1案例

  决策树（Decision Tree）是一种树模型，既可用于分类任务，也可用于回归任务。决策树模型基于各种情况发生的所需条件构成，以实现期望最大化为目的，由于决策分支画成图形如同一棵树的枝干，故称为决策树。比如，根据年龄、姓名信息判断是否玩电子游戏：

• age<15：可能玩电子游戏。
• male：可能玩电子游戏。

在对任意数据进行预测时，都需要从决策树的根结点开始，一步步走到叶子结点（执行决策的过程），最终完成决策。但注意，决策树对每次决策时所选择的信息有着严格要求，比如此时不能先判断性别，而必须先判断年龄。一般的，会将分类效果最优秀的属性信息放在离根节点最近处用于决策，而分类效果的评价指标，就需要使用到熵的概念。对于决策树的结构，可有如下理解：

• 根节点：第一个选择节点。
• 非叶子节点与分支：中间过程。
• 叶子节点：最终的决策结果。

  决策树的训练与测试：

• 训练阶段：从给定的训练集构造出一棵树（从根节点开始选择特征）。
• 测试节点：根据构造的决策树模型从根节点走到叶节点的过程。

在构造好决策树后，只需从根节点走到叶节点即可完成分类或预测任务。

1.2熵

  熵是表示随机变量不确定性的度量（即，物体内部的混乱程度），比如两个集合A、B：
$$\begin{gathered} A=1,1,1,1,1,1,1,1,2,2 \\ B=1,2,3,4,5,6,7,8,9,1 \end{gathered}$$
显然，A集合中的熵值低于B集合，因为A集合中只有1、2两种数据，更加稳定。而B集合中数据种类更多，熵值就会大很多。
  在决策树选择节点时，其希望使用该节点属性对样本数据进行分类后，能使整个样本集在各自的类别里尽可能单一，即希望某个特征在被用于分类后，能最大程度地降低样本数据的熵。如：

可以直观认为，决策树2的效果更加优秀，从熵的角度看，决策树2通过特征$x_2$分类后，整个样本被划分为两个分别有序的类簇；而决策树 1 在通过特征$x1$进行分类后，得到的分类结果依然混乱（甚至有熵增的情况），因此这个特征在现阶段被认为是无效特征。也可以说，选择特征$x_2$所获得的信息增益大于选择特征$x1$。

• 信息增益：表示特征X使得类Y的不确定性减少的程度。

  熵的计算公式为：

• $X$：取值在有限范围内的一个离散随机变量。
• $p_i$：随机变量$X=x_i$时的概率密度。
• $k$：随机变量X的取值个数。

$p_i、k$的定义如下图所示：

从熵值定义公式可以看出，熵值仅仅依赖于随机变量X的分布而与其取值无关。并且，熵值有如下特点：

• $H(X)=0$：随机变量X完全没有不确定性，即到达叶子节点，完成了预测或分类。
• $H(X)=1$：随机变量X不确定性最大。

在引入熵的计算公式后，就能更准确地实现对节点特征的选择。

【例子】现有两个集合， A = { 1 , 2 } ， B = { 1 , 2 , 3 , 4 , 5 , 6 } A=\{1,2\}，B=\{1,2,3,4,5,6\} A={1,2}，B={1,2,3,4,5,6}，计算其熵值。
  集合A的分布列为：

  计算熵值：

  集合B的分布列为：

  计算熵值：

  显然，集合A的熵值更低，B的熵值更高。

1.2条件熵

  在提出熵的概念后，在构建决策树时即可根据选择某一特征时对样本数据集熵值所产生的影响，来确定合适的分支节点用于构造决策树。例如，当选择不同特征对数据集划分时，可得到共4种决策树模型：

• 1.计算原始数据集D的熵，数据集D仅有举办与不举办两标签，初始熵为：

• 2.计算按天气特征划分后得到数据集的熵：

按天气划分后可得晴天、阴天、雨天共三个子数据集，计算各自的熵值：

从原始数据表可知，“天气” 特征取值为 “晴天”、“阴天”、“雨天” 的概率分别为$\frac{8}{14}$、$\frac{3}{14}$、$\frac{3}{14}$因此，若以 “天气” 特征为现阶段的内部节点（用于划分的特征），则整个系统的熵值为：

实际上，求解按天气特征划分下各子集熵值的过程，就是在求条件熵$H(Y|X)$。
  条件熵$H(Y|X)$：在已知随机变量$X$的条件下随机变量$Y$的不确定性。其公式定义为：

其中，$p_i=P(X=x_i)$，在上例中，即为晴天、阴天、雨天在整个样本集的比例。$H(Y|X=x_i)$：$X=x_i$时，数据集的熵值、在上例中，即为三个子数据集的熵值。

• 3.按此定义，可计算出特征取温度时的条件熵：
  $H(Y\mid X_{温度})=P(X="炎热")H(Y\mid X="炎热")+P(X="正常")H(Y\mid X="正常")+P(X="寒冷")H(Y\mid X="寒冷")\approx 0.6931$
• 4.特征取风速时的条件熵：
  $H(Y\mid X_{风速})=P(X="强")H(Y\mid X="强")+P(X="弱")H(Y\mid X="弱")\approx 0.5983$
• 5.特征取湿度时的条件熵：
  $H(Y\mid X_{湿度})=P(X="干燥")H(Y\mid X="干燥")+P(X="正常")H(Y\mid X="正常")+P(X="潮湿")H(Y\mid X="潮湿")\approx 0.6315$

三、划分依据

  从上文中学会了决策树的基本原理、计算熵、计算条件熵，而如何利用这些计算结果完成决策树的构造，衍生出了几种方案。

3.1ID3算法：信息增益

• 信息增益$g(D,X)$：以某特征划分数据集后，数据集不确定性（熵）的减少程度，计算方式为数据集D的熵$H(D)$与给定特征X划分后得到数据子集的熵$H(D|X)$之差：

  ID3算法使用信息增益作为选择节点特征的依据，前文中已计算出数据集熵为$H(D)=0.6931$，按不同特征划分后得到的条件熵为：

• $H(D|X_{天气})$=0.3961
• $H(D|X_{温度})$=0.6931
• $H(D|X_{风速})$=0.5983
• $H(D|X_{湿度})$=0.6315

从而计算出按不同特征划分后的信息增益：

• $g(D|X_{天气})=H(D)-H(D|X_{天气})$=0.6931−0.3961=0.2970
• $g(D|X_{温度})=H(D)-H(D|X_{湿度})$=0.6931−0.6931=0.0000
• $g(D|X_{风速})=H(D)-H(D|X_{风速})$=0.6931−0.5983=0.0948
• $g(D|X_{湿度})=H(D)-H(D|X_{湿度})$=0.6931−0.6315=0.0616

可见，以天气作为划分依据时，系统整体熵值降低为0.297，此时信息增益最大。

3.2C4.5算法：信息增益率

  ID3算法以信息增益作为划分依据时，其会偏向于取值多的特征。比如给数据集加上编号作为特征，其共有14个取值。此时，该特征会成为最优的划分特征（给定一个编号就一定能知道那天是否举行过运动会，因此有最高的信息增益）。

将编号作为特征划分决策树：

条件熵：

此时信息增益为最大值：

但这种划分方式实际上并无意义，在C4.5算法中引入信息增益率作为划分条件。

• 信息增益率$g_R(D,X)$：特征X在数据集D熵的信息增益$g(D,X)$与数据集D在特征X上值的熵$H_X(D)$之比。计算方法：

其中，$$H_X(D)=-\sum _{i=1}^k\frac{|D_i|}{D}log\frac{|D_i|}{D}$$，其中，k是特征X的取值类别个数。信息增益率考虑了特征本身的熵（此时，当某特征取值类别较多时，$g_R(D,X)$式中的分母也会增大），从而降低了 “偏向取值较多的特征” 这一影响。根据该式，可得到基于各特征划分的信息增益率如下：

3.3CART算法：基尼系数

  ID3算法、C4.5算法均涉及大量对数运算，提高了模型复杂度、分类回归树（Classification and Regression Tree，CART）使用基尼系数来代替信息增益率，从而避免复杂的对数运算。基尼系数代表了模型的不纯度，基尼系数越小，则不纯度越低，特征越好。注：这一点和信息增益（率）恰好相反。
  分类问题中，假设有k个类别，且第i个类别的概率分布为$p_i$，则该数据集的基尼系数为：

【例子】

  使用$Gini(D,X)$表示按特征X划分后，数据集D的基尼系数。计算公式为：

该值越大，表示数据集D的不确定性越大，也说明按特征X划分时效果并不好。将数据集按不同特征划分后，所得系统整体基尼系数为：
$Gini(D,X_{编号})={\sum }_{i=1}^{14}\frac{|C_i|}{D}Gini(D_i)=\frac{1}{14}(1-1^2)+\frac{1}{14}(1-1^2)+...+\frac{1}{14}(1-1^2)$
$Gini(D,X_{天气})={\sum }_{i=1}^3\frac{|C_i|}{D}Gini(D_i)=\frac{8}{14}(1-((\frac{4}{8}{)}^2+(\frac{4}{8}{)}^2))+\frac{3}{14}(1-(\frac{3}{3}{)}^2)+\frac{3}{14}(1-(\frac{3}{3}{)}^2)$≈0.2857
$Gini(D,X_{温度})={\sum }_{i=1}^3\frac{|C_i|}{D}Gini(D_i)=\frac{6}{14}(1-((\frac{3}{6}{)}^2+(\frac{3}{6}{)}^2))+\frac{4}{14}(1-((\frac{2}{4}{)}^2+(\frac{2}{4}{)}^2))+\frac{4}{14}(1-((\frac{2}{4}{)}^2+(\frac{2}{4}{)}^2))$≈0.5000
$Gini(D,X_{风速})={\sum }_{i=1}^2\frac{|C_i|}{D}Gini(D_i)=\frac{7}{14}(1-((\frac{2}{7}{)}^2+(\frac{2}{5}{)}^2))+\frac{7}{14}(1-((\frac{5}{7}{)}^2+(\frac{2}{7}{)}^2))\approx 0.4082$
$Gini(D,X_{湿度})={\sum }_{i=1}^3\frac{|C_i|}{D}Gini(D_i)=\frac{4}{14}(1-((\frac{2}{4}{)}^2+(\frac{2}{4}{)}^2))+\frac{6}{14}(1-((\frac{4}{6}{)}^2+(\frac{2}{6}{)}^2))+\frac{4}{14}(1-((\frac{1}{4}{)}^2+(\frac{3}{4}{)}^2))$≈0.4405

  由此可见，基尼系数也无法解决编号问题，为此衍生出基尼增益、基尼增益比，见文章：点击跳转。

四、连续值的处理

  在上文的数据集中，各特征包括标签均为离散型数据（如，天气={晴天，阴天，雨天}，风速={强，弱}、标签={是，否}），这些数据方便实现数据集的划分，但当存在连续型数据的特征时，就需要将连续型数据划分为多个区间，并将每个区间视为该特征的一个取值（新的离散值），再根据这一取值划分数据集。
【例子】数据集中引入连续型数据特征——温度

  可按约定俗成的标准将温度特征转化为离散型随机变量：

  而对于一组任意的数据，如：

常见的方式为对原数据进行排序，再取任意相邻值的中位点作为划分点。如，取65和72的中位点=$\frac{65+72}{2}=68.5$进行划分。
  对于含有n个数据的特征，共有n-1个中位点供选择，事实上，中位点的选取标准与决策树构建标准相同，均是希望划分后的数据集不确定度得以降低，故仍可使用信息熵、基尼系数作为指标来选取中位点。如，选择68.5作为中位点，此时温度特征划分为含两个离散值的特征，再计算此时的信息增益即可。
  注意，在评估决策树执行分类或回归任务的效果时，其方式也有所不同。对于分类任务，可用熵或基尼系数；对于回归任务，则需要用方差来衡量最终落到某个叶子节点中的数值之间的差异（方差越小则说明数据之间的差异越小，越应该被归类到一类）。注：决策树在执行回归任务时，其最终反馈的结果应当取某个叶子结点中所有数的均值。

五、决策树剪枝处理

  对于决策树而言，只要不断向下划分，理论能将几乎所有数据全都区分开，此时决策树也非常庞大。故而，决策树需要通过剪枝解决其存在的过拟合风险。主要有两种剪枝策略：

• 预剪枝：构建决策树的同时进行剪枝处理。
• 后剪枝：构建决策树后再剪枝处理。

5.1预剪枝策略

  预剪枝策略主要包含限制决策树深度、叶子节点个数、叶子节点样本数、信息增益量等。

• 1.限制决策树深度。

• 2.限制决策树中叶子节点的个数

• 3.限制决策树中叶子结点包含的样本个数

• 4.限制决策树的最低信息增益

5.2后剪枝策略

  后剪枝有如下衡量标准：

• $L_{\alpha }$：决策树模型的最终损失（越小越好）。
• $Gini(T)$：当前节点的熵或基尼系数。
• $|T|$：当前节点包含的数据样本个数。
• $T_{leaf}$:当前结点被划分后产生的叶子结点个数（显然，叶子节点越多损失越大）.
• $\alpha$：用户指定的偏好指数（$\alpha$越大代表我们对 “划分出更多的子结点” 的惩罚越大，即越不偏好于决策树的过分划分，因此有助于控制模型过拟合；反之，$\alpha$越小表示我们对 “划分出更多的子结点” 的惩罚越小，即更希望决策树能在训练集上得到较好的结果，而不在意过拟合风险）

常见的决策树模型：
【例子1】

【例子2】

六、回归问题的解决

  分类问题中，当执行到决策树的叶子节点时，会以该叶子节点所含样本的众数作为分类类别（决策树模型是监督学习算法）。而在回归问题中，其最终反馈的结果应当取某个叶子结点中所有数的均值。
  并且，在评估决策树执行分类或回归任务的效果时，其方式也有所不同。对于分类任务，可用熵或基尼系数；对于回归任务，则需要用方差来衡量最终落到某个叶子节点中的数值之间的差异（方差越小则说明数据之间的差异越小，越应该被归类到一类）。