基于Weka平台的决策树J48算法实验研究

高海宾



基于Weka平台的决策树J48算法实验研究

高海宾

(淮南联合大学计算机系, 安徽淮南 232001)

在介绍了ID3算法和J48算法之间的关系以及J48算法的流程的基础上, 着重对信息增益率的计算方法进行了说明, 然后在Weka平台上选用鸢尾花数据集(Iris)进行分类实验, 并对结果进行了分析, 最后随机选取了几种常见的决策树算法继续实验, 与J48算法实验结果进行对比分析可知, J48算法在同类决策树算法中不仅分类准确率高而且速度快. 实验研究结果旨在为J48算法研究工作提供一些参考.

J48算法; 决策树; Weka; 信息增益率

决策树方法(Decision Tree Method)最早产生于20世纪60年代. 决策树方法是一种逼近离散函数的方法, 是当前数据挖掘中最常用的一种分类方法[1]. 这种方法易于理解和解释, 它对数据的准备要求不高, 而其他的技术多数对于数据属性有一定的约束性, 要对数据进行一般化处理后才可以应用, 比如需要删除空值或者多余的属性[2]. 另外决策树是一个白盒模型, 假设有一个观察的模型, 那么通过所产生的决策树能很方便地推导相应的逻辑规则[3]. 由于决策树可以对有许多属性的数据集构造决策树, 所以可以很好地扩展到大型数据库中, 同时它的大小独立于数据库的大小, 能够在较短的时间内对大型数据源做出可行而且很好的处理结果.

决策树算法是一种典型的监管学习, 所谓监管学习就是给定一堆样本, 每个样本都有一个类别和一组属性, 这些类别是预先确定好的, 通过学习得到一个分类规则, 根据这个规则能够对新出现的实例进行正确地分类. 决策树算法在数据处理过程中, 把数据按照树形结构分成若干分枝的决策树, 树的分枝包含数据元组的类别归属共性, 然后从每个分枝中提取有用信息, 形成分类规则[4]. 如何构造精确度高、规模小的决策树是决策树算法的核心内容. 决策树J48算法是近几年最为流行的一种决策树算法, 在机器学习和数据挖掘的分类问题中已经得到了广泛应用.

1 决策树J48算法介绍

1975年J.Ross Quinlan提出了分类预测ID3算法, 算法的核心是“信息熵”[5]. ID3算法(Iteratie Dichotomic Version 3)采用信息增益度作为属性划分的衡量标准, 寻找具有最大信息量的属性字段, 建立决策树的根节点, 再根据该属性字段的不同取值建立树的分支, 在每个分支集中重复建立树的下一个节点和分支[6]. 但是ID3算法在实际应用中也存在一定问题, 信息增益度的缺点是倾向于选择取值较多的属性, 但是这类属性很可能都是一些用处不大甚至是无用的信息. 其次ID3算法只能对离散型属性的数据集构造决策树.

1993年J.Ross Quinlan在ID3算法的基础上进行改进后提出了C4.5算法[7]. 决策树C4.5算法除了继承了ID3算法所有的功能, 还可以利用信息增益率来选择属性, 合并具有连续属性值、处理含有未知属性值的训练样本等. 对ID3算法的改进具体包括以下几方面:

(1) 在树的构造过程中进行剪枝; (2) 能够很好地处理不完整的数据; (3) 对于连续属性值能够很好地进行离散化处理; (4) 最佳分裂属性的选择用信息增益率高低来确定, 解决了用信息增益度确定属性时倾向选择取值多的属性的缺陷[8].

引入信息增益率是C4.5算法是对ID3算法的最大改进之处. 利用信息增益率来选择属性, 完成对连续属性的离散化处理, 将知识表示为决策树的形式, 并最终生成规则. 信息增益率的计算过程如下:

得出信息增益率以后, 选择信息增益率最高的属性作为根节点, 然后向下递归建树最终形成产生式规则. 在Weaka平台中把C4.5算法的实现命名为J48算法, 以下均称为J48算法. J48算法基本工作流程如图1所示[9].

2 决策树J48算法在Weka中的实验与分析

2.1 Weak平台介绍

