最新精品课程完整(第8讲)---数据分类-决策树ppt课件

1、数据分类-决策树目录根本概念决策树ID3算法决策树C4.5算法2学习目的1.掌握数据分类的根本原理和评价目的2.了解两种决策树算法3Part I数据分类的根本概念4定义数据分类是指把数据样本映射到一个事先定义的类中的学习过程即给定一组输入的属性向量及其对应的类，用基于归纳的学习算法得出分类分类问题是数据发掘领域中研讨和运用最为广泛的技术之一，如何更准确、更有效地分类不断是人们追求的目的数据分类的义务经过学习得到一个目的函数f，把每个属性集x映射到一个预先定义的类标号y5分类的例如两类分类例如银行业：区分高端信誉卡和低端信誉卡医疗诊断：区分正常细胞和癌细胞互联网：区分正常邮件和渣滓邮件多类分类例

2、如油气传输：区分行人走过、汽车碾过、镐刨、电钻等行为文字识别：区分不同的字符其中汉字识别是一个大类别问题社会网络：区分中心用户、活泼用户、不活泼用户、马甲用户等6例如数据集数据集包含多个描画属性和一个类别属性普通来说描画属性：延续值或离散值类别属性：只能是离散值目的属性延续对应回归问题AgeSalaryClass30highc125highc221lowc243highc118lowc233lowc1.7分类问题的方式化描画8分类的过程获取数据预处置分类决策分类器设计9获取数据数值型数据病例中的各种化验数据空气质量监测数据描画性数据人事部门档案资料图片型数据指纹、掌纹自然场景图片很多情况下，需

3、求将上述数据一致转换为数值型数据序列，即构成特征向量特征提取10预处置为了提高分类的准确性和有效性，需求对分类所用的数据进展预处置去除噪声数据对空缺值进展处置数据降维特征选择-PCA、LDA 主成分分析 Principal Component Analysis ， PCA 线性鉴别分析(LinearDiscriminantAnalysis,LDA)，有时也称Fisher线性判别(FisherLinearDiscriminant,FLD)，这种算法是RonaldFisher于1936年发明的，是方式识别的经典算法。11分类器设计1-划分数据集给定带有类标号的数据集，并且将数据集划分为两个部分训练

4、集training set测试集testing set划分战略1.当数据集D的规模较大时 训练集2|D|/3，测试集是1|D|/32.当数据集D的规模不大时 n交叉验证法n-fold validation将数据集随机地划分为n组之后执行n次循环，在第i次循环中，将第i组数据样本作为测试集，其他的n-1组数据样本作为训练集,最终的精度为n个精度的平均值。123.当数据集D的规模非常小时每次交叉验证时，只选择一条测试数据，剩余的数据均作为训练集。原始数据集有m条数据时，相当于m-次交叉验证。是N-次交叉验证的一个特例。 分类器设计2-分类器构造利用训练集构造分类器分类模型经过分析由属性描画的每类样

5、本的数据信息，从中总结出分类的规律性，建立判别公式或判别规那么在分类器构造过程中，由于提供了每个训练样本的类标号，这一步也称作监视学习supervised learning14分类器设计3-分类器测试利用测试集对分类器的分类性能进展评价，详细方式是首先，利用分类器对测试集中的每一个样本进展分类其次，将分类得到的类标号和测试集中数据样本的原始类标号进展对比由上述过程得到分类器的分类性能如何评价？15分类决策在构呵斥功分类器之后经过测试，那么可以利用该分类器实践执行分类16分类的评价准那么-商定和假设17分类的评价准那么-目的1准确度accuracy是最常用的评价准那么代表测试集中被正确分类的数据

6、样本所占的比例反映了分类器对于数据集的整体分类性能18分类的评价准那么-目的2查全率recall第j个类别的查全率召回率表示在本类样本中，被正确分类的样本占的比例代表该类别的分类精度19分类的评价准那么-目的3查准率precision第j个类别的查准率表示被分类为该类的样本中，真正属于该类的样本所占的比例代表该类别的分类纯度20分类的评价准那么-目的4F-measure可以比较合理地评价分类器对每一类样本的分类性能它是查全率和查准率的组合表达式其中参数是可以调理的，通常取值为121分类的评价准那么-目的5几何均值G-mean它能合理地评价数据集的整体分类性能是各个类别查全率的平方根，当各个类别

7、的查全率都大时才增大同时兼顾了各个类别的分类精度22延伸阅读Jin-Mao Wei, Xiao-Jie Yuan, et al. A novel measure for evaluating classifiers, Expert Systems with Applications, 37(2021):3799-380923关于数据分类的小结所谓分类即是运用某种分类模型，以对象的假设干维描画属性为输入，经过计算输出该对象所属类别的过程数据分类的两个关键步骤是分类器训练：选定适宜的分类模型及参数分类器测试：利用适宜的目的检验分类器有效性目前已有一些成熟的分类器可供运用决策树支持向量机最近邻/k-

