【原创】数据挖掘课程论文：C0与CART算法的分类预测效果比较研究附数据代码

1、上海大学2013-2014学年春季学期硕士研究生课程考试课程名称：数据挖掘与商务智能课程编号：29SBG9016论文题目：C5.0与CART算法的分类预测效果比较研究研究生姓名（学号）：论文评价:评价项目具体评价标准得分（最高5分）选题意义选题有理论或实际意义；选题的难易程度；清楚了解专业背景12345知识水平对课程所讲授的理论知识熟练掌握，正确运用；理论掌握的深入程度12345论义表述主题突出，观点明确，论据充分，结构合理，层次清楚，语言通顺，文字简练，无错别字12345结论与创新结论表述清晰，推导合理，意义明确，有理论或应用上的指导性价值；研究力法肩创新，或改进了现有成果（建议在论文中直接

2、提及）12345参考文献格式#版文献引用合理元力一;经受文献格式止确；严格遵守论文格式及排版要求12345是否达到本课程小论文要求：是（）否（）论文成绩：任课教师：评阅日期：2014年6月C5.0与CART算法的分类预测效果比较研究摘要：数据挖掘实质上是一种发现知识的应用技术，是一个提取有用信息的过程。数据挖掘有很多方法，本文主要对决策树方法中的经典算法C5.0和CART算法的预测效果做了对比分析，所用数据来源于2013年版中国期刊引证报告（扩展板）。实验结果表明，两种算法在期刊评价预测中的效果都比较好，CART的效果则更胜一筹。关键词：数据挖掘；决策树；C5.0;CART1引言数据挖掘（Da

3、taMining,DM）技术出现于20世纪80年代后期，是一门融合了统计、人工智能机器学习、专家系统（依靠过去的经验法则）、模式识别和可视化技术的交叉学科1-2。早期学者Imielinski和Virmani将数据挖掘定义为从海量数据中提取有用模式3。华人学者韩家炜认为数据挖掘是知识发现过程的一个步骤4。因而数据挖掘可被理解为，是通过分析海量数据来揭示提取有价值有意义的新模式或知识的非平凡过程，是决策支持过程，是数据库知识发现（Knowledge-DiscoveryinDatabases）中的一个步骤。数据挖掘模型从挖掘结构中获取数据，然后使用数据挖掘算法分析这些数据。挖掘结构和挖掘模型是单独的

4、对象。挖掘结构存储定义数据源的信息。总体上来说数据挖掘主要分为以下几类：神经网络方法、遗传算法、决策树方法、粗糙集方法、统计分析方法、模糊集方法等。决策树算法是一种逼近离散函数值的方法。它是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。典型的决策树算法有ID3、C4.5、CHAID（ChisquaredAutomaticInteractionDetector,卡方自动交互检测）、CART（ClassficationAndRegressionTrees,分类与回归树）等。本文主要基于Cl

5、ementine软件对C5.0和CART算法的分类预测效果做比较研究。2决策树算法概述2.1决策树算法概述决策树就是一个类似流程图的树型结构，其中树的每个内部结点代表对一个属性（取值）的测试，其分支就代表测试的每个结果。为了对未知数据对象进行分类识别，可以根据决策树的结构对数据集中的属性值进行测试，从决策树的根结点到叶结点的一条路径就形成了对相应对象的类别预测。另外，与很多同样可以实现分类预测的算法相比，决策树算法的最大特点是，它的分类预测是基于逻辑的，即通过对输入变量取值的逻辑比较（布尔比较）实现对输出变最的分类预测。年龄40图1决策树示意图图1所示就是一棵决策树示意描述，该决策树描述了一个

6、购买电脑的分类模型，利用它可以对一个学生是否会在本商场购买电脑进行分类预测。决策树的中间结点通常用矩形表示；而叶子结点常用椭圆表示。沿着根结点到叶结点的路径有五条，就形成了五条分类规则：规则1:if年龄30and是学生then会购买电脑规则2：if年龄30and不是学生then不会购买电脑规则3:if年龄在30到40之间then会购买电脑规则4：if年龄40and信用等级良好then会购买电脑规则5:if年龄40and信用等级一般then不会购买电脑通常，决策树包括分类决策树和回归决策树两种，分别简称分类树和回归树。分类树实现对分类型输出变量（离散变量）的分类，回归树则完成对数值型输出变量（连

