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

数据挖掘与商务智能范勤勤物流研究中心第八章分类1基本概念2决策树归纳3贝叶斯分类方法4基于规则的分类5模型评估与选择6提高分类准确率的技术基本概念分类VS.预测分类预测类标号（离散值）根据训练数据集和类标号属性，构建模型来分类现有数据，并用来分类新数据典型应用信誉证实（分类为低，中，高风险）医疗诊断（肿瘤是良性还是恶性）性能预测目标市场预测建立连续函数值模型，比如预测空缺值4一个两步过程第一步，建立一个分类模型，描述预定数据类或概念集假定每个元组属于一个预定义的类，由一个类标号属性确定基本概念训练数据集：由为建立模型而被分析的数据元组形成训练样本：训练数据集中的单个样本（元组）学习模型可以由分类规则、判定树或数学公式的形式提供第二步，使用模型，对将来的或未知的对象进行分类评估模型的预测准确率测试集：要独立于训练样本集，避免“过分拟合”的情况对每个测试样本，将已知的类标号和该样本的学习模型类预测比较准确率：被模型正确分类的测试样本的百分比如果准确率可以接受，那么使用该模型来分类标签为未知的样本56第一步——建立模型训练数据集分类算法IFrank=‘professor’ORyears>6THENtenured=‘yes’分类规则7第二步——用模型进行分类分类规则测试集未知数据(Jeff,Professor,4)Tenured?有指导的学习VS.无指导的学习有指导的学习（用于分类）模型的学习在被告知每个训练样本属于哪个类的“指导”下进行新数据使用训练数据集中得到的规则进行分类无指导的学习（用于聚类）每个训练样本的类编号是未知的，要学习的类集合或数量也可能是事先未知的通过一系列的度量、观察来建立数据中的类编号或进行聚类8决策树归纳用决策树归纳分类什么是决策树？类似于流程图的树结构每个内部节点（非树叶节点）表示在一个属性上的测试每个分枝代表该测试的一个输出每个树叶节点存放一个类标号10age?nostudent?credit_rating?noyesfairexcellentyouthseniornoyesyesyesMiddleaged决策树：Buys_computer用决策树归纳分类使用决策树分类给定一个类标号未知的元组X，在决策树上测试元组的属性值，跟踪一条由根到叶节点的路径，叶节点存放该元组的类预测。决策树容易转换为分类规则决策树的生成由两个阶段组成决策树构建：自顶向下递归地分治方式使用属性选择度量来选择将元组最好的划分为不同的类的属性递归的通过选定的属性（必须是离散值）来划分样本树剪枝决策树建立时，许多分枝反映的是训练数据中的噪声或离群点，树剪枝试图识别并剪去这种分枝，以提高对未知数据分类的准确性11决策树归纳策略输入数据分区D，训练元组和他们对应类标号的集合attribute_list,候选属性的集合Attribute_selection_method，指定选择属性的启发式过程算法步骤1.树以代表训练样本的单个节点（N）开始2.如果样本都在同一个类，则该节点成为树叶，并用该类标记3.否则，算法调用Attribute_selection_method，选择能够最好的将样本分类的属性；确定“分裂准则”，指出“分裂点”或“分裂子集”4.对测试属性每个已知的值，创建一个分支，并以此划分元组5.算法使用同样的过程，递归的形成每个划分上的元组决策树。一旦一个属性出现在一个节点上，就不在该节点的任何子节点上出现6.递归划分步骤停止的条件划分D（在N节点提供）的所有元组属于同一类没有剩余属性可以用来进一步划分元组——使用多数表决没有剩余的样本给定分支没有元组，则以D中多数类创建一个树叶12属性选择度量属性选择度量属性选择度量是一种选择分裂准则，将给定类标号的训练元组最好的进行划分的方法理想情况，每个划分都是“纯”的，即落在一个给定分区的所有元组都属于相同的类属性选择度量又称为分裂规则常用的属性选择度量信息增益增益率基尼指数（Gini指数）13信息增益选择具有最高信息增益的属性作为结点N的分裂属性pi是D中任意元组属于类Ci的非零概率，并用|Ci,D|/|D|估计对D中的元组分类所需要的期望信息（熵）由下式给出：14信息增益用属性A将D划分为v个分区或子集后，为了得到准确的分类，我们还需要多少信息？这个量由下式度量：例8.115ageincomestudentcredit_ratingbuys_computeryouthhighnofairnoyouthhighnoexcellentnomiddle_agedhighnofairyesseniormediumnofairyesseniorlowyesfairyesseniorlowyesexcellentnomiddle_agedlowyesexcellentyesyouthmediumnofairnoyouthlowyesfairyesseniormediumyesfairyesyouthmediumyesexcellentyesmiddle_agedmediumnoexcellentyesmiddle_agedhighyesfairyesseniormediumnoexcellentno16例8.1代表“age<=30”占14个样本中的5个有2个"yes"和3个"no"ClassP:buys_computer=“yes”ClassN:buys_computer=“no”相应的，计算对D中元组分类所需要的期望信息：若元组根据age划分，则：这种划分的信息增益：计算连续值属性的信息增益假设A是连续值的，而不是离散值分裂D1是满足A≤split-point的元组集合,而D2是满足A>split-point的元组集合必须确定A的“最佳”分裂点将A的值按递增序排序典型的，每对相邻值的中点被看作可能的分裂点A的值ai和ai+1之间的中点是(ai+ai+1)/2A具有最小期望信息需求的点选做A的分裂点17增益率信息增益度量倾向于选择具有大量值的属性18ID3的后继C4.5使用一种称为增益率的信息增益扩充，试图克服这种偏倚，它用“分裂信息”值将信息增益规范化，分裂信息定义如下：分裂信息增益率选择具有最大增益率的属性作为分裂属性—GainRatio(income)=0.029/1.557=0.019例8.2incomehigh4medium6low4基尼指数如果A的二元划分将D划分成D1和D2，则给定该划分，D的基尼指数为：最大化不纯度降低（或等价地，具有最小基尼指数）的属性选为分裂属性。（需要枚举所有可能的分裂情况）19基尼指数度量数据分区或训练元组集D的不纯度，定义为：其中pj是D中元组属于Ci类的概率不纯度降低为:属性选择度量对比信息增益偏向于多值属性基尼指数偏向于多值属性当类的数量很大时会有困难倾向于导致相等大小的分区和纯度增益率倾向于不平衡的划分，其中一个分区比其他分区小得多20三种度量通常会得到好的结果，但这些度量并非无偏的过度拟合与树剪枝产生的决策树会出现过分适应数据的问题由于数据中的噪声和离群点，许多分枝反映的是训练数据的异常对未知样本判断不准确防止过分拟合的两种方法先剪枝通过提前停止树的构造，如果划分一个结点元组导致低于预定义临界值的划分，则给定子集的进一步划分将停止。选择一个合适的临界值往往很困难后剪枝由“完全生长”的树剪去子集——算法产生一个渐进的剪枝树集合使用一个独立的测试集来评估每颗树的准确率，就能得到具有最小期望错误率的决策树21可伸缩性与决策树归纳RainForest(雨林)能适应可用的内存量，并用于任意决策树归纳算法结点N上属性A的AVC-集给出N上元组A的每个值的类标号计数在每个结点，对每个属性维护一个AVC-集（其中AVC表示“属性-值，类标号”），描述该结点的训练元组结点N上所有AVC-集的集合是N的AVC-组群2223雨林:训练集和它的AVC-集AVC-setonincomeAVC-setonAgeAVC-setonStudentAVC-setoncredit_ratingAgeBuy_Computeryesno<=302331..4040>4032incomeBuy_Computeryesnohigh22medium42low31studentBuy_Computeryesnoyes61no34CreditratingBuy_Computeryesnofair62excellent33贝叶斯分类方法贝叶斯定理设X是数据元组（“证据”）：类标号未知P(H|X)是后验概率，或在条件X下，H的后验概率例如，X是一位35岁的顾客，其收入为4万美元。令H为某种假设，如顾客将购买计算机令H为某种假设，如数据元组X属于某个特定类C25P(H)(priorprobability)是先验概率，或H的先验概率例如,X将购买电脑,无论年龄和收入等等P(X)是X的先验概率，可观察到样本数据用上面的例子，它是顾客集合中年龄为35岁且收入为四万美元的概率贝叶斯定理为朴素贝叶斯分类（NaïveBayesian）设D是训练元组和它们相关联的类标号的集合。通常，每个元组用一个n维属性向量X=(x1,x2,…,xn)表示，描述由n个属性对元组的n个测量给定元组X，分类法将预测X属于具有最高后验概率的类（在条件X下）假设有m个类C1,C2,…,Cm26根据贝叶斯定理由于P(X)对所有类为常数，所以需将下式最大化类条件独立使用朴素贝叶斯分类预测类标号类C1:buys_computer=‘yes’C2:buys_computer=‘no’希望分类的元组X=(age<=30,Income=medium,Student=yes，Credit_rating=Fair)27ageincomestudentcredit_ratingbuys_computer<=30highnofairno<=30highnoexcellentno31…40highnofairyes>40mediumnofairyes>40lowyesfairyes>40lowyesexcellentno31…40lowyesexcellentyes<=30mediumnofairno<=30lowyesfairyes>40mediumyesfairyes<=30mediumyesexcellentyes31…40mediumnoexcellentyes31…40highyesfairyes>40mediumnoexcellentno使用朴素贝叶斯分类预测类标号P(Ci)P(buys_computer=“yes”)=9/14=0.643P(buys_computer=“no”)=5/14=0.357为计算P(X|Ci)，计算下面的条件概率P(age=“<=30”|buys_computer=“yes”)=2/9=0.222P(age=“<=30”|buys_computer=“no”)=3/5=0.600P(income=“medium”|buys_computer=“yes”)=4/9=0.444P(income=“medium”|buys_computer=“no”)=2/5=0.400P(student=“yes”|buys_computer=“yes)=6/9=0.667P(student=“yes”|buys_computer=“no”)=1/5=0.200P(credit_rating=“fair”|buys_computer=“yes”)=6/9=0.667P(credit_rating=“fair”|buys_computer=“no”)=2/5=0.40028ageincomebuys_computer<=30highno<=30highno31…40highyes>40mediumyes>40lowyes>40lowno31…40lowyes<=30mediumno<=30lowyes>40mediumyes<=30mediumyes31…40mediumyes31…40highyes>40mediumnostudentcredit_ratingbuys_computernofairnonoexcellentnonofairyesnofairyesyesfairyesyesexcellentnoyesexcellentyesnofairnoyesfairyesyesfairyesyesexcellentyesnoexcellentyesyesfairyesnoexcellentno使用朴素贝叶斯分类预测类标号X=(age<=30,income=medium,student=yes,credit_rating=fair)P(X|Ci)*P(Ci)P(X|buys_computer=“yes”)*P(buys_computer=“yes”)=0.028P(X|buys_computer=“no”)*P(buys_computer=“no”)=0.007P(X|Ci)P(X|buys_computer=“yes”)=0.222x0.444x0.667x0.667=0.044P(X|buys_computer=“no”)=0.6x0.4x0.2x0.4=0.019因此，对于元组X，朴素贝叶斯分类预测元组X的类为“buys_computer=yes”29使用拉普拉斯校准避免计算零概率值例8.5假设在某训练数据库D上,类buys-computer=yes包含1000个元组，0个元组income=low,990个元组income=medium,10个元组income=high用拉普拉斯进行校准对每个收入-值对增加一个元组Prob(income=low)=1/1003Prob(income=medium)=991/1003Prob(income=high)=11/1003这些“校准的”概率估计与对应的“未校准的”估计很接近，但是避免了零概率值30基于规则的分类使用IF-THEN规则分类一个IF-THEN规则是一个如下形式的表达式R:IFage=youthANDstudent=yesTHENbuys_computer=yes规则前件/规则的结论将R的覆盖率和准确率定义为ncovers

