FAFU机器学习 06-1ecisionree中文.pptxVIP

机器学习决策树基础 数据挖掘十大算法C4.5.K均值支持向量机先验的EM（最大似然）PageRank阿达博斯特KNN奈韦巴耶斯推车 主要分类方法逻辑回归线性判别分析决策树归纳最近的邻居贝叶斯分类方法反向传播分类支持向量机集合方法… 说明分类任务 决策树示例 决策树的另一个例子 决策树分类任务 对测试数据应用模型 决策树分类任务 10决策树归纳算法许多算法:亨特算法（最早的算法之一）ID3（迭代二分法）C4.5.分类回归树任务中的监督学习决策树的可伸缩性，可并行化归纳…… 11决策树归纳算法基本算法（一种贪婪算法）树是以自顶向下递归分治的方式构造的在开始时，所有的训练例子都是在根部属性是范畴的（如果是连续值，则它们被预先离散化）示例是基于所选属性递归分区的基于启发式或统计度量（例如，信息增益）选择测试属性停止分区的条件给定节点的所有样本都属于同一个类没有剩余的属性用于进一步的分区--采用多数投票来对叶进行分类没有样本了… 12决策树归纳算法 13决策树归纳算法贪婪的策略基于优化某些标准的属性测试拆分记录（）问题确定如何选择最佳属性？如何拆分到记录？如何确定最佳拆分？确定何时停止分裂 14决策树归纳算法如何拆分记录？取决于属性类型名义上序数连续的取决于拆分方式的数量2路分流多路分流 15决策树归纳算法基于名义属性的拆分？多路拆分:使用与不同值一样多的分区二进制拆分:将值分成两个子集需要找到最优分区 16决策树归纳算法基于序数属性的拆分？多路拆分:使用与不同值一样多的分区二进制拆分:将值分成两个子集需要找到最优分区 17决策树归纳算法基于连续属性的拆分离散化以形成有序的范畴属性二进制判决:(Av)或(A=v)consider all possible splits and finds the best cut can be more computation intensive 18Algorithm for Decision Tree InductionGreedy strategy Split the records based on an attribute test that optimizes certain criterion Issues Determine how to select the best attributeHow to split the records? How to determine the best split? Determine when to stop splitting 19Algorithm for Decision Tree InductionHow to determine the Best SplitBefore Splitting: 10 records of class C0, 10 records of class C1 20Algorithm for Decision Tree InductionHow to determine the Best SplitGreedy approach: Nodes with homogeneous class distribution are preferred Need a measure of node impurity (purity): 21How to determine the Best SplitNeed a measure 22Measures of Node Impurity EntropyGini Index … Brief Review of Entropy?23m = 2 24Attribute Selection Measure: Information Gain (ID3/C4.5)Select the attribute with the highest information gainLet pi be the probability that an arbitrary tuple in D belongs to class Ci, estimated by |Ci, D|/|D|Expected information (entropy) needed to classify a tuple in D:Information needed (after using A to split D into v partitions) to classify D:Information gained by branching on attribute AInformation gain is the difference between the entropy of the parent n