机器学习 3.2 决策树模型 学习笔记(待补)

3.2.1 模型结构

决策树模型将思维过程抽象为一系列对已知数据属性的判别和决策过程，使用树结构表示和判别的逻辑和关系和一系列的判别过程，并通过叶节点表示判别或决策结果。

如上图所示，一颗树上的叶节点全部表示最终结果，而非叶节点表示每个决策的点，也就是对样本某一属性的判别。不难发现决策树是一个外向树模型，每个内部节点都将直接或间接的影响决策的最终结果。从根节点到某一叶节点的的路径称为测试序列。

我们可以将决策树模型的构造过程描述为如下的过程：

1. 根据某种分类规则得到最优的划分特征，计算最优特征子函数，并创建特征的划分节点，按照划分节点将数据集划分为若干部分子数据集；
2. 在子数据集重复使用判别规则，构造出新的节点，作为树的新分支；
3. 在生成子数据集时，注意检查数据是否均属于同一类别或者再也没有用于数据划分的属性；如果仍能继续分类，则递归执行上述过程；否则将当前节点作为叶节点，结束该分支的构造过程。

3.2.2 判别标准

构造决策树的关键在于合理选择其颞部节点所对应的样本属性，使得节点所对应样本子集中的样本尽可能多属于同一类别，即具有尽可能高的纯度。

决策树模型的判别标准需要满足以下两点：

1. 如果节点对应数据子集中的样本基本属于同一个类别，则不用再对节点的数据子集做进一步划分，否则就要对该节点的数据子集做进一步划分，生成新的判别标准；
2. 如果新的判别标准能够基本上把节点上不同类别的数据分离开，使得每个子节点都是类别比较单一的数据，那么该判别标准就是一个好规则，否则需要重新选取判别标准。

如何量化决策树的判别属性选择标准？

我们一般使用信息熵(熵)对样本集合的纯度进行定量分析。信息熵时信息论中定量描述随机变量不确定度的的一类度量指标，主要用于衡量数据取值的无序程度，熵值越大则表明数据取值越杂乱无序。

假设$\xi$为具有$n$个可能取值$\{s_1,s_2,\dots ,s_n\}$的离散型随机变量，概率分布为$P(\xi =s_i)=p_i$，则其信息熵定义为：
$$H(\xi )=-\sum _{i=1}^n{p}_i{\log }_2{p}_i$$
当$H(\xi )$的值越大时，表明随机变量$\xi$的不确定性就越大。

对于任意给定的两个离散型随机变量$\xi ,\eta$，其联合概率分布为：
$$P(\xi =s_i,\eta =t_i)=p_{ij},i=1,2,\dots ,n;j=1,2,\dots ,m$$
则$\eta$关于$\xi$的信息熵$H(\eta |\xi )$定量表示在已知随机变量$\xi$取值的条件下随机变量$\eta$取值的不确定性，计算公式为随机便变量$\eta$基于条件概率分布的熵对随机变量$\xi$的数学期望，即有：
$$H(\eta |\xi )=\sum _{i=1}^n{p}_{i}H(\eta |\xi =s_i)$$
其中，$p_i=P(\xi =s_i),i=1,2,\dots ,n$。

对于任意给定的训练样本集合$D$，可将集合$D$看作时一个关于样本标签取值状态的随机变量，由此可根据熵的本质内涵来定义一个量化指标$H(D)$进而度量$D$中样本类型的纯度，通常称$H(D)$为经验熵。$H(D)$的值越大，则表明$D$中所包含的样本标签取值越杂乱；反之越小则表明越样本标签取值越纯净。$H(D)$的具体计算公式如下：
$$H(D)=-\sum _{k=1}^n\frac{|C_k|}{|D|}{\log }_2\frac{|C_k|}{|D|}$$
其中，$n$表示样本标签值的取值状态数；$C_k$表示训练样本集$D$中所有标注值为第$k$个取值的训练样本组成的集合，$|D|$和$|C_k|$分别表示集合$D$和$C_k$的基数。

