决策树算法

   朴素贝叶斯要求特征相互独立，只能处理文本这种，更好的分类要用到决策树，决策树后面还有更更好的随机森林属于集成学习 可以解决很多的事情

文章目录

学完决策树算法，您应该掌握

  • 掌握决策树实现过程
  • 知道信息熵的公式以及作用
  • 知道信息增益的作用
  • 知道信息增益率的作用
  • 知道基尼指数则作用
  • 知道id3,c4.5，cart算法的区别
  • 了解cart剪枝的作用
  • 应用DecisionTreeClassifier实现决策树分类

二、 决策树分类原理重点


构建决策树：寻找对目标值影响最大的特征以及这个特征分支的方式（有三个办法解决：信息增益、信息增益率、基尼值增益）

信息增益 基于概率计算信息熵
信息增益率 基于概率计算信息熵
基尼值增益 基于概率计算基尼值

1 熵

1.1 概念

物理学上，熵 Entropy 是“混乱”程度的量度。

系统越有序，熵值越低；系统越混乱或者分散，熵值越高。

  • 信息理论：

1、从信息的完整性上进行的描述:

当系统的有序状态一致时，**数据越集中的地方熵值越小，数据越分散的地方熵值越大。

2、从信息的有序性上进行的描述:

当数据量一致时，系统越有序，熵值越低；系统越混乱或者分散，熵值越高。

1948年香农提出了信息熵（Entropy）的概念。

假如事件A的分类划分是（A1,A2,…,An），每部分发生的概率是(p1,p2,…,pn)，那信息熵定义为公式如下：（log是以2为底，lg是以10为底）


比如有ABCD四个球队，预测最后哪个队是冠军
最复杂的情况：每个球队实力相当的时候最难判断哦
最混乱

A B C D
1/4 1/4 1/4 1/4

最有序

A B C D
1 0 0 0

计算熵的时候，最混乱的那个熵最大，最有序的熵最小
如果从离散来说，越离散的熵越大，越密集的熵越小

再来算一个概率的情况

A B C D
1/8 1/8 1/2 1/4


总结：要记住熵的公式

信息熵（Entropy）的概念。
假如事件A的分类划分是（A1,A2,…,An），每部分发生的概率是(p1,p2,…,pn)，那信息熵定义为公式如下：（log是以2为底，lg是以10为底）

1.2 案例

课堂案例1：
如果一颗骰子的六个面都是1 ，投掷它不会给你带来任何新信息，因为你知道它的结果肯定是1，它的信息熵为？？

答案：
 - log(1) = 0 。
课堂案例2：
假设我们没有看世界杯的比赛，但是想知道哪支球队会是冠军，
我们只能猜测某支球队是或不是冠军，然后观众用对或不对来回答，
我们想要猜测次数尽可能少，你会用什么方法？

答案：
二分法：
假如有 16 支球队，分别编号，先问是否在 1-8 之间，如果是就继续问是否在 1-4 之间，
以此类推，直到最后判断出冠军球队是哪只。
如果球队数量是 16，我们需要问 4 次来得到最后的答案。那么世界冠军这条消息的信息熵就是 4。

如果有32个球队，准确的信息量应该是： 
H = -（p1 * logp1 + p2 * logp2 + ... + p32 * logp32），
其中 p1, ..., p32 分别是这 32 支球队夺冠的概率。
当每支球队夺冠概率相等都是 1/32 的时：H = -（32 * 1/32 * log1/32） = 5
每个事件概率相同时，熵最大，这件事越不确定。
随堂练习：
篮球比赛里，有4个球队 {A,B,C,D} ，获胜概率分别为{1/2, 1/4, 1/8, 1/8}
求H(X)
答案：
H(X) = 1\2log(2)+1\4log(4)+1\8log(8)+1\8log(8)=(1\2+1\2+3\8+3\8)log(2)=7\4bits
tips:
    以2为底，记做lb,单位bit
    以e为底，记做ln,单位nat

2 决策树的划分依据一------信息增益

2.1 概念

信息增益：以某特征划分数据集前后的熵的差值。熵可以表示样本集合的不确定性，熵越大，样本的不确定性就越大。因此可以使用划分前后集合熵的差值来衡量使用当前特征对于样本集合D划分效果的好坏。

信息增益 = entroy(前) - entroy(后)

  • 定义与公式

特征A对训练数据集D的信息增益g(D,A),定义为集合D的信息熵H(D)与特征A给定条件下D的信息条件熵H(D|A)之差，即公式为：

