数据挖掘第8章分类基本概念.ppt

《数据挖掘第8章分类基本概念.ppt》由会员分享，可在线阅读，更多相关《数据挖掘第8章分类基本概念.ppt（54页珍藏版）》请在三一文库上搜索。

1、数据挖掘与商务智能范勤勤范勤勤物流研究中心物流研究中心第八章 分类1基本概念2决策树归纳3贝叶斯分类方法4基于规则的分类5模型评估与选择6提高分类准确率的技术1基本概念54分类 VS.预测分类预测类标号（离散值）根据训练数据集和类标号属性，构建模型来分类现有数据，并用来分类新数据典型应用信誉证实（分类为低，中，高风险）医疗诊断（肿瘤是良性还是恶性）性能预测目标市场预测建立连续函数值模型，比如预测空缺值454一个两步过程 第一步，建立一个分类模型，描述预定数据类或概念集假定每个元组属于一个预定义的类，由一个类标号属性确定基本概念训练数据集：由为建立模型而被分析的数据元组形成训练样本：训练数据集中

2、的单个样本（元组）学习模型可以由分类规则、判定树或数学公式的形式提供第二步，使用模型，对将来的或未知的对象进行分类评估模型的预测准确率测试集：要独立于训练样本集，避免“过分拟合”的情况对每个测试样本，将已知的类标号和该样本的学习模型类预测比较准确率：被模型正确分类的测试样本的百分比如果准确率可以接受，那么使用该模型来分类标签为未知的样本5546第一步建立模型训练数据集分类算法IF rank=professorOR years 6THEN tenured=yes 分类规则547第二步用模型进行分类分类规则测试集未知数据(Jeff,Professor,4)Tenured?54有指导的学习 VS.无

3、指导的学习有指导的学习（用于分类）模型的学习在被告知每个训练样本属于哪个类的“指导”下进行新数据使用训练数据集中得到的规则进行分类无指导的学习（用于聚类）每个训练样本的类编号是未知的，要学习的类集合或数量也可能是事先未知的通过一系列的度量、观察来建立数据中的类编号或进行聚类82决策树归纳54用决策树归纳分类什么是决策树？类似于流程图的树结构每个内部节点（非树叶节点）表示在一个属性上的测试每个分枝代表该测试的一个输出每个树叶节点存放一个类标号10age?nostudent?credit_rating?noyesfairexcellentyouthseniornoyesyesyesMiddleag

4、ed决策树：Buys_computer54用决策树归纳分类使用决策树分类给定一个类标号未知的元组X，在决策树上测试元组的属性值，跟踪一条由根到叶节点的路径，叶节点存放该元组的类预测。决策树容易转换为分类规则决策树的生成由两个阶段组成决策树构建：自顶向下递归地分治方式使用属性选择度量来选择将元组最好的划分为不同的类的属性递归的通过选定的属性（必须是离散值）来划分样本树剪枝决策树建立时，许多分枝反映的是训练数据中的噪声或离群点，树剪枝试图识别并剪去这种分枝，以提高对未知数据分类的准确性1154决策树归纳策略输入数据分区D，训练元组和他们对应类标号的集合attribute_list,候选属性的集合A

5、ttribute_selection_method，指定选择属性的启发式过程算法步骤1.树以代表训练样本的单个节点（N）开始2.如果样本都在同一个类，则该节点成为树叶，并用该类标记3.否则，算法调用Attribute_selection_method，选择能够最好的将样本分类的属性；确定“分裂准则”，指出“分裂点”或“分裂子集”4.对测试属性每个已知的值，创建一个分支，并以此划分元组5.算法使用同样的过程，递归的形成每个划分上的元组决策树。一旦一个属性出现在一个节点上，就不在该节点的任何子节点上出现6.递归划分步骤停止的条件划分D（在N节点提供）的所有元组属于同一类没有剩余属性可以用来进一步划

6、分元组使用多数表决没有剩余的样本给定分支没有元组，则以D中多数类创建一个树叶1254属性选择度量属性选择度量属性选择度量是一种选择分裂准则，将给定类标号的训练元组最好的进行划分的方法理想情况，每个划分都是“纯”的，即落在一个给定分区的所有元组都属于相同的类属性选择度量又称为分裂规则常用的属性选择度量信息增益增益率基尼指数（Gini指数）1354信息增益选择具有最高信息增益的属性作为结点N 的分裂属性pi 是D中任意元组属于类Ci的非零概率，并用|Ci,D|/|D|估计对D中的元组分类所需要的期望信息（熵）由下式给出：14信息增益用属性A将D划分为v个分区或子集后，为了得到准确的分类，我们还需要

