基于决策树的分类方法研究资料下载.pdf

基于决策树的分类方法研究资料下载.pdf

《基于决策树的分类方法研究资料下载.pdf》由会员分享，可在线阅读，更多相关《基于决策树的分类方法研究资料下载.pdf（42页珍藏版）》请在冰点文库上搜索。

以及突破主存容量限制，具有良好的伸缩性和并行性的SI，lQ和SPRINT算法。

对这些算法的特点作了详细的分析和比较，指出了它们各自的优势和不足。

文中对分布式环境下的决策树分类方法进行了描述，提出了分布式ID3算法。

该算法在传统的ID3算法的基础上引进了新的数掘结构：

属性按类别分稚表，使得算法具有可伸缩性和并行性。

最后着重介绍了作者独立完成的一个决策树分类器。

它使用的核心算法为可伸缩的ID3算法，分类器使用MicrosoftVisualc+60开发。

实验结果表明作者开发的分类器可以有效地生成决策树，建树时间随样本集个数呈线性增长，具有可伸缩性。

，荡囊关键字：

数据挖掘1分类规则，决策树，分布式数据挖掘南京师范大学2003年硕士研究生毕业论文娃于决策树的分类方法研究AbstractDatamining，referredtoasknowledgediscoveryindatabases，istheextractionofpaRemsrepresentingvaluableknowledgeimplicitlystoredinlargedatabasesordatawarehousesClassificationisaformofdataanalysisthatCallbeusedtoextractmodelsdescribingimportantdataclassesTherearemanytechniquesfordataclassificationsuchasdecisiontreeinduction，BayesianclassificationandBayesianbeliefnetworks，associationbasedclassification，geneticalgorithms，roughsets，andknearestneiighborclassifiersThispaperintroducesthedecisiontreemethodforclassificationFirstlysomebasicalgorithmsforinducingdecisiontreearediscussed，includingID3，whichusesinformationgaintoselectasplittingattributewhenpartitioningatrainingset；

C45，whichCandealwithnumericattributes；

CART,whichBsesGNIruleinattributeselectionandinducesabinarytree；

PUBLIC，whichputstreepruninginthetreebuildingphase；

Interactivemethod，whichputsArtificialIntelligenceandhumancomputerinteractionintotheprocedureofdecisiontreeinduction；

aswellasSLIQandSPRINTwhicharescalableandcanbeeasilyparallelizedAdvantagesanddisadvantagesofthesealgorithmsarealsopresentedMethodsforinducingdecisiontreeindistributeddatabasesystemaredescribedandadistributedalgorithmbasedonID3isproposedUsinganewdatastructurecalledattributesdistributionlistthisalgorithmCanbescalableandparallelizedAdecisiontreeclassifierusingascalable1D3algorithmisdevelopedbyMicrosoRVisualC+60SomeactualtrainingsethasbeenputtotesttheclassifierandtheexperimentshowsthattheclassifiercansuccessfullybuilddecisiontreesandhasgoodscalabilityKeywords：

datamining，classificationrules，decisiontree，distributeddecisionlI南京师范大学2003年硕士研究生毕业论文声明本人郑重声明：

1、坚持以“求实、创新”的科学精神从事研究工作。

2、本论文是我个人在导师指导下进行的研究工作和取得的研究成果3、本论文中除引文外，所有实验、数据和有关材料均是真实的4、本论文中除引文和致谢的内容外，不包含其他人或其它机构已经发表或撰写过的研究成果5、其他同志对本研究所做的贡献均已在论文中作了声明并表示了谢意作者签名：

煎堑日期：

鲨2：

生：

12南京师范大学2003年硕士研究生毕业论文基十决策树的分类方法研究第一章绪论11课题的来源、研究背景及意义本课题来源于江苏省教育厅自然科学基金项目。

（项目号为2001SXXTSJBl2）。

随着数据库技术的不断发展及数据库管理系统的推广应用，存储在数据库中的数据量急剧增大，大量数据背后必定蕴藏着许多信息，如何从数据库中抽取出有用信息逐渐成为商业界普遍关心的问题。

数据挖掘的概念为解决这一问题而提出并在近年来引起学术界的广泛关注，成为学术研究的热点。

数据挖掘，又称数据库中的知识发现，是指从大型数据库或数据仓库中提取隐含的、未知的、非平凡的及有潜在应用价值的知识或模式，它是数据库研究中的一个很有应用价值的新领域，融合了数据库、人工智能、机器学习、统计学等多个领域的理论和技术。