公式的详细解释：

注：信息增益表示得知特征X的信息而使得类Y的信息熵减少的程度

2.2 案例：

如下左图，第一列为论坛号码，第二列为性别，第三列为活跃度，最后一列用户是否流失。

我们要解决一个问题：性别和活跃度两个特征，哪个对用户流失影响更大？

通过计算信息增益可以解决这个问题，统计上右表信息

其中Positive为正样本（已流失），Negative为负样本（未流失），下面的数值为不同划分下对应的人数。

可得到三个熵：

整体熵：

性别熵：

性别信息增益：

活跃度熵：


活跃度信息增益：

活跃度的信息增益比性别的信息增益大，也就是说，活跃度对用户流失的影响比性别大。

在做特征选择或者数据分析的时候，我们应该重点考察活跃度这个指标。


3 决策树的划分依据二----信息增益率

改良信息增益
信息增益倾向于选择划分数量多的。这样不好，我们用信息增益率
**增益率：**增益比率度量是用前面的增益度量Gain(S，A)和所分离信息度量SplitInformation(如上例的性别，活跃度等)的比值来共同定义的。
分子是信息增益

分母是计算每一个分类的熵，解决掉分类多信息增益大的问题

4 决策树的划分依据三——基尼值和基尼指数

4.1 概念

**基尼值Gini（D）：**从数据集D中随机抽取两个样本，其类别标记不一致的概率。故，Gini（D）值越小，数据集D的纯度越高。
、
1-两个相同样本的概率

基尼值越小，数据越纯



**基尼指数Gini_index（D）：**一般，选择使划分后基尼系数最小的属性作为最优化分属性。

4.2 案例

请根据下图列表，按照基尼指数的划分依据，做出决策树。


基尼值判别的时候，我们只能选择二叉树，此时就变成了很复杂的情况，就比如婚姻状况来说就有三种分法



年龄划分成两个的话有更多的分法，我们按从小到大排列，然后后面根据基尼值来算

贷款和有房已经是两个的



接下来就根据基尼值增益来计算房子及贷款，年收入，婚姻这四个特征对于目标值的影响

房子及贷款的基尼值增益

注意房子和贷款是在一起的情况

贷款基尼值

然后再看是不是因为房子贷款的

那么算一下划分后各个节点的基尼值

所以按照是否有房来划分贷款的话，基尼值增益为

1，对数据集非类标号属性{是否有房，婚姻状况，年收入}分别计算它们的Gini系数增益，取Gini系数增益值最大的属性作为决策树的根节点属性。

2，根节点的Gini系数为：

3，当根据是否有房来进行划分时，Gini系数增益计算过程为：



同样的方法计算婚姻状况
4，若按婚姻状况属性来划分，属性婚姻状况有三个可能的取值{married，single，divorced}，分别计算划分后的Gini系数增益。

{married} | {single,divorced}

{single} | {married,divorced}

{divorced} | {single,married}

分组为{married} | {single,divorced}时：

当分组为{single} | {married,divorced}时：

当分组为{divorced} | {single,married}时：


对比计算结果，根据婚姻状况属性来划分根节点时取Gini系数增益最大的分组作为划分结果，即:{married} | {single,divorced}

5，同理可得年收入Gini：

对于年收入属性为数值型属性，首先需要对数据按升序排序，然后从小到大依次用相邻值的中间值作为分隔将样本划分为两组。例如当面对年收入为60和70这两个值时，我们算得其中间值为65。以中间值65作为分割点求出Gini系数增益。


0.42是划分之前按照是否拖欠贷款的根节点算的，还没有算子节点

后面1/10*0是小于65的基尼值，9/10（1-（1/9）2-(3/9)2）是大于65的基尼值

最大化增益等价于最小化子女结点的不纯性度量（Gini系数）的加权平均值，现在我们希望最大化Gini系数的增益。根据计算知道，三个属性划分根节点的增益最大的有两个：年收入属性和婚姻状况，他们的增益都为0.12。此时，选取首先出现的属性作为第一次划分。

6，接下来，采用同样的方法，分别计算剩下属性，其中根节点的Gini系数为（此时是否拖欠贷款的各有3个records）

7，对于是否有房属性，可得：

8，对于年收入属性则有：


4.3 小结

