决策树算法在Weka平台上的数据挖掘应用

ＭｉｃｒｏｃｏｍｐｕｔｅｒＡｐｐｌｉｃａｔｉｏｎｓ　Ｖｏ１．３１，Ｎｏ．０６，２０１５　文章编号：１００７—７５７Ｘ（２０１５）０６—００６３—０３　技术交流　微型电脑应用２０１５年第３１卷第Ｏ６期　决策树算法在Ｗｅｋａ平台上的数据挖掘应用　程斐斐，王子牛，侯立铎　摘要：决策树算法可以对数据集进行有效的训练学习和快速准确的分类，其中ＩＤ３算法是最早提出的一种决策树算法，　但是，此算法只适用于处理取值较多属性的数据，不能处理连续数据，对噪声也比较敏感。Ｃ４．５算法是对ＩＤ３算法的优　化，不仅可以对连续值属性进行处理，而且增加了对空值数据的处理功能。在研究和分析主流决策树算法基础上，针对二　手汽车数据库在Ｗｅｋａ数据挖掘平台进行了Ｃ４．５算法的设计与实现。实验结果表明该算法对预测数据集中的相应属性能　进行较为准确的预测。　关键词：决策树算法；ＩＤ３；Ｃ４．５；Ｗｅｋａ　中图分类号：ＴＰ３０２文献标志码：Ａ　Ｄａｔａ　Ｍｉｎｉｎｇ　Ａｐｐｌｉｃａｔｉｏｎ　ｉｎ　Ｗｅｋａ　Ｐｌａｔｆｏｒｍ　Ｂａｓｅｄ　ｏｎ　Ｄｅｃｉｓｉｏｎ　Ｔｒｅｅ　Ｃｌａｓｓｉｆｉｃａｔｉｏｎ　Ｃｈｅｎｇ　Ｆｅｉｆｅｉ．Ｗａｎｇ　Ｚｉｎｉｕ．ＨＯＨ　Ｌｉｄｕｏ　（Ｃｏｌｌｅｇｅ　ｏｆＢｉｇ　Ｄａｔａ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｇｕｉｚｈｏｕ　Ｕｎｉｖｅｒｓｉｔｙ，Ｇｕｉｙａｎｇ　５５００２５，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｄｅｃｉｓｉｏｎ　ｔＴｅｅ　ａｌｇｏｒｉｔｈｍ　ｃａｎ　ｄｏ　ｅｆｆｅｃｔｉｖｅ　ｔｒａｉｎｉｎｇ　ａｎｄ　ｌｅａｒｎｉｎｇ　ａｓ　ｗｅｌｌ　ａｓ　ｆａｓｔ　ａｃｃｕｒａｔｅ　ｃｌａｓｓｉｉｃａｔｉｏｎ　ｔｏ　ｄａｔｆａｓｅｔ．ＩＤ３　ａｌｇｏｒｉｔｈｍ　ｉＳ　ｔｈｅ　ｅａｒｌｉｅｓｔ　ｄｅｃｉｓｉｏｎ　ｔｒｅｅ　ａｌｇｏｒｉｔｈｍ．Ｂｕｔ　ｔｈｉｓ　ａｌｇｏｒｉｔｈｍ　ｃａｒｌ　ｏｎｌｙ　ｂｅ　ａｐｐｌｉｅｄ　ｔｏ　ｈａｎｄｌｅ　ｍｏｒｅ　ａｔｔｒｉｂｕｔｅ　ｄａｔａ　ｖａｌｕｅｓ．ａｎｄ　ｃｏｎｔｉｎｕｏｕｓ　ｄａｔａ　ｃａｎ’ｔ　ｂｅ　ｓｏｌｖｅｄ　ｅｆｈｃｉｅｎｔｌｙ．Ｉｔ　ｉＳ　ａｌｓｏ　ｓｅｎｓｉｔｉｖｅ　ｔｏ　ｎｏｉｓｅ．Ｃ４．５　ａｌｇｏｒｉｔｈｍ　ｉＳ　ｔｈｅ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｏｆ　ＩＤ３　ａｌｇｏｒｉｔｈｍ．Ｉｔ　ｃａｎ　ｎｏｔ　ｏｎｌｙ　ｓｏｌｖｅ　ｔｈｅ　ｃｏｎｔｉｎｕｏｕｓ　ａｔｔｒｉｂｕｔｅ　ｖａｌｕｅｓ，ｂｕｔ　ａｌｓｏ　ｉｎｃｒｅａｓｅ　ｔｈｅ　ｆｕｎｃｔｉｏｎ　ｏｆ　ｅｍｐｔｙ　ｄａｔａ．Ｔｈｉｓ　Ｐａ１）ｅｒ　ｍａｉｎｌｙ　ｕｓｅｓ　Ｗｅｋａ　ｄａｔａ　ｍｉｎｉｎｇ　ｔｏｏｌｓ　ｔｏ　ｄｏ　ｔｈｅ　ｄｅｓｉｇｎ　ａｎｄ　ｒｅａｌｉｚａｔｉｏｎ　ｏｆ　Ｃ４．５　ａｌｇｏｒｉｔｈｍ．ｗｈｉｃｈ　ｉｓ　ｂａｓｅｄ　ｏｎ　ａｎ　ｅｘａｍｐｌｅ　ｏｆ　Ｓｅｃｏｎｄ—ｈａｎｄ　ｃａｒ　ｄａｔａｂａｓｅ．Ｔｈｉｓ　ｅｘｐｅｒｉｍｅｎｔ　ｉｎｄｉｃａｔｅｓ　ｔｈａｔ　ｔｈｏｓｅ　ｃｏｎｃｅｎｔｒａｔｅｄ　ｖａｌｕｅｓ　ｃａｎ　ｂｅ　ｐｒｅｄｉｃｔｅｄ　ａｃｃｕｒａｔｅｌｙ　ｂｙ　ｔｈｉｓ　ａｌｇｏｒｉｔｈｍ．　Ｋｅｙ　ｗｏｒｄｓ：Ｄｅｃｉｓｉｏｎ　１１ｒｅｅ　Ａｌｇｏｒｉｔｈｍ；ＩＤ３：Ｃ４．５：、ｖｅｋａ　０引言　随着计算机和信息时代的发展，人们收集、存储和访问　的数据急剧增加，如何从大量的数据中提取并发现有用信息　点。在决策树的基本结构图中，中间结点常用矩形表示，叶　子结点代表目标类别属性的值，用椭圆形表示。是～棵简单　的决策树，如图ｌ所示：　或知识，引起了学术界的广泛关注。数据挖掘因此应运而生。　数据挖掘的方法有很多，包括分类、预测、聚类、关联规则　挖掘、序列模式挖掘等。其中分类问题是被广泛研究的课题　之一，它是用来分析数据库中的一组对象，找出共同的属性，　构造分类模型，然后利用这个模型对其它的数据对象进行分　类。广泛使用的分类方法有决策树、贝叶斯分类、遗传算法　和神经网络等。其中，决策树是一种常用于预测模型的算法，　它将大量数据有目的的进行分类，从中找到一些具有商业价　值的、潜在的信息。　图ｌ决策树结构图　１．２决策树的主要步骤　ｌ决策树介绍　１．１决策树技术　决策树构造可以分两步进行：　第一步，建树阶段：由训练数据集生成决策树的过程。　按递归算法构造决策树，直到每个叶子结点属于同一类为　止，其本质是贪心算法。　决策树是用于分类与预测的主要技术，它是以实例为基　础的归纳学习算法，通过一组无次序、无规则的事例中推理　第二步，剪枝阶段：它是用数据对生成的决策树进行检　验，将不正确的问题进行调整，对决策树进行剪枝和增加结　点，直到建立一个正确的决策树。剪枝的主要目的是去掉噪　声和异常数据，使决策树具有更泛化能力。　利用决策树对数据进行分类和预测遵循两大步骤，如图　２所示：　出决策树表现形式的分类规则。这种算法采用“自顶向下、　分而治之”的方法，通常用来形成分类器和预测模型，可以　对未知数据进行分类、预测和数据预处理等。　决策树是一个类似于流程图的树结构，每个分枝代表一　个测试输出，树叶代表类或类分布，树的最顶层结点是根结　作者简介：程斐斐（１９８８一），女，贵州大学大数据与信息工程学院，硕士研究生，研究方向为用户上网行为的数据挖掘，贵阳，５５００２５　王子牛（１９６１．），男，贵州大学网络与信息化管理中心，副教授，本科，主要研究方向为数据挖掘，贵阳，５５００２５　侯立铎（１９８８．），男，贵州大学大数据与信息工程学院，硕士研究生，研究方向为数据挖掘，贵阳，５５００２５　・６３・　ＭｉｃｒｏｃｏｍｐｕｔｅｒＡｐｐｌｉｃａｔｉｏｎｓ　Ｖｏ１．３１，Ｎｏ．０６，２０１５　＠ｒｅｌａｔｉｏｎ　ｃａｒ—ｎｅｗ　技术交流　微型电脑应用２０１５年第３１卷第０６期　＠ａｔｔｉｒｂｕｔｅ　ｂｕｙｉｎｇ｛Ｖ—ｈｉｇｈ，ｈｉｇｈ，ｍｅｄ，ｌｏｗ】　＠ａｔｔｉｒｂｕｔｅ　ｍａｉｎｔ｛Ｖ—ｈｉｇｈ，ｈｉｇｈ，ｍｅｄ，ｌｏｗ）　＠ａｔｔｉｒｂｕｔｅ　ｄｏｏｒｓ｛２．０，３．０，４．０，５一ｍｏｒｅ｝　算法Ｃ４．５，对汽车信息库中各类标号属性值进行分类和预测。　结果表明Ｃ４．５算法可以快速准确的对属性明确的数据进行　分类和预测。如何把决策树其它算法更好的应用于Ｗｅｋａ平　台是笔者需要进一步研究的工作。　＠ａｔｔｒｉｂｕｔｅ　ｐｅｒｓｏｎｓ｛２．０，４．０，ｍｏｒｅ｝　＠ａｔｔｒｉｂｕｔｅ　ｌｕｇｂｏｏｔ｛ｓｍａｌｌ，ｍｅｄ，ｂｉｇ｝　＠ａｔｔｒｉｂｕｔｅ　ｓａｆｅｔｙ｛ｌｏｗ，ｍｅｄ，ｈｉｇｈ｝　＠ａｔｔｒｉｂｕｔｅ　ｃｌａｓｓ｛ｕｎａｃｃ，ａｃｃ，Ｖ—ｇｏｏｄ，ｇｏｏｄ｝　＠ｄａｔａ　Ｖ—ｈｉｇｈ，ｈｉｇｈ，２．０，２．０，ｍｅｄ，ｌｏｗ，？　ｈｉｇｈ，Ｖ—ｈｉｇｈ，２．０，４．０，ｓｍａｌｌ，ｍｅｄ，？　Ｖ—ｈｉｇｈ，Ｖ—ｈｉｇｈ，２．０，４．０，ｓｍａｌｌ，ｈｉｇｈ，？　参考文献　［１】　Ｊｉａｗｅｉ　Ｈａｎ，Ｍｉｃｈｗｌｉｎｅ　Ｋａｍｂｅｒ，Ｊｉａｎ　Ｐｅｉ．Ｄａｔａ　Ｍｉｎｉｎｇ　Ｃｏｎｃｅｐｔｓ　ａｎｄ　Ｔｅｃｈｎｉｑｕｅｓ［Ｍ］．３ｎｄ　ｅｄ．Ｂｅｉｊｉｎｇ：Ｃｈｉｎａ　Ｍａｃｈｉｎｅ　Ｐｒｅｓｓ，２０１２．　［２］　ＩａｎＨ．Ｗｉｔｔｅｎ，Ｅｉｂｅ　Ｆｒａｎｋ．Ｄａｔａ　Ｍｉｎｉｎｇ　Ｐｒａｃｔｉｃａｌ　Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ　Ｔｏｏｌｓ　ａｎｄ　Ｔｅｃｈｎｉｑｕｅｓ　Ｓｅｃｏｎｄ　Ｅｄｉｔｉｏｎ［Ｍ］．３ｎｄ　Ｖ—ｈｉｇｈ，Ｖ—ｈｉｇｈ，３．０，２．０，ｍｅｄ，ｌｏｗ，？　通过已有的分类器对此文件的最后一个属性值进行预　测。经过在ｗｅｋａ里分类预测后生成新文件Ｃａｒ—ｐｒｅｄｉｃｔｅｄ．ａｒｆｆ，　变化的部分如下：　＠ａｔｔｒｉｂｕｔｅ　ｐｒｅｄｉｃｔｅｄｃｌａｓｓ｛ｕｎａｃｃ，ａｃｃ，ｖ—ｇｏｏｄ，ｇｏｏｄ｝　＠ａｔｔｉｒｂｕｔｅ　ｃｌａｓｓ｛ｕｎａｃｃ，ａｃｃ，ｖ—ｇｏｏｄ，ｇｏｏｄ｝　＠ｄａｔａ　０，Ｖ—ｈｉｇｈ，ｈｉｇｈ，２．０，２．０，ｍｅｄ，ｌｏｗ，ｕｎａｃｃ，？　ｅｄ．Ｂｅｉｊｉｎｇ：Ｃｈｉｎａ　Ｍａｃｈｉｎｅ　Ｐｒｅｓｓ．２００６．　［３］　王继魁，吕凯，李虹．基于决策树分类的Ｗｅｋａ平台上数　据挖掘应用［Ｊ】．白城师范学院学报，２０１３，２７（５）：３６—４０．　【４］　戴南．基于决策树的分类方法研究【Ｄ】．南京：南京师范大　学，２００３．　【５］　赵蕊．基于ＷＥＫＡ平台的决策树算法设计与实现［Ｄ］．武　汉：中南大学，２００７．　【６］　王黎明．决策树学习及其剪枝算法研究［Ｄ】．武汉：武汉理　工大学，２００７．　【７］　冯少荣．决策树算法的研究与改进【Ｊ１．厦门大学学报（自　然科学版），２００７，４６（４）：４９６—５００．　【８］　邹媛．基于决策树的数据挖掘算法的应用与研究［Ｊ］．科　学技术与工程，２０１０，１０（１８）：４５１０—４５１５．　【９］　李如平．数据挖掘中决策树分类算法的研究［Ｊ］．东华理　１，ｈｉｇｈ，Ｖ—ｈｉｇｈ，２．０，４．０，ｓｍａｌｌ，ｍｅｄ，ｕｎａｃｃ，？　２，Ｖ—ｈｉｇｈ，Ｖ—ｈｉｇｈ，２．０，４．０，ｓｍａｌｌ，ｈｉｇｈ，ａｃｃ，？　３，ｖ—ｈｉｇｈ，ｖ—ｈｉｇｈ，３．０，２．０，ｍｅｄ，ｌｏｗ，ｕｎａｃｃ，？　有两个新的属性被添加到文件中，其中Ｐｒｅｄｉｃｔｅｄｃｌａｓｓ　的值就是对原ｃｌａｓｓ属性值的预测。　工大学学报（自然科学版），２０１０，３３（２）：１９２—１９６．　【ｌ０］但小容，陈轩恕，刘飞，柳德伟．数据挖掘中决策树分类　算法的研究与改进［Ｊ１．软件导刊，２００９，８（２）：４１—４３．　［１１］胡江洪．基于决策树的分类算法研究［Ｄ】．武汉：武汉理　工大学，２００６．　４总结　决策树是一种常用于预测模型的算法，Ｗｅｋａ工具可以　高效的进行数据挖掘，并提供了分类、聚类、关联规则等多　种方法，为数据挖掘提供了一个方便快捷的平台。本文针对　二手车数据库，通过使用Ｗｅｋａ数据挖掘工具及决策树分类　ｃ６拳ｃ　ｃ６事ｃ　ｃ　ｃ　ｃ６￥ｃ６事￡　ｃ　ｃ６￥￡　ｃ６事ｃ６￥ｃ　ｃ６事ｃ６事￡　【１２］杨学兵，张俊．决策树算法及其核心技术［ＪＪ＿计算机技术　与发展，２００７，１７（１）：４３—４５．　［１３］唐华松，姚耀文．数据挖掘中决策树算法的探讨［Ｊ］计算　机应用研究，２００１，１８（８）：１９—２２．　（收稿日期：２０１４．１２．１６）　擎ｃ６擎　ｃ６　擎ｃ６簪ｃ６拳ｃ　ｃｇ拳　ｃ６拳　ｃ６拳　￥　拳　￥ｃ　（上接第６２页）　时间复杂度：最好情况下为Ｏ（ｎｌｏｇｎ），最坏情况下为　Ｏ（ｎ　２１。　生），多次测试结果如下表　数据（＊１０００）　３０　７０　快速排序（ｓ）　Ｏ．Ｏ５５　Ｏ．１Ｏ８　挤压式排序（ｓ）　Ｏ．２２１　Ｏ．３ｌ２　冒泡排序（ｓ）　３．９００　９．４０５　空间复杂度：需Ｏ（１ｏｇｎ）的辅助空间。　（２）冒泡排序　１Ｏ５　１５０　２００　Ｏ．１６２　０．２２０　０．２７２　０．８６７　１．２０７　１．２６８　１３．８６５　２Ｏ．２８１　２８．８２ｌ　冒泡排序算法的基本思想：将被排序的数组Ｄ［１…ｎ１垂　直排列，每个元素Ｄ［ｉ］视为重量为Ｄｆｉ１．ｋｅｙ的气泡。根据轻　气泡不能在重气泡之下的原则，从下往上扫描数组Ｄ，凡扫　描到违反本原则的轻气泡，就使其向上“飘浮”。如此反复　由上表对比实验结果数据分析可得：挤压排序在时间性　能上略低于快速排序，但却比冒泡排序快很多。　进行，直到最后任何两个气泡都是轻者在卜，重者在下为止。　时间复杂度：最好情况下（初始为正序），只需通过ｎ一１　次比较，不需要移动关键字，即为Ｏ（ｎ）；最坏情况下（初始　４总结　本文研究提出的挤压排序算法是合理的、有效的，具有　一定的先进性和应用前景。　为逆序），须进行ｎ（ｎ一１）／２次比较，即为０（ｎ　２）　。　空问复杂度：整个排序过程为比较交换，需０（１）的辅助　空间。　表１复杂度对比分析情况表　排序算法　最好情况　最坏情况　冒泡排序　０（ｎ）　０（ｎ　２）　机．２００２．　参考文献　［１】　霍红卫，许进．快速排序算法研究【Ｊｌ＿微电子学与计算　［２］　周建钦．超快速排序算－法【ＪＪ．计算机工程与应用，２００６．　辅助空间　０（１）　０（ｎ）　０（１ｏｇｎ）　［３】　汪维清，罗先文，汪维华．分组排序算法［Ｊ１．计算机工程与　应用，２００８．　挤压排序　快速排序　０（ｎ）　０（ｎｌｏｇｎ）　０（ｎ　２）　０（ｎ　２）　【４］　淦艳，杨有．五种排序算法的性能分析ｆＪ１．重庆文理学院　学报（自然科学版），２０１０．　【５］　Ｃｌｉｆｆｏｒｄ　Ａ．Ｓｈａｆｆｅｒ．Ｄａｔａ　Ｓｔｒｕｃｔｕｒｅｓ　ａｎｄ　Ａｌｇｏｒｉｔｈｍ　Ａｎａｌｙｓｉｓ　ｉｎ　Ｃ＋＋【Ｍ】．北京：电子工业出版社，２０１３．　（收稿日期：２０１４．１２．０７）　３算法性能对比分析　对大量数据进行多次测试（数据由随机函数Ｒａｎｄ（）产　・６５・