决策树

参考

https://blog.csdn.net/u012328159/article/details/79396893
https://blog.csdn.net/u012328159/article/details/79413610
https://www.cnblogs.com/fionacai/p/5894142.html

原理

决策树常用来解决分类问题，是一种基本的分类与回归方法。它递归每个特征的各种取值，将样本切分为多个类，最后可以得到一个树形结构。

举个例子：引用自这里的例子

一位母亲在给女儿介绍对象时，有这么一段对话：
母亲：给你介绍个对象。
女儿：年纪多大了？
母亲：26。
女儿：长的帅不帅？
母亲：挺帅的。
女儿：收入高不？
母亲：不算很高，中等情况。
女儿：是公务员不？
母亲：是，在税务局上班呢。
女儿：那好，我去见见。

这个女生的决策过程就是典型的分类决策树。相当于对年龄、外貌、收入和是否公务员等特征将男人分为两个类别：见或者不见。假设这个女生的决策逻辑如下：

1.png

在上面女儿的决策中，将男生根据不同的特征分为了两类：见或者不见。但图中的判断顺序取决于母亲的询问顺序，有时候是不合理的，有可能女生开始判断是公务员其它条件不管是什么都回去见呢。。：）

所以我们需要找到什么特征对女生的影响最大，先判断影响大的，再去判断影响小的。这样引入下面的基本概念。

基础概念

熵

熵表示随机变量的不确定性度量。也就是说我们可以用熵去表示特征的不确定性。

熵的公式为:

屏幕快照 2018-04-12 21.40.49.png
屏幕快照 2018-04-12 21.44.24.png

解释一下，在上面的例子中，集合A中一共有10个样本，值取1有8个，取2有2个，那么p1为8/10，p2为2/10，熵为：
H(X) = - 8/10 * log(8/10) - 2/10 * log(2/10) = 0.5004024235381879

条件熵

条件熵表示在某个条件下随机变量的不确定性度量。
以上面的集合A为例，当变量小于1.5的时候，集合A中，所有的变量都为1。当变量大于1.5的时候，所有的变量都为2。

当变量小于1.5时，熵为: H(X | X < 1.5) = - 8/8 * log(8/8) = 0.0
当变量大于1.5时，熵为: H(X | X > 1.5) = - 2/2 * log(2/2) = 0.0

将这两个上相加，就是以1.5值作为条件划分之后，新的数据集的熵值。 为0

信息增益

信息增益表示，当数据集根据某个特征划分之后，熵的变化大小。

在上面的例子中，在没有条件(X> 1.5 或 X < 1.5)的时候熵为0.5004024235381879。在经过条件的划分后，新的熵值为0，那么信息增益就是旧值减去新值。g(D,A)=H(D)−H(D|A)= 0.5004024235381879 - 0 = 0.5004024235381879

这样，如果有多个特征，分别计算根据各个特征作为条件后的熵值，并得到信息增益。我们选择信息增益最大的特征作为影响最大的特征，先进行分类判断。

信息增益率

有时候特征数据不确定性比较大的时候，比如上面的集合B，这样的数据计算出来的信息增益特别的大，因为，对它进行划分后，每个分类里的值都是唯一的，熵都为0。这样显然不合理。

信息增益率 = 信息增益 / 原熵值

我们用信息增益率来代替信息增益，选取信息增益率最大的作为优先划分特征。

构建树的结束条件

遇到下面几种情况，就停止继续划分节点：

1. 节点中所有样本属于同一类。
2. 该节点中所有样本的属性取值一致。
3. 树的深度达到设定的阈值。
4. 该节点所含样本值小于设定的父节点应含观测数的阈值。
5. 该节点的的子节点所按样本数将小鱼设定的阈值。
6. 没有属性能满足设定的分裂准则的阈值。

例子

def createDataSet():
    dataSet = [['youth', 'no', 'no', 1, 'refuse'],
               ['youth', 'no', 'no', '2', 'refuse'],
               ['youth', 'yes', 'no', '2', 'agree'],
               ['youth', 'yes', 'yes', 1, 'agree'],
               ['youth', 'no', 'no', 1, 'refuse'],
               ['mid', 'no', 'no', 1, 'refuse'],
               ['mid', 'no', 'no', '2', 'refuse'],
               ['mid', 'yes', 'yes', '2', 'agree'],
               ['mid', 'no', 'yes', '3', 'agree'],
               ['mid', 'no', 'yes', '3', 'agree'],
               ['elder', 'no', 'yes', '3', 'agree'],
               ['elder', 'no', 'yes', '2', 'agree'],
               ['elder', 'yes', 'no', '2', 'agree'],
               ['elder', 'yes', 'no', '3', 'agree'],
               ['elder', 'no', 'no', 1, 'refuse'],
               ]
    labels = ['age', 'working?', 'house?', 'credit_situation']
    return dataSet, labels