7、多少信息？这个量由下式度量：54例8.115ageincomestudentcredit_ratingbuys_computeryouthhighnofairnoyouthhighnoexcellentnomiddle_agedhighnofairyesseniormediumnofairyesseniorlowyesfairyesseniorlowyesexcellentnomiddle_agedlowyesexcellentyesyouthmediumnofairnoyouthlowyesfairyesseniormediumyesfairyesyouthmediumyesexcellen

8、tyesmiddle_agedmediumnoexcellentyesmiddle_agedhighyesfairyesseniormediumnoexcellentno5416例8.1代表“age split-point 的元组集合必须确定A的“最佳”分裂点将A的值按递增序排序典型的，每对相邻值的中点被看作可能的分裂点A的值 ai 和 ai+1 之间的中点是(ai+ai+1)/2A具有最小期望信息需求的点选做A的分裂点1754增益率信息增益度量倾向于选择具有大量值的属性18ID3 的后继 C4.5 使用一种称为增益率的信息增益扩充，试图克服这种偏倚，它用“分裂信息”值将信息增益规范化，分裂信

9、息定义如下：分裂信息增益率选择具有最大增益率的属性作为分裂属性 GainRatio(income)=0.029/1.557=0.019例8.2incomehigh4medium6low454基尼指数如果A的二元划分将D划分成D1和D2，则给定该划分，D的基尼指数为：最大化不纯度降低（或等价地，具有最小基尼指数）的属性选为分裂属性。（需要枚举所有可能的分裂情况）19基尼指数度量数据分区或训练元组集D的不纯度，定义为：其中 pj 是D 中元组属于Ci类的概率不纯度降低为:54属性选择度量对比信息增益偏向于多值属性基尼指数偏向于多值属性当类的数量很大时会有困难倾向于导致相等大小的分区和纯度增益率倾向

10、于不平衡的划分，其中一个分区比其他分区小得多20三种度量通常会得到好的结果，但这些度量并非无偏的54过度拟合与树剪枝产生的决策树会出现过分适应数据的问题由于数据中的噪声和离群点，许多分枝反映的是训练数据的异常对未知样本判断不准确防止过分拟合的两种方法先剪枝通过提前停止树的构造，如果划分一个结点元组导致低于预定义临界值的划分，则给定子集的进一步划分将停止。选择一个合适的临界值往往很困难后剪枝由“完全生长”的树剪去子集算法产生一个渐进的剪枝树集合使用一个独立的测试集来评估每颗树的准确率，就能得到具有最小期望错误率的决策树2154可伸缩性与决策树归纳RainForest(雨林)能适应可用的内存量，并

11、用于任意决策树归纳算法结点N上属性A的AVC-集给出N上元组A的每个值的类标号计数 在每个结点，对每个属性维护一个AVC-集（其中AVC表示“属性-值，类标号”），描述该结点的训练元组结点N上所有AVC-集的集合是N的AVC-组群225423雨林:训练集和它的AVC-集AVC-set on incomeAVC-set on AgeAVC-set on StudentAVC-set on credit_ratingAgeBuy_Computeryesno4032incomeBuy_Computeryesnohigh22medium42low31studentBuy_Computeryesnoye

12、s61no34CreditratingBuy_Computeryesnofair62excellent333贝叶斯分类方法54贝叶斯定理设X是数据元组（“证据”）：类标号未知P(H|X)是后验概率，或在条件X下，H的后验概率例如，X是一位35岁的顾客，其收入为4万美元。令H为某种假设，如顾客将购买计算机令 H 为某种假设，如数据元组 X 属于某个特定类C 25P(H)(prior probability)是先验概率，或H的先验概率例如,X 将购买电脑,无论年龄和收入等等P(X)是X的先验概率，可观察到样本数据用上面的例子，它是顾客集合中年龄为35岁且收入为四万美元的概率贝叶斯定理为54朴素贝叶

