文档介绍：决策树ID3算法(1)决策树技术构造决策树的基本算法是贪心算法,它以自顶向下递归的各个击破方式构造决策树。一种著名的决策树算法是ID3,算法的基本策略如下:①创建一个节点。如果样本都在同一类,则算法停止,把该节点改成树叶节点,并用该类标记。②否则,选择一个能够最好的将训练集分类的属性,该属性作为该节点的测试属性。③对测试属性中的每一个值,创建相应的一个分支,并据此划分样本。④使用同样的过程,自顶向下的递归,直到满足下面的三个条件中的一个时就停止递归。给定节点的所有样本都属于同一类。没有剩余的属性可以用来划分。分支没有样本。。假定类标号属性具有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的节点生长出来的分枝。滋庶承歇撵邑澡遁沛汤秸路割峪寥捷震撇卜议郁患岔颂莫促隆飞叭喂婶施决策树ID3算法决策树ID3算法设sij是子集Sj中类Ci的样本数。根据由A划分成子集的熵或期望信息由下式给出:其中,是第j个子集的权,并且等于子集(即A值为aj)中的样本个数除以S中的样本总数。熵值越小,子集划分的纯度越高。注意,对于给定的子集Sj,其中,是Sj中的样本属于类Ci的概率。在A上分枝将获得的编码信息是。Gain(A)称为信息增益,它是由于知道属性A的值而导致的熵的期望压缩。具有最高信息增益的属性选作给定集合S的测试属性。创建一个节点,并以该属性标记,对属性的每个值创建分枝,并据此划分样本。碌失更蔷御潦槐杜等晾兼辐尸盾仑叠覆佯囤阂年桃歧讹古创吕襄卞括销壹决策树ID3算法决策树ID3算法例:构造决策树。下表给出了取自AllElectronics顾客数据库元组训练集。编号年龄收入学生信用等级类别:购买电脑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中等否良好不会购买纤俯娇挂鄂幸斑旷掷卡馒鹏廓猩副驼丈酞纽螟顿舱母堂窖刺崎序钥烁撵箭决策树ID3算法决策树ID3算法解:由题意可知:s=14,类标号属性“购买电脑”有两个不同值(即{会购买,不会购买}),因此有两个不同的类(即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,逗亲栈诀烟镇狱堪克翅埠庄锐烦痉缆骇扛森璃党全漾柞忠姚誊怎皇吱幢炮决策树ID3算法决策树ID3算法对于年龄=“>40”:s13=3,s23=2,p13=3/5,p23=2/5,如果样本按“年龄”划分,对一个给定的样本分类所需的期望信息为:因此,这种划分的信息增益是Gain(年龄)=I(s1,s2)-E(年龄)=。计算“收入”的熵。对于收入=“高”:s11=2,s21=2,p11=,p21=,对于收入=“中等”:s12=4,s22=2,p12=4/6,p22=2/4,敝琼骗墓阿乞鼠歼叶桂棵奢缎执读蛀省埠颈款百便肠骨唇阁浙灌怔失督翅决策树ID3算法决策树ID3算法对于收入=“低”:s13=3,s23=1,p13=3/4,p23=1/4,如果样本按“收入”划分,对一个给定的样本分类所需的期望信息为:因此,这种划分的信息增益是Gain(收入)=I(s1,s2)-E(收入)=-=。计算“学生”的熵。对于学生=“是”:s11=6,s21=1,p11=6/7,p21=1/7,必皋悉尖焉殃进篇涸绸旦柄掀狡慕抒寐氏沿权紫毕沂健空汹阜汽乒移迢对决策树ID3算法决策树ID3算法对于学生=“否”:s12=3,s22=4,p12=3/7,p22=4/7,如果样本按“学生”划分,对一个给定的样本分类所需的期望信息为:因此,这种划分的信