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

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

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

3、TomAssistant Prof2noMerlisaAssociate Prof7noGeorge Professor5yesJoseph Assistant Prof7yes未知数据(Jeff, Professor, 4)Tenured?54有指导的学习 VS. 无指导的学习有指导的学习（用于分类） 模型的学习在被告知每个训练样本属于哪个类的“指导”下进行 新数据使用训练数据集中得到的规则进行分类无指导的学习（用于聚类） 每个训练样本的类编号是未知的，要学习的类集合或数量也可能是事先未知的 通过一系列的度量、观察来建立数据中的类编号或进行聚类82决策树归纳54用决策树归纳分类什么是决策树？

4、 类似于流程图的树结构 每个内部节点（非树叶节点）表示在一个属性上的测试 每个分枝代表该测试的一个输出 每个树叶节点存放一个类标号10age?nostudent?credit_rating?noyesfairexcellentyouthseniornoyesyesyesMiddleaged决策树：Buys_computer54用决策树归纳分类使用决策树分类 给定一个类标号未知的元组X，在决策树上测试元组的属性值，跟踪一条由根到叶节点的路径，叶节点存放该元组的类预测。 决策树容易转换为分类规则决策树的生成由两个阶段组成 决策树构建：自顶向下递归地分治方式 使用属性选择度量来选择将元组最好的划分为

5、不同的类的属性 递归的通过选定的属性（必须是离散值）来划分样本 树剪枝 决策树建立时，许多分枝反映的是训练数据中的噪声或离群点，树剪枝试图识别并剪去这种分枝，以提高对未知数据分类的准确性1154决策树归纳策略输入 数据分区D，训练元组和他们对应类标号的集合 attribute_list,候选属性的集合 Attribute_selection_method，指定选择属性的启发式过程算法步骤 1. 树以代表训练样本的单个节点（N）开始 2. 如果样本都在同一个类，则该节点成为树叶，并用该类标记 3. 否则，算法调用Attribute_selection_method，选择能够最好的将样本分类的属性

6、；确定“分裂准则”，指出“分裂点”或“分裂子集” 4. 对测试属性每个已知的值，创建一个分支，并以此划分元组 5. 算法使用同样的过程，递归的形成每个划分上的元组决策树。一旦一个属性出现在一个节点上，就不在该节点的任何子节点上出现 6. 递归划分步骤停止的条件 划分D（在N节点提供）的所有元组属于同一类 没有剩余属性可以用来进一步划分元组使用多数表决 没有剩余的样本 给定分支没有元组，则以D中多数类创建一个树叶1254属性选择度量属性选择度量 属性选择度量是一种选择分裂准则，将给定类标号的训练元组最好的进行划分的方法 理想情况，每个划分都是“纯”的，即落在一个给定分区的所有元组都属于相同的类