数据挖掘的任务是从大量的数据中发现模式或知识。

一类称为描述型模式，它是对数据中存在的规律作出描述。

如泛化模式、聚类模式、关联模式及时间序列模式。

另一类是预测型模式，它依据从已有数据获得的知识对未知数据的某些性质进行预测。

包括分类模式和回归模式。

其中，分类模式是一种重要的预测型模式。

挖掘分类模式在实际生活中有着重要的实用价值。

例如，某信用卡公司的数据库中保存着所有持卡人的记录，公司根据信誉程度，已将持卡人记录分成三类：

良好、一般、较差，并且已将这三种类别标记赋给了数据库中的各个记录。

挖掘分类模式就是分析该数据库的记录数据，提取出客户属性和客户所属类别的关系，形成分类规则。

如通过分类挖掘产生了这样三条规则：

规则1：

“年收入在5万元以上，年龄在4050岁之间的客户信誉良好”，规则2：

“年龄在30-40岁南京师范大学2003年碘士研究生毕业论文堪十决策树的分类方法研究之间，年收入在35万元的客户信誉一般”，规则3：

“年龄在30岁以下，年收入不足3万元的客户信誉较差”。

根据分类规则l，公司可以对年龄在4050岁之间，年收入在5万元以上的新客户作出信誉良好的预测，从而接受他们的申请服务请求。

公司也可以根据分类规则3拒绝对信誉预测值较差的新客户提供服务。

由此可见，对信用卡公司的数据库进行分类规则挖掘，提取出有用的分类规则，可以使公司有选择地提供服务，提高了公司的运营效率。

抽象地说，挖掘分类模式的步骤如下：

首先，要对待挖数据库进行预处理：

包括整理数据库中的记录，去除些不全的汜录和无关的属性，主要是确定一个类别属性并确保每一个记录的类别属性都已给出。

然后，从待挖数据集中抽取出一定数量的配录形成训练样本集。

对训练样本集运用种或多种分类挖掘方法进行挖掘，最终输出某种形式的分类模式。

分类模式的形式有决策树，数学公式，分类规则等。

用于挖掘分类模式的方法有很多，如决策树方法，贝叶斯网络，遗传算法，基于关联的分类方法，粗糙集，k最临近方法，等等。

其中决策树方法以其易被人理解、需要信息煎少、效率及准确率较高等优点占据着重要地位。

决策树方法自产生至今，先后涌现出多种算法，包括ID3，C45，CART，SLIQ，SPRINT，PUBLIC，基于人机交互的方法等。

他们的共同特点是对训练样本集进行挖掘后都会生成一棵形如二叉树或多叉树的决策树。

树的叶子节点代表某一类别，非叶节点，包括根节点及内节点代表某个一般属性（非类别屈性）的一个测试，测试的一个结果形成非叶节点的一个分枝。

从根节点到叶子节点的一条路径形成一条分类规则。

一棵决策树能够很方便的转化为若干条分类规则。

人们可以依据分类规则直观地对未知类别的样本进行预测。

综上所述，分类模式挖掘技术作为数据挖掘的重要分支将对电信、银行、保险、零售、医疗等诸多行业提供决策支持，对未来商业和人们的生活也将产生深远的影响。

挖掘分类模式的算法有很多，其中，决策树算法因其卓越的优点在分类挖掘算法中占有重要地位。

本文作者选择分类挖掘方法作为研究课题，并着重研究了基于决策树的分类挖掘方法。

2南京师范大学2003年硕士研究生毕业论文：

jil=十决策树的分类方去研究12论文的内容安排论文首先在第一章介绍了研究课题的来源、背景和意义。

接着在第二章介绍了决策树分类方法的主要概念，对几种具有代表性的决策树算法进行了较详细地阐述，并对各种算法的性能作了分析比较，指出了它们的优缺点。

在第三章，作者对分布式环境下的分类规则挖掘进行了探讨，介绍了主要概念和研究现状，提出了一种在主从分布式环境下的决策树分类算法：

分稚式ID3算法，并对其性能作了分析。

作者依据ID3算法的基本原理，结合SLIQ、SPRINT算法的可伸缩特性，提出了一种可伸缩的ID3算法，以此算法为核心，作者独立开发了一个决策树分类器。

在论文的第四章给出了对这个分类器的功能介绍和性能分析。

在论文最后，作者对全文进行了总结并指出了进一步研究的方向。