Weka(Waikato Environment for Knowledge Analysis)全名是怀卡托智能分析环境, 它是一款免费的、非商业化、基于Java环境下开源的机器学习和数据挖掘软件. Weka这个名词来源于新西兰的一种鸟的名字. Weka是由新西兰的怀卡托大学开发的, 经历近二十多年的发展, 功能已经十分强大, 代表了当今数据挖掘和机器学习领域的最高水平. 作为一个公开的数据挖掘工作平台, 汇集了当今最前沿的机器学习算法和数据预处理工具, 包括对数据进行预处理、分类、聚类、回归、关联规则等, 它为数据挖掘实验的整个过程, 包括准备要输入的数据, 用统计方法评估学习方案, 以及可视化输入数据和学习结果, 提供了广泛的支持[10].

2.2 鸢尾花数据集

鸢尾花数据集(Iris)是一个非常著名的用于数据挖掘测试的数据集, 经常作为比较数据挖掘算法的基准. 鸢尾花数据集包括三个类别: Iris Virginica(维基亚鸢尾), Iris Setosa(山鸢尾)和Iris Versicolour(变色鸢尾), 每个类别各有50个实例. 数据集定义了5个属性: sepal width(花萼宽)、sepal length(花萼长)、petal width(花瓣宽)、petal length(花瓣长)、class(类别). 最后一个属性作为类别属性, 其余属性都是数值. 表1摘录了鸢尾花数据集(Iris)片段.

2.3决策树J48算法在Weka平台上的实验

利用Weka对鸢尾花数据集进行分类处理, 具体实验步骤如下:

(1) 在预处理Preproccess标签页点击 open file, 选择Weka安装目录下data 文件夹中的iris.arff数据集文件.

(2) 选择Classify标签页然后点击Classifiers→tree→J48. 打开J48参数设置面板主要参数设置如下, 使用未剪枝confidenceFactor参数设置用于修剪的置信因子(小于该值将导致修剪), 设置值为0.25; numFolds参数设置用于reduced-error(减少-误差)修剪的数据量, 设置值为3; seed参数设置是减少误差修剪时, 用于随机化数据的种子, 设置值为1; reducedErrorPruning参数设置是否使用减少-误差修剪, 而不是C4.5修剪, 设置值为False, 使用C4.5修剪; minNumObj参数设置每个叶的最小实例数量,设置值为2;

subtreeRaising参数设置修剪树的时候是否考虑子树上升操作, 设置值为True; unpruned参数设置修剪是否需要, 设置值为False; useLaplace参数设置是否叶节点基于拉普拉斯平滑, 设置值为False.

(3)选择cross-validation Folds的值为10, 可以保证生成的模型的准确性, 不至于出现过拟合(overfitting)的现象.

(4)单击Start按钮, 启动实验. 实验结果如图2所示.

根据图2可以看出, Correctly Classified Instances反映训练好的模型的准确度, 有144个实例被正确分类, 准确率高达96%, 6个实例被错误分类, 错误率4%. Kappa Statistic = 0.94, 用于评判分类器的分类结果和随机分类的差异度.= 1表示分类结果完全与随机分类结果相异(理想状况),= 0表示分类结果与随机分类相同(说明分类器没有效果),= −1表示分类结果比随机分类还要差. 所以越接近于1越好, 0.94反映实验分类结果很好. 平均绝对差Mean absolute error = 0.035, 用于评判预测值和实际值之间的差异度. 均方根误差Root mean squared error = 0.1586, 预测标签与真实标签偏差的平方和与测试样本数比值的平方根. 这两个值很好地反映预测的精密度, 值很小说明实验预测精密度高.

在resultlist中选择Visualize tree可以看到可视化的决策树, 如图3所示. 树的根节点选择了petalwidth属性, 说明petalwidth的信息增益率最大, 以它做分裂结点能得到更纯的子结点.

最后, 分裂结点选择的属性是petallength. 决策树建立的规则的是根据花瓣的宽度和长度不同判断出不同种类的鸢尾花. 例如: 当petalwidth小于等于0.6时, 即为iris-setosa; 当petalwidth大于1.7, 即为Iris-virginica; 当petalwidth小于等于1.7大于0.6而petallength小于等于4.9时, 为iris-versicolor; 当petalwidth小于等于1.5大于0.6而petallength大于4.9时, 为iris-virginica; 当petalwidth小于等于1.7大于1.5而petallength大于4.9时, 为iris-versicolor.

2.4几种决策树算法实验比较

常用的分类算法度量标准有TP、FP、Precision和Recall等. TP为识别率, 表示对某一分类的实例有多少概率把它识别出来. TP是一个很重要的标准, 例如在医疗系统中提高识别率很重要, 如果病人有病, 却没有识别出来, 后果就会很严重. FP为误判率, 表示对其他分类的实例, 有多少概率把实例识别成本分类. Precision为精准度, 表示对某一个类别的分类中正确的实例数占总数的比率. Recall为召回率, 又称查全率, 表示识别正确的实例数占该类别的实例的总数.

