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

数据挖掘算法之

决策树算法

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

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

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

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

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”

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

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

欢迎您的意见和建议

算法

编程

数据库

网络安全

数据结构和分析

一体的平台

不仅仅是数据库!

原文发布于微信公众号 - 数据库SQL(SQLdba)

原文发表时间:2016-07-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大数据智能实战

神经网络在关系抽取中的应用

一、关系抽取简介 信息抽取的主要目的是将非结构化或半结构化描述的自然语言文本转化成结构化数据(Structuring),关系抽取是其重要的子任务,主要负责从文本...

27210
来自专栏IT派

玩转TensorFlow深度学习

导语:据介绍,Google Developers Codelabs 提供了有引导的、教程式的和上手式的编程体验。大多数 Codelabs 项目都能帮助你了解开发...

3488
来自专栏AI研习社

Must Know! 数据科学家们必须知道的 5 种聚类算法

聚类是一种关于数据点分组的机器学习技术。给出一组数据点,我们可以使用聚类算法将每个数据点分类到特定的组中。理论上,同一组中的数据点应具有相似的属性或特征,而不同...

3938
来自专栏数据科学学习手札

(数据科学学习手札40)tensorflow实现LSTM时间序列预测

  上一篇中我们较为详细地铺垫了关于RNN及其变种LSTM的一些基本知识,也提到了LSTM在时间序列预测上优越的性能,本篇就将对如何利用tensorflow,在...

3764
来自专栏AI研习社

机器学习小窍门:Python 帮你进行特征选择

特征选择,也就是从数据集中找出并选择最有用特征的过程,是机器学习工作流中一个非常重要的步骤。不必要的特征降低了训练速度,降低了模型的可解释性,最重要的是降低了测...

853
来自专栏人工智能

基于TensorFlow生成抽象纹理

来源:otoro 编译:weakish 编者按:Google Brain机器学习开发者hardmu使用TensorFlow,基于CPPN网络生成了许多有趣的高分...

5348
来自专栏深度学习自然语言处理

TreeLSTM Sentiment Classification

昨天的周日讨论班讲的是TreeLSTM Sentiment Classification,主讲人:王铭涛 今天我来做一下总结。 下面的图片来自于 王铭涛的ppt...

39411
来自专栏人工智能

【机器学习】彻底搞懂CNN

作者:水奈樾人工智能爱好者 博客专栏:http://www.cnblogs.com/rucwxb/ 上世纪科学家们发现了几个视觉神经特点,视神经具有局部感受野,...

49710
来自专栏深度学习自然语言处理

机器学习之多层感知机理论与实践

阅读大概需要10分钟 作者 Lefteris 翻译 bluepomelo 编辑 zenRRan 有修改 原文链接 http://blog.refu.co/?p=...

4024
来自专栏ATYUN订阅号

深度实践:如何用神经网络给黑白照片着色

现如今,将图片彩色化是通常用Photoshop处理的。一幅作品有时候需要用一个月的时间来着色。可能单单一张脸就需要20层的粉色、绿色和蓝色阴影才能让它看起来恰到...

2857

扫码关注云+社区