数据分类-决策树

《数据分类-决策树》由会员分享，可在线阅读，更多相关《数据分类-决策树（71页珍藏版）》请在装配图网上搜索。

1、数据分类数据分类-决策树决策树目录目录v 基本概念基本概念v 决策树决策树ID3ID3算法算法v 决策树决策树C4.5C4.5算法算法学习目标学习目标1.1.掌握数据分类的基本原理和评价指标掌握数据分类的基本原理和评价指标2.2.了解两种决策树算法了解两种决策树算法定义定义v 数据分类数据分类 是指把数据样本映射到一个事先定义的类中的学习过程是指把数据样本映射到一个事先定义的类中的学习过程 即给定一组输入的属性向量及其对应的类，用基于归纳的学习算即给定一组输入的属性向量及其对应的类，用基于归纳的学习算法得出分类法得出分类 分类问题是数据挖掘领域中研究和应用最为广泛的技术之一，如分类问题是数据挖

2、掘领域中研究和应用最为广泛的技术之一，如何更精确、更有效地分类一直是人们追求的目标何更精确、更有效地分类一直是人们追求的目标v 数据分类的任务数据分类的任务 通过学习得到一个目标函数通过学习得到一个目标函数f f，把每个属性集，把每个属性集x x映射到一个预先定映射到一个预先定义的类标号义的类标号y y分类的示例分类的示例v 两类分类示例两类分类示例 银行业：区分高端信用卡和低端信用卡银行业：区分高端信用卡和低端信用卡 医疗诊断：区分正常细胞和癌细胞医疗诊断：区分正常细胞和癌细胞 互联网：区分正常邮件和垃圾邮件互联网：区分正常邮件和垃圾邮件v 多类分类示例多类分类示例 油气传输：区分行人走过、

3、汽车碾过、镐刨、电钻等行为油气传输：区分行人走过、汽车碾过、镐刨、电钻等行为 文字识别：区分不同的字符文字识别：区分不同的字符（其中汉字识别是一个大类别问题）（其中汉字识别是一个大类别问题）社会网络：区分中心用户、活跃用户、不活跃用户、马甲用户等社会网络：区分中心用户、活跃用户、不活跃用户、马甲用户等示例数据集示例数据集v 数据集包含多个描述属性和一个类别属性数据集包含多个描述属性和一个类别属性v 一般来说一般来说 描述属性：连续值或离散值描述属性：连续值或离散值 类别属性：只能是离散值类别属性：只能是离散值（目标属性连续对应回归问题）（目标属性连续对应回归问题）AgeAgeSalarySal

