决策树（decision tree）

2020-07-06 本文已影响0人夜猫子丶CC

一. 信息论

1. 熵（entropy）

（1）熵：随机变量 不确定性 的度量

（2）数据：信息+噪音

① 信息：消除不确定性（熵）

② 噪音：干扰信息的获取

2. 熵与条件熵与联合熵推导

（1）熵公式

① 设：X是一个取有限个值的离散随机变量，概率分布为 $P(X=x_i)=p_i$

② 抛3个硬币的等可能结果有 $2^3=8$ 种，是指数关系，因此用反函数log计算

则：信息量 $I(x_i)=log\frac{1}{p(x_i)}$ （p(x)表示事件x发生的概率）

③ $H(X)=E[I(x_i)]=\sum_{i=1}^{n } p_i·I(x_i)=-\sum_{i=1}^{n } p_{i} \cdot \log p_{i}$ （底数可选，默认为e）

熵表示：各事件信息量的数学期望，范围[0,logn]。只依赖于X的分布，故也记为做H(p)

单位：比特（bit）或纳特（nat），与编码长度有关

（2）联合熵

① 设随机变量(X,Y)的联合概率分布为 $P(X=x_i,Y=y_j)=p_{ij}$

$H(X,Y)=E[I(X,Y)]=-\sum_{x,y} p(x,y)·logp(x,y)$

（3）条件熵（Conditional entropy）

① 定义：X在给定条件Y下的条件概率分布的熵对X的期望

②

$=-\sum_{x}\sum_{y}p_{ij}·logp(y|x)=\sum_{x,y}p_{ij}·logp(y|x)$

（4） $H(Y|X)=H(X,Y)−H(X)H(Y|X)=H(X,Y)−H(X)$

I(X,Y)称为互信息（mutual information）

3.信息增益

（1）定义：等价于互信息。表示得知特征A的信息后，使数据集D的分类不确定性减少的程度

（2）max： $Gain(D,A)=H(D)-H(D|A)$

（3）算法：

① 输入：训练数据集D，特征A

样本个数记为 $|D|$ ，类 $C_k$ 的样本个数记为 $|C_k|$

特征A取值记为{ $a_1,a_2...a_n$ }，根据A的取值将D划分为n个子集{ $D_1,D_2...D_n$ }

$D_{ik}$ 表示 $D_i$ 中属于类 $C_{k}$ 的样本

② 输出：训练集的经验熵： $H(D)=-\sum_{k=1}^{K} p_{k} \cdot \log p_{k} =-\sum_{k=1}^K \frac{|C_k|}{|D|} log\frac{|C_k|}{|D|}$

条件熵： $H(D|A)=-\sum_{x}p_i\sum_{y}p(y|x)logp(y|x)=-\sum_{i=1}^n \frac{|D_i|}{|D|} \sum_{k=1}^K\frac{|D_{ik}|}{|D_i|} log\frac{|D_{ik}|}{|D_i|}$

信息增益： $Gain(D,A)=H(D)-H(D|A)$

（4）改进：信息增益存在 “偏向选择取值多的特征” 的问题，引入信息增益率

训练集D关于特征A的熵： $H_A(D)=-\sum_{i=1}^n\frac{|D_i|}{|D|} \cdot \log \frac{|D_i|}{|D|}$

信息增益率： $Gain_{ratio}(D,A)=\frac{Gain(D,A)}{H_A(D)}$ （利用分母惩罚）

4.基尼系数

（1）定义：基尼系数代表了模型的不纯度，Gini(D)越小，D的纯度越高

（2）分类问题中，设有K个类C，样本属于第k类的概率为 $p_k$ ，则概率分布的基尼指数：

$Gini(p)=\sum_{k=1}^K p_k(1-p_k)=1-\sum_{k=1}^K p_k^2=1-\sum_{k=1}^K （\frac{|C_k|}{|D|} ）^2$

则，样本集合D根据特征A是否取某一可能值a被分割成D1和D2两部分

$Gini_{index}(D,A)=\frac{|D_1|}{|D|} Gini(D_1)+\frac{|D_2|}{|D|} Gini(D_2)$

二. 决策树模型

1. 定义

