数据分类-决策树(PPT-71页)

数据分类-决策树2目录基本概念决策树ID3算法决策树C4.5算法3学习目标1.掌握数据分类的基本原理和评价指标2.了解两种决策树算法4PartI数据分类的基本概念5定义数据分类是指把数据样本映射到一个事先定义的类中的学习过程即给定一组输入的属性向量及其对应的类，用基于归纳的学习算法得出分类分类问题是数据挖掘领域中研究和应用最为广泛的技术之一，如何更精确、更有效地分类一直是人们追求的目标数据分类的任务通过学习得到一个目标函数f，把每个属性集x映射到一个预先定义的类标号y6分类的示例两类分类示例银行业：区分高端信用卡和低端信用卡医疗诊断：区分正常细胞和癌细胞互联网：区分正常邮件和垃圾邮件多类分类示例油气传输：区分行人走过、汽车碾过、镐刨、电钻等行为文字识别：区分不同的字符（其中汉字识别是一个大类别问题）社会网络：区分中心用户、活跃用户、不活跃用户、马甲用户等7示例数据集数据集包含多个描述属性和一个类别属性一般来说描述属性：连续值或离散值类别属性：只能是离散值（目标属性连续对应回归问题）AgeSalaryClass30highc125highc221lowc243highc118lowc233lowc1..................8分类问题的形式化描述},,,{m,,,d,,,),,,(d),,2,1(},,,2,1|),{(21212121miiididiiidiiiiiicccyxyAAAxxxxxxxtotalixtotaliyxX个类别，则假设给定数据集包含的类标号表示数据样本的具体取值个描述属性分别对应表示维特征向量用其中数据样本数据集9分类的过程获取数据预处理分类决策分类器设计10获取数据数值型数据病例中的各种化验数据空气质量监测数据描述性数据人事部门档案资料图片型数据指纹、掌纹自然场景图片很多情况下，需要将上述数据统一转换为数值型数据序列，即形成特征向量（特征提取）11预处理为了提高分类的准确性和有效性，需要对分类所用的数据进行预处理去除噪声数据对空缺值进行处理数据降维（特征选择）--（PCA、LDA）主成分分析（PrincipalComponentAnalysis，PCA）线性鉴别分析(LinearDiscriminantAnalysis,LDA)，有时也称Fisher线性判别(FisherLinearDiscriminant,FLD)，这种算法是RonaldFisher于1936年发明的，是模式识别的经典算法。12分类器设计1-划分数据集给定带有类标号的数据集，并且将数据集划分为两个部分训练集（trainingset）测试集（testingset）划分策略1.当数据集D的规模较大时训练集2|D|/3，测试集是1|D|/32.当数据集D的规模不大时n交叉验证法（n-foldvalidation）•将数据集随机地划分为n组•之后执行n次循环，在第i次循环中，将第i组数据样本作为测试集，其余的n-1组数据样本作为训练集,最终的精度为n个精度的平均值。3.当数据集D的规模非常小时每次交叉验证时，只选择一条测试数据，剩余的数据均作为训练集。原始数据集有m条数据时，相当于m-次交叉验证。是N-次交叉验证的一个特例。14分类器设计2-分类器构造利用训练集构造分类器（分类模型）通过分析由属性描述的每类样本的数据信息，从中总结出分类的规律性，建立判别公式或判别规则在分类器构造过程中，由于提供了每个训练样本的类标号，这一步也称作监督学习（supervisedlearning）15分类器设计3-分类器测试利用测试集对分类器的分类性能进行评估，具体方式是首先，利用分类器对测试集中的每一个样本进行分类其次，将分类得到的类标号和测试集中数据样本的原始类标号进行对比由上述过程得到分类器的分类性能（如何评价？）16分类决策在构造成功分类器之后（通过测试），则可以利用该分类器实际执行分类17分类的评价准则-约定和假设jjjmiiiiiitestFPFNTPjcccyxyxNiyxX该类的样本数量是其他类别被错误分类为是被错误分类的样本数量是被正确分类的样本数量个类别，设定：对于测试集的第个类别，则假设分类问题含有的类标号；表示数据样本本；表示测试集中的数据样数；表示测试集中的样本个其中给定测试集},,,{mN},,,2,1|),{(2118分类的评价准则-指标1精确度（accuracy）是最常用的评价准则代表测试集中被正确分类的数据样本所占的比例反映了分类器对于数据集的整体分类性能NTPAccuracymjj119分类的评价准则-指标2查全率（recall）第j个类别的查全率（召回率）表示在本类样本中，被正确分类的样本占的比例代表该类别的分类精度jjjjFNTPTPRecalljjjFPFNTP该类的样本数量是其他类别被错误分类为是被错误分类的样本数量是被正确分类的样本数量20分类的评价准则-指标3查准率（precision）第j个类别的查准率表示被分类为该类的样本中，真正属于该类的样本所占的比例代表该类别的分类纯度jjjjFPTPTPPrecisionjjjFPFNTP该类的样本数量是其他类别被错误分类为是被错误分类的样本数量是被正确分类的样本数量21分类的评价准则-指标4F-measure可以比较合理地评价分类器对每一类样本的分类性能它是查全率和查准率的组合表达式其中参数β是可以调节的，通常取值为1jjjjjPrecisionRecallPrecisionRecallmeasureF22)1(22分类的评价准则-指标5几何均值（G-mean）它能合理地评价数据集的整体分类性能是各个类别查全率的平方根，当各个类别的查全率都大时才增大同时兼顾了各个类别的分类精度mjjRecallmeanG123延伸阅读Jin-MaoWei,Xiao-JieYuan,etal.Anovelmeasureforevaluatingclassifiers,ExpertSystemswithApplications,37(2010):3799-380924关于数据分类的小结所谓分类即是使用某种分类模型，以对象的若干维描述属性为输入，经过计算输出该对象所属类别的过程数据分类的两个关键步骤是分类器训练：选定合适的分类模型及参数分类器测试：利用合适的指标检验分类器有效性目前已有一些成熟的分类器可供使用决策树支持向量机最近邻/k-近邻25PartII决策树算法26决策树是一种以给定的数据样本为基础的归纳学习方法在给定已知类标号的数据集的情况下，采用自顶向下的递归方式来产生一个类似于流程图的树结构树的最顶层节点是根节点最底层节点是叶节点：代表样本的类别根节点和叶节点之间的节点是内部节点决策树方法在根节点和内部节点上根据给定的度量标准来选择最适合的描述属性作为分支属性并根据该属性的不同取值向下建立分支27决策树示例-购买保险A1-公司职员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中优c228保险决策树解决了哪类人更倾向于购买保险的问题年龄信誉度公司职员c1c1c2c1c2=4041~5050是否良优29决策树向程序语言的转化if(年龄=40&&是公司职员)买保险if(年龄=40&&不是公司职员)不买保险if(年龄介于41~50之间)买保险if(年龄50&&信誉度为良)买保险if(年龄50&&信誉度为优)不买保险30基本决策树方法基本算法(贪婪算法)自顶向下的分治算法构造树开始,所有的训练样本和树根相连属性为分类属性(若是连续值，则离散化)根据选定的属性递归地划分样本?如何选择•基于启发式或统计度量选取测试属性(e.g.,信息增益)停止划分的准则所有样本均和属于同一类的节点连接无剩下的属性用于继续划分样本–叶节点分类应用多数表决法无剩余的样本其它的提前中止法属性选择度量属性选择度量－划分规则划分属性：度量得分高的属性流行的属性选择度量信息增益(ID3，C4.5)•选取时，偏向于多值属性增益率(C4.5)•偏向不平衡划分Gini指标(CART,SLIQ,SPRINT)•偏向于多值属性•类的数量很大时，计算较困难信息增益(InformationGain)基于信息论“熵”，选取具有最大信息增益的属性划分在属性节点A处，样本集D所具有的熵(p(j|D)为类j在节点t处的概率).度量节点的均质性当所有的类均匀分布时，最大为(lognc)，具有最多信息当只有所有样本属于一类时，最小为(0.0)，具有最少信息在属性A处，将样本分为v类的信息量通过在属性A，形成v个分支后，信息增益为,增益最大的选为划分属性()()(|)log(|)jInfoDEntropyDpjDpjD1()()viAiinInfoDInfoDn()()()AGainAInfoDInfoD信息增益例子类P:buys_computer=“yes”类N:buys_computer=“no”指14个样本中有5个“age=30”,两个属于类p，2个属于类N,因此Similarly,agepiniI(pi,ni)=30230.97131…4040040320.97154()(2,3)(4,0)14145(3,2)0.69414ageInfoDIII048.0)_(151.0)(029.0)(ratingcreditGainstudentGainincomeGain246.0)()()(DInfoDInfoageGainageageincomestudentcredit_ratingbuys_computer=30highnofairno=30highnoexcellentno31…40highnofairyes40mediumnofairyes40lowyesfairyes40lowyesexcellentno31…40lowyesexcellentyes=30mediumnofairno=30lowyesfairyes40mediumyesfairyes=30mediumyesexcellentyes31…40mediumnoexcellentyes31…40highyesfairyes40mediumnoexcellentno)3,2(145I229955()log()log()0.94014141414InfoD()()(|)log(|)jInfoDEntropyDpjDpjD1()()viAiinInfoDInfoDn决策树－首层ageincomestudentcredit_ratingbuys_computer=30highnofairno=30highnoexcellentno=30mediumnofairno=30lowyesfairyes=30mediumyesexcellentyesageincomestudentcredit_ratingbuys_computer31…40lowyesexcellentyes31…40highnofairyes31…40mediumnoexcellentyes31…40highyesfairyesage?=304030..40ageincomestudentcredit_ratingbuys_computer40mediumnofairyes40lowyesfairyes40mediumyesfairyes40lowy