一、决策树

1.1原理

决策树:从训练数据中学习得出一个树状结构的模型。

• 决策树属于判别模型。
• 决策树是一种树状结构，通过做出一系列决策（选择)来对数据进行划分，这类似于针对一系列问题进行选择。
• 决策树的决策过程就是从根节点开始，测试待分类项中对应的特征属性，并按照其值选择输出分支，直到叶子节点，将叶子节点的存放的类别作为决策结果。

就相当于这种树状模型。比如说女生找对象，首先看长相，家庭背景，等等以此往下。

1. 决策树算法是一种归纳分类算法，它通过对训练集的学习，挖掘出有用的规则，用于对新数据进行预测。
2. 决策树算法属于监督学习方法。
3. 决策树归纳的基本算法是贪心算法，自顶向下来构建决策树。
4. 贪心算法:在每一步选择中都采取在当前状态下最好/优的选择。
5. 在决策树的生成过程中，分割方法即属性选择的度量是关键。

 1.2决策树的特点

优点:

• 推理过程容易理解，计算简单，可解释性强。
• 比较适合处理有缺失属性的样本。
• 可自动忽略目标变量没有贡献的属性变量，也为判断属性变量的重要性，减少变量的数目提供参考。

缺点:

• 容易造成过拟合，需要采用剪枝操作。
• 忽略了数据之间的相关性。
• 对于各类别样本数量不一致的数据，信息增益会偏向于那些更多数值的特征。

 1.3决策树的三种基本类型

             建立决策树的关键，即当前状态下选择哪个属性作为分类依据。根据不同的目标函数，建立决策树主要有以下三个算法：ID3(Iterative Dichotomiser)、C4.5、CART(Classification And Regression Tree)。

 二、ID3（信息增益）算法

       ID3算法最早是由罗斯昆(J.Ross Quinlan)于1975年提出的一种决策树构建算法，算法的核心是“信息嫡”，期望信息越小，信息嫡越大，样本纯度越低。

• ID3算法是以信息论为基础，以信息增益为衡量标准，从而实现对数据的归纳分类。
• ID3算法计算每个属性的信息增益，并选取具有最高增益的属性作为给定的测试属性。 

 其大致步骤：

1.  初始化特征集合和数据集合;
2. 计算数据集合信息嫡和所有特征的条件嫡，选择信息增益最大的特征作为当前决策节点;
3. 更新数据集合和特征集合（(删除上一步使用的特征，并按照特征值来划分不同分支的数据集合);
4. 重复2，3两步，若子集值包含单一特征，则为分支叶子节点。

 2.1信息熵

“信息熵”是度量样本集合纯度最常用的一种指标。

 按年龄划分：

 2.2条件熵

条件熵 H(X|Y) 表示在已知随机变量Y的条件下，随机变量 X 的不确定性。

 2.3信息增益详解

信息增益 = 信息熵 - 条件熵

       有几个公式不能弄混，很相似，但完全不同。这个信息熵是针对类别算出。而那个条件熵，是针对一个条件进行计算，步骤是先算出在该条件下的信息熵，然后按照公式  上图是按照老年属性算的条件熵，所以最后算出的是老年的信息增益。基本前面有样例，可对比查看。同理，我也可以按照年龄的信息熵来计算信息增益，就是一个不同属性划分的问题。西瓜书上那个p78页就是根据每一个属性划分类别，判断好坏瓜。

3. ID3算法缺点

• ID3没有剪枝策略，容易过拟合;
• 信息增益准则对可取值数目较多的特征有所偏好，类似“编号”的特征其信息增益接近于1;
• 只能用于处理离散分布的特征;
• 没有考虑缺失值。

 三、C4.5算法

 针对于ID3的算法缺点，进行改进，C4.5算法。

C4.5算法是Ross 对ID3算法的改进

• 用信息增益率来选择属性。ID3选择属性用的是子树的信息增益，而C4.5用的是信息增益率。
• 在决策树构造过程中进行剪枝。
• 对非离散数据也能处理。
• 能够对不完整数据进行处理。

1.信息增益率 

信息增益率的定义是。

 把每一个特征都计算出来信息增益率，选出最大的信息增益率，进行分列。