8、近邻24Part II决策树算法25决策树是一种以给定的数据样本为根底的归纳学习方法在给定知类标号的数据集的情况下，采用自顶向下的递归方式来产生一个类似于流程图的树构造树的最顶层节点是根节点最底层节点是叶节点：代表样本的类别根节点和叶节点之间的节点是内部节点决策树方法在根节点和内部节点上根据给定的度量规范来选择最适宜的描画属性作为分支属性并根据该属性的不同取值向下建立分支26决策树例如-购买保险A1-公司职员A2-年龄A3-收入A4-信誉度C-买保险否=40高良c2否50中良c1是50低良c1是50低优c2是4150低优c1否=40中良c2是50中良c1是50中优c227保险决策树处理了哪类人

9、更倾向于购买保险的问题年龄信誉度公司职员c1c1c2c1c250是否良优28决策树向程序文语的转化if (年龄=40 & 是公司职员)买保险if (年龄50 & 信誉度为良)买保险if (年龄50 & 信誉度为优)不买保险29根本决策树方法根本算法 (贪婪算法)自顶向下的分治算法构造树开场, 一切的训练样本和树根相连属性为分类属性 (假设是延续值，那么离散化)根据选定的属性递归地划分样本?如何选择基于启发式或统计度量选取测试属性 (e.g., 信息增益)停顿划分的准那么一切样本均和属于同一类的节点衔接无剩下的属性用于继续划分样本 叶节点分类运用多数表决法无剩余的样本其它的提早中止法30属性选择

10、度量属性选择度量划分规那么划分属性：度量得分高的属性流行的属性选择度量信息增益(ID3， C4.5)选取时，偏向于多值属性增益率(C4.5)偏向不平衡划分Gini目的( CART, SLIQ, SPRINT)偏向于多值属性类的数量很大时，计算较困难信息增益(Information Gain)基于信息论“熵，选取具有最大信息增益的属性划分在属性节点A处，样本集D所具有的熵 (p( j | D) 为类 j 在节点 t处的概率).度量节点的均质性当一切的类均匀分布时，最大为 (log nc)，具有 最多信息当只需一切样本属于一类时，最小为 (0.0) ，具有最少信息在属性A处，将样本分为v类的信息量

11、经过在属性A，构成v个分支后，信息增益为,增益最大的选为划分属性信息增益例子类 P: buys_computer = “yes类 N: buys_computer = “no 指 14个样本中有5个“age =30, 两个属于类p，2个属于类N ,因此Similarly,决策树首层age?4030.40增益率(Gain Ratio)C4.5 (ID3的后继算法) 运用增益率抑制信息增益的偏斜性 (信息增益的规范化)Ex.GainRatio(income) = 0.029/0.926 = 0.031具有最大增益率的属性选为划分属性信息增益缺陷: 倾向于选择分割数目多的属性。Gini指数Gini指

12、数:节点属性 A划分样本的不纯度，设样本集为D(NOTE: p( j | D) 类 j 在样本D中的概率).当一切样本均匀分布在不同类时，最大为(1 - 1/nc), 表示最小兴趣信息当一切的样本属于一类时，最小 为(0.0)，表示最大兴趣信息Gini例子P(C1) = 0/6 = 0 P(C2) = 6/6 = 1Gini = 1 P(C1)2 P(C2)2 = 1 0 1 = 0 P(C1) = 1/6 P(C2) = 5/6Gini = 1 (1/6)2 (5/6)2 = 0.278P(C1) = 2/6 P(C2) = 4/6Gini = 1 (2/6)2 (4/6)2 = 0.444

13、基于Gini指数的划分用于CART算法在节点A，将训练集D划分为k个子集(子节点Di )，那么以划分的不纯度加权和度量其优劣 ni = 子树 的训练样本个数i, n = 节点p处训练样本个数.二值属性的Gini指数划分为两个子集带权划分的效果: Gini指数越小越好寻求更大和更纯的划分B?YesNoNode N1Node N2Gini(D1) = 1 (5/7)2 (2/7)2 = 0.174 Gini(D2) = 1 (1/5)2 (4/5)2 = 0.32Gini(Children) = 7/12 * 0.174 + 5/12 * 0.32= 0.204决策树归纳算法算法种类多Hunts

14、Algorithm (one of the earliest)CARTID3, C4.5SLIQ,SPRINTID3算法原理选择具有较高信息增益的描画属性作为给定数据集X的分支属性，从而创建决策树中的一个节点根据该描画属性的不同取值再创建分支之后对各个分支中的样本子集递归调用上述方法建立下一级子节点当某个分支上的一切数据样本都属于同一个类别时划分停顿，构成叶节点或者当某个分支上的样本不属于同一个类别，但是又没有剩余的描画属性可以进一步划分数据集时也构成叶节点，并且用多数样本所属的类别来标志这个叶节点41ID3算法例如该样本集中共包含4个描画属性和1个类别属性，空间容量为14目的是利用ID3思想

