数据分类决策树课件

第4讲数据分类-决策树第4讲数据分类-决策树目录基本概念决策树ID3算法决策树C4.5算法2目录基本概念2本周学习目标1.掌握数据分类的基本原理和评价指标2.了解两种决策树算法3本周学习目标1.掌握数据分类的基本原理和评价指标34PartI数据分类的基本概念4PartI定义数据分类是指把数据样本映射到一个事先定义的类中的学习过程即给定一组输入的属性向量及其对应的类，用基于归纳的学习算法得出分类分类问题是数据挖掘领域中研究和应用最为广泛的技术之一，如何更精确、更有效地分类一直是人们追求的目标数据分类的任务通过学习得到一个目标函数f，把每个属性集x映射到一个预先定义的类标号y5定义数据分类5分类的示例两类分类示例银行业：区分高端信用卡和低端信用卡医疗诊断：区分正常细胞和癌细胞互联网：区分正常邮件和垃圾邮件多类分类示例油气传输：区分行人走过、汽车碾过、镐刨、电钻等行为文字识别：区分不同的字符（其中汉字识别是一个大类别问题）社会网络：区分中心用户、活跃用户、不活跃用户、马甲用户等6分类的示例两类分类示例6示例数据集数据集包含多个描述属性和一个类别属性一般来说描述属性：连续值或离散值类别属性：只能是离散值（目标属性连续对应回归问题）7AgeSalaryClass30highc125highc221lowc243highc118lowc233lowc1..................示例数据集数据集包含多个描述属性和一个类别属性7AgeSal分类问题的形式化描述8分类问题的形式化描述8分类的过程9获取数据预处理分类决策分类器设计分类的过程9获取数据预处理分类决策分类器设计获取数据数值型数据病例中的各种化验数据空气质量监测数据描述性数据人事部门档案资料图片型数据指纹、掌纹自然场景图片很多情况下，需要将上述数据统一转换为数值型数据序列，即形成特征向量（特征提取）10获取数据数值型数据10预处理为了提高分类的准确性和有效性，需要对分类所用的数据进行预处理去除噪声数据对空缺值进行处理数据降维（特征选择）--（PCA、LDA）11预处理为了提高分类的准确性和有效性，需要对分类所用的数据进行分类器设计1-划分数据集给定带有类标号的数据集，并且将数据集划分为两个部分训练集（trainingset）测试集（testingset）划分策略随机抽取法2/1<训练集/测试集<8/1十交叉验证法（10-foldvalidation）将数据集随机地划分为10组之后执行10次循环，在第i次循环中，将第i组数据样本作为测试集，其余的9组数据样本作为训练集12分类器设计1-划分数据集给定带有类标号的数据集，并且将数据集分类器设计2-分类器构造利用训练集构造分类器（分类模型）通过分析由属性描述的每类样本的数据信息，从中总结出分类的规律性，建立判别公式或判别规则在分类器构造过程中，由于提供了每个训练样本的类标号，这一步也称作监督学习（supervisedlearning）13分类器设计2-分类器构造利用训练集构造分类器（分类模型）13分类器设计3-分类器测试利用测试集对分类器的分类性能进行评估，具体方式是首先，利用分类器对测试集中的每一个样本进行分类其次，将分类得到的类标号和测试集中数据样本的原始类标号进行对比由上述过程得到分类器的分类性能（如何评价？）14分类器设计3-分类器测试利用测试集对分类器的分类性能进行评估分类决策在构造成功分类器之后（通过测试），则可以利用该分类器实际执行分类15分类决策在构造成功分类器之后（通过测试），则可以利用该分类器分类的评价准则-约定和假设16分类的评价准则-约定和假设16分类的评价准则-指标1精确度（accuracy）是最常用的评价准则代表测试集中被正确分类的数据样本所占的比例反映了分类器对于数据集的整体分类性能17分类的评价准则-指标1精确度（accuracy）17分类的评价准则-指标2查全率（recall）第j个类别的查全率（召回率）表示在本类样本中，被正确分类的样本占的比例代表该类别的分类精度18分类的评价准则-指标2查全率（recall）18分类的评价准则-指标3查准率（precision）第j个类别的查准率表示被分类为该类的样本中，真正属于该类的样本所占的比例代表该类别的分类纯度19分类的评价准则-指标3查准率（precision）19分类的评价准则-指标4F-measure可以比较合理地评价分类器对每一类样本的分类性能它是查全率和查准率的组合表达式其中参数β是可以调节的，通常取值为120分类的评价准则-指标4F-measure20分类的评价准则-指标5几何均值（G-mean）它能合理地评价数据集的整体分类性能是各个类别查全率的平方根，当各个类别的查全率都大时才增大同时兼顾了各个类别的分类精度21分类的评价准则-指标5几何均值（G-mean）21延伸阅读Jin-MaoWei,Xiao-JieYuan,etal.Anovelmeasureforevaluatingclassifiers,ExpertSystemswithApplications,37(2010):3799-380922延伸阅读Jin-MaoWei,Xiao-JieYuan关于数据分类的小结所谓分类即是使用某种分类模型，以对象的若干维描述属性为输入，经过计算输出该对象所属类别的过程数据分类的两个关键步骤是分类器训练：选定合适的分类模型及参数分类器测试：利用合适的指标检验分类器有效性目前已有一些成熟的分类器可供使用决策树支持向量机最近邻/k-近邻23关于数据分类的小结所谓分类即是使用某种分类模型，以对象的若干24PartII决策树ID3算法24PartII决策树是一种以给定的数据样本为基础的归纳学习方法在给定已知类标号的数据集的情况下，采用自顶向下的递归方式来产生一个类似于流程图的树结构树的最顶层节点是根节点最底层节点是叶节点：代表样本的类别根节点和叶节点之间的节点是内部节点决策树方法在根节点和内部节点上根据给定的度量标准来选择最适合的描述属性作为分支属性并根据该属性的不同取值向下建立分支25决策树是一种以给定的数据样本为基础的归纳学习方法25决策树示例-购买保险26A1-公司职员A2-年龄A3-收入A4-信誉度C-买保险否<=40高良c2否<=40高优c2否41~50高良c1否>50中良c1是>50低良c1是>50低优c2是41~50低优c1否<=40中良c2是<=40低良c1是>50中良c1是<=40中优c1否41~50中优c1是41~50高良c1否>50中优c2决策树示例-购买保险26A1-公司职员A2-年龄A3-收入A保险决策树解决了哪类人更倾向于购买保险的问题27年龄信誉度公司职员c1c1c2c1c2<=4041~50>50是否良优保险决策树解决了哪类人更倾向于购买保险的问题27年龄信誉度公决策树向程序语言的转化if(年龄<=40&&是公司职员)

