3.1、摘要
在前面两篇文章中,分别介绍和讨论了朴素贝叶斯分类与贝叶斯网络两种分类算法。这两种算法都以贝叶斯定理为基础,可以对分类及决策问题进行概率推断。在这一篇文章中,将讨论另一种被广泛使用的分类算法——决策树(decision tree)。相比贝叶斯算法,决策树的优势在于构造过程不需要任何领域知识或参数设置,因此在实际应用中,对于探测式的知识发现,决策树更加适用。
3.2、决策树引导
通俗来说,决策树分类的思想类似于找对象。现想象一个女孩的母亲要给这个女孩介绍男朋友,于是有了下面的对话:
女儿:多大年纪了?
母亲:26。
女儿:长的帅不帅?
母亲:挺帅的。
女儿:收入高不?
母亲:不算很高,中等情况。
女儿:是公务员不?
母亲:是,在税务局上班呢。
女儿:那好,我去见见。
这个女孩的决策过程就是典型的分类树决策。相当于通过年龄、长相、收入和是否公务员对将男人分为两个类别:见和不见。假设这个女孩对男人的要求是:30岁以下、长相中等以上并且是高收入者或中等以上收入的公务员,那么这个可以用下图表示女孩的决策逻辑(声明:此决策树纯属为了写文章而YY的产物,没有任何根据,也不代表任何女孩的择偶倾向,请各位女同胞莫质问我^_^):
上图完整表达了这个女孩决定是否见一个约会对象的策略,其中绿色节点表示判断条件,橙色节点表示决策结果,箭头表示在一个判断条件在不同情况下的决策路径,图中红色箭头表示了上面例子中女孩的决策过程。
这幅图基本可以算是一颗决策树,说它“基本可以算”是因为图中的判定条件没有量化,如收入高中低等等,还不能算是严格意义上的决策树,如果将所有条件量化,则就变成真正的决策树了。
有了上面直观的认识,我们可以正式定义决策树了:
决策树(decision tree)是一个树结构(可以是二叉树或非二叉树)。其每个非叶节点表示一个特征属性上的测试,每个分支代表这个特征属性在某个值域上的输出,而每个叶节点存放一个类别。使用决策树进行决策的过程就是从根节点开始,测试待分类项中相应的特征属性,并按照其值选择输出分支,直到到达叶子节点,将叶子节点存放的类别作为决策结果。
可以看到,决策树的决策过程非常直观,容易被人理解。目前决策树已经成功运用于医学、制造产业、天文学、分支生物学以及商业等诸多领域。知道了决策树的定义以及其应用方法,下面介绍决策树的构造算法。
3.3、决策树的构造
不同于贝叶斯算法,决策树的构造过程不依赖领域知识,它使用属性选择度量来选择将元组最好地划分成不同的类的属性。所谓决策树的构造就是进行属性选择度量确定各个特征属性之间的拓扑结构。
构造决策树的关键步骤是分裂属性。所谓分裂属性就是在某个节点处按照某一特征属性的不同划分构造不同的分支,其目标是让各个分裂子集尽可能地“纯”。尽可能“纯”就是尽量让一个分裂子集中待分类项属于同一类别。分裂属性分为三种不同的情况:
1、属性是离散值且不要求生成二叉决策树。此时用属性的每一个划分作为一个分支。
2、属性是离散值且要求生成二叉决策树。此时使用属性划分的一个子集进行测试,按照“属于此子集”和“不属于此子集”分成两个分支。
3、属性是连续值。此时确定一个值作为分裂点split_point,按照>split_point和<=split_point生成两个分支。
构造决策树的关键性内容是进行属性选择度量,属性选择度量是一种选择分裂准则,是将给定的类标记的训练集合的数据划分D“最好”地分成个体类的启发式方法,它决定了拓扑结构及分裂点split_point的选择。
属性选择度量算法有很多,一般使用自顶向下递归分治法,并采用不回溯的贪心策略。这里介绍ID3和C4.5两种常用算法。
3.3.1、ID3算法
从信息论知识中我们直到,期望信息越小,信息增益越大,从而纯度越高。所以ID3算法的核心思想就是以信息增益度量属性选择,选择分裂后信息增益最大的属性进行分裂。下面先定义几个要用到的概念。
设D为用类别对训练元组进行的划分,则D的熵(entropy)表示为:
其中pi表示第i个类别在整个训练元组中出现的概率,可以用属于此类别元素的数量除以训练元组元素总数量作为估计。熵的实际意义表示是D中元组的类标号所需要的平均信息量。
现在我们假设将训练元组D按属性A进行划分,则A对D划分的期望信息为:
而信息增益即为两者的差值:
ID3算法就是在每次需要分裂时,计算每个属性的增益率,然后选择增益率最大的属性进行分裂。下面我们继续用SNS社区中不真实账号检测的例子说明如何使用ID3算法构造决策树。为了简单起见,我们假设训练集合包含10个元素:
其中s、m和l分别表示小、中和大。
设L、F、H和R表示日志密度、好友密度、是否使用真实头像和账号是否真实,下面计算各属性的信息增益。
因此日志密度的信息增益是0.276。
用同样方法得到H和F的信息增益分别为0.033和0.553。
因为F具有最大的信息增益,所以第一次分裂选择F为分裂属性,分裂后的结果如下图表示:
在上图的基础上,再递归使用这个方法计算子节点的分裂属性,最终就可以得到整个决策树。
上面为了简便,将特征属性离散化了,其实日志密度和好友密度都是连续的属性。对于特征属性为连续值,可以如此使用ID3算法:
先将D中元素按照特征属性排序,则每两个相邻元素的中间点可以看做潜在分裂点,从第一个潜在分裂点开始,分裂D并计算两个集合的期望信息,具有最小期望信息的点称为这个属性的最佳分裂点,其信息期望作为此属性的信息期望。
3.3.2、C4.5算法
ID3算法存在一个问题,就是偏向于多值属性,例如,如果存在唯一标识属性ID,则ID3会选择它作为分裂属性,这样虽然使得划分充分纯净,但这种划分对分类几乎毫无用处。ID3的后继算法C4.5使用增益率(gain ratio)的信息增益扩充,试图克服这个偏倚。
C4.5算法首先定义了“分裂信息”,其定义可以表示成:
其中各符号意义与ID3算法相同,然后,增益率被定义为:
C4.5选择具有最大增益率的属性作为分裂属性,其具体应用与ID3类似,不再赘述。
3.4、关于决策树的几点补充说明
3.4.1、如果属性用完了怎么办
在决策树构造过程中可能会出现这种情况:所有属性都作为分裂属性用光了,但有的子集还不是纯净集,即集合内的元素不属于同一类别。在这种情况下,由于没有更多信息可以使用了,一般对这些子集进行“多数表决”,即使用此子集中出现次数最多的类别作为此节点类别,然后将此节点作为叶子节点。
3.4.2、关于剪枝
在实际构造决策树时,通常要进行剪枝,这时为了处理由于数据中的噪声和离群点导致的过分拟合问题。剪枝有两种:
先剪枝——在构造过程中,当某个节点满足剪枝条件,则直接停止此分支的构造。
后剪枝——先构造完成完整的决策树,再通过某些条件遍历树进行剪枝。
关于剪枝的具体算法这里不再详述,有兴趣的可以参考相关文献。
张洋 http://www.cnblogs.com/leoo2sk/archive/2010/09/19/decision-tree.html
相关推荐
算法杂货铺——分类算法之决策树(Decision tree).doc
决策树是一种广泛应用于数据挖掘和机器学习领域的算法,它的核心思想是通过构建树状模型来对数据进行分类或回归分析。这种模型易于理解和解释,因此在处理复杂问题时,特别是涉及人类决策的问题时,决策树成为了首选...
5. **决策树**(Decision Tree):决策树是一种直观的分类和回归方法,通过构建树形结构进行预测。Python的`sklearn`库提供了`DecisionTreeClassifier`和`DecisionTreeRegressor`。 6. **随机森林**(Random Forest...
亲测可用
资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。
【项目资源】: 物联网项目适用于从基础到高级的各种项目,特别是在性能要求较高的场景中,比如操作系统开发、嵌入式编程和底层系统编程。如果您是初学者,可以从简单的控制台程序开始练习;如果是进阶开发者,可以尝试涉及硬件或网络的项目。 【项目质量】: 所有源码都经过严格测试,可以直接运行。 功能在确认正常工作后才上传。 【适用人群】: 适用于希望学习不同技术领域的小白或进阶学习者。 可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【附加价值】: 项目具有较高的学习借鉴价值,也可直接拿来修改复刻。 对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。 【沟通交流】: 有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。 鼓励下载和使用,并欢迎大家互相学习,共同进步。 # 注意 1. 本资源仅用于开源学习和技术交流。不可商用等,一切后果由使用者承担。 2. 部分字体以及插图等来自网络,若是侵权请联系删除。
【项目资源】: 单片机项目适用于从基础到高级的各种项目,特别是在性能要求较高的场景中,比如操作系统开发、嵌入式编程和底层系统编程。如果您是初学者,可以从简单的控制台程序开始练习;如果是进阶开发者,可以尝试涉及硬件或网络的项目。 【项目质量】: 所有源码都经过严格测试,可以直接运行。 功能在确认正常工作后才上传。 【适用人群】: 适用于希望学习不同技术领域的小白或进阶学习者。 可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【附加价值】: 项目具有较高的学习借鉴价值,也可直接拿来修改复刻。 对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。 【沟通交流】: 有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。 鼓励下载和使用,并欢迎大家互相学习,共同进步。 # 注意 1. 本资源仅用于开源学习和技术交流。不可商用等,一切后果由使用者承担。 2. 部分字体以及插图等来自网络,若是侵权请联系删除。
【项目资源】: 单片机项目适用于从基础到高级的各种项目,特别是在性能要求较高的场景中,比如操作系统开发、嵌入式编程和底层系统编程。如果您是初学者,可以从简单的控制台程序开始练习;如果是进阶开发者,可以尝试涉及硬件或网络的项目。 【项目质量】: 所有源码都经过严格测试,可以直接运行。 功能在确认正常工作后才上传。 【适用人群】: 适用于希望学习不同技术领域的小白或进阶学习者。 可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【附加价值】: 项目具有较高的学习借鉴价值,也可直接拿来修改复刻。 对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。 【沟通交流】: 有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。 鼓励下载和使用,并欢迎大家互相学习,共同进步。 # 注意 1. 本资源仅用于开源学习和技术交流。不可商用等,一切后果由使用者承担。 2. 部分字体以及插图等来自网络,若是侵权请联系删除。
【项目资源】: 物联网项目适用于从基础到高级的各种项目,特别是在性能要求较高的场景中,比如操作系统开发、嵌入式编程和底层系统编程。如果您是初学者,可以从简单的控制台程序开始练习;如果是进阶开发者,可以尝试涉及硬件或网络的项目。 【项目质量】: 所有源码都经过严格测试,可以直接运行。 功能在确认正常工作后才上传。 【适用人群】: 适用于希望学习不同技术领域的小白或进阶学习者。 可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【附加价值】: 项目具有较高的学习借鉴价值,也可直接拿来修改复刻。 对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。 【沟通交流】: 有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。 鼓励下载和使用,并欢迎大家互相学习,共同进步。 # 注意 1. 本资源仅用于开源学习和技术交流。不可商用等,一切后果由使用者承担。 2. 部分字体以及插图等来自网络,若是侵权请联系删除。
IDE护眼主题套件
内容概要:文章详细介绍了基于Matlab/Simulink构建的增程式电动车仿真模型。该模型由电池、电机、发动机、整车动力学、控制策略和驾驶员模块六大组件构成,重点在于各模块间的能量流动逻辑。文中特别强调了功率跟随控制策略,通过PID闭环控制使发动机功率与电池需求动态匹配,优化了燃油经济性和SOC控制精度。此外,模型采用开放式架构,所有参数通过m脚本集中管理,便于修改和扩展。文章展示了模型在典型工况下的性能表现,并突出了其在科研和工程应用中的灵活性和实用性。; 适合人群:对新能源汽车技术感兴趣的工程师、研究人员以及高校相关专业师生。; 使用场景及目标:①用于研究增程式电动车的能量管理策略;②作为教学案例帮助学生理解复杂系统的建模方法;③为实际工程项目提供可复用的仿真平台。; 阅读建议:读者应重点关注模型的架构设计和关键控制算法实现,同时结合提供的代码片段进行实践操作,以便更好地掌握增程式电动车的工作原理及其优化方法。
51a30-main.zip
内容概要:本文详细介绍了多种类型的数据库索引及其应用场景,包括普通索引、唯一性索引、单个索引、复合索引、聚簇索引、非聚簇索引、主索引、外键索引、全文索引和空间索引。每种索引都有其独特的定义、要点和适用场景,并附有具体的SQL代码示例。此外,文章还对比了InnoDB和MyISAM两种存储引擎的特点,解释了脏读、不可重复读、可重复读和幻读的概念,并讨论了SQL优化的方法以及数据库事务的ACID特性。 适合人群:具备一定数据库基础知识的开发者、数据库管理员以及参与数据库设计和优化的技术人员。 使用场景及目标:①帮助开发者选择合适的索引类型以提高查询效率;②理解不同存储引擎的特点,选择最适合应用场景的存储引擎;③掌握事务隔离级别的概念,避免数据不一致问题;④学习SQL优化技巧,提升数据库性能;⑤理解ACID特性,确保数据库操作的一致性和可靠性。 阅读建议:本文内容较为全面且深入,建议读者结合实际项目需求,重点理解不同类型索引的应用场景,掌握SQL优化的基本原则,并熟悉事务处理的最佳实践。
内容概要:本文详细介绍了MATLAB中优化算法的实现方法,涵盖确定性算法(如梯度下降法)和随机性算法(如遗传算法、粒子群优化)。文章首先讲解了梯度下降法和MATLAB优化工具箱的应用,展示了如何使用fmincon解决约束优化问题。接着,文章深入探讨了线性规划、非线性规划和多目标优化的理论和实践,提供了具体的MATLAB代码示例。此外,文中还介绍了遗传算法、粒子群优化和模拟退火算法的原理及应用,并通过实例展示了这些算法在实际问题中的使用。最后,文章讨论了优化算法在工程、金融和机器学习领域的高级应用,以及调试和优化的常见策略。 适合人群:具备一定编程基础,对优化算法感兴趣的工程师、研究人员和学生。 使用场景及目标:①理解优化算法的基础理论和实现方法;②掌握MATLAB优化工具箱的使用,解决线性、非线性、多目标优化问题;③学习遗传算法、粒子群优化和模拟退火算法的具体应用;④提高优化算法的性能和可靠性,解决实际工程、金融和机器学习问题。 阅读建议:本文内容丰富,涉及多种优化算法及其MATLAB实现,建议读者先掌握基本的优化理论和MATLAB编程基础,再逐步深入学习各类算法的具体应用。在学习过程中,结合提供的代码示例进行实践,并尝试调整参数以优化算法性能。
this is for myself learn coding, change a pc debug.
项目资源包含:可运行源码+sql文件 适用人群:学习不同技术领域的小白或进阶学习者;可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 项目具有较高的学习借鉴价值,也可拿来修改、二次开发。 有任何使用上的问题,欢迎随时与博主沟通,博主看到后会第一时间及时解答。 开发语言:Python 框架:django Python版本:python3.8 数据库:mysql 5.7 数据库工具:Navicat 开发软件:PyCharm 浏览器:谷歌浏览器
【项目资源】: 单片机项目适用于从基础到高级的各种项目,特别是在性能要求较高的场景中,比如操作系统开发、嵌入式编程和底层系统编程。如果您是初学者,可以从简单的控制台程序开始练习;如果是进阶开发者,可以尝试涉及硬件或网络的项目。 【项目质量】: 所有源码都经过严格测试,可以直接运行。 功能在确认正常工作后才上传。 【适用人群】: 适用于希望学习不同技术领域的小白或进阶学习者。 可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【附加价值】: 项目具有较高的学习借鉴价值,也可直接拿来修改复刻。 对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。 【沟通交流】: 有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。 鼓励下载和使用,并欢迎大家互相学习,共同进步。 # 注意 1. 本资源仅用于开源学习和技术交流。不可商用等,一切后果由使用者承担。 2. 部分字体以及插图等来自网络,若是侵权请联系删除。
内容概要:本文深入探讨了MMC型STATCOM/SVG的核心技术和调试技巧,重点讲解了载波移相调制(CPS-PWM)和电压均衡控制两大关键技术。载波移相调制通过为每个子模块设置不同的载波相位差,有效降低谐波含量并优化开关频率。电压均衡则分为桥臂内、桥臂间和相间三个层次,分别采用动态排序、比例控制和零序电压注入等方法,确保系统稳定运行。文章还分享了多个实战经验,如低压调试、红外热像仪检测以及避免参数设置不当引发的问题。; 适合人群:从事电力电子领域,特别是参与STATCOM/SVG项目的设计、开发和调试的技术人员。; 使用场景及目标:①理解MMC型STATCOM/SVG的工作原理和技术细节;②掌握载波移相调制的具体实现方法;③学习电压均衡控制的各种策略及其应用场景;④获取实际调试过程中常见问题的解决方案。; 阅读建议:本文涉及大量技术细节和实战经验,建议读者结合实际项目进行阅读,重点关注载波移相调制和电压均衡控制的具体实现,并参考提供的代码片段进行实践。
liangmmm_finalll.scdoc
内容概要:本文详细介绍了Solidity语言的核心概念和语法特性,涵盖结构体、函数修改器、事件、类型系统、数组、映射、操作符、合约可见性、构造函数、抽象合约、接口、继承、控制结构、异常处理和keccak256哈希函数等内容。通过这些知识点的讲解,帮助开发者理解如何构建高效、安全的智能合约。; 适合人群:对区块链开发感兴趣,尤其是希望深入了解以太坊智能合约开发的初学者及有一定编程基础的研发人员。; 使用场景及目标:①掌握Solidity语言的基本语法和高级特性,如结构体、函数修改器、事件等;②理解合约的可见性、继承、接口等面向对象编程特性;③学会使用keccak256等安全机制保障智能合约的安全性;④能够运用控制结构和异常处理编写健壮的合约逻辑。; 阅读建议:建议读者从基础语法开始逐步深入,结合实际案例进行练习。尤其要注意合约的安全性和性能优化,避免常见的漏洞和错误。在学习过程中,应多参考官方文档和其他优质资料,不断巩固和拓展知识体系。