分类算法——决策树——经典算法比较

标签: 分类 算法 决策树 | 发表时间:2014-03-20 11:23 | 作者:wokao159
出处:http://www.iteye.com

决策树是以实例为基础的归纳学习算法。它从一组无次序、无规则的元组中推理出决策树表示形式的分类规则。它采用自顶向下的递归方式,在决策树的内部结点进行属性值的比较,并根据不同的属性值从该结点向下分支,叶结点是要学习划分的类。从根到叶结点的一条路径就对应着一条合取规则,整个决策树就对应着一组析取表达式规则。

       1986年Quinlan提出了著名的ID3算法。在ID3算法的基础上,1993年Quinlan又提出了C4.5算法。为了适应处理大规模数据集的需要,后来又提出了若干改进的算法,其中SLIQ (super-vised learning in quest)和SPRINT (scalable parallelizableinduction of decision trees)是比较有代表性的两个算法。

 

  (1) ID3 算法

ID3算法的核心是:在决策树各级结点上选择属性时,用信息增益(information gain)作为属性的选择标准,以使得在每一个非叶结点进行测试时,能获得关于被测试记录最大的类别信息。其具体方法是:检测所有的属性,选择信息增益最大的属性产生决策树结点,由该属性的不同取值建立分支,再对各分支的子集递归调用该方法建立决策树结点的分支,直到所有子集仅包含同一类别的数据为止。最后得到一棵决策树,它可以用来对新的样本进行分类。

 

ID3算法的优点是:

算法的理论清晰,方法简单,学习能力较强。其缺点是:只对比较小的数据集有效,且对噪声比较敏感,当训练数据集加大时,决策树可能会随之改变。

 

(2) C4.5算法

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

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

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

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

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

 

C4.5算法与其它分类算法如统计方法、神经网络等比较起来有如下优点:产生的分类规则易于理解,准确率较高。其缺点是:在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,因而导致算法的低效。此外,C4.5只适合于能够驻留于内存的数据集,当训练集大得无法在内存容纳时程序无法运行。

 

(3) SLIQ算法

SLIQ算法对C4.5决策树分类算法的实现方法进行了改进,在决策树的构造过程中采用了“预排序”和“广度优先策略”两种技术。

1) 预排序。对于连续属性在每个内部结点寻找其最优分裂标准时,都需要对训练集按照该属性的取值进行排序,而排序是很浪费时间的操作。为此,SLIQ算法采用了预排序技术。所谓预排序,就是针对每个属性的取值,把所有的记录按照从小到大的顺序进行排序,以消除在决策树的每个结点对数据集进行的排序。具体实现时,需要为训练数据集的每个属性创建一个属性列表,为类别属性创建一个类别列表。

 

2) 广度优先策略。在C4.5算法中,树的构造是按照深度优先策略完成的,需要对每个属性列表在每个结点处都进行一遍扫描,费时很多,为此,SLIQ采用广度优先策略构造决策树,即在决策树的每一层只需对每个属性列表扫描一次,就可以为当前决策树中每个叶子结点找到最优分裂标准。

SLIQ算法由于采用了上述两种技术,使得该算法能够处理比C4.5大得多的训练集,在一定范围内具有良好的随记录个数和属性个数增长的可伸缩性。

 

然而它仍然存在如下缺点:

1)由于需要将类别列表存放于内存,而类别列表的元组数与训练集的元组数是相同的,这就一定程度上限制了可以处理的数据集的大小。

2) 由于采用了预排序技术,而排序算法的复杂度本身并不是与记录个数成线性关系,因此,使得SLIQ算法不可能达到随记录数目增长的线性可伸缩性。

 

(4) SPRINT算法

为了减少驻留于内存的数据量,SPRINT算法进一步改进了决策树算法的数据结构,去掉了在SLIQ中需要驻留于内存的类别列表,将它的类别列合并到每个属性列表中。这样,在遍历每个属性列表寻找当前结点的最优分裂标准时,不必参照其他信息,将对结点的分裂表现在对属性列表的分裂,即将每个属性列表分成两个,分别存放属于各个结点的记录。

 

 SPRINT算法的优点是在寻找每个结点的最优分裂标准时变得更简单。其缺点是对非分裂属性的属性列表进行分裂变得很困难。解决的办法是对分裂属性进行分裂时用哈希表记录下每个记录属于哪个孩子结点,若内存能够容纳下整个哈希表,其他属性列表的分裂只需参照该哈希表即可。由于哈希表的大小与训练集的大小成正比,当训练集很大时,哈希表可能无法在内存容纳,此时分裂只能分批执行,这使得SPRINT算法的可伸缩性仍然不是很好。

 

 

本文转自: http://blog.csdn.net/Duke147/article/details/21622317



已有 0 人发表留言,猛击->> 这里<<-参与讨论


ITeye推荐



相关 [分类 算法 决策树] 推荐:

