决策树系列之决策树知识点

1、什么是决策树；（decision tree）

决策树是一种树型结构，其中：

    每个内部的结点表示在一个属性的测试；

    每个分支代表一个测试的输出；

    每个叶节点代表一种类别；

决策树是以实例为基础的归纳学习，采取的是自顶向下的递归方法；

其基本思想是，以信息熵为度量构建一颗熵值下降最快的树，到叶子结点处的熵值为0，此时所有的叶节点的熵值都属于同一类。

附上：叶节点的信息熵公式为：

2、决策树算法的整体特点：

最大的特点是，可以自学习，不要求过多的理论知识，只需要对训练实例能进行较好的标注。

属于有监督学习，是从一群无序、无规则（概念）中推理出决策树表示的分类规则。

3、生成算法的整体思路：

决策树的关键在于：

 Step 1、如何评估当前的状态？

 Step 2、如何确定，在当前状态下选择哪个属性为分类依据？

 Step 3、如何评估决策树模型？

 Step 4、如何解决过拟合问题？

在此之前，我们先需要理清相关概念。

4、基本概念：

接下来解释五个概念,分别有信息熵、信息增益、经验条件熵、信息增益率、Gini系数。

4.1、信息熵：Entropy

信息熵就是平均而言发生一个事件我们得到的信息量大小。所以数学上，信息熵其实是信息量的期望。

信息熵越大，则表示目前的数据显式更加混乱的阶段。

更多信息熵的探讨，可以前往：https://www.zhihu.com/question/22178202/answer/49929786

4.2、信息增益：Information Gain

特征A对训练集D的信息增益g(D,A),定义为集合D的经验信息熵H(D)与特征A给定条件下，D的经验条件信息熵H(D|A)之差，即为训练集D和特征A的互信息。

其中，经验熵为集合D中的信息熵，而经验条件信息熵，即在经过A节点属性划分后的信息熵。

在熵的理解那部分提到了，熵可以表示样本集合的不确定性，熵越大，样本的不确定性就越大。因此可以使用划分前后集合熵的差值来衡量使用当前特征对于样本集合D划分效果的好坏。

缺点：信息增益偏向取值较多的特征

原因：当特征的取值较多时，根据此特征划分更容易得到纯度更高的子集，因此划分之后的熵更低，由于划分前的熵是一定的，因此信息增益更大，因此信息增益比较 偏向取值较多的特征。

4.3、经验条件信息熵H(D|A)

  推导的过程中用到了条件概率公式：

  整体的结论为，H(D|A)等于在该特征n个不同特征值的概率乘以该特征值的信息熵之乘积的汇总。

其中，

  设训练样本数据集为D，|D|表示样本数量；

  设有K个类，Ck, k=1,2,3..K, |Ck|位属于类Ck的样本个数，有

  设特征A有n个不同的取值，{a1,a2,..an}，根据特征A的取值，将D划分为n个子集，D1,D2,..,Dn,设|Di|为Di的样本个数，有

  记子集Di中属于类Ck的样本集合为Dik, |Dik|为Dik的样本个数

4.4 信息增益率 Information Gain Rate

信息增益比 = 惩罚参数 * 信息增益

注意：其中的HA(D)，对于样本集合D，将当前特征A作为随机变量（取值是特征A的各个特征值），求得的经验熵。

其中：

信息增益比本质： 是在信息增益的基础之上乘上一个惩罚参数。特征个数较多时，惩罚参数较小；特征个数较少时，惩罚参数较大。通俗理解,特征个数越多越分散，信息熵越大，惩罚参数越小。

缺点：信息增益比偏向取值较少的特征

原因：  当特征取值较少时HA(D)的值较小，因此其倒数较大，因而信息增益比较大。因而偏向取值较少的特征。

用途：基于以上缺点，并不是直接选择信息增益率最大的特征，而是现在候选特征中找出信息增益高于平均水平的特征，然后在这些特征中再选择信息增益率最高的特征。

