算法改善ID3算法和原算法比较

摘要：本文对数据挖掘算法中的决策树算法进行了深入的分析和研究，在研究ID3算法的过程中总结了该算法的优缺点，同时针对原算法计算量大计算复杂的缺点进行改进，同时对改进的算法过程进行描述阐述其优于原算法的特点。
关键词：ID3算法 原算法
1007-9416（2013）02-0108-02
1 前言
ID3算法属于数据挖掘技术，所谓的数据挖掘（Data Mining，简称DM）技术是一种进行大量数据深度挖掘、剖析的一种技术。它能够在事先收集好的或是已经积累多年的大量的可以是不完整或是模糊的不确定的具有噪声的数据内部，研究并深度找出人们经常忽略的及隐含的但很可能是非常重要的数据信息的过程。
数据挖掘的方法和技术可以包括公式发现、模糊数学方法、归纳学习法和数据分类等多种方法，而在数据分类技术中最常用和经典的方法就是决策树分类方法，该方法的早期算法产生在上个世纪的60年代，之后经过不断的发展到现在已经研究出好多种常用的决策树算法了，例如典型的决策树ID3算法、分类与回归树CART算法以及将ID3算法进行改进的决策树学习算法.5等等，而在本文中主要研究的是ID3算法及改进后的应用研究。

2 ID3算法的基本思想

在数据挖掘技术中的ID3算法主要是建立用来建立决策树，并能通过建立的决策树来分析判断隐藏在数据后面的能对信息结果起到决定作用的重要因素，它是由CLS发展而来的。ID3算法在建立决策树时首先要进行树的根节点和子节点的选取，主要选取方法是根据计算每个给定属性的信息熵的值按照它们的下降程度进行选取，此方法在很多实际分类的应用上进行了广泛的应用，包括对学生成绩的分析中。
ID3算法的核心点主要在如何选择要建立的决策树的所有的分裂节点上。首先要计算出每个给定属性的信息增益值，在得出的信息增益值中最大的属性先选作分裂节点属性的备选项，这样除了根节点对其他节点进行测试的时候得到对于训练样本来说类别信息是最大的。然后，使用刚刚确定的分列属性中的备选项属性进行训练样本集合划分，将其划分成相应的子集合系统，这样得到的熵的值是最小的，最后通过求得每个属性的信息增益进行比较，找出最大的信息增益属性。

3 ID3算法的优缺点

在整个建立决策树的过程中，ID3算法的特点很突出具备它自己的优缺点下面分别详细的介绍。

3.1 算法优点

在众多的分类算法中，决策树算法已经深入的被研究并且被广泛的应用到各个领域中。该算法被作为较为通用的分类函数逼近算法应用，它本身存在很多的优点，分别为：
3.

1.1 生成的规则容易理解

ID3算法是通过树形结构中的每个分支代表一个分类来查看最终的分类结果的，在分类的时候才用判断的形式进行分类，所以能形成用的形式表示出来的规则。这种“如果…就…”规则很容易让人们接受，对现实世界描述的表示形式非常接近自然语言。而在算法的实际应用中，这种特点是非常重要的。
3.

1.2 容易确定属性之间的重要程度

在建树的过程中要根据熵值和信息增益值来确定根节点和每个叶子节点，通过熵计算的结果对属性进行分类。通过整个分类的决策树形结构图中就会很容易的观察出哪个属性比较重要，就是容易区分出属性的重要性了。因为，在建立的决策树中从根节点开始一直到最后的叶子节点都是按照属性的重要性进行选取的，节点越高越重要如果同一层属性的重要程度是一样的。
3.

1.3 计算量少运算速度高

ID3算法采用的是自上而下的方法进行搜索，在进行空间搜索时确保搜索该部分所用的测试次数是最少的，分类速度也是最快的。大大的提高了工作效率，速度也提高了很多。

3.2 算法的缺点

（1）通过信息熵的办法来选择所有属性中的最优属性，可能会产生出取值很大但是属性并不一定是最重要的，例如学生的性别属性。
（2）建立的决策树的节点之间联系比较松散，这是由属性特征值决定决策树节点的原因。
（3）ID3不容易去除噪声，该算法对噪声比较敏感，有时取错特征值或给错类别。
（4）ID3算法会随着训练集的改变建立的决策树发生改变，对于一些可变的数据集合建树是不太合适的。
（5）算法复杂也是缺点中最大的，计算每个属性的信息增益值的计算量是非常大的，通过计算的值进行分裂点选取不只耗费了大量的时间、资源而且还很占用机器内存，重要的选取出的属性未必是最优的。

4 改进ID3算法的研究及应用

本文将粗糙集理论中的决策协调度引入到ID3算法中，进行选定分裂点过程的改进不仅能够得到简单的决策树，而且是整个建树过程简化大大降低了原有算法的复杂度。过程是在整个决策系统中随机选取出某些规则，通过选出规则的前驱和后继条件相同的几率判断它们的相互协调的几率。这样可以看出起到决策作用的那些属性对可以作为条件属性到底有多少依赖程度，完全可以通过决策协调度表示出来。所以，可以通过决策协调度度量在构造决策树时选取的属

源于：论文的标准格式www.udooo.com

性。

4.1 决策协调度的概念

设定一个系统将其用作决策中，式子中的D代表决策的属性，用来表示某一个属性的子集，用来表示条件属性或者也称作为用于预测的属性[3]。则，的决策协调度可以表示为：
其中，，表示的基数。而表示在决策系统中，任意取出两条它们的前件和后继都相同的规则计算可能性大小，通过可以反映出数据对的依赖程度。因此，就表示集合中任意一子集的协调度，也可说用来度量的优劣性，越大，对的依赖性越大，属性集就越能预测的优良。

4.2 基于决策协调度的决策树生成算法

将上面描述的协调度概念引入到决策树的建立中，能够快速并准确的找出所有属性中的好与坏。整个过程可以描述为：计算所有样本集中的属性的决策协调度，如果决策协调度相近的再计算其信息增益值；值大的会被选作决策的分裂点，如果无需计算信息增益值那么协调度大的会被选作决策分裂点以该分裂节点进行划分后的每个属性中含有的训练元组都是同类的，并可将其作为叶子节点；利用递归调用直到条件属性为空值结束，最后生成决策树。
5 结语
综合上面对ID3算法及改进算法的分析，利用ID3算法进行属性信息增益计算时用的是对数运算计算量非常大。而改进的算法是在决策协调度相近的情况下才计算信息增益值，所以在计算量上降低计算的复杂度。
参考文献
杜聪.数据挖掘技术在科研评价系统中应用研究.济南：山东大学，2009
牛文颖.改进的ID3决策树分类算法在成绩分析中的应用研究.大连：大连交通大学，2008.
[3]刘宇阳.一种改进的ID3 决策树算法研究.哈尔滨工程大学，2009.6：18-22.