Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >数据挖掘算法之决策树算法

数据挖掘算法之决策树算法

作者头像
赵腰静
发布于 2018-03-09 07:02:27
发布于 2018-03-09 07:02:27
8490
举报
文章被收录于专栏:程序猿程序猿

数据挖掘算法之

决策树算法

机器学习中,决策树是一个预测模型;它代表的是对象属性值与对象值之间的一种映射关系。树中每个节点表示某个对象,每个分叉路径则代表的某个可能的属性值,而每个叶结点则对应具有上述属性值的子对象。决策树仅有单一输出;若需要多个输出,可以建立独立的决策树以处理不同输出。

从数据产生决策树的机器学习技术叫做决策树学习, 通俗说就是决策树。

决策树学习也是数据挖掘中一个普通的方法。在这里,每个决策树都表述了一种树型结构,它由它的分支来对该类型的对象依靠属性进行分类。每个决策树可以依靠对源数据库的分割进行数据测试。这个过程可以递归式的对树进行修剪。当不能再进行分割或一个单独的类可以被应用于某一分支时,递归过程就完成了。另外,随机森林分类器将许多决策树结合起来以提升分类的正确率。

决策树同时也可以依靠计算条件概率来构造。决策树如果依靠数学的计算方法可以取得更加理想的效果。

1.1 决策树的工作原理

决策树一般都是自上而下的来生成的。

选择分割的方法有多种,但是目的都是一致的,即对目标类尝试进行最佳的分割。

从根节点到叶子节点都有一条路径,这条路径就是一条“规则”。

决策树可以是二叉的,也可以是多叉的。

对每个节点的衡量:

1) 通过该节点的记录数;

2) 如果是叶子节点的话,分类的路径;

3) 对叶子节点正确分类的比例。

有些规则的效果可以比其他的一些规则要好。

1.2 ID3算法

1.2.1 概念提取算法CLS

1) 初始化参数C={E},E包括所有的例子,为根;

2) 如果C中的任一元素e同属于同一个决策类则创建一个叶子节点YES终止;否则依启发式标准,选择特征Fi={V1, V2, V3,……, Vn}并创建判定节点,划分C为互不相交的N个集合C1,C2,C3,……,Cn;

3) 对任一个Ci递归。

1.2.2 ID3算法

1) 随机选择C的一个子集W (窗口);

2) 调用CLS生成W的分类树DT(强调的启发式标准在后);

3) 顺序扫描C搜集DT的意外(即由DT无法确定的例子);

4) 组合W与已发现的意外,形成新的W;

5) 重复2)到4),直到无例外为止。

启发式标准:

只跟本身与其子树有关,采取信息理论用熵来量度。

熵是选择事件时选择自由度的量度,其计算方法为:P=freq(Cj,S)/|S|;INFO(S)=-SUM(P*LOG(P));SUM()函数是求j从1到n的和。Gain(X)=Info(X)-Infox(X);Infox(X)=SUM( (|Ti|/|T|)*Info(X);

为保证生成的决策树最小,ID3算法在生成子树时,选取使生成的子树的熵(即Gain(S))最小的特征来生成子树。

ID3算法对数据的要求:

1) 所有属性必须为离散量;

2) 所有的训练例的所有属性必须有一个明确的值;

3) 相同的因素必须得到相同的结论且训练例必须唯一。

1.3 C4.5算法

由于ID3算法在实际应用中存在一些问题,于是Quilan提出了C4.5算法,严格上说C4.5只能是ID3的一个改进算法。

C4.5算法继承了ID3算法的优点,并在以下几方面对ID3算法进行了改进:

1) 用信息增益率来选择属性,克服了用信息增益选择属性时偏向选择取值多的属性的不足;

2) 在树构造过程中进行剪枝;

3) 能够完成对连续属性的离散化处理;

4) 能够对不完整数据进行处理。

C4.5算法有如下优点:

产生的分类规则易于理解,准确率较高。

C4.5算法有如下缺点:

在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,因而导致算法的低效。此外,C4.5只适合于能够驻留于内存的数据集,当训练集大得无法在内存容纳时程序无法运行。

分类决策树算法:

C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法。

分类决策树算法是从大量事例中进行提取分类规则的自上而下的决策树。

决策树的各部分是:

根:学习的事例集;

枝:分类的判定条件;

叶:分好的各个类。

1.3.1 C4.5对ID3算法的改进:

1) 熵的改进,加上了子树的信息。

Split_Infox(X)= -SUM( (|T|/|Ti|)*LOG(|Ti|/|T|));

Gain ratio(X)= Gain(X)/Split_Infox(X);

2) 在输入数据上的改进