：为规则R覆盖的元组数ncorrect：R正确分类的元组数coverage(R)=ncovers/|D|/*D:trainingdataset*/accuracy(R)=ncorrect/ncovers32使用IF-THEN规则分类如果多个规则被触发，则需要一种解决冲突的策略来决定激活哪一个规则，并对X指派它的类预测规模序:方案把最高优先权赋予具有“最苛刻”要求的被触发的规则，其中苛刻性用规则前件的规模度量，激活具有最多属性测试的被触发的规则。基于类的序:类按“重要性”递减排序，如按普遍性的降序排序基于规则的序:根据规则质量的度量，或领域专家的建议，把规则组织成一个优先权列表33由决策树提取规则规则比大的决策树更容易理解对每条从根到树叶结点的路径创建一个规则规则是互斥的和穷举的例8.7由决策树提取分类规则IFage=youngANDstudent=noTHENbuys_computer=noIFage=youngANDstudent=yesTHENbuys_computer=yesIFage=mid-age THENbuys_computer=yesIFage=oldANDcredit_rating=excellentTHENbuys_computer=noIFage=oldANDcredit_rating=fairTHENbuys_computer=yes34age?student?creditrating?<=30>40noyesyesyes31..40nofairexcellentyesno模型评估与选择模型评估与选择评价指标:我们如何测量精度?其他指标要考虑吗?评估一个分类准确率的方法保持方法,随机二次抽样交叉验证自助法分类器的准确率最好在检验集上估计模型选择统计显著性检验基于成本效益和ROC曲线36评估分类器性能的度量37正组元（P）：感兴趣的主要类的元组。负组元（N）：其他元组。真正例（TruePositive，TP）：是指被分类器正确分类的正元组。真负例（TrueNegative，TN）：是指被分类器正确分类的负元组。假正例（FalsePositive，FP）：是被错误地标记为正元组的负元组。假负例（False

