机器学习__ID算法.pptxVIP

ID3算法 决策树一个决策树是一个类似于流程图的树结构，通过一系列规则对数据进行分类的过程。其中每个内部节点表示在一个属性上的测试，每个分枝代表一个测试的结果，叶节点代表类或类分布。天气晴朗多云有雨 湿度 高 正常 风力强 弱NoYesYesYesNo ID3算法构造过程：从代表所有训练样本的单个根节点开始使用分类属性（如果是量化属性，则需先进行离散化）递归的通过选择相应的分裂属性，来划分样本，一旦一个属性出现在一个节点上，就不在该节点的任何后代上出现分裂属性是根据某种启发信息或者是统计信息来进行选择分裂结点叶子结点分裂结点分裂结点叶子结点叶子结点决策树结构自顶向下的分治方式构造判定树 ID3算法预备知识：信息熵?度量X的不确定性 ID3算法熵?信息增益：计算当前划分对信息熵所造成的变化划分前的信息熵划分后的信息熵值越大，越好值越小，则D的纯度越高比较划分前后父亲结点与其所有儿子结点纯度的提升程度。选择“最好”的分裂属性满足分支的数据子集 ID3算法计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买假定公司收集了左表数据，那么对于任意给定的客人（测试样例），你能帮助公司将这位客人归类吗？即：你能预测这位客人是属于“买”计算机的那一类，还是属于“不买”计算机的那一类？又：你需要多少有关这位客人的信息才能回答这个问题？决策树可以帮助你解决好这个问题 ID3算法计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买分类属性：买计算机？共分两类(m=2): 买/不买 D1 = 640, D2 = 383 D = D1+ D2 = 1024 p1 = D1 /D = 640/1023 = 0.6260 p2 = D2 /D = 383/1023 = 0.3740Ent(D) = - (p1 log2(p1) + p2 log2(p2)) = 0.954训练数据 ID3算法计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买年龄计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128青中否良不买64青低是良买64青中是优买计数年龄收入学生信誉归类：买计算机？128中高否良买64中低是优买32中中否优买32中高是良买计数年龄收入学生信誉归类：买计算机？60老中否良买64老低是良买64老低是优不买132老中是良买63老中否优不买青中老 ID3算法计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买年龄计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128青中否良不买64青低是良买64青中是优买计数年龄收入学生信誉归类：买计算机？128中高否良买64中低是优买32中中否优买32中高是良买计数年龄收入学生信誉归类：买计算机？60老中否良买64老低是良买64老低是优不买132老中是良买63老中否优不买青中老信息期望=？信息期望=0信息期望=？信息期望=？ ID3算法假定选择年龄作树根节点，则： 青年组: Ent(D1)=0.9183 中年组: : Ent(D2)=0 老年组: Ent(D3)=0.9157 青年组比例: (128+256)/1023=0.375 中年组比例: 256/1024=0.25 老年组比例: (257+127)/1023=0.375平均信息期望（加权总和）： E(年龄）= 0.375*0.9183 +0.25*0+0.375*0.9157 = 0.6877计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128青中否良不买64青低是良买64青中是优买计数年龄收入学生信誉归类：买计算机？128中高否良买64中低是优买32中中否优买32中高是良买计数年龄收入学生信誉归类：买计算机？60老中否