数据挖掘学习笔记--决策树（一）
博客整理自 《统计学习方法》李航著
一、决策树关键问题
1.选择特征
2.树的生长和终止
3.如何剪枝
二、决策树基本概念
基尼指数(Gini index):
假设有K个类，样本点属于第k类的概率为p k：
（式1）****
基于给定的数据集D，在类别总数中K表示不同类别数量，在对应的第k个类别中包含有C_k个样本子集的情况下，则该情况下的基尼指数值为：
（式2）****
在特征A的条件下，集合D的基尼指数为：
（式3）****
信息增益(information gain)：
随机变量X的熵(entropy)：
**
（式4）**
条件熵(conditional entropy)：
**
（式5）**
信息增益的计算（训练数据集D和特征A）：
** a.计算数据集D的经验熵H(D)**
**
（式6）
**
** b.计算特征A 对数据集D的经验条件熵H(D|A)**
**
（式7）**
** c.计算信息增益**
**
（式8）
**
其中，在数据集中包含m个样本的数据集D被定义为其容量；类别共有K种类型，并且每个类别类型的数量由其对应符号表示；属性A具有n种可能的不同取值；基于这些属性的不同取值将整个数据集划分为若干子集；在每个子集中与特定类别相关的部分被单独标识并记录其数量信息。
信息增益比(information gain ratio): 旨在纠正那些倾向于选择取值范围较大的属性的信息增益
__特征A对训练数据集D的信息增益比:
**
（式9）**
其中，n是特征A取值的个数：
**
（式10）**
**
**
**
**
以一组贷款申请样本数据表作为例子，计算信息增益：
贷款申请样本数据表 | ID| 年龄| 类别 |
| --- | --- | --- |
|---|---|---|
| 2 | 青年 | 否 |
| 3 | 青年 | 是 |
| 4 | 青年 | 是 |
| 5 | 青年 | 否 |
| 6 | 中年 | 否 |
| 7 | 中年 | 否 |
| 8 | 中年 | 是 |
| 9 | 中年 | 是 |
| 10 | 中年 | 是 |
| 11 | 老年 | 是 |
| 12 | 老年 | 是 |
| 13 | 老年 | 是 |
| 14 | 老年 | 是 |
| 15 | 老年 | 否 |
计算经验熵H(D) = -6/15log2(6/15) - 9/15log2(9/15)=0.971;
以年龄作为特征H(D|age) =5/15*[-2/5log2(2/5)-3/5log2(3/5)] + 5/15*[-2/5log2(2/5)-3/5log2(3/5)]+5/15*[-4/5log2(4/5)-1/5log2(1/5)] =0.888;
以年龄为划分特征的信息增益g(D,age) = H(D)-H(D|age) = 0.971-0.888=0.083.
__
三、著名的决策树算法
1.ID3：核心是选择信息增益作为特征选择标准
输入：训练数据集D，特征集A，阈值e;
输出：决策树T.
如果D中的每一个实例都属于同一个类别Ck，则将T设为单节点树，并将其标记为类别Ck之后返回该树结构T；
(2)若A=
，则T为单结点树，并将D中实例数最大的类Ck作为该结点的类标记，返回T；
(3)否则，计算A中各特征对D 的信息增益，选择信息增益最大的特征Ag ；
当Ag的信息增益低于预设阈值e时，则设定决策树模型T为单结点树；随后，在数据集D中实例数量最多的类别Ck被确定为该分类任务的目标类别，并输出生成的决策树模型T。
否则的话，请考虑对于Ag的所有可能取值ai，在数据集D上按Ag=ai进行划分。对于每个划分后的子集Di来说，将其实例数最多的类别作为标记类别，并相应地建立子节点。
由结点及其子结点构成树T，返回T；
对第i个子节点进行处理，并基于Di作为训练数据集，在使用A-{Ag}作为特征集合的前提下，按照步骤（1）至（5）进行递归调用以生成相应的子树Ti，并最终返回生成的子树Ti
2.C4.5：使用信息增益比来选择特征
输入：训练数据集D，特征集A，阈值e;
输出：决策树T.
如果数据集D中的所有实例都属于同一个类别Ck，则生成一棵仅包含单个节点的树，并将其类别标记设为Ck。
(2)若A=
，则T为单结点树，并将D中实例数最大的类Ck作为该结点的类标记，返回T；
(3)否则，计算A中各特征对D 的信息增益比，选择信息增益比最大的特征Ag ；
当Ag的信息增益低于阈值e时，则设T为单一节点树，并将实例数量最多的类别Ck作为该类的标记类别。
否则的话,对于Ag的所有可能取值 ai ,根据 Ag=ai 对数据集D进行划分.对于每个Di(即每个子集),将Di中的实例数量最多的类别设为标记类别,并生成相应的子节点.
由结点及其子结点构成树T，返回T；
处理第i个子节点时，请基于Di作为训练数据集，并使用A−Ag作为特征集合。通过递归调用步骤（1）至（5），生成相应的子树结构Ti，并将其返回。
3.CART分类树：用基尼指数选择最优特征
输入：训练数据集D，停止计算的条件；
输出：CART决策树
基于训练数据集X, 自根节点出发按照层次逐步对每个节点依次执行以下操作来生成一棵二叉决策树模型：
给定节点及其相关的训练数据集D，在评估现有特征在该数据集上的基尼指数时发现某些特性具有显著差异性。对于每个特征变量A，在其可能取值中的每一个a上（例如参考式（3）），将训练数据集D划分为两个子集D₁和D₂，并计算当特征A取特定值a时（如式（3）所示）的数据纯度
(2)对于每一个可选的特征A及其所有的可能切分点a，在这些组合中计算基尼指数，并选出基尼指数最低（即最接近于零）的那个组合作为最佳特征及其最佳切分点。基于选定的最佳特征及其对应的最佳切分值将其划分为两个子节点，并将训练数据按照该特征分配至这两个子节点中去
(3)对两个子结点递归地调用(1),(2)，直至满足停止条件
(4)生成CART决策树
算法停止计算的条件是该节点内的样本数量低于预先设定的标准；或者该数据集的Gini系数低于预先设定的标准；或者缺乏进一步的区分特征。