对于训练样本集$D$上的任意属性$A$，可在经验熵$H(D)$的基础上进一步定义一个量化指标$H(D|A)$来度量集合$D$中样本在以属性$A$为标准划分后的纯度，通常乘$H(D|A)$为集合$D$关于属性$A$的经验条件熵。$H(D|A)$的计算公式如下：
$$H(D|A)=\sum _{i=1}^m\frac{|D_i|}{|D|}H(D_i)$$
其中，$m$表示属性$A$的取值状态数；$D_i$表示集合$D$在以属性$A$为标准划分后产生的子集，即为$D$中所有属性$A$取第$i$个状态的样本组成的样本集合。

由经验熵$H(D|A)$的定义可知，其值越小则样本集合$D$的纯度越高，可在经验熵的基础上进一步计算每个属性作为划分指标后对数据集合经验熵变化的影响，即信息增益。信息增益度量的是已知随机变量$\xi$的信息使得随机变量$\eta$的信息不确定性减少的程度。

对于任意给定的训练样本数据集$D$及上的某个属性$A$，属性$A$关于集合$D$的信息增益$G(D,A)$定义为经验熵$H(D)$与条件经验熵$H(D|A)$之差，即有：
$$G(D,A)=H(D)-H(D|A)$$
显然，对于属性$A$关于集合$D$的信息增益$G(D,A)$，如果其值越大则表示使用属性$A$划分后的样本集合纯度越高，使得决策树模型具有更强的分类能力，故可将$G(D,A)$作为标准选择合适的判别属性，通过递归计算样本属性的信息增益以实现对决策树的构造。

使用信息增益指标作为划分属性选择标准的时候，选择结果通常会偏向取值状态数目加多的属性。为了解决这个问题，最简单的思路是对信息增益进行归一化，信息增益率便可以看作对信息增益进行归一化的一个度量标准。信息增益率在信息增益的基础上引入一个增益因子，消除属性取值数目变化对计算结果的干扰。具体来说，对于给任意给定的训练样本的数据集合$D$及其上的某个属性$A$，属性$A$关于集合$D$的信息增益率$G_r(D,A)$定义为：
$$G_r(D,A)=\frac{G(D,A)}{Q(A)}$$
其中$Q(A)$为校正因子，由下式计算：
$$Q(A)=-\sum _{i=1}^m\frac{|D_i|}{|D|}{\log }_2\frac{|D_i|}{|D|}$$
显然，属性$A$的取值状态数$m$值越大，则$Q(A)$值也越大，由此可以减少信息增益的不良偏好对决策树某型结构所带来的影响。

对于决策树模型，还可以用基尼指数作为划分标准来选择最优属性。与上的概念类似，基尼指数可以用来度量数据集的纯度。对于任意给定的一个$m$分类，假设样本点属于第$k$类的概率为$p_k$，则关于这个概率分布$p$的基尼指数可以定义为
$$Gini(p)=\sum _{k=1}^m{p}_k(1-p_k)$$
即有：
$$Gini(p)=1-\sum _{k=1}^m{p}_k^2$$
相应的，对于任意给定的样本集合$D$，可将其基尼指数定义为：
$$Gini(D)=1-\sum _{k=1}^m(\frac{|C_k|}{|D|}{)}^2$$
其中，$C_k$是$D$中属于第$k$类的样本子集；$m$是类别方案数。

样本集合$D$的基尼指数表示在$D$中随机选中一个样本被错误分类的概率。显然，$Gini(D)$的值越小，数据集$D$中样本的纯度越高，或者说$D$中样本种类一致性越高。

若样本集合$D$根据属性$A$是否取某一可能值$a$而被分割为$D_1$和$D_2$两部分，即
$$D_1=\{(X,y)\in D|A(X)=a\},D_2=D-D_1$$
则在属性$A$为划分属性的条件下，集合$D$的基尼指数可以定义为：
$$Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)$$

3.2.3 模型构造（占坑）

基于上述判断标准，主要有三种相应的决策树生成算法

• 基于信息增益：ID3算法
• 基于信息增益率：C4.5算法
• 基于基尼指数：CART算法

待补