Negative，FN）：是被错误地标记为负元组的正元组。评估分类器性能的度量：混淆矩阵混淆矩阵给定m个类，混淆矩阵前m行和m列中的表目CMi,j指出类i的元组被分类器标记为类j的个数混淆矩阵的例子38实际的类\预测的类yesnoyesTPFNnoFPTN类buy_computer=yesbuy_computer=no合计buy_computer=yes6954467000buy_computer=no41225883000合计7366263410000准确性、错误率、敏感度和特效性类不平衡问题其中感兴趣的主类是稀少的，例如“欺诈”正类多，负类少灵敏性(召回率):正确识别的正元组的百分比,灵敏性=TP/P特效性:正确识别的负元组的百分比,特效性=TN/N准确率=灵敏性×P/(P+N)+特效性×N/(P+N)=(TP+TN)/(P+N)错误率)=(FP+FN)/(P+N)39A\Pyesno合计yesTPFNPnoFPTNN合计P’N’P+N精度、召回率、F度量精度:精确性的度量，即标记为正类元组实际为正类所占的百分比F度量(F1

或F分数):把精度和召回率集中到一个度量中Fß:精度和召回率的加权度量它赋予召回率权重是赋予进度的β倍40例子41类cancer=yescancer=no合计识别率(%)cancer=yes90（TP）210（FN）300（P）30.00(sensitivitycancer=no140（FP）9560（TN）9700（N）98.56(specificity)合计23097701000096.40(accuracy)准确率（TP+TN）/(P+N)错误率（FP+FN）/(P+N)敏感度（召回率）TP/P特效性TN/N精度TP/(TP+FP)Precision=90/230=39.13%

Recall=90/300=30.00%保持方法,随机二次抽样保持方法给定的数据随机的划分为两个独立的集合训练集，通常2/3的数据被分配到训练集检验集，通常1/3的数据被分配到检验集随机二次抽样:保持方法的变形将保持方法重复k次，总准确率估计取每次迭代准确率的平均值交叉验证(k-折交叉验证)初始数据随机地划分成k个互不相关的子集，每个子集的大小大致相等在第i次迭代,分区Di用作检验集，其他区位训练集留一:每次只给检验集“留出”一个样本分层交叉验证：折被分层，使的每个折中样本的类分布与在初始数据中的大致相同42自助法自助法处理较小的数据集合比较有效从给定训练元组中有放回的均匀抽样在有放回的抽样中，允许机器多次选择同一个元组43有多种自助方法,最常用的一种是.632自助法假设给定的数据集包括d个元组。该数据集有放回地抽样d次，产生d个样本的自助样本集或训练集。结果是，在平均的情况下，63.2%的原数据元组将出现在自助样本中，而其余36.8%的元组将形成检验使用统计显著性检验选择模型假设已经由数据产生了两个分类模型M1

和M2,如何确定哪一个更好？M1

和M2

的平均错误率虽不同，但差别可能不是统计显著的进行10折交叉验证，得到每一个平均错误率err(M1)和err(M2)i如果二者之间的差别只是偶然的，该如何处理？统计显著性检验44使用统计显著性检验选择模型如果我们能拒绝原假设,则则可以断言模型之间的差是统计显著的在此情况下，我们可以选择具有较低错误率的模型45进行10次10-折交叉验证利用t-检验假设它们服从具有k-1个自由度的t分布，其中k=10.原假设:M1&M2

相同t-检验46如果使用单个检验集:逐对比较