ID3算法的实现与改进

目录ID3算法的实现与改进3一、ID3算法简介3二、ID3算法的具体实现方法3三、ID3算法的不足与改进4四、分析5五、总结和心得体会7ID3算法的实现与改进一、ID3算法简介 构造决策树的基本算法是贪心算法，它以自顶向下递归的各个击破方式构造决策树。ID3算法的基本策略如下： 1.创建一个节点。如果样本都在同一类，则算法停止，把该节点改成树叶节点，并用该类标记。2.否则，选择一个能够最好的将训练集分类的属性，该属性作为该节点的测试属性。3.对测试属性中的每一而值，创建相应的一个分支，并据此划分样本。4.使用同样的过程，自顶向下的递归，直到满足下面的三个条件中的一个时就停止递归。给定节点的所有样本都属于同一类。没有剩余的属性可以用来划分。分支没有样本。二、ID3算法的具体实现方法设S是s个数据样本的集合。假定类标号属性具有m个不同的值，定义m个不同类Ci(i=1,2,，m)。设si是类Ci中的样本数。对一个给定的样本分类所需要的期望信息(熵)由下式给出：I(s1,s2,sm)=-i=1mpilog2(pi)其中pi是任意样本属性Ci的概率，并用si/s估计。设属性A具有v个不同值a1,a2,，av。可以用属性A将S划分为v个子集S1,S2,Sv；其中，Sj包含S中这样一些样本，他们在A上具有值aj。如果A选作测试属性（即最好的分裂属性），则这些子集对应于包含集合S的节点生长出来的分歧。设Sij是子集Sj中类Ci的样本数。根据由A划分成子集的熵或期望信息由下式给出：EA=j=1vs1j+s2j+smjsI(s1j,s2j,smj)其中，s1j+s2j+smjs是第j个子集的权，并且等于子集(即A值为aj)重的样本个数除以S中的样本总数。熵值越小，子集划分的纯度越高。注意，对于给定的子集Sj有I(s1j,s2j,smj)=-i=1mpijlog2(pij) 其中，pij=sijSj是Sj中的样本属于类Ci的概率。 在A上分枝将获得的编码信息是GainA=Is1,s2,sm-E(A) Gain(A)称为信息增益，它是由于知道属性A的值而导致额熵的期望压缩。具有最高信息增益的属性将选作给定集合S的测试属性。创建一个节点，并以该属性标记，对于属性的每个值创建分枝，并据此划分样本。三、ID3算法的不足与改进ID3算法往往偏向于选择取值较多的属性，而在很多情况下取值较多的属性并不总是最重要的属性，即按照使熵值最小的原则被ID3算法列为应该首先判断的属性在现实情况中确并不一定非常重要。改进：针对信息增益GainA=Is1,s2,sm-E(A)，为了弥补上述分裂属性选取是的多值偏向，可对GainA乘上一个条件修正函数，对其进行一定的“惩罚”，从而使各待选属性的信息增益值重新给排序。新的公式为 GainA=1-f(n)Is1,s2,sm-E(A)其中fn=sin13,n4sin1n,n4,n为v,即属性A中不同值的个数具体实现：f(n) Gain(A)四、分析对改进前和改进后的ID3算法进行分析对比。样本数据集如下：由于原样本数据集中各属性的v值都不超过3，所以我在阴晴属性和湿度属性中添加了几个新值，阴晴中添加了rany1（大雨），snow；在湿度属性中添加了low下面是改进前ID3算法的测试结果 改进后ID3算法的测试结果：从上可以明显看出，改进后的ID3算法要优于改进前的ID3算法。五、总结和心得体会上这门课程之前说模式识别是什么可能不知道，但上完这门课之后，肯定了解了什么是数据挖掘，什么是机器学习，在这门课程中，先后学习了决策树ID3算法，以及ID3的改进算法C4.5,还有朴素贝叶斯、K近邻等算法,对数据挖掘有了更全面的认识。这次实习主要研究了ID3算法，其实ID3算法有很多不足的地方，比