本质上是通过一系列规则对数据进行分类的过程。决策树是一个树结构，每个内部节点表示对一个属性的判断，每个分支代表一个判断结果的输出，最后每个叶节点代表一种分类结果。

2. 概念

（1）根结点(Root Node)：表示整个样本集合，该节点可以进一步划分成两个或多个子集。

（2）拆分(Splitting)：表示将一个结点拆分成多个子集的过程。

（3）决策结点(Decision Node)：当一个子结点进一步被拆分成多个子节点时，这个子节点就叫做决策结点。

（4）叶子结点(Leaf/Terminal Node)：无法再拆分的结点被称为叶子结点。

（5）剪枝(Pruning)：移除决策树中子结点的过程就叫做剪枝，跟拆分过程相反。

（6）分支/子树(Branch/Sub-Tree)：一棵决策树的一部分就叫做分支或子树。

（7）父结点和子结点(Paren and Child Node)：一个结点被拆分成多个子节点，这个结点就叫做父节点；其拆分后的子结点也叫做子结点。

3. 优点与缺点

（1）可读性高，推理过程便于写成 If-Then形式（互斥且完备）

（2）推理过程完全依赖于属性变量的取值特点

（3）可自动忽略目标变量没有贡献的属性变量，可为判断属性变量的重要性、减少变量的数目提供参考。

（4）对未知的测试数据未必有好的分类、泛化能力，可能发生过拟合现象，此时可采用剪枝或随机森林。

4. 条件概率分布

（1）决策树表示为：给定特征条件下，类的条件概率分布P(Y|X)。

（2）将特征空间划分为互斥的区域，决策树的一条路径对应于划分中的一个区域，并在每个区域定义一个类的概率分布，组成一个条件概率分布。

三. 决策树学习

1.目标：损失函数最小化

（1）假设：给定训练数据集D={ $(x _1 ,y _1 ),(x _2,y_2 ),...,(x _N ,y _N )$ }

其中， $x_i=(x^{(1)}_i,x^{(2)}_i,...,x^{(n)}_i)^T$ 为输入实例，n为特征个数， $y_i\in$ {1,2,...,K} 为类标记，N 为样本容量。

（2）损失函数确定以后，学习问题就变为在损失函数意义下选择最优决策树的问题。通常采用启发式方法，近似求解这一最优问题。这样得到的决策树是次最优（sub-optimal）的。

2. 特征选择

（1）目的：选择具有分类能力的特征，准则是划分后，不确定性降低

① ID3：通过信息增益选择特征

② C4.5：通过信息增益比选择特征

③ CART：通过Gini指数选择特征

（2）方法：相当于特征空间的划分。递归地选择最优特征，并根据该特征对训练数据进行切割，使得对各个子数据集有一个最好的分类的过程。

3. 决策树的生成

根据选择的特征评估标准，从上至下递归地生成子节点，直到数据集不可分则停止决策树停止生长。每个子集都被分到叶结点上，即都有了明确的类。这就生成了一棵决策树。

4. 决策树的修剪

（1）为避免过拟合，对已生成的树自下而上进行剪枝，将树变得简单（叶节点数少、叶子节点深度小），从而使得它具有更好的泛化能力。具体地，就是去掉过于细分的叶结点，使其回退到父结点，甚至更高的结点，然后将父点或更高的结点改为新的叶结点。

（2）通过极小化损失函数实现： $C_α(T)=\sum_{t=1}^{|T|} N_tH_t(T)+α|T|$

C(T)为训练数据的预测误差，Nt为叶节点样本数，α≥0，|T|为模型的复杂度。

四. 决策树算法

1. ID3

（1）概念：从根节点开始，对每个特征进行遍历，选择特征中信息增益最大的特征来划分数据，并建立子节点。之后在子节点中递归调用该方法。ID3相当于用极大似然法进行概率模型的选择。

（2）算法

① 输入：训练数据集D，特征A，阈值

② 输出：决策树T

Step1—若D中所有实例属同一类 $C_k$ ，则T为单结点树。将 $C_k$ 作为该结点的类标记，返回T；

Step2—若A=∅，则T为单结点树，将D中实例数最大的类 $C_k$ 作为该结点的类标记，返回T；

Step3—否则，计算A中各特征对D的信息增益，选择信息增益最大的特征 $A_g$