4、aryClassClass30highc125highc221lowc243highc118lowc233lowc1.分类问题的形式化描述分类问题的形式化描述,m,d,),(d),2,1(,2,1|),(21212121miiididiiidiiiiiicccyxyAAAxxxxxxxtotalixtotaliyxX个类别，则假设给定数据集包含的类标号表示数据样本的具体取值个描述属性分别对应表示维特征向量用其中数据样本数据集分类的过程分类的过程获取数据预处理分类决策分类器设计获取数据获取数据v 数值型数据数值型数据 病例中的各种化验数据病例中的各种化验数据 空气质量监测数据空气质量监测数据v

5、描述性数据描述性数据 人事部门档案资料人事部门档案资料v 图片型数据图片型数据 指纹、掌纹指纹、掌纹 自然场景图片自然场景图片v 很多情况下，需要将上述数据统一转换为数值型数据序列很多情况下，需要将上述数据统一转换为数值型数据序列，即形成特征向量（，即形成特征向量（特征提取特征提取）预处理预处理v 为了提高分类的准确性和有效性，需要对分类所用的数据为了提高分类的准确性和有效性，需要对分类所用的数据进行预处理进行预处理 去除噪声数据去除噪声数据 对空缺值进行处理对空缺值进行处理 数据降维（数据降维（特征选择特征选择）-（PCAPCA、LDALDA）主成分分析主成分分析 （Principal Co

6、mponent Analysis Principal Component Analysis，PCA PCA）线性鉴别分析线性鉴别分析(LinearDiscriminantAnalysis,LDA)(LinearDiscriminantAnalysis,LDA)，有时也称，有时也称FisherFisher线性线性判别判别(FisherLinearDiscriminant,FLD)(FisherLinearDiscriminant,FLD)，这种算法是这种算法是RonaldFisherRonaldFisher于于 19361936年发明的，是模式识别的经典算法。年发明的，是模式识别的经典算法。分类

7、器设计分类器设计1-1-划分数据集划分数据集v 给定带有类标号的数据集，并且将数据集划分为两个部分给定带有类标号的数据集，并且将数据集划分为两个部分 训练集（训练集（training settraining set）测试集（测试集（testing settesting set）v 划分策略划分策略1.1.当数据集当数据集D D的的规模较大规模较大时时 训练集训练集2|D|/32|D|/3，测试集是，测试集是1|D|/31|D|/32.2.当数据集当数据集D D的的规模不大规模不大时时 n n交叉验证法（交叉验证法（n-fold validationn-fold validation）将数据集随

8、机地划分为将数据集随机地划分为n n组组 之后执行之后执行n n次循环，在第次循环，在第i i次循环中，将第次循环中，将第i i组数据样本作为测试集，其余的组数据样本作为测试集，其余的n-1n-1组数据样本作为训练集组数据样本作为训练集,最终的精度为最终的精度为n n个精度的平均值。个精度的平均值。当数据集当数据集D D的的规模非常小时规模非常小时v每次交叉验证时，只选择一条测试数据，剩余的数每次交叉验证时，只选择一条测试数据，剩余的数据均作为训练集。据均作为训练集。v原始数据集有原始数据集有mm条数据时，相当于条数据时，相当于mm-次交叉验证。次交叉验证。v是是N-N-次交叉验证的一个特例。

9、次交叉验证的一个特例。分类器设计分类器设计2-2-分类器构造分类器构造v 利用训练集构造分类器（分类模型）利用训练集构造分类器（分类模型）v 通过分析由属性描述的每类样本的数据信息，从中总结出通过分析由属性描述的每类样本的数据信息，从中总结出分类的规律性，建立判别公式或判别规则分类的规律性，建立判别公式或判别规则v 在分类器构造过程中，由于提供了每个训练样本的类标号在分类器构造过程中，由于提供了每个训练样本的类标号，这一步也称作监督学习（，这一步也称作监督学习（supervised learningsupervised learning）分类器设计分类器设计3-3-分类器测试分类器测试v 利用

10、测试集对分类器的分类性能进行评估，具体方式是利用测试集对分类器的分类性能进行评估，具体方式是 首先，利用分类器对测试集中的每一个样本进行分类首先，利用分类器对测试集中的每一个样本进行分类 其次，将分类得到的类标号和测试集中数据样本的原始类标号进其次，将分类得到的类标号和测试集中数据样本的原始类标号进行对比行对比 由上述过程得到分类器的分类性能（由上述过程得到分类器的分类性能（如何评价？如何评价？）分类决策分类决策v 在构造成功分类器之后（通过测试），则可以利用该分类在构造成功分类器之后（通过测试），则可以利用该分类器实际执行分类器实际执行分类分类的评价准则分类的评价准则-约定和假设约定和假设j

11、jjmiiiiiitestFPFNTPjcccyxyxNiyxX该类的样本数量是其他类别被错误分类为是被错误分类的样本数量是被正确分类的样本数量个类别，设定：对于测试集的第个类别，则假设分类问题含有的类标号；表示数据样本本；表示测试集中的数据样数；表示测试集中的样本个其中给定测试集,mN,2,1|),(21分类的评价准则分类的评价准则-指标指标1 1v 精确度（精确度（accuracyaccuracy）是最常用的评价准则是最常用的评价准则 代表测试集中被正确分类的数据样本所占的比例代表测试集中被正确分类的数据样本所占的比例 反映了分类器对于数据集的整体分类性能反映了分类器对于数据集的整体分类性

12、能NTPAccuracymjj1分类的评价准则分类的评价准则-指标指标2 2v 查全率（查全率（recallrecall）第第j j个类别的查全率（召回率）表示在本类样本中，被正确分类的个类别的查全率（召回率）表示在本类样本中，被正确分类的样本占的比例样本占的比例 代表该类别的代表该类别的分类精度分类精度jjjjFNTPTPRecalljjjFPFNTP该类的样本数量是其他类别被错误分类为是被错误分类的样本数量是被正确分类的样本数量分类的评价准则分类的评价准则-指标指标3 3v 查准率（查准率（precisionprecision）第第j j个类别的查准率表示被分类为该类的样本中，真正属于该类

13、的个类别的查准率表示被分类为该类的样本中，真正属于该类的样本所占的比例样本所占的比例 代表该类别的代表该类别的分类纯度分类纯度jjjjFPTPTPPrecisionjjjFPFNTP该类的样本数量是其他类别被错误分类为是被错误分类的样本数量是被正确分类的样本数量分类的评价准则分类的评价准则-指标指标4 4v F-measureF-measure 可以比较合理地评价分类器对每一类样本的分类性能可以比较合理地评价分类器对每一类样本的分类性能 它是查全率和查准率的组合表达式它是查全率和查准率的组合表达式 其中参数其中参数 是可以调节的，通常取值为是可以调节的，通常取值为1 1jjjjjPrecisi

14、onRecallPrecisionRecallmeasureF22)1(分类的评价准则分类的评价准则-指标指标5 5v 几何均值（几何均值（G-meanG-mean）它能合理地评价数据集的整体分类性能它能合理地评价数据集的整体分类性能 是各个类别查全率的平方根，当各个类别的查全率都大时才增大是各个类别查全率的平方根，当各个类别的查全率都大时才增大 同时兼顾了各个类别的分类精度同时兼顾了各个类别的分类精度mjjRecallmeanG1延伸阅读延伸阅读v Jin-Mao Wei,Xiao-Jie Yuan,et al.A novel measure Jin-Mao Wei,Xiao-Jie Yua

15、n,et al.A novel measure for evaluating classifiers,Expert Systems with for evaluating classifiers,Expert Systems with Applications,37(2010):3799-3809Applications,37(2010):3799-3809关于数据分类的小结关于数据分类的小结v 所谓分类即是使用某种分类模型，以对象的若干维描述属所谓分类即是使用某种分类模型，以对象的若干维描述属性为输入，经过计算输出该对象所属类别的过程性为输入，经过计算输出该对象所属类别的过程v 数据分类的两

16、个关键步骤是数据分类的两个关键步骤是 分类器训练：选定合适的分类模型及参数分类器训练：选定合适的分类模型及参数 分类器测试：利用合适的指标检验分类器有效性分类器测试：利用合适的指标检验分类器有效性v 目前已有一些成熟的分类器可供使用目前已有一些成熟的分类器可供使用 决策树决策树 支持向量机支持向量机 最近邻最近邻/k-/k-近邻近邻决策树决策树v 是一种以给定的数据样本为基础的归纳学习方法是一种以给定的数据样本为基础的归纳学习方法v 在给定已知类标号的数据集的情况下，采用自顶向下的递在给定已知类标号的数据集的情况下，采用自顶向下的递归方式来产生一个类似于流程图的树结构归方式来产生一个类似于流程

17、图的树结构 树的最顶层节点是根节点树的最顶层节点是根节点 最底层节点是叶节点：代表样本的类别最底层节点是叶节点：代表样本的类别 根节点和叶节点之间的节点是内部节点根节点和叶节点之间的节点是内部节点 决策树方法在根节点和内部节点上根据给定的决策树方法在根节点和内部节点上根据给定的度量标准度量标准来选择最来选择最适合的描述属性作为分支属性适合的描述属性作为分支属性 并根据该属性的不同取值向下建立分支并根据该属性的不同取值向下建立分支决策树示例决策树示例-购买保险购买保险A1-A1-公司职员公司职员A2-A2-年龄年龄A3-A3-收入收入A4-A4-信誉度信誉度C-C-买保险买保险否=40高良c2否

18、50中良c1是50低良c1是50低优c2是4150低优c1否=40中良c2是50中良c1是50中优c2保险决策树保险决策树v 解决了哪类人更倾向于购买保险的问题解决了哪类人更倾向于购买保险的问题年龄信誉度公司职员c1c1c2c1c250是否良优决策树向程序语言的转化决策树向程序语言的转化v if(if(年龄年龄=40&=40&是公司职员是公司职员)买保险买保险v if(if(年龄年龄=40&50&50&信誉度为良信誉度为良)买保险买保险v if(if(年龄年龄50&50&信誉度为优信誉度为优)不买保险不买保险基本决策树方法基本决策树方法v 基本算法基本算法 (贪婪算法贪婪算法)自顶向下的分治算

19、法构造树自顶向下的分治算法构造树 开始开始,所有的训练样本和树根相连所有的训练样本和树根相连 属性为分类属性属性为分类属性 (若是连续值，则离散化若是连续值，则离散化)根据选定的属性递归地划分样本根据选定的属性递归地划分样本?如何选择如何选择 基于启发式或统计度量选取测试属性基于启发式或统计度量选取测试属性(e.g.,(e.g.,信息增益信息增益)v 停止划分的准则停止划分的准则 所有样本均和属于同一类的节点连接所有样本均和属于同一类的节点连接 无剩下的属性用于继续划分样本无剩下的属性用于继续划分样本 叶节点分类应用叶节点分类应用多数表决法多数表决法 无剩余的样本无剩余的样本 其它的提前中止法

20、其它的提前中止法属性选择度量属性选择度量v 属性选择度量划分规则属性选择度量划分规则 划分属性：度量得分高的属性划分属性：度量得分高的属性v 流行的属性选择度量流行的属性选择度量 信息增益信息增益(ID3(ID3，C4.5)C4.5)选取时，偏向于多值属性选取时，偏向于多值属性 增益率增益率(C4.5)(C4.5)偏向不平衡划分偏向不平衡划分 GiniGini指标指标(CART,SLIQ,SPRINT)(CART,SLIQ,SPRINT)偏向于多值属性偏向于多值属性 类的数量很大时，计算较困难类的数量很大时，计算较困难信息增益信息增益(Information Gain)(Information

21、 Gain)v 基于信息论基于信息论“熵熵”，选取具有最大信息增益的属性划分，选取具有最大信息增益的属性划分v 在属性节点在属性节点A A处，样本集处，样本集D D所具有的熵所具有的熵 (p(j|D)为类为类 j j 在节点在节点 t t处的概率处的概率).).v 度量节点的均质性度量节点的均质性 当所有的类均匀分布时，最大为当所有的类均匀分布时，最大为 (log n(log nc c)，具有，具有 最多信息最多信息 当只有所有样本属于一类时，最小为当只有所有样本属于一类时，最小为 (0.0)(0.0)，具有最少信息，具有最少信息v 在属性在属性A A处，将样本分为处，将样本分为v v类的信息

22、量类的信息量v 通过在属性通过在属性A A，形成，形成v v个分支后，信息增益为个分支后，信息增益为,增益最大的选为划分增益最大的选为划分属性属性()()(|)log(|)jInfo DEntropy Dp j Dp j D 1()()viAiinInfoDInfo Dn()()()AGain AInfo DInfoD信息增益例子信息增益例子类类 P:buys_computer=“yes”P:buys_computer=“yes”类类 N:buys_computer=“no”N:buys_computer=“no”指 14个样本中有5个“age=30”,两个属于类p，2个属于类N ,因此Sim

23、ilarly,54()(2,3)(4,0)14145(3,2)0.69414ageInfoDIII048.0)_(151.0)(029.0)(ratingcreditGainstudentGainincomeGain246.0)()()(DInfoDInfoageGainageageincomestudentcredit_ratingbuys_computer=30highnofairno40mediumnofairyes40lowyesfairyes40lowyesexcellentno3140lowyesexcellentyes=30mediumnofairno40mediumyesfai

24、ryes40mediumnoexcellentno)3,2(145I229955()log()log()0.94014141414Info D ()()(|)log(|)jInfo DEntropy Dp j Dp j D 1()()viAiinInfoDInfo Dn决策树首层决策树首层age?4030.40增益率增益率(Gain Ratio)(Gain Ratio)v C4.5(ID3C4.5(ID3的后继算法的后继算法)应用增益率克服信息增益的偏斜性应用增益率克服信息增益的偏斜性 (信信息增益的规范化息增益的规范化)v Ex.Ex.GainRatio(income)=0.029/0.92

25、6=0.031GainRatio(income)=0.029/0.926=0.031v 具有最大增益率的属性选为划分属性具有最大增益率的属性选为划分属性21()log()vjjAjnnSplitInfoDnn 926.0)144(log144)146(log146)144(log144)(222DSplitInfoA()()()Gain AGainRatio ASplitInfo A信息增益缺点:倾向于选择分割数目多的属性。GiniGini指数指数v GiniGini指数指数:节点属性节点属性 A A划分样本的不纯度，设样本集为划分样本的不纯度，设样本集为D D(NOTE:(NOTE:p(j|

26、D)p(j|D)类类 j j 在样本在样本D D中的概率中的概率).).当所有样本均匀分布在不同类时，最大为当所有样本均匀分布在不同类时，最大为(1-1/nc),(1-1/nc),表示最小表示最小兴趣信息兴趣信息 当所有的样本属于一类时，最小当所有的样本属于一类时，最小 为为(0.0)(0.0)，表示最大兴趣信息，表示最大兴趣信息2()1(|)iGini Dp i D C10C26Gini=0.000C12C24Gini=0.444C13C23Gini=0.500C11C25Gini=0.278GiniGini例子例子C1 0 C2 6 C1 2 C2 4 C1 1 C2 5 P(C1)=0/

27、6=0 P(C2)=6/6=1P(C1)=0/6=0 P(C2)=6/6=1Gini=1 P(C1)Gini=1 P(C1)2 2 P(C2)P(C2)2 2=1 0 1=1 0 1=0 0 2()1(|)jGINI Dp j D P(C1)=1/6 P(C2)=5/6P(C1)=1/6 P(C2)=5/6Gini=1 (1/6)Gini=1 (1/6)2 2 (5/6)(5/6)2 2=0.278=0.278P(C1)=2/6 P(C2)=4/6P(C1)=2/6 P(C2)=4/6Gini=1 (2/6)Gini=1 (2/6)2 2 (4/6)(4/6)2 2=0.444=0.444C

28、13C 23G i n i=0.5 0 0基于基于GiniGini指数的划分指数的划分v 用于用于CARTCART算法算法v 在节点在节点A A，将训练集，将训练集D D划分为划分为k k个子集个子集(子节点子节点D Dii )，则以划，则以划分的不纯度加权和度量其优劣分的不纯度加权和度量其优劣 n nii=子树子树 的训练样本个数的训练样本个数i,i,n n =节点节点p p处训练样本个数处训练样本个数.1()()kiAiinGiniDGini Dn二值属性的二值属性的GiniGini指数指数v 划分为两个子集划分为两个子集v 带权划分的效果带权划分的效果:Gini:Gini指数越小越好指数

29、越小越好 寻求更大和更纯的划分寻求更大和更纯的划分B?YesNoNode N1Node N2Gini(D1)Gini(D1)=1 (5/7)=1 (5/7)2 2 (2/7)(2/7)2 2 =0.174=0.174 Gini(D2)Gini(D2)=1 (1/5)=1 (1/5)2 2 (4/5)(4/5)2 2 =0.32=0.32Gini(Children)Gini(Children)=7/12=7/12*0.174+0.174+5/12 5/12*0.32 0.32=0.204=0.204决策树归纳算法决策树归纳算法v 算法种类多算法种类多 Hunts Algorithm(one of

30、 Hunts Algorithm(one of the earliest)the earliest)CARTCART ID3,ID3,C4.5C4.5 SLIQ,SPRINTSLIQ,SPRINTID3ID3算法原理算法原理v 选择具有较高信息增益的描述属性作为给定数据集选择具有较高信息增益的描述属性作为给定数据集X X的分的分支属性，从而创建决策树中的一个节点支属性，从而创建决策树中的一个节点v 根据该描述属性的不同取值再创建分支根据该描述属性的不同取值再创建分支v 之后对各个分支中的样本子集递归调用上述方法建立下一之后对各个分支中的样本子集递归调用上述方法建立下一级子节点级子节点v 当某个

31、分支上的所有数据样本都属于同一个类别时划分停当某个分支上的所有数据样本都属于同一个类别时划分停止，形成叶节点止，形成叶节点v 或者当某个分支上的样本不属于同一个类别，但是又没有或者当某个分支上的样本不属于同一个类别，但是又没有剩余的描述属性可以进一步划分数据集时也形成叶节点，剩余的描述属性可以进一步划分数据集时也形成叶节点，并且用多数样本所属的类别来标记这个叶节点并且用多数样本所属的类别来标记这个叶节点ID3ID3算法示例算法示例该样本集中共该样本集中共包含包含4 4个描述个描述属性和属性和1 1个类别个类别属性，空间容量属性，空间容量为为1414目标是利用目标是利用ID3ID3思想构建一棵思

32、想构建一棵可用于新样本可用于新样本分类的决策树分类的决策树A1-A1-公司职员公司职员A2-A2-年龄年龄A3-A3-收入收入A4-A4-信誉度信誉度C-C-买保险买保险否=40高良c2否50中良c1是50低良c1是50低优c2是4150低优c1否=40中良c2是50中良c1是50中优c2第第1 1步：计算对训练集分类所需的期望信息步：计算对训练集分类所需的期望信息v 已知已知 total=14total=14 c1(c1(买保险买保险)的样本数量是的样本数量是n1=9n1=9 c2(c2(不买保险不买保险)的样本数量是的样本数量是n2=5n2=5v 所以所以 P(c1)=9/14P(c1)=

33、9/14 P(c2)=5/14P(c2)=5/14v 根据期望信息公式可得根据期望信息公式可得94.0)145(log145)149(log149()(log)(),(2221221jjjcPcPnnI第第2 2步：计算步：计算A1A1（公司职员）的熵（公司职员）的熵v A1A1包含两种取值：包含两种取值：“是是”和和“否否”v 利用利用A1A1可将可将X X划分为两个子集划分为两个子集X1X1和和X2X2 X1X1中的数据样本都是公司职员（中的数据样本都是公司职员（7 7个）个）标号为标号为c1c1的有的有6 6个，个，n11=6n11=6 标号为标号为c2c2的有的有1 1个，个，n21=

34、1n21=1 则可得则可得 p11=6/7p11=6/7 p21=1/7p21=1/7A1-A1-公司职员公司职员C-C-买保险买保险否c2否c2否c1否c1是c1是c2是c1否c2是c1是c1是c1否c1是c1否c2592.0)71(log71)76(log76()(log),(22211212111jjjppnnI第第2 2步：计算步：计算A1A1（公司职员）的熵（公司职员）的熵v 利用利用A1A1可将可将X X划分为两个子集划分为两个子集X1X1和和X2X2 X2X2中的数据样本都不是公司职员（中的数据样本都不是公司职员（7 7个）个）标号为标号为c1c1的有的有3 3个，个，n12=3

35、n12=3 标号为标号为c2c2的有的有4 4个，个，n22=4n22=4 则可得则可得 p12=3/7p12=3/7 p22=4/7p22=4/7A1-A1-公司职员公司职员C-C-买保险买保险否c2否c2否c1否c1是c1是c2是c1否c2是c1是c1是c1否c1是c1否c2985.0)74(log74)73(log73()(log),(22212222212jjjppnnI第第2 2步：计算步：计算A1A1（公司职员）的熵（公司职员）的熵v 则计算出则计算出A1A1划分训练集所得的熵为划分训练集所得的熵为789.0985.0147592.0147),()(2121211sssssnnIt

36、otalnnAE第第3 3步：计算步：计算A1A1（公司职员）的信息增益（公司职员）的信息增益151.0789.094.0)(),()(12111AEnnIAGainA益为：划分数据集时的信息增利用描述属性第第4 4步：求出其他描述属性的信息增益步：求出其他描述属性的信息增益v Gain(A2)=0.246Gain(A2)=0.246v Gain(A3)=0.029Gain(A3)=0.029v Gain(A4)=0.048Gain(A4)=0.048v 经比较可知经比较可知Gain(A2)Gain(A2)最大，所以选择最大，所以选择A2A2（年龄）作为决（年龄）作为决策树的根节点策树的根节点

37、v 进一步将树划分为进一步将树划分为3 3个分支个分支第第5 5步：根据根节点划分数据集步：根据根节点划分数据集年龄年龄=405050的子集的子集在此子集内继续检查在此子集内继续检查Gain(A1)Gain(A1)、Gain(A3)Gain(A3)、Gain(A4)Gain(A4)选取信息增益最大的描述属性作为内部节点选取信息增益最大的描述属性作为内部节点A1-A1-公司职员公司职员A3-A3-收入收入A4-A4-信誉度信誉度C-C-买保险买保险否中良c1是低良c1是低优c2是中良c1否中优c2ID3ID3算法小结算法小结v 使用使用ID3ID3算法的基本思想是算法的基本思想是 采用自顶向下的

38、递归方式，将原始样本空间划分成若干更小的样采用自顶向下的递归方式，将原始样本空间划分成若干更小的样本空间本空间 再对他们单独进行处理再对他们单独进行处理 其中，选择哪一个描述属性作为新建节点，依据是考察该描述属其中，选择哪一个描述属性作为新建节点，依据是考察该描述属性的信息增益是否最大性的信息增益是否最大下载地址http:/ 使用信息增益作为属性选择依据使用信息增益作为属性选择依据 带有倾向性，倾向于选择取值较多的属性带有倾向性，倾向于选择取值较多的属性 为什么？为什么？一种可能的解释是：对于较难分类的集合，优先将样本分割到尽一种可能的解释是：对于较难分类的集合，优先将样本分割到尽可能多的分支

39、中将极大简化分类工作可能多的分支中将极大简化分类工作ID3ID3的不足（的不足（2/22/2）v 无法处理未知值的样本无法处理未知值的样本 对于个别样本缺失了某项描述属性的情况，无法处理对于个别样本缺失了某项描述属性的情况，无法处理v 无法处理连续值的样本无法处理连续值的样本 对于描述属性是连续值的情况，无法处理对于描述属性是连续值的情况，无法处理变化一：使用信息增益比变化一：使用信息增益比qsssfffffjsjssssffsqfqfffftotalntotalnAsplitAsplitAGainAratioGainXAcXnXnaAXXXXqXAaaadfA122121)(log)()()

40、()(_,q),2,1(其中所得的信息增益比为：划分则描述属性的样本数量中属于类别表示子集中的样本数量表示子集设上具有相同取值中的样本在其中个子集划分为可以将利用个不同的取值具有设描述属性变化二：处理未知值的训练样本（变化二：处理未知值的训练样本（1/21/2）v 思想思想 将未知值用最常用的值来替代（较将未知值用最常用的值来替代（较容易）容易）或，依据现有取值的概率分布来估或，依据现有取值的概率分布来估计未知值（较真实）计未知值（较真实）v 显然：依据思想一，在已知样本显然：依据思想一，在已知样本中年龄的三个区间分布是中年龄的三个区间分布是=405050，5 5人人 则可以直接指定未知值为则

41、可以直接指定未知值为“5050”A2-A2-年龄年龄C-C-买保险买保险=40c250c150c150c24150c1=40c250c1？c14150c14150c150c2变化二：处理未知值的训练样本（变化二：处理未知值的训练样本（2/22/2）v 思想思想 将未知值用最常用的值来替代（较将未知值用最常用的值来替代（较容易）容易）或，依据现有取值的概率分布来估或，依据现有取值的概率分布来估计未知值（较真实）计未知值（较真实）v 显然：依据思想二，在已知样本显然：依据思想二，在已知样本中年龄的三个区间分布是中年龄的三个区间分布是=405050，5 5人人v 考虑未知值样本后，分布更新为考虑未知

42、值样本后，分布更新为=405050，5+5/135+5/13人人A2-A2-年龄年龄C-C-买保险买保险=40c250c150c150c24150c1=40c250c1？c14150c14150c150c2变化三：处理连续值的训练样本（变化三：处理连续值的训练样本（1/101/10）v 思想思想 将所有数据样本按照连续型描述属性将所有数据样本按照连续型描述属性AcAc的具体取值，由小到大进的具体取值，由小到大进行升序排列，得到的属性值取值序列行升序排列，得到的属性值取值序列AA1c1c,A,A2c2c,.,A,.,Atotalctotalc 在在AA1c1c,A,A2c2c,.,A,.,Ato

43、talctotalc 中生成中生成total-1total-1个分割点，第个分割点，第i i个分割点的取值个分割点的取值设置为设置为v vii=(A=(Aicic+A+A(i+1)c(i+1)c)/2)/2或者或者v vii=A=Aicic 该分割点将数据集划分为两个子集，即描述属性该分割点将数据集划分为两个子集，即描述属性A Ac c的取值在区间的取值在区间AA1c1c,v,vii 的数据样本和在区间的数据样本和在区间(v(vii,A,Atotalctotalc 的数据样本，显然划分共有的数据样本，显然划分共有total-1total-1种方式种方式 从从total-1total-1个分割点

44、中选择最佳分割点。对于每一个分割点划分数个分割点中选择最佳分割点。对于每一个分割点划分数据集的方式，计算其信息增益比，从中选择信息增益比最大的分据集的方式，计算其信息增益比，从中选择信息增益比最大的分割点来划分数据集割点来划分数据集变化三：处理连续值的训练样本（变化三：处理连续值的训练样本（2/102/10）v 示例示例 求利用求利用C4.5C4.5算法在连续值描述属性算法在连续值描述属性A A上的上的最佳分割点最佳分割点v 解：解：第第0 0步，将步，将A A的取值升序排列的取值升序排列65,70,70,70,75,78,80,80,80,85,90,90,95,9665,70,70,70,

45、75,78,80,80,80,85,90,90,95,96 第第1 1步，计算步，计算vi=65vi=65时的信息增益比时的信息增益比A AC C85c290c278c196c180c170c26565c1c195c270c180c170c190c175c180c294.0)145(log145)149(log149()(log)(),(2221221jjjcPcPnnI变化三：处理连续值的训练样本（变化三：处理连续值的训练样本（3/103/10）v 解：解：第第1 1步，计算步，计算vi=65vi=65时的信息增益比时的信息增益比A AC C85c290c278c196c180c170c26

46、565c1c195c270c180c170c190c175c180c20)10(log10)11(log11()(log),(22211212111jjjppnnI961.0)135(log135)138(log138()(log),(22212222212jjjppnnI892.0961.014130141),()(2121211sssssnnItotalnnAE变化三：处理连续值的训练样本（变化三：处理连续值的训练样本（4/104/10）v 解：解：第第1 1步，计算步，计算vi=65vi=65时的信息增益比时的信息增益比A AC C85c290c278c196c180c170c26565

47、c1c195c270c180c170c190c175c180c2371.01413log1413141log141)(log)(222121ssstotalntotalnAsplit129.0371.0892.094.0)()()(_1111AsplitAGainAratioGainX所得的信息增益比为：划分在分割点变化三：处理连续值的训练样本（变化三：处理连续值的训练样本（5/105/10）v 解：解：第第2 2步，计算步，计算vi=70vi=70时的信息增益比时的信息增益比A AC C85c290c278c196c180c17070c2c26565c1c195c27070c1c180c17

48、070c1c190c175c180c294.0)145(log145)149(log149()(log)(),(2221221jjjcPcPnnI变化三：处理连续值的训练样本（变化三：处理连续值的训练样本（6/106/10）v 解：解：第第2 2步，计算步，计算vi=70vi=70时的信息增益比时的信息增益比A AC C85c290c278c196c180c17070c2c26565c1c195c27070c1c180c17070c1c190c175c180c2811.0)41(log41)43(log43()(log),(22211212111jjjppnnI971.0)104(log104

49、)106(log106()(log),(22212222212jjjppnnI926.0971.01410811.0144),()(2121211sssssnnItotalnnAE变化三：处理连续值的训练样本（变化三：处理连续值的训练样本（7/107/10）v 解：解：第第2 2步，计算步，计算vi=70vi=70时的信息增益比时的信息增益比A AC C85c290c278c196c180c17070c2c26565c1c195c27070c1c180c17070c1c190c175c180c2863.01410log1410144log144)(log)(222121ssstotalntot

50、alnAsplit016.0863.0926.094.0)()()(_1111AsplitAGainAratioGainX所得的信息增益比为：划分在分割点变化三：处理连续值的训练样本（变化三：处理连续值的训练样本（8/108/10）v 解：解：第第3 3步，计算步，计算vi=75vi=75时的信息增益比时的信息增益比A AC C85c290c278c196c180c17070c2c26565c1c195c27070c1c180c17070c1c190c17575c1c180c294.0)145(log145)149(log149()(log)(),(2221221jjjcPcPnnI变化三：处

51、理连续值的训练样本（变化三：处理连续值的训练样本（9/109/10）v 解：解：第第3 3步，计算步，计算vi=75vi=75时的信息增益比时的信息增益比A AC C85c290c278c196c180c17070c2c26565c1c195c27070c1c180c17070c1c190c17575c1c180c2722.0)51(log51)54(log54()(log),(22211212111jjjppnnI991.0)94(log94)95(log95()(log),(22212222212jjjppnnI895.0991.0149722.0145),()(2121211sssssn

52、nItotalnnAE变化三：处理连续值的训练样本（变化三：处理连续值的训练样本（10/1010/10）v 解：解：第第3 3步，计算步，计算vi=75vi=75时的信息增益比时的信息增益比A AC C85c290c278c196c180c17070c2c26565c1c195c27070c1c180c17070c1c190c17575c1c180c2941.0149log149145log145)(log)(222121ssstotalntotalnAsplit048.0941.0895.094.0)()()(_1111AsplitAGainAratioGainX所得的信息增益比为：划分在分

53、割点过拟合现象（过拟合现象（OverfittingOverfitting）噪声引起分类面扭曲噪声引起分类面扭曲数据缺失，使得决策树使用其它数据缺失，使得决策树使用其它分类任务的预测值进行分类分类任务的预测值进行分类v 分支太多，由噪声或孤立点产生异常分支太多，由噪声或孤立点产生异常v 分类未见数据时精度低分类未见数据时精度低剪枝方法处理过拟合剪枝方法处理过拟合v 前剪枝前剪枝 (Early Stopping Rule)(Early Stopping Rule)在生成完全树之前中止在生成完全树之前中止 典型的中止条件典型的中止条件:所有的样本属于同一类所有的样本属于同一类 所有的属性值相同所有的

54、属性值相同 更严格的条件更严格的条件:当树的深度达到用户给定阈值时当树的深度达到用户给定阈值时 样本数少于用户指定的数量样本数少于用户指定的数量 样本的类分布独立于已知特征样本的类分布独立于已知特征(e.g.,using (e.g.,using 2 2 test)test)如果继续划分当前节点并不会改善不纯度如果继续划分当前节点并不会改善不纯度(e.g.,Gini or (e.g.,Gini or information gain).information gain).剪枝方法处理过拟合剪枝方法处理过拟合v 后剪枝后剪枝 在生成完全树之后处理在生成完全树之后处理 以自底向上的方式修剪节点以自底向上的方式修剪节点 如果修建后改善了泛化误差，则以叶节点代替子树如果修建后改善了泛化误差，则以叶节点代替子树 叶节点的类标号以子树中大多数样本的标号代替叶节点的类标号以子树中大多数样本的标号代替 可以使用可以使用 MDL MDL 实现后剪枝实现后剪枝