《【教学课件】第5讲专家系统.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第5讲专家系统.ppt（13页珍藏版）》请在三一办公上搜索。
1、1,第5讲 专家系统,2,决策树学习概述,决策树（Decision Tree）学习是以样本为基础的归纳学习方法。决策树的表现形式是类似于流程图的树结构，在决策树的内部节点进行属性值测试，并根据属性值判断由该节点引出的分支，在决策树的叶节点得到结论。内部节点是属性或属性的集合，叶节点代表样本所属的类或类分布。经由训练样本集产生一棵决策树后，为了对未知样本集分类，需要在决策树上测试未知样本的属性值。测试路径由根节点到某个叶节点，叶节点代表的类就是该样本所属的类。,3,数据实例,PlayTennis数据库片段：,4,决策树实例,关于PlayTennis的决策树如图所示：,5,决策树学习算法的代表,决
2、策树学习的基本算法是贪心算法，采用自顶向下的递归方式构造决策树。Quinlan于1986年提出了著名的ID3算法（published on ML）。之后Quinlan对ID3算法做了一系列的改进，于1993年形成了C4.5算法。,6,ID3算法,ID3的思想自顶向下构造决策树从“哪一个属性将在树的根节点被测试”开始使用统计测试来确定每一个实例属性单独分类训练样例的能力ID3的过程分类能力最好的属性被选作树的根节点根节点的每个可能值产生一个分支训练样例排列到适当的分支重复上面的过程,7,伪代码,算法 Decision_Tree（samples,attribute_list）输入 由离散值属性描述
3、的训练样本集samples；候选属性集合atrribute_list。输出 一棵决策树。方法(1)创建节点N；(2)if samples 都在同一类C中 then(3)返回N作为叶节点，以类C标记；(4)if attribute_list为空 then,8,伪代码（续）,(5)返回N作为叶节点，以samples中最普遍的类标记；/多数表决(6)选择attribute_list中具有最高信息增益的属性test_attribute；(7)以test_attribute标记节点N；(8)for each test_attribute的已知值v/划分samples(9)由节点N分出一个对应test_a
4、ttribute=v的分支；(10)令Sv为samples中test_attribute=v的样本集合；/一个划分块(11)if Sv为空 then(12)加上一个叶节点，以samples中最普遍的类标记；(13)else 加入一个由Decision_Tree(Sv,attribute_listtest_attribute)返回的节点。,9,信息熵,ID3算法采用基于信息熵定义的信息增益度量来选择内节点的测试属性。熵（Entropy）刻画了任意样本集的纯度。设S是n个数据样本的集合，将样本集划分为c个不同的类Ci(i=1,2,c)，每个类Ci含有的样本数目为ni，则S划分为c个类的信息熵或期望
5、信息为：其中，pi为S中的样本属于第i类Ci的概率，即pini/n。,10,信息熵（续）,熵值反映了对样本集合S分类的不确定性，也是对样本分类的期望信息。熵值越小，划分的纯度越高，对样本分类的不确定性越低。一个属性的信息增益，就是用这个属性对样本分类而导致的熵的期望值下降。因此，ID3算法在每一个节点选择取得最大信息增益的属性。,11,期望熵,假设属性A的所有不同值的集合为Values(A)，Sv是S中属性A的值为v的样本子集，即Sv=sSA(s)=v，在选择属性A后的每一个分支节点上，对该节点的样本集Sv分类的熵为E(Sv)。选择A导致的期望熵定义为每个子集Sv的熵的加权和，权值为属于Sv的
6、样本占原始样本S的比例，即期望熵为：其中，E(Sv)是将S v中的样本划分到c个类的信息熵。,12,信息增益,属性A相对样本集合S的信息增益Gain(S,A)定义为：Gain(S,A)=E(S)E(S,A)Gain(S,A)是指因知道属性A的值后导致的熵的期望压缩。Gain(S,A)越大，说明选择测试属性A对分类提供的信息越多。Quinlan的ID3算法就是在每个节点选择信息增益Gain(S,A)最大的属性作为测试属性。,13,ID3算法的不足及改进,ID3算法存在的主要不足过度拟合问题处理连续属性值问题处理缺少属性值问题属性选择的度量标准问题处理不同代价的属性问题针对ID3的这些不足，ID3被扩展成为C4.5,