上面是银行贷款的15个样本数据，有4种特征，最后一列为是否同意贷款。是我们的分类类别。前面4个是年龄段、是否有工作、是否有房、信用等级。

下面的log计算，是以底为2计算的。之前的是以10为底。这个没有关系

首先我们计算在没有条件下，分类的熵情况，同意的情况有9次，不同意的情况有6次。则：
H(x) = - 9/15 * log(9/15) - 6/15 * log(6/15) = 0.9709505944546686

然后我们分别计算每个特征分类条件下的熵值：
以age为例：当age取值为youth时，有5个样本，同意的情况有2次，不同意3次，那么熵为：
H(x | age == youth) = - 3/5 * log(3/5) - 2/5 * log(2/5) = 0.9709505944546686
同理
H(x | age == mid) = - 3/5 * log(3/5) - 2/5 * log(2/5) = 0.9709505944546686
H(x | age == elder) = - 4/5 * log(4/5) - 1/5 * log(1/5) = 0.7219280948873623

那么
H(x | age) = H(x | age == youth) + H(x | age == mid) + H(x | age == elder) = 2.663829
信息增益g(x,age) = 0.9709505944546686 - 2.663829 = -1.692879 (负值代表划分后不确定性更高了，一般不可取)
信息增益率(age) = g(x,age) / H(x | age) = -1.743527

继续计算working、house、credit_situation：
g(x, working) = 0.000000
g(x, house) = 0.052655
g(x, credit_situation) = -0.669273

信息增益率(working) = 0.000000
信息增益率(house) = 0.054230
信息增益率(credit_situation) = -0.689297

无论是以信息增益 还是信息增益率，选取最大的作为最有影响的特征，house（是否有房）作为第一节点。

接着讲house划分为两个数据集，继续上面的步骤，再次计算信息增益或信息增益率，最终得到决策树。

Unknown.png

当我们进行两个迭代后，判断house和working后，所有的样本都在同一个类别下面了，就停止迭代。

连续值处理

当我们的特征数据中存在连续值的时候，我们不能将每个值都当做一个分类吧！！

常用的办法就是二分法，也是C4.5中采用的策略，具体意思就是将确定一个值，将数据分为大于这个值和小于这个值的两类。

如何确定这个值呢？

公式定理：

20180228135729007.jpeg

白话文就是，首先将连续值进行排序，将排序后每两个值中间的值作为划分点，循环计算每个点划分后，连续值的信息增益，选取信息增益最大的划分点。

举个简单例子
连续值集合A [1,1,1,3,3,3,4] 排序后，计算划分点的集合为[2, 3.5]

集合A熵值= H(x) =- 1/7 * log(1/7) - 3/7 * log(3/7) - 3/7 * log(3/7) = 1.0042424730540764

计算划分点为2
当x<2时，H(A| x<2) = - 3/3 * log(3/3) = 0
当x>=2时，H(A | x>=2) = - 3/4 * log(3/4) - 1/4 * log(1/4) = 0.5623351446188083
熵为 = H(A| x<2) + H(A | x>=2) = 0.5623351446188083
信息增益 = g(A | 2为划分点) = H(x) - H(A| 2为划分点) = 0.44190732843526814

计算划分点为3.5
当x<3.5时，H(A | x < 3.5) = - 3/6 * log(3/6) - 3/6 * log(3/6) = 0.6931471805599453
当x >= 3.5 时，H(A | x >= 3.5) = - 1/1 * log(1/1) = 0
熵为 = H(A| x< 3.5) + H(A | x>= 3.5) = 0.6931471805599453
信息增益 = g(A | 3.5为划分点) = H(x) - H(A| 3.5为划分点) = 0.31109529249413115

这样相比当划分点为2的时候，信息增益比较大，将2作为划分点。

思考：如果数据量比较大，那划分点的数量会非常多，会不会比较慢，有没有更好的方案？
如果想选择多个划分点，是否可以直接选择剩下的信息增益低的特征。

