1、数据挖掘导论,Pang-ning Tan,Michael Stieinbach,and Vipin Kumar著Pearson Education LTD.范明 等译人民邮电出版社,第5章 分类:其他技术,基于规则的分类最近邻分类贝叶斯分类神经网络支持向量机组合方法不平衡类问题多类问题,5.1 基于规则的分类器,2023年8月5日星期六,数据挖掘导论,4,基于规则的分类器,使用一组“ifthen”规则进行分类规则:(Condition)y其中 Condition 是属性测试的合取 y 是类标号左部:规则的前件或前提右部:规则的结论分类规则的例子:(Blood Type=Warm)(Lay Eg
2、gs=Yes)Birds(Taxable Income 50K)(Refund=Yes)Evade=No,2023年8月5日星期六,数据挖掘导论,5,基于规则的分类器:例,脊椎动物数据集,2023年8月5日星期六,数据挖掘导论,6,基于规则的分类器的使用,规则 r 覆盖 实例 x，如果该实例的属性满足规则r的条件r1：（胎生=否）（飞行动物=是）鸟类r2：（胎生=否）（水生动物=是）鱼类r3：（胎生=是）（体温=恒温）哺乳类r4：（胎生=否）（飞行动物=否）爬行类r5：（水生动物=半）两栖类规则r1覆盖“鹰”=鸟类规则r3 覆盖“灰熊”=哺乳类,2023年8月5日星期六,数据挖掘导论,7,规则
3、的质量,用覆盖率和准确率度量规则的覆盖率（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,90K,Yes,10
4、,2023年8月5日星期六,数据挖掘导论,8,如何用规则分类,一组规则r1：（胎生=否）（飞行动物=是）鸟类r2：（胎生=否）（水生动物=是）鱼类r3：（胎生=是）（体温=恒温）哺乳类r4：（胎生=否）（飞行动物=否）爬行类r5：（水生动物=半）两栖类待分类记录狐猴触发规则 r3,它分到哺乳类海龟触发规则r4和 r5-冲突狗鲨未触发任何规则,2023年8月5日星期六,数据挖掘导论,9,规则的分类器的特征,互斥规则集每个记录最多被一个规则覆盖如果规则都是相互独立的，分类器包含互斥规则如果规则集不是互斥的一个记录可能被多个规则触发如何处理?有序规则集基于规则的序 vs 基于类的序 无序规则集 使用
5、投票策略,2023年8月5日星期六,数据挖掘导论,10,规则的分类器的特征(续),穷举规则集每个记录至少被一个规则覆盖如果规则集涵盖了属性值的所有可能组合，则规则集具有穷举覆盖如果规则集不是穷举的一个记录可能不被任何规则触发如何处理?使用缺省类,2023年8月5日星期六,数据挖掘导论,11,有序规则集,根据规则优先权将规则排序定秩（rank）有序规则集又成决策表（decision list）对记录进行分类时由被触发的，具有最高秩的规则确定记录的类标号如果没有规则被触发，则指派到缺省类,2023年8月5日星期六,数据挖掘导论,12,规则定序方案,基于规则的序根据规则的质量排序基于类的序属于同一类
6、的规则放在一起基于类信息（如类的分布、重要性）对每类规则排序,2023年8月5日星期六,数据挖掘导论,13,如何建立基于规则的分类器,直接方法:直接由数据提取规则例如:RIPPER,CN2,Holtes 1R间接方法:由其他分类模型提取规则(例如，从决策树、神经网络等).例如:C4.5rules,2023年8月5日星期六,数据挖掘导论,14,直接方法:顺序覆盖,基本思想依次对每个类建立一个或多个规则对第i类建立规则第i类记录为正例，其余为负例建立一个第i类的规则r，尽可能地覆盖正例，而不覆盖负例删除r覆盖的所有记录，在剩余数据集上学习下一个规则，直到所有第i类记录都被删除,2023年8月5日星
7、期六,数据挖掘导论,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年8月5日星期六,数据挖掘导论,16,顺序覆盖:例,(a)Original data,
8、(b)Step 1,(c)Step 2,(c)Step 3,2023年8月5日星期六,数据挖掘导论,17,删除实例,为什么要删除实例?否则,下一个规则将与前面的规则相同为什么删除正实例?确保下一个规则不同为什么删除负实例?防止低估规则的准确率比较图中的规则 R2 和 R3,2023年8月5日星期六,数据挖掘导论,18,Learn-One-Rule,规则增长实例删除规则评估停止准则规则剪枝,2023年8月5日星期六,数据挖掘导论,19,规则增长,两种策略一般到特殊从初始规则r:y开始反复加入合取项，得到更特殊的规则，直到不能再加入 特殊到一般随机地选择一个正例作为初始规则反复删除合取项，得到更一
9、般的规则，直到不能再删除问题加入/删除合取项有多种选择，如何选择？何时停止加入/删除合取项？需要评估标准,2023年8月5日星期六,数据挖掘导论,20,规则增长:例,一般到特殊,特殊到一般,2023年8月5日星期六,数据挖掘导论,21,规则评估,常用的度量准确率似然比LaplaceM-estimateFOIL信息增益,2023年8月5日星期六,数据挖掘导论,22,规则评估(续),准确率Accuracyn:被规则覆盖的实例数nc:被规则正确分类的实例数问题：准确率高的规则可能覆盖率太低似然比（越高越好）k是类的个数fi是被规则覆盖的类i的样本的观测频度ei是规则作随机猜测的期望频度,2023年8
10、月5日星期六,数据挖掘导论,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.9 R(r2)=2 2log2(2/0.75)+0log2(0/1.25)=5.
11、66 r1比r2好,2023年8月5日星期六,数据挖掘导论,24,规则评估(续),考虑规则覆盖率的评估度量 n是规则覆盖的样例数，f+是规则覆盖的正例数，k是类的总数，p+是正类的先验概率 当规则的覆盖率很高时，两个度量都渐近地趋向于规则的准确率f+/n 继续前例r1的Laplace度量为51/57=89.47%，很接近它的准确率r2的Laplace度量（75%）比它的准确率小很多,2023年8月5日星期六,数据挖掘导论,25,规则评估(续),考虑规则的支持度计数的评估度量规则的支持度计数对应于它所覆盖的正例数 FOIL信息增益（First Order Inductive Leaner inf
12、ormation gain）设规则r:A+覆盖p0个正例和n0个反例;规则r:A B+覆盖p1个正例和n1个反例.扩展后规则的FOIL信息增益定义为 该度量与p1和p1/(p1+n1)成正比，所以它更倾向于选择那些高支持度计数和高准确率的规则 继续前例r1和r2的FOIL信息增益分别为43.12和2，因此规则r1比r2好,2023年8月5日星期六,数据挖掘导论,26,停止条件与规则剪枝,停止条件计算增益如果增益不显著,则丢弃新规则规则剪枝类似于决策树后剪枝降低错误剪枝:删除规则中的合取项 比较剪枝前后的错误率 如果降低了错误率,则剪掉该合取项,2023年8月5日星期六,数据挖掘导论,27,直接
13、方法:RIPPER,对于2类问题,选定一个类为正类，另一个为负类从正类学习规则负类时缺省类多类问题按类的大小（属于特定类的实例所占的比例）对诸类排序从最小的类开始学习规则，其余类都看做负类对次小类学习规则，如此下去,2023年8月5日星期六,数据挖掘导论,28,直接方法:RIPPER(续),规则增长:由空规则开始只要能够提高FOIL信息增益就增加一个合取项当规则不再覆盖负实例时就停止剪枝剪枝度量:v=(pn)/(p+n)p:验证集中被规则覆盖的正实例数 n:验证集中被规则覆盖的负实例数剪枝方法:如果剪掉合取项可以提高v就剪,2023年8月5日星期六,数据挖掘导论,29,直接方法:RIPPER(
14、续),建立规则集:使用顺序覆盖算找出覆盖当前正实例的最佳规则删除被规则覆盖的所有正实例和负实例当一个规则加入规则集时，计算新的描述长度当新的描述长度比已经得到的描述长度多d位时，就停止增加新规则,2023年8月5日星期六,数据挖掘导论,30,直接方法:RIPPER(续),优化规则集:对规则集R中的每个规则 r考虑2个替换的规则:替换规则(r*):重新增长新规则编辑的规则(r):把一个新的合取项增加到规则 r 比较替换前后的规则集 选择最小化MDL的规则集对剩下的正实例，重复规则产生和优化,2023年8月5日星期六,数据挖掘导论,31,规则提取的间接方法,决策树从根结点到叶结点的每一条路径都可以
15、表示为一个分类规则 路径中的测试条件构成规则前件的合取项，叶结点的类标号赋给规则后件,2023年8月5日星期六,数据挖掘导论,32,间接方法:C4.5rules(续),从未剪枝的决策树提取规则规则产生对每个规则 r:A y,考虑替换规则 r:A y 其中 A 由删除A的一个合取项得到比较r与所有r的悲观误差如果r的悲观误差小，则剪枝重复该过程，直到不能改进,2023年8月5日星期六,数据挖掘导论,33,间接方法:C4.5rules,规则定序不是对规则定序，而是对规则的子集定序(class ordering)每个规则子集是一组具有相同规则后件(class)的规则计算每个子集的描述长度描述长度=L
16、(error)+g L(model)g 是参数，考虑规则集中冗余属性(缺省值g=0.5),2023年8月5日星期六,数据挖掘导论,34,C4.5 vs C4.5rules vs RIPPER,2023年8月5日星期六,数据挖掘导论,35,基于规则的分类器的特征,表达能力与决策树一样高容易解释容易产生能够快速对新实例分类性能可与决策树相媲美,5.2 最近邻分类器,2023年8月5日星期六,数据挖掘导论,37,急切学习 vs 惰性学习,急切学习（Eager Learner）两步过程:(1)归纳(2)演绎惰性学习（lazy learner）把训练数据建模过程推迟到需要对样本分类时例子Rote-lea
17、rner（死记硬背）记住所有的训练数据，仅当记录的属性值与一个训练记录完全匹配才对它分类最近邻（Nearest neighbor）使用“最近”的 k 个点(最近邻)进行分类,2023年8月5日星期六,数据挖掘导论,38,最近邻分类器,基本思想:If it walks like a duck,quacks like a duck,then its probably a duck,2023年8月5日星期六,数据挖掘导论,39,最近邻分类器,要求存放训练记录计算记录间距离的度量k值,最近邻数对未知记录分类:计算域各训练记录的距离找出 k 个最近邻 使用最近邻的类标号决定未知记录的类标号(例如,多数表
18、决),2023年8月5日星期六,数据挖掘导论,40,最近邻定义,记录x的k-最近邻是与x之间距离最小的k个训练数据点,2023年8月5日星期六,数据挖掘导论,41,1 nearest-neighbor,Voronoi Diagram,2023年8月5日星期六,数据挖掘导论,42,k-最近邻分类算法,k-最近邻分类算法1：令k是最近邻数目，D是训练样例的集合2：for 每个测试样例 z=(x,y)do3：计算z和每个样例(x,y)D之间的距离d(x,x)4：选择离z最近的k个训练样例的集合Dz D5：6：end for 距离加权表决,2023年8月5日星期六,数据挖掘导论,43,k-最近邻,k值
19、的选择:如果 k 太小,则对噪声点敏感如果 k 太大,邻域可能包含很 多其他类的点定标问题（规范化）属性可能需要规范化，防止距 离度量被具有很大值域的属性 所左右,2023年8月5日星期六,数据挖掘导论,44,k-NN的特点,k-NN的特点是一种基于实例的学习 需要一个邻近性度量来确定实例间的相似性或距离 不需要建立模型，但分类一个测试样例开销很大需要计算域所有训练实例之间的距离 基于局部信息进行预测，对噪声非常敏感 最近邻分类器可以生成任意形状的决策边界 决策树和基于规则的分类器通常是直线决策边界 需要适当的邻近性度量和数据预处理 防止邻近性度量被某个属性左右,5.3 贝叶斯分类器,2023
20、年8月5日星期六,数据挖掘导论,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年8月5日星期六,数据挖掘导论,47,朴素贝叶斯分类,朴素贝叶斯分类(Nave Bayes Classifier)工作原理给定一个未知的数据样本X,分类法将预测X属于具有最高后验概率的类.即,未知的样本分
21、配给类yj,当且仅当根据贝叶斯定理,我们有由于P(X)对于所有类为常数,只需要最大化P(X|yj)P(yj)即可.,2023年8月5日星期六,数据挖掘导论,48,朴素贝叶斯分类(续),估计P(yj)类yj的先验概率可以用下式估计 P(yj)=nj/n 其中,nj是类yj中的训练样本数,而n是训练样本总数 估计P(X|yj)为便于估计P(X|yj),假定类条件独立-给定样本的类标号,假定属性值条件地相互独立.于是,P(X|Y=yj)可以用下式估计 其中,P(xi|yj)可以由训练样本估值,2023年8月5日星期六,数据挖掘导论,49,朴素贝叶斯分类(续),估计P(xi|yj)设第i个属性Ai是分
22、类属性,则 P(xi|yj)=nij/nj其中nij是在属性Ai上具有值xi的yj类的训练样本数,而nj是yj类的训练样本数 设第i个属性Ai是连续值属性把Ai离散化假定Ai服从高斯分布 其中,ij,ij分别为给定yj类的训练样本在属性Ai上的均值和标准差,2023年8月5日星期六,数据挖掘导论,50,朴素贝叶斯分类,朴素贝叶斯分类器所需要的信息计算每个类的先验概率P(yj)P(yj)=nj/n 其中,nj是yi类的训练样本数,而n是训练样本总数 对于离散属性Ai，设的不同值为ai1,ai2,ail，对于每个类yj，计算后验概率P(aik|yj),1 k lP(aik|yj)=nikj/nj其
23、中nikj 是在属性Ai上具有值aik 的yj类的训练样本数,而nj是yj类的训练样本数 对于连续属性Ai 和每个类yj，计算yj类样本的均值ij,标准差ij,2023年8月5日星期六,数据挖掘导论,51,贝叶斯分类器:例,例:,P(Yes)=3/10P(No)=7/10P(有房=是|No)=3/7P(有房=否|No)=4/7P(有房=是|Yes)=0P(有房=否|Yes)=1P(婚姻状况=单身|No)=2/7P(婚姻状况=离婚|No)=1/7P(婚姻状况=已婚|No)=4/7P(婚姻状况=单身|Yes)=2/3P(婚姻状况=离婚|Yes)=1/3P(婚姻状况=已婚|Yes)=0年收入：类=N
24、o：样本均值=110 样本方差=2975类=Yes：样本均值=90 样本方差=25,2023年8月5日星期六,数据挖掘导论,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(有房=否|Yes)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
25、.7=0.00168P(X|Yes)P(Yes)=0 0.3=0因为P(X|No)P(No)P(X|Yes)P(Yes),所以X分类为No,2023年8月5日星期六,数据挖掘导论,53,贝叶斯分类器,问题如果诸条件概率P(Xi=xi|Y=yj)中的一个为0，则它们的乘积（计算P(X|Y=yj)的表达式）为0很可能每个P(X|Y=yj)都为0解决方法使用Laplace 估计:原估计:P(Xi=xi|Y=yj)=nij/nj,2023年8月5日星期六,数据挖掘导论,54,贝叶斯分类器的特点,对孤立的噪声点的鲁棒性个别点对概率估计的影响很小容易处理缺失值在估计概率时忽略缺失值的训练实例对不相关属性的
26、鲁棒性各类在不相关属性上具有类似分布类条件独立假设可能不成立 使用其他技术，如贝叶斯信念网络（Bayesian Belief Networks，BBN）,2023年8月5日星期六,数据挖掘导论,55,贝叶斯信念网络,贝叶斯信念网络(Bayesian belief network)允许在变量的子集间定义类条件独立性 因果关系图模型 表示变量之间的依赖给出联合概率分布的说明图示节点:随机变量边:依赖X,Y 是Z的父节点/前驱,并且Y 是P的父节点/前驱Z 和P之间没有依赖关系图中没有环,2023年8月5日星期六,数据挖掘导论,56,贝叶斯信念网络:例,变量LungCance(LC)值的条件概率表(
27、CPT),给出其双亲结点FamilyHistory和Smoke的每个可能值的组合的条件概率,2023年8月5日星期六,数据挖掘导论,57,贝叶斯信念网络:例(续),给出了LungCancer的CPT.对于其双亲值的每个可能组合,表中给出了LungCancer的每个值的条件概率.例如,由左上角和右下角,我们分别看到 P(LungCancer=“yes”|FamilyHistory=“yes”,Smoker=“yes”)=0.8 P(LungCancer=“no”|FamilyHistory=“no”,Smoker=“no”)=0.9 对应于属性或变量Z1,Zn的任意元组(z1,zn)的联合概率由
28、下式计算其中,P(zi|parents(zi)的值对应于Zi的CPT中的表目,2023年8月5日星期六,数据挖掘导论,58,训练贝叶斯信念网络,若干情况给定网络结构和所有可观测变量只需要学习CPT网络结构已知,而某些变量是隐藏的使用梯度下降法或类似于神经网络的方法训练信念网络网络结构未知,所有的变量可以观测搜索模型空间,构造网络拓扑结构网络结构未知,所有变量是隐藏的没有已知的好算法D.Heckerman,Bayesian networks for data mining,2023年8月5日星期六,数据挖掘导论,59,训练贝叶斯信念网络,梯度下降法设S是s个训练样本X1,X2,.,Xs的集合,w
29、ijk是具有双亲Ui=uik的变量Y=yij的CPT项 wijk可以看作权,类似于神经网络中隐藏单元的权.权的集合记作w 这些权被初始化为随机概率值.梯度下降策略采用贪心爬山法.在每次迭代中,修改这些权,并最终收敛到一个局部最优解 基于w的每个可能设置都等可能的假定,该方法搜索能最好地对数据建模wijk值.目标是最大化,2023年8月5日星期六,数据挖掘导论,60,训练贝叶斯信念网络:梯度下降法,给定网络结构和wijk的初值,该算法按以下步骤处理 计算梯度：对每个i,j,k，计算 沿梯度方向前进一小步:用下式更新权值 l是表示步长的学习率,设置为一个小常数 重新规格化权值：由于权值wijk是概
30、率值,它们必须在0.0和1.0之间,并且对于所有的i,k，必须有,2023年8月5日星期六,数据挖掘导论,61,BBN的特点,BBN提供了一种用图形模型来捕获特定领域的先验知识的方法。网络还可以用来对变量间的因果依赖关系进行编码构造网络可能既费时又费力。然而，一旦网络结构确定下来，添加新变量就十分容易贝叶斯网络很适合处理不完整的数据。对有属性遗漏的实例可以通过对该属性的所有可能取值的概率求和或求积分来加以处理因为数据和先验知识以概率的方式结合起来了，所以该方法对模型的过分拟合问题是 非常鲁棒的,2023年8月5日星期六,数据挖掘导论,62,使用BBN进行推理举例,E:锻炼,D:饮食,HD:心脏
31、病,Hb:胸口痛,BP:血压,CP:胸痛,2023年8月5日星期六,数据挖掘导论,63,情况一：没有先验信息,通过计算先验概率P(HD=Yes)和P(HD=No)来确定一个人是否可能患心脏病 设Yes,No表示锻炼的两个值，健康,不健康表示饮食的两个值，由全概率公式 P(HD=Yes)=0.250.70.25+0.450.70.75+0.550.30.25+0.750.30.75=0.49因为P(HD=No)=1P(HD=Yes)=0.51，所以，此人不得心脏病的机率略微大一点,2023年8月5日星期六,数据挖掘导论,64,情况二：高血压,如果一个人有高血压，可以通过比较后验概率P(HD=Ye
32、s|BP=高)和P(HD=No|BP=高)来诊断他是否患有心脏病 先用全概率公式，计算P(BP=高)P(BP=高)=0.850.49+0.20.51=0.5185其中Yes,No 用贝叶斯公式计算此人患心脏病的后验概率,2023年8月5日星期六,数据挖掘导论,65,情况三,情况三：高血压、饮食健康、经常锻炼身体患心脏病的后验概率,5.4 人工神经网络,2023年8月5日星期六,数据挖掘导论,67,神经网络,神经网络最早是由心理学家和神经学家提出的,旨在寻求开发和测试神经的计算模拟 神经网络是一组连接的输入/输出单元,其中每个连接都与一个权相关联 在学习阶段,通过调整神经网络的权,使得能够预测输
33、入样本的正确类标记神经网络的优点对噪音数据的高承受能力对未知样本的分类能力 神经网络缺点需要很长的训练时间,因而对于有足够长训练时间的应用更合适很难解释蕴涵在学习权之中的符号含义 它需要大量的参数,这些通常主要靠经验确定,如网络拓扑或“结构”,2023年8月5日星期六,数据挖掘导论,68,多层前馈神经网络,后向传播是一种神经网络学习算法 后向传播算法在多层前馈(multilayer feed-forward)神经网络上学习 例:一个多层前馈神经网络训练样本X=x1,x2,.,xi馈入输入层.每层之间存在加权连接;其中,wij表示由某层的单元j到前一层的单元i的权,2023年8月5日星期六,数据挖掘导论,69,多层前馈神经网络(续),输入同时提供给称作输入层的单元层 隐藏层的数量是任意的,实践中通常只用一层 输出层发布给定样本的网络预测 隐藏层和输出层的单元,有时称作neurodes(源于符
