Decision Tree
1. 什么是决策树
决策树是一个极其直观的算法(这也使得它的可解释性非常好),比如下面这个决策树
2. 基本决策树算法
从上面可以看出来这个形式非常的简单,那么如何生成一颗决策树?相信开始了nano degree并完成了P0的同学们都已经自己实现过一个决策树了,也就是大家做的Titanic的project,在第三个问题中,大家自己通过不断的选择特征,产看结果,最终得到了一个准确率超过80%的模型,这就是一个决策树。
可是这种方法明显是没有可扩展性可言的,大家可以体验到对于这么小的一个数据集大家都构建的很辛苦,并且准确率也不是太高。所以我们需要一个自动构建的算法。
其实这个算法也十分简单,对于我们的数据集来说我们关键是按照下面两步来完成决策树的构建:
- 选择一个最佳属性进行划分
- 对每一个子节点迭代进行划分,知道完全划分开
划分准则的选择
从上面关键的两步可以看出划分准则的选择是一个很重要的问题,因为理论上来说找到一个最佳的划分是一个NP-hard的问题,所以说我们不能够通过某一种算法得到最优划分,那么现在的做法就是通过一些启发式的指标来选择合适的划分准则,常用的有(下面我就不一一列公式了,大家可以从其他地方查一下):
- 信息增益(ID3使用这种)
计算划分前后信息熵的差值,增益大的划分好
- 信息增益率(C4.5使用这种)
信息增益存在的一个问题是,它对于可取值数目多的属性有偏好(极端情况,我把每一个值都作为一个划分将获得一个很大的信息增益)。所以定义了增益率(不过增益率会对取指少的有偏好,所以C4.5实际上对选择还有一个权衡,结合了增益和增益率考虑)。
- 基尼系数(CART使用这种)
暂时不了解它有什么明显缺陷,应该是现在相对最好的一个准则吧。
3. 常见决策树算法
常见的三个算法有:
- ID3
- CART
- C4.5
这三个算法都符合上面的简单形式,他们的不同点主要体现在1.如何选择最佳属性?2.对于各种不同属性的处理3.剪枝。大家可以学习下,我就不一一写出来了。
4. 决策树的剪枝
为什么需要剪枝?
上面没有太谈剪枝问题,那么首先看下为什么要剪枝?因为如果我们不对决策树剪枝的话,决策树会不断生长,这样就会出现我们熟悉的过拟合问题了。所以对决策树剪枝是十分必要的。
剪枝方式
- 前剪枝
所谓前剪枝就是我们可以在树还没有构建的情况下,选择一些先验的准则对树的生长做限制,比如:限制树最多生长多少层,限制树有多少节点等。这个部分大家如果用sklearn的话,实际上它后面的很多参数就是做了一个前剪枝的工作。
- 后剪枝
所谓后剪枝就是我们在树已经构建完成之后,我们对树进行修剪。这时候修剪当然就要考虑到生成的数和原始的数据集。所以一般的做法就是我们专门为决策树构建出一个剪枝测试集。然后对于树上的节点(可以一次考虑一个或者多个)我们都考虑保留这些节点和不保留这些节点,如果过测试出来不保留更佳的话我们就可以把这个剪掉。一般来说后剪枝的效果会更好,但是代价也会大很多所以是否采用也需要权衡。
5. 决策树的优缺点
我们也可以考虑一下决策树的优缺点,这里也能够帮助理解他的思想。这里简单列出几点:
优点
- 可解释性好
- 只需要很少的数据预处理工作。并且能够处理各种类型的特征
- 原生支持多分类
缺点
- 决策树容易过拟合
- 决策树不稳定,也就是说可能数据集的一个很小的变动就会导致树发生很大的改变。
- 构建一个最佳的决策树是一个NP-hard问题,现有的启发式算法不能够保证最优(也没有一个理论的上下界)。
- 简单的决策树模型比较简单,很难表示数据集中的复杂关系。
6. 建议学习方向
- 看一下具体的ID3(这个在Udacity提供的附加资料中就有)、C4.5、CART算法(其实这三个算法并不复杂,而且只是某个算法在某一方面做了一些优化)
- 自己实现一个决策树?(比如可以看《机器学习实战》,很简单)
- 看一下sklearn介绍1
7. 总结
决策树的关键在于如何自动构建和防止过拟合。
如果大家觉得还有一些知识是课程中提到或者是没提到但是十分重要的部分也欢迎补充。
相关推荐
机器学习十大算法(1):决策树C4.5.rar
《机器学习》算法实例-决策树算法-预测鱼类和非鱼类实例 根据不浮出水面是否可以生存、是否有脚蹼2 个特征,将动物分成两类:...使用算法: 此步骤可以适用于任何监督学习任务,而使用决策树可以更好地理解数据的内在含义
决策树算法效果评估 决策树生成算法 ID3算法 ID3算法优缺点 C4.5算法 8 CART算法 8 ID3\C4.5\CART分类回归树算法总结 分类树和回归树的区别 决策树优化策略 决策树的剪枝 决策树剪枝过程 附录:
决策树(Decision Tree)是在已知各种情况发生概率的基础上,通过构成决策树来求取净现值的期望值大于等于零的概率,评价项目风险,判断其可行性的决策分析方法,是直观运用概率分析的一种图解法。由于这种决策分支画...
决策树分类(ID3,C4.5,CART) 三种算法的区别如下: (1) ID3算法以信息增益为准则来进行选择划分属性,选择信息增益最大的; (2) C4.5算法先从候选划分属性中找出信息增益高于平均水平的属性,再从中选择增益率...
决策树算法matlab实现,构造分类决策树并用决策树对模式进行分类识别
决策树分类算法实验报告18页-作者原创机器学习大作业-目录内容: 1.研究意义2.数据描述3.模型描述4.算法实现5.运行结果及意义说明6.总结-包含算法流程图,运行结果截图
机器学习--决策树(ID3)算法及案例.docx机器学习--决策树(ID3)算法及案例.docx机器学习--决策树(ID3)算法及案例.docx机器学习--决策树(ID3)算法及案例.docx机器学习--决策树(ID3)算法及案例.docx机器学习--决策树(ID3...
1.领域:matlab,模糊控制和决策树算法 2.内容:基于模糊控制和决策树的预测算法matlab仿真+代码操作视频 3.用处:用于模糊控制和决策树算法编程学习 4.指向人群:本硕博等教研学习使用 5.运行注意事项: 使用...
决策树算法经典优秀论文(1).zip 决策树算法经典优秀论文(1).zip 决策树算法经典优秀论文(1).zip 决策树算法经典优秀论文(1).zip 决策树算法经典优秀论文(1).zip 决策树算法经典优秀论文(1).zip 决策树算法经典优秀...
决策树是一种常用的机器学习算法,用于解决分类和回归问题。它的可解释性和易于理解的特点使得决策树成为了智能决策的重要工具。本文将介绍决策树的原理、构建过程以及在实际应用中的优势和限制。 第一部分:决策树...
代码及数据集:决策树分类算法--隐形眼镜材质分类。数据集来自UCI数据库。隐形眼镜类型包括:硬材质、软材质、不适合佩戴隐形眼镜
课程设计作业——基于iris数据集进行机器学习算法(决策树、朴素贝叶斯、随机森林、SVM)的训练,使用交叉检验对比算法预测准确率 Algorithms Average prediction accuracy(%) Standard deviation 决策树(Decision ...
人工智能课件:决策树算法.pdf
决策树算法原理以及实现方法,基于监督的学习方法。在信息论中,熵代表了一个系统的混乱程度,熵越大,说明我们的数据集纯度越低,当我们的数据集都是同一个类别的时候,熵为0
1.什么是分类算法 2.关于分类算法的问题 3.决策树算法介绍 4.评估模型的准确性 5.应用:决策树算法在python中的实现 6.总结
数据挖掘:决策树算法及应用拓展.ppt
摘 要: 决策树是归纳学习和数据挖掘的重要方法, 通常用来形成分类器和预测模型。概述了决策树分类算法, 指出了决策树算法的核心技术: 测试属性的选择和树枝修剪技术。通过对当前数据挖掘中具有代表性的优秀分类...
MATLAB神经网络和优化算法专题: 决策树与随机森林参考程序.zip
机器学习C++源码解析-决策树cart算法-源码+数据