2.剪枝

因为决策树会出现过拟合的原因：

• 为了尽可能正确分类训练样本，节点的划分过程会不断重复直到不能再分，这样就可能对训练样本学习的“太好”了，把训练样本的一些特点当做所有数据都具有的一般性质，从而导致过拟合。
• 通过剪枝处理去掉一些分支来降低过拟合的风险。
• 剪枝的基本策略有“预剪枝”(prepruning）和“后剪枝”(post-pruning)

 2.1 预剪枝

         预剪枝不仅可以降低过拟合的风险而且还可以减少训练时间，但另一方面它是基于“贪心”策略，会带来欠拟合风险。

针对数据集：

 预剪枝后：

 看到1->4是划分后比划分前更高了。所以可以继续划分。

         讲述一下预剪枝过程，对于上图的序号2 .用表4.2的验证集对这个单节点决策树进行评估，则编号为{4，5，8}的样例被分类正确，另外四例分类错误，于是验证集是3/7 *100%=42.9%。预剪枝是从根结点往下来，首先从脐部划分，上图中的序号2，3，4，分别包含编号为{1，2，3，14}，{6，7，15，17}，{10，16}的训练样例，因此这三个节点分别被标记为叶结点“好瓜”，“好瓜”，“坏瓜”。此时，验证集中编号为{4，5，8，11，12}的样例被分类正确，其中4，5，8是好瓜，11，12是坏瓜。验证集精度为5/7*100%=71.4%>42.9%，于是能够进行往下划分。

        下一级划分的时候，就要按71.4%来划分，首先从左边划分属性是色泽，对于验证集来看{5}的色泽是浅白，将是从分类正确划分为错误，分类正确的还有{4，5，11，12},于是4/7*100%=57.1%，小于71.4%。所以不能划分。

       同理，根蒂，将其改成好瓜，验证集还是71.4%，禁止划分。

       序号4就不行划分了。

2.2后剪枝

• 在已经生成的决策树上进行剪枝,从而得到简化版的剪枝决策树。
• 后剪枝决策树通常比预剪枝决策树保留了更多的分支。一般情况下，后剪枝的欠拟合风险更小，泛化性能往往优于预剪枝决策树。

        后剪枝先从训练集生成一课完整决策树，例如基于表4.2的数据训练集得到后剪枝前的决策树。易知，该决策树的验证集精度为42.9%。

         后剪枝是从后往前，首先看序号6 纹理，如果将其替换调，就会变成叶结点，替换后的叶节点包含编号为{7，15}的训练样本，于是将叶结点的类别标记为“好瓜”，此时决策树的验证集精度提升到57.1%（9号加入到好瓜队列，所以4/7*100%=57.1%），能够进行剪枝。

        序号5 ，如果将其替换调，就会变成叶结点，替换后的叶节点包含编号为{6，7，14，15}的训练样本，于是将叶结点的类别标记为“好瓜”，此时决策树的验证集精度提升到57.1%（验证集的9号加入到好瓜队列，所以4/7*100%=57.1%），

       序号2，如果将其替换调，就会变成叶结点，替换后的叶节点包含编号为{1，2，3，14}的训练样本，于是将叶结点的类别标记为“好瓜”，此时决策树的验证集精度提升到71.4%（在序号6剪枝的基础上，把13号加入好瓜队列，验证集精度为5/7*100%=71.4%）超过了57.1%（在序号6剪枝后的基础上），进行剪枝。

       序号3 ，如果将其替换调，就会变成叶结点，将叶结点的类别标记为“好瓜”，此时决策树的验证集精度未发生变化（在序号2，5剪枝的基础上5/7*100%=71.4%）

就变成了后面的结果：

 后剪枝后：

 3.缺点

• 剪枝策略可以再优化;
• C4.5用的是多叉树，用二叉树效率更高;
• C4.5只能用于分类;
• C4.5使用的嫡模型拥有大量耗时的对数运算，连续值还有排序运算;
• C4.5在构造树的过程中，对数值属性值需要按照其大小进行排序，从中选择一个分割点，所以只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时，程序无法运行。

四、CART算法 

因为 C4.5算法是基于多叉树的，所以说效率是比较低的。