决策树的理解与应用

背景

决策树🌲是一种基本的分类和回归的方法【以前总是下意识以为决策树只能用于分类，事实上还可以用于回归】。在分类问题中，决策树基于特征对实例进行分类，这个分类过程可以认为是if-then的规则集合，也可以认为是特征空间与类空间上的条件概率分布。

NOTE:
if—then规则集合具有一个重要的特征：互斥且完备，即每个实例都被一条路径或者一条规则所覆盖，而且只能被一条路径或一条规则所覆盖

优点：简单易理解、分类速度快

过程：利用损失函数最小化原则对训练集进行建模，再利用建立好的模型进行分类。决策树的学习算法通常是递归地选择最优特征，并根据特征对训练集进行分割，最终形成从【根结点->叶子结点】的树模型，但是这样生成的树可以容易发生过拟合，所以需要自底向上修剪✋

决策树学习包括三个步骤：特征选择、决策树生成、决策树修剪
1.当特征数量较多时，在学习之前先进行特征选择
2.决策树生成对应局部最优
3.决策树修剪对应全局最优

目标：选择一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。

特征选择

通常，特征选择的准则是信息增益或者信息增益比

先介绍基本概念：

熵
熵用来表示随机变量不确定的程度，熵越大，不确定程度越大。
设 $X$ 是一个取有限值的随机变量，概率分布为 $P(X=x_i)=p_i,i=1,2,...,n$
那么熵定义为：
$H(X)=-\sum_{i=1}^{n}p_ilogp_i,i=1,2,...,n$
NOTE:
熵只依赖 $X$ 的分布，与 $X$ 的取值无关，定义 $0log0=0$ 。
条件熵
条件熵 $H(Y|X)$ 表示在已知随机变量 $X$ 的条件下随机变量 $Y$ 的不确定性。
定义为： $H(Y|X)=\sum_{i=1}^{n}P(X=x_i)H(Y|X=x_i),i=1,2,...,n$
经验熵和经验条件熵
当熵和条件熵中的概率是由数据估计而得到的，所对应的熵和条件熵被称为经验熵和经验条件熵
信息增益
特征 $A$ 对训练集 $D$ 的信息增益 $g(D,A)$ ,定义为集合 $D$ 的经验熵与在给定条件 $A$ 下 $D$ 的经验条件熵H(D|A)之差，即
$g(D,A)=H(D)-H(D|A)$
特征选择过程：对训练集计算每个特征的信息增益，并比较信息增益的大小，选择信息增益最大是特征。
算法：
INPUT:训练数据集 $D$ 和特征 $A$
OUTPUT:特征 $A$ 对训练数据 $D$ 的信息增益 $g(D,A)$
计算数据集 $D$ 的经验熵**
$H(D)=-\sum_{k=1}^{K}\frac{|C_k|}{|D|}log_2\frac{|C_k|}{|D|}$
计算特征 $A$ 对训练数据 $D$ 的经验条件熵 $H(D|A)$ ：**
$H(D|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|}$
计算信息增益**
$g(D,A)=H(D)-H(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$ 的个数。

决策树生成

ID3算法
核心：在决策树各个结点上应用信息增益准则选择特征，然后递归地构建决策树。
过程：从根结点开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点，再对子结点递归地调用以上方法，构建决策树，直到所有的特征信息增益均很小或者没有特征可以选择为止。
ID3相当于用极大似然法进行概率模型的选择
NOTE:
由于ID3算法只有树的生成，所以生成的树模型容易产生过拟合现象。
C4.5算法
过程与ID3相似，只是对ID3进行了改进，使用信息增益比来选择特征。

决策树剪枝

决策树的生成过程仅考虑到对训练数据集分类的准确性，这样生成的树模型容易出现过拟合且构建的树过于复杂，所以有必要对其进行剪枝。

剪枝：从已生成的树上裁掉一些子树或者叶结点，并将其根结点或者父结点作为新的叶结点，从而简化分类树模型。剪枝往往是通过极小化决策树的整体损失函数来实现的

定义损失函数：
设树 $T$ 的叶结点个数为 $|T|$ , $t$ 是树的叶结点，该叶结点有 $N_t$ 个样本点，其中 $k$ 类的样本点有 $N_{tk},k=1,2,...,K$ ，其中 $H_t(T)$ 是叶子结点 $t$ 的经验熵， $\alpha\geq 0$ 为参数，决策树学习的损失函数为：
$C_a(T)=\sum_{t=1}^{|T|}N_tH_t(T)+\alpha|T|$
其中 $H_t(T)=-\sum_{k=1}^{K}\frac{N_{tk}}{N_t}log\frac{N_{tk}}{N_t}$
所以最终的损失函数表示为：
$C_a(T)=-\sum_{t=1}^{|T|}\sum_{k=1}^{K}N_{tk}log\frac{N_{tk}}{N_t}+\alpha|T|$

公式解释： $-\sum_{t=1}^{|T|}\sum_{k=1}^{K}N_{tk}log\frac{N_{tk}}{N_t}$ 是表示模型对训练集的预测误差，即模型与训练集的拟合程度， $|T|$ 表示模型的复杂度，叶子节点数越大模型越复杂， $\alpha$ 是调节参数，控制模型的拟合和复杂程度。
当 $\alpha$ 确定时，选择损失函数最小的模型，这里定义的损失函数其实等价于正则化的极大似然估计。

算法：
INPUT: 生成算法产生的整个树 $T$ ，参数 $\alpha$
OUPUT: 修剪后的子树 $T_a$
1.计算每个结点的经验熵
2.递归地从树的叶结点向上回缩
回缩前后整体树的损失函数比较，如果回缩前的损失函数大于回缩后，进行剪枝。
3.重复2，直到不能继续为止，得到损失函数最小的子树 $T_a$

python 代码实现

后期加入

总结：决策树是一种简单快速的分类算法，本文不仅把熵相关的概念给整理了一遍，文中信息增益和信息增益比也可以用于其他模型的特征选择，而最后剪枝部分提到的决策树的损失函数是我之前在专门写的《详述机器学习中的损失函数》博客中没有提到的，这里也是一个补充。