模式识别决策树分类.ppt
模式识别决策树分类2022-9-71现在学习的是第1页，共12页数据实例 PlayTennis数据库片段：2022-9-72现在学习的是第2页，共12页决策树实例 关于PlayTennis的决策树：High Overcast Normal Strong Weak Sunny Rain Outlook Wind Humidity No Yes Yes No Yes 2022-9-73现在学习的是第3页，共12页决策树学习算法的代表 早在1986年的时候，Quinlan就提出了著名的ID3算法。（Published on MLJ）用ID3算法长树的基本思想：分类能力最好的属性被测试并创建树的根结点 测试属性每个可能的值产生一个分支 训练样本划分到适当的分支形成儿子结点 重复上面的过程，直到所有的结点都是叶子结点两个问题：什么属性最好？什么结点才是叶子结点？两个问题：什么属性最好？什么结点才是叶子结点？2022-9-74现在学习的是第4页，共12页信息增益（Information Gain）属性A划分样本集S的信息增益Gain(S,A)为：Gain(S,A)=E(S)E(S,A)其中，E(S)为划分样本集S为c个类的熵；E(S,A)为属性A划分样本集S导致的期望熵。2022-9-75现在学习的是第5页，共12页熵（Entropy）划分样本集S为c个类的熵E(S)为：其中，pi ni/n，为S中的样本属于第i类Ci的概率，n为S中样本的个数。ciiippSE12log2022-9-76现在学习的是第6页，共12页期望熵（Expected Entropy）属性A划分样本集S导致的期望熵E(S,A)为：其中，Values(A)为属性A取值的集合；Sv为S中A取值为v的样本子集，Sv=sSA(s)=v；E(Sv)为将Sv中的样本划分为c个类的信息熵。|Sv|/|S|为Sv和S中的样本个数之比。AValuesvvvSESSASE,2022-9-77现在学习的是第7页，共12页回味ID3算法 ID3算法每一步选择具有最大信息增益的属性作为测试属性来长树。直到最大的信息增益为也零为止。（两个问题的解决两个问题的解决）熵（Entropy）刻画了样本集的纯度，长树的过程是一个熵降低、信息增益、从混沌到有序的过程。（长树的物理意义长树的物理意义）2022-9-78现在学习的是第8页，共12页伪代码 算法 Decision_Tree（samples,attribute_list）输入 由离散值属性描述的训练样本集samples；候选属性集合atrribute_list。输出 一棵决策树。方法 (1)创建节点N；(2)if samples 都在同一类C中 then (3)返回N作为叶节点，以类C标记；(4)if attribute_list为空 then 2022-9-79现在学习的是第9页，共12页伪代码（续）(5)返回N作为叶节点，以samples中最普遍的类标记；/多数表决(6)选择attribute_list中具有最高信息增益的属性test_attribute；(7)以test_attribute标记节点N；(8)for each test_attribute的已知值v /划分samples(9)由节点N分出一个对应test_attribute=v的分支；(10)令Sv为samples中test_attribute=v的样本集合；/一个划分块(11)if Sv为空 then(12)加上一个叶节点，以samples中最普遍的类标记；(13)else 加入一个由Decision_Tree(Sv,attribute_listtest_attribute)返回的节点。2022-9-710现在学习的是第10页，共12页ID3算法的不足及改进 ID3算法存在的主要不足：过度拟合问题(tree prunning)处理连续属性值问题(discretization)处理缺少属性值问题(replacement)属性选择的度量标准问题(heuristic measure)针对这些不足，Quinlan做了一系列的改进，并于1993年形成了C4.5算法。（C4.5:Programs for Machine Learning）2022-9-711现在学习的是第11页，共12页决策树学习总结 决策树（Decision Tree）学习是以样本为基础的归纳学习方法，它采用自顶向下的递归方式来构造决策树。（贪心算法贪心算法）决策树的表现形式是类似于流程图的树结构，在决策树的内部结点进行属性值测试，并根据属性值判断由该结点引出的分支，最后在决策树的叶子结点分类。（学习阶段、训练阶段学习阶段、训练阶段）由训练样本集学到决策树后，为了对未知样本分类，需要在决策树上测试未知样本的属性值。测试路径由根结点到某个叶子结点，叶子结点代表的类就是未知样本所属的类。（工作阶段、测试阶段工作阶段、测试阶段）2022-9-712现在学习的是第12页，共12页