① 因素属性的值可以是连续量,C4.5对其排序并分成不同的集合后按照ID3算法当作离散量进行处理,但结论属性的值必须是离散值。

② 训练例的因素属性值可以是不确定的,以?表示,但结论必须是确定的。

3) 对已生成的决策树进行裁剪,减小生成树的规模。

后面还有贝叶斯、邻近算法、人工神经网络等等。未完待续

扫一下下方二维码关注“数据库SQL”

打造数据库爱好者的学习之地

我们在不断的探索新的模式

欢迎您的意见和建议

算法

编程

数据库

网络安全

数据结构和分析

一体的平台

不仅仅是数据库!

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2016-07-15,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 数据库SQL 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
机器学习之决策树(Decision Tree)及其Python代码实现
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/article/details/54927178
大黄大黄大黄
2018/09/14
2.6K0
机器学习之决策树(Decision Tree)及其Python代码实现
机器学习--决策树算法
在生活中,“树”这一模型有很广泛的应用,事实证明,它在机器学习分类和回归领域也有着深刻而广泛的影响。在决策分析中,决策树可以明确直观的展现出决策结果和决策过程。如名所示,它使用树状决策模型。它不仅仅是在数据挖掘中用户获取特定目标解的策略,同时也被广泛的应用于机器学习。
Kindear
2021/10/26
6690
机器学习笔记之决策树分类Decision Tree
决策树(decision tree)是一种依托于策略抉择而建立起来的树。机器学习中,决策树是一个预测模型;他代表的是对象属性与对象值之间的一种映射关系。 树中每个节点表示某个对象,而每个分叉路径则代表的某个可能的属性值,从根节点到叶节点所经历的路径对应一个判定测试序列。决策树可以是二叉树或非二叉树,也可以把他看作是 if-else 规则的集合,也可以认为是在特征空间上的条件概率分布。决策树在机器学习模型领域的特殊之处,在于其信息表示的清晰度。决策树通过训练获得的 “知识”,直接形成层次结构。这种结构以这样的方式保存和展示知识,即使是非专家也可以很容易地理解。
Jetpropelledsnake21
2021/03/12
4K0
机器学习笔记之决策树分类Decision Tree
决策树算法:ID3,C4.5,CART
对于基本树我将大致从以下四个方面介绍每一个算法:思想、划分标准、剪枝策略,优缺点。
zhangjiqun
2024/12/14
2790
决策树算法:ID3,C4.5,CART
三种决策树算法(ID3, CART, C4.5)及Python实现
决策树是属于机器学习监督学习分类算法中比较简单的一种,决策树是一个预测模型;他代表的是对象属性与对象值之间的一种映射关系。
YingJoy_
2018/03/11
21.9K2
三种决策树算法(ID3, CART, C4.5)及Python实现
【算法】决策树与ID3算法
小编邀请您,先思考: 1 如何构建决策树? 2 决策树适合解决什么问题? 1. 什么是决策树/判定树(decision tree)? 决策树(Decision Tree)算法是机器学习(Machine
陆勤_数据人网
2018/03/27
1.3K0
【算法】决策树与ID3算法
决策树算法原理(上)
    决策树算法在机器学习中算是很经典的一个算法系列了。它既可以作为分类算法,也可以作为回归算法,同时也特别适合集成学习比如随机森林。本文就对决策树算法原理做一个总结,上篇对ID3, C4.5的算法思想做了总结,下篇重点对CART算法做一个详细的介绍。选择CART做重点介绍的原因是scikit-learn使用了优化版的CART算法作为其决策树算法的实现。
刘建平Pinard
2018/08/14
6660
决策树算法原理(上)
机器学习--决策树算法(CART)
​ 我们知道,在ID3算法中我们使用了信息增益来选择特征,信息增益大的优先选择。在C4.5算法中,采用了信息增益比来选择特征,以减少信息增益容易选择特征值多的特征的问题。但是无论是ID3还是C4.5,都是基于信息论的熵模型的,这里面会涉及大量的对数运算。能不能简化模型同时也不至于完全丢失熵模型的优点呢?有!CART分类树算法使用基尼系数 来代替信息增益比,基尼系数代表了模型的不纯度,基尼系数越小,则不纯度越低,特征越好。这和信息增益(比)是相反的。
Kindear
2021/11/24
1.1K0
机器学习--决策树算法(CART)
【数据挖掘】决策树算法简介 ( 决策树模型 | 模型示例 | 决策树算法性能要求 | 递归创建决策树 | 树根属性选择 )
1 . 决策树 : 决策时基于 “树” 结构 , 这也是模拟人在进行决策时采用的策略 ;
韩曙亮
2023/03/27
2.8K0
【数据挖掘】决策树算法简介 ( 决策树模型 | 模型示例 | 决策树算法性能要求 | 递归创建决策树 | 树根属性选择 )
【机器学习】决策树
本文介绍了 ID3,C4.5,CART三种基本的决策树模型。首先介绍了决策树的特征选择,包括信息增益,信息增益率、基尼指数、最小均方差分别对应分类树ID3、C4.5、CART、回归树CART。然后介绍了决策树建树的一般流程、对比分类树和回归树建树的区别。最后介绍了树模型中避免过拟合问题的剪枝方法,包括前剪枝和后剪枝。
yuquanle
2020/04/01
7120
【机器学习】决策树
决策树(Decision Tree)C4.5算法
C4.5,是机器学习算法中的另一个分类决策树算法,它是决策树(决策树也就是做决策的节点间的组织方式像一棵树,其实是一个倒树)核心算法,也是上节所介绍的ID3的改进算法,所以基本上了解了一半决策树构造方法就能构造它。
Ai学习的老章
2019/04/08
1.8K0
决策树(Decision Tree)C4.5算法
C4.5决策树及CART决策树
信息增益比本质: 是在信息增益的基础之上乘上一个惩罚参数。特征个数较多时,惩罚参数较小;特征个数较少时,惩罚参数较大。惩罚参数:数据集D以特征A作为随机变量的熵的倒数。
用户10950404
2024/07/30
1690
C4.5决策树及CART决策树
决策树理论
在决策树理论中,有这样一句话,“用较少的东西,照样可以做很好的事情。越是小的决策树,越优于大的决策树”。数据分类是一个两阶段过程,包括模型学习阶段(构建分类模型)和分类预测阶段(使用模型预测给定数据的类标号)。决策树分类算法属于监督学习(Supervised learning),即样本数据中有类别标号。下面是两个阶段的简单描述:
用户1359560
2018/11/12
1.1K0
决策树之ID3、C4.5、C5.0等五大算法及python实现
版权声明:博主原创文章,微信公众号:素质云笔记,转载请注明来源“素质云博客”,谢谢合作!! https://blog.csdn.net/sinat_26917383/article/details/47617801
悟乙己
2019/05/28
2.7K0
机器学习 | 决策树模型(一)理论
决策树(Decision tree)是一种基本的分类与回归方法,是一种非参数的有监督学习方法。
数据STUDIO
2021/06/24
1.6K0
[机器学习算法]决策树引论和CART算法
决策树decision tree分类法是一种简单但广泛使用的分类技术。以是否贷款违约的二分类问题为例,当我们希望根据给定的训练集习得一个模型对新出现的贷款人进行分类时,经常需要从大量的贷款申请单中识别出来哪些贷款人是劣质的贷款人(容易拖欠贷款)。想象一下客户经理和助手针对一个贷款者进行的如下对话:
TOMOCAT
2020/06/09
7020
[机器学习算法]决策树引论和CART算法
机器学习17:决策树模型
决策树分为两大类:分类树和回归树,分类树用于分类标签值,回归树用于预测连续值,常用算法有ID3、C4.5、CART等。
用户5473628
2019/08/08
9820
机器学习17:决策树模型
MADlib——基于SQL的数据挖掘解决方案(24)——分类之决策树
决策树(Decision Tree)又称为分类树(Classification Tree),是最为广泛的归纳推理算法之一,处理类别型或连续型变量的分类预测问题,可以用图形和if-then的规则表示模型,可读性较高。决策树模型通过不断地划分数据,使因变量的差别最大,最终目的是将数据分类到不同的组织或不同的分枝,在因变量的值上建立最强的归类。
用户1148526
2019/05/25
1.2K0
决策树的构建 -- ID3 与 C4.5 算法
在系统流程图中,我们常常会构建决策树,例如上面的例子是一个简单的用于动物分类的专家系统,是一个典型的树状结构。 决策树通常用来处理数值型或标称型数据,它用来预测对象属性与对象值之间的关系。
用户3147702
2022/06/27
1.2K0
决策树的构建 -- ID3 与 C4.5 算法
决策树学习笔记(二):剪枝,ID3,C4.5
推荐导读:本篇为树模型系列第二篇,旨在从最简单的决策树开始学习,循序渐进,最后理解并掌握复杂模型GBDT,Xgboost,为要想要深入了解机器学习算法和参加数据挖掘竞赛的朋友提供帮助。
1480
2019/07/15
1.5K0
决策树学习笔记(二):剪枝,ID3,C4.5
推荐阅读
相关推荐
机器学习之决策树(Decision Tree)及其Python代码实现
更多 >
LV.1
这个人很懒,什么都没有留下~
作者相关精选
交个朋友
加入腾讯云官网粉丝站
蹲全网底价单品 享第一手活动信息
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档