数据挖掘-第8章--分类：基本概念

数据挖掘与商务智能范勤勤物流研究中心第八章分类1基本概念2决策树归纳3贝叶斯分类方法4基于规则的分类5模型评估与选择6提高分类准确率的技术1基本概念54分类VS.预测分类预测类标号（离散值）根据训练数据集和类标号属性，构建模型来分类现有数据，并用来分类新数据典型应用信誉证实（分类为低，中，高风险）医疗诊断（肿瘤是良性还是恶性）性能预测目标市场预测建立连续函数值模型，比如预测空缺值454一个两步过程第一步，建立一个分类模型，描述预定数据类或概念集假定每个元组属于一个预定义的类，由一个类标号属性确定基本概念训练数据集：由为建立模型而被分析的数据元组形成训练样本：训练数据集中的单个样本（元组）学习模型可以由分类规则、判定树或数学公式的形式提供第二步，使用模型，对将来的或未知的对象进行分类评估模型的预测准确率测试集：要独立于训练样本集，避免“过分拟合”的情况对每个测试样本，将已知的类标号和该样本的学习模型类预测比较准确率：被模型正确分类的测试样本的百分比如果准确率可以接受，那么使用该模型来分类标签为未知的样本5546第一步——建立模型训练数据集NAMERANKYEARSTENUREDMikeAssistantProf3noMaryAssistantProf7yesBillProfessor2yesJimAssociateProf7yesDaveAssistantProf6noAnneAssociateProf3no分类算法IFrank=‘professor’ORyears6THENtenured=‘yes’分类规则547第二步——用模型进行分类分类规则测试集NAMERANKYEARSTENUREDTomAssistantProf2noMerlisaAssociateProf7noGeorgeProfessor5yesJosephAssistantProf7yes未知数据(Jeff,Professor,4)Tenured?54有指导的学习VS.无指导的学习有指导的学习（用于分类）模型的学习在被告知每个训练样本属于哪个类的“指导”下进行新数据使用训练数据集中得到的规则进行分类无指导的学习（用于聚类）每个训练样本的类编号是未知的，要学习的类集合或数量也可能是事先未知的通过一系列的度量、观察来建立数据中的类编号或进行聚类82决策树归纳54用决策树归纳分类什么是决策树？类似于流程图的树结构每个内部节点（非树叶节点）表示在一个属性上的测试每个分枝代表该测试的一个输出每个树叶节点存放一个类标号10age?nostudent?credit_rating?noyesfairexcellentyouthseniornoyesyesyesMiddleaged决策树：Buys_computer54用决策树归纳分类使用决策树分类给定一个类标号未知的元组X，在决策树上测试元组的属性值，跟踪一条由根到叶节点的路径，叶节点存放该元组的类预测。决策树容易转换为分类规则决策树的生成由两个阶段组成决策树构建：自顶向下递归地分治方式使用属性选择度量来选择将元组最好的划分为不同的类的属性递归的通过选定的属性（必须是离散值）来划分样本树剪枝决策树建立时，许多分枝反映的是训练数据中的噪声或离群点，树剪枝试图识别并剪去这种分枝，以提高对未知数据分类的准确性1154决策树归纳策略输入数据分区D，训练元组和他们对应类标号的集合attribute_list,候选属性的集合Attribute_selection_method，指定选择属性的启发式过程算法步骤1.树以代表训练样本的单个节点（N）开始2.如果样本都在同一个类，则该节点成为树叶，并用该类标记3.否则，算法调用Attribute_selection_method，选择能够最好的将样本分类的属性；确定“分裂准则”，指出“分裂点”或“分裂子集”4.对测试属性每个已知的值，创建一个分支，并以此划分元组5.算法使用同样的过程，递归的形成每个划分上的元组决策树。一旦一个属性出现在一个节点上，就不在该节点的任何子节点上出现6.递归划分步骤停止的条件划分D（在N节点提供）的所有元组属于同一类没有剩余属性可以用来进一步划分元组——使用多数表决没有剩余的样本给定分支没有元组，则以D中多数类创建一个树叶1254属性选择度量属性选择度量属性选择度量是一种选择分裂准则，将给定类标号的训练元组最好的进行划分的方法理想情况，每个划分都是“纯”的，即落在一个给定分区的所有元组都属于相同的类属性选择度量又称为分裂规则常用的属性选择度量信息增益增益率基尼指数（Gini指数）1354信息增益选择具有最高信息增益的属性作为结点N的分裂属性pi是D中任意元组属于类Ci的非零概率，并用|Ci,D|/|D|估计对D中的元组分类所需要的期望信息（熵）由下式给出：14信息增益(D)InfoInfo(D)Gain(A)A)(log)(21imiippDInfo用属性A将D划分为v个分区或子集后，为了得到准确的分类，我们还需要多少信息？这个量由下式度量：)(||||)(1jvjjADInfoDDDInfo54例8.115ageincomestudentcredit_ratingbuys_computeryouthhighnofairnoyouthhighnoexcellentnomiddle_agedhighnofairyesseniormediumnofairyesseniorlowyesfairyesseniorlowyesexcellentnomiddle_agedlowyesexcellentyesyouthmediumnofairnoyouthlowyesfairyesseniormediumyesfairyesyouthmediumyesexcellentyesmiddle_agedmediumnoexcellentyesmiddle_agedhighyesfairyesseniormediumnoexcellentno5416例8.1940.0)145(log145)149(log149)5,9()(22IDInfo)3,2(145I代表“age=30”占14个样本中的5个有2个yes和3个noClassP:buys_computer=“yes”ClassN:buys_computer=“no”agepiniI(pi,ni)=30230.97131…4040040320.971048.0)_(151.0)(029.0)(ratingcreditGainstudentGainincomeGain相应的，计算对D中元组分类所需要的期望信息：694.0)2,3(145)0,4(144)3,2(145)(IIIDInfoage若元组根据age划分，则：246.0)()()(DInfoDInfoageGainage这种划分的信息增益：54计算连续值属性的信息增益假设A是连续值的，而不是离散值分裂D1是满足A≤split-point的元组集合,而D2是满足Asplit-point的元组集合必须确定A的“最佳”分裂点将A的值按递增序排序典型的，每对相邻值的中点被看作可能的分裂点A的值ai和ai+1之间的中点是(ai+ai+1)/2A具有最小期望信息需求的点选做A的分裂点1754增益率信息增益度量倾向于选择具有大量值的属性18ID3的后继C4.5使用一种称为增益率的信息增益扩充，试图克服这种偏倚，它用“分裂信息”值将信息增益规范化，分裂信息定义如下：分裂信息增益率)||||(log||||)(21DDDDDSplitInfojvjjAA)SplitInfo(/Gain(A)=A)GainRatio(选择具有最大增益率的属性作为分裂属性557.1)144(log144)146(log146)144(log144)(S222DplitInfoincome—GainRatio(income)=0.029/1.557=0.019例8.2incomehigh4medium6low454基尼指数如果A的二元划分将D划分成D1和D2，则给定该划分，D的基尼指数为：最大化不纯度降低（或等价地，具有最小基尼指数）的属性选为分裂属性。（需要枚举所有可能的分裂情况）19基尼指数度量数据分区或训练元组集D的不纯度，定义为：其中pj是D中元组属于Ci类的概率njpjD121)(Gini)(Gini||||)(Gini||||)(Gini2211DDDDDDDA不纯度降低为:)(Gini)(Gini)(GiniDDAA54属性选择度量对比信息增益偏向于多值属性基尼指数偏向于多值属性当类的数量很大时会有困难倾向于导致相等大小的分区和纯度增益率倾向于不平衡的划分，其中一个分区比其他分区小得多20三种度量通常会得到好的结果，但这些度量并非无偏的54过度拟合与树剪枝产生的决策树会出现过分适应数据的问题由于数据中的噪声和离群点，许多分枝反映的是训练数据的异常对未知样本判断不准确防止过分拟合的两种方法先剪枝通过提前停止树的构造，如果划分一个结点元组导致低于预定义临界值的划分，则给定子集的进一步划分将停止。选择一个合适的临界值往往很困难后剪枝由“完全生长”的树剪去子集——算法产生一个渐进的剪枝树集合使用一个独立的测试集来评估每颗树的准确率，就能得到具有最小期望错误率的决策树2154可伸缩性与决策树归纳RainForest(雨林)能适应可用的内存量，并用于任意决策树归纳算法结点N上属性A的AVC-集给出N上元组A的每个值的类标号计数在每个结点，对每个属性维护一个AVC-集（其中AVC表示“属性-值，类标号”），描述该结点的训练元组结点N上所有AVC-集的集合是N的AVC-组群225423雨林:训练集和它的AVC-集ageincomestudentcredit_ratingbuys_computer=30highnofairno=30highnoexcellentno31…40highnofairyes40mediumnofairyes40lowyesfairyes40lowyesexcellentno31…40lowyesexcellentyes=30mediumnofairno=30lowyesfairyes40mediumyesfairyes=30mediumyesexcellentyes31…40mediumnoexcellentyes31…40highyesfairyes40mediumnoexcellentnoAVC-setonincomeAVC-setonAgeAVC-setonStudentAVC-setoncredit_ratingAgeBuy_Computeryesno=302331..40404032incomeBuy_Computeryesnohigh22medium42low31studentBuy_Computeryesnoyes61no34CreditratingBuy_Computeryesnofair62excellent333贝叶斯分类方法54贝叶斯定理设X是数据元组（“证据”）：类标号未知P(H|X)是后验概率，或在条件X下，H的后验概率例如，X是一位35岁的顾客，其收入为4万美元。令H为某种假设，如顾客将购买计算机令H为某种假设，如数据元组X属于某个特定类C25P(H)(priorprobability)是先验概率，或H的先验概率例如,X将购买电脑,无论年龄和收入等等P(X)是X的先验概率，可观察到样本数据用上面的例子，它是顾客集合中年龄为35岁且收入为四万美元的概率贝叶斯定理为()()()()PHPHPHPXXX54朴素贝叶斯分类（NaïveBayesian）设D是训练元组和它们相关联