7、属性选择度量又称为分裂规则常用的属性选择度量 信息增益 增益率 基尼指数（Gini指数）1354信息增益选择具有最高信息增益的属性作为结点N 的分裂属性pi 是D中任意元组属于类Ci的非零概率，并用|Ci, D|/|D| 估计对D中的元组分类所需要的期望信息（熵）由下式给出：14信息增益(D)InfoInfo(D)Gain(A)A)(log)(21imiippDInfo用属性A将D划分为v个分区或子集后，为了得到准确的分类，我们还需要多少信息？这个量由下式度量：)(|)(1jvjjADInfoDDDInfo54例8.115ageincomestudentcredit_ratingbuys_co

8、mputeryouthhighnofairnoyouthhighnoexcellentnomiddle_agedhighnofairyesseniormediumnofairyesseniorlowyesfairyesseniorlowyesexcellentnomiddle_agedlowyesexcellentyesyouthmediumnofairnoyouthlowyesfairyesseniormediumyesfairyesyouthmediumyesexcellentyesmiddle_agedmediumnoexcellentyesmiddle_agedhighyesfairy

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

10、分裂信息定义如下： 分裂信息 增益率)|(log|)(21DDDDDSplitInfojvjjAA)SplitInfo( / Gain(A) = A)GainRatio(选择具有最大增益率的属性作为分裂属性557. 1)144(log144)146(log146)144(log144)(S222DplitInfoincome GainRatio(income) = 0.029/1.557 = 0.019例8.2incomehigh4medium6low454基尼指数如果A的二元划分将D划分成D1和D2，则给定该划分，D的基尼指数为：最大化不纯度降低（或等价地，具有最小基尼指数）的属性选为分裂属

11、性。（需要枚举所有可能的分裂情况）19基尼指数度量数据分区或训练元组集D的不纯度，定义为： 其中 pj 是D 中元组属于Ci类的概率njpjD121)(Gini)(Gini|)(Gini|)(Gini2211DDDDDDDA不纯度降低为:)(Gini)(Gini)(GiniDDAA54属性选择度量对比信息增益 偏向于多值属性基尼指数 偏向于多值属性 当类的数量很大时会有困难 倾向于导致相等大小的分区和纯度增益率 倾向于不平衡的划分，其中一个分区比其他分区小得多20三种度量通常会得到好的结果，但这些度量并非无偏的54过度拟合与树剪枝产生的决策树会出现过分适应数据的问题 由于数据中的噪声和离群点，

12、许多分枝反映的是训练数据的异常 对未知样本判断不准确防止过分拟合的两种方法 先剪枝 通过提前停止树的构造，如果划分一个结点元组导致低于预定义临界值的划分，则给定子集的进一步划分将停止。 选择一个合适的临界值往往很困难 后剪枝 由“完全生长”的树剪去子集算法产生一个渐进的剪枝树集合 使用一个独立的测试集来评估每颗树的准确率，就能得到具有最小期望错误率的决策树2154可伸缩性与决策树归纳RainForest (雨林)能适应可用的内存量，并用于任意决策树归纳算法结点N上属性A的AVC-集给出N上元组A的每个值的类标号计数 在每个结点，对每个属性维护一个AVC-集（其中AVC表示“属性-值，类标号”）

13、，描述该结点的训练元组结点N上所有AVC-集的集合是N的AVC-组群225423雨林: 训练集和它的AVC-集AVC-set on incomeAVC-set on AgeAVC-set on StudentAVC-set on credit_ratingAgeBuy_Computeryesno4032incomeBuy_Computeryesnohigh22medium42low31studentBuy_Computeryesnoyes61no34CreditratingBuy_Computeryesnofair62excellent333贝叶斯分类方法54贝叶斯定理设X是数据元组（“证据”

14、）：类标号未知P(H|X)是后验概率，或在条件X下，H的后验概率 例如，X是一位35岁的顾客，其收入为4万美元。令H为某种假设，如顾客将购买计算机令 H 为某种假设 ，如数据元组 X 属于某个特定类C 25P(H) (prior probability)是先验概率，或H的先验概率 例如, X 将购买电脑, 无论年龄和收入等等P(X)是X的先验概率，可观察到样本数据 用上面的例子，它是顾客集合中年龄为35岁且收入为四万美元的概率贝叶斯定理为()()()()PHP HP HPXXX54朴素贝叶斯分类（Nave Bayesian）设D是训练元组和它们相关联的类标号的集合。通常，每个元组用一个n维属性

15、向量X = (x1, x2, , xn) 表示，描述由n个属性对元组的n个测量给定元组X，分类法将预测X属于具有最高后验概率的类（在条件X下）假设有m个类 C1, C2, , Cm26根据贝叶斯定理)()()|()|(XXXPiCPiCPiCP由于 P(X) 对所有类为常数 ，所以需将下式最大化)()|()|(iCPiCPiCPXX 121()()()()()nikiiinikPCP xCP xCP xCP xCX类条件独立54使用朴素贝叶斯分类预测类标号类 C1:buys_computer = yes C2:buys_computer = no希望分类的元组 X = (age =30,Inc

16、ome = medium,Student = yes，Credit_rating = Fair)27ageincome student credit_rating buys_computer=30highnofairno40mediumnofairyes40lowyesfairyes40lowyesexcellentno3140lowyesexcellentyes=30mediumnofairno40mediumyesfairyes40mediumnoexcellentno54使用朴素贝叶斯分类预测类标号P(Ci) P(buys_computer = “yes”) = 9/14 = 0.643

17、 P(buys_computer = “no”) = 5/14= 0.357为计算P(X|Ci) ，计算下面的条件概率 P(age = “=30” | buys_computer = “yes”) = 2/9 = 0.222 P(age = “= 30” | buys_computer = “no”) = 3/5 = 0.600 P(income = “medium” | buys_computer = “yes”) = 4/9 = 0.444 P(income = “medium” | buys_computer = “no”) = 2/5 = 0.400 P(student = “yes”

18、 | buys_computer = “yes) = 6/9 = 0.667 P(student = “yes” | buys_computer = “no”) = 1/5 = 0.200 P(credit_rating = “fair” | buys_computer = “yes”) = 6/9 = 0.667 P(credit_rating = “fair” | buys_computer = “no”) = 2/5 = 0.40028ageincome buys_computer=30highno40mediumyes40lowyes40lowno3140lowyes=30 mediu

19、mno40mediumyes40mediumnostudent credit_ratingbuys_computernofairnonoexcellentnonofairyesnofairyesyesfairyesyesexcellentnoyesexcellentyesnofairnoyesfairyesyesfairyesyesexcellentyesnoexcellentyesyesfairyesnoexcellentno54使用朴素贝叶斯分类预测类标号 X = (age = 30 , income = medium, student = yes, credit_rating = fai

20、r)P(X|Ci)*P(Ci) P(X|buys_computer = “yes”) * P(buys_computer =“yes”) = 0.028 P(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.667 = 0.044 P(X|buys_computer = “no”) = 0.6 x 0.4 x 0.2 x 0.4 = 0.019因此，对于元组X，朴素贝叶斯分类预测元组X的类为“buys_com

21、puter = yes”29)C|P(x)C|)P(xC|P(x)C|P(x)C|P(Xini2i1n1kiki 54使用拉普拉斯校准避免计算零概率值 例8.5 假设在某训练数据库D上,类buys-computer=yes包含1000个元组，0个元组 income=low,990个元组 income= medium, 10个元组income = high 用拉普拉斯进行校准 对每个收入-值对增加一个元组 Prob(income = low) = 1/1003 Prob(income = medium) = 991/1003 Prob(income = high) = 11/1003 这些“校准

22、的”概率估计与对应的“未校准的”估计很接近，但是避免了零概率值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-T

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

24、uys_computer = no IF age = young AND student = yes THEN buys_computer = yes IF age = mid-age THEN buys_computer = yes IF age = old AND credit_rating = excellent THEN buys_computer = no IF age = old AND credit_rating = fair THEN buys_computer = yes34age?student?credit rating?40noyesyesyes31.40nofaire

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

26、egative，FN）：是被错误地标记为负元组的正元组。54评估分类器性能的度量：混淆矩阵混淆矩阵给定m个类，混淆矩阵前m行和m列中的表目CMi,j指出类i的元组被分类器标记为类j的个数混淆矩阵的例子38实际的类预测的类yesnoyesTPFNnoFPTN类buy_computer = yesbuy_computer = no合计buy_computer = yes6954467000buy_computer = no41225883000合计736626341000054准确性、错误率、敏感度和特效性类不平衡问题 其中感兴趣的主类是稀少的，例如“欺诈” 正类多，负类少 灵敏性(召回率): 正

27、确识别的正元组的百分比,灵敏性 = TP/P 特效性:正确识别的负元组的百分比,特效性 = TN/N 准确率 =灵敏性P/(P+N)+特效性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 = y

28、es90（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%54保持方法, 随机二次抽样保持方法 给定的数据随机的划分为两个独立的集合 训练集，通常

29、2/3的数据被分配到训练集 检验集，通常1/3的数据被分配到检验集 随机二次抽样: 保持方法的变形将保持方法重复k次，总准确率估计取每次迭代准确率的平均值交叉验证(k-折交叉验证) 初始数据随机地划分成k个互不相关的子集，每个子集的大小大致相等 在第i次迭代, 分区 Di 用作检验集，其他区位训练集 留一: 每次只给检验集“留出”一个样本 分层交叉验证：折被分层，使的每个折中样本的类分布与在初始数据中的大致相同4254自助法自助法 处理较小的数据集合比较有效 从给定训练元组中有放回的均匀抽样 在有放回的抽样中，允许机器多次选择同一个元组43有多种自助方法, 最常用的一种是 .632 自助法 假

30、设给定的数据集包括d个元组。该数据集有放回地抽样d次，产生d个样本的自助样本集或训练集。结果是，在平均的情况下， 63.2% 的原数据元组将出现在自助样本中，而其余 36.8%的元组将形成检验54使用统计显著性检验选择模型假设已经由数据 产生了两个分类模型 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-折交叉验证 使用相同的交叉验证得到 err(M1)i and