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

数据挖掘算法之

决策树算法

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

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

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

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

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 条评论
登录 后参与评论

相关文章

来自专栏量化投资与机器学习

【深入研究】使用RNN预测股票价格系列二

接昨天的 系列一(可点击查看) 在系列一的教程中,我们想继续有关股票价格预测的主题,并赋予在系列1中建立的具有对多个股票做出响应能力的RNN。 为了区分不同价格...

2798
来自专栏PaddlePaddle

【排序学习】基于Pairwise和Listwise的排序学习

导语 PaddlePaddle提供了丰富的运算单元,帮助大家以模块化的方式构建起千变万化的深度学习模型来解决不同的应用问题。这里,我们针对常见的机器学习任务,提...

1.3K8
来自专栏深度学习计算机视觉

数据挖掘之数据预处理学习笔记数据预处理目的主要任务

数据预处理目的 保证数据的质量,包括确保数据的准确性、完整性和一致性 主要任务 数据清理 填写缺失的值、光滑噪声数据、识别或者删除离群的点,先解决这些脏数据,否...

2633
来自专栏小鹏的专栏

01 TensorFlow入门(2)

Working with Matrices:         了解TensorFlow如何使用矩阵对于通过计算图理解数据流非常重要。 Getting read...

2356
来自专栏量化投资与机器学习

CNN预测股票走势基于Tensorflow(思路+程序)

前言 我们希望找出跟随价格上涨的模式。通过每日收盘价,MA,KD,RSI,yearAvgPrice 本次推文研究只是展示深入学习的一个例子。 结果估计不是很好。...

2K7
来自专栏人工智能

构建基于JAVA的朴素贝叶斯文本分类器

在前面的文章中,我们讨论了朴素贝叶斯文本分类器的理论背景以及在文本分类中使用特征选择技术的重要性。在本文中,我们将结合两种方法,用JAVA简单实现朴素贝叶斯文本...

3966
来自专栏iOSDevLog

Python机器学习:Scikit-Learn教程

一个易于理解的scikit-learn教程,可以帮助您开始使用Python机器学习。

2655
来自专栏机器之心

教程 | 维度、广播操作与可视化:如何高效使用TensorFlow

选自GitHub 机器之心编译 参与:Nurhachu Null、李泽南 本文从 Tensorflow 基础、理解静态维度和动态维度、广播操作(Broading...

4215
来自专栏racaljk

中文分词基本算法主要分类

基于词典的方法、基于统计的方法、基于规则的方法、(传说中还有基于理解的-神经网络-专家系统)

994
来自专栏移动开发面面观

你需要知道的数学知识——卷积

1293

扫码关注云+社区