为了更好地验证J48决策树算法的分类效果, 再随机选取BTree、LADTree、NBTree、RandomForest、REPTree等几种决策树算法分别在Iris数据集进行分类实验. 由于篇幅有限, 相关参数设置和实验过程不一一介绍, 这里直接给出运行结果, 对实验结果汇总处理, 见表2.

通过几种算法在Iris数据集的实验结果可以看出, J48算法在进行分类过程中, 准确率要高于其他几种决策树算法, 运行速度方面也是最快的. REPTree 算法用时约为0.02秒, 速度快, 但是准确率0.94劣于其他算法. LADTree算法的时间0.03秒, 但是准确率却是最低的. 随机森林RandForest算法准确率较高, 但是运行速度0.08秒, 要逊于J48算法. J48算法的运行时间约等于0, 用时最少, 识别率也是最高的.

综上可以认为J48算法要明显优于其他几种决策树算法.

3 结束语

通过实验结果可以看出J48算法对数据集分类运行速度快, 产生的分类规则也易于理解, 准确率在同类决策树算法中也是较高的, 因而在医学、制造和生产、天文学、金融分析、分子生物学和遥感影像分类、机器学习和知识发现等领域都可以广泛应用. 但是该算法自身也存在一定的不足, 比如在构造树的过程中, 需要对数据集进行反复地顺序扫描和排序, 这样就会耗费大量的内存资源, 导致算法运行低效. 另外如果数据集增大了一点, 那么学习时间就会有一个迅速地增长, 这些问题需要在今后的数据挖掘工作中进行深入地研究. J48决策树算法所涉及的知识实在太广泛, 笔者仅从一个Iris数据集实验角度进行了讨论和分析, 得出的结论和观点难免有些偏颇, 仅供广大决策树算法研究人员参考.

[1] 王小妮. 数据挖掘技术[M]. 北京: 北京航空航天大学出版社, 2014: 9~10

[2] 黄 震. 数据挖掘在电信客户流失预警中的应用[D]. 北京: 北京邮电大学硕士学位论文, 2008: 12~14

[3] 宋 鉴. 基于C 4.5算法的BBS检索排名策略[D]. 北京: 北京邮电大学硕士学位论文, 2009: 28~29

[4] 张建良. 数据挖掘在炼铁系统中的应用现状及展望(上) [J]. 冶金自动化, 2012, 36(5): 6~9

[5] 王志春. 一种改进C4.5算法[J]. 电子技术与软件工程, 2016. 37 (09): 182~183

[6] 张同伟. 基于多分类器组合的垃圾网页的检测[D]. 广州: 华南理工大学硕士学位论文, 2010: 15~16

[7] 晁 进. 基于数据挖掘技术的电网智能报警系统的研究[D]. 北京: 华北电力大学硕士学位论文, 2011: 7~8

[8] 何广东. 高校就业工作中决策树技术应用初探[J]. 成功(教育).2013, 21(1): 56~58

[9] 梁 伟. VoIP呼叫分拣关键技术研究与设计[D]. 郑州: 解放军信息工程大学硕士学位论文, 2012: 17~19

[10] 段轶轩. 探索B2C账号在线评论特征[D]. 重庆: 重庆工商大学硕士学位论文, 2014: 6~7

Experimental Study on J48 Algorithm of Decision Tree Based on Weka

GAO Haibin

(Department of Computer Science, Huainan Union University, Huainan 232001, China)

Firstly, we introduce what J48 algorithm and algorithm flow, focusing on the information rate of gain calculation methods were introduced. Then we use the Iris data set on the Weka platform to classify experiments and analyze the results. Finally, several common decision tree algorithms are randomly selected and compared with the experimental results of J48 algorithm, and some conclusions are drawn. The experimental results are intended to provide some reference for J48 algorithm research.

J48 algorithm, decision tree, Weka, information gain ratio

TP312

A

1672-5298(2017)01-0021-05

2016-12-20

安徽省高等学校省级自然科学研究项目“基于Bandit算法的推荐系统优化研究” (KJ2017A585)

高海宾(1979− ), 男, 安徽淮北人, 硕士, 淮南联合大学计算机系讲师. 主要研究方向: 软件技术