7、续变量）的预测。分类或预测的结果均体现在决策树的叶节点上。分类树叶节点所含样本中，输出变量的众数类别就是分类结果；回归树叶节点所含样本中，输出变量的平均值就是预测结果。因此，对新数据进行分类预测时，只需按照决策树的层次,从根节点开始依次对新数据输入变量值进行判断并进入不同决策树分枝，直至叶节点为止。2.2决策树的生成决策树的生成是指由训练数据集生成决策树的过程。一般情况下，训练数据集是根据实际需要由实际的历史数据获得的、有一定综合程度的、用于数据分析处理的数据集。在训练集合上生成一般决策树的基本步骤为：用户根据实际需求以及所处理数据的特性，对训练数据集做进一步的处理。根据用户的实际需要选择合适

8、的属性集作为决策树的候选属性集。在候选属性集中选择最有分类能力的属性作为当前决策结点的分裂依据（第一个决策结点称为根结点），结点上被选中的候选属性也称为测试属性。根据当前决策结点测试属性取值的不同，将训练数据集划分为若干子集。针对上一步中得到的每一个子集，重复进行上述的、两个步骤，直到最后的子集符合下面的三个条件之一：条件一：子集中的所有数据记录都属于同一类；条件二：该子集是遍历了所有候选属性得到的；条件三：子集中的所有剩余候选属性取值完全相同，己不能根据这些候选属性进一步进行子集划分。确定叶结点的类别。对“条件一”所产生的叶子结点，直接根据其中的数据所属类别进行类别标识；对“条件二”或“条件

9、三”所产生的叶子结点，选取子集所含数据的代表性类别特征进行类别标识，一般是以数据记录个数最多的类别进行类别标识。通过上述步骤，对数据集建立了可进行分类的决策树。由决策树的每一个从根结点到叶子结点的分枝都可以得到一条用于判断数据类别归属的初步规则。决策树生成算法的流程可表示为图2。图2决策树生长过程示意图2.3常用的决策树算法决策树学习算法是以一组样本数据集为基础的一种归纳学习算法，它着眼于从一组无次序、无规则的样本数据中推理出决策树表示形式的分类规则。比较成熟的决策树算法有ID3、C4.5、CHAID（ChisquaredAutomaticInteractionDetector,卡方自动交互检

10、测）、CART（ClassificationAndRegressionTrees,分类与回归树）等。由于本文主要对CART于C5.0算法的分类预测效果做研究，故这里只简单介绍CART算法和C5.0（C4.5）算法，其他算法不再一一作介绍。2.3.1 C5.0算法（C4.5算法）由于C5.0算法并未完全公开，而C5.0算法是对C4.5算法的升级，所以这里简单介绍C4.5算法。C4.5算法是从ID3算法演变而来的，除了拥有ID3算法的功能外，C4.5算法还引入了新的方法和增加了新的功能。例如：用信息增益率的概念；合并具有连续属性的值；可以处理具有缺少属性值的训练样本；通过使用不同的修剪技术以避免树

11、的过度拟合；k交叉验证；规则的产生方式等。C4.5在本质上和我们前面给出的决策树推导方法相同：在选择测试属性时，通过信息嫡公式计算出各属性的信息增益。C4.5采用启发式搜索来选择导致最大信息增益率GainRatio(A)的属性A作为扩展属性进行分枝，整个算法是个递归过程，直到无法分裂出新的结点为止。信息增益率(GainRatio)方法认为应当选择信息增益好的属性，一个属性的信息增益率用下面的公式给出：GainRatio(A)=Gain(A)Split(A)其中，属性的信息增益Gain(A)用前面给出的公式计算，分裂信息Split(A)计算如下:Split(A-喟。噜)可见，C4.5采用的信息增

12、益率表示了由分枝产生的有用信息的比率，这个值越大，分枝包含的有用信息越多。对于连续属性，C4.5处理过程如下： 根据属性的值，对数据集排序； 用不同的阈值将数据集动态的进行划分；当输出改变时确定一个阈值； 取两个实际值中的中点作为一个阈值；取两个划分，所有样本都在这两个划分中； 得到所有可能的阈值、增益及增益率；在每一个属性会变为两个取值，即小于阈值或大于等于阈值。C4.5处理的样本中可以含有未知属性值，其处理方法是用最常用的值替代或者是将最常用的值分在同一类中。具体采用概率的方法，依据属性已知的值，对属性的每一个值赋予一个概率，取得这些概率，取得这些概率依赖于该属性已知的值。C4.5算法在选