南京师范大学2003年硕士研究生毕业论文基于决策树的分类方法研究第二章基于决策树的分类技术21决策树分类技术概述决策树，又称判定树，是一种类似二叉树或多叉树的树结构。

树中的每个非叶节点（包括根节点）对应于训练样本集中一个非类别属性的测试，非叶节点的每一个分枝对应属性的一个测试结果，每个叶子节点则代表一个类或类分布。

决策树可以很方便地转化为分类规则，是一种非常直观的分类模式表示形式。

例如，图21是从某银行的借贷业务中抽取出的训练样本集。

一个样本记录为一个请求借贷的用户。

每个样本除有样本序号、年薪，学历三个一般属性外，还有一个类别属性。

所有样本可分为拒绝受理和同意受理两类。

图22为从图21挖掘出的决策树。

其中，圆圈代表非叶节点，方块代表叶子节点。

由图中可以看出每个非叶节点上都有一个属性的测试，测试条件的结果形成了该节点的分枝。

每个叶子节点代表一个类。

图22直观地映射出三条分类规则，规则l：

年薪低于20，000且学历为本科的同意受理其借贷请求；

规则2：

年薪低于20，000但学历不是本科的拒绝其借贷请求；

规则3：

年薪超过20，000的同意其借贷请求。

样本号年薪学历类别llo，ooo高中拒绝240ooo研究生同意315。

ooo研究生拒绝475，ooo本科同意518。

ooo本科同意图21样本集实例同意拒绝图22决策树实例南京师范大学2003年颂I：

研究生毕业论文基于决策树的分类方法研究总的来说，决策树的构建是一种自上而下、分而治之的归纳过程，本质是贪心算法。

从根节点开始，对每个非叶节点，找出其对应样本集中的一个属性（本文中称为测试属性）对样本集进行测试，根据不同的测试结果将训练样本集划分成若干个子样本集，每个子样本集构成一个新叶节点，对新叶节点再重复上述划分过程，这样不断循环，直至达到特定的终止条件。

其中，测试属性的选择和如何划分样本集是构建决策树的关键环节。

不同的决策树算法在此使用的技术不尽相同。

在实际应用中，由于训练样本集的规模一般较大，相应生成的决策树的分枝和层数也较多，另外，训练样本集中存在的异常和噪声也会导致一些异常分枝的产生，这就需要对生成好的决策树进行剪枝。

剪枝按其实施的时间可分为预剪枝和后剪枝。

预剪枝是在决策树的构建过程中对每一个预生成分枝的节点进行判断，若可能生成异常分枝，则停止此分枝的生成，即将此预生成的分枝剪去；

后剪枝则是待决策树完全生成后运用特定的剪枝算法对整棵树进行修剪。

有的树剪枝的过程同时也是对决策树分类准确率的检测过程。

树剪枝的目的是生成一棵分类准确率较高而规模相对较小，即分枝和层数较少的决策树。

本文在以下两节中对几种典型的决策树算法作了详细的阐述，并对它们在选择测试属性、划分样本集和树剪枝上用到的技术进行了分析和比较。

22几种典型的决策树算法221ID3算法早期著名的决策树算法是1986年由Quilan提出的ID3算法【11。

ID3算法的具体描述由图23的伪代码给出。

其中，假设用T代表当前样本集，当前的候选属性集用T_attributelist表示，候选属性集中的所有属性皆为离散型，连续值属性必须事先经过预处理转化为离散型。

南京师范大学2003年硕士研究生毕业论文基于决策树的分类方法研究（I）创建根节点N；

（2）IFT都属于同一类C，则返回N为叶节点标记为类c；

（3）IFTattributelist为空则返回N为叶节点，标记N为T中出现最多的类：

（4）FOREACHTattributelist中的属性计算信息增益gain；

（5）N的测试属性test_attribute=T_attributelist中具有最高gain值的属性；

（6）FOREACHtestattribute的取值由节点N长出一个新叶子节点；

IF新叶节点对应的样本子集T为空则不再分裂此叶子节点，将其标记为T中出现最多的类；

ELSE在该叶节点上执行Id3formtree（T,T_attributelist），继续对它分裂l图23ID3算法ld3formtree（T,T_attributelist）ID3算法运用信息熵理论，选择当前样本集中具有最大信息增益值的属性作为测试属性；

样本集的划分则依据测试属性的取值进行，测试属性有多少不同取值就将样本集划分为多少子样本集，同时，决策树上相应于该样本集的节点长出新的叶子节点。

