大学精品课件：CHAPTER7-分类：基本概念.ppt

1、第一次作业n第二章：习题第二章：习题2.4(P53)和习题和习题2.8(P54)n第三章：习题第三章：习题3.3(P79)和习题和习题3.7(P80)n程序题：习题程序题：习题3.12(P80)，递交分析和检验报告和，递交分析和检验报告和 MATLAB源代码（加简单注释）文档。源代码（加简单注释）文档。n数据库下载地址：数据库下载地址：http:/archive.ics.uci.edu/ml/datasets/Iris2作业作业n课后习题：课后习题：6.6、6.8、6.14钱钱 峰峰通信与信息工程学院通信与信息工程学院2018年年第第7 7章章 分类分类4第第7章：分类：基本概念章：分类：基本

2、概念n 基本概念基本概念n 决策树归纳决策树归纳n 贝叶斯分类方法贝叶斯分类方法n 基于规则的分类基于规则的分类n 模型评估与选择模型评估与选择n 提高分类准确率的技术提高分类准确率的技术n 高级分类方法高级分类方法n 小结小结5有监督与无监督学习有监督与无监督学习n有监督学习有监督学习(分类分类)n监督：训练数据（观察，测量等）都带有标签监督：训练数据（观察，测量等）都带有标签,指示观察的类别指示观察的类别n根据训练集分类新数据根据训练集分类新数据n无监督学习无监督学习(聚类聚类)n训练集的类别（标签）未知训练集的类别（标签）未知n给定一个观察，测量等的集合，目标是建立数给定一个观察，测量等

3、的集合，目标是建立数据中存在的数据的类或簇据中存在的数据的类或簇6n分类分类n预测分类的预测分类的类标签类标签（离散（离散 or名义）名义）n基于训练数据和类标签基于训练数据和类标签 构造一个模型，并分类新数据构造一个模型，并分类新数据n数值预测数值预测 n建连续值函数建连续值函数/模型，预测未知模型，预测未知/缺失值缺失值 回归分析回归分析n典型应用典型应用n信用卡信用卡/贷款审批：信用是否良好？贷款审批：信用是否良好？n医疗诊断：肿瘤是癌或良性？医疗诊断：肿瘤是癌或良性？n欺诈检测：交易欺诈欺诈检测：交易欺诈?n网页分类：这是哪一类？网页分类：这是哪一类？预测问题：预测问题：分类与数值预测

4、分类与数值预测7分类分类:一个两步的过程一个两步的过程n模型构建模型构建:描述一组预先定义的类描述一组预先定义的类n假定每个元组假定每个元组/样本样本 属于一个类属于一个类,由由类标号属性类标号属性设定设定n用于构建模型的元组集合称为训练元组用于构建模型的元组集合称为训练元组n模型可以表示为分类规则模型可以表示为分类规则,决策树决策树,数学公式数学公式n模型使用模型使用:分类将来分类将来/未知对象未知对象n估计模型的准确率估计模型的准确率n测试集：测试集：独立于训练集的样本独立于训练集的样本（避免过分拟合（避免过分拟合 overfitting）n比较测试样本的已知标号比较测试样本的已知标号/由

5、模型预测（得到）标号由模型预测（得到）标号n准确率：准确率：测试样本集中模型正确预测测试样本集中模型正确预测/分类的样本的比分类的样本的比n如果准确率合适如果准确率合适,使用模型来分类标号为未知的样本使用模型来分类标号为未知的样本8模型构建模型构建TrainingDataClassificationAlgorithmsIF rank=professorOR years 6THEN tenured=yes Classifier(Model)9利用模型进行预测利用模型进行预测ClassifierTestingDataUnseen Data(Jeff,Professor,4)Tenured?10第第

6、7章：分类：基本概念章：分类：基本概念n 基本概念基本概念n 决策树归纳决策树归纳n 贝叶斯分类方法贝叶斯分类方法n 基于规则的分类基于规则的分类n 模型评估与选择模型评估与选择n 提高分类准确率的技术提高分类准确率的技术n 小结小结11决策树归纳决策树归纳:例子例子age?student?credit rating?40noyesyesyes3140nofairexcellentyesnoq决策树：类似于流程图的树结构决策树：类似于流程图的树结构q训练集训练集:购买计算机购买计算机内部节点：内部节点：一个属性上的测试一个属性上的测试分枝：分枝：测试的一个输出（样本子集）测试的一个输出（样本子

