机器学习周志华笔记系列-第四章-决策树（欢迎讨论）

系列背景：

从周志华机器学习第四章开始，总结每章的知识点。

非科班，能源工科，复习过考研微积分，线性代数，概率论。机器学习小白。

所以总结机器学习方法的思想，尽量不涉及数学工具，如矩阵微分、奇异值分解、凸优化、概率论共轭分布、KL散度等（书中附录）。

结构简单，问题导向，每个问题分为：问题，思想，其他方法和比较，具体方法，思考，其他。

“？”为自己提出的一些问题，欢迎大家提出自己的想法

欢迎讨论

第四章 决策树

1.问题：分类问题

解决：决策树

思想：模仿人根据事物属性对事物分类的过程

其他方法和比较：分类方法还有对数几率回归、线性判别分析LDA。几种方法有什么优缺点，适用于什么情况？

具体方法：决策树的组成有样例集，属性集，测试节点，叶节点。对于每一个测试节点，选择一个属性对样例集进行判断，会有下面三种执行情况：（1）如果样例集为空，则将该测试节点定义为叶节点，用父节点的样例数量较多的类作为该测试节点的标签（基于先验分布？）（2）如果样例集全部属于同一类，则将该测试节点定义为叶节点，该类作为该测试节点的标签（基于后验分布？）（3）如果不属于上述两种，则在该测试节点产生分支，每个分支代表该属性的可能取值，每个分支产生新的测试节点，样例子集，除去从该测试节点到根节点之间的属性之后剩余属性组成的属性集，递归重复上述过程

2.问题：每个测试节点如何选择属性

思想：测试节点的作用是使样例集经过一个属性分类后得到的样例子集都会变得更纯（即属于一类的更多，属于其他类的更少），所以我们从属性集中选择能让样例集变得最纯的属性

3.问题：怎么衡量样例集的纯度

解决：信息熵和基尼系数。

思想：信息熵的思想是什么？为什么最后看的是信息增益而不是直接用属性分类的信息熵进行选择，像基尼系数基尼系数则不看增益？

基尼系数的思想是假设一个数据集有N类数据，从中有放回的拿出一类之后再拿出不属于这类的其他类的概率，对于每一类都做这样的操作，再将概率求和。基尼系数为零表示只有一类，越接近1，表示类别越多，以此来衡量样例集的纯度

其他方法和比较：二者的优缺点？有没有其他方法？

4.问题：信息增益会更倾向于选择属性值较多的属性，如何减轻这种倾向

解决：增益率。

思想：属性值越多，按照属性值对样例分类越复杂，属性值的信息熵越大（对照之前类别的信息熵）。所以用之前求得的信息增益除以属性值的信息熵，是属性值越多的属性，信息增益打的折扣更大。

其他方法：可不可以用基尼系数来表示属性值的信息复杂程度？

其他：过犹不及，增益率倾向于选择属性值较少的属性，所以采用启发法，先从属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。另外基尼系数会不会也倾向于选择属性值较多的属性？

5.问题：过拟合怎么办

解决：预剪枝和后剪枝

思想：我的理解，决策树很容易产生过拟合，因为训练过程中决策树完全学习了每一个样例，不存在类似线性回归最小二乘法的整体拟合，所以得到的模型对个例没有修正，泛化能力差。所以要减去个例的分支，即剪枝技术。

6.问题：怎么衡量泛化能力

思想：采用验证集测试的方法。

（接5.问题）具体方法和工具：

预剪枝：训练时，对于生成的每一个节点，用验证集测试在该节点不分类的精度和分类之后的精度，不分类精度大于等于分类之后的，就不分类，该节点就成为叶节点。

后剪枝：训练结束后从下到上的对每个节点，用验证集测试在该节点不分类的精度和分类之后的精度，不分类精度大于等于分类之后的，就不分类，该节点就成为叶节点。

其他：过犹不及，剪枝技术过度会导致欠拟合。一般情况下后剪枝比预剪枝保留更多的分支，不易发生欠拟合，泛化性能较高，但训练时间更长。

7.问题：数据冲突怎么办

思想：数据冲突的解决方法一是去掉冲突数据，二是冲突数据同样用于训练模型，对于一个测试节点，返回数量较多的类型作为标签。

8.问题：连续的属性如何处理

解决：二分法

思想：解决连续特征问题就是解决分支问题，二分法用到信息增益的思想。

具体方法：对于一个属性，将训练集中该可能取值从大到小排序，相邻两个数的平均值，作为候选分支点，然后对于每个候选点计算信息增益，选择信息增益最大的值。

其他：未被选中的一些候选点可在接下来的属性选择中继续利用。

9.问题：缺失数据如何处理

思想：直接删除造成信息浪费。对于一个属性，缺失数据的样例可能属于任何一个分支，把它们放在每一个分支中，会使样例在各个分支中分布更加平均，平均意味着信息熵更大，即按照该属性分类之后信息纯度低，所以尽量不选这样的特征，也就是说这样的属性计算信息熵时已经给自我惩罚了，为什么还要用如下的方法呢？

具体方法：保留样例，但是赋予每个样例权值，初始权值相同。选择属性时排除缺失数据样例之后计算信息增益，然后乘以数据完整率进行惩罚；缺失数据的样例分配到每个分支中，权重发生改变，权重基于排除缺失数据样例之后计算。

10.问题：多变量决策树

思想：如果建立一个坐标系，每个属性是一个坐标轴，每个样例是坐标系中的一个点。单变量决策树在每一个测试节点只判断一个属性，这样的分类边界是平行于坐标轴的一段段折线。但是实际的分类边界可能是曲线。一种方法是用折线去近似曲线，显然需要很多段折线，也就是很多测试节点；另一种方法是在测试节点用曲线边界测试，即x^2代替x，或者引入多变量测试，即x1+x2这种斜线边界。

其他方法和比较：有没有其他方法？

（接1.问题）其他：

属性选择对泛化性能影响有限，剪枝技术对泛化性能影响很大

一些决策树与线性模型，感知机，神经网络结合（见原书4.6节阅读材料）

一些决策树可进行增量学习（接收新样本后只需调整模型，而不需重新训练）

最后

以上就是勤劳犀牛为你收集整理的机器学习周志华笔记系列-第四章-决策树（欢迎讨论）的全部内容，希望文章能够帮你解决机器学习周志华笔记系列-第四章-决策树（欢迎讨论）所遇到的程序开发问题。

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