决策树的特征选择、生成、剪枝。熵、信息增益、基尼指数。ID3、C4.5、CART。

决策树背景

概览

树的意义

决策树是一棵if-then树。 内部节点代表一个属性或特征，叶节点代表一个类。

决策树也是给定各个特征的情况下，某类别的概率。即条件概率$P(Y\mid X)$。

树的生成

构建根节点，选择最优特征。按照特征划分子集，继续选择新的最优特征，直到没有或者全部被正确分类。

剪枝

决策树的生成对应于模型的局部选择，会尽量拟合训练数据，导致模型复杂和过拟合。

决策树的剪枝对应于模型的全局选择， 自下而上删掉一些节点。

熵和信息增益

在每个节点，要选择一个最优特征生成。

• ID3使用信息增益最大选择最优特征
• C4.5使用信息增益率最大来选择最优特征
• CART回归树 ，平方误差最小
• CART分类树， 基尼指数最小

信息量

信息量是随机变量$X$不确定性的度量。

$$I(X)=-\log p(x)$$

熵

熵是信息量的期望，也是随机变量不确定性的度量。熵偏向离散属性， 基尼指数偏向连续属性。

$$H(X)=-\sum _{x\in X}p(x)\log p(x)$$

条件熵

条件熵是在给定随机变量$X$的情况下，随机变量$Y$的不确定性。

$$H(Y\mid X)=\sum _{i=1}^{K}p(x_i)H(Y\mid X=x_i)$$

$X$共有K类，$p(x_i)$表示$X$属于第$i$类的概率。$H(Y\mid X=x_i)$表示$X=x_i$时$Y$的子集的熵。

经验熵和经验条件熵

由数据估计（极大似然估计）得到的熵和条件熵。

如数据集D，有K个类别。经验熵是

$$H(D)=-\sum _{k=1}^K\frac{|C_k|}{|D|}{\log }_2\frac{|C_k|}{|D|}$$

特征A根据取值把数据集D划分为n个子集，则给定特征A时数据集D的经验条件熵是：

$$H(D\mid A)=\sum _{i=1}^n\frac{|D_i|}{|D|}H(D_i)=-\sum _{i=1}^n\frac{|D_i|}{|D|}\sum _{k=1}^K\frac{|D_{ik}|}{|D_i|}{\log }_2\frac{|D_{ik}|}{|D_i|}$$

信息增益

信息增益是给定特征A，使得数据集D不确定性减少的程度。信息增益 = 划分前熵 - 划分后熵 = 熵 - 条件熵

$$g(D,A)=H(D)-H(D\mid A)$$

特征A的信息增益越大，不确定性减少越多，A的分类能力就越强。

信息增益的问题

对于取值很多的特征，比如连续型数据(时间)。每一个取值几乎都可以确定一个样本。即这个特征就可以划分所有的样本数据。

• 信息增益不适合连续型、取值多的特征

• 使得所有分支下的样本集合都是纯的，极端情况每一个叶子节点都是一个样本

• 数据更纯，信息增益更大，选择它作为根节点，结果就是庞大且深度很浅的树

信息增益比

数据集$D$关于特征A的熵，$n$是特征A的取值个数：

$$H_A(D)=-\sum _{i=1}^n\frac{|D_i|}{|D|}{\log }_2\frac{|D_i|}{|D|}$$

信息增益比 = 信息增益 / 划分前熵 = 信息增益 / D关于特征A的熵 ：

$$g_R(D,A)=\frac{g(D,A)}{H_A(D)}=\frac{H(D)-H(D\mid A)}{H_A(D)}$$

解决信息增益的问题：特征A分的类别越多，$D$关于A的熵就越大，作为分母，所以信息增益$g_R(D,A)$ 就越小。在信息增益的基础上增加了一个分母惩罚项。

信息增益比的问题：实际上偏好可取类别数目较少的特征。

基尼指数

CART分类树使用基尼指数来选择最优特征。 基尼指数也是度量不确定性。 熵偏向离散属性， 基尼指数偏向连续属性。

概率分布基尼指数

分类中，有$K$类。 样本属于第$k$类的概率为$p_k$。

