决策树ID3算法

《决策树ID3算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、决策树ID3算法（1）决策树技术构造决策树的基本算法是贪心算法，它以自顶向下递归的各个击破方式构造决策树。一种著名的决策树算法是ID3，算法的基本策略如下：①创建一个节点。如果样本都在同一类，则算法停止，把该节点改成树叶节点，并用该类标记。②否则，选择一个能够最好的将训练集分类的属性，该属性作为该节点的测试属性。③对测试属性中的每一个值，创建相应的一个分支，并据此划分样本。④使用同样的过程，自顶向下的递归，直到满足下面的三个条件中的一个时就停止递归。给定节点的所有样本都属于同一类。没有剩余的属性可以用来划分。分

2、支没有样本。8.5决策树设S是s个数据样本的集合。假定类标号属性具有m个不同值，定义m个不同类Ci（i＝1，2，…，m）。设si是类Ci中的样本数。对一个给定的样本分类所需要的期望信息由下式给出：其中pi是任意样本属于Ci的概率，并用si/s估计。设属性A具有v个不同值｛a1，a2，…，av｝。可以用属性A将S划分为v个子集｛S1，S2，…，SV｝；其中，Sj包含S中这样一些样本，它们在A上具有值aj。如果A选作测试属性（即最好的分裂属性），则这些子集对应于由包含集合S的节点生长出来的分枝。设sij是子集Sj中

3、类Ci的样本数。根据由A划分成子集的熵或期望信息由下式给出：其中，是第j个子集的权，并且等于子集（即A值为aj）中的样本个数除以S中的样本总数。熵值越小，子集划分的纯度越高。注意，对于给定的子集Sj，其中，是Sj中的样本属于类Ci的概率。在A上分枝将获得的编码信息是。Gain(A)称为信息增益，它是由于知道属性A的值而导致的熵的期望压缩。具有最高信息增益的属性选作给定集合S的测试属性。创建一个节点，并以该属性标记，对属性的每个值创建分枝，并据此划分样本。例：构造决策树。下表给出了取自AllElectronics

4、顾客数据库元组训练集。编号年龄收入学生信用等级类别：购买电脑1<=30高否一般不会购买2<=30高否良好不会购买331…40高否一般会购买4>40中等否一般会购买5>40低是一般会购买6>40低是良好不会购买731…40低是良好会购买8<=30中等否一般不会购买9<=30低是一般会购买10>40中等是一般会购买11<=30中等是良好会购买1231…40中等否良好会购买1331…40高是一般会购买14>40中等否良好不会购买解：由题意可知：s＝14，类标号属性“购买电脑”有两个不同值（即｛会购买，不会购买｝），因

5、此有两个不同的类（即m＝2）。设类C1对应于“会购买”，类C2对应于“不会购买”。则s1＝9，s2＝5，p1＝9/14，p2=5/14。①计算对给定样本分类所需的期望信息：②计算每个属性的熵。先计算属性“年龄”的熵。对于年龄＝“<=30”：s11＝2，s21＝3，p11=2/5，p21=3/5，对于年龄＝“31…40”：s12=4，s22=0，p12=4/4=1，p22=0，对于年龄＝“>40”：s13=3，s23=2，p13=3/5，p23=2/5，如果样本按“年龄”划分，对一个给定的样本分类所需的期望信息为

6、：因此，这种划分的信息增益是Gain(年龄)=I(s1,s2)-E(年龄)=0.246。计算“收入”的熵。对于收入＝“高”：s11=2，s21=2，p11=0.5，p21=0.5，对于收入＝“中等”：s12=4，s22=2，p12=4/6，p22=2/4，对于收入＝“低”：s13=3，s23=1，p13=3/4，p23=1/4，如果样本按“收入”划分，对一个给定的样本分类所需的期望信息为：因此，这种划分的信息增益是Gain(收入)=I(s1,s2)-E(收入)=0.940-0.911＝0.029。计算“学生”的

7、熵。对于学生＝“是”：s11=6，s21=1，p11=6/7，p21=1/7，对于学生＝“否”：s12=3，s22=4，p12=3/7，p22=4/7，如果样本按“学生”划分，对一个给定的样本分类所需的期望信息为：因此，这种划分的信息增益是Gain(学生)=I(s1,s2)-E(学生)=0.940-0.789＝0.151。计算“信用等级”的熵。对于信用等级＝“一般”：s11=6，s21=2，p11=6/8，p21=2/8，对于信用等级＝“良好”：s12=3，s22=3，p12=3/6，p22=3/6，如果样本按

8、“信用等级”划分，对一个给定的样本分类所需的期望信息为：因此，这种划分的信息增益是Gain(信用等级)=I(s1,s2)-E(信用等级)=0.940-0.892＝0.048。由于“年龄”属性具有最高信息增益，它被选作测试属性。创建一个节点，用“年龄”标记，并对每个属性值引出一个分支。样本据此划分，如图所示。收入学生信用等级类高否一般会购买低是良好会购买中等否良好会购买高是一般会购买收入