Step4—若 $Gain (D,A_g)<ε$ ，则T为单结点树，将D中实例数最大的类 $C_k$ 作为该结点的类标记，返回T；

Step5—否则。对 $A_g$ 的每一个可能值 $a_i$ ，依 $A_g=a_i$ 将D分割为若干非空子集 $D_i$ ，将 $D_i$ 中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树T，返回T；

Step6—对第i个子结点，以 $D_i$ 为训练集，以 $A−{\lceil A_g}\rfloor$ 为特征集，递归地调用1~5，得到子树 $T_i$ ，返回 $T_i$ ；

（3）缺点：

① ID3没有考虑连续特征，比如长度，密度都是连续值，无法在ID3运用。

② 采用信息增益的缺点：在相同条件下，取值较多的特征信息增益大。

2. C4.5

C4.5算法过程跟ID3算法一样，只是选择特征的方法改成信息增益比。

3. 分类回归树(Classification and Regression Tree，CART）——二叉树

（1）回归树：平方误差最小化（复杂度较高）

① 设Y是连续变量，训练集为D={ $(x_1,y_1), (x_2,y_2), …, (x_n,y_n)$ }

将输入空间划分为M个区域 $R_1,R_2,…,R_m$ ，每个区域的输出值分别为 $c_1,c_2,…,c_m$

则回归树模型可表示为： $f(x)=\sum_{m=1}^M c_mI$ （I为指示函数，为真取1）

② 平方误差： min $\sum_{x_i} (y_i-f(x_i))^2$

③ 启发式生成算法：

Step1—依次遍历每个特征 j ，以及该特征的每个取值s，计算每个切分点（j,s）的损失函数，选择损失函数最小的作为切分点

Step2—用切分点将当前的输入空间切分为 $R_1、R_2$ ，决定输出值 $\hat{c_m}=\frac{\sum_{x_i} y_i}{N_m}$

Step3—对上述两个子区域递归调用(1)(2)，直到没有特征可以选择，或者子节点数目很小或者平方误差小于阈值为止

Step4—将输出空间划分为M个区域，生成决策树

（2）分类树：Gini index最小化

① 基尼指数： $Gini_{index}(D,A)=\frac{|D_1|}{|D|} Gini(D_1)+\frac{|D_2|}{|D|} Gini(D_2)$

② 生成算法：

从根结点开始，递归地对每个结点进行以下操作，构建二叉决策树：

Step1—设结点的训练数据集为D，对每一个特征A可能取的每个值a，根据样本点对A=a的测试为“是”或“否”，将D分割成D1和D2两部分，计算A=a时的基尼指数；

Step2—在所有可能的特征A以及它们所有可能的切分点a中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点；

Step3—对两个子结点递归地调用(1)(2)。算法停止条件是节点中的样本个数小于预定阈值，或样本集的基尼指数小于预定阈值，或者没有更多特征。

Step4—生成CART决策树

（2）对连续特征和离散特征的处理

① 连续特征：与C4.5思想相同，都是将连续的特征离散化。

② 离散特征：不停地二分离散特征。

（3）剪枝算法：

① 损失函数： $C_α(T)=\sum_{t=1}^{|T|} =N_tH_t(T)+α|T|$

② 算法：

Step1—设 $k=0，T=T_0$ ， $α=+∞$

Step2—自下向上从 $T_0$ 开始剪枝，以t为单节点树的损失函数 $C_α(t)=C(t)+α$ ;

以t为根节点树的子树 $T_t$ 的损失函数 $C_α(T_t)=C(T_t)+α|T_t|$ ；

Step3—当α充分小，有 $C_α(T_t)<C_α(t)$ ，随着α增大，不等式反向。

令 $g(t)=\frac{C(t)-C(T_t)}{|T_t|-1}$ ，在 $T_0$ 中剪去g(t)的最小 $T_t$ ，令 $α=min⁡(α,g(t))$

Step4—自上向下访问各内部节点t，若 $g(t)=\alpha$ ，则进行剪枝，并对t以多数表决的方式决定其类。得到树T；

Step5—若T不是由根节点单独构成的树，则重复步骤(4)，得到一系列的子树。

Step5—最后使用交叉验证的方式从子树序列{ $T_0,T_1,...T_n$ }中选取最优子树