决策树算法综述（共8篇）
决策树算法综述 篇1
1 概述
决策树是构建人工智能系统的主要方法之一, 随着数据挖掘技术在商业智能等方面的应用, 决策树技术将在未来发挥越来越强大的作用[1]。自从Quinlan在1979年提出构造决策树ID3算法以来, 决策树的实现已经有很多算法, 常见的有:CLS (concept learning system) 学习算法, ID4、ID5R、C4.5算法, 以及CART、C5.0、Fuzzy C4.5、0C1、QUEST和CAL5等[2]。
现在, 许多学者在规则学习与决策树学习的结合方面, 做了大量的研究工作。Brako等的ASSISTANT, 将AQ15中的近似匹配方法引入决策树中。Clark等的CN2, 将ID3算法和AQ算法编织在一起, 用户可选择其中任何一种算法使用。Utgoff等的ID5R算法, 不要求一次性提供所有的训练实例, 训练实例可以逐次提供, 生成的决策树逐次精化, 以支持增量式学习。洪家荣教授结合实际应用问题对ID3算法作了一些改进, 提出了两个ID3和AQ结合的改进算法, IDAQ和AQID, 此外, 还陆续出现了处理大规模数据集的决策树算法, 如SLIQ, SPRINT等等[3]。
2 决策树算法研究
2.1 构造决策树算法
决策树学习是从无次序、无规则的样本数据集中推理出决策树表示形式、逼近离散值目标函数的分类规则方法。它采用自顶向下的递归方式, 在决策树的内部结点进行属性值的比较并根据不同的属性值判断从该结点向下的分支, 在决策树的叶结点得到结论, 因此从根结点到叶结点的一条路径就对应着一条规则, 整棵决策树就对应着一组表达式规则。我们可将决策树看成是定义布尔函数的一种方法。其输入是一组属性描述的对象, 输出为yes/no决策。决策树代表一个假设, 可以写成逻辑公式。决策树的表达能力限于命题逻辑, 该对象的任一个属性的任一次测试均是一个命题。在命题逻辑范围内, 决策树的表达能力是完全的。一棵决策树可以代表一个决定训练例集分类的决策过程, 树的每个结点对应于一个属性名或一个特定的测试, 该测试在此结点根据测试的可能结果对训练例集进行划分。划分出的每个部分都对应于相应训练例集子空间的一个分类子问题, 该分类子问题可以由一棵决策树来解决。因此, 一棵决策树可以看作是一个对目标分类的划分和获取策略[4]。
2.2 处理大规模数据集的决策树算法
ID3或者C4.5算法都是在建树时将训练集一次性装载入内存的。但当面对大型的有着上百万条纪录的数据库时, 就无法实际应用这些算法。针对这一问题, 前人提出了不少改进方法, 如数据采样法、连续属性离散化法或将数据分为若干小块分别建树然后综合成一个最终的树, 但这些改进都以降低了树的准确性为代价。直到Metha, Agrawal和Rissane在1996年提出了SLIQ方法, 以及在此基础上进行改进得到的SPRINT[6]方法。
3 决策树学习的常见问题
3.1 过度拟合
在利用决策树归纳学习时, 需要事先给定一个假设空间, 且必须在这个假设空间中选择一个, 使之与训练实例集相匹配。我们知道任何一个学习算法不可能在没有任何偏置的情况下学习。如果事先知道所要学习的函数属于整个假设空间中的一个很小的子集, 那么即使训练实例不完整, 也有可能从已有的训练实例集中学习到有用的假设, 使它对未来的实例进行正确的分类。当然, 我们往往无法事先知道所要学习的函数属于整个假设空间中的哪个很小的子集, 即使是知道, 我们还是希望有一个大的训练实例集。因为训练实例集越大, 关于分类的信息就越多。这时, 即使随机地从与训练实例集相匹配的假设集中选择一个, 它也能对未知实例的分类进行预测。相反, 如果训练实例集与整个假设空间相比过小, 即使在有偏置的情况下, 仍有过多的假设与训练实例集相匹配, 这时作出假设的泛化能力将很差。当有过多的假设与训练实例集相匹配, 便称为过度拟合 (overfit) 。
3.2 树剪枝
对决策树进行修剪可以控制决策树的复杂程度, 避免决策树过于复杂和庞大。此外, 还可以解决过度拟合的问题。
修剪决策树有多种算法, 通常分为这样五类。最为常用的是通过预剪枝 (pre-pruning) 和后剪枝 (post-pruning) 完成, 或逐步调整树的大小;其次是扩展测试集方法, 首先按特征构成是数据驱动还是假设驱动的差别, 将建立的特征组合或分割, 然后在此基础上引进多变量测试集。第三类方法包括选择不同的测试集评价函数, 通过改善连续特征的描述或修改搜索算法本身实现;第四类方法使用数据库约束, 即通过削减数据库或实例描述特征集来简化决策树;第五类方法是将决策树转化成另一种数据结构。这些方法通常可以在同另一种算法相互结合中, 增强各自的功能。
4 决策树在工程中的应用
决策树在工程中的诸多领域获得了非常广泛的应用, 主要有以下几个方面:
4.1 决策树技术应用于机器人导航
E.Swere和D.J.Mulvaney将决策树技术应用于移动机器人导航并取得了一定的成功。
4.2 决策树技术应用于地铁中的事故处理
法国的Brezillon等人成功地将决策树技术应用于地铁交通调度智能系统。他们根据决策树的基本思想开发出上下文图表来帮助驾驶员针对事故做出正确的处理。
4.3 决策树技术应用于图像识别
决策树技术应用于包括图像在内的科学数据分析。如利用决策树对上百万个天体进行分类, 利用决策树对卫星图像进行分析以估计落叶林和针叶林的基部面积值。
4.4 决策树应用于制造业
决策树技术已经成功应用于焊接质量的检测以及大规模集成电路的设计, 它不仅可以规划印刷电路板的布线, 波音公司甚至将它用于波音飞机生产过程的故障诊断以及质量控制。
5 决策树技术面临的问题和挑战
发展至今, 决策树技术面临的问题和挑战表现在以下几个方面:
5.1 决策树方法的效率亟待提高
数据挖掘面临的数据往往是海量的, 对实时性要求较高的决策场所, 数据挖掘方法的主动性和快速性显得日益重要。应用实时性技术、主动数据库技术和分布并行算法设计技术等现代计算机先进技术, 是数据挖掘方法实用化的有效途径。
5.2 适应多数据类型、容噪的决策树挖掘方法
随着计算机网络和信息的社会化, 数据挖掘的对象已不是关系数据库模型, 而是分布、异构的多类型数据库, 数据的非结构化程度、噪声等现象越来越突出, 这也是决策树技术面临的困难问题。
6 结论
决策树技术早已被证明是利用计算机模仿人类决策的有效方法, 已经得到广泛的应用, 并且已经有了许多成熟的系统。但是, 解决一个复杂的数据挖掘问题的任何算法都要面临以下问题:从错误的数据中学习、从分布的数据中学习、从有偏的数据中学习、学习有弹性的概念、学习那些抽象程度不同的概念、整合定性与定量的发现等, 因此, 还有很多未开发的课题等待研究。若将决策树技术与其他新兴的技术相结合, 决策树技术将焕发出新的生命力。
摘要：决策树分类学习算法是使用广泛、实用性很强的归纳推理方法之一, 在机器学习、数据挖掘等人工智能领域有相当重要的理论意义与实用价值。在详细阐述决策树技术的几种典型算法以及它的一些常见问题后, 介绍了它在工程上的实际应用, 最后提出了它的研究方向以及它所面临的问题和挑战。
关键词：决策树,决策树算法,ID3,C4.5,SLIQ,SPRINT
参考文献
[1]J Han, M Kamber.范明, 孟小峰, 等译.数据挖掘:慨念与技术[M].北京:机械工业出版社, 2001.
[2]史忠植.知识发现[M].北京:清华大学出版社, 2002.1.
[3]王珏, 石纯一.机器学习研究[J].广西师范大学学报 (自然科学版) .June2003.Vol.21, Issue 2:1-15
[4]田金兰, 赵庆玉.并行决策树算法的研究[J].计算机工程与应用, 2001, (20) :112-114.
决策树算法综述 篇2
数据挖掘就是从大量的不完全的有噪声的模糊的随机的实际应用数据中，抽取隐含在其中的、事先并不知道的、但又是潜在有用的信息和知识的过程。
决策树算法作为常用的数据挖掘技术之一，其基本思想是将实例库中记录的大量有限的具体事实数据进行归纳和分类并建立树型结构，以发现并形成隐含在大量实例中的若干形式化的分类判别规则，典型的决策树算法方法有ID3方法和IBLE（Information—based Learning from Example）方法。
利用决策树评估教材质量的基本思想
笔者以高校教学质量建设中的重头戏——教材建设为例来阐释决策树算法在教育统计中的应用。
从教材的教学水平，科学水平等两大要素来对教材的质量进行合理分类，探索出科学合理的决策树的模型，使之成为学校教材建设管理的理论方法，并在今后的教材管理中起着一定的指导作用。
教学水平：教材符合人才培养目标及本课程教学的要求：取材合适、深度适宜、份量恰当；符合认知规律；富有启发性；便于学习。
科学水平：能反映本学科国内外科学研究和教学研究的先进成果；能完整地表达本课程应包含的知识；反映其相互联系及发展规律；结构严谨。
构建决策树模型
即利用训练集（教材建设数据库）建立并精化一棵决策树。该过程可分为建树和剪枝两阶段。其中，建树是用每一个属性将训练集划分成一个或多个子集，递归地调用该过程，直到每个子集中的记录都属于同一类，最终得到决策树。剪枝是为提高树的精度及分类效率，而去掉因训练数据中的噪声和孤立点等引起的不可靠或可能是噪声的一些枝条。
利用决策树研究影响教材质量的因素
首先，将学生问卷调查数据库和教学管理部门所掌握的资料结合起来，分类整理，同时进行规范化的数据清洗，得到创建决策树模型的训练集，如表1所示。
根据评估预期的要求，将所有教材的评估结果分为两类：
Class p：综合评价=“优秀”
Class n：综合评价=“一般”
从上表显示的数据可知，综合评价为“一般”的教材有9种， 综合评价为“优秀”的教材有6种，从而可以计算出样本分类的期望信息：
—∑Pi log2（pi）=
I（p，n）=I（9，6）= —[（9/15）×log2（9/15）+6/15×log2=（6/15）]
=—（—0.444—0.53）=0.974
下面以综合评价是否为“优秀”作为衡量标准分别计算由各个属性划分子集的信息熵，以及各自的信息增益度。
计算“教学水平”的信息增加益度
从而算出信息熵E（教学水平）=
I（3，1）+I（3，2）+I（0，3）+I（0，3）=0.43
再计算出其信息增益度
GainI（p，n）—E（教学水平）=0.974—0.507=0.467
计算“科学水平”的信息增益度
计算信息熵E（科学水平）=I（2，1）+I（3，2）+I（1，6）+I（0，0）—0.783再计算出其信息增益度GainI（科学水平）=I（p，n）—E（科学水平）=0.974—0.783=0.191
计算“教材编者职称”的信息增益度
从而算出信息熵E（教材编者职称）=I（4，1）+I（2，1）+I（0，4）+I（0，3）=0.424再计算出其信息增益度GainI（教材编者职称）—I（p，n）—E（教材编者职称）=0.974—0.424=0.55
计算“教材编者学历”的信息增益度
计算信息熵E（教材编者学历）=I（3，1）+I（3，3）+I（0，5）=0.667再计算出其信息增益度GainI（教材编者学历）=（p，n）—（教材编者学历）=0.974—0.667=0.307
由此可以得知“教材编者职称”的信息增益度最大，它是最能区别训练集实例中教材质量的属性，应作为决策树的根节点。根据各个属性的信息增益度的大小，可以构建该训练集实例的决策树如下图1所示：
由该决策树可以得出诸如以下结论：
教材编者职称的高低程度（也可以说是教学经验的丰富程度）很大程度上影响着教材的质量，教材的教学水平的优劣程度对教材质量的影响程度次之，教材编者的学历和教材的科学水平也在相当程度上影响教材的质量。
遥感监督分类的决策树算法研究 篇3
一、决策树算法的图像分类研究
1. 常用的决策树算法简介
决策树是一个类似流程图的树型结构, 其中树的每个内部节点代表对一个属性的测试, 其分支代表测试的每个结果, 而树的每个叶子节点代表一个类别, 树的最高层节点就是根节点, 是整个决策树的开始。这类算法无须相关领域知识, 且相对于基于模糊理论的分类方法, 具有更高的分类准确率和更快的处理速度。在很多领域特别是数据挖掘中, 决策树是一种经常要用到的技术, 它可以用于分析数据, 也可以用来作预测, 常用的算法有ID3, CART, C4.5等。
(1) ID3算法是最有影响和最早的决策树算法之一, 其建立在推理系统和概念学习系统的基础上, 但它是非递增学习算法。每当一个或数个新例子进来, 就必须重新执行一次该算法, 把新来的例子和以前旧的全部例子集合变成决策树, 因此效率非常低。而且它是基于单变量的, 难以表达复杂概念, 抗噪性差。
(2) C4.5是ID3的改进版本。它主要在以下几个方面对ID3作了改进:缺省值的预测属性仍可用, 提出了修剪思想, 可以进行规则推导。
(3) CART (ClassificationandRegressio nTree, 分类回归树) 是一种数据勘测和预测算法。它用一种非常简单的方法来选择问题, 即将每个问题均试一次, 然后挑出最好的一个, 用它把数据分成更有序的两个分割, 再对新的分割分别提出所有可能的问题。因此该算法得到的决策树每个节点有两个分支, 即二叉树。
2. 改进决策树生成算法
为了更好地将决策树算法应用于遥感图像分类中, 本文在CART算法的基础上作了以下改进。
(1) 常用的决策树算法均由用户提供训练样本集, 计算机执行算法生成决策树, 整个过程由计算机自动完成, 不需要任何人工干预。由于遥感图像训练集的属性取值太多, 而有些取值是用不到的, 需要把这些用不到的取值过滤掉, 否则会影响整颗树的质量。因此本文在决策树的生成过程中引入人机交互技术, 将用户的先验知识用于决策树的生成过程中, 使得生成的决策树更加合理可信。基于人机交互的决策树方法由用户与计算机相互交互, 共同完成, 故要求计算机提供可视化环境和工具, 友好的界面方便用户输入先验知识。
(2) 建立一棵树首先需要选择一个属性作为根节点, 然后将该属性的每一个可能值作为一个分支;再在每个分支所剩余的属性中找出一个属性作为该分支的下一个节点, 如此循环到所有属性均被选用为止。常用的决策树算法均采用信息熵作为选择标准。由于遥感图像中的噪音比较多, 而基于信息熵属性选择标准往往抗干扰能力不强且以对数计算为累加计算的计算量较大, 故本文采用了一种新型的属性选择标准:属性重要性来提高属性选择的效率。该方法是用训练值的变化而引起输出变化的累加值作为衡量属性重要性的标准, 即对于某个属性, 如果训练值的变化而引起的输出变化越大, 说明该属性就越重要。可用式 (1) 表示为C (K) =∑x (i, k) -x (j, k) ×signy (i) -y (j) (i≠j) (1) 式中:C (K) 表示第k个属性的输入/输出关联值;x (i, k) , x (j, k) 表示第i, j个样本的第k个条件属性值;y (i) , y (j) 表示第i, j个样本的决策属性值;sign (x) 表示符号函数。
3. 一种自定义的数据结构
数据结构的设计在程序设计中很关键, 一个好的数据结构可以让算法更加精练, 大大提高开发效率。本文采用的算法是在CART算法的基础上改进过来的, 因此生成的也是一棵二叉树。但由于在生成算法中要频繁地查找和调整决策树 (添加或者删除子树) , 传统的二叉树结构在速度上不能满足算法的需求, 故笔者在设计系统时创新了一种类二叉树的结构。在树的每一层都设置了一个头节点, 且树的每个节点只有指向父节点和左右兄弟节点的指针。
4. 系统实现
图3为系统架构图。其中D是训练集合, A为分类属性集合。另有测试数据集合T用来评估生成决策树的误差ε。整个过程分为两个部分进行: (1) 决策树构造, 也称学习过程, 主要工作是输入训练集, 采用改进的决策树生成算法生成决策树, 并作好分类前的预备工作, 即提取分类规则; (2) 决策树预测, 也称分类过程, 主要工作是应用分类规则进行分类, 并根据测试集, 计算出分类误差, 误差较大的对决策树作裁剪算法。误差较小的就输出其分类结果, 分类结果有两种: (1) 将分类结果写入新的遥感图像文件 (如MIG文件) 中; (2) 可视化的树结构, 在树的叶子节点保存着每一类的属性。
二、结语
通过本文研究发现:决策树算法对于输入数据的空间特征和分类标志具有更好的弹性和坚韧性, 它用于遥感数据分类的优势主要在于对数字图像数据特征空间的分割上, 其分类结构简单明了, 尤其是二叉树结构的单一决策树结构十分容易解释。因此, 当遥感图像数据特征的空间分布很复杂, 或者源数据各维具有不同的统计分布和尺度时, 基于决策树算法的分类方法能够获得较为理想的分类结果。
参考文献
[1]李宁, 等.决策树算法及其常见问题的解决[J].计算机与数字工程, 2010, 3 (33) :60264.
一种改进的决策树学习算法 篇4
分类是数据挖掘领域的重要研究课题之一。目前, 有多种分类方法, 如:贝叶斯、决策树、神经网络等。其中决策树是一种非常直观的知识表示方法, 同时也是高效的分类器。在各种决策树算法中, 最有影响的是J.R.Quinlan1986年提出的以信息熵下降速度为启发信息选取节点的ID 3算法[1]、C 4.5算法[2]等。这种方法已广泛应用于实际分类问题, 但C.45采用的是分而治之的策略, 在构造树的内部节点时是局部最优的搜索方式, 所以它所得到的最终结果尽管有很高的准确性, 仍然达不到全局最优的结果。为此, 现引入平衡度系数对传统C 4.5算法进行改进, 最终使建立的决策树具有更高的准确性。
1 C 4.5算法简介
在决策树学习算法中, 最有影响力的是Quinlan提出的ID 3算法。C 4.5算法是Quinlan于1993年提出的, 是对ID 3算法的改进, 主要是克服了ID 3算法选择偏向于取值多的属性的不足, 但难以获得全局的最优解[3,4]。
C 4.5算法主要步骤如下。
设T为数据集, 类别集合为{C1, C2, …, Ck}, 选择一个属性V把T分为多个子集。V有互不重合的n个取值{v1, v2, …, vn}, 则T被分为n个子集T1, T2, …, Tn, 其中Ti中所有实例的取值均为vi。令T为数据集T的例子数, Ti为V=vi的例子数, Cj=freq (Cj, T) 为Cj的例子数, Cjv是V=vi例子中具有类别Cj的例子数。则有:
(1) 类别Cj的发生概率为:
(2) 属性V=vi的发生概率为:
(3) 属性V=vi的例子中, 具有类别Cj的条件概率为:
(4) 类别信息熵计算:
H (C) =-∑j P (Cj) lgP (Cj) =-∑kj=1freq (Cj, T) T lg freq (Cj, T) T=Info (T) (1)
(5) 类别条件熵:
(6) 信息增益:
(7) 属性V的信息熵:
(8) 信息增益率:
C.45算法的一些不足。
第一, C.45采用的是分而治之的策略, 在构造树的内部节点时是局部最优的搜索方式, 所以它所得到的最终结果尽管有很高的准确性, 仍然达不到全局最优的结果;
第二, C 4.5评价决策最主要的依据是决策树的错误率, 而对树的深度、节点的个数等不进行考虑, 而树平均深度直接对应着决策树的预测速度, 树的节点个数则代表树的规模;
第三, 一边构造决策树, 一边进行评价, 决策树构造出来之后, 很难再调整树的结构和内容, 决策树性能的改善十分困难;
第四, C 4.5在进行属性值分组时逐个试探, 没有一种使用启发搜索的机制, 分组时的效率较低。
2 C 4.5算法的改进
C 4.5算法在构造树的内部节点的时候是局部最优的搜索方式, 所以它所得到的最终结果尽管有很高的准确性, 仍然达不到全局最优。对此下面提出一个平衡度系数λ (0<λ<1) , 它是一个模糊的概念, 其大小由决策者根据先验知识或领域知识来确定[5]。
改进的C 4.5算法是针对规则生成方法即属性选择标准算法进行了改进。通过对式 (2) 和式 (4) 中的加权和引入一平衡度系数, 降低了某些属性的信息熵, 相应地提高了其他属性的信息熵。把加权和转换为加权和加平衡度系数, 最终使建立的决策树在特定环境下具有更高的准确性。
现指定某一属性的平衡度系数为λ, 引入平衡度系数后式 (2) 、式 (4) 、式 (5) 分别变形为式 (6) 式 (7) 和式 (8) 所示。
改进的C 4.5算法就是把式 (6) 、式 (7) 和式 (8) 作为测试属性的选择标准来构造决策树。现实应用中可以首先用C 4.5算法构造决策树, 如果结果中出现了某些重要属性比非重要属性离根结点的距离远的情况, 则可设定此平衡度系数, 再利用改进后的C 4.5算法重新构造决策树并进行规则提取, 来达到特定环境下具有更高准确率的特性。
3实例分析
下面表1给出了根据天气情况决定是否适合做运动的几个相关指标的数据集合, 共有4个属性:outlook、temperature、humidity和windy。这4个属性被分为play和dontplay两类。 (见表1)
现将以此样本数据集为训练集, 采用C 4.5算法构造决策树对训练数据进行分类。经计算可知:Gain ratio (outlook) (=0.3058) >Gain ratio (humidity) (=0.0618) >Gain ratio (temperature) (=0.0269) >Gain ratio (windy) (=0.0031) , 因此首先选取“outlook”作为划分属性对上述样本训练集进行分类, 可得决策树如下图1所示。
但是在实际生活中, 人们判断某天天气是否适合出去作某项运动, 虽然在很大程度上受outlook属性的影响很大, 但是对于一些比较特别的一些室内运动却受outlook属性的影响相对较小。所以在这种特殊情况下必须降低outlook属性在判断天气情况中的重要性, 相应提高其他Attributes在判断天气情况中的重要性, 才能建立更符合实际情况的决策树以便作出更加准确合理的决策。
下面用改进后的算法对表1样本数据集重新生成决策树。指定outlook属性的平衡度系数λ=0.3, 其它属性的平衡度系数设为0。根据改进算法条件熵、属性信息熵的计算公式, 同样利用表1的数据来生成决策树。首先对根结点进行分类, 则由表1可知, play类实例个数为9个, don't play类实例个数为11个, 将上述实例数据代入公式 (6) 、 (7) 、 (8) :
由改进后的算法重新构造的决策树如下图2所示:
比较图2和表图可以看出outlook属性离根结点距离变远, humidity、temperature属性离根节点距离缩短。即改进算法基本上降低了在特定情况下不能作为判断天气情况的次要因素-outlook属性在分类中的重要性, 同时提高了humidity、temperature属性在分类中的重要性。令分类结果更为准确合理, 可以更为准确的判断天气情况, 便于决策者做出正确的决策。但因样本数据集太小的原因, 生成的规则中会有少数与实际情况不符, 如果增大训练集并对数据进行预处理消除噪音干扰等则效果更好[5,6]。
4 结论
改进的C4.5算法是在传统C4.5算法的基础上加进平衡度系数构成的, 它可以依靠先验知识或领域知识在特定环境下人工增大某些属性信息的信息熵, 相应降低其他属性信息的信息熵, 最终使建立的决策树具有更高的准确性。文章在特定环境下人工协调了各属性信息增益率, 用改进的算法构造出的决策树进行分类更为准确、合理。这不仅拓展了决策树分类算法在实际领域中的应用, 对数据挖掘技术的研究和发展也起到了一定的推动作用。
参考文献
[1] Quinlan J R.Induction of decision tree.Machine Learning, 1986; (1) :81—106
[2] Quinlan J R.C 4.5:program for machine learning.San Marteo:Mor-gan Kaufmann Publisher-s, 1993:21—301
[3]毛聪莉, 易波.基于决策协调度的最简决策树生成算法.计算机工程与设计, 2008;29 (5) :1250—1252
[4]史长琼, 易昂.基于多决策树算法的网络入侵检测.计算机工程与设计, 2004;25 (4) :518—519
[5]曲开社, 成文丽, 王俊红.ID3算法的一种改进算法.计算机工程与应用, 2003; (25) :104—107
一种改进的决策树算法研究 篇5
决策树分类算法中的ID3算法是Quilan在1986年提出来的,也是决策树构造中的经典算法[1]。ID3算法是以信息论为基础,它使用信息熵和信息增益两个指标为衡量标准,选择信息增益最大的属性划分训练样本,从而生成决策树。
定义1、按类标签对训练集D的属m性集A进行划分,信息熵为:
Pi为训练集D中属于第i类的概率。
定义2、按属性集A中每个属性进行划分,得到一组信息熵:
Dj为属性集中每个属性的出现的次数,D为所有属性的总次数。
定义3、信息增益为:
ID3算法对每个节点中选择Gain(A)中最大的属性A作为选择分支的属性。这种算法的缺点是:倾向于选择取值较多的属性[2],在有些情况下这类属性可能不会提供什么有意义的信息,ID3学习简单逻辑表达式的能力差[3]。此外,ID3将注意力集中在属性的选择方面,而属性的选择对决策树的影响如何, 仍无定论[4]。
2 改进的ID3算法
1)调整信息增益
针对ID3算法偏向于选择取值较多但实际中并不总是最优的属性作为测试属性的缺点,调整信息增益。Gain’(A)=Gain(A) /X,其中X的取值大于等于1,主要由属性A的取值个数和使用者根据经验及领域知识来确定,一般取值个数越多则X越大。改进的ID3算法通过调整每个属性的信息增益,使生成决策树时数量少但又很重要的属性不会被淹没,最终使决策树克服了对取值多的属性的偏爱,因为属性取值越多,调整后的信息增益就越小,这个属性当然就很难被选中为判断属性了。
2)剪枝
剪枝方法主要是考虑在决策树的哪个位置产生叶子合适 [5]。剪枝算法分前剪枝和后剪枝。前剪枝是在决策树构造过程中选取某个预定义的阀值,使得某些节点不再继续分裂,限制树的生长。后剪枝是将已生成的决策树做去分支处理[6]。前剪枝由于很难选取一个合适的阀值,应用困难。后剪枝的时间复杂度高,但生成的决策树准确度高,但主要应用的几种后剪枝算法都存在过剪枝或欠剪枝现象。由于各种剪枝算法都有缺点,所以本文提出采用灵活的剪枝方法进行剪枝。
剪枝方法为:首先,根据具体需要设定生成决策树的高度、精确度等信息,设定主要依据经验和领域知识来确定。然后, 针对决策树节点a来说,对a进行剪枝,则产生的错误分配样本数为:
未剪枝的子树错误分配样本数为:
未剪枝的子树误差为:
其中,e(a)为a节点的错误分配样本数,Ti(i=1,2,…,n)是Ta节点的子节点,Ca是Ta节点的子节点数。如果叶子节点的成立,那么Ta可以剪枝。
3实验测试结果
实验所用数据为UCI数据库中的Iris数据集(样本数209个,属性7个)、Breast数据集(样本数817个,属性11个)和Seg-mentation数据集(样本数2932个,属性26个)。对这三个数据集所有连续值的属性使用DBChi2算法对数据进行离散,随机抽取每个数据集中的2/3用于训练样本集,其余的1/3用作测试样本集,然后分别用传统的ID3算法和改进的ID3算法构建决策树,最后通过测试样本集测试准确度。上述构造决策树的方法反复进行十次,得出的结果如表1。
从表1中能明显的得出,改进的ID3算法平均的分类准确度更高,生成决策树的平均叶子数也高过传统的ID3算法,具有更低的复杂性。从实验还得出改进的ID3算法通过不断的学习调整信息增益,从而克服了传统ID3算法倾向于选择取值较多的属性的缺点,但是改进的ID3算法通过实验得出在时间复杂度上和传统ID3几乎一致。
4 结束语
改进的ID3算法调整了传统的ID3算法的信息增益计算方法,又加入了灵活的剪枝策略。它可以依靠经验或领域知识人工增强重要属性在分类决策中调整信息增益,从而减少非重要属性的信息量,特别是它可以减少ID3算法对取值较多的属性的依赖性,从而改善分类规则和结果。
摘要：决策树算法是数据挖掘中的一个常用算法,它通过构造决策树来发现数据中蕴含的分类规则,如何构造精度高、规模小的决策树是决策树算法的核心内容。决策树算法中常用的一种是ID3算法,该文针对传统ID3算法的缺点,提出一种改进的ID3算法,通过实验证实,改进的ID3算法在生成的决策树的规模和精度方面都比传统的ID3算法好,使用这种改进的ID3算法可以提高性能。
决策树算法综述 篇6
虽然ID3决策树算法已经得到了广泛应用, 但是该算法还存在一些缺陷和可以改进的方面。通过对ID3决策树算法建立决策树的过程中所存在的多值偏向问题的分析和探索, 提出了一种基于信息增益和样本结构相似度共同作用的属性判断指标, 通过改进指标来修正多值偏向给ID3决策树算法的准确性带来的影响。其实现过程对于在继续改进和丰富ID3决策树算法的判断指标和提高决策的准确性具有一定的现实价值和参考价值。
1 ID3决策树算法的不足
ID3决策树算法选用当前层次信息增益最大的属性来作为节点进行分支判断, 而每次信息增益的计算很大程度上会受到多值偏向性问题的影响, 即取值较多的属性有优先选取的倾向。这就难以判断得到的测试属性究竟是因为本身比较重要还是由于属性取值较多的缘故而被算法作为节点属性而选择的。
如果数据集中的不同属性间关系较为复杂, 属性间联系的强弱关系又没有明确的判断方法时, 信息增益的计算将很大程度上受到样本数据集中取值较多的属性的影响, 从而无法确实的反映客观的分类情况。由此可以得知, 在属性的关系复杂且重要度不确定的情况下构建的ID3决策树存在忽视重要的非多值属性的趋势。为提高分类预测的准确性, 针对ID3 决策树算法引入样本结构相似度模型对原算法的多值偏向性问题进行改进。
2 SS_ID3决策树算法简介
在样本数据集和实际数据集中一般情况下都存在一个共同的分类属性, 该属性具有若干个不同的属性值, 所有的数据元组都将指向这个分类属性中的各个属性值。从样本数据集中列的角度来看, 由于数据元组各个属性中属性值的随机性使得这些数据结构具有很大的不同, 从而使得每个属性列在表面上看起来往往是杂乱无章的。通过经验判断可以看出其中有一部分属性间没有很明确的联系, 但还是有一些属性间确实具有很明显或者很直接的关联关系。因为ID3决策树算法只是通过划分前后信息量之间的差值大小 (即信息增益) 为分类依据, 并没有考虑到描述属性和分类属性间的联系关系, 所以, 提出了一种改进的ID3决策树算法——SS_ID3决策树算法。
SS_ID3算法将描述属性和分类属性间的关联关系引入到了属性选择的步骤中与信息增益联合使用, 这样的处理能够帮助一些与分类属性在结构上相似或联系比较紧密的属性能够在描述属性选择的过程中得到更多的砝码, 从而能够在一定程度上减少或克服一些联系较紧密的描述属性由于属性值偏少而造成信息熵的减少不足导致的在选择中被忽略的问题, 同时还兼顾信息增益较大的属性, 使得这些属性不被样本结构相似度所掩盖。引入的样本结构相似度模型是一个用来度量样本数据集中的描述属性的属性值与分类属性的属性值之间的空间结构重叠性的数值指标, 样本结构相似度越大说明该描述属性的分类样本数在物理上越趋近于分类属性, 反之则越不同。计算主要用到的数值包括: (1) 总的样本数据元组数; (2) 分类属性的属性值; (3) 描述属性的每个属性值; (4) 结构相似矩阵。通过相应的计算得到的数值作为一个加权因子参与到描述属性的选择过程中来完成对ID3决策树算法的改进。
3 属性结构相似矩阵
计算样本结构相似度需要在样本数据集上建立一个数据模型——结构相似矩阵, 用来描述某个描述属性与分类属性间的分布情况, 即每个描述属性的属性值分别在所有分类属性值下出现的次数, 并获取其中重叠次数最多的数值。结构相似矩阵模型将为每个描述属性建立一个矩阵用来提供相应的计算样本结构相似度的参数, 并刻画了属性值在样本数据集中的结构分布情况。
3.1 结构相似矩阵的描述
在分类属性的取值空间R=[r1, r2, …, ry]上不同元组的属性值都有其各自不同的位置和数量, 可以根据属性值的位置得出一个向量V=[v1, v2, v3, …, vn], 其中v1至vn为样本数据集的所有元组所对应的分类属性的所有取值。同样每个描述属性都有一个向量与V对应。将每个描述属性向量分别与分类属性的向量合并成一个二维向量, 通过对这个二维向量进行处理就可以得到每个描述属性相对于分类属性的结构相似矩阵。
3.2 结构相似矩阵的数学定义
设存在一个训练样本数据集S, S中包括s个数据元组;存在数据项B为训练样本集S的一个描述属性, 属性B的取值空间为B={B1, B2, …, Bn}, 属性A在样本数据集中的结构为
undefined
;存在数据项C训练样本集S的分类属性, 具有m个不同值, 用来定义m个不同的类, 属性C的取值空间为C={C1, C2, …, Cm}, 对C按照样本数的多少从大到小进行排序得到整理后新的C′={C′1, C′2, …, C′m}。属性C′在样本数据集中的结构为
undefined
。由该描述属性和分类属性的值所构成的数据结构为:
undefined
。以描述属性B的取值为行, 分类属性C的取值为列, 可以通过UV得到一个n行m列的矩阵A, 按照Bj的顺序定位矩阵A的行顺序, 按照C′i的顺序定位矩阵A的列顺序, 并记矩阵A中的aij为UV中v的取值为C′i时且u的取值为Bj时数据元组的样本数量, 直到将UV中的所有数据自上而下进行遍历, 统计样本数后就得到了描述属性B相对于分类属性C的结构相似矩阵A。
undefined
4 样本结构相似度
通过对该矩阵中的数值进行提取和计算就可以得到该描述属性相对于分类属性的样本结构相似度。简单地来说样本结构相似度是一种通过计算得到的用以判断在样本数据集中指定描述属性的结构相似情况与分类属性的数据分布在不复用数据的情况下相吻合的程度。可见样本结构相似度是一种运用单个描述属性的结构相似矩阵通过计算得到该描述属性与分类属性在结构上的相似度的方法。
4.1 样本结构相似度的计算公式
样本结构相似度的数学定义如下:设存在样本数据集S, S中包含样本数据元组个数为s, 其中包含描述属性B其取值空间为B=[B1, B2 , …, Bn]和分类属性C其取值空间为C=[C1, C2 , …, Cm], B的取值个数为n, C的取值个数为m, 可以得到一个行数为n和列数为m的矩阵DT, 其中的矩阵元素为a[x], [y], 根据如下计算公式可以得到该描述属性相对于分类属性的样本结构相似度Fb (DT) 。
undefined[Max (a[], [j]) ]}, k=[1, 2, …, n]
其中公式Maxk (a[], [j]) 为获得结构相似矩阵DT的第j列的最大值, 而Adrx[Max (a[], [j]) ]是用来得到第j列的最大值所在的行数, k为记录结构相似矩阵DT各个行号得到的数据集, k=k-Adrx[Max (a[], [j]) ]就是将已取得当前列最大值的一行从之后的计算中剔除掉以保证该数据不被复用从而去除二义性和不确定性。
4.2 样本结构相似度的应用
由于样本结构相似度是一种用来修正信息增益在选择属性时产生的多值偏向问题的权值, 所以在ID3决策树算法的运作过程中需要将其加入到节点选择和判断的标准中, 即将样本结构相似度和信息增益相结合以得到进行了结构相似修正后的新的判断数值, 然后再对新数值进行比较来选择用来划分数据集的当前属性。使用相同的样本数据, 见表1, 分别进行ID3决策树和SS_ID3决策树的构建, 通过构建出来的决策属来进行比较。
由于根节点、各内部节点和叶节点的选择参数发生了变化后, SS_ID3算法和ID3算法所构建的决策树存在着明显的不同, 如图1所示。改进后的规则描述由原有的5条增加为8条, 这样就能够对数据的分类更加细致, 有助于提高决策树分类的准确性。
5 结论
通过决策树结构来看, SS_ID3决策树算法对取值数较多的属性并不敏感。SS_ID3算法使得决策树的结构更加平衡, 判断路径更加丰富, 对数据的分类更加细致, 有助于提高决策树分类的准确性。通过比较可以得到一些SS_ID3决策树算法的优点:一是在一定程度上解决了仅使用信息增益作为判断标准而造成的多值偏向问题。二是决策树的结构更加均衡。三是提高了结构相似度较高但取值不多的属性的权重, 使得决策树分类更加科学。四是对数据集的分类会更加细致, 有助于提高分类的准确率。
参考文献
[1]Joong-Hee Lee, Jong-Hyouk Lee, Seon-Gyoung Sohn, et al.Effective Value of Decision Tree with KDD 99 Intru-sion Detection Datasets for Intrusion Detection System[J].2008 (2) :17-20.
[2]Dunham M.Data Mining:Introductory and AdvancedTop ics[M].Upper Saddle River, NJ:Pearson Educa-tion, 2003.
[3]陆秋, 程小辉.基于属性相似度的决策树算法[J].计算机工程, 2009 (3) .
[4]鲁为, 王枞.决策树算法的优化与比较[J].计算机工程, 2007.
[5]房祥飞, 刘希玉.决策树在数据挖掘中的新进展和发展前景[J].信息技术与信息化.
[6]梁循.数据挖掘算法与应用[M].北京:北京大学出版社.
[7]段玉春, 晓艳, 孙玉强.一种改进的ID3决策树算法[J].南阳师范学院学报, 2006 (5) .
[8]唐松华, 姚耀文.数据挖掘中决策树算法的探讨[J].计算机应用研究, 2002 (8)
一种改进的C4.5决策树算法 篇7
决策树方法在分类、预测、规则提取等领域应用广泛。构造决策树的算法有很多种,其中最具影响力的决策树算法是ID3算法[1]和C4.5算法[2]。ID3算法是由Quinlan于1979年提出来的,C4.5算法是由Quinlan于1993年在ID3算法的基础上提出来的,保留了原有算法的优点并改进了原算法的缺点。但是,C4.5算法仍然存在一些不足,比如在处理现实数据时,数据集中存在很多与决策属性关联性很小甚至毫无关联的冗余属性;连续属性值处理过程中最优分割阈值选择比较耗时等等。因此,本文提出一种改进的C4.5算法,通过实验将它与传统的C4.5算法进行比较与分析,以此来说明改进算法的优越性。
1C4.5算法原理
C4.5决策树算法主要利用信息熵原理,选择信息增益率最大的属性作为分类属 性,递归地构 造决策树 的分支,完成决策树的构造[3]。它是在ID3算法的基 础上提出来的。ID3算法的基本原理[4]如下:设E = F1×F2 ×F…×Fn是n维有穷向量空间,其中Fi是有穷离散符号集。E中的元素e= {V1,V2,…Vn}称为样本 空间的例子,其中Vj∈Fi ,(j=1,2,…n),为简单起见,假定样本例子在真实世界中仅有两 个类别,在这两个 类别的归纳任务中,PE和NE是实体分配,称为概念的正例和反例。一样本集被一棵决策树作出正确分类所需要的信息量为:
如果选择属性A作为决策树的根,A取V个不同的值{A1,…,An},利用属性A可以将E划分为V个子集{E1,…Ev},其中Ei(1≤i≤V)包含了E中的属性A取Ai 值的样本数据,假设Ei中含有pi个正例和n个反例,那么子集Ei所需要的期望信息是I(pi,ni),以属性A为根,所需要的期望熵为:
其中,
以属性A为根的信息增益为:
对样本集T,假设A有s个不同取值的离散属性,划分为s1,s2,···,sn共n个子集,用A分割样本集所得的信息增益算法与ID3一样,分割信息量为:
信息增益率为:
C4.5算法的基本原理与以上ID3算法的基本原理类似,唯一不同的是ID3算法是选择信息增益最大的属性作为测试属性,而C4.5算法是按公式(6)计算信息增益率。选择具有最高信息增益率的属性作为测试属性,较好地解决了ID3算法的多值属性偏向问题。
2基于粗糙集理论的属性约简
1982年波兰数学家Z.Pawlak提出了一 种新的数 学工具,主要用来处理不确定性和模糊性问题,它就是粗糙集(RoughSet)理论。和处理不确定性问题的数学工具相比,粗糙集理论具有一定的优越性。比如,它在处理数据时,并不需要关于数据的任何已知的或额外的信息;另一个特点则是它能表达和处理不完备信息,能够通过属性约简推导出知识的最小表达。
2.1粗糙集概念
定义2:在一个已知的信息系统中,对于属性集RA且R≠Φ的不可区分关系IND(R)定义为:IND(R)={(x,y)|(x,y)∈U×U且a∈R,有f(x,a)=f(y,a)},若(x,y)∈IND(R),则称x和y是R不可分辨的。显然IND(R)是一个等价关系,记作U/IND(R)= {[x]p:x∈U},简记为U/R,其中:[x]p= {y∈U | (x,y)∈IND(R)}。
2.2粗糙集的属性约简
定义4:一个属性a的重要性(P对U有一个分类,R对U也有一个分类,如果分类完全相同,则P,R对于分类来说是一样的)可以利用两个属性集合P,R之间的相互依赖程度来确定。属性集P对R的依赖程度用γR(P)表示,定义如下:
其中card(.)表示集合的基数,POSR(P)是属性集R在U/IND(P)中的正区域。
定义5:属性a加入R,对于分类U/IND(P)的重要性程度为:SGF(a,R,P)=γR(P)-γR-{a}(P)。
定义6:在信息系统S= (U,A,V,f)中,,且P是独立的,满足IND(P)=IND(A),则称P是A的一个约简,用RED(A)表示P的所有约简集合;如果P中的所有元素在A中不可省 略,则称P是A的核,记为Core(A),显然Core(A)=∩RED(A)。
3C4.5决策树算法改进
3.1算法改进思想
3.1.1属性约简基本思想
粗糙集理论中进行属性约简的方法有很多种,本文采用的是基于属性重要性的属性约简方法,基本思想为:
依据定义4计算决策表中决策属性对条件属性C的依赖程度γc(D),如果POSc(D)≠POSC-{c}(D),表示该属性为核属性,将此属性加入核属性集Core(D);依据定义5分别计算每个属性相对于核属性集的重要性程度,选择重要性程度最高的属性与属性核集进行合并,作为当前约简结果集,直到约简集能够保持相对约简为止,输出约简结果;否则继续计算,相对约简的标准为IND(RED)=IND(D)。
3.1.2连续数据离散化过程改进基本思想
C4.5算法在连续属性离散化过程中,需要对属性的所有划分进行预测,这一计算量很大,将占有很多时间,如何快速定位连续属性的最佳分割点已成为亟待解决的问题。根据Fayyad[5]边界点判 定定理,无论数据 集有多少种分类,无论数据分类怎样分布,连续属性的最佳划分点总是出现于连续序列中两个相邻异类实例的边界点上[6]。所以,在对连续属性进行离散化过程中,不需要对每个阈值点比较,只要比较相邻不同类别的边界点即可。例如,当排序后的实例属性值为 {v1,v2,···,v10},其中前3个属性类别C1,后3个属于类 别C2,最后3个属于类 别C3 ,只需要检查两个边界点v3和v7,无需检查其余7个阈值点,然后选择v3和v7中使得平均类熵最小的那个作为最优阈值[7]。
3.2改进算法描述
输入:决策系统S = (U,V,F,C∪D)
输出:决策树
(1)对决策树系统进行规范,依次对每个属性从1开始逐个编号,每个属性的取值范围也从0开始逐个编号。
(2)根据定义2计算不可分辨关系U/IND(R),就是将相同条件属性值的实例分在同一个组,形成若干个这样的组,从而构成U上的一个划分,用二维数组IND的每一行存放每一组实例。
(3)根据定义3计算条件 属性C的正域POSC(D)。扫描IND数组的每一行,如果存在决策树属性值不一样的实例,就将这一行删除,POSC(D)就为剩下的实例集合。
(4)根据定义4计算决策表中决策属性对条件属性C的依赖程度γc(D)。
(5)令核属性集Core(D)=φ。
(6)对每个条 件属性c计算POSC-{c}(D),如果POSc(D)≠POSC-{c}(D),则Core(D)=Core(D)+{c}。
(7)令约简集RED =Core(C)。
(8)如果IND(RED)=IND(D),则输出最 小约简集RED,否则对每 个C-RED的属性p,计算属性 重要性SGF,选择属性重要性程度最大的加入到RED中,如果同时存在多个属性达到最大值,则从中选择一个属性值组合数最少的属性加入到RED中,重复第(8)步直至输出最终约简集RED。
(9)利用以上得到的最小约简属性,得到新的数据样本集合,作为算法的数据输入。
(10)利用传统算法中的方法创建节点,如果样本集中存在连续型属性时,则使用改进的离散化方法进行处理。
(11)对样本集重复进行步骤(10)操作,直至分支样本集中全为同一类别或者样本集为空。
3.3实验结果分析
为了验证改进算法 的优越性,在Win7系统和WEKA3.6.9平台下,利用UCI数据集中的Credit-a数据集进行具体分析和验证。Credit-a数据集包括690个样本,共16个属性(包含了决策属性),其中有6个连续型属性,有2类。首先,分别对每个属性和属性的取值范围逐个编号,利用上述的粗糙集属性约简算法对该数据集进行属性约简,约简后决 策表中仅 剩6个条件属 性:A2、A6、A7、A9、A14和1个决策属性class,然后采用改进的C4.5算法对约简后的数据集进行分类(其中70%作为训练样本,30%作为测试样本),分别利用传统的C4.5算法和改进的C4.5算法进行分类,对比分析与比较两种算法的结果,如表1所示。
结果显示,改进的C4.5算法得到的决策树比传统的C4.5算法小,属性个数从16降到了6,减少了数据冗余,节点数从42减到了22,叶子节点数也从30减到了14,决策树的规模得到了优化;分类时间从0.22减少到0.02,提高了分类 效率;分类准确 率则从85.507% 提高到86.087%。因此,可以看出改进的C4.5算法不仅缩小了树的规模,提高了分类效率,而且提高了分类准确率。
4结语
基于决策树的数据挖掘算法研究 篇8
随着计算机技术的日益发展和数据量的不断增多, 人们选择了通过计算机和信息服务技术来处理数据, 很大程度上增强了企业“收、存、管”数据的功能。经验的累积造就了企业的大数据量, 数据越多对一个企业越有利。在数据达到某种程度时, 就会总结出一定的规律, 因此需要新的工具盒技术挖掘数据仓库, 获得有效的资料, 让企业获得指导, 使之快速、稳定的发展。一些新的技术和概念随着计算机和信息技术的逐渐发展也慢慢出现, 如因特网 (Internet) 、神经网络、数据仓库 (Databaye) 等等。在技术和市场需求共存的情况下, 就产生了数据挖掘技术KDD (Knowledge Diycovery in Databayey) 的概念[1]。
数据挖掘是指从许多不清楚的数据中, 找出隐藏在信息里面的有效的信息和资料。也可以用好像数据融合、策略支持还有数据分析等这些与它非常相似的专业术语。
数据挖掘它是受多个领域的影响的, 可以把它看做是一个互相重叠交错的学科领域, 因此也就有相异分类的数据挖掘系统。下面分别从数据挖掘的目标、数据挖掘的方法以及用途、数据仓库类别三个方面进行讲解。
(1) 按照数据挖掘的目标分类
数据挖掘是多目标的, 这些目标多种多样, 有多媒体的数据挖掘、web方式数据挖掘, 还有文本的数据掘, 除此之外, 还包含了其他目标。不同的数据挖掘目标使用的挖掘方法不同。
(2) 按照数据挖掘的做法和技能匪类
数据挖掘的方法多种多样, 其用途也不尽相同, 关年、聚类、分类、预测、偏差的数据挖掘分析等等都是数据挖掘常用的方法。
(3) 按照数据仓库的类别分类
按不同的标准我们可以将数据仓库系统进行分类。按解决数据的某些类型可以将数据仓库划分为文本的、空间的、时间的、WWW的, 或是多媒体的数据挖掘系统;按数据模型可以将数据仓库划分为事务的、对象关系的、面向对象的、数据仓库的数据挖掘系统[2]。
二、决策树基本概念
数据分类是一种高效的解析方法, 它是数据挖掘中的一个非常重要的环节。利用解析训练, 数据分类可以快速找到信息, 然后创建出分类模型, 接下来就通过该模型将数据库里的信息项反映到指定的类别中去[3]。
决策树可分为两种:回归树和分类树。前者在相对于连续变量的情况下产生了决策树;后者是在相对于离散数据集的情况下产生了决策树。图1展示的是决策树产生的步骤。
决策树的构造和流程图的构造大致是一样的, 利用事例, 决策树从根节点向某叶子节点依次将事例分类, 叶子的节点就是事例的所属分类。树上的节点即事例的某一属性检测, 且该属性的可能值与节点上的分支一一对应。
图2展示的是决策树的事例, 用于分析学生的成绩。通过该模型可以分析出影响学生成绩的原因。叶子节点大多用椭圆形表示, 中间节点则用长方形表示。
三、决策树算法
Apriori算法存在一个致命的弊端, 那就是当用它来解决大数量的候选项目集时需要耗费大量的时间, 并且在在对候选项目集进行合适的选择时需要对数据库进行多次扫描。鉴于Apriori算法存在以上弊端, Lee等在FP-Tree的关联规则算法的基础上, 发明了更为先进的FP-Growth算法。利用压缩的数据结构, 这种算法可以把所有关联规则搜索要求的数据资料一一记录下来;通过反复扫描源数据, 这种算法可以将数据资料记录到结构里, 避免了候选项集的产生, 这就是无候选项集产生算法 (Frequent Patterny Growth, FP-Growth) [4]。
1. FP-Growth算法原理与相关含义
这种算法通过下列三点创新, 避免了候选项集的产生, 开拓出新的挖掘思路。
(1) FP-Growth算法创建了FP-Tree。FP-Tree是一种新的扩张前缀树结构, 用于存储关于反复模式数量的主要信息。树中的叶节点长度均为1, 频度越高的叶节点与根节点的距离越短。这样就降低了频度低的项与频度高的项共享相同节点的概率。
(2) FP-Growth算法在FP-Tree的基础上, 研发出片断成长算法。以长度为1的模式为出发点, 查询目标只针对它的条件模式和创建的模式树, 采用递归的形式挖掘数据。在联合条件模式数产生扩展模式的基础之上, 模式的成长最终得以实现。革新之后, FP-Tree算法不用像Apriori算法一样要进行再测试, 因为在FP-Tree算法里, 事务处理频繁项要对着树里的节点进行编写, 就避免了再测试的过程。计算累加值、改变前缀树是挖掘的两项基本操作, 这种算法相对于Apriori算法可以节约一大笔开销。
(3) 在分区的基础上选用合适的搜索技术进行挖掘, 对数据进行分割后再处理。与FP-Growth算法不同, FP-Tree下有一个名为“null”的目录, 还有一个由频繁项组成的表。树中的所有节点共计有3个地址:项名、节点链接和计数。当中, 节点链接代表树里下一个相同的节点, 假如无相同节点就指向空;计数存储的是到达该节点的路径所代表的需要解决的数目。由频繁项组成的表里的媒体信息包含2个地址:item name和node-link的头。其中node-link的头指向树中第一个相同的节点。
FP-Tree中只记录了符合最小支持度的项的合集, 因此, 第一就要先了解哪些项满足要求, 这就是构造头表的内容。展开首次搜索获得符合最小支持度的项并按照从低到高的顺序把它们排列在表中。在获得表之后, 对其再一次展开搜索, 对这些事务解决中存在的频繁项遵循它在头表中的前后关联加到树中。插入到树中的事务解决的频繁项自然是树的一个节点, 单假如树里有其他与性节点完全一样或者是类似的节点, 就要把这两个节点合并:将事务解决插入到FP-Tree中的函数inyert-tree是步骤中一个必要的环节。
FP-Tree是一个高度压缩的结构, 它记录了频繁模式挖掘需要的所有资料, FP-Tree远远小于源数据与在关联规则挖掘步骤中生成的候选项集的大小。而且, 在频繁项集中的项按支持度从低到高的顺序来陈列, 支持度越低的项和FP-Tree的根离得越远, 所以有许多的项是共享的。
2. FP-Growth算法描述
和Apriori算法的不一样, FP-Growth算法中频繁项集的产生是通过两步展开的, 首先是构造FP-Tree, 其次是在FP-Tree的基础上对产生的树展开搜索来构造频繁项集。基本的方法如下:
步骤2.1:构造FP-Tree:
输入:一个交易数据库ZX和一个最小支持度y。
输出:它的FP-Tree。
步骤:
1) 搜索数据库ZX一次, 获得频繁项的合集F和所有频繁项的支持度。将F按支持度从高到低的顺序, 结果记为L。
2) 构造FP-Tree的根节点, 记做Q, 标记为null。然后对ZX里的所有因素Trany做下面的方法。按照Y中的安排, 找到Trany中的因素项。将Trany中已经排好的因素项列表记做[f], 其中f是第一个项, f是列表余下的部分。选择inyert＿tree ([f], T) 。
函数inyert＿tree ([f|f], T) 的步骤如下:
假如Q有一个子结点N, 当N.item-name=p item-name, 那么把N的count域值增加1;要不然构造一个新节点M, 让它的计数为1, 让它的父节点为R, 而且让它的节点链接和那些有着同样项名域连接。假如P非空, 就递归调用inyert＿tree (T M) 。
步骤2.2:对FP-Tree展开搜索, 步骤如下:
FP-Growth方法把找到模式的因素改变成递归地找到一些短模式, 然后和扩展相连。它选择最不频繁的项作扩展, 供应了好的使用性。这个方法很大程度上减少了花费。在数据库非常大时, 创建在内存基础上的FP一树是不可能的。一种不可思议的换算是第一将数据库分为投影数据库的合集, 第二在所有投影数据库上创建FP一树而且搜索它。这个步骤能够递归地适用于投影数据库, 假如其FP-Tree还无法装入内存。相较于FP-Tree办法的用途开发说明:相较于挖掘长和短的模式, 它都是简单的和有序的, 而且比其他的方法快。它也比树-投影算法快。
FP-Growth算法开创了简单快速挖掘的新方法。但是, 它在时间和空间效率方面还存在不足, 还需要慢慢的进步。
摘要：决策树, 英文名为Deciyion Tree, 是一种很久以前就开始风靡全球的人工智能技术。随着数据挖掘技术的不断进步, 决策树已经成为构建决策系统不可缺少的技术, 它不仅在数据挖掘方面起着关键性的作用, 在数据分析方面也是一个领军者。决策树在数据挖掘中被用于预测、解决、分类等。
关键词：决策树,数据挖掘,Apriori算法
参考文献
[1]朱睿君。数据挖掘与最优化技术及其应用[M].天津科学出版, 2007.127-131
[2]孙倩义。关联规则在提高图书馆服务质量中的应用[J].北京出版社.2007 (2) ;144-148
[3]陈之哲。.数据挖掘在高校图书馆中的应用[J].学习出版社, 2002 (8) ;33-36