分类算法——决策树——经典算法比较

- - 数据库 - ITeye博客
决策树是以实例为基础的归纳学习算法. 它从一组无次序、无规则的元组中推理出决策树表示形式的分类规则. 它采用自顶向下的递归方式,在决策树的内部结点进行属性值的比较,并根据不同的属性值从该结点向下分支,叶结点是要学习划分的类. 从根到叶结点的一条路径就对应着一条合取规则,整个决策树就对应着一组析取表达式规则.

[原]从决策树学习谈到贝叶斯分类算法

- - 结构之法 算法之道
    第一篇:从决策树学习谈到贝叶斯分类算法.     最近在面试中,除了基础 &  算法 & 项目之外,经常被问到或被要求介绍和描述下自己所知道的几种分类或聚类算法,而我向来恨对一个东西只知其皮毛而不得深入,故写一个有关聚类 & 分类算法的系列文章以作为自己备试之用(尽管貌似已无多大必要,但还是觉得应该写下以备将来常常回顾思考).

使用ID3算法构造决策树

- - 四火的唠叨
文章系本人原创,转载请保持完整性并注明出自 《四火的唠叨》. 决策树是一个预测模型,它代表的是对象属性与对象值之间的一种映射关系. 树中每个节点表示某个对象,而每个分叉路径则代表的某个可能的属性值,而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值. 这张图很好地解释了决策树:. 例子中可以找到两层的分类依据属性,第一层是晴/阴/雨,第二层是是否潮湿和是否刮风,分类依据的确定和先后顺序对决策树的质量有决定性的影响.

决策树仍是最好的数据挖掘算法

- 无藏 - 36氪
决策树仍是最好的数据挖掘算法:理由如下:. 决策树是白箱「white box」,意味着可以生成简单易懂的规则. 你可以通过查看决策树清楚明白各个分支,明白某个分支的影响,并且将其和其他分支进行对比. 决策树术为非参数「non-parametric」,意味着无需特定的数据分流. 决策树可以轻松应对连续变量和类别变量.

分类算法概述。

- - 小彰
摘 要:分类是数据挖掘、机器学习和模式识别中一个重要的研究领域. 通过对当前数据挖掘中具有代表性的优秀分类算法进行分析和比较,总结出了各种算法的特性,为使用者选择算法或研究者改进算法提供了依据. 分类的目的是根据数据集的特点构造一个分类函数或分类模型(也常常称作分类器),该模型能把未知类别的样本映射到给定类别中的某一个.

数据挖掘 - 分类算法比较

- - IBM developerWorks 中国 : 文档库
随着计算能力、存储、网络的高速发展,人类积累的数据量正以指数速度增长. 对于这些数据,人们迫切希望从中提取出隐藏其中的有用信息,更需要发现更深层次的规律,对决策,商务应用提供更有效的支持. 为了满足这种需求,数据挖掘技术的得到了长足的发展,而分类在数据挖掘中是一项非常重要的任务,目前在商业上应用最多.

[转载]基于贝叶斯算法的文本分类算法

- - 小蚊子乐园
原文地址: 基于贝叶斯算法的文本分类算法 作者: TBKKEN.     因为要做一个关于数据挖掘的算法应用PPT,虽然知道很多数据挖掘的算法怎么使用,但是需要讲解它们的原理,还真的需要耗费很多精力,之前做一个曲线拟合,已经发在博客里,现在做贝叶斯算法的基础原理. 分类是把一个事物分到某个类别中.

Naïve Bayes分类算法在Hadoop上的实现

- Roger - 董的博客
Naïve Bayes算法介绍. Naïve Bayes是一个简单有效的分类算法,已经得到广泛使用. 本文讨论了海量数据(TB级)下Naïve Bayes算法的实现方法,并给出了Hadoop上的实现方案. Naïve Bayes算法介绍. 朴素贝叶斯分类器基于一个简单的假定: 在给定目标值时属性值之间相互独立, 即特征对于给定类的影响独立于其它特征.

Tree Based Classification 基于树的分类算法

- - xlvector
非线性分类问题向来是分类问题中最有挑战性的问题,这主要是因为线性分类问题已经可以完美的解决了. 解决非线性分类问题基本有如下的思路:. 非线性Kernel的SVM:其实是将原空间的非线性分类问题转化成了距离空间的线性分类问题. Mixture Model : 这种其实只能解决一类特殊的非线性分类问题,即样本分成不同的簇,而不同的簇有不同的类标.

机器学习的分类与主要算法对比

- - CSDN博客综合推荐文章
重要引用: Andrew Ng Courera Machine Learning; 从机器学习谈起; 关于机器学习的讨论; 机器学习常见算法分类汇总; LeNet Homepage; pluskid svm.   首先让我们瞻仰一下当今机器学习领域的执牛耳者:.   这幅图上的三人是当今机器学习界的执牛耳者.