$$\mathrm{G}\mathrm{i}\mathrm{n}\mathrm{i}(\mathrm{p})=\sum _{\mathrm{k}=1}^{\mathrm{K}}{\mathrm{p}}_{\mathrm{k}}(1-{\mathrm{p}}_{\mathrm{k}})=1-\sum _{\mathrm{k}=1}^{\mathrm{K}}{\mathrm{p}}_{\mathrm{k}}^2$$

样本集合基尼指数

集合D，有$K$类，$D_k$ 是第k类的样本子集。则D的基尼指数

$$\mathrm{G}\mathrm{i}\mathrm{n}\mathrm{i}(\mathrm{D})=1-\sum _{\mathrm{k}=1}^{\mathrm{K}}{\left(\frac{|{\mathrm{D}}_{\mathrm{k}}|}{|\mathrm{D}|}\right)}^2$$

特征A条件基尼指数

特征A取值为某一可能取值为a。 根据A是否取值为a把D划分为$D_1$和$D_2$两个集合。

在特征A的条件下，D的基尼指数如下：

$$\mathrm{G}\mathrm{i}\mathrm{n}\mathrm{i}(\mathrm{D},\mathrm{A})=\frac{|{\mathrm{D}}_1|}{|\mathrm{D}|}\mathrm{G}\mathrm{i}\mathrm{n}\mathrm{i}({\mathrm{D}}_1)+\frac{|{\mathrm{D}}_2|}{|\mathrm{D}|}\mathrm{G}\mathrm{i}\mathrm{n}\mathrm{i}({\mathrm{D}}_2)$$

$\mathrm{G}\mathrm{i}\mathrm{n}\mathrm{i}(\mathrm{D},\mathrm{A})$是集合D根据特征A分割后，集合D的不确定性。

ID3算法

决策树的生成，ID3算法以信息增益最大为标准选择特征。递归构建，不断选择最优特征对训练集进行划分。

递归终止条件：

• 当前节点的所有样本，属于同一类别$C_k$，无需划分。该节点为叶子节点，类标记为$C_k$
• 当前属性集为空，或所有样本在属性集上取值相同
• 当前节点的样本集合为空，没有样本

在集合D中，选择信息增益最大的特征$A_g$ ：

• 增益小于阈值，则不继续向下分裂，到达叶子节点。该节点的标记为该节点所有样本中的majority class$C_k$。 这也是预剪枝
• 增益大于阈值，按照特征$A_g$的每一个取值$A_g=a_i$把D划分为各个子集$D_i$，去掉特征$A_g$

继续对每个内部节点进行递归划分。

C4.5算法

C4.5是ID3的改进，C4.5以信息增益率最大为标准选择特征。

ID3/C4.5决策树剪枝

决策树的生成，会过多地考虑如何提高对训练数据的分类，从而构建出非常复杂的决策树。就容易过拟合。

剪枝就是裁掉一些子树和叶节点，并将其根节点或父节点作为叶节点。剪枝分为预剪枝和后剪枝。

预剪枝

在生成树的时候，设定信息增益的阈值，如果某节点的某特征的信息增益小于该阈值，则不继续分裂，直接设为叶节点。选择该节点的D中类别数量最多的类别 （majority class）作为类别标记。

后剪枝

树构建好以后，基于整体，极小化损失函数，自下而上地进行剪枝。

树T的参数表示

• 叶节点的个数$|T|$
• 叶节点$t$
• 叶节点$t$上有$N_t$个样本
• 有$K$类
• 叶节点t上的经验熵$H_t(T)$
• $\alpha \ge 0$ 为惩罚系数

叶节点t上的经验熵

$$H_t(T)=-\sum _{k=1}^K\frac{N_{tk}}{N_t}\log \frac{N_{tk}}{N_t}$$

模型对训练数据的拟合程度$C(T)$ ，所有叶节点的经验熵和：

$$C(T)=\sum _{t=1}^{|T|}{N}_t{H}_t(T)$$

最终损失函数 = 拟合程度 + 惩罚因子 ：

$$C_{\alpha }(T)=C(T)+\alpha |T|$$