13、斯分类（Nave Bayesian）设D是训练元组和它们相关联的类标号的集合。通常，每个元组用一个n维属性向量X=(x1,x2,xn)表示，描述由n个属性对元组的n个测量给定元组X，分类法将预测X属于具有最高后验概率的类（在条件X下）假设有m个类 C1,C2,Cm26根据贝叶斯定理由于 P(X)对所有类为常数，所以需将下式最大化类条件独立54使用朴素贝叶斯分类预测类标号类C1:buys_computer=yesC2:buys_computer=no希望分类的元组X=(age=30,Income=medium,Student=yes，Credit_rating=Fair)27ageincome

14、student credit_rating buys_computer=30highnofairno40mediumnofairyes40lowyesfairyes40lowyesexcellentno3140lowyesexcellentyes=30mediumnofairno40mediumyesfairyes40mediumnoexcellentno54使用朴素贝叶斯分类预测类标号P(Ci)P(buys_computer=“yes”)=9/14=0.643P(buys_computer=“no”)=5/14=0.357为计算P(X|Ci)，计算下面的条件概率P(age=“=30”|buy

15、s_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

16、0.667P(credit_rating=“fair”|buys_computer=“no”)=2/5=0.40028ageincome buys_computer=30highno40mediumyes40lowyes40lowno3140lowyes=30 mediumno40mediumyes40mediumnostudent credit_ratingbuys_computernofairnonoexcellentnonofairyesnofairyesyesfairyesyesexcellentnoyesexcellentyesnofairnoyesfairyesyesfairye

17、syesexcellentyesnoexcellentyesyesfairyesnoexcellentno54使用朴素贝叶斯分类预测类标号 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.222 x 0.444 x 0.667 x 0.

18、667=0.044P(X|buys_computer=“no”)=0.6 x 0.4 x 0.2 x 0.4=0.019因此，对于元组X，朴素贝叶斯分类预测元组X的类为“buys_computer=yes”2954使用拉普拉斯校准避免计算零概率值 例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(

19、income=high)=11/1003这些“校准的”概率估计与对应的“未校准的”估计很接近，但是避免了零概率值304基于规则的分类54使用IF-THEN规则分类一个 IF-THEN 规则是一个如下形式的表达式R:IF age=youth AND student=yes THEN buys_computer=yes规则前件/规则的结论将R的覆盖率和准确率定义为ncovers：为规则R覆盖的元组数ncorrect：R正确分类的元组数coverage(R)=ncovers/|D|/*D:training data set*/accuracy(R)=ncorrect/ncovers3254使用IF-

20、THEN规则分类如果多个规则被触发，则需要一种解决冲突的策略来决定激活哪一个规则，并对X指派它的类预测规模序:方案把最高优先权赋予具有“最苛刻”要求的被触发的规则，其中苛刻性用规则前件的规模度量，激活具有最多属性测试的被触发的规则。基于类的序:类按“重要性”递减排序，如按普遍性的降序排序基于规则的序:根据规则质量的度量，或领域专家的建议，把规则组织成一个优先权列表3354由决策树提取规则规则比大的决策树更容易理解对每条从根到树叶结点的路径创建一个规则规则是互斥的和穷举的 例8.7 由决策树提取分类规则IF age=young AND student=no THEN buys_computer=

21、noIF age=young AND student=yes THEN buys_computer=yesIF age=mid-age THEN buys_computer=yesIF age=old AND credit_rating=excellent THEN buys_computer=noIF age=old AND credit_rating=fair THEN buys_computer=yes34age?student?credit rating?40noyesyesyes31.40nofairexcellentyesno5模型评估与选择54模型评估与选择评价指标:我们如何测量

22、精度?其他指标要考虑吗?评估一个分类准确率的方法保持方法,随机二次抽样交叉验证自助法分类器的准确率最好在检验集上估计模型选择统计显著性检验基于成本效益和ROC 曲线3654评估分类器性能的度量37正组元（P）：感兴趣的主要类的元组。负组元（N）：其他元组。真正例（True Positive，TP）：是指被分类器正确分类的正元组。真负例（True Negative，TN）：是指被分类器正确分类的负元组。假正例（False Positive，FP）：是被错误地标记为正元组的负元组。假负例（False Negative，FN）：是被错误地标记为负元组的正元组。54评估分类器性能的度量：混淆矩阵混淆矩

23、阵给定m个类，混淆矩阵前m行和m列中的表目CMi,j指出类i的元组被分类器标记为类j的个数混淆矩阵的例子38实际的类预测的类yesnoyesTPFNnoFPTN类buy_computer=yesbuy_computer=no合计buy_computer=yes6954467000buy_computer=no41225883000合计736626341000054准确性、错误率、敏感度和特效性类不平衡问题其中感兴趣的主类是稀少的，例如“欺诈”正类多，负类少灵敏性(召回率):正确识别的正元组的百分比,灵敏性=TP/P特效性:正确识别的负元组的百分比,特效性=TN/N准确率=灵敏性P/(P+N)+

24、特效性N/(P+N)=(TP+TN)/(P+N)错误率)=(FP+FN)/(P+N)39APyesno合计yesTPFNPnoFPTNN合计PNP+N54精度、召回率、F 度量 精度:精确性的度量，即标记为正类元组实际为正类所占的百分比F 度量(F1 或 F分数):把精度和召回率集中到一个度量中F:精度和召回率的加权度量它赋予召回率权重是赋予进度的倍4054例子41类cancer=yescancer=no合计识别率(%)cancer=yes90（TP）210（FN）300（P）30.00(sensitivitycancer=no140（FP）9560（TN）9700（N）98.56(speci

25、ficity)合计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%54保持方法,随机二次抽样保持方法给定的数据随机的划分为两个独立的集合训练集，通常2/3的数据被分配到训练集检验集，通常1/3的数据被分配到检验集随机二次抽样:保持方法的变形将保持方法重复k次，总准确率估计取每次迭代准确率的平均值交叉验证(k-折交叉验证)初始数据随机地划分成k

26、个互不相关的子集，每个子集的大小大致相等在第i次迭代,分区 Di 用作检验集，其他区位训练集留一:每次只给检验集“留出”一个样本分层交叉验证：折被分层，使的每个折中样本的类分布与在初始数据中的大致相同4254自助法自助法处理较小的数据集合比较有效从给定训练元组中有放回的均匀抽样在有放回的抽样中，允许机器多次选择同一个元组43有多种自助方法,最常用的一种是.632 自助法假设给定的数据集包括d个元组。该数据集有放回地抽样d次，产生d个样本的自助样本集或训练集。结果是，在平均的情况下，63.2%的原数据元组将出现在自助样本中，而其余 36.8%的元组将形成检验54使用统计显著性检验选择模型假设已经

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

28、到 err(M1)i and err(M2)i对 10轮的M1和M2 的错误率分别取平均值t-检验计算样本具有k-1自由度的t-统计量:如果有两个检验集54使用统计显著性检验选择模型M1&M2 是否显著不同?计算 t.选择显著水平sig(e.g.sig=5%)查找t分布表查找 置信界 z=sig/2(这里,0.025)如果 t z or t -z,则t落在拒绝区域，两个模型间存在统计显著差别否则,两者之间的差是随机的476提高分类准确率的技术54提高分类准确率的技术组合分类方法利用模型的组合来提高准确率把k个学习得到的模型,M1,M2,Mk,组合在一起 旨在创建一个改进的复合分类模型 M*常见

29、的组合分类方法装袋提升随机森林4954装袋：自助聚集类比:最终诊断根据多数表决做出分类:对未知元组 X 分类每个分类器 Mi 返回它的类预测装袋分类器 M*统计得票，并将得票最高的类赋予X步骤给定d个元组的集合D,对于迭代i,d个元组的训练集 Di 采用有放回抽样，由原始元组集D抽取由每个训练集Di 学习，得到一个分类模型Mi50预测:通过取给定检验元组的每个预测的平均值，装袋也可用于连续值得预测准确率：通常高于从原训练集 D导出的单个分类器的准确率54提升怎样提升?权重赋予每个训练元组迭代地学习k个分类器学习得到分类器 Mi 后,更新权重，使其后的分类器 Mi+1“更关注”Mi 误分类的训练元组最终提升的分类器 M*组合每个个体分类器的表决，其中每个分类器投票的权重是其准确率的函数5154Adaboost52给定数据集D，包涵d个类标记的元组,(X1,y1),(Xd,yd)为组合分类器产生k个基分类器需要执行算法其余部分k轮开始，对每个训练元组赋予相等的权重(1/d)错误率:err(Xj)是元组 Xj误分类误差.Mi 的权重54提高类不平衡数据的分类准确率类不平衡问题:正类多，负类少，例如“欺诈”提高类不平衡数据分类准确率的方法过抽样欠抽样阀值移动组合技术传统的分类算法旨在最小化分类误差，不适合类不平衡数据53谢谢关注欢迎指导