数据挖掘导论第5章-分类-其他技术.ppt
《数据挖掘导论第5章-分类-其他技术.ppt》由会员分享,可在线阅读,更多相关《数据挖掘导论第5章-分类-其他技术.ppt(134页珍藏版)》请在三一办公上搜索。
1、数据挖掘导论,Pang-ning Tan,Michael Stieinbach,and Vipin Kumar著Pearson Education LTD.范明 等译人民邮电出版社,第5章 分类:其他技术,基于规则的分类最近邻分类贝叶斯分类神经网络支持向量机组合方法不平衡类问题多类问题,5.1 基于规则的分类器,2023/10/14,数据挖掘:概念与技术,4,基于规则的分类器,使用一组“ifthen”规则进行分类规则:(Condition)y其中 Condition 是属性测试的合取 y 是类标号左部:规则的前件或前提右部:规则的结论分类规则的例子:(Blood Type=Warm)(Lay
2、Eggs=Yes)Birds(Taxable Income 50K)(Refund=Yes)Evade=No,2023/10/14,数据挖掘:概念与技术,5,基于规则的分类器:例,脊椎动物数据集,2023/10/14,数据挖掘:概念与技术,6,基于规则的分类器的使用,规则 r 覆盖 实例 x,如果该实例的属性满足规则r的条件r1:(胎生=否)(飞行动物=是)鸟类r2:(胎生=否)(水生动物=是)鱼类r3:(胎生=是)(体温=恒温)哺乳类r4:(胎生=否)(飞行动物=否)爬行类r5:(水生动物=半)两栖类规则r1覆盖“鹰”=鸟类规则r3 覆盖“灰熊”=哺乳类,2023/10/14,数据挖掘:概念
3、与技术,7,规则的质量,用覆盖率和准确率度量规则的覆盖率(coverage):满足规则前件的记录所占的比例规则的准确率(accuracy):在满足规则前件的记录中,满足规则后件的记录所占的比例规则:(Status=Single)No Coverage=40%,Accuracy=50%,Tid,Refund,Marital,Status,Taxable,Income,Class,1,Yes,Single,125K,No,2,No,Married,100K,No,3,No,Single,8,No,Single,85K,Yes,9,No,Married,75K,No,10,No,Singl,e,90
4、K,Yes,10,2023/10/14,数据挖掘:概念与技术,8,如何用规则分类,一组规则r1:(胎生=否)(飞行动物=是)鸟类r2:(胎生=否)(水生动物=是)鱼类r3:(胎生=是)(体温=恒温)哺乳类r4:(胎生=否)(飞行动物=否)爬行类r5:(水生动物=半)两栖类待分类记录狐猴触发规则 r3,它分到哺乳类海龟触发规则r4和 r5-冲突狗鲨未触发任何规则,2023/10/14,数据挖掘:概念与技术,9,规则的分类器的特征,互斥规则集每个记录最多被一个规则覆盖如果规则都是相互独立的,分类器包含互斥规则如果规则集不是互斥的一个记录可能被多个规则触发如何处理?有序规则集基于规则的序 vs 基于
5、类的序 无序规则集 使用投票策略,2023/10/14,数据挖掘:概念与技术,10,规则的分类器的特征(续),穷举规则集每个记录至少被一个规则覆盖如果规则集涵盖了属性值的所有可能组合,则规则集具有穷举覆盖如果规则集不是穷举的一个记录可能不被任何规则触发如何处理?使用缺省类,2023/10/14,数据挖掘:概念与技术,11,有序规则集,根据规则优先权将规则排序定秩(rank)有序规则集又成决策表(decision list)对记录进行分类时由被触发的,具有最高秩的规则确定记录的类标号如果没有规则被触发,则指派到缺省类,2023/10/14,数据挖掘:概念与技术,12,规则定序方案,基于规则的序根
6、据规则的质量排序基于类的序属于同一类的规则放在一起基于类信息(如类的分布、重要性)对每类规则排序,2023/10/14,数据挖掘:概念与技术,13,如何建立基于规则的分类器,直接方法:直接由数据提取规则例如:RIPPER,CN2,Holtes 1R间接方法:由其他分类模型提取规则(例如,从决策树、神经网络等).例如:C4.5rules,2023/10/14,数据挖掘:概念与技术,14,直接方法:顺序覆盖,基本思想依次对每个类建立一个或多个规则对第i类建立规则第i类记录为正例,其余为负例建立一个第i类的规则r,尽可能地覆盖正例,而不覆盖负例删除r覆盖的所有记录,在剩余数据集上学习下一个规则,直到
7、所有第i类记录都被删除,2023/10/14,数据挖掘:概念与技术,15,直接方法:顺序覆盖,顺序覆盖(sequential covering)算法 1:令E是训练记录,A是属性值对的集合(Aj,vj)2:令Yo是类的有序集y1,y2,.,yk 3:令R=是初始规则列表 4:for 每个类 yYo yk do 5:while 终止条件不满足 do 6:r Learn-One-Rule(E,A,y)7:从E中删除被r覆盖的训练记录 8:追加r到规则列表尾部:RR r 9:end while10:end for11:把默认规则yk插入到规则列表R尾部,2023/10/14,数据挖掘:概念与技术,1
8、6,顺序覆盖:例,(a)Original data,(b)Step 1,(c)Step 2,(c)Step 3,2023/10/14,数据挖掘:概念与技术,17,删除实例,为什么要删除实例?否则,下一个规则将与前面的规则相同为什么删除正实例?确保下一个规则不同为什么删除负实例?防止低估规则的准确率比较图中的规则 R2 和 R3,2023/10/14,数据挖掘:概念与技术,18,Learn-One-Rule,规则增长实例删除规则评估停止准则规则剪枝,2023/10/14,数据挖掘:概念与技术,19,规则增长,两种策略一般到特殊从初始规则r:y开始反复加入合取项,得到更特殊的规则,直到不能再加入
9、特殊到一般随机地选择一个正例作为初始规则反复删除合取项,得到更一般的规则,直到不能再删除问题加入/删除合取项有多种选择,如何选择?何时停止加入/删除合取项?需要评估标准,2023/10/14,数据挖掘:概念与技术,20,规则增长:例,一般到特殊,特殊到一般,2023/10/14,数据挖掘:概念与技术,21,规则评估,常用的度量准确率似然比LaplaceM-estimateFOIL信息增益,2023/10/14,数据挖掘:概念与技术,22,规则评估(续),准确率Accuracyn:被规则覆盖的实例数nc:被规则正确分类的实例数问题:准确率高的规则可能覆盖率太低似然比(越高越好)k是类的个数fi是
10、被规则覆盖的类i的样本的观测频度ei是规则作随机猜测的期望频度,2023/10/14,数据挖掘:概念与技术,23,规则评估:例,例:60个正例和100个反例 规则r1:覆盖50个正例和5个反例(acc=90.9%)规则r2:覆盖2个正例和0个反例(acc=100%)使用准确率,r2好使用似然比r1:正类的期望频度为e+=5560/160=20.625 负类的期望频度为e=55100/160=34.375 r2:正类的期望频度为e+=260/160=0.75 负类的期望频度为e=2100/160=1.25 R(r1)=2 50log2(50/20.625)+5log2(5/34.375)=99.
11、9 R(r2)=2 2log2(2/0.75)+0log2(0/1.25)=5.66 r1比r2好,2023/10/14,数据挖掘:概念与技术,24,规则评估(续),考虑规则覆盖率的评估度量 n是规则覆盖的样例数,f+是规则覆盖的正例数,k是类的总数,p+是正类的先验概率 当规则的覆盖率很高时,两个度量都渐近地趋向于规则的准确率f+/n 继续前例r1的Laplace度量为51/57=89.47%,很接近它的准确率r2的Laplace度量(75%)比它的准确率小很多,2023/10/14,数据挖掘:概念与技术,25,规则评估(续),考虑规则的支持度计数的评估度量规则的支持度计数对应于它所覆盖的正
12、例数 FOIL信息增益(First Order Inductive Leaner information gain)设规则r:A+覆盖p0个正例和n0个反例;规则r:A B+覆盖p1个正例和n1个反例.扩展后规则的FOIL信息增益定义为 该度量与p1和p1/(p1+n1)成正比,所以它更倾向于选择那些高支持度计数和高准确率的规则 继续前例r1和r2的FOIL信息增益分别为43.12和2,因此规则r1比r2好,2023/10/14,数据挖掘:概念与技术,26,停止条件与规则剪枝,停止条件计算增益如果增益不显著,则丢弃新规则规则剪枝类似于决策树后剪枝降低错误剪枝:删除规则中的合取项 比较剪枝前后的
13、错误率 如果降低了错误率,则剪掉该合取项,2023/10/14,数据挖掘:概念与技术,27,直接方法:RIPPER,对于2类问题,选定一个类为正类,另一个为负类从正类学习规则负类时缺省类多类问题按类的大小(属于特定类的实例所占的比例)对诸类排序从最小的类开始学习规则,其余类都看做负类对次小类学习规则,如此下去,2023/10/14,数据挖掘:概念与技术,28,直接方法:RIPPER(续),规则增长:由空规则开始只要能够提高FOIL信息增益就增加一个合取项当规则不再覆盖负实例时就停止剪枝剪枝度量:v=(pn)/(p+n)p:验证集中被规则覆盖的正实例数 n:验证集中被规则覆盖的负实例数剪枝方法:
14、如果剪掉合取项可以提高v就剪,2023/10/14,数据挖掘:概念与技术,29,直接方法:RIPPER(续),建立规则集:使用顺序覆盖算找出覆盖当前正实例的最佳规则删除被规则覆盖的所有正实例和负实例当一个规则加入规则集时,计算新的描述长度当新的描述长度比已经得到的描述长度多d位时,就停止增加新规则,2023/10/14,数据挖掘:概念与技术,30,直接方法:RIPPER(续),优化规则集:对规则集R中的每个规则 r考虑2个替换的规则:替换规则(r*):重新增长新规则编辑的规则(r):把一个新的合取项增加到规则 r 比较替换前后的规则集 选择最小化MDL的规则集对剩下的正实例,重复规则产生和优化
15、,2023/10/14,数据挖掘:概念与技术,31,规则提取的间接方法,决策树从根结点到叶结点的每一条路径都可以表示为一个分类规则 路径中的测试条件构成规则前件的合取项,叶结点的类标号赋给规则后件,2023/10/14,数据挖掘:概念与技术,32,间接方法:C4.5rules(续),从未剪枝的决策树提取规则规则产生对每个规则 r:A y,考虑替换规则 r:A y 其中 A 由删除A的一个合取项得到比较r与所有r的悲观误差如果r的悲观误差小,则剪枝重复该过程,直到不能改进,2023/10/14,数据挖掘:概念与技术,33,间接方法:C4.5rules,规则定序不是对规则定序,而是对规则的子集定序
16、(class ordering)每个规则子集是一组具有相同规则后件(class)的规则计算每个子集的描述长度描述长度=L(error)+g L(model)g 是参数,考虑规则集中冗余属性(缺省值g=0.5),2023/10/14,数据挖掘:概念与技术,34,C4.5 vs C4.5rules vs RIPPER,2023/10/14,数据挖掘:概念与技术,35,基于规则的分类器的特征,表达能力与决策树一样高容易解释容易产生能够快速对新实例分类性能可与决策树相媲美,5.2 最近邻分类器,2023/10/14,数据挖掘:概念与技术,37,急切学习 vs 惰性学习,急切学习(Eager Learn
17、er)两步过程:(1)归纳(2)演绎惰性学习(lazy learner)把训练数据建模过程推迟到需要对样本分类时例子Rote-learner(死记硬背)记住所有的训练数据,仅当记录的属性值与一个训练记录完全匹配才对它分类最近邻(Nearest neighbor)使用“最近”的 k 个点(最近邻)进行分类,2023/10/14,数据挖掘:概念与技术,38,最近邻分类器,基本思想:If it walks like a duck,quacks like a duck,then its probably a duck,2023/10/14,数据挖掘:概念与技术,39,最近邻分类器,要求存放训练记录计算
18、记录间距离的度量k值,最近邻数对未知记录分类:计算域各训练记录的距离找出 k 个最近邻 使用最近邻的类标号决定未知记录的类标号(例如,多数表决),2023/10/14,数据挖掘:概念与技术,40,最近邻定义,记录x的k-最近邻是与x之间距离最小的k个训练数据点,2023/10/14,数据挖掘:概念与技术,41,1 nearest-neighbor,Voronoi Diagram,2023/10/14,数据挖掘:概念与技术,42,k-最近邻分类算法,k-最近邻分类算法1:令k是最近邻数目,D是训练样例的集合2:for 每个测试样例 z=(x,y)do3:计算z和每个样例(x,y)D之间的距离d(
19、x,x)4:选择离z最近的k个训练样例的集合Dz D5:6:end for 距离加权表决,2023/10/14,数据挖掘:概念与技术,43,k-最近邻,k值的选择:如果 k 太小,则对噪声点敏感如果 k 太大,邻域可能包含很 多其他类的点定标问题(规范化)属性可能需要规范化,防止距 离度量被具有很大值域的属性 所左右,2023/10/14,数据挖掘:概念与技术,44,k-NN的特点,k-NN的特点是一种基于实例的学习 需要一个邻近性度量来确定实例间的相似性或距离 不需要建立模型,但分类一个测试样例开销很大需要计算域所有训练实例之间的距离 基于局部信息进行预测,对噪声非常敏感 最近邻分类器可以生
20、成任意形状的决策边界 决策树和基于规则的分类器通常是直线决策边界 需要适当的邻近性度量和数据预处理 防止邻近性度量被某个属性左右,5.3 贝叶斯分类器,2023/10/14,数据挖掘:概念与技术,46,贝叶斯定理,每个记录用一个d维特征向量X=(x1,x2,xd)表示假定有k个类y1,y2,yk.给定X,X属于yj类的后验概率P(yj|X)满足贝叶斯(Bayes)定理MAP(maximum posteriori hypothesis,最大后验假设)将X指派到具有最大后验概率P(yj|X)的类yj,即将X指派到P(X|yj)P(yj)最大的类yj,2023/10/14,数据挖掘:概念与技术,47
21、,朴素贝叶斯分类,朴素贝叶斯分类(Nave Bayes Classifier)工作原理给定一个未知的数据样本X,分类法将预测X属于具有最高后验概率的类.即,未知的样本分配给类yj,当且仅当根据贝叶斯定理,我们有由于P(X)对于所有类为常数,只需要最大化P(X|yj)P(yj)即可.,2023/10/14,数据挖掘:概念与技术,48,朴素贝叶斯分类(续),估计P(yj)类yj的先验概率可以用下式估计 P(yj)=nj/n 其中,nj是类yj中的训练样本数,而n是训练样本总数 估计P(X|yj)为便于估计P(X|yj),假定类条件独立-给定样本的类标号,假定属性值条件地相互独立.于是,P(X|Y=
22、yj)可以用下式估计 其中,P(xi|yj)可以由训练样本估值,2023/10/14,数据挖掘:概念与技术,49,朴素贝叶斯分类(续),估计P(xi|yj)设第i个属性Ai是分类属性,则 P(xi|yj)=nij/nj其中nij是在属性Ai上具有值xi的yj类的训练样本数,而nj是yj类的训练样本数 设第i个属性Ai是连续值属性把Ai离散化假定Ai服从高斯分布 其中,ij,ij分别为给定yj类的训练样本在属性Ai上的均值和标准差,2023/10/14,数据挖掘:概念与技术,50,朴素贝叶斯分类,朴素贝叶斯分类器所需要的信息计算每个类的先验概率P(yj)P(yj)=nj/n 其中,nj是yi类的
23、训练样本数,而n是训练样本总数 对于离散属性Ai,设的不同值为ai1,ai2,ail,对于每个类yj,计算后验概率P(aik|yj),1 k lP(aik|yj)=nikj/nj其中nikj 是在属性Ai上具有值aik 的yj类的训练样本数,而nj是yj类的训练样本数 对于连续属性Ai 和每个类yj,计算yj类样本的均值ij,标准差ij,2023/10/14,数据挖掘:概念与技术,51,贝叶斯分类器:例,例:,P(Yes)=3/10P(No)=7/10P(有房=是|No)=3/7P(有房=否|No)=4/7P(有房=是|Yes)=0P(有房=否|Yes)=1P(婚姻状况=单身|No)=2/7P
24、(婚姻状况=离婚|No)=1/7P(婚姻状况=已婚|No)=4/7P(婚姻状况=单身|Yes)=2/3P(婚姻状况=离婚|Yes)=1/3P(婚姻状况=已婚|Yes)=0年收入:类=No:样本均值=110 样本方差=2975类=Yes:样本均值=90 样本方差=25,2023/10/14,数据挖掘:概念与技术,52,贝叶斯分类器:例(续),X=(有房=否,婚姻状况=已婚,年收入=$120K)计算P(X|No)和P(X|Yes)P(X|No)=P(有房=否|No)P(婚姻状况=已婚|No)P(年收入=$120K|No)=4/74/70.0072=0.0024 P(X|Yes)=P(有房=否|Ye
25、s)P(婚姻状况=已婚|Yes)P(年收入=$120K|Yes)=101.2109=0 计算P(X|No)P(No)和P(X|Yes)P(Yes)P(X|No)P(No)=0.0024 0.7=0.00168P(X|Yes)P(Yes)=0 0.3=0因为P(X|No)P(No)P(X|Yes)P(Yes),所以X分类为No,2023/10/14,数据挖掘:概念与技术,53,贝叶斯分类器,问题如果诸条件概率P(Xi=xi|Y=yj)中的一个为0,则它们的乘积(计算P(X|Y=yj)的表达式)为0很可能每个P(X|Y=yj)都为0解决方法使用Laplace 估计:原估计:P(Xi=xi|Y=yj
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据 挖掘 导论 分类 其他 技术

链接地址:https://www.31ppt.com/p-6296667.html