做做分类（2）

没时间解释了，快上车！

1

什么是决策树

上次说到根据事物的属性对事物进行分类，比如形状、大小、颜色、材质等，分类的过程就是依次判断这些属性属于哪一类。比如先判断形状是球形，然后判断直径是44mm，颜色是纯白，材质是塑料….到这一步，这个物体也基本确定了。

面这一些列判断可以画成一个树状图，每一次决策都会发生一次分叉。

对每一个样本，我们都可以走一次这个决策树，最后就能引导我们来到一个叶节点，也就是最终的结论。

对每一个样本集，存在的属性肯定是有限的，拥有无限多属性的物体，我只想象到“上帝”这个概念。对于这样的样本，我们总可以进行有限次判断，对物体进行正确的分类。

属性既可以是离散的取值既可以是离散的（比如不同的类别），也可以是连续的。对于离散的取值，直接根据取值的不同来划分；对于连续的取值，可以根据取值范围来进行划分。

同一个属性可以反复用作判断的指标。比如先判断直径,然后判断颜色是黑色，然后又判断

。同理，也不是所有的属性都需要用上，有时候部分属性就足够把所有的样本区分开。

判断的顺序对整个决策树的性能也有很大影响，有时候直接根据关键属性的取值可以很快得出最后结论，节省了判断时间。

2

决策树的好坏

先来介绍一个概念——信息熵。

对于一个数据集D，假设第k类样本占的比例是，那么数据集D信息熵定义为

这里的单位是nat（纳特），也可以用2当作对数底数，那么单位就是bit（比特），如果是以10为底数，单位就是dit（底特）。

可以肉眼看一下，数据集“纯度”越高，熵就越小，比如只有一种类别，那么，就是没有任何信息。信息熵的大小，反应了数据集的“纯度”。决策树的叶节点，数据的信息熵就应该是零，让它们都属于同一类。

假有个数据集D，它有N个数据，它的信息熵是E(D)。属性a有V种取值

，根据这V种取值可以把原有的N个数据分成V个部分，每部分的样本数量是，每部分单独的信息熵是

，那么可以定义这个划分的信息熵增益为

就是数据集D按照属性a划分的信息熵增益。可以看到第二部分，按照各部分数据的大小给给他们的信息熵求了加权和，表征了划分后的信息熵。

根据信息熵的概念，可以知道，信息熵增益越大，这个划分就越有价值，让决策树往叶节点推进了一大步。在构建决策树的时候，我们先选择一种属性，然后做一个最大化信息熵增益的划分，然后选择另一个属性，求得相应的最大信息熵增益，如此重复，找到所有属性的最优划分，最后比较不同属性的最优划分，最后选择最好的一个作为当前步的划分。

3

简要谈谈

最大化信息熵增益是决策树的核心思想。信息熵这个概念在机器学习里经常出现，比如交叉熵等，因为从信息论的角度研究机器学习可以提供一些很宏观的视角，特别是在深度学习领域，可以帮助我们更好的理解网络的功能和属性。（上一次说的SVM，其实可以从另一个角度——流形学习——来导出，流形学习也是一个近年十分热门的研究方向，据说丘成桐的一个弟子就在做这方面的工作。）

关于决策树，还有很多细节

增益率。可以看出，如果每次划分得越细，划分的信息熵增益就会越大，比如有8个数据，我根据一个属性把属性分成了8组，那么这次划分的信息熵增益无疑是最大的。但是，这种划分是没有意义的，就是把每个样本单独归为一类，对预测没有任何帮助，也就是过拟合。解决这个问题，就是定义增益率

，就信息熵增益需要除以划分之后的数据集个数。

剪枝。把信息熵增益改成增益率还是不能完全解决过拟合问题，这个时候就需要做剪枝处理。剪枝分为前剪枝和后剪枝。剪枝需要测试集作为评判标准，每次划分完，前剪枝都会检测一下划分之后的正确率，如果比划分之前低，就放弃这次划分。但是有时会出现虽然这次正确率降低，但是下次正确率又涨上来的情况，所以就需要后剪枝——在决策树完全构建完后，逐层检查去掉这次划分会不会使正确率升高。

4

集成学习

和决策树经常一起出现的名词还有随机森林、adboost，xgboost等。后面三个其实是另一种方式，叫集成学习。它们使用多个分类器进行组合，来达到更优的效果。

横向组合。把数据集随机分为几个部分，在每个部分上训练出不同的分类器，预测的时候，就综合不同分类器的结果。比如加权，比如投票等。

纵向组合。把上一个分类器的分类结果作为下一个分类器的输入。比如上次分类之后由三个叶节点，那么这次就针对每个叶节点再做一次分类。

随机森林属于第一种。在实际操作中，还有很多讲究，比如如何把数据集分成不同的部分，每个部分是重合还是不重合，重合的话该重合多少等。除了数据集的随机还可以有属性的随机，就是每次训练一个新的分类器，我只是随机选择几个数据性。数据集合和属性的随机性都尽可能的让不同的分类器完成不同的任务，最后组合的时候结果更加稳定。

之所以这些集成学习的概念总是和决策树一起出现，是因为集成学习大多采用决策树作为基础分类器，但是也不一定，我们可以组合决策树和SVM，也可以组合神经网络和决策树，完全取决于应用场景。

和SVM相比，决策树的非线性能力会更强，因为它针对不同的属性做了划分，每一次划分都可以是完全非线性的（甚至可以用SVM来做每一次的划分），最后还对每次的划分做了整合，所以整体的表征能力（容量）是更大的。

决策树配合随机森林，还有很强的泛化能力，也就是不容易过拟合，因此应用十分广泛。

好文！必须点赞