网站首页  词典首页

请输入您要查询的论文：

　

标题 ID3改进算法研究
范文 杨霖+周军+梅红岩+杜晶鑫



摘 要：ID3算法是构造决策树的一种经典算法，传统的ID3算法存在很多問题，研究者提出了多种改进算法。简要概述基于粗糙集、粒计算和分类矩阵的ID3改进算法，通过实验分析对比3种改进算法的优势和不足，并对ID3算法的应用前景提出展望。
关键词：ID3算法；决策树；改进算法
DOIDOI：10.11907/rjdk.171383
中图分类号：TP312
文献标识码：A 文章编号文章编号：1672-7800（2017）008-0021-04
0 引言
分类是一种重要的数据分析形式，是数据挖掘中最常用的方法之一，是提取刻画重要数据类的模型。决策树是分类方式之一，它构造简单，不需要设置参数，可以处理高维数据。决策树分类采用树的表示形式较为直观，学习和归纳的步骤简单且快速，因此很容易被人理解和接受。
在决策树构造算法中，ID3算法的应用最为广泛，但同时也有许多缺点。ID3算法更倾向于选择属性值较多的属性作为根节点[1-4]，对于数据量较大的数据集，该方法可能会失效[5-8]，而且非类别属性越多，需要计算的时间也会急剧增加，并且分类的速度和精确度也大大降低[9-11]。此外，ID3算法对噪声数据比较敏感[12]。为了解决这些问题，近年来许多专家学者致力于ID3算法研究，提出了多种改进和优化的ID3算法，使得ID3算法更加完善，效率也更提高。其中，研究较为广泛的有：基于粗糙集的ID3算法改进、基于粒计算的ID3算法改进、基于分类矩阵的ID3算法改进等。本文将介绍ID3算法的基本原理，重点介绍基于粗糙集、粒计算、分类矩阵的ID3改进算法，并分析对比3类ID3改进算法。
1 ID3算法理论
ID3算法是J·Ross Quinlan于1986年提出的非回溯方法，其中决策树以自顶向下递归的分治方式构造[13]。以信息论为基础，引入属性选择度量的概念，将给定训练元组的数据分区划分成最纯的，即每个分区的所有元组都属于相同的类。
ID3算法采用信息增益作为属性选择度量，这里引入熵和期望信息的概念。
设数据分区为N类，属标号为a，且定义a个不同的类Mi（i=1，...，a）。设Mi，N是N中Mi类元组集合，|N|和|Mi，N|分别为N和Mi，N中元组个数。则熵（entropy）为：
Info（N）=-∑ai=1pilog2（pi）（1）
若对元组N进行元组划分，将N划分为v个子集{D1，D2，...，Dv}，则Dj包含D中的元组，理想状态下，每个分区都是纯的，则期望信息为：
InfoA（D）=∑vj=1DjD×Info（Dj）（2）
需要的期望信息越小，分区的纯度越高。
信息增益为：
Gain（A）=Info（D）-InfoA（D）（3）
2 ID3算法改进
2.1 基于粗糙集的ID3算法改进
波兰数学家Z·Pawlak教授[14-16]于1982年提出粗糙集理论数据挖掘方法。基于粗糙集技术的改进算法是一种完全数据驱动的归纳算法。针对ID3算法倾向于选取属性值较多的属性作为根节点的问题， 翟俊海[17]等提出基于粗糙集的决策树归纳。
基于粗糙集的ID3算法描述如下：
输入：决策表，其中，C={a1，a2，...，am}，决策属性D的取值为VD={d1，d2，...，dn}；
输出：决策树。
算法伪代码如下：
步骤1：计算决策表关于决策属性的分类：π（U）={X1，X2，...，Xn}。其中，Xi=[x]di，i=1，2，...，n。
步骤2：for（i=1；i≤m；i++） { for（j=1；j≤n；j++） { 计算Xj的重要度 } 计算π（U） 的重要度 }
步骤3：计算aj=argmax1≤i≤msgiai（π（U））。
步骤4：计算aj在U中的划分。
步骤5：for（i=1；i≤k；i++） {
如果Ui中类别属于同一类，结束计算；
否则，对于Ui重复步骤2—步骤5； }
在基于信息熵的ID3算法中，生成的子树会出现重复现象，甚至有些属性在某一路径上被检验许多次，当出现对分类无关属性较多时，生成的决策树结构性差。丁春荣等[18]提出一种利用属性加权分类粗糙度作为新的启发式函数构造决策树的方法，并用变精度粗糙集进行优化，提高了分类的效率和效果，王越等[19]也采用了变精度粗糙集进行优化。章晓等[20]基于粗糙集理论及凹函数性质，引入函数重要度概念，从理论上分析多值偏向问题，并分析了属性多值对属性重要度的影响。离散化方法的连续值决策树归纳在选择扩展属性时，需要度量每一个属性的每一个割点的分类不确定性，通过割点的不确定性选择扩展属性，但这一方法的计算时间复杂度高。翟俊海等[21]提出基于相容粗糙集技术的连续值属性决策树归纳方法，该方法利用相容粗糙集技术选择扩展属性，然后找出该属性的最优割点，分割样例集，并递归构建决策树。
2.2 基于粒计算的ID3算法改进
信息粒度化的思想由Zadeh[22]提出，后来Yao等[23]在此基础上进行了粒计算的研究。周浩等[24]提出基于粒计算的决策树并行算法应用，是为了解决海量数据的挖掘问题。该方法首先基于二进制信息粒关联矩阵，提出新的信息增益计算方法，再在Hadoop平台上，结合并行处理模型MapReduce进行决策树分类[25]。
基于MapReduce模型和粒计算的并行化设计思想主要有两点：一是二进制信息粒关联矩阵并行化计算，此过程中要设计一个Map和Reduce函数实现任一节点的关联矩阵，为计算属性的信息增益提供数据；二是决策树的任何分支点进行最佳分裂属性选择的并行化计算，这里的并行采用数据和任务两种并行方式，在训练阶段用两个Map函数和Reduce函数设计任务，第一个MapReduce任务是数据处理并行化，第二个任务是对树的分枝节点并行计算出每一个子数据集的最佳分裂属性，然后根据输出结果生产规则或者构建一层决策树[26-29]。
2.3 基于分类矩阵的ID3算法改进
分类矩阵是评估预测结果的重要工具，因为它使得结果更易于理解并说明错误预测的影响。陶道强等[30]提出了基于分类矩阵的决策树算法，为了提高决策树分类速度和精确率，解决ID3算法的多值偏向性，同时利用分类矩阵证明了ID3算法具有多值偏向性。
定义分类矩阵[30]，给定一个训练集H，按照非类别属性L=L1，L2，...，Lm将H分为集合H1，H2，...，Hm，同时集合Hi=（i=1，2，...，m）又按照类别属性C=C1，C2，...，Cn分为mn个部分，形成L到C的映射，这种映射定义为分类矩阵，记为AX，C，且：
AX，C=a1l…a1naml…amn
根据ID3算法的信息增益公式推导，得到分类矩阵的信息增益为Gain（AX，C），表示如下：
Gain（AX，C）={（∑mi=1∑nj=1aij）log2（∑mi=1∑nj=1aij）-∑nj=1（∑mi=1aij）log2（∑mi=1aij）-∑mi=1（∑nj=1aij）log2（∑nj=1aij）+∑mi=1∑nj=1（aijlog2aij）（∑mi=1∑nj=1aij）}（4）
为解决ID3算法多值偏向性问题，该算法引入权重因子Z，将Q暂时作为属性选择标准，其中Q=z×Gain（AX，C），Z=1/log2m，m为属性L的取值个数，即属性的选择标准修改为[30]：
tempGain（AX，C）=Gain（AX，C）log2m（5）
引入权重因子Z，使增益在[0，1]范围内比较，这种比较更固定、更准确，同时提高计算速度。当取值的非类别属性个数相差很大时，基于分类矩阵的改进算法能准确、高效地找出非类别属性。
2.4 其它ID3改进算法
除上述改进算法外，研究者还提出如下改进算法：基于神经网络的分类改进算法[31]、基于相关系数的决策树优化算法[32]、基于朴素贝叶斯与ID3 算法的决策树分类[33]、粗糙模糊决策树归纳算法[34]等。
3 部分改进算法实验分析
实验采用UCI数据库中的6个数据集（见表1）进行对比分析，其中3个较小的数据集和3个较大的数据集中，所有数据均为离散型，无缺失数据。实验前，选取1/3样本作为训练集，其余2/3样本作为测试集，利用文献[35]对数据集中连续属性进行离散化处理。
在同一台电脑上，运用MATLAB工具对数据集进行实验分析，分别对6个UCI数据集进行30次实验， 连续重复分类500次，利用测试集进行测试，取平均值作为分类的精确率。将较小的数据集Wine、Balance-Scale、Car Evaluation用传统ID3和改进分类算法进行对比以验证分类精确率，将较大的数据集Nursery、Adult、Bank Marketing用传统ID3和改进分类算法进行对比，验证分类精确率，得到实验数据如表2、表3所示。
基于粗糙集改进算法和基于分类矩阵的改进算法都是针对ID3分类算法的多值偏向性问题对算法进行改进。但从实验过程和结果可以看出，基于粗糙集的改进算法不太适合数据集较大的分类模式，对于较小的数据集分类效果明显。若取值的非类别属性个数相差很大时，基于分类矩阵的改进算法能准确、高效地找出非类别属性，分类方法优于粗糙集的改进方法。基于粒计算的改进算法处理较大数据集时，分类速度快，由于该算法没有解决多值偏向性问题，因此在处理较小数据集时，分类速度会低于传统的ID3算法。基于粒计算的改进算法在数据集群下更有效果，很适用于当前背景下的大数据分类分析。
4 结语
大数据已成为信息时代的一大新兴产业，并引起了国内外政府、学术界和产业界的高度关注，许多国家将大数据发展提升至戰略高度。自2009年的联合国“全球脉动计划”，经过2012年美国的“大数据研究和发展倡议”，到现在包括各国各级政府层面、学术层面和产业层面的广泛关注，使得大数据成为最新的、最具魅力的研究领域。当前，大数据技术研究风起云涌，大数据的“4V”特点（容量、多样性、速度和价值），使得大数据的研究面临许多新的挑战，如何对大数据中的知识进行提取是目前研究的重点。
知识提取方法研究主要针对关系数据库，包括结构化的静态和动态数据知识提取方法研究，半结构化的静态和动态数据知识提取方法研究，非结构化的静态和动态数据知识提取方法研究等。采用决策树分类算法，发现存在于数据间的蕴含关系，对数据进行快速的挖掘分析，提取数据中的价值。
本文归纳总结了多种经典的ID3改进算法，从实验结果来看，都要优于最初的ID3分类算法，分类效率大大提高，分类结果也很好。随着数据挖掘技术的不断发展，结合更多领域的专业知识，研究者们会提出更理想的ID3分类算法。在发展大数据技术的背景下，ID3分类算法将会应用到更多的技术领域。
参考文献：
[1] 张凤莲，林健良.新的决策树构造方法[J].计算机工程与应用，2009，45（10）：141-143.
[2] 武献宇，王建芬，谢金龙.决策树ID3算法研究与优化[J].微型机与应用，2010，29（21）：7-9.
[3] 潘大胜，屈迟文.一种改进ID3型决策树挖掘算法[J].华侨大学学报，2016，37（1）：71-73.
[4] 李瑞，徐旭睿.决策树ID3算法的分析与优化[J].大连交通大学学报，2015，36（2）：91-95.
[5] 黄宇达，范太华.决策树ID3算法的分析与优化[J].计算机工程与设计，2012，33（8）：3089-3093.
[6] 王永梅，胡学钢.决策树中ID3算法的研究[J].安徽大学学报，2011，35（3）：71-75.
[7] 罗雨滋，付兴宏.数据挖掘ID3决策树分类算法及其改进算法[J].计算机系统应用，2013，22（10）：136-138，187.
[8] 王小巍，魏玉明.决策树ID3算法的分析与改进[J].计算机工程与设计，2011，32（9）：3069-3072，3076.
[9] 张琳，陈燕，李桃迎，等.决策树分类算法研究[J].计算机工程，2011，37（13）：66-67，70.
[10] KIIT，ROHTAK.Comparative study of popular classification techniques of data mining[J].International Journal of Advance Research in Computer Science and Management Studies，2015，3（9）：267-272.
[11] 喻金平，黄细妹，李康顺.基于一种新的属性选择标准的ID3改进算法[J].计算机应用研究，2012，29（8）：2895-2898，2908.
[12] 胡煜，郑娟.基于粗糙集理论的ID3算法的改进与应用[J].贵阳学院学报，2015，10（1）：16-20.
[13] 韩家炜.数据挖掘：概念与技术[M].第3版.范明，孟小峰，译.北京：机械工业出版社，2012：213-218.
[14] PAWLAK Z.Rough set[J].International Journal of Infor-mation and Computer Sciences，1982，11（5）：341-356.
[15] PAWLAK Z，SKOWRON A.Rough sets and Boolean reasoning[J].Information Sciences，2006，177（1）：41-73.
[16] PAWLAK Z，SKOWRON A.Rudiments of rough sets[J].Infor-mation Sciences，2007，177（1）：3-27.
[17] 翟俊海，王熙照，张沧生.基于粗糙集技术的决策树归纳[J].计算机工程与应用，2009，45（18）：45-47.
[18] 丁春荣，李龙澍，杨宝华.基于粗糙集的决策树构造算法[J].计算机工程，2010，36（11）：75-77.
[19] 王越，万洪.一种新的应用变精度粗糙集的决策树构造方法[J].重庆理工大学学报，2013，21（11）：58-64.
[20] 章晓，何熊熊，朱忠记，等.基于粗糙方法的决策树多值偏向理论分析[J].杭州：电子科技大学学报，2014，32（2）：41-44.
[21] 翟俊海，翟梦尧，李胜杰.基于相容粗糙集技术的连续值属性决策树归纳[J].计算机科学，2012，39（11）：183-186.
[22] 张素兰，郭平，张继福，等.图像语义自动标注及其粒度分析方法[J].自动化学报，2012，38（5）：689-697.
[23] YAO YY.Reational interpretation of neighborhood operators and rough set approximation operators[J].Information Sciences，1998，111（198）：239-259.
[24] 周浩，刘萍，邱桃荣，等.基于粒计算的决策树并行算法的应用[J].计算机工程与设计，2015，36（6）：1504-1509.
[25] 徐剑锋，刘斓，邱桃荣，等.基于粒计算的二进制矩阵及在决策树算法的应用[J].广西师范大学学报，2008，26（3）：158-159.
[26] 钱网伟.基于MapReduce的ID3决策树分类算法研究[J].计算机与现代化，2012，28（2）：28-29.
[27] WU G，LI H，HU X，et al.MReC4.5：C4.5 ensemble classification with MapReduce[C].ChinaGrid Annual Conference，2009：249-255.
[28] HE Q，ZHANG F，LI J，et al.Parallel implementation of classification algorithms based on MapReduce[M].Rough Set and Knowledge Technology.Springer Berlin Heidelberg，2010：655-662.
[29] 陆秋.基于MapReduce的决策树算法并行化[J].计算机应用，2012，32（9）：2463-2469.
[30] 陶道强，马良荔，彭超.基于分类矩阵的决策树算法[J].計算机工程与设计，2012，33（6）：2309-2313.
[31] 杨林，富元斋，黄立平.基于神经网络的分类算法的改进[J].计算机工程与应用，2002（5）：71-73.
[32] 董跃华，刘力.基于相关系数的决策树优化算法[J].计算机工程与科学，2015，37（9）：1783-1793.
[33] 黄宇达，王迤冉.基于朴素贝叶斯与ID3 算法的决策树分类[J].计算机工程，2012，38（14）：41-47.
[34] 翟俊海，侯少星，王熙照.粗糙模糊决策树归纳算法[J].南京大学学报，2016，52（2）：306-312.
[35] HU X，CERCONE N.Data mining via generalization discrimin-tion and rough set feature selection[J].Konwledge and Infomation System：an International Journal，1999（1）：21-27.
随便看

　

科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。

　

Copyright © 2004-2023 puapp.net All Rights Reserved
更新时间：2025/3/15 13:35:36