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 删除。

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

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
idea安装激活步骤及工具下载
Idea安装激活步骤及idea下载 第一步:安装idea: 我使用的版本是:IntelliJ IDEA 2018.2.4 x64 Idea下载地址:链接: https://pan.baidu.com/s/1aj2Q1vQ18g2lH_G8J2M9fA 提取码: pfn2 第二步:配置 JetbrainsCrack-3.1-release-enc.jar 下载地址链接: https://pan.baidu.com/s/1aj2Q1vQ18g2lH_G8J2M9fA 提取码: pfn2 bin里面有这个
挑战者
2019/10/14
1.9K0
idea安装激活步骤及工具下载
Visual Studio 2017 “无法查找或打开PDB文件“ 解决方法
我这儿选择使用http://msdl.microsoft.com/download/symbols,然后选择路径。
全栈程序员站长
2022/08/22
6.9K1
Visual Studio 2017 “无法查找或打开PDB文件“ 解决方法
Origin2018安装教程「建议收藏」
Origin 是由OriginLab公司开发的一个科学绘图、数据分析软件,支持在Microsoft Windows下运行,它能支持各种各样的2D/3D图形,其数据分析功能很强大,包括统计,信号处理,曲线拟合以及峰值分析。 Origin 中的曲线拟合是采用基于Levernberg-Marquardt算法(LMA)的非线性最小二乘法拟合,它强大的数据导入功能,支持多种格式的数据,包括ASCII、Excel、NI TDM、DIADem、NetCDF、SPC等等。不仅如此,它的图形输出格式也多种多样,例如JPEG,GIF,EPS,TIFF等,其内置的查询工具还可通过ADO访问数据库数据,是一款绘图的好软件。 以下将介绍Origin 2018版的安装过程(win 10系统)。
全栈程序员站长
2022/07/01
6.5K0
Origin2018安装教程「建议收藏」
Maven添加依赖速度太慢的解决办法
(也可以直接下载我这个:<链接:https://pan.baidu.com/s/1lKI6w0yPycVjnGFuSvS-ww 提取码:oe26 > 复制这段内容后打开百度网盘手机App,操作更方便哦)
悟空宇
2024/03/11
7520
Maven添加依赖速度太慢的解决办法
Mac PyCharm永久激活
链接: https://pan.baidu.com/s/16ZZ9Z0xdWhniqjBmnCXBIw     提取码: 41e4
新人小试
2020/03/30
2.3K0
Mac PyCharm永久激活
当我学python时遇见的问题汇总(持续更新)
PS:一开始我在cmd里面安装过pygame的,但是我用IDLE运行时还是出错,于是只能自己去网上下载来安装
天天Lotay
2022/12/01
6360
当我学python时遇见的问题汇总(持续更新)
电脑c盘满了内存不足怎么办?如何清理c盘空间垃圾
c盘是电脑的心脏,操作系统在里面,而其运行,会产生非常多的垃圾文件,同时不少的软件默认安装在c盘,还有很多系统更新、补丁之类的,自动储存在c盘,因此,如果电脑的c盘分区储存不大的话,很容易就导致c盘接近存满状态,影响电脑运行速度和其他很多操作。C盘空间不足,用着用着电脑c盘满了,会让你的电脑反应速度慢!还容易让系统崩溃!那么c盘内存不足怎么办?电脑c盘满了怎么清理呢?怎样才能解决电脑c盘储存空间变小的问题
雾海梦曦
2022/11/12
4.1K0
电脑c盘满了内存不足怎么办?如何清理c盘空间垃圾
2.1 为gdal添加FileGDB插件
  大家好我是费老师,很多读者朋友跟随着我先前写作的基于geopandas的空间数据分析系列教程文章(快捷访问地址:https://www.cnblogs.com/feffery/tag/geopandas/),掌握了有关geopandas的诸多实用方法,从而更方便地在Python中处理分析GIS数据。其中在文件IO篇中给大家介绍过针对ESRI GeoDataBase格式的文件(也就是大家简称的gdb文件),可以在指定图层名layer参数后进行读取,但无法进行gdb文件的写出操作。
Feffery
2022/10/05
2.8K0
2.1 为gdal添加FileGDB插件
TreeSize:免费的磁盘清理与管理神器,解决C盘爆满的燃眉之急
假如你买了一台新电脑,随着时间的推移,你注意到电脑启动变慢,程序响应也不如以前迅速,打开“我的电脑”,发现C盘的可用空间已经低于10%。那么不用怀疑,就是因为你的C盘空间爆满导致的系统运行缓慢、应用程序性能下降、电脑启动变慢,严重甚至会导致频繁的系统崩溃或者蓝屏。
watermelo37
2025/01/22
2.1K0
TreeSize:免费的磁盘清理与管理神器,解决C盘爆满的燃眉之急
虚拟机vmware安装教程_红帽系统安装步骤
虚拟软件是一个可以使你在一台机器上同时运行二个或更多Windows、LINUX等系统。它可以模拟一个标准PC环境。这个环境和真实的计算机一样,都有芯片组、CPU、内存、显卡、声卡、网卡、软驱、硬盘、光驱、串口、并口、USB控制器等。
全栈程序员站长
2022/09/20
1.3K0
虚拟机vmware安装教程_红帽系统安装步骤
windows服务器Nginx服务化一键安装于部署
  作为一名专业搬砖工,Nginx是我们绕不开的砖头,最近连续部署了几个服务器,Ctrl a + Ctrl v 在飞来飞去,总是会遇到不同不样的问题,通过总结,整理了Nginx服务化的一次完整安装部署笔记,供参考学习。
小小许
2022/11/16
1.4K0
windows服务器Nginx服务化一键安装于部署
Linux系列教程(二)——Linux系统安装(手把手学安装centos6.8)
IT可乐
2018/01/04
2.6K0
Linux系列教程(二)——Linux系统安装(手把手学安装centos6.8)
CentOS 6.8 虚拟机安装详解
IT可乐
2018/01/04
2.5K0
CentOS 6.8 虚拟机安装详解
VScode配置c语言;
VS Code(Visual Studio Code)是一款轻量级的代码编辑器,由微软开发并免费提供。它可在多个操作系统(包括Windows、Mac和Linux)上运行,并提供了丰富的功能和扩展性。
用户10922923
2024/01/23
3580
VScode配置c语言;
【2024全新保姆级教图文教程】三分钟快速安装好Anacaonda3+Pycharm运行Python
首先我们去其官网进行官方版本的相关下载,如下图所示: https://repo.anaconda.com/archive/
程序员洲洲
2024/06/07
1.1K0
【2024全新保姆级教图文教程】三分钟快速安装好Anacaonda3+Pycharm运行Python
Dimension 2020软件下载和安装教程
Adobe Dimension 2020是一款2D和3D设计软件,它可以很容易地制作出高质量的逼真的3D图像,并在环境产品中进行2D和3D视觉资源的合成!该软件为用户提供了一套专业的解决方案,用户可以使用一套专业的工具来处理3D图像的逼真3D图像,并支持处理各种3D广告,以及处理大量艺术品。调节亮度、纹理、对比、色温、壁纸等各种细节!尽管在 Adobe系列中并不是最有名的,但很多行业人士都使用它,让大家可以利用3D工具来制作产品模型,品牌可视化效果,包装设计等。
肉肉软件安装
2023/01/05
3700
Dimension 2020软件下载和安装教程
地表最简单安装MySQL及配置的方法,没有之一
第一步下载我的压缩包 链接:https://pan.baidu.com/s/1EE40dU0j2U1d-bAfj7TeVA 提取码:n25c 复制这段内容后打开百度网盘手机App,操作更方便哦 第二步解压到D盘都放进来看图。
风骨散人Chiam
2020/10/28
6130
安卓漏洞扫描工具_软件漏洞扫描工具
参考链接:Acunetix介绍_「Acunetix Web漏洞扫描中文使用手册」 – 网安
全栈程序员站长
2022/09/29
6.4K0
安卓漏洞扫描工具_软件漏洞扫描工具
虚拟机VirtualBox-5.1安装
VirtualBox 是一款开源虚拟机软件。VirtualBox 是由德国 Innotek 公司开发,由Sun Microsystems公司出品的软件,使用Qt编写,在 Sun 被 Oracle 收买后正式更名成 Oracle VM VirtualBox。Innotek 以 GNU General Public License (GPL) 释出 VirtualBox,并提供二进制版别及 OSE 版别的代码。使用者能够在VirtualBox上装置并且执行Solaris、Windows、DOS、Linux、OS/2 Warp、BSD等系统作为客户端操作系统。现在则由甲骨文公司进行开发,是甲骨文公司xVM虚拟化平台技能的一部份。
申霖
2019/12/27
1.4K0
虚拟机VirtualBox-5.1安装
B4A如何运行在Win11安卓子系统上
在开始菜单,点击Windows Subsystem for Android突变进入子系统进行配置
办公魔盒
2023/03/02
1.8K0
B4A如何运行在Win11安卓子系统上
推荐阅读
相关推荐
idea安装激活步骤及工具下载
更多 >
LV.0
这个人很懒,什么都没有留下~
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档