`
wbj0110
  • 浏览: 1598734 次
  • 性别: Icon_minigender_1
  • 来自: 上海
文章分类
社区版块
存档分类
最新评论

决策树算法

阅读更多

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

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

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

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

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) 对已生成的决策树进行裁剪,减小生成树的规模。

 

1.4 剪枝

 

1)子树置换

2)子树上升

两者都是根据剪枝前与剪枝后的误差估计来决定是否剪枝。

http://blog.csdn.net/whycold/article/details/6555071

 

分享到:
评论

相关推荐

    基于MapReduce实现决策树算法

    基于MapReduce实现决策树算法的知识点 基于MapReduce实现决策树算法是一种使用MapReduce框架来实现决策树算法的方法。在这个方法中,主要使用Mapper和Reducer来实现决策树算法的计算。下面是基于MapReduce实现决策...

    决策树算法及其实现

    决策树算法是数据挖掘和机器学习领域中一个非常重要的分类方法,它通过一系列规则对数据集进行分治,直到每个分支都对应一个单一的类别为止。决策树是基于监督学习方法实现的,这意味着它需要一个事先已标记的数据集...

    Java实现的决策树算法完整实例

    Java实现的决策树算法完整实例 决策树算法是机器学习领域中的一种常见算法,主要用于分类和预测。Java实现的决策树算法完整实例中,主要介绍了决策树的概念、原理,并结合完整实例形式分析了Java实现决策树算法的...

    决策树算法,决策分析

    决策树算法作为一种重要的数据挖掘和机器学习方法,在数据分析领域占据着核心地位。它不仅理论基础扎实,而且在实践应用中展现出高效性和灵活性,被广泛应用于分类、预测、权重确定和规则挖掘等多个方面。 ### 决策...

    数据挖掘决策树算法的国内外研究现状.pdf

    在数据挖掘领域中,决策树算法是一种被广泛应用的分类算法,其在处理非数值型数据和大规模数据集方面表现尤为突出。 国内外对决策树算法的研究主要集中在算法的改进和新算法的提出上。1986年,J.R.Quinlan提出了ID3...

    决策树算法 matlab实现

    决策树算法matlab实现,构造分类决策树并用决策树对模式进行分类识别

    决策树算法PPT详解及其代码 覃秉丰.rar

    决策树算法是机器学习领域中一种简单而有效的监督学习方法,尤其适合于处理分类和回归问题。本资源“决策树算法PPT详解及其代码 覃秉丰.rar”提供了全面的理论讲解和实践代码,是初学者入门以及面试准备的理想资料。...

    实验三 决策树算法实验实验报告.pdf

    本实验报告主要关注的是决策树算法的实践应用,旨在帮助学生理解其分类原理和实现过程。 实验原理基于决策树学习和分类,决策树通过不断选择最优属性进行划分,以最大化信息增益或基尼指数,直到所有样本属于同一...

    机器学习决策树算法中特征选项的算法实现——信息熵

    机器学习决策树算法中特征选项的算法实现——信息熵 首先我们将信息熵的定义进行阐述: 熵经验熵 我们这里以网上数据贷款申请为例:数据来自(https://blog.csdn.net/c406495762/article/details/75663451) 在...

    用python实现决策树算法

    在这个"用Python实现决策树算法"的资料包中,包含的是C4.5决策树和ID3决策树的Python实现,以及用于训练和测试的数据集。 首先,让我们深入理解这两个决策树算法: 1. ID3(Iterative Dichotomiser 3):这是最早...

    Matlab实现决策树算法

    Matlab实现决策树算法,使用ID3_2函数并设计了十指交叉验证,可显示每一次的模型精度。资源提供类一个数据集用于模型训练,将之直接替换为自己的数据即可运行。最终的决策树建立结果以画图的形式表示,并且为每一类...

    《机器学习》算法实例-决策树算法-预测鱼类和非鱼类实例

    《机器学习》算法实例-决策树算法-预测鱼类和非鱼类实例 根据不浮出水面是否可以生存、是否有脚蹼2 个特征,将动物分成两类: 鱼类和非鱼类。 收集数据: 可以使用任何方法 准备数据: 树构造算法(这里使用的是ID3算法...

    决策树和决策树算法简介

    在决策树算法中,ID3(Iterative Dichotomiser 3)是由Ross Quinlan提出的早期决策树算法,主要用于离散属性的数据集。ID3算法的核心是信息增益,即通过计算各个属性划分数据集的信息增益来选择最优的划分属性。信息...

    机器学习决策树算法的Python实现

    决策树算法是机器学习领域中常用的一种模型,尤其在分类问题上表现突出。它通过构建一个树状模型来表示输入特征与输出类别之间的关系。在Python中,我们通常使用scikit-learn库来实现决策树算法,这个库提供了丰富的...

    决策树算法(ID3和C45)

    决策树算法是机器学习领域中常用的一种监督学习方法,它通过构建一棵树状模型来做出一系列决策,最终根据特征值预测目标变量。ID3(Iterative Dichotomiser 3)算法是最早由Ross Quinlan提出的决策树构建算法,而C...

    论文研究-基于决策树算法的设计模式抽取 .pdf

    根据提供的文件内容,本文讨论了基于决策树算法的设计模式抽取的重要性与实现方法。设计模式是软件开发中应用广泛的一种经验总结,它能指导开发者更高效地解决软件设计中常见的问题。设计模式不仅包括架构层面,而且...

    基于决策树算法的遥感影像面向对象分类软件

    我们以AdaBoost和C4.5算法为基础,通过算法改进,创建了适用于遥感影像分类的决策树算法GLC树,并依托C#+ArcEngine平台设计实现了GLC_Info v1.1。该软件以GLC分类器为核心,不仅提供了基于像元的遥感影像分类功能,...

    第三章 决策树算法-2.pdf

    决策树算法与KNN分类算法详解 本文将详细介绍决策树算法和KNN分类算法的基本概念、优缺点、应用场景和实现步骤。 一、决策树算法 决策树是一种常用的机器学习算法,用于对实例进行分类。决策树模型是一种树形结构...

    决策树算法原理详解

    ### 决策树算法原理详解 #### 一、信息熵(Entropy) 信息量是指一个样本或事件所包含的信息量。若一个事件的发生概率较高,则该事件携带的信息量相对较少。例如,“太阳从东方升起”这一事件是确定性的,因此不...

Global site tag (gtag.js) - Google Analytics