7、集）叶节点：叶节点：类标签（用数据子集代表）类标签（用数据子集代表）12决策树归纳的算法决策树归纳的算法n基本算法基本算法(贪心算法贪心算法)：根据每个属性，递归的对样本集进行划分根据每个属性，递归的对样本集进行划分n树构建：自顶向下递归地分治方式树构建：自顶向下递归地分治方式n开始，所有的训练样本位于根节点开始，所有的训练样本位于根节点n属性是分类属性属性是分类属性(若是连续值若是连续值,事先离散化事先离散化)n基于选择的属性，样本被递归地分割（分割为子集）基于选择的属性，样本被递归地分割（分割为子集）n基于启发式基于启发式/统计测来选择统计测来选择测试属性测试属性（例如（例如 信息增益）信

8、息增益）n终止划分的条件终止划分的条件n一个给定节点的所有样本属于一个类别一个给定节点的所有样本属于一个类别n没有属性剩下（运用多数投票来标记此节点）没有属性剩下（运用多数投票来标记此节点）n没有样本剩下没有样本剩下qP215，图，图8.3属性选择度量属性选择度量n属性选择度量属性选择度量n分裂规则，决定给定节点上的元组如何分裂分裂规则，决定给定节点上的元组如何分裂n具有最好度量得分的属性选定位分裂属性具有最好度量得分的属性选定位分裂属性n三种度量三种度量n信息增益、增益率、信息增益、增益率、Gini指标指标n数学符号数学符号nD为元组的训练集，元组属于为元组的训练集，元组属于m个不同的类个不