15、构建一棵可用于新样本分类的决策树A1-公司职员A2-年龄A3-收入A4-信誉度C-买保险否=40高良c2否50中良c1是50低良c1是50低优c2是4150低优c1否=40中良c2是50中良c1是50中优c242第1步：计算对训练集分类所需的期望信息知total=14c1(买保险)的样本数量是n1=9c2(不买保险)的样本数量是n2=5所以P(c1)=9/14P(c2)=5/14根据期望信息公式可得43第2步：计算A1公司职员的熵A1包含两种取值：“是和“否利用A1可将X划分为两个子集X1和X2X1中的数据样本都是公司职员7个标号为c1的有6个，n11=6标号为c2的有1个，n21=1那么可得

16、p11=6/7p21=1/7A1-公司职员C-买保险否c2否c2否c1否c1是c1是c2是c1否c2是c1是c1是c1否c1是c1否c244第2步：计算A1公司职员的熵利用A1可将X划分为两个子集X1和X2X2中的数据样本都不是公司职员7个标号为c1的有3个，n12=3标号为c2的有4个，n22=4那么可得p12=3/7p22=4/7A1-公司职员C-买保险否c2否c2否c1否c1是c1是c2是c1否c2是c1是c1是c1否c1是c1否c245第2步：计算A1公司职员的熵那么计算出A1划分训练集所得的熵为46第3步：计算A1公司职员的信息增益47第4步：求出其他描画属性的信息增益Gain(A2

17、)=0.246Gain(A3)=0.029Gain(A4)=0.048经比较可知Gain(A2)最大，所以选择A2年龄作为决策树的根节点进一步将树划分为3个分支48第5步：根据根节点划分数据集年龄50的子集在此子集内继续检查Gain(A1)、Gain(A3)、Gain(A4)选取信息增益最大的描画属性作为内部节点A1-公司职员A3-收入A4-信誉度C-买保险否中良c1是低良c1是低优c2是中良c1否中优c251ID3算法小结运用ID3算法的根本思想是采用自顶向下的递归方式，将原始样本空间划分成假设干更小的样本空间再对他们单独进展处置其中，选择哪一个描画属性作为新建节点，根据是调查该描画属性的信

18、息增益能否最大52Part IIIC4.5算法下载地址httprulequest/Personal/53ID3的缺乏1/2运用信息增益作为属性选择根据带有倾向性，倾向于选择取值较多的属性 为什么？一种能够的解释是：对于较难分类的集合，优先将样本分割到尽能够多的分支中将极大简化分类任务54ID3的缺乏2/2无法处置未知值的样本对于个别样本缺失了某项描画属性的情况，无法处置无法处置延续值的样本对于描画属性是延续值的情况，无法处置55变化一：运用信息增益比56变化二：处置未知值的训练样本1/2思想将未知值用最常用的值来替代较容易或，根据现有取值的概率分布来估计未知值较真实显然：根据思想一，在知样本中

19、年龄的三个区间分布是50，5人那么可以直接指定未知值为“50A2-年龄C-买保险=40c250c150c150c24150c1=40c250c1？c14150c14150c150c257变化二：处置未知值的训练样本2/2思想将未知值用最常用的值来替代较容易或，根据现有取值的概率分布来估计未知值较真实显然：根据思想二，在知样本中年龄的三个区间分布是50，5人思索未知值样本后，分布更新为50，5+5/13人A2-年龄C-买保险=40c250c150c150c24150c1=40c250c1？c14150c14150c150c258变化三：处置延续值的训练样本1/10思想将一切数据样本按照延续型描画

20、属性Ac的详细取值，由小到大进展升序陈列，得到的属性值取值序列A1c,A2c,.,Atotalc在A1c,A2c,.,Atotalc中生成total-1个分割点，第i个分割点的取值设置为vi=(Aic+A(i+1)c)/2或者vi=Aic该分割点将数据集划分为两个子集，即描画属性Ac的取值在区间A1c,vi的数据样本和在区间(vi,Atotalc的数据样本，显然划分共有total-1种方式从total-1个分割点中选择最正确分割点。对于每一个分割点划分数据集的方式，计算其信息增益比，从中选择信息增益比最大的分割点来划分数据集59变化三：处置延续值的训练样本2/10例如求利用C4.5算法在延续值

21、描画属性A上的最正确分割点解：第0步，将A的取值升序陈列65,70,70,70,75,78,80,80,80,85,90,90,95,96第1步，计算vi=65时的信息增益比AC85c290c278c196c180c170c265c195c270c180c170c190c175c180c260变化三：处置延续值的训练样本3/10解：第1步，计算vi=65时的信息增益比AC85c290c278c196c180c170c265c195c270c180c170c190c175c180c261变化三：处置延续值的训练样本4/10解：第1步，计算vi=65时的信息增益比AC85c290c278c196c180c170c265c195c270c180c170c190c175c180c262变化三：处置延续值的训练样本5/10解：第2步，计算vi=70时的信息增益比AC85c290c278c196c180c170c265c195c270c180c170c190c175c180c263变化三：处置延续值的训练样本6/10解：第2步，计算vi=70时的信息增益比AC85c290c278c196c180c170c265c195c270c180c170c190c175c180c264变化三：处置延续值的训练样本7/10解：第2步，计