13、择测试属性，分割样本集上所采用的技术仍然没有脱离信息嫡原理，因此生成的决策树仍然是多叉树。如果想生成更为简洁和高效的决策树，必须对算法进行改进。2.3.2 CART算法CART是ClassficationAndRegressionTee的简称，可以处理高度倾斜或多态的数值型数据，也可处理顺序或无序的类属性数据。CART选择具有最小gini系数值的属性作为测试属性，gini值越小，样本的“纯净度”越高，划分效果越好。对样本集T,gini(T)=1p：其中pj是类别j在T中出现的概率。若T被划分为T1,T2,则此加sphtTniTiJS2giniT2次划分的gini系数为：其中，s是T中样本的个数

14、，S1、S2分别为T1,T2中的样本个数。与C4.5算法类似，CART算法也是先建树后剪枝，但在具体实现上有所不同。由于二叉树不易产生数据碎片，精确度往往高于多叉树，因此CART算法采用二分递归划分，在分支节点上进行布尔测试，判断条件为真的划归左分支，否则划归右分支，最终形成一棵二叉决策树。对于连续属性A,判断A=S是否成立(同C4.5算法)；对于离散型属性A,判断A属于S是否成立，其中S是属性A所有取值的子集，可用贪心算法或穷举法确定。Cj/i-lliNitNiCi/j)口NjtNjCART算法在建树时，不管节点N是否将被划分，均给N标记相应的类，方法是判断不等式,若对于除i以外的所有类j都

15、成立，则将N标记为类io其中口(i),表示先验概率，N(i促训练集中类i的数量，从N()t是节点N的样本中类i的数量,C(j|i)表示将i错误分类为j的代价，可通过查找决策损失(代价)矩阵得到。CART算法在满足下述条件之一时停止建树：(1)所有叶节点中的样本数为1或者样本属于同一类；(2)决策树高度到达用户设置的阀值。CART算法仍然使用后剪枝。在树生成过程中，考虑到多展开一层会有多一些的信息被发现，CART算法运行到不能再长出分枝为止，从而得到一棵最大的决策树。然后CART对这棵超大的决策树进行剪枝。剪枝算法使用独立于训练样本集的测试样本集对子树的分类错误进行计算，找出分类错误最小的子树作

16、为最终的分类模型。对于有些样本集，由于样本数太少而不能分出独立的测试样本集，CART算法采用一种称为交叉确定(crossvalidation)的剪枝方法。该方法将原始训练样本分为N份(假定每份的数据分布近似或相同)。N份中取第一份作为测试集，其余N-1份合并后用作训练集，经过一次完整的建树的剪枝的过程，得到一棵局部决策树。然后选择第二份作为测试集，将其余N-1份合并形成训练集，又得到一棵局部决策树。以此类推，直到N份样本集都做了一次测试集为止，这样总共得到N棵局部决策树，综合这N棵局部决策树形成全局决策树。这样形成的全局决策树在性能超群上非常近似于由包含所有样本的原始训练样本集得出的决策树。该

17、方法解决了在小样本集上挖掘决策树由于某种原因没有独立测试样本集而造成的过度拟合问题。3决策树算法的国内外研究现状最早的决策树学习系统要追溯到Hunt等人5于1966年研制的一个概念学习系统(concertLearningsystem,CLS),该系统第一次提出使用决策树进行概念学习，是许多决策树学习算法的基础。随后，迭代分类器(IterativeDiehotomizer3,ID3)算法，类似概念学习系统(AnalogConceptLearningSystem,ACLS)算法，分类及回归树(ClassificationandRegressionTree,CART)算法，C4.5算法分别被提出6。

18、1999年，ARNOJ等人7提出了用选择图表示的多关系决策树分类(Multi-relationalDecisionTreeLearning,MRDTL)的方法。该方法生成的决策树比ILP、CrossMine等分类方法更直观、更容易理解。随后的几年时间里，HectorLeiva,AnnaAtramentov等人提出了MRDTL2的算法，该算法通过引入建立补充表的方法大大简化了计算信息增益所需的时间8。2002年，S.Ruggieri提出了C4.5的改进算法高效C4.5(EfficientC4.5,EC4.5)算法9。实验表明，在生成同样一棵决策树时，与C4.5相比，EC4.5可将效率提高5倍，但EC4.5占用内存比C4.5多10。2003年，C.Olaru提出一种新的模糊决策树分类方法一一软决策树11。软决策树综合决策树的生成和修剪来决定其本身的结构，并利用重修和磨合来提高树的归纳能力，因此软决策树比一般决策树的正确率要高。SasoDzerroski对M