《知识发现与机器学习.ppt》由会员分享,可在线阅读,更多相关《知识发现与机器学习.ppt(86页珍藏版)》请在金锄头文库上搜索。
1、21 八月 2024DMKD Sides By MAO1第三章第三章 分类方法分类方法 内容提要内容提要n分类的基本概念与步骤 n基于距离的分类算法 n决策树分类方法 n贝叶斯分类 n规则归纳 n与分类有关的问题 21 八月 2024DMKD Sides By MAO2分类是数据挖掘中重要的任务 n分类的目的是学会一个分类器(分类函数或模型),该分类器能把待分类的数据映射到给定的类别中。n分类可用于预测。从利用历史数据纪录中自动推导出对给定数据的推广描述,从而能对未来数据进行类预测。n分类具有广泛的应用,例如医疗诊断、信用卡系统的信用分级、图像模式识别等。n分类器的构造依据的方法很广泛:n统计
2、方法:包括贝叶斯法和非参数法等。n机器学习方法:包括决策树法和规则归纳法。n神经网络方法。n其他,如粗糙集等(在前面绪论中也介绍了相关的情况)。21 八月 2024DMKD Sides By MAO3分类方法的类型n从使用的主要技术上看,可以把分类方法归结为四种类型:n基于距离的分类方法n决策树分类方法n贝叶斯分类方法n规则归纳方法。n本章将择选一些有代表性的方法和算法来介绍这四类分类方法。21 八月 2024DMKD Sides By MAO4分类问题的描述n定定义4-1 给定一个数据库D=t1,t2,tn和一组类C=C1,Cm,分类问题是去确定一个映射f: DC,使得每个元组ti被分配到一
3、个类中。一个类Cj 包含映射到该类中的所有元组,即Cj = ti | f(ti) = Cj,1 i n,而且ti D。n例如,把学生的百分制分数分成A、B、C、D、F五类,就是一个分类问题:D是包含百分制分数在内的学生信息,C=A、B、C、D、F。n解决分类问题的关键是构造一个合适的分类器:从数据库到一组类别集的映射。一般地,这些类是被预先定义的、非交叠的。21 八月 2024DMKD Sides By MAO5数据分类的两个步骤1建立一个模型,描述建立一个模型,描述预定的数据定的数据类集或概念集集或概念集n数据元组也称作样本、实例或对象。n为建立模型而被分析的数据元组形成训练数据集。n训练数
4、据集中的单个元组称作训练样本,由于提供了每个训练样本的类标号,因此也称作有指导的学习。n通过分析训练数据集来构造分类模型,可用分类规则、决策树或数学公式等形式提供。n2使用模型使用模型进行分行分类n首先评估模型(分类法)的预测准确率。n如果认为模型的准确率可以接受,就可以用它对类标号未知的数据元组或对象进行分类。21 八月 2024DMKD Sides By MAO6第三章第三章 分类方法分类方法 内容提要内容提要n分类的基本概念与步骤 n基于距离的分类算法 n决策树分类方法 n贝叶斯分类 n规则归纳 n与分类有关的问题 21 八月 2024DMKD Sides By MAO7基于距离的分类算
5、法的思路n定定义4-2 给定一个数据定一个数据库 D=t1,t2,tn和一和一组类C=C1,Cm。假定每个元。假定每个元组包括一些数包括一些数值型的属性型的属性值:ti=ti1,ti2,tik,每个,每个类也包也包含数含数值性属性性属性值:Cj=Cj1,Cj2,Cjk,则分分类问题是要分配每个是要分配每个ti到到满足如下条件的足如下条件的类Cj:simsim( (t ti i,C Cj j)=)=simsim( (t ti i,C Cl l) ) , C Cl lC C,C Cl lC Cj j,其中其中sim(ti,Cj)被称被称为相似性。相似性。n在在实际的的计算中往往用算中往往用距离距离
6、来表征,距离越近,来表征,距离越近,相似性越大,距离越相似性越大,距离越远,相似性越小。,相似性越小。n距离的距离的计算方法有多种,最常用的是通算方法有多种,最常用的是通过计算每算每个个类的中心来完成。的中心来完成。21 八月 2024DMKD Sides By MAO8 基于距离的分类算法的一般性描述n算法4-1通过对每个元组和各个类的中心来比较,从而可以找出他的最近的类中心,得到确定的类别标记。算法算法4-1基于距离的分类算法输入:每个类的中心C1,Cm;待分类的元组t。 输出:输出类别c。 (1)dist=;/距离初始化(2)FOR i:=1 to m DO (3) IF dis(ci,
7、t)dist THEN BEGIN(4)c i; (5)distdist(ci,t); (6) END.21 八月 2024DMKD Sides By MAO9基于距离的分类方法的直观解释(a)类定义(b)待分类样例(c)分类结果21 八月 2024DMKD Sides By MAO10K-近邻分类算法nK-近邻分类算法(K Nearest Neighbors,简称KNN)通过计算每个训练数据到待分类元组的距离,取和待分类元组距离最近的K个训练数据,K个数据中哪个类别的训练数据占多数,则待分类元组就属于哪个类别。算法算法4-2K-近邻分类算法输入: 训练数据T;近邻数目K;待分类的元组t。 输
8、出: 输出类别c。 (1)N=;(2)FOR each d T DO BEGIN(3) IF |N|K THEN(4) N=Nd; (5) ELSE(6) IF u N such that sim(t,u)sim(t,d) THEN BEGIN (7) N=N-u;(8) N=Nd;(9) END(10)END(11)c=class to which the most uN. 21 八月 2024DMKD Sides By MAO11KNN的例子姓名性别 身高(米)类别Kristina女 1.6矮Jim男 2高Maggie女 1.9中等Martha女 1.88中等Stephanie女 1.7矮
9、Bob男 1.85中等Kathy女 1.6矮Dave男 1.7矮Worth男 2.2高Steven男 2.1高Debbie女 1.8中等Todd男 1.95中等Kim女 1.9中等Amy女 1.8中等Wynette女 1.75中等“高度”用于计算距离,K=5,对分类。 对T前K=5个记录,N=、和。对第6个记录d=,得到N=、和。对第7个记录d=,得到N=、和。对第8个记录d=,得到N=、和。对第9和10个记录,没变化。对第11个记录d=,得到N=、和。对第12到14个记录,没变化。对第15个记录d=,得到N=、和。 最后的输出元组是、和。在这五项中,四个属于矮个、一个属于中等。最终KNN方法
10、认为Pat为矮个。 。21 八月 2024DMKD Sides By MAO12第三章第三章 分类方法分类方法 内容提要内容提要n分类的基本概念与步骤 n基于距离的分类算法 n决策树分类方法 n贝叶斯分类 n规则归纳 n与分类有关的问题 21 八月 2024DMKD Sides By MAO13决策树表示与例子n决策树(Decision Tree)的每个内部结点表示在一个属性上的测试,每个分枝代表一个测试输出,而每个树叶结点代表类或类分布。树的最顶层结点是根结点。nbuys_computer的决策树示意21 八月 2024DMKD Sides By MAO14决策树分类的特点n决策树分类方法采
11、用自顶向下的递归方式,在决策树的内部结点进行属性值的比较并根据不同的属性值判断从该结点向下的分枝,在决策树的叶结点得到结论。所以从决策树的根到叶结点的一条路径就对应着一条合取规则,整棵决策树就对应着一组析取表达式规则。n基于决策树的分类算法的一个最大的优点就是它在学习过程中不需要使用者了解很多背景知识(这同时也是它的最大的缺点),只要训练例子能够用属性-结论式表示出来,就能使用该算法来学习。n决策树分类模型的建立通常分为两个步骤:n决策树生成n决策树修剪。21 八月 2024DMKD Sides By MAO15决策树生成算法描述n构造好的决策树的关键在于如何选择好的属性进行树的拓展。研究结果
12、表明,一般情况下或具有较大概率地说,树越小则树的预测能力越强。由于构造最小的树是NP-难问题,因此只能采取用启发式策略来进行。n属性选择依赖于各种对例子子集的不纯度(Impurity)度量方法,包括信息增益(Informatin Gain)、信息增益比(Gain Ratio)、Gini-index、距离度量(Distance Measure)、J-measure、G统计、2统计、证据权重(Weight of Evidence)、最小描述长度(MLP)、正交法(Ortogonality Measure)、相关度(Relevance)和Relief等。算法算法4-3Generate_decisio
13、n_tree(samples, attribute_list) /*决策树生成算法*/输入:训练样本samples,由离散值属性表示;候选属性的集合attribute_list。输出:一棵决策树。(1) 创建结点N;(2) IF samples 都在同一个类C THEN 返回N 作为叶结点,以类 C标记;(3) IF attribute_list为空 THEN 返回N作为叶结点,标记为samples中最普通的类;/多数表决(4) 选择attribute_list中具有最高信息增益的属性test_attribute;(5) 标记结点N为test_attribute;(6) FOR each te
14、st_attribute中的已知值ai 由结点N长出一个条件为test_attribute=ai的分枝;(7)设si是samples 中test_attribute =ai的样本的集合;/一个划分(8)IF si 为空 THEN 加上一个树叶,标记为samples中最普通的类;(9)ELSE 加上一个由Generate_decision_tree(si, attribute_list-test_attribute)返回的结点;21 八月 2024DMKD Sides By MAO16决策树修剪算法n基本的决策树构造算法没有考虑噪声,因此生成的决策树完全与训练例子拟合。在有噪声情况下,将导致过分
15、拟合(Overfitting),即对训练数据的完全拟合反而使对现实数据的分类预测性能下降。n现实世界的数据一般不可能是完美的,可能缺值(Missing Values);数据不完整;含有噪声甚至是错误的。n剪枝是一种克服噪声的基本技术,同时它也能使树得到简化而变得更容易理解。有两种基本的剪枝策略:n预先剪枝(Pre-Pruning):在生成树的同时决定是继续对不纯的训练子集进行划分还是停机。n后剪枝(Post-Pruning):是一种拟合+化简(fitting-and-simplifying)的两阶段方法。首先生成与训练数据完全拟合的一棵决策树,然后从树的叶子开始剪枝,逐步向根的方向剪。剪枝时要
16、用到一个测试数据集合(Tuning Set或Adjusting Set),如果存在某个叶子剪去后能使得在测试集上的准确度或其他测度不降低(不变得更坏),则剪去该叶子;否则停机。理论上讲,后剪枝好于预先剪枝,但计算复杂度大。n剪枝过程中一般要涉及一些统计参数或阈值(如停机阈值)。要防止过分剪枝(Over-Pruning)带来的副作用。21 八月 2024DMKD Sides By MAO17ID3算法nID3是Quinlan提出的一个著名决策树生成方法:n决策树中每一个非叶结点对应着一个非类别属性,树枝代表这个属性的值。一个叶结点代表从树根到叶结点之间的路径对应的记录所属的类别属性值。n每一个非
17、叶结点都将与属性中具有最大信息量的非类别属性相关联。n采用信息增益来选择能够最好地将样本分类的属性。n为了聚焦重点,将对ID3算法采用如下方式讲解:n伪代码详细描述见课本;n给出信息增益对应的计算公式;n通过一个例子来说明它的主要过程。21 八月 2024DMKD Sides By MAO18信息增益的计算n设S是s个数据样本的集合,定义m个不同类Ci(i=1,2,m),设si是Ci类中的样本数。对给定的样本S所期望的信息值由下式给出:其中pi是任意样本属于Ci的概率: si / s 。 n设属性A具有个不同值a1, a2, , av ,可以用属性A将样本S划分为 S1, S2, , Sv ,
18、设sij 是Sj中Ci类的样本数,则由A划分成子集的熵由下式给出: n有A进行分枝将获得的信息增益可以由下面的公式得到:21 八月 2024DMKD Sides By MAO19ID3算法例子样本数据warm_bloodedfeathersfurswimslays_eggs111001200011311001411001510010610100 假设目标分类属性是lays_eggs,计算Gain(lays_eggs): warm_blooded=1, warm_blooded=0,类似的,Gain(feathers)=0.459;Gain(fur)=0.316;Gain(swims)=0.04
19、4。由于feathers在属性中具有最高的信息增益,所以它首先被选作测试属性。并以此创建一个结点,数据集被划分成两个子集。21 八月 2024DMKD Sides By MAO20ID3算法例子(续)n根据feathers的取值,数据集被划分成两个子集n对于feathers=1的所有元组,其目标分类属性=lays_eggs均为1。所以,得到一个叶子结点。 n对于feathers=0的右子树,计算其他属性信息增益:nGain(Gain(warm_bloodedwarm_blooded)=)=0.9180.918nGain(Gain(furfur)=0.318)=0.318nGain(Gain(s
20、wimsswims)=0.318)=0.318n根据warm_blooded的取值,左右子树均可得到叶子结点,结束。21 八月 2024DMKD Sides By MAO21ID3算法的性能分析nID3算法的假设空间包含所有的决策树,它是关于现有属性的有限离散值函数的一个完整空间。所以ID3算法避免了搜索不完整假设空间的一个主要风险:假设空间可能不包含目标函数。nID3算法在搜索的每一步都使用当前的所有训练样例,大大降低了对个别训练样例错误的敏感性。因此,通过修改终止准则,可以容易地扩展到处理含有噪声的训练数据。nID3算法在搜索过程中不进行回溯。所以,它易受无回溯的爬山搜索中的常见风险影响:
21、收敛到局部最优而不是全局最优。nID3算法只能处理离散值的属性。n信息增益度量存在一个内在偏置,它偏袒具有较多值的属性。例如,如果有一个属性为日期,那么将有大量取值,这个属性可能会有非常高的信息增益。假如它被选作树的根结点的决策属性则可能形成一颗非常宽的树,这棵树可以理想地分类训练数据,但是对于测试数据的分类性能可能会相当差。nID3算法增长树的每一个分支的深度,直到恰好能对训练样例完美地分类。当数据中有噪声或训练样例的数量太少时,产生的树会过渡拟合训练样例。21 八月 2024DMKD Sides By MAO22C4.5算法对ID3的主要改进nC4.5算法是从ID3算法演变而来,除了拥有I
22、D3算法的功能外,C4.5算法引入了新的方法和增加了新的功能:n用信息增益比例的概念;n合并具有连续属性的值;n可以处理具有缺少属性值的训练样本;n通过使用不同的修剪技术以避免树的过度拟合;nK交叉验证;n规则的产生方式等。21 八月 2024DMKD Sides By MAO23信息增益比例的概念n信息增益比例是在信息增益概念基础上发展起来的,一个属性的信息增益比例用下面的公式给出:其中假如我们以属性A的值为基准对样本进行分割的化,Splitl(A)就是前面熵的概念。 21 八月 2024DMKD Sides By MAO24C4.5处理连续值的属性n对于连续属性值,C4.5其处理过程如下:
23、n根据属性的值,对数据集排序;n用不同的阈值将数据集动态的进行划分;n当输出改变时确定一个阈值;n取两个实际值中的中点作为一个阈值;n取两个划分,所有样本都在这两个划分中;n得到所有可能的阈值、增益及增益比;n在每一个属性会变为取两个取值,即小于阈值或大于等于阈值。n简单地说,针对属性有连续数值的情况,则在训练集中可以按升序方式排列。如果属性A共有n种取值,则对每个取值vj(j=1,2,n),将所有的记录进行划分:一部分小于vj;另一部分则大于或等于vj。针对每个vj计算划分对应的增益比率,选择增益最大的划分来对属性A进行离散化。21 八月 2024DMKD Sides By MAO25C4.
24、5的其他处理 nC4.5处理的样本中可以含有未知属性值,其处理方法是用最常用的值替代或者是将最常用的值分在同一类中。n具体采用概率的方法,依据属性已知的值,对属性和每一个值赋予一个概率,取得这些概率,取得这些概率依赖于该属性已知的值。n规则的的产生:生:一旦树被建立,就可以把树转换成if-then规则。n规则存储于一个二维数组中,每一行代表树中的一个规则,即从根到叶之间的一个路径。表中的每列存放着树中的结点。 21 八月 2024DMKD Sides By MAO26C4.5算法例子样本数据OutlookTemperatureHumidityWindPlayTennisSunnyHot85fa
25、lseNoSunnyHot90trueNoOvercastHot78falseYesRainMild96falseYesRainCool80falseYesRainCool70trueNoOvercastCool65trueYesSunnyMild95falseNoSunnyCool70falseYesRainMild80falseYesSunnyMild70trueYesOvercastMild90trueYesOvercastHot75falseYesRainMild80trueNo(1)首先对Humidity进行属性离散化,针对上面的训练集合,通过检测每个划分而确定最好的划分在75处,则
26、这个属性的范围就变为(75)。(2)计算目标属性PlayTennis分类的期望信息: (3)计算每个属性的GainRatio:( 4) 选 取 最 大 的GainRatio, 根 据Outlook的取值,将三分枝。(5)再扩展各分枝节点,得到最终的决策树(见课本图4-7 )。 21 八月 2024DMKD Sides By MAO27第三章第三章 分类方法分类方法 内容提要内容提要n分类的基本概念与步骤 n基于距离的分类算法 n决策树分类方法 n贝叶斯分类 n规则归纳 n与分类有关的问题 nOutlook数据nS1=9,S2=4 nS11=2,s21=3-sunnynS12=4,S22=0-o
27、vercastnS13=3,S23=2-rainnI(s1,S2)=-(9/14)*log(9/14,2)-(5/14)*log(5/14,2)=0.940285959nI(S11,S21)=-0.4*LOG(0.4,2)-0.6*LOG(0.6,2)=0.9709-sunnynI(S12,S22)=-1*LOG(1,2)-0-overcastnI(S13,S23)=-0.6*LOG(0.6,2)-0.4*LOG(0.4,2)=0.9709-rainnE(Outlook)=(5/14)*0.9709*2=0.6935nGain(Outlook)=0.9403-0.6935=0.2468nSpl
28、ite(Outlook)=-5/14*LOG(5/14,2)*2-4/14*LOG(4/14,2)=1.577406nGainratio(Outlook)=Gain(Outlook)/Splite(Outlook)=0.2465/1.577406=0.15621 八月 2024DMKD Sides By MAO28nS11=4,S21=1nS12=5,S22=4nI(S1,S2)=I(s1,S2)=-(9/14)*log(9/14,2)-(5/14)*log(5/14,2)=0.940285959nI(S11,S21)=-0.4*LOG(0.4,2)-0.6*LOG(0.6,2)=0.7219
29、nI(S12,S22)=-(5/9)*LOG(5/9,2)-(4/9)*LOG(4/9,2)=0.9911nE(Humidity)=(5/14)*0.7219+(9/14)*0.9911=0.8950nGain(Humidity)=0.9403-0.8950=0.0453nSplite(Humidity)=-(5/14)*LOG(5/14,2)-(9/14)*LOG(9/14,2)=0.940285959nGainratio(Humidity)=Gain(Humidity)/Splite(Humidity)=0.0453/0.9402=0.04818123821 八月 2024DMKD Sid
30、es By MAO2921 八月 2024DMKD Sides By MAO30贝叶斯分类n定定义4-24-2设X是是类标号号未未知知的的数数据据样本本。设H为某某种种假假定定,如如数数据据样本本X属属于于某某特特定定的的类C。对于于分分类问题,我我们希希望望确确定定P(H|X),即即给定定观测数数据据样本本X,假假定定H成成立立的的概概率率。贝叶斯定理叶斯定理给出了如下出了如下计算算P(H|X)的的简单有效的方法有效的方法: :nP(H)是是先先验概概率率,或或称称H的的先先验概概率率。P(X |H)代代表表假假设H成成立立的的情情况况下下,观察察到到X的的概概率率。P(H| X )是是后后
31、验概概率率,或或称条件称条件X下下H的后的后验概率。概率。n例例如如,假假定定数数据据样本本域域由由水水果果组成成,用用它它们的的颜色色和和形形状状来来描描述述。假假定定X表表示示红色色和和圆的的,H表表示示假假定定X是是苹苹果果,则P(H|X)反反映映当当我我们看看到到X是是红色色并并是是圆的的时,我我们对X是是苹苹果的确信程度。果的确信程度。n贝叶叶斯斯分分类器器对两两种种数数据据具具有有较好好的的分分类效效果果:一一种种是是完完全独立的数据,另一种是函数依全独立的数据,另一种是函数依赖的数据。的数据。21 八月 2024DMKD Sides By MAO31朴素贝叶斯分类n朴素朴素贝叶斯
32、分叶斯分类的工作的工作过程如下:程如下:n(1)(1) 每每个个数数据据样本本用用一一个个n维特特征征向向量量X= x1,x2,xn表表示示,分分别描描述述对n个个属属性性A1,A2,An样本本的的n个度量。个度量。n(2)(2)假假定定有有m个个类C1,C2,Cm,给定定一一个个未未知知的的数数据据样本本X(即即没没有有类标号号),分分类器器将将预测X属属于于具具有有最最高高后后验概概率率(条条件件X下下)的的类。也也就就是是说,朴朴素素贝叶叶斯斯分分类将将未未知知的的样本本分分配配给类Ci(1im)当当且且仅当当P(Ci|X) P(Cj|X),对任任意意的的j=1,2,m,ji。这样,最最
33、大大化化P(Ci|X)。其其P(Ci|X)最最大大的的类Ci称称为最最大大后后验假假定定。根根据据贝叶斯定理叶斯定理21 八月 2024DMKD Sides By MAO32朴素贝叶斯分类(续)n(3)(3)由由于于P(X)对于于所所有有类为常常数数,只只需需要要P(X|Ci)*P(Ci)最最大大即即可可。如如果果Ci类的的先先验概概率率未未知知,则通通常常假假定定这些些类是是等等概概率率的的,即即P(C1)=P(C2)=P(Cm),因因此此问题就就转换为对P(X|Ci)的的最最大大化化(P(X|Ci)常常被被称称为给定定Ci时数数据据X的的似似然然度度,而而使使P(X|Ci)最最大大的的假假
34、设Ci称称为最最大大似似然然假假设)。否否则,需需要要最最大大化化P(X|Ci)*P(Ci)。注注意意,类的的先先验概概率率可可以以用用P(Ci)=si/s计算算,其其中中si是是类Ci中中的的训练样本本数数,而而s是是训练样本本总数数。n(4)(4)给定定具具有有许多多属属性性的的数数据据集集,计算算P(X|Ci)的的开开销可可能能非非常常大大。为降降低低计算算P(X|Ci)的的开开销,可可以以做做类条条件件独独立立的的朴朴素素假假定定。给定定样本本的的类标号号,假假定定属属性性值相相互互条条件件独独立立,即在属性即在属性间,不存在依,不存在依赖关系。关系。这样21 八月 2024DMKD
35、Sides By MAO33朴素贝叶斯分类(续)其中概率其中概率P(x1|Ci),P(x2|Ci),P(xn|Ci)可以由可以由训练样本估本估值。n如果如果A Ak k是离散属性,则是离散属性,则P P( (x xk k| |C Ci i)=)=s sikik| |s si i,其中其中s sikik是在属性是在属性A Ak k上具有值上具有值x xk k的的类类C Ci i的训练样本数,而的训练样本数,而s si i是是C Ci i中的训练样本数。中的训练样本数。 n如果如果A Ak k是连续值属性,则通常假定该属性服从高斯分布。因而,是连续值属性,则通常假定该属性服从高斯分布。因而, 是高
36、斯分布函数,是高斯分布函数, 而分别为平均值和标准差。而分别为平均值和标准差。 n(5)(5)对未未知知样本本X分分类,也也就就是是对每每个个类Ci,计算算P(X|Ci)*P(Ci)。样本本X被被指指派派到到类Ci,当当且且仅当当P(Ci|X) P(Cj|X),1jm,ji,换言之,言之,X被指派到其被指派到其P(X|Ci)*P(Ci)最大的最大的类。21 八月 2024DMKD Sides By MAO34朴素贝叶斯分类举例样本数据 Ageincomestudentcredit_ratingbuy_computer=30 High NoFairNo40 Medium NoFairYes40
37、Low YesFairYes40 Low YesExcellentNo3140 Low YesExcellentYes=30 Medium NoFairNo40 Medium YesFairYes40 Medium NoExcellentNo(1) 我们需要最大化P(X|Ci)*P(Ci),i=1,2。每个类的先验概率P(Ci)可以根据训练样本计算:P(buys_computer=”yes”)=9/14=0.643,P(buys_computer=”no”)=5/14=0.357。 (2) 为计算P(X|Ci),i=1,2,我们计算下面的条件概率:P(age=30|buys_computer=
38、”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”|buys_computer=”yes” )=6/9=0.677,P(student=”yes”|buys_computer=”no” )=1/5=0.200,P(credit_rating=”fair”|buys_computer=”yes” )=6/
39、9=0.667,P(credit_rating=”fair”|buys_computer=”no” )=2/5=0.400。 (3) 假设条件独立性,使用以上概率,我们得到: P(X|buys_computer=”yes” )=0.222*0.444*0.667*0.667=0.044, P(X|buys_computer=”no” )=0.600*0.400*0.200*0.400=0.019, P(X|buys_computer=”yes” )*P(buys_computer=”yes” )= 0.044*0.643=0.028 P(X|buys_computer=”no” )*P(buy
40、s_computer=”no” )= 0.019*0.357=0.007。 因 此 , 对 于 样 本 X, 朴 素 贝 叶 斯 分 类 预 测buys_computer=”yes”。数据样本用属性ageage,incomeincome,studentstudent和credit_ratingcredit_rating描述。类标号属性buys_computerbuys_computer具有两个不同值(即yesyes,nono)。设C1对应于类buys_computer=”yes”,而C2对应于类buys_computer=”no”。我们希望分类的未知样本为:X=(age=”=30”,incom
41、e=”medium”,student=”yes”,credit_rating=”fair”)。21 八月 2024DMKD Sides By MAO35第三章第三章 分类方法分类方法 内容提要内容提要n分类的基本概念与步骤 n基于距离的分类算法 n决策树分类方法 n贝叶斯分类 n神经网络学习方法n与分类有关的问题 21 八月 2024DMKD Sides By MAO3621 八月 2024DMKD Sides By MAO3721 八月 2024DMKD Sides By MAO3821 八月 2024DMKD Sides By MAO3921 八月 2024DMKD Sides By MA
42、O4021 八月 2024DMKD Sides By MAO4121 八月 2024DMKD Sides By MAO4221 八月 2024DMKD Sides By MAO4321 八月 2024DMKD Sides By MAO44第三章第三章 分类方法分类方法 内容提要内容提要n分类的基本概念与步骤 n基于距离的分类算法 n决策树分类方法 n贝叶斯分类 n神经网络学习方法n与分类有关的问题 21 八月 2024DMKD Sides By MAO454621 八月 2024DMKD Sides By MAO4721 八月 2024DMKD Sides By MAO4821 八月 2024
43、DMKD Sides By MAO4921 八月 2024DMKD Sides By MAO5021 八月 2024DMKD Sides By MAO5121 八月 2024DMKD Sides By MAO5221 八月 2024DMKD Sides By MAO5321 八月 2024DMKD Sides By MAO5421 八月 2024DMKD Sides By MAO5521 八月 2024DMKD Sides By MAO5621 八月 2024DMKD Sides By MAO5721 八月 2024DMKD Sides By MAO5821 八月 2024DMKD Sides
44、 By MAO5921 八月 2024DMKD Sides By MAO60第三章第三章 分类方法分类方法 内容提要内容提要n分类的基本概念与步骤 n基于距离的分类算法 n决策树分类方法 n贝叶斯分类 n规则归纳 n与分类有关的问题 21 八月 2024DMKD Sides By MAO61规则归纳n常见的采用规则表示的分类器构造方法有:n利用规则归纳技术直接生成规则n利用决策树方法先生成决策树,然后再把决策树转换为规则;n使用粗糙集方法生成规则;n使用遗传算法中的分类器技术生成规则等。n本节将只讨论规则归纳方法。我们这里讨论的规则归纳算法,可以直接学习规则集合,这一点与决策树方法、遗传算法有
45、两点关键的不同。n它们可学习包含变量的一阶规则集合:这一点很重要,因为一阶子句的表达能力比命题规则要强得多。n这里讨论的算法使用序列覆盖算法:一次学习一个规则,以递增的方式形成最终的规则集合。21 八月 2024DMKD Sides By MAO62规则归纳(续)n规则归纳有四种策略:减法、加法,先加后减、先减后加策略。n减法策略:以具体例子为出发点,对例子进行推广或泛化,推广即减除条件(属性值)或减除合取项(为了方便,我们不考虑增加析取项的推广),使推广后的例子或规则不覆盖任何反例。n加法策略:起始假设规则的条件部分为空(永真规则),如果该规则覆盖了反例,则不停地向规则增加条件或合取项,直到
46、该规则不再覆盖反例。n先加后减策略:由于属性间存在相关性,因此可能某个条件的加入会导致前面加入的条件没什么作用,因此需要减除前面的条件。n先减后加策略:道理同先加后减,也是为了处理属性间的相关性。n典型的规则归纳算法有AQ、CN2和FOIL等。21 八月 2024DMKD Sides By MAO63 AQ算法n AQ算法利用覆盖所有正例,排斥所有反例的思想来寻找规则。比较典型的有Michalski的AQ11方法,洪家荣改进的AQ15方法以及洪家荣的AE5方法。nAQR是一个基于最基本AQ算法的归纳算法。其实,在很多的算法中,都采用了基本AQ算法,象AQ11和GEM。但和其它方法比较而言,AQ
47、R更加简单一些,如在AQ11中使用一种复杂的包括置信度的规则推导方法。下面我们首先对AQR算法进行概念描述,然后介绍算法描述和相关例子,最后分析其性能。21 八月 2024DMKD Sides By MAO64AQR算法有关定义nAQR为每一个分类推导出一条规则,每一条规则形式如下:if then predict 。n在一个属性上的基本测试被称为一个Selector。下面是一些Selector的例子:或60。nAQR允许测试做=,。Selectors的合取被称为复合(Complex),Complexes之间的析取被称为覆盖(Cover)。如果一个表达式对某个样本为真,则我们称其为对这个样本的一
48、个覆盖。这样,一个空Complex覆盖所有的样本,而一个空Cover不覆盖任何样本。n在AQR中,一个新样本被区分是看其属于哪个推导出来的规则。如果该样本只满足一条规则,则这个样本就属于这条规则;如果该样本满足多条规则,则被这些规则所预测的最频繁的分类被赋予这条规则;如果该样本不属于任何规则,则其分类为样本集中最频繁的分类。21 八月 2024DMKD Sides By MAO65 AQR算法描述算法算法4-5AQR输入:正例样本POS;反例样本NEG。输出:覆盖COVER。(1) COVER= ;/初始化COVER为空集(2) WHILE COVER does not cover all p
49、ositive examples in POS DO BEGIN(3) Select a SEED;/选取一个种子SEED,例如没有被COVER覆盖的一个正样例(4) Call procedure STAR(SEED,NEG); /产生一个能覆盖种子而同时排除所有反例的星(5) Select the best Complex BEST from the STAR according to user-defined criteria;/*从星中选取一个最好的复合*/(6) Add BEST as an extra disjuct to COVER /*把最好的复合与COVER合取,形成新的COV
50、ER*/(7) END(8) RETURN COVER.在算法AQR中调用了过程STAR,来排除所有的反例,产生覆盖种子的星。21 八月 2024DMKD Sides By MAO66 AQR算法描述(续)算法算法4-6 STAR输入:种子SEED;反例NEG。输出:星STAR。 (1)初始化STAR为空Complex(2)WHILE one or more Complexes in STAR covers some negative examples in NEG BEGIN /*如果STAR中的一个或多个Complex覆盖NEG中的负样例*/(3)Select a negative exa
51、mple Eneg covered by a Complex in STAR;/*选取一个被STAR中的Complex覆盖的负样例*/(4)Let EXTENSION be all Selectors that cover SEED but not ENEG;/*令EXTENSION为那些覆盖SEED但不覆盖ENEG的Selectors;*/(5)Let STAR be the set xy|xSTAR,yEXTENSION;/*令STAR= xy|xSTAR,yEXTENSION;*/(6) Remove all Complexes in STAR subsumed by other Com
52、plexes in STAR;/*从STAR中除去被其他Complexes所包含的Complexes;*/(7)Remove the worst Complexes from STAR UNTIL size of STAR is less than or equal to user-defined maximum (maxstar)/*删除STAR中最坏的Complex直到STAR的大小等于或小于用户定义的最大数目maxstar*/(8)END(9)RETURN STAR. /*返回一系列覆盖SEED但不覆盖NEG的规则*/21 八月 2024DMKD Sides By MAO67AQR算法举
53、例假设现有一个训练集,其包含两种属性:size (属性值:micro,tiny,mid,big,huge,vast)type (属性值:bicycle,motorcycle,car,prop,jet,glider)现有正例、反例样本分别如表4-6,表4-7所示: 下面给出用AQR算法对giant 2-wheeler类的规则进行获取过程,具体步骤如下:()COVER=。()空cover不覆盖任何样本,进入循环。()一开始COVER并没有覆盖任何正例,假定从正例中选取的SEED 为 size=huge,type =bicycle 。()调用STAR(SEED,NEG)去产生一个覆盖SEED但不包含
54、NEG的STAR集合;初始化STAR为空,即STAR=。空的complex覆盖所有样例,STAR覆盖多个负样例,进入循环。 a ) 选取一个被STAR中的复合覆盖的负样例ENEG,假定被选取的是 Eneg= size= tiny, type = motorcycle 。 b ) 使EXTENSION为所有覆盖SEED但不覆盖ENEG的选择,则EXTENSION包括size= huge和type =bicycle,则又根据STAR=xy|xSTAR,yEXTENSION,因此,STAR= size=hugetype =bicycle 。 c ) 在这里定义maxstar为2,可不对STAR进行精
55、简。 d ) 接着选取另一个被STAR中的复合覆盖的负样例ENEG,显然已经没有这样的负样例,因此,STAR= size=hugetype =bicycle 。从STAR(SEED,NEG)返回。反例样本sizetypeclassTiny motorcycle conventional transportation tiny car conventional transportation mid car conventional transportation micro jetfast planeTiny jetfast planeMid jetfast plane正例样本sizetypecl
56、assHuge bicycle giant 2-wheelerHuge motorcycle giant 2-wheeler21 八月 2024DMKD Sides By MAO68AQR算法举例(5)BEST= size=hugetype =bicycle ,COVER = size=hugetype =bicycle 。 (6)显然COVER不能覆盖所有的正例,从正例中选取另一个SEED= size=huge,type = motorcycle。 (7)调用STAR(SEED,NEG)去产生一个覆盖SEED但不包含NEG的STAR集合。 初始化STAR为空,即STAR=;空的complex
57、覆盖所有样例, 所以STAR覆盖负样例,进入循环; a ) 假定被选取的是Eneg= size= tiny, type = motorcycle ; b ) 使EXTENSION为所有覆盖SEED但不覆盖Eneg的选择,则EXTENSION包括size= huge,则又根据STAR=xy|xSTAR,yEXTENSION,因此,STAR= size=huge; c ) 接着选取另一个被STAR中的复合覆盖的负样例Eneg,显然已经没有这样的负样例,因此,STAR= size=huge; d ) 接着选取另一个被STAR中的复合覆盖的负样例ENEG,显然已经没有这样的负样例,因此,STAR= s
58、ize=hugetype =bicycle 。从STAR(SEED,NEG)返回。(8)BEST=size=huge,将BEST添加到COVER中,COVER = size=hugetype =bicycle size=huge= size=huge。 (9)这时,COVER已经覆盖到全部的正例,则算法结束。输出规则为gaint 2-wheelersize=huge。假设现有一个训练集,其包含两种属性:size (属性值:micro,tiny,mid,big,huge,vast)type (属性值:bicycle,motorcycle,car,prop,jet,glider)现有正例、反例样本
59、分别如表4-6,表4-7所示: 反例样本sizetypeclassTiny motorcycle conventional transportation tiny car conventional transportation mid car conventional transportation micro jetfast planeTiny jetfast planeMid jetfast plane正例样本sizetypeclassHuge bicycle giant 2-wheelerHuge motorcycle giant 2-wheeler21 八月 2024DMKD Sides
60、 By MAO69CN2算法描述nCN2使用一种基于噪音估计的启发式方法,使用这种方法可以不用对所有的训练样本进行正确的区分,但是规约出的规则在对新数据的处理上有很好的表现。算法算法4-7 CN2输入:E /*E为训练样本*/输出:RULE_LIST /*返回一个覆盖若干样例的规则*/(1) Let RULE_LIST be the empty list; /* 初始化RULES_LIST为空;*/(2) REPEAT(3) Let BEST_CPX be Find_Best_Complex(E);/*寻找最佳的规则Find_Best_Complex(E)并将其结果放入BEST_CPX中;*/
61、(4) IF BEST_CPX is not nil THEN BEGIN(5) Let E be the examples covered by BEST_CPX;/*令E为BEST_CPX覆盖的所有样例*/(6) Remove from E the examples E covered by BEST_CPX; /*从训练样本E中除去E,即E=E-E;*/(7) Let C be the most common class of examples in E; /*令C为样本子集E中最频繁的分类标号;*/(8) Add the rule if BEST_CPX then class=C to
62、 the end of RULE_LIST;/*将规则if BEST_CPX then class=C添加到RULES_LIST中*/(9) END(10)UNTIL BEST_CPX is nil or E is empty. /*直到BEST_CPX为空或者训练样本E为空*/(11)RETURN RULE_LIST算法CN2需要通过调用函数Find_Best_Complex,它的描述写成下面算法4-8。 21 八月 2024DMKD Sides By MAO70CN2算法描述(续)算法算法4-8 Find_Best_Complex输入:E /*E为训练样本*/输出:BEST_CPX /*返
63、回最佳的规则BEST_CPX */(1) Let the set STAR contain only the empty Complex; /*初始化集合STAR为空Complex;*/(2) Let BEST_CPX be nil; /*初始化BEST_CPX为空*/(3) Let SELECTORS be the set of all possible Selectors; /*集合SELECTOR为所有可能的选择*/(4) WHILE STAR is not empty DO BEGIN(5) Let NEWSTAR be the set xy|xSTAR,yEXTENSION;/*令N
64、EWSTAR= xy|xSTAR,yEXTENSION;*/(6) Remove all Complexes in NEWSTAR that are either in STAR or are null;/*从NEWSTAR中除去包括在STAR中的Complex或者为空的Complex*/(7) FOR every complex Ci in NEWSTAR (8) IF Ci is statistically significant when tested on E and better than BEST_CPX according to user-defined criteria whe
65、n tested on E /*如果Ci在统计上有意义,并且对训练集E测试后符合用户定义的条件且优于BEST_CPX*/(9) THEN replace the current value of BEST_CPX by Ci; /*将BEST_CPX替换为Ci*/(10) REPEAT remove worst Complexes from NEWSTAR (11) UNTIL size of NEWSTAR is = user-defined maximum maxstar;/*逐步移去在NEWSTAR中最坏的complex直到NEWSTAR的大小等于或小于用户 定义的最大数目maxstar
66、*/(12)Let STAR be NEWSTAR; /*令STAR=NEWSTAR*/(13)END(14)RETURN BEST_CPX。/*返回BEST_CPX*/ 21 八月 2024DMKD Sides By MAO71FOIL算法nFOIL学习系统已经被广泛地应用在逻辑规约领域。FOIL是用来对无约束的一阶Horn子句进行学习。一个概念的定义是由一系列的子句组成,而其中每一个子句描述了一种证明一个样本是这个概念的实例的唯一方法。每个子句由一些文字的析取组成。nFOIL由一系列的外部定义的断言开始,其中之一被确定为当前学习的概念,而其他作为背景文字。FOIL从这些外部定义的断言中获取
67、一系列包括文字的子句。nFOIL算法由一个空子句开始查找,其不断的向当前的子句中追加文字直到没有负样例被子句所覆盖。之后,FOIL重新开始一个子句的查找,直到所有的正样例均被已经生成的子句所覆盖。FOIL计算每一个外部定义断言的信息熵(Information Gain)和合法的变量(Legal Variabilization)用来决定哪一个文字添加到子句中。21 八月 2024DMKD Sides By MAO72一阶Horn子句的主要术语n一阶Horn子句所涉及的主要术语有:n所有表达式由常量(如Mary、23或Joe)、变量(如x)、谓词(如在Female(Mary)中的Female和函数
68、(如在age(Mary)中的age)组成;n项(Term)为任意常量、任意变量或任意应用到项集合上的函数。例如,Mary,x,age(Mary),age(x);n文字(Literal)是应用到项集合上的任意谓词或其否定。例如,Female(Mary),Greater_than(age(Mary),20);n基本文字(Ground Literal)是不包括任何变量的文字;n负文字(Negative Literal)是包括否定谓词的文字;n正文字(Positive Literal)是不包括否定谓词的文字;n子句(Clause)是多个文字的析取式,M1Mn,其中所有变量是全程量化的;21 八月 20
69、24DMKD Sides By MAO73一阶Horn子句的表达nHorn子句是一个如下形式的表达式: H(L1Ln)。其中,H,L1,L2,Ln为正文字。H被称为Horn子句的头(Head)或推论(Consequent)。文字合取式L1L2.Ln被称为Horn子句的体(Body)或者先行词(Antecedents)。n置换(Substitution)是一个将某些变量替换为某些项的函数。例如,置换x/3,y/z把变量x替换为项3并且把变量y替换为项z。给定一个置换和一个文字L,我们使用L代表应用置换到L得到的结果。21 八月 2024DMKD Sides By MAO74FOIL算法描述算法算
70、法 4-9 4-9 FOIL (Target_predicate,Predicates,Examples)输入:Examples /*样本数据*/ Predicates /*断言集合*/ Target_predicate /*目标断言*/输出:规则(1) PosExamples中Target_predicate为Ture的成员;(2) NegExamples中Target_predicate为False的成员;(3) Learen_rules;(4) WHILE Pos不空DO BEGIN /*学习NewRule*/(5) NewRules没有前件的谓词Target_predicate规则;(
71、6) NewRuleNegNeg;(7) WHILE NewRuleNeg不空 BEGIN /*增加新文字以特化NewRule*/(8) Candidate_literals对NewRule生成后选新文字,基于Predicates;(9) Best_literalargmax Foil_Gain (L,NewRule); /*获取最佳文字*/(10) 把Best_literal加入到NewRule的前件;(11) NewRuleNegNewRuleNeg中满足NewRule前件的子集(12) END;(13) Learned_rulesLearned_rules+NewRule;(14) Po
72、sPos-被NewRule覆盖的Pos成员(15) END;(16) 返回Learned_rules21 八月 2024DMKD Sides By MAO75FOIL算法介绍n FOIL中的候选特征化式的生成: 为生成当前规则的候选特征式,FOIL生成多个不同的新文字,每个可被单独地加到规则前件中。更精确地讲,假定当前规则为:P(x1,x2,xk) L1L其中,L1,Ln为当前规则前件中的文字,而P(x1,x2,xk)为规则头(或后件)。FOIL生成该规则的候选特征化式的方法是考虑符合下列形式的新文字Ln+1:n Q(v1,vr),其中Q为在Predicates中出现的任意谓词名,并且vi既可
73、 为新变量,也可为规则中已有的变量。vi中至少一个变量必须是当前规则中已有的。nEqual(xj,xk),其中xj和xk为规则中已有的变量。n上述两种文字的否定。21 八月 2024DMKD Sides By MAO76FOIL算法介绍(续)n Foil_Gain函数函数 n FOIL使用评估函数以估计增加新文字的效用,它基于加入新文字前后的正例和反例的约束数目。更精确地讲,考虑某规则R和一个可能被加到R的规则体的后选文字L。令R为加入文字L到规则R后生成的规则。Foil_Gain(L,R)的值定义为:其中,p0为规则R的正例约束数目,n0为R的反例约束数目,p1是规则R的正例约束数,n1为规
74、则R的反例约束数目。最后,t是在加入文字L到R后仍旧能覆盖的规则R的正例约束数目。当加入L引入了一个新变量到R中时,只要在R的约束中的某些约束扩展了原始的约束,它们仍然能被覆盖。 21 八月 2024DMKD Sides By MAO77FOIL算法举例假设学习目标文字fathe(A,B)的规则集例子。训练数据包括下列简单的断言集合:Examples: /*样本数据*/positive: father(christopher,arthur) father(christopher,victoria)negative: father(penelope,arthur) father(christop
75、her,penelope)Predicates: /断言集合male(christopher),male(arthur)female(victoria),female(penelope)parent(christopher,arthur),parent(christopher,victoria)parent(penelope,arthur),parent(penelope,victoria)则根据FOIL算法:nPos=father(christopher,arthur),father(christopher,victoria);nNeg=father(penelope,arthur), fa
76、ther(christopher,penelope);nLearned_rules=;n当Pos不为空,则学习NewRulea) NewRule=father(A,B);b) NewRuleNeg= father(penelope,arthur), father(christopher,penelope);c) 当NewRuleNeg不为空,则增加特征化文字:由FOIL中的侯选特征化式的规则,根据father(A,B)可生成的侯选文字为:male(A), not(male(A), male(B), not(male(B),female(A), not(female(A), female(B),
77、 not(female(B),parent(A,A), not(parent(A,A), parent(B,B), not(parent(B,B),parent(A,B), not(parent(A,B), parent(B,A), not(parent(B,A),parent(A,C), not(parent(A,C), parent(C,A), not(parent(C,A),parent(B,C), not(parent(B,C), parent(C,B), not(parent(C,B);因此,Candidate_literals= male(A),male(B),female(A),
78、female(B),之后计算最佳文字Best_literal,具体计算过程如下表所示(p0=2,n0=2 )。21 八月 2024DMKD Sides By MAO78FOIL算法举例(续) 文字的获益计算结果Testp1n1tGainmale(A)2120.83not(male(A)0100.00male(B)1110.00not(male(B)1110.00female(A)0100.00not(female(A)2120.83female(B)1110.00not(female(B)1110.00parent(A,A)0000.00not(parent(A,A)2220.00parent
79、(A,B)2120.83not(parent(A,B)0100.00parent(B,B)0000.00not(parent(B,B)2220.00parent(B,A)0000.00not(parent(B,A)2220.00parent(A,C)4420.00not(parent(A,C)0000.00parent(C,B)0000.00not(parent(C,B)2120.8321 八月 2024DMKD Sides By MAO79FOIL算法举例(续)选择文字male(A) 添加到Best_literal,NewRule= father(A,B) male(A),其覆盖两个正例和一
80、个反例。NewRuleNeg改写为NewRuleNeg=father(penelope,arthur),d) 当NewRuleNeg不为空,则增加特征化文字:则下一个文字应添加parent(A,B)。再将Best_literal加为NewRule的前件,则NewRule= father (A,B) male(A)parent(A,B);这时NewRuleNeg中的所有成员满足NewRule前件的子集,跳出内层循环。e) Learn_rules=Learn_rules+ father (A,B) male(A)parent(A,B) ;f) 再从Pos中减去被NewRules覆盖的成员;n这时P
81、os为空,算法结束。21 八月 2024DMKD Sides By MAO80第三章第三章 分类方法分类方法 内容提要内容提要n分类的基本概念与步骤 n基于距离的分类算法 n决策树分类方法 n贝叶斯分类 n规则归纳 n与分类有关的问题 21 八月 2024DMKD Sides By MAO81分类数据预处理n分类的效果一般和数据的特点有关,有的数据噪声大,有的有空缺值,有的分布稀疏,有的字段或属性间相关性强,有的属性是离散的而有的是连续值或混合式的。目前普遍认为不存在某种方法能适合于各种特点的数据。因此,在分类以前需要做一些数据的预处理。n 数据清理数据清理n主要是消除或减少数据噪声和处理空缺
82、值。 n 特征选择特征选择n从已知一组特征集中按照某一准则选择出有很好的区分特性的特征子集n或按照某一准则对特征的分类性能进行排序,用于分类器的优化设计。n 数据变换数据变换n就是通过平滑、聚集、数据概化、规范化、特征构造等手段将数据转化为适合于挖掘的形式。21 八月 2024DMKD Sides By MAO82分类器性能的表示n分类器性能的表示方法类似信息检索系统的评价方法,可以采用OC曲线和ROC曲线、混淆矩阵等。n定定义4-3 给定一个类Cj和一个数据库元组ti,ti可能被分类器判定为属于Cj或不属于Cj,其实ti本身可能属于Cj或不属于Cj,这样就会产生如下一些情况:n真正: 判定t
83、i在Cj中,实际上的确在其中。n假正: 判定ti在Cj中,实际上不在其中。n真负: 判定ti不在Cj中,实际上不在其中。n假负: 判定ti不在Cj中,实际上的确在其中。n在上述定义的基础上,人们经常使用OC曲线和ROC曲线表示“假正”和“真正”的关系。OC曲线通常用于通信领域来测试误报率。OC曲线的水平轴一般表示“假正”的百分比,另外一个轴表示“真正”的百分比。21 八月 2024DMKD Sides By MAO83分类器性能的表示(续)n混淆矩阵是另外一种表示分类准确率的方法。假定有m个类,混淆矩阵是一个 m*m 的矩阵,Ci,j表明了D中被分到类Cj但实际类别是Ci的元组的数量。显然地,
84、最好解决方案是对角线以外的值为全零。混淆矩阵示例实 际 分 类矮中等高矮040中等053高01221 八月 2024DMKD Sides By MAO84分类器性能的评估n保持法和交叉验证是两种基于给定数据随机选样划分的、常用的评估分类方法准确率的技术。n(1 1)保持法)保持法把给定的数据随机地划分成两个独立的集合:训练集和测试集。通常,三分之一的数据分配到训练集,其余三分之二分配到测试集。使用训练集得到分类器,其准确率用测试集评估。n(2 2)交叉验证)交叉验证先把数据随机分成不相交的n份,每份大小基本相等,训练和测试都进行n次。比如,如果把数据分成10份,先把第一份拿出来放在一边用作模型测试,把其他9份合在一起来建立模型,然后把这个用90%的数据建立起来的模型用上面放在一边的第一份数据做测试。这个过程对每一份数据都重复进行一次,得到10个不同的错误率。最后把所有数据放在一起建立一个模型,模型的错误率为上面10个错误率的平均。 21 八月 2024DMKD Sides By MAO85第三章第三章 分类方法分类方法 内容提要内容提要n分类的基本概念与步骤 n基于距离的分类算法 n决策树分类方法 n贝叶斯分类 n规则归纳 n与分类有关的问题 21 八月 2024DMKD Sides By MAO86Thank you !