参数$\alpha$权衡了训练数据的拟合程度和模型复杂度。

• $\alpha$大，决策树简单，拟合不好
• $\alpha$小，决策树复杂，过拟合

剪枝步骤

1. 计算每个节点的经验熵
2. 递归从树的叶节点向上回缩。叶节点回缩到父节点：整体树：回缩前$T_1$ ，回缩后$T_2$
   • $C_{\alpha }(T_2)\le C_{\alpha }(T_1)$， 则回缩到父节点， 父节点变成新的叶节点。

CART-回归树

Classification and regression tree分类与回归树。

• 回归-平方误差最小
• 分类-基尼指数最小
• 二叉树
• 内部节点：是 - 否。如特征$A \le a $或 $A>a$

模型

把输入空间划分为M个单元$R_1,R_2,\cdots ,R_M$， 每个单元有多个样本，有一个固定的输出值$c_m$。

$${\hat{c}}_m=\mathrm{a}\mathrm{v}\mathrm{g}({\mathrm{y}}_{\mathrm{i}}),{\mathrm{y}}_{\mathrm{i}}\in {\mathrm{R}}_{\mathrm{m}}$$

树模型 ：

$$f(x)=\sum _{m=1}^M{c}_{m}I(x\in R_m)$$

划分单元

寻找最优切分变量j和最优切分点s 。

选择第$j$个变量$x^{(j)}$和其取值$s$， 作为切分变量和切分点，划分为两个空间 $R_1,R_2$，输出分别为**$c_1,c_2$** :

$$R_1(j,s)=\{x\mid x^{(j)}\le s\},R_2(j,s)=\{x\mid x^{(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_1(j,s)}(y_i-c_1{)}^2]$$

对每个区域重复划分过程，直到停止。也叫作最小二乘回归树。

CART-分类树

基尼指数最小原则 。

对每一个数据集D，对每一个特征A，对每一个A的取值$A=a$ 是或者否，划分两个自己$D_1$和$D_2$

• 计算在特征$A=a$条件下的基尼指数$\mathrm{G}\mathrm{i}\mathrm{n}\mathrm{i}(\mathrm{D},\mathrm{A}=\mathrm{a})$
• 选择基尼指数最小特征A及其取值a，作为最优特征和最优切分点
• 从现节点划分为两个子节点

CART剪枝

剪枝总体步骤

• 从生成的决策树$T_0$开始， 从底端向上开始剪枝，直到$T_0$的根节点。损失函数决定是否剪枝

• 形成子树序列$\{T_0,T_1,\cdots ,T_n\}$

• 交叉验证子树序列，选择最优子树

K-折交叉验证法

数据集划分为K个子集。每个子集分别做一次验证集，其余K-1组作为训练集。得到K个模型。

剪枝损失函数

$$C_{\alpha }(T)=C(T)+\alpha |T|$$

$C(T)$为所有叶节点的经验熵和 ：

$$C(T)=\sum _{t=1}^{|T|}{N}_t{H}_t(T)$$

$\alpha$权衡训练数据拟合程度和模型复杂度。

整体树$T_0$的任意内部节点t ， $\alpha$从0开始，每次一个小区间$[{\alpha }_i,{\alpha }_{i+1})$ ：

• t为单节点树时损失：$C\alpha (t)=C(t)+\alpha$
• t为根节点子树时损失：$C_{\alpha }(T_t)=C(T_t)+\alpha |T_t|$
• $\alpha =0$时， $C\alpha (t)<C_{\alpha }(T_t)$ 。因为，树大，精确，损失小。
• 随着$\alpha$的增大，会达到： $C\alpha (t)=C_{\alpha }(T_t)$

求得临界点$\alpha$

$$\alpha =\frac{C(T)-C(T_t)}{|T_t|-1}$$

对每个内部节点求：

$$g(t)=\frac{C(T)-C(T_t)}{|T_t|-1}$$

• 在$T_0$中减去最小的$g(t)$对应的子树$T_t$ ， 作为$T_1$
• t节点作为叶子节点，类标记为majority class
• 最后再交叉验证所有的子树序列即可