买保险if(年龄<=40&&不是公司职员)

不买保险if(年龄介于41~50之间)

买保险if(年龄>50&&信誉度为良)

买保险if(年龄>50&&信誉度为优)

不买保险28决策树向程序语言的转化if(年龄<=40&&是公司职员ID3算法的原理核心思想在选择根节点和各个内部节点上的分支属性时，采用信息增益（informationgain）作为度量标准特别说明创建根节点时，X是最初给定的所有数据创建内部节点时，X是上层节点的某个分支对应的数据集29ID3算法的原理核心思想29ID3算法的原理期望信息30什么情况下信息量更大？分布更平均？vs

分布更极端？分布更集中？VS分布更疏散？ID3算法的原理期望信息30什么情况下信息量更大？ID3算法的原理熵熵值E(Af)越小，表示属性Af对数据集划分的纯度越高31ID3算法的原理熵31ID3算法的原理信息增益32ID3算法的原理信息增益32ID3算法原理选择具有较高信息增益的描述属性作为给定数据集X的分支属性，从而创建决策树中的一个节点根据该描述属性的不同取值再创建分支之后对各个分支中的样本子集递归调用上述方法建立下一级子节点当某个分支上的所有数据样本都属于同一个类别时划分停止，形成叶节点或者当某个分支上的样本不属于同一个类别，但是又没有剩余的描述属性可以进一步划分数据集时也形成叶节点，并且用多数样本所属的类别来标记这个叶节点33ID3算法原理选择具有较高信息增益的描述属性作为给定数据集XID3算法示例该样本集中共包含4个描述属性和1个类别属性，空间容量为14目标是利用ID3思想构建一棵可用于新样本分类的决策树34A1-公司职员A2-年龄A3-收入A4-信誉度C-买保险否<=40高良c2否<=40高优c2否41~50高良c1否>50中良c1是>50低良c1是>50低优c2是41~50低优c1否<=40中良c2是<=40低良c1是>50中良c1是<=40中优c1否41~50中优c1是41~50高良c1否>50中优c2ID3算法示例该样本集中共34A1-公司职员A2-年龄A3-第1步：计算对训练集分类所需的期望信息已知total=14c1(买保险)的样本数量是n1=9c2(不买保险)的样本数量是n2=5所以P(c1)=9/14P(c2)=5/14根据期望信息公式可得35第1步：计算对训练集分类所需的期望信息已知35第2步：计算A1（公司职员）的熵A1包含两种取值：“是”和“否”利用A1可将X划分为两个子集X1和X2X1中的数据样本都是公司职员（7个）标号为c1的有6个，n11=6标号为c2的有1个，n21=1则可得p11=6/7p21=1/736A1-公司职员C-买保险否c2否c2否c1否c1是c1是c2是c1否c2是c1是c1是c1否c1是c1否c2第2步：计算A1（公司职员）的熵A1包含两种取值：“是”和“第2步：计算A1（公司职员）的熵利用A1可将X划分为两个子集X1和X2X2中的数据样本都不是公司职员（7个）标号为c1的有3个，n12=3标号为c2的有4个，n22=4则可得p12=3/7p22=4/737A1-公司职员C-买保险否c2否c2否c1否c1是c1是c2是c1否c2是c1是c1是c1否c1是c1否c2第2步：计算A1（公司职员）的熵利用A1可将X划分为两个子集第2步：计算A1（公司职员）的熵则计算出A1划分训练集所得的熵为38第2步：计算A1（公司职员）的熵则计算出A1划分训练集所得的第3步：计算A1（公司职员）的信息增益39第3步：计算A1（公司职员）的信息增益39第4步：求出其他描述属性的信息增益Gain(A2)=0.246Gain(A3)=0.029Gain(A4)=0.048经比较可知Gain(A2)最大，所以选择A2（年龄）作为决策树的根节点进一步将树划分为3个分支40第4步：求出其他描述属性的信息增益Gain(A2)=0.24第5步：根据根节点划分数据集年龄<=40的子集在此子集内继续检查Gain(A1)、Gain(A3)、Gain(A4)选取信息增益最大的描述属性作为内部节点41A1-公司职员A3-收入A4-信誉度C-买保险否高良c2否高优c2否中良c2是低良c1是中优c1第5步：根据根节点划分数据集年龄<=40的子集41A1-公司第5步：根据根节点划分数据集年龄41~50的子集该子集中所有样本的类别标号都一样，所以无需继续划分可将它标注为一个叶节点，而且叶节点的类标号为c142A1-公司职员A3-收入A4-信誉度C-买保险否高良c1是低优c1否中优c1是高良c1第5步：根据根节点划分数据集年龄41~50的子集42A1-公第5步：根据根节点划分数据集年龄>50的子集在此子集内继续检查Gain(A1)、Gain(A3)、Gain(A4)选取信息增益最大的描述属性作为内部节点43A1-公司职员A3-收入A4-信誉度C-买保险否中良c1是低良c1是低优c2是中良c1否中优c2第5步：根据根节点划分数据集年龄>50的子集43A1-公司职ID3算法小结使用ID3算法的基本思想是采用自顶向下的递归方式，将原始样本空间划分成若干更小的样本空间再对他们单独进行处理其中，选择哪一个描述属性作为新建节点，依据是考察该描述属性的信息增益是否最大44ID3算法小结使用ID3算法的基本思想是4445PartIIIC4.5算法45PartIIIID3的不足（1/2）使用信息增益作为属性选择依据带有倾向性，倾向于选择取值较多的属性为什么？一种可能的解释是：对于较难分类的集合，优先将样本分割到尽可能多的分支中将极大简化分类工作46ID3的不足（1/2）使用信息增益作为属性选择依据46ID3的不足（2/2）无法处理未知值的样本对于个别样本缺失了某项描述属性的情况，无法处理无法处理连续值的样本对于描述属性是连续值的情况，无法处理47ID3的不足（2/2）无法处理未知值的样本47变化一：使用信息增益比48变化一：使用信息增益比48变化二：处理未知值的训练样本（1/2）思想将未知值用最常用的值来替代（较容易）或，依据现有取值的概率分布来估计未知值（较真实）显然：依据思想一，在已知样本中年龄的三个区间分布是<=40，4人41~50，4人>50，5人则可以直接指定未知值为“>50”49A2-年龄C-买保险<=40c2<=40c241~50c1>50c1>50c1>50c241~50c1<=40c2<=40c1>50c1？c141~50c141~50c1>50c2变化二：处理未知值的训练样本（1/2）思想49A2-年龄C-变化二：处理未知值的训练样本（2/2）思想将未知值用最常用的值来替代（较容易）或，依据现有取值的概率分布来估计未知值（较真实）显然：依据思想二，在已知样本中年龄的三个区间分布是<=40，4人41~50，4人>50，5人考虑未知值样本后，分布更新为<=40，4+4/13人41~50，4+4/13人>50，5+5/13人50A2-年龄C-买保险<=40c2<=40c241~50c1>50c1>50c1>50c241~50c1<=40c2<=40c1>50c1？c141~50c141~50c1>50c2变化二：处理未知值的训练样本（2/2）思想50A2-年龄C-变化三：处理连续值的训练样本（1/10）思想将所有数据样本按照连续型描述属性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个分割点中选择最佳分割点。对于每一个分割点划分数据集的方式，计算其信息增益比，从中选择信息增益比最大的分割点来划分数据集51变化三：处理连续值的训练样本（1/10）思想51变化三：处理连续值的训练样本（2/10）示例求利用C4.5算法在连续值描述属性A上的最佳分割点解：第0步，将A的取值升序排列{65,70,70,70,75,78,80,80,80,85,90,90,95,96}第1步，计算vi=65时的信息增益比52AC85c290c278c196c180c170c265c195c270c180c170c190c175c180c2变化三：处理连续值的训练样本（2/10）示例52AC85c2变化三：处理连续值的训练样本（3/10）解：第1步，计算vi=65时的信息增益比53AC85c290c278c196c180c170c265c195c270c180c170c190c175c180c2变化三：处理连续值的训练样本（3/10）解：53AC85c2变化三：处理连续值的训练样本（4/10）解：第1步，计算vi=65时的信息增益比54AC85c290c278c196c180c170c265c195c270c180c170c190c175c180c2变化三：处理连续值的训练样本（4/10）解：54AC85c2变化三：处理连续值的训练样本（5/10）解：第2步，计算vi=70时的信息增益比55AC85c290c278c196c180c170c265c195c270c180c170c190c175c180c2变化三：处理连续值的训练样本（5/10）解：55AC85c2变化三：处理连续值的训练样本（6/10）解：第2步，计算vi=70时的信息增益比56AC85c290c278c196c180c170c265c195c270c180c170c190c175c180c2变化三：处理连续值的训练样本（6/10）解：56AC85c2变化三：处理连续值的训练样本（7/10）解：第2步，计算vi=70时的信息增益比57AC85c290c278c196c180c170c265c195c270c180c170c190c175c180c2变化三：处理连续值的训练样本（7/10）解：57AC85c2变化三：处理连续值的训练样本（8/10）解：第3步，计算vi=75时的信息增益比58AC85c290c278c196c180c170c265c195c270c180c170c190c175c180c2变化三：处理连续值的训练样本（8/10）解：58AC85c2变化三：处理连续值的训练样本（9/10）解：第3步，计算vi=75时的信息增益比59AC85c290c278c196c180c170c265c195c270c180c170c190c175c180c2变化三：处理连续值的训练样本（9/10）解：59AC85c2变化三：处理连续值的训练样本（10/10）解：第3步，计算vi=75时的信息增益比60AC85c290c278c196c180c170c265c195c270c180c170c190c175c180c2变化三：处理连续值的训练样本（10/10）解：60AC85c本章结束本章结束演讲完毕，谢谢观看！演讲完毕，谢谢观看！第4讲数据分类-决策树第4讲数据分类-决策树目录基本概念决策树ID3算法决策树C4.5算法64目录基本概念2本周学习目标1.掌握数据分类的基本原理和评价指标2.了解两种决策树算法65本周学习目标1.掌握数据分类的基本原理和评价指标366PartI数据分类的基本概念4PartI定义数据分类是指把数据样本映射到一个事先定义的类中的学习过程即给定一组输入的属性向量及其对应的类，用基于归纳的学习算法得出分类分类问题是数据挖掘领域中研究和应用最为广泛的技术之一，如何更精确、更有效地分类一直是人们追求的目标数据分类的任务通过学习得到一个目标函数f，把每个属性集x映射到一个预先定义的类标号y67定义数据分类5分类的示例两类分类示例银行业：区分高端信用卡和低端信用卡医疗诊断：区分正常细胞和癌细胞互联网：区分正常邮件和垃圾邮件多类分类示例油气传输：区分行人走过、汽车碾过、镐刨、电钻等行为文字识别：区分不同的字符（其中汉字识别是一个大类别问题）社会网络：区分中心用户、活跃用户、不活跃用户、马甲用户等68分类的示例两类分类示例6示例数据集数据集包含多个描述属性和一个类别属性一般来说描述属性：连续值或离散值类别属性：只能是离散值（目标属性连续对应回归问题）69AgeSalaryClass30highc125highc221lowc243highc118lowc233lowc1..................示例数据集数据集包含多个描述属性和一个类别属性7AgeSal分类问题的形式化描述70分类问题的形式化描述8分类的过程71获取数据预处理分类决策分类器设计分类的过程9获取数据预处理分类决策分类器设计获取数据数值型数据病例中的各种化验数据空气质量监测数据描述性数据人事部门档案资料图片型数据指纹、掌纹自然场景图片很多情况下，需要将上述数据统一转换为数值型数据序列，即形成特征向量（特征提取）72获取数据数值型数据10预处理为了提高分类的准确性和有效性，需要对分类所用的数据进行预处理去除噪声数据对空缺值进行处理数据降维（特征选择）--（PCA、LDA）73预处理为了提高分类的准确性和有效性，需要对分类所用的数据进行分类器设计1-划分数据集给定带有类标号的数据集，并且将数据集划分为两个部分训练集（trainingset）测试集（testingset）划分策略随机抽取法2/1<训练集/测试集<8/1十交叉验证法（10-foldvalidation）将数据集随机地划分为10组之后执行10次循环，在第i次循环中，将第i组数据样本作为测试集，其余的9组数据样本作为训练集74分类器设计1-划分数据集给定带有类标号的数据集，并且将数据集分类器设计2-分类器构造利用训练集构造分类器（分类模型）通过分析由属性描述的每类样本的数据信息，从中总结出分类的规律性，建立判别公式或判别规则在分类器构造过程中，由于提供了每个训练样本的类标号，这一步也称作监督学习（supervisedlearning）75分类器设计2-分类器构造利用训练集构造分类器（分类模型）13分类器设计3-分类器测试利用测试集对分类器的分类性能进行评估，具体方式是首先，利用分类器对测试集中的每一个样本进行分类其次，将分类得到的类标号和测试集中数据样本的原始类标号进行对比由上述过程得到分类器的分类性能（如何评价？）76分类器设计3-分类器测试利用测试集对分类器的分类性能进行评估分类决策在构造成功分类器之后（通过测试），则可以利用该分类器实际执行分类77分类决策在构造成功分类器之后（通过测试），则可以利用该分类器分类的评价准则-约定和假设78分类的评价准则-约定和假设16分类的评价准则-指标1精确度（accuracy）是最常用的评价准则代表测试集中被正确分类的数据样本所占的比例反映了分类器对于数据集的整体分类性能79分类的评价准则-指标1精确度（accuracy）17分类的评价准则-指标2查全率（recall）第j个类别的查全率（召回率）表示在本类样本中，被正确分类的样本占的比例代表该类别的分类精度80分类的评价准则-指标2查全率（recall）18分类的评价准则-指标3查准率（precision）第j个类别的查准率表示被分类为该类的样本中，真正属于该类的样本所占的比例代表该类别的分类纯度81分类的评价准则-指标3查准率（precision）19分类的评价准则-指标4F-measure可以比较合理地评价分类器对每一类样本的分类性能它是查全率和查准率的组合表达式其中参数β是可以调节的，通常取值为182分类的评价准则-指标4F-measure20分类的评价准则-指标5几何均值（G-mean）它能合理地评价数据集的整体分类性能是各个类别查全率的平方根，当各个类别的查全率都大时才增大同时兼顾了各个类别的分类精度83分类的评价准则-指标5几何均值（G-mean）21延伸阅读Jin-MaoWei,Xiao-JieYuan,etal.Anovelmeasureforevaluatingclassifiers,ExpertSystemswithApplications,37(2010):3799-380984延伸阅读Jin-MaoWei,Xiao-JieYuan关于数据分类的小结所谓分类即是使用某种分类模型，以对象的若干维描述属性为输入，经过计算输出该对象所属类别的过程数据分类的两个关键步骤是分类器训练：选定合适的分类模型及参数分类器测试：利用合适的指标检验分类器有效性目前已有一些成熟的分类器可供使用决策树支持向量机最近邻/k-近邻85关于数据分类的小结所谓分类即是使用某种分类模型，以对象的若干86PartII决策树ID3算法24PartII决策树是一种以给定的数据样本为基础的归纳学习方法在给定已知类标号的数据集的情况下，采用自顶向下的递归方式来产生一个类似于流程图的树结构树的最顶层节点是根节点最底层节点是叶节点：代表样本的类别根节点和叶节点之间的节点是内部节点决策树方法在根节点和内部节点上根据给定的度量标准来选择最适合的描述属性作为分支属性并根据该属性的不同取值向下建立分支87决策树是一种以给定的数据样本为基础的归纳学习方法25决策树示例-购买保险88A1-公司职员A2-年龄A3-收入A4-信誉度C-买保险否<=40高良c2否<=40高优c2否41~50高良c1否>50中良c1是>50低良c1是>50低优c2是41~50低优c1否<=40中良c2是<=40低良c1是>50中良c1是<=40中优c1否41~50中优c1是41~50高良c1否>50中优c2决策树示例-购买保险26A1-公司职员A2-年龄A3-收入A保险决策树解决了哪类人更倾向于购买保险的问题89年龄信誉度公司职员c1c1c2c1c2<=4041~50>50是否良优保险决策树解决了哪类人更倾向于购买保险的问题27年龄信誉度公决策树向程序语言的转化if(年龄<=40&&是公司职员)

买保险if(年龄<=40&&不是公司职员)

不买保险if(年龄介于41~50之间)

买保险if(年龄>50&&信誉度为良)

买保险if(年龄>50&&信誉度为优)

不买保险90决策树向程序语言的转化if(年龄<=40&&是公司职员ID3算法的原理核心思想在选择根节点和各个内部节点上的分支属性时，采用信息增益（informationgain）作为度量标准特别说明创建根节点时，X是最初给定的所有数据创建内部节点时，X是上层节点的某个分支对应的数据集91ID3算法的原理核心思想29ID3算法的原理期望信息92什么情况下信息量更大？分布更平均？vs

分布更极端？分布更集中？VS分布更疏散？ID3算法的原理期望信息30什么情况下信息量更大？ID3算法的原理熵熵值E(Af)越小，表示属性Af对数据集划分的纯度越高93ID3算法的原理熵31ID3算法的原理信息增益94ID3算法的原理信息增益32ID3算法原理选择具有较高信息增益的描述属性作为给定数据集X的分支属性，从而创建决策树中的一个节点根据该描述属性的不同取值再创建分支之后对各个分支中的样本子集递归调用上述方法建立下一级子节点当某个分支上的所有数据样本都属于同一个类别时划分停止，形成叶节点或者当某个分支上的样本不属于同一个类别，但是又没有剩余的描述属性可以进一步划分数据集时也形成叶节点，并且用多数样本所属的类别来标记这个叶节点95ID3算法原理选择具有较高信息增益的描述属性作为给定数据集XID3算法示例该样本集中共包含4个描述属性和1个类别属性，空间容量为14目标是利用ID3思想构建一棵可用于新样本分类的决策树96A1-公司职员A2-年龄A3-收入A4-信誉度C-买保险否<=40高良c2否<=40高优c2否41~50高良c1否>50中良c1是>50低良c1是>50低优c2是41~50低优c1否<=40中良c2是<=40低良c1是>50中良c1是<=40中优c1否41~50中优c1是41~50高良c1否>50中优c2ID3算法示例该样本集中共34A1-公司职员A2-年龄A3-第1步：计算对训练集分类所需的期望信息已知total=14c1(买保险)的样本数量是n1=9c2(不买保险)的样本数量是n2=5所以P(c1)=9/14P(c2)=5/14根据期望信息公式可得97第1步：计算对训练集分类所需的期望信息已知35第2步：计算A1（公司职员）的熵A1包含两种取值：“是”和“否”利用A1可将X划分为两个子集X1和X2X1中的数据样本都是公司职员（7个）标号为c1的有6个，n11=6标号为c2的有1个，n21=1则可得p11=6/7p21=1/798A1-公司职员C-买保险否c2否c2否c1否c1是c1是c2是c1否c2是c1是c1是c1否c1是c1否c2第2步：计算A1（公司职员）的熵A1包含两种取值：“是”和“第2步：计算A1（公司职员）的熵利用A1可将X划分为两个子集X1和X2X2中的数据样本都不是公司职员（7个）标号为c1的有3个，n12=3标号为c2的有4个，n22=4则可得p12=3/7p22=4/799A1-公司职员C-买保险否c2否c2否c1否c1是c1是c2是c1否c2是c1是c1是c1否c1是c1否c2第2步：计算A1（公司职员）的熵利用A1可将X划分为两个子集第2步：计算A1（公司职员）的熵则计算出A1划分训练集所得的熵为100第2步：计算A1（公司职员）的熵则计算出A1划分训练集所得的第3步：计算A1（公司职员）的信息增益101第3步：计算A1（公司职员）的信息增益39第4步：求出其他描述属性的信息增益Gain(A2)=0.246Gain(A3)=0.029Gain(A4)=0.048经比较可知Gain(A2)最大，所以选择A2（年龄）作为决策树的根节点进一步将树划分为3个分支102第4步：求出其他描述属性的信息增益Gain(A2)=0.24第5步：根据根节点划分数据集年龄<=40的子集在此子集内继续检查Gain(A1)、Gain(A3)、Gain(A4)选取信息增益最大的描述属性作为内部节点103A1-公司职员A3-收入A4-信誉度C-买保险否高良c2否高优c2否中良c2是低良c1是中优c1第5步：根据根节点划分数据集年龄<=40的子集41A1-公司第5步：根据根节点划分数据集年龄41~50的子集该子集中所有样本的类别标号都一样，所以无需继续划分可将它标注为一个叶节点，而且叶节点的类标号为c1104A1-公司职员A3-收入A4-信誉度C-买保险否高良c1是低优c1否中优c1是高良c1第5步：根据根节点划分数据集年龄41~50的子集42A1-公第5步：根据根节点划分数据集年龄>50的子集在此子集内继续检查Gain(A1)、Gain(A3)、Gain(A4)选取信息增益最大的描述属性作为内部节点105A1-公司职员A3-收入A4-信誉度C-买保险否中良c1是低良c1是低优c2是中良c1否中优c2第5步：根据根节点划分数据集年龄>50的子集43A1-公司职ID3算法小结使用ID3算法的基本思想是采用自顶向下的递归方式，将原始样本空间划分成若干更小的样本空间再对他们单独进行处理其中，选择哪一个描述属性作为新建节点，依据是考察该描述属性的信息增益是否最大106ID3算法小结使用ID3算法的基本思想是44107PartIIIC4.5算法45PartIIIID3的不足（1/2）使用信息增益作为属性选择依据带有倾向性，倾向于选择取值较多的属性为什么？一种可能的解释是：对于较难分类的集合，优先将样本分割到尽可能多的分支中将极大简化分类工作108ID3的不足（1/2）使用信息增益作为属性选择依据46ID3的不足（2/2）无法处理未知值的样本对于个别样本缺失了某项描述属性的情况，无法处理无法处理连续值的样本对于描述属性是连续值的情况，无法处理109ID3的不足（2/2）无法处理未知值的样本47变化一：使用信息增益比110变化一：使用信息增益比48变化二：处理未知值的训练样本（1/2）思想将未知值用最常用的值来替代（较容易）或，依据现有取值的概率分布来估计未知值（较真实）显然：依据思想一，在已知样本中年龄的三个区间分布是<=40，4人41~50，4人>50，5人则可以直接指定未知值为“>50”111A2-年龄C-买保险<=40c2<=40c241~50c1>50c1>50c1>50c241~50c1<=40c2<=40c1>50c1？c141~50c141~50c1>50c2变化二：处理未知值的训练样本（1/2）思想49A2-年龄C-变化二：处理未知值的训练样本（2/2）思想将未知值用最常用的值来替代（较容易）或，依据现有取值的概率分布来估计未知值（较真实）显然：依据思想二，在已知样本中年龄的三个区间分布是<=40，4人41~50，4人>50，5人考虑未知值样本后，分布更新为<=40，4+4/13人41~50，4+4/13人>50，5+5/13人112A2-年龄C-买保险<=40c2<=40c241~50c1>50c1>50c1>50c241~50c1<=40c2<=40c1>50c1？c141~50c141~50c1>50c2变化二：处理未知值的训练样本（2/2）思想50A2-年龄C-变化三：处理连续值的训练样本（1/10）思想将所有数据样本按照连续型描述属性Ac的具体取值，由小到大进行升序排列，得到的属性值取值序列{A1c,A2c,...,Atotalc}在{A1c,A2c,...,Atotalc}中生成total-1个分割点，第i个分割点的取值设置为vi=(Aic+A(i+1)c)/2或者vi=Aic该分割点将数据集划分为两个子集，即描述属性Ac的取值在区间[A1c,vi]的数据样本和在区间(vi,