一，决策树构建的基本步骤如下：

  1. 开始将所有记录看作一个节点重要，记录=样本
  2. 遍历每个变量的每一种分割方式，找到最好的分割点依据三个指标（三选一找到最优的）
  3. 分割成两个节点N1和N2
  4. 对N1和N2分别继续执行2-3步，直到每个节点足够“纯”为止。分的两个节点要分别执行

目的是每个节点足够纯，要把不纯的放在最上面然后往下分，这句话很【重要】哦，剪枝可以判断足够纯

二，决策树的变量可以有两种：

  1. 数字型（Numeric）：变量类型是整数或浮点数，如前面例子中的“年收入”。用“>=”，“>”,“<”或“<=”作为分割条件（排序后，利用已有的分割情况，可以优化分割算法的时间复杂度）。
  2. 名称型（Nominal）：类似编程语言中的枚举类型，变量只能从有限的选项中选取，比如前面例子中的“婚姻情况”，只能是“单身”，“已婚”或“离婚”，使用“=”来分割。

三，如何评估分割点的好坏？

如果一个分割点可以将当前的所有节点分为两类，使得每一类都很“纯”，也就是同一类的记录较多，那么就是一个好分割点。

比如上面的例子，“拥有房产”，可以将记录分成了两类，“是”的节点全部都可以偿还债务，非常“纯”；“否”的节点，可以偿还贷款和无法偿还贷款的人都有，不是很“纯”，但是两个节点加起来的纯度之和与原始节点的纯度之差最大，所以按照这种方法分割。构建决策树采用贪心算法，只考虑当前纯度差最大的情况作为分割点。

5 总结:常见决策树类型比较划分方式


5.1 ID3 算法

存在的缺点

(1) ID3算法在选择根节点和各内部节点中的分支属性时，采用信息增益作为评价标准。信息增益的缺点是倾向于选择取值较多的属性，在有些情况下这类属性可能不会提供太多有价值的信息.

(2) ID3算法只能对描述属性为离散型属性的数据集构造决策树。

5.2 C4.5算法

做出的改进(为什么使用C4.5要好)

(1) 用信息增益率来选择属性

(2) 可以处理连续数值型属性

(3)采用了一种后剪枝方法

(4)对于缺失值的处理

C4.5算法的优缺点

优点：

产生的分类规则易于理解，准确率较高。

缺点：

在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。

此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。

5.3 CART算法

决策树复杂度很大容易过拟合，所以我们要cart剪枝
CART算法相比C4.5算法的分类方法，采用了简化的二叉树模型**，同时特征选择采用了近似的基尼系数来简化计算。

C4.5不一定是二叉树，但CART一定是二叉树。

同时，无论是ID3, C4.5还是CART,在做特征选择的时候都是选择最优的一个特征来做分类决策，但是大多数，**分类决策不应该是由某一个特征决定的，而是应该由一组特征决定的。**这样决策得到的决策树更加准确。这个决策树叫做多变量决策树(multi-variate decision tree)。在选择最优特征的时候，多变量决策树不是选择某一个最优特征，而是选择最优的一个特征线性组合来做决策。这个算法的代表是OC1，这里不多介绍。

如果样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习里面的随机森林之类的方法解决。

三、 cart剪枝

1 为什么要剪枝

•横轴表示在决策树创建过程中树的结点总数，纵轴表示决策树的预测精度。

•实线显示的是决策树在训练集上的精度，虚线显示的则是在一个独立的测试集上测量出来的精度。

•随着树的增长，在训练样集上的精度是单调上升的， 然而在独立的测试样例上测出的精度先上升后下降。

出现这种情况的原因：

•原因1：噪声、样本冲突，即错误的样本数据。

•原因2：特征即属性不能完全作为分类标准。

•原因3：巧合的规律性，数据量不够大。

2 常用的减枝方法

剪枝的意思

2.1 预剪枝 创建的时候进行剪枝，不要去添加某些枝

（1）每一个结点所包含的最小样本数目，例如10，则该结点总样本数小于10时，则不再分；

（2）指定树的高度或者深度，例如树的最大深度为4；

（3）指定结点的熵小于某个值，不再划分。随着树的增长， 在训练样集上的精度是单调上升的， 然而在独立的测试样例上测出的精度先上升后下降**。**

2.2 后剪枝： 创建好决策树之后再剪枝

后剪枝，在已生成过拟合决策树上进行剪枝，可以得到简化版的剪枝决策树。

剪枝的目的

减少决策树节点的数量>降低决策树的复杂度>防止决策树过拟合