9、同的类Ci(i=1m)nCi,D是是D中的中的Ci类的元组集合类的元组集合n|Ci,D|和和|D|分别表示各自的元组个数分别表示各自的元组个数15n选择具有最高信息增益的属性选择具有最高信息增益的属性n令令 pi 为为D中的任一元组属于类中的任一元组属于类 Ci概率概率,估计为估计为|Ci,D|/|D|n分类分类D中元组需要的中元组需要的期望信息期望信息(entropy):n(利用利用 A 分裂分裂D 为为v个部分后个部分后)分类分类D 需要的信息为需要的信息为:n以属性以属性A分枝得到的信息增益分枝得到的信息增益)(log)(21imiippDInfo)(|)(1jvjjADInfoDDDI

10、nfo)()()(DInfoDInfoAGainA属性选择度量属性选择度量:信息增益信息增益(ID3/C4.5)16gClass P:买电脑买电脑=“yes”gClass N:买电脑买电脑=“no”048.0)_(151.0)(029.0)(ratingcreditGainstudentGainincomeGain246.0)()()(DInfoDInfoageGainage940.0)145(log145)149(log149)(22DInfo属性选择属性选择:信息增益信息增益17计算信息增益计算信息增益-连续值属性连续值属性n令令 A 为连续属性为连续属性n必须为必须为A确定一个最佳分裂点

11、确定一个最佳分裂点 best split pointn上升序排序上升序排序 A n典型地典型地,每对相邻值的中点是一个可能的分裂点每对相邻值的中点是一个可能的分裂点n(ai+ai+1)/2是是ai与与ai+1的的中点中点n具有最小期望信息需求的点选为具有最小期望信息需求的点选为A的分裂点的分裂点nSplit:nD1为为D中元组满足中元组满足A split-point,D2 是元组满足是元组满足Asplit-point18增益率增益率(C4.5)n信息增益倾向于有大量不同取值的属性（划分更细，更纯）信息增益倾向于有大量不同取值的属性（划分更细，更纯）n极端：每个划分子集只有一个样本，即一个类极端

12、：每个划分子集只有一个样本，即一个类n此时此时Info(d)=0 nC4.5(ID3 后继后继)使用增益率来克服这一问题使用增益率来克服这一问题(规范化信息增益规范化信息增益)nGainRatio(A)=Gain(A)/SplitInfo(A)nEx.ngain_ratio(income)=0.029/1.557=0.019n具有最大增益率的属性选为分裂属性具有最大增益率的属性选为分裂属性)|(log|)(21DDDDDSplitInfojvjjA19基尼指数基尼指数Gini Indexn数据数据 D 包含包含n 类别的样本类别的样本,gini指标指标,gini(D)定义为定义为:pj 为类别

13、为类别j在在D中的频率中的频率n数据集数据集 D 基于属性基于属性A 分裂为子集分裂为子集 D1 和和 D2,gini 指标定义为指标定义为n不纯度减少不纯度减少:n具有最小具有最小ginisplit(D)的属性的属性(or不纯度减少最大的不纯度减少最大的)用于分裂用于分裂节点节点(需要枚举所有可能的分裂情况需要枚举所有可能的分裂情况)(|)(|)(2211DginiDDDginiDDDginiA)()()(DginiDginiAginiA21()1njjgini Dp 20计算计算Gini Index指标指标nD 有有 9个元组买电脑个元组买电脑=“yes”/5 个买电脑个买电脑=“no”n

14、设属性设属性income分裂分裂D为包含为包含10个元组的个元组的D1:low,medium/4个个元组的元组的D2Ginilow,high=0.458;Ginimedium,high=0.450.因此因此low,medium/high分裂，分裂，由于其有最小的由于其有最小的Gini indexn假设所有属性都是连续值，需要其他技术假设所有属性都是连续值，需要其他技术,e.g.,聚类聚类,来获得可来获得可能的分裂点能的分裂点459.01451491)(22Dgini21比较属性选择度量比较属性选择度量n通常三种度量获得较好的结果通常三种度量获得较好的结果n信息增益信息增益Information

15、 gain:n偏向于多值属性偏向于多值属性n增益率增益率Gain ratio:n倾向于不平衡的分裂，其中一个子集比其他小得多倾向于不平衡的分裂，其中一个子集比其他小得多nGini index:n偏向于多值属性偏向于多值属性n当类数目较大时，计算困难当类数目较大时，计算困难n倾向于导致大小相等的分区和纯度倾向于导致大小相等的分区和纯度22其他属性选择度量其他属性选择度量nCHAID:一种流行的决策树算法一种流行的决策树算法,基于独立基于独立 2 检验的选择度量检验的选择度量nC-SEP:某些情况下比信息增益某些情况下比信息增益gini指标更好指标更好nG-statistic:非常近似于非常近似于

16、 2 分布分布nMDL(最小描述长度最小描述长度)(i.e.,首选最简单的解首选最简单的解):n最佳树为需要最小二进位的树最佳树为需要最小二进位的树(1)编码树编码树,(2)编码树的异常编码树的异常n多元划分多元划分(基于多变量组合来划分基于多变量组合来划分)nCART:基于属性的线性组合来发现多元划分基于属性的线性组合来发现多元划分n哪一个是最好的哪一个是最好的?n 大部分可以获得较好结果大部分可以获得较好结果,没有一个显著地优于其他没有一个显著地优于其他23过拟合与数剪枝过拟合与数剪枝n过拟合过拟合Overfitting:一棵归纳的树一棵归纳的树 可能过分拟合训练数据可能过分拟合训练数据n

17、分枝太多分枝太多,某些反映训练数据中的异常，噪音某些反映训练数据中的异常，噪音/孤立点孤立点n对未参与训练的样本的低精度预测对未参与训练的样本的低精度预测n两种处理方法两种处理方法 n先剪枝先剪枝:提前终止树构造提前终止树构造 n如果对一个节点的分裂产生低于给定的阈值的度量，划分停止如果对一个节点的分裂产生低于给定的阈值的度量，划分停止n选择一个合适的阈值很难选择一个合适的阈值很难n后剪枝后剪枝:从完全生长的树中剪去树枝从完全生长的树中剪去树枝得到逐步修剪树得到逐步修剪树n例如，最小化代价复杂度（树节点个数和错误率的函数）例如，最小化代价复杂度（树节点个数和错误率的函数）n使用不同于训练集的数

18、据来确定哪一个是使用不同于训练集的数据来确定哪一个是“best pruned tree”24决策树归纳的增强决策树归纳的增强n允许连续值属性允许连续值属性n动态地定义新的离散值属性，其把连续值属性分成离散动态地定义新的离散值属性，其把连续值属性分成离散的区间的区间n处理缺失属性值处理缺失属性值n分配属性的最常见值分配属性的最常见值n为每一个可能的值分配概率为每一个可能的值分配概率n属性构造属性构造n基于现有的稀少出现的属性创建新的属性，基于现有的稀少出现的属性创建新的属性，n这减少了分散，重复和复制这减少了分散，重复和复制25大型数据库中分类大型数据库中分类n分类分类被统计学和机器学习研究人员

19、广泛地研究的经典问题被统计学和机器学习研究人员广泛地研究的经典问题n可伸缩性可伸缩性:以合理的速度分类由带有数百个属性的百万个样本以合理的速度分类由带有数百个属性的百万个样本组成的数据集组成的数据集n为什么决策树归纳受欢迎？为什么决策树归纳受欢迎？n相对快的训练速度相对快的训练速度(与其他分类方法相比与其他分类方法相比)n转换为简单、易于理解的分类规则转换为简单、易于理解的分类规则n可用可用 SQL查询来访问数据库查询来访问数据库n与其它方法可比的分类精度与其它方法可比的分类精度nRainForest(VLDB98 Gehrke,Ramakrishnan&Ganti)nBuilds an AV

20、C-list(attribute,value,class label)26雨林（雨林（RainForest）的可扩展性框架）的可扩展性框架n在决策树的每个节点，对于每个属性建立并维持在决策树的每个节点，对于每个属性建立并维持 AVC-list:AVC(属性属性-值值,类标号类标号)nAVC集集(of an attribute X)n把训练样本集投影到属性把训练样本集投影到属性X和类标签上，给出属性和类标签上，给出属性X的每的每个值上的类标签计数个值上的类标签计数nAVC组群组群 (在节点在节点n)n节点节点n上所有预测属性的上所有预测属性的AVC集合集合组群组群 27Rainforest:训练

21、集和训练集和AVC集集 studentBuy_Computeryesnoyes61no34AgeBuy_Computeryesno4032CreditratingBuy_Computeryesnofair62excellent33AVC-set on incomeAVC-set on AgeAVC-set on StudentTraining ExamplesincomeBuy_Computeryesnohigh22medium42low31AVC-set on credit_rating28自助乐观算法自助乐观算法(BOAT：Bootstrapped Optimistic Algorithm

22、 for Tree Construction)n使用一个叫做使用一个叫做 bootstrapping自助法的统计技术多个自助法的统计技术多个更小的样本集（子集）更小的样本集（子集）,每一个可放入内存每一个可放入内存n每个子集产生一个树每个子集产生一个树,导致多个树导致多个树 n考察这些树并用他们构造一个新树考察这些树并用他们构造一个新树Tn事实证明事实证明，T 非常接近于使用全部数据集构造的树非常接近于使用全部数据集构造的树nAdv:只要求扫描只要求扫描DB两遍，并且是一个两遍，并且是一个增量算法增量算法Data Mining:Concepts and Techniques29Interact

23、ive Visual Mining by Perception-Based Classification(PBC)2023年3月1日星期三Data Mining:Concepts and Techniques30分类结果的陈述/表示2023年3月1日星期三Data Mining:Concepts and Techniques31决策树可视化SGI/MineSet 3.0SGI公司和美国公司和美国Standford大学联合开发的多大学联合开发的多任务任务数据挖掘数据挖掘系统。系统。MineSet以先进的可视化显示方法闻名于世以先进的可视化显示方法闻名于世 32第第7章：分类：基本概念章：分类：基

24、本概念n 基本概念基本概念n 决策树归纳决策树归纳n 贝叶斯分类方法贝叶斯分类方法n 基于规则的分类基于规则的分类n 模型评估与选择模型评估与选择n 提高分类准确率的技术提高分类准确率的技术n 小结小结33贝叶斯理论贝叶斯理论n令令X 为数据元组：类标签未知为数据元组：类标签未知n令令H为一个假设在：为一个假设在：X属于类别属于类别 C n分类就是确定分类就是确定 P(H|X)(后验概率后验概率)n给定观察数据给定观察数据 X，假设，假设H成立的概率成立的概率nP(H)(先验概率先验概率)最初的概率最初的概率n例例,不管年龄和收入等条件不管年龄和收入等条件 X将会购买计算机将会购买计算机nP(

25、X)：数据元组：数据元组X被观察到的概率被观察到的概率nP(X|H)(可能性可能性)n假设假设H成立，那么观测到样本成立，那么观测到样本X的概率的概率nE.g.,已知已知X购买计算机，购买计算机，X 为为31.40且中等收入的概率且中等收入的概率34贝叶斯理论（贝叶斯理论（Bayesian Theorem）n给定训练数据给定训练数据 X,假设假设H的后验概率的后验概率 P(H|X)满足贝叶斯理论满足贝叶斯理论n预测预测X属于类别属于类别Ci当且仅当概率当且仅当概率P(Ci|X)是所有是所有P(Ck|X)for all the k classes最大的最大的n实际困难：需要许多可能性的初步知识，

26、计算成本显著实际困难：需要许多可能性的初步知识，计算成本显著)(/)()|()()()|()|(XXXXXPHPHPPHPHPHP35朴素贝叶斯（朴素贝叶斯（Nave Bayesian）分类）分类nD为训练数据集（包含类别标签）为训练数据集（包含类别标签）,并且每个元组表示为一并且每个元组表示为一个个n-维的属性向量维的属性向量X=(x1,x2,xn)n假定有假定有 m 个类别个类别 C1,C2,Cmn分类就是推导最大的后验概率分类就是推导最大的后验概率,i.e.,the maximal P(Ci|X)，可以由贝叶斯理论计算可以由贝叶斯理论计算n由于对所有类由于对所有类P(X)是常量，只需要最

27、大化是常量，只需要最大化)()()|()|(XXXPCPCPCPiii)()|()|(iiiCPCPCPXX36朴素贝叶斯分类器的推导朴素贝叶斯分类器的推导n一个简单假定一个简单假定:属性之间相互独立属性之间相互独立n优点：极大地减少了计算代价，只需要统计类的分布优点：极大地减少了计算代价，只需要统计类的分布n若若Ak 是分类属性是分类属性nP(xk|Ci)=Ci 类中类中Ak取值为取值为xk 的元组数的元组数/|Ci,D|(类类Ci 的大小的大小)n若若Ak是连续值是连续值n假设假设xk服从均值服从均值 标准差标准差 的高斯分布的高斯分布)|(.)|()|()|()|(211CxPCxPCx

28、PCxPCPikiinkikiX222)(21),(xexg),()|(iiCCkxgCiPX37朴素贝叶斯分类朴素贝叶斯分类:训练数据集训练数据集两个类别:C1:buys_computer=yesC2:buys_computer=no数据样本 X=(age=30,Income=medium,Student=yesCredit_rating=Fair)38Nave Bayesian Classifier:例子例子nP(Ci):P(buys_computer=“yes”)=9/14=0.643 P(buys_computer=“no”)=5/14=0.357nCompute P(X|Ci)for

29、 each class P(age=“=30”|buys_computer=“yes”)=2/9=0.222 P(age=“=30”|buys_computer=“no”)=3/5=0.6 P(income=“medium”|buys_computer=“yes”)=4/9=0.444 P(income=“medium”|buys_computer=“no”)=2/5=0.4 P(student=“yes”|buys_computer=“yes)=6/9=0.667 P(student=“yes”|buys_computer=“no”)=1/5=0.2 P(credit_rating=“fai

30、r”|buys_computer=“yes”)=6/9=0.667 P(credit_rating=“fair”|buys_computer=“no”)=2/5=0.4n X=(age=30,income=medium,student=yes,credit_rating=fair)P(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.019P(X|Ci)*P(Ci):P(X|buys_computer=“yes”)*

31、P(buys_computer=“yes”)=0.028 P(X|buys_computer=“no”)*P(buys_computer=“no”)=0.007Therefore,X belongs to class(“buys_computer=yes”)39避免零概率问题避免零概率问题n朴素贝叶斯要求每个条件概率非零.然而,预测的概率可能为零nEx.假定有1000 元组,e=low(0),income=medium(990),and income=high(10)nUse Laplacian correction校准校准(or Laplacian estimator估计法)nAdding

32、1 to each caseProb(income=low)=1/1003Prob(income=medium)=991/1003Prob(income=high)=11/1003n校准的“corrected”概率估计很接近未校准的nkikiCxPCXP1)|()|(40Nave Bayesian Classifier:评论评论 n优点：优点：n分类过程容易执行分类过程容易执行 n在很多情况下都能获得较好的分类效果在很多情况下都能获得较好的分类效果n缺点：缺点：n类条件独立性，损失精度类条件独立性，损失精度n实际中，变量间存在依赖实际中，变量间存在依赖 nE.g.,医院：患者：简介：年龄，家族

33、病史等医院：患者：简介：年龄，家族病史等症状：发烧，咳嗽等疾病：肺癌，糖尿病等症状：发烧，咳嗽等疾病：肺癌，糖尿病等 n上述属性之间的关系无法用独立性描述上述属性之间的关系无法用独立性描述n解决方案：解决方案：nBayesian Belief Networks41第第7章：分类：基本概念章：分类：基本概念n 基本概念基本概念n 决策树归纳决策树归纳n 贝叶斯分类方法贝叶斯分类方法n 基于规则的分类基于规则的分类n 模型评估与选择模型评估与选择n 提高分类准确率的技术提高分类准确率的技术n 小结小结42使用使用IF-THEN 规则分类规则分类n使用使用 IF-THEN 规则表示知识：规则表示知识

34、：nR：IF age=youth AND student=yes THEN buys_computer=yesn规则前件（前提）与规则结论（后件）规则前件（前提）与规则结论（后件）n规则评估：覆盖率（规则评估：覆盖率（coverage）与准确率（）与准确率（accuracy）nncovers=规则规则R覆盖覆盖的元组数的元组数 nncorrect=R正确分类的元组数正确分类的元组数ncoverage(R)=ncovers/|D|D:训练数据集训练数据集naccuracy(R)=ncorrect/ncovers43n需解决的问题：如果超过需解决的问题：如果超过1条规则被触发，需要解决条规则被触发

35、，需要解决冲突冲突n规模序规模序Size ordering:最高优先权赋予最高优先权赋予“最苛刻最苛刻”的规的规则（即则（即,最多属性测试）最多属性测试）n基于类的序：每个类的错误分类代价的下降序基于类的序：每个类的错误分类代价的下降序n基于规则的序（决策表）：根据一些规则的质量度量或基于规则的序（决策表）：根据一些规则的质量度量或由专家建议，规则被组织成一个长的优先级列表由专家建议，规则被组织成一个长的优先级列表n若所有规则都不满足若所有规则都不满足设置默认规则设置默认规则使用使用IF-THEN 规则分类规则分类44从决策树提取规则从决策树提取规则n规则比一棵大的决策树更容易理解规则比一棵大

36、的决策树更容易理解n从根到每个叶子的路径产生一个规则从根到每个叶子的路径产生一个规则n沿路径的每个属性值对一起形成了一个联合沿路径的每个属性值对一起形成了一个联合:叶节叶节点形成规则后件点形成规则后件 n规则是规则是互斥的互斥的和和穷举的穷举的n没有冲突规则，每个元组被覆盖没有冲突规则，每个元组被覆盖45nExample:Rule extraction from our buys_computer decision-treeIF age=young AND student=no THEN buys_computer=noIF age=young AND student=yes THEN buy

37、s_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=yes从决策树提取规则从决策树提取规则age?student?credit rating?40noyesyesyes3140nofairexcellentyesno46n顺序覆盖算法顺序覆盖算法:n直接从训练数据抽取规则，顺序学习直接从训练数据抽取规则，顺序学习n典型的算

38、法典型的算法:nFOIL,AQ,CN2,RIPPERn规则判断准则：规则判断准则：n类类Ci的规则尽量覆盖的规则尽量覆盖Ci 的元组，不或少覆盖其他类元组的元组，不或少覆盖其他类元组顺序覆盖算法的规则归纳顺序覆盖算法的规则归纳 47n基本步骤基本步骤:n一次学习一个规则一次学习一个规则n每学习一个规则，删除此规则覆盖的元组每学习一个规则，删除此规则覆盖的元组n对剩下的元组重复该过程直到终止条件（对剩下的元组重复该过程直到终止条件（e.g.,没有训练没有训练样本样本/返回的规则的质量低于用户给定的阈值）返回的规则的质量低于用户给定的阈值）n与决策树对照：与决策树对照：n构建决策树，同时学习一组规

39、则构建决策树，同时学习一组规则顺序覆盖算法的规则归纳顺序覆盖算法的规则归纳 48while(enough target tuples left)generate a ruleremove positive target tuples satisfying this ruleExamples coveredby Rule 3Examples coveredby Rule 2Examples coveredby Rule 1Positive examples顺序覆盖算法的规则归纳顺序覆盖算法的规则归纳 Positive examples（正元组）：用于学习规则的（正元组）：用于学习规则的类的类的元

40、组，其元组，其余的为负元组余的为负元组49规则产生规则产生nTo generate a rule（利用度量判断规则的质量）（利用度量判断规则的质量）while(true)find the best predicate pif foil-gain(p)threshold then add p to current ruleelse breakPositive examplesNegative examplesA3=1A3=1&A1=2A3=1&A1=2&A8=5顺序覆盖算法顺序覆盖算法规则学习步骤规则学习步骤n从可能的最一般的规则开始：从可能的最一般的规则开始：condition=emptyn采

41、用贪心的深度优先策略添加新属性到规则中采用贪心的深度优先策略添加新属性到规则中n选择对选择对“规则质量规则质量”提高最大的那个属性提高最大的那个属性52规则质量度量与剪枝规则质量度量与剪枝n规则质量度量：同时考虑覆盖率和准确率规则质量度量：同时考虑覆盖率和准确率nFOIL-Gain：评价扩展条件的：评价扩展条件的info_gainnFOIL：一阶归纳学习器一阶归纳学习器npos(neg)：规则覆盖的正（负）元组数：规则覆盖的正（负）元组数n偏向于具有高准确率并覆盖许多正元组的规则偏向于具有高准确率并覆盖许多正元组的规则n基于独立测试集进行规则剪枝，即删除一个属性测试基于独立测试集进行规则剪枝，

42、即删除一个属性测试)log(log_22negposposnegposposposGainFOILnegposnegposRPruneFOIL)(_53第第7章：分类：基本概念章：分类：基本概念n 基本概念基本概念n 决策树归纳决策树归纳n 贝叶斯分类方法贝叶斯分类方法n 基于规则的分类基于规则的分类n 模型评估与选择模型评估与选择n 提高分类准确率的技术提高分类准确率的技术n 小结小结模型评价与选择模型评价与选择n评价指标评价指标:怎样度量准确率怎样度量准确率?n使用测试集（带标签）代替训练集评估准确度使用测试集（带标签）代替训练集评估准确度n估计分类器准确率的方法估计分类器准确率的方法:n

43、保持保持n随机二次抽样随机二次抽样n交叉验证交叉验证Cross-validationn自助法自助法Bootstrapn分类器比较：比较分类器的准确率之差是否偶然分类器比较：比较分类器的准确率之差是否偶然n置信区间置信区间n代价效益分析和代价效益分析和ROC曲线曲线54分类器评价指标分类器评价指标:混淆矩阵混淆矩阵实际类实际类预测类预测类buy_computer=yesbuy_computer=noTotalbuy_computer=yes6954467000buy_computer=no41225883000Total7366263410000n感兴趣的类定为感兴趣的类定为“正类正类”或或“阳

44、性类阳性类”，反之则为，反之则为“负负/阴性类阴性类”n正样本正样本/负样本负样本 n可以提供额外的行可以提供额外的行/列提供列提供“合计合计”和和“识别率识别率”混淆矩阵混淆矩阵Confusion Matrix:实际类实际类预测类预测类C1C1C1True Positives(TP)False Negatives(FN)C1False Positives(FP)True Negatives(TN)55分类器评价指标分类器评价指标:准确度准确度,误差率误差率,灵敏性灵敏性,特效性特效性n分类器准确度或分类器准确度或识别率:测试元组被正确识别的比例Accuracy=(TP+TN)/Alln误差率

45、误差率:1Accuracy，orError rate=(FP+FN)/Alln类分布不平衡问题类分布不平衡问题：感兴趣主类是稀少的，比如：欺诈,或者HIV阳性n敏感度敏感度:真正例识别率Sensitivity=TP/Pn特效性特效性:正确识别负元组的识别率Specificity=TN/NAPCCCTPFNPCFPTNNPNAll56分类器评价指标分类器评价指标:精度精度、召回、召回、F度量度量nPrecision：正确被分类器标记为正类的样本中实际上属于“正类”的比例nRecall：正元组标记为正的百分比（精度和召回率逆关系）nF measure(F1 or F-score)：精度和召回的调和

46、平均值nF:精确度和召回率的加权量nAssigns times as much weight to recall as to precision57分类器评价指标分类器评价指标:例子例子58Precision=90/230=39.13%Recall=90/300=30.00%真实类预测类cancer=yescancer=noTotalRecognition(%)cancer=yes9021030030.00(sensitivity)cancer=no1409560970098.56(specificity)Total23097701000096.40(accuracy)评测分类器的正确率评测分

47、类器的正确率:Holdout&Cross-Validation Methodsn保持方法保持方法n给定数据随机分成两个部分给定数据随机分成两个部分n训练集训练集(e.g.,2/3)用于模型构造用于模型构造n测试集测试集(e.g.,1/3)用于正确率估计用于正确率估计n随机二次抽样随机二次抽样:a variation of holdoutn重复保持方法重复保持方法k次，次，accuracy=所有正确率的平均值所有正确率的平均值n交叉验证交叉验证(k-fold,k=10最常用最常用)n随机分割数据为随机分割数据为k互不相交的子集，每一个大小近似相等；在互不相交的子集，每一个大小近似相等；在i-th

48、 迭迭代中，使用代中，使用Di 为测试集其他的为训练集为测试集其他的为训练集n留一法：留一法：k 设置为原始样本数设置为原始样本数n分层交叉验证：分层交叉验证：每个部分分层使得每个子集中类分布近似原始数据每个部分分层使得每个子集中类分布近似原始数据59评测分类器的正确率评测分类器的正确率:自助法自助法n自助法（自助法（boostrap）n从给定样本中从给定样本中有放回有放回的均匀抽样：每次一个样本被选中的均匀抽样：每次一个样本被选中,把它把它加入训练集并且等可能得被再次选中加入训练集并且等可能得被再次选中n对于小样本数据，效果很好对于小样本数据，效果很好n多个自助法（最常用的是多个自助法（最常

49、用的是.632）n含含d个样本的数据集有放回抽样个样本的数据集有放回抽样d次，产生次，产生d个样本的训练集，个样本的训练集，没有被抽到的样本组成测试集没有被抽到的样本组成测试集.n大约大约63.2%的样本被抽中，剩余的的样本被抽中，剩余的36.8%形成测试集形成测试集(1 1/d)d e-1=0.368n重复抽样过程重复抽样过程k 次次,总体准确率为：总体准确率为：60估计置信区间估计置信区间:分类器分类器 M1 vs.M2n假定有两个分类器 M1 and M2,那一个更好?n用10折交叉验证获得了n这些平均误差率仅是未来数据总体误差的一种估计n2个错误率之间差别如果是否是偶然的？n使用统计显

50、著性检验统计显著性检验 n获得估计误差的置信界（置信界（confidence limits）61估计置信区间估计置信区间:原假设原假设(null hypothesis)n执行10折交叉验证n假定样本服从k1个自由度的t分布(k=10)，利用t-test(or students t-test)n原假设：原假设：M1&M2 相同（即没有区别）n如果可以拒绝原假设原假设n可以断定M1&M2 间的不同是统计上显著的n选择具有较低错误率的模型62估计置信区间估计置信区间:t-检验检验n当只有一个测试集时当只有一个测试集时:成对比较成对比较n对于对于10倍交叉验证中第倍交叉验证中第i次次,使用相同的样本分