4.5 基尼指数 Gini Index,基尼不纯度

表示在样本集合中一个随机选中的样本被分错的概率.

Gini指数越小表示集合中被选中的样本被分错的概率越小，也就是说集合的纯度越高，反之，集合越不纯

4.6 纯结点

若某结点上，只有一种类型，称该节点为纯结点。熵值为0。

4.7 均结点

若某结点上，所有类型占比相同，则成为均结点。熵值最大。

5、决策树的学习算法：

一个属性的信息增益（或者信息增益率、基尼系数的降低值）越大，表明属性对于样本的熵减少能力更强，这个属性将数据有不确定性变为确定性的能力越强。

5.1 ID3算法：使用信息增益（互信息）g(D,A)进行特征选择

选择标准：选择出G（D,A）最大的特征；

缺点：信息增益偏向取值较多的特征

原因：当特征的取值较多时，根据此特征划分更容易得到纯度更高的子集，因此划分之后的熵更低，由于划分前的熵是一定的，因此信息增益更大，因此信息增益比较 偏向取值较多的特征。（假设前提是划分的越多，对应的熵减越大）

5.2 C4.5算法：使用信息增益率

选择标准：选择信息增益率最大的特征

缺点：信息增益比偏向取值较少的特征

原因：  当特征取值较少时HA(D)的值较小，因此其倒数较大，因而信息增益比较大。因而偏向取值较少的特征。

用途：基于以上缺点，并不是直接选择信息增益率最大的特征，而是现在候选特征中找出信息增益高于平均水平的特征，然后在这些特征中再选择信息增益率最高的特征。

5.3 CART算法：使用Gini系数

步骤：1、选择特征；2、选择特征划分点；（都是选择Gini系数最小的）

CART是个二叉树，也就是当使用某个特征划分样本集合只有两个集合：1. 等于给定的特征值 的样本集合D₁ ， 2 不等于给定的特征值 的样本集合D_2。

6、决策树的评价方法：

评价方法1： 树结构：将所有的叶节点的熵求和。

评判标准：若该值越小，则对样本的分类越准确。

评判方法2：是否存在过拟合

过拟合的意思是，决策树对训练属于很好的分类的能力，但是对于未知的测试集未必有很好的分类能力，繁华能力差。

7、如何避免决策树的过拟合情况：

1、剪枝；2、随机森林；

7.1 剪枝

三种决策树的剪枝过程算法相同，只是评估标准不同；

7.1.1 剪枝的整体思路：

1、通过完全树T0开始，剪枝部分节点得到T1,再次剪枝部分节点得到T2，直到仅剩下数根节点Tk;

2、在验证数据集上对k个树分别评价，选择损失函数最小的树Ta;

7.1.2 剪枝系数

由于原来的损失函数会倾向于生成更深的树，所以损失函数需要重新修正：

其中|T|为叶子的复杂度

剪枝系数alpha的确定：

对alpha有两种极限考虑：

若alpha=0，未剪枝的决策树损失最小；

若alpha=正无穷，单结点的决策树损失最小；

假定当前对以r为根的子树剪枝，剪枝后，只保留r本身而删掉所有的子结点。

以r为根的子树：

剪枝之后的损失函数：

剪枝之前的损失函数：

令两者相等，得到剪枝系数

7.1.3 剪枝详细步骤

5、使用验证样本集选择最优子树。

从最小的剪枝系数开始，能最大保留树本身的结构。

备注：使用验证集评价的时候，公式为：

QA:为什么没有选择加入正则化系数alpha？

主要是因为正则化系数alpha不确定，而且建模后对样本的熵减已经是对模型最好的评估。

Q&A:

若有发现以上博客有问题的话，欢迎大家指出，邮箱：314923628@qq.com ,欢迎交流。

最后

以上就是执着心锁为你收集整理的决策树系列之决策树知识点的全部内容，希望文章能够帮你解决决策树系列之决策树知识点所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。