ID3算法的实现与改进.doc

《ID3算法的实现与改进.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、目录ID3算法的实现与改进3一、ID3算法简介3二、ID3算法的具体实现方法3三、ID3算法的不足与改进4四、分析5五、总结和心得体会7ID3算法的实现与改进一、ID3算法简介构造决策树的基本算法是贪心算法，它以自顶向下递归的各个击破方式构造决策树。ID3算法的基本策略如下：1.创建一个节点。如果样本都在同一类，则算法停止，把该节点改成树叶节点，并用该类标记。2.否则，选择一个能够最好的将训练集分类的属性，该属性作为该节点的测试属性。3.对测试属性中的每一而值，创建相应的一个分支，并据此划分样本。4.使用同样的过程，自顶向下的递归，直到

2、满足下面的三个条件中的一个时就停止递归。·给定节点的所有样本都属于同一类。·没有剩余的属性可以用来划分。·分支没有样本。二、ID3算法的具体实现方法设S是s个数据样本的集合。假定类标号属性具有m个不同的值，定义m个不同类(i=1,2,···，m)。设是类中的样本数。对一个给定的样本分类所需要的期望信息(熵)由下式给出：其中pi是任意样本属性Ci的概率，并用估计。设属性A具有v个不同值{}。可以用属性A将S划分为v个子集{}；其中，包含S中这样一些样本，他们在A上具有值。如果A选作测试属性（即最好的分裂属性），则这些子集对应于包含集合S的

3、节点生长出来的分歧。设是子集中类的样本数。根据由A划分成子集的熵或期望信息由下式给出：其中，是第j个子集的权，并且等于子集(即A值为)重的样本个数除以S中的样本总数。熵值越小，子集划分的纯度越高。注意，对于给定的子集有其中，是中的样本属于类的概率。在A上分枝将获得的编码信息是Gain(A)称为信息增益，它是由于知道属性A的值而导致额熵的期望压缩。具有最高信息增益的属性将选作给定集合S的测试属性。创建一个节点，并以该属性标记，对于属性的每个值创建分枝，并据此划分样本。三、ID3算法的不足与改进ID3算法往往偏向于选择取值较多的属性，而在很

4、多情况下取值较多的属性并不总是最重要的属性，即按照使熵值最小的原则被ID3算法列为应该首先判断的属性在现实情况中确并不一定非常重要。改进：针对信息增益，为了弥补上述分裂属性选取是的多值偏向，可对乘上一个条件修正函数，对其进行一定的“惩罚”，从而使各待选属性的信息增益值重新给排序。新的公式为其中,n为v,即属性A中不同值的个数具体实现：f(n)Gain(A)四、分析对改进前和改进后的ID3算法进行分析对比。样本数据集如下：由于原样本数据集中各属性的v值都不超过3，所以我在阴晴属性和湿度属性中添加了几个新值，阴晴中添加了rany1（大雨），

5、snow；在湿度属性中添加了low下面是改进前ID3算法的测试结果改进后ID3算法的测试结果：从上可以明显看出，改进后的ID3算法要优于改进前的ID3算法。五、总结和心得体会上这门课程之前说模式识别是什么可能不知道，但上完这门课之后，肯定了解了什么是数据挖掘，什么是机器学习，在这门课程中，先后学习了决策树ID3算法，以及ID3的改进算法C4.5,还有朴素贝叶斯、K近邻等算法,对数据挖掘有了更全面的认识。这次实习主要研究了ID3算法，其实ID3算法有很多不足的地方，比如像不能处理数值型的属性，决策树结点之间的相关性不强。主要针对多值偏向问

6、题进行了改进，通过引入一个修正函数来对信息增益加以修正，在一定程度上弥补了ID3算法的缺陷。