决策树（ID3、C4.5）

决策树是什么

• 决策树由结点(node)和有向边(directed edge)组成。
• 结点有两种类型：内部结点(internal node)和叶结点(leaf node)。
• 内部结点表示一个特征或属性。
• 叶结点表示一个类，是无法再拆分的结点。

决策树构造过程

       把决策树看成一个if-then规则的集合，将决策树转换成if-then规则的过程是这样的：

• 由决策树的根结点(root node)到叶结点(leaf node)的每一条路径构建一条规则。
• 路径上内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。
• 决策树的路径或其对应的if-then规则集合具有一个重要的性质：互斥并且完备。这就是说，每一个实例都被一条路径或一条规则所覆盖，而且只被一条路径或一条规则所覆盖。这里所覆盖是指实例的特征与路径上的特征一致或实例满足规则的条件。

       决策树的构造过程一般分为3个部分，分别是特征选择、决策树生产和决策树裁剪。

1. 特征选择

• 表示从众多的特征中选择一个特征作为当前节点分裂的标准，如何选择特征有不同的量化评估方法，从而衍生出不同的决策树，如ID3（通过信息增益选择特征）、C4.5（通过信息增益比选择特征）、CART（通过Gini指数选择特征）等。

       目的（准则）：使用某特征对数据集划分之后，各数据子集的纯度要比划分前的数据集D的纯度高（也就是不确定性要比划分前数据集D的不确定性低）

2. 决策树的生成

       根据选择的特征评估标准，从上至下递归地生成子节点，直到数据集不可分则停止决策树停止生长。这个过程实际上就是使用满足划分准则的特征不断的将数据集划分成纯度更高，不确定性更小的子集的过程。对于当前数据集的每一次划分，都希望根据某个特征划分之后的各个子集的纯度更高，不确定性更小。

3.决策树的裁剪

决策树容易过拟合，一般需要剪枝来缩小树结构规模、缓解过拟合。

ID3算法

• 核心是在决策树各个节点上应用信息增益准则选择特征递归地构建决策树

信息增益

1. 熵

       信息论与概率统计中，熵是表示随机变量不确定性的度量。设$X$X是一个取有限个值得离散随机变量，其概率分布为：
                            
则随机变量X的熵定义为：
                            
期中n是分类的数目。熵越大，随机变量的不确定性就越大。

2. 条件熵
有随机变量（X, Y），其联合概率分布为：
                            

        条件熵$H(Y|X)$H(Y∣X)表示在已知随机变量$X$X的条件下，随机变量$Y$Y的不确定性。随机变量X给定的条件下随机变量$Y$Y的条件熵$H(Y|X)$H(Y∣X)，定义为$X$X给定条件下$Y$Y的条件概率分布的熵对$X$X的数学期望：
                            
        当熵和条件熵中的概率由数据估计得到时（如极大似然估计），所对应的熵与条件熵分别称为经验熵和经验条件熵。

3. 信息增益
        信息增益是相对于特征而言的。所以，特征A对训练数据集D的信息增益$g(D,A)$g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵$H(D|A)$H(D∣A)之差，即：
                            
       设训练数据集为$D$D，$|D|$∣D∣表示样本容量（样本个数）。有K个类

$C_k$Ck​,$k=1,2,..,|C_k|$k=1,2,..,∣Ck​∣为属于类$C_k$Ck​的样本个数，$\sum^{K}_{k=1}{|C_k|=|D|}$∑k=1K​∣Ck​∣=∣D∣.

设特征A有n个不同的取值${\lbrace a_1,a_2,...,a_n\rbrace}${a1​,a2​,...,an​}，根据特征A的取值将D划

分为$n$n个子集$D_1.D_2,...,D_n$D1​.D2​,...,Dn​, $|D_i|$∣Di​∣为子集$D_i$Di​的样本数,

$\sum^{n}_{i=1}{|D_i|=|D|}$∑i=1n​∣Di​∣=∣D∣.记子集$D_i$Di​中属于类$C_k$Ck​的样本集合为$D_{ik}$Dik​,即

$D_{ik}=D_i\bigcap C_k$Dik​=Di​⋂Ck​,$|D_{ik}|$∣Dik​∣为$D_{ik}$Dik​的样本数。

条件熵公式可以写为下式：

理解：选择划分后信息增益大的作为划分特征，说明使用该特征后划分得到的子集纯度越高，即不确定性越小。因此我们总是选择当前使得信息增益最大的特征来划分数据集。

缺点：信息增益偏向取值较多的特征（原因：当特征的取值较多时，根据此特征划分更容易得到纯度更高的子集，因此划分后的熵更低，即不确定性更低，因此信息增益更大）。
       下面来举例说明上式公式的计算。

• 数据（统计学习方法）
  
• 计算
  数据集D有2个类别$C_1（否）和C_2（是）$C1​（否）和C2​（是），$|C_1|=6$∣C1​∣=6,$|C_2|=9$∣C2​∣=9，计算经验熵$H(D)$H(D):
         
  计算各个特征对数据集的增益,四个特征为$A_1,A_2,A_3,A_4$A1​,A2​,A3​,A4​。
  以$A_1$A1​为例进行说明。

       $A_1$A1​有3个不同的取值，特征$A_1$A1​将数据集划分为3个子集，$D_1,D_2,D_3分别是取值为青年、中年、老年的数据集。 $|D_1|=5$∣D1​∣=5,$|D_2|=5$∣D2​∣=5,$|D_3|=5$∣D3​∣=5 , $D_1$D1​ 中类别否的个数为3，类别是的个数为2，即$|D_{11}|=3$∣D11​∣=3，$|D_{12}|=2$∣D12​∣=2，类似地，$|D_{21}|=2$∣D21​∣=2，$|D_{22}|=3$∣D22​∣=3，$|D_{31}|=1$∣D31​∣=1，$|D_{32}|=4$∣D32​∣=4。故$A_1$A1​对数据集$D$D的增益为：

根据上述方法同样可计算其他特征对数据集D的增益。

4. ID3算法流程
输入：训练数据集D，特征集A，阈值ε；

输出：决策树T.

Step1：若D中所有实例属于同一类，则T为单结点树，并将类作为该节点的类标记，返回T；

Step2：若A=Ø，则T为单结点树，并将D中实例数最大的类作为该节点的类标记，返回T；

Step3：否则，计算A中个特征对D的信息增益，选择信息增益最大的特征；

Step4：如果的信息增益小于阈值ε，则T为单节点树，并将D中实例数最大的类作为该节点的类标记，返回T

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

Step6：对第i个子节点，以为训练集，以为特征集合，递归调用Step1~step5，得到子树，返回。

C4.5

        C4.5算法与ID3算法相似，它是在生成决策树过程中采用信息增益比来选择特征。信息增益会偏向取值较多的特征，使用信息增益比可以对这一问题进行校正。
                                                                               
        C4.5算法过程跟ID3算法一样，只是选择特征的方法由信息增益改成信息增益比。