由于决策树的结构越简单越能从本质的层次上概括事物的规律，我们于是期望非叶节点到达后代节点的平均路径总是最短，即生成的决策树的平均深度最小。

这就要求在每个节点选择好的划分。

香农的信息论表明：

系统的不确定性越小，信息的传递就越充分。

ID3算法根据信息理论。

采用划分后样本集的不确定性作为衡量划分好坏的标准，用信息增益值度量：

信息增益值越大，不确定性越小。

因此，算法在每个非叶节点选择信息增益最大的属性作为测试属性。

信息增益值的算法在以下给出：

设S是s个样本的集合。

假定类别属性具有m个不同值，定义m个不同类G（f=1，m）。

设蜀是类C，中的样本数。

对一个给定的样本集，它总的信息熵值由公式21给出：

，：

s。

）=嵩川。

gzcP，）（21）6南京师范大学2003年硕士研究生毕业论文牡十决策树的分类方法研究其中，Pj是任意样本属于c，的概率，并用旦S估计。

设属性A具有v个不同值。

可用属性A将s划分为v个子集，s：

，S，；

其中Sj包含s中这样一些样本，它们在上具有口，值。

如果选择爿作为测试属性则这些子集就是从代表样本集s的节点生长出来的新的叶节点。

设曲是子集s，中类别为C的样本数，则根据A划分样本的信息熵值由公式22给出e

（一）=砉华，G-，2IP（22）其中札吻s州）=一和092鼢驴尚是s，中类她的样本的概率。

最后，用属性A划分样本集S后所得的信息增益值由公式23给出。

Gain（A）=，GI，s2“。

）一E（“）（23）ID3算法将待挖样本集分为训练样本集和测试样本集，决策树的构建是在对训练样本集的学习上产生的，决策树生成之后，再运用测试样本集对树进行后剪枝，将分类预测准确率不符合条件的叶节点剪去。

ID3算法使用的基于信息增益的测试属性选择方法存在一个弊端：

由于信息增益度量倾向于拥有许多值的属性，ID3偏向于选择取值较多的属性，但取值较多的属性不一定是最佳的属性。

刘小虎等人提出的MID3算法【2】给出了优化方法；

每当选择一个新的属性时，不仅考虑该属性带来的信息增益，而且考虑选择该属性后，继续选择的属性带来的信息增益，即同时考虑树的两层节点。

即对任意未选择的属性A，假设有v个属性值，对应的概率分别为Pl，P2，P。

，以属性彳划分，生成v个子节点切l，占2，B，j，西是属性A取第i个值时，按照最小信息熵原理选择的A的后继属性，分别对应的信息熵为E臼AE国2lE晤，）；

根据公式南京师范大学2003年硕士研宄生毕业论文桀十决策树的分类方法研究E，（）；

壹PfE悟）计算，选择使得Eb+）最小，将_作为测试属性。

实验表明J=IMID3和ID3的算法复杂度相同，但前者比后者具有更好的分类效果。

与ID3算法相比，MID3虽然有了明显的改进，但是它仍然存在一些不足：

不能在算法中直接处理连续型属性，不能处理属性值空缺的样本，生成的决策树分枝较多、规模较大。

这也是基于ID3的一系列算法存在的普遍不足。

为改进这些不足，产生了C45算法【51。

222C45算法C45算法是Quilan在1993年提出的，它既是ID3算法的后继，也成为以后诸多决策树算法的基础。

在应用于单机的决策树算法中，c45算法不仅分类准确率高而且是速度最快的。

C45算法在ID3的基础上加进了对连续型属性，属性值空缺情况的处理，对树剪枝也有了较成熟的方法。

图24列出了C45算法C45formtree（T）的伪代码。

其中，假设T代表当fitr样本集，当前候选属性集用Tattributelist表示。

（1）创建根节点N；

（2）IFT都属于同一类C，则返回N为叶节点，标记为类c：

（3）IFT_attributelist为空ORT中所剩的样本数少于某给定值则返回N为叶节点，标记为T中出现最多的类；

（4）FOREACHTattributelist中的属性计算信忠增益率informationgainratio；

（5）N的测试属性test_attribute=T_attributelist中具有最高信息增益率的属性；

（6）IF测试属性为连续型则找到该属性的分割阈值：

（7）FOREACH由节点N长出的新叶节点IF该叶节点对应的样本子集T为空则分裂该叶节点生成一个新叶节点，将其标记为T