缺省值处理

在实际情况中，数据总是会有缺失的，当然也可以将这些特征给删除掉，但有时候这样也是不合理的。

下面引用参考文章中的例子：

20180301204809787.jpg

公式，文本的说法可以直接看参考文章。下面是我自己的白话文。。。

以色泽这个特征为例，
第一步，我们将缺失的值去掉，留下无缺失值的集合编号[2,3,4,6,7,8,9,10,11,12,14,15,16,17]。
第二步，计算这个无缺失值集合的信息增益。
H(x) = - 6/14 * log(6/14) - 8/14 * log(8/14) = 0.985
H(x | x = 青绿) = - 2/4 * log(2/4) - 2/4 * log(2/4) = 1
H(x | x = 乌黑) = - 4/6 * log(4/6) - 2/6 * log(2/6) = 0.918
H(x | x = 浅白) = - 0/4 * log(0/4) - 4/4 * log(4/4) = 0
g(x) = H(x) - (H(x | x = 青绿) * 4/14 + H(x | x = 乌黑) * 6/14 + H(x | x = 浅白) * 4/ 14) = 0.306

这样分别计算每个特征的信息增益，选取信息增益最大的特征，作为根节点。

比较发现，“纹理”在所有属性中的信息增益值最大，因此，“纹理”被选为划分属性，用于对根节点进行划分。划分结果为：“纹理=稍糊”分支：{7,9,13,14,17}，“纹理=清晰”分支：{1,2,3,4,5,6,15}，“纹理=模糊”分支：{11,12,16}。

但是纹理的[8,10]是缺失的，改怎么处理？

将8和10两个样本，分别划入每个分支中，给每个分支中的8和10的样本设置权重，

20180302150552337.png

然后我们一这个新的分支集合，继续执行决策树的构造过程。
以纹理=稍糊为例：现在的集合是[7,8,9,10,13,14,17]

20180302152911787.png

再次技术色泽的信息增益，色泽无缺失集合为[7,8,9,10,14,17]，但是，8和10的权重不是1了，是之前计算的权重值 1/3。

不好描述 还是截图吧。

屏幕快照 2018-04-17 下午1.52.44.png

这样分别计算各个特征的信息增益，发现“敲声”，信息增益最大，这样得到了在稍糊分支上的特征划分。

20180303105613522.png

继续按照这规则递归下去，得到整颗树：

20180303112711995.jpg

剪枝

如果以决策树的定义，叶节点内的所有的样本都属于同一个类的话，决策树一般会非常庞大，而且可能分类效果也不好，产生过拟合的现象。所以需要对决策树进行剪枝

剪枝一般有两种思路，预剪枝和后剪枝。

• 预剪枝，在决策树开始构造之前，预先定义一些参数，比如，树深度，叶节点数量等，然后在构造树的过程中，瞒住条件参数，就可以停止继续构造了。
• 后剪枝，先将整颗树构造完毕，然后使用测试集测试在剪枝后的误差和剪枝前的误差，如果剪枝后误差变小了，那么可以剪枝。

随机森林

尽管有各种剪枝算法，一棵树的效果肯定还是不如多颗树，因此有了随机森林，解决决策树泛化能力弱的缺点。

这时就有了Bagging策略可以产生多个不同的数据集。

1. 在数据集不变的情况下，我们可以选择ID3、C4.5、CART、SVM、LOGISTIC等算法作为不同的判断条件，分别建立不同的树。
2. 还可以更进一步在数据集上做文章：
   • 样本的随机：从样本集中随机选取n个样本。
   • 特征的随机：从所有特征中，随机选取k个特征。

这样可以建立m个随机的决策树。

得到m个决策树后，测试数据集分别进入这m棵树进行分类，被分类到的次数越多，就是选那个分类。

调参：

1. 如何选取K，可以考虑有N个属性，取K=根号N
2. 最大深度（不超过8层）
3. 棵数
4. 最小分裂样本树
5. 类别比例

决策树的重要参数都是防止过拟合的. 有2个参数是关键，min_samples_leaf 这个sklearn的默认值是1，经验上必须大于100，如果一个节点都没有100个样本支持他的决策，一般都被认为是过拟合；max_depth 这个参数控制树的规模。决策树是一个非常直观的机器学习方法。一般我们都会把它的决策树结构打印出来观察，如果深度太深对于我们的理解是有难度的。