基于数据缩减和存储过程的ID3算法改进设计
时间：2021-04-08 07:55:51 来源：达达文档网 本文已影响 人 
【摘要】 ID3算法在分类数据挖掘中应用广泛，但其在对大规模训练样本集进行挖掘时，占用主存空间较大，且执行效率不高.运用属性约简和分组计数方法对训练样本集进行数据缩减，得到数据规模较小的新训练样本集，然后再运用ID3算法对新训练样本集进行分类挖掘.整个执行过程全部使用现代数据库技术和存储过程编程加以实现.实验表明，通过改进设计提高了ID3算法的执行效率，增强了算法的扩展性.
【关键词】 ID3算法；粗糙集；属性约简；分组计数；数据缩减；存储过程
0引言
ID3算法是一个经典的决策树分类算法，也是决策树生成最常用的具体实现方法，其基本思想是采用信息论中的互信息作为决策属性分类判别能力的度量，进行决策节点属性的选择.ID3算法的理论基础清晰，实现较简单，学习能力较强，在数据挖掘和机器学习领域中得到很好的应用.
ID3算法在对大规模训练样本集进行挖掘时，占用主存空间较大，执行效率不高，在现有研究[1-10]基础上，运用数据缩减和现代数据库技术对ID3算法进行改进，以增强经典ID3算法的执行效率和扩展性.
1改进算法设计思想
1.1粗糙集与属性约简
所谓属性约简是指在保持信息系统分类或决策能力不变的条件下，删除条件属性中的冗余属性，从而减少数据挖掘要处理的数据量，提高数据挖掘结果的简洁性[9].
粗糙集（Rough Set）理论[11]是由波兰数学家Z.Pawlak于1982年提出的，是一种刻画不完整性和不确定性的数学工具，能有效地分析不精确、不一致、不完整等各种不完备的信息，还可以对数据进行分析和推理，从中发现隐含的知识，揭示潜在的规律.粗糙集理论用在数据库中的知识发现方面的一个重要体现就是对数据库表进行属性约简[12]，通过属性约简删除数据库表中的冗余属性字段，减少需要挖掘分析的数据量.
1.2分组计数
分组计数，即将样本中所有属性取值相同的记录进行合并，同时在记录中增加一个字段来标记相同记录的个数.即在样本集R={r | r（C1，C2，…，Cn，D）} 中，将所有取值相同的样本r用一条记录r（C1，C2，…，Cn，D，samplesTotal）来表示，其中samplesTotal用来标记该条记录的相同个数.通过分组计数，压缩样本集的数据行数，从而减少样本数据的扫描时间.尤其对于大数据量、只有有限个属性字段且属性取离散值的样本集而言，使用分组计数方法达到的数据缩减效果十分明显.
1.3改进算法的基本思想
一方面，对于数据量巨大的训练集来说，使用ID3算法进行挖掘其执行效率受到很大影响，运用属性约简方法删除训练集中的一些对分类没有影响的条件属性，再利用分组计数的方法，将属性值相同的记录进行合并，缩小训练样本集的数据规模，增强ID3算法的执行效率；另一方面，在ID3算法的传统使用中，很多情况下将训练样本集数据以文件形式提供，算法主要基于主存而设计的，处理的数据量相对较小，对数据量巨大的数据进行挖掘时，算法效率不高，在改进设计时引入现代数据库技术，充分发挥数据库技术对海量数据高效操作和管理的优势，从而提高算法的执行效率和扩展性.
基于属性约简和分组计数方法对传统ID3算法加以改进，改进算法的基本思想：首先，运用属性约简和分组计数方法对训练样本集进行预处理，产生新的训练样本集；再运用
ID3算法对新的训练样本集进行挖掘分析，并将挖掘得到的分类规则以记录行的形式保存到数据库表中.改进算法的设计与执行均使用数据库存储过程、查询语言编程等数据库技术加以实现.
[BT4]
2改进算法描述
算法具体过程：
图1所示的数据库表dm_Rough_Set_R记录的对原始样本集循环执行属性约简的执行结果，直到属性约简算法执行完成，最后一条记录（即id值最大）为最终所要求的属性约简集R.例1原始样本集经过约简后的属性字段包括教学效果、教学方法、教学内容、仪表仪态、课堂气氛和作业批改，和原始样本集TestData相比减少了两个属性字段，相应属性字段的数据也就不在挖掘分析之列.图2所示的是原始样本集经过属性约简和分组计数后得到的新的样本集，在本例中将原始样本数由200个缩减到89个，压缩效果明显，也即意味着挖掘程序只需对89个记录进行挖掘，而不需要对原始的200个记录进行挖掘，从而大大提高挖掘算法的执行效率.
（2）分类挖掘过程
执行分类挖掘主程序，生成的分类规则被保存到数据库表dm_ID3_BranchRules中，在本例中共产生了43条分类规则，如图3所示.
4改进算法的性能分析
采用实验方法来分析改进算法的性能.为达到在相同实验条件下进行挖掘测试比较的目的，在实验中实现经典ID3算法和改进算法的程序均采用SQL Server 2005存储过程及其数据库管理技术.实验时以UCI mushroom数据为原始训练样本集，在相同机器条件下分别运用ID3算法和改进的算法，各执行5次后计算平均值.实验测试的最终结果见表1和表2所示.
实验结果表明，改进算法首先对原始训练样本集进行数据缩减，得到比原始训练样本集更加简洁的新训练样本集，然后再进行数据挖掘，最终得到几乎完全一致的分类规则，而改进算法总的执行时间比经典ID3算法总的执行时间有了很大的提高.同时在算法实现中采用了基于现代数据库的存储过程编程，充分利用了数据库技术，减少数据库服务器和应用程序之间的通信成本.实验表明，与经典ID3算法相比，改进算法大大提高了经典ID3算法的执行效率，而且改进算法充分发挥了现代数据库技术，增强了经典ID3算法的扩展性，使其应用范围得到了较大拓展.
[BT4]
5结束语
在经典ID3分类算法的基础上，研究运用属性约简、分组计数和数据库技术对其进行改进设计，使用属性约简和分组计数能够有效降低训练集的规模，同时算法的实现过程中充分利用了数据库及存储过程编程技术，发挥数据库对数据的高效操作和管理的优势，增强了改进算法的执行效率、拓展了改进算法的扩展性.该文是在其他学者大量研究基础之上，提出引入数据缩减和数据库技术对经典ID3算法进行优化，为进一步拓展经典ID3算法的应用提供了一种思路.
参考文献
[1]
丁祥武，王斌.一种基于ID3的前剪枝改进算法[J].计算机与现代化，2008，（9）.
[2]王苗，柴瑞敏.一种改进的决策树分类属性选择方法[J].计算机工程与应用，2010，46（8）：127-129.
[3]曲开社，成文丽，王俊红.ID3的算法的一种改进算法[J].计算机工程与应用，2003，（25）：104-107.
[4]张凤莲，林健良.新的决策树构造方法[J].计算机工程与应用，2009，45（10）：141-143.
[5]刘小虎，李生.决策树的优化算法[J].软件学报，1998，9（10）：797-800.
[6]李世娟，马骥等.基于改进ID3算法的决策树构建[J].沈阳大学学报，2009，21（6）23-25.
[7]黄爱辉，陈湘涛.决策树ID3算法的改进[J].计算机工程与科学，2009，31（6）：109-111.
[8]刘少辉，盛秋戬等.Rough集高效算法的研究[J].计算机学报，2003，26（5）：524-529.
[9]乔梅，韩文秀.基于Rough集和数据库技术的属性约简算法[J].计算机工程，2005，31（6）：18-19.
[10]刘红岩，陆宏钧，陈剑.利用数据库技术实现的可扩展的分类算法[J].软件学报，2002，13（6）：1075-1081.
[11]Pawlak Z.Rough sets.International Journal of Computer and Information Science，1982，11（5）：341-356.
[12]陈文伟.数据仓库与数据挖掘教程[M].北京：清华大学出版社，2006.
Abstract：
ID3 Algorithm is widely used in classified data mining， but if we use it in the mining of large-scale training sample set， too much main-memory space will be occupied， which results in low execution efficiency. The author uses attribute reduction method and classified counting method to reduce data in the training sample set and gets a new one with smaller scale， and then applies ID3 Algorithm in the classification mining of the new training sample set. The whole execution process is realized through modern database technology and stored procedure programming totally. The experiment shows that the improved design enhances the execution efficiency of ID3 Algorithm and extends its application range.
Keywords： ID3 algorithm； Rough set； Attribute reduction； Group counting； Data reduction； Stored procedure
（责任编辑：李家云）
