19 基于规则的分类器.ppt

第十九讲基于规则的分类器,主讲：王彦,1,数据挖掘,2020年6月3日星期三,数据挖掘导论,2,基于规则的分类器,使用一组“ifthen”规则进行分类规则:(Condition)y其中Condition是属性测试的合取y是类标号左部:规则的前件或前提右部:规则的结论分类规则的例子:(胎生=否)(飞行动物=是)鸟类,2020年6月3日星期三,数据挖掘导论,3,基于规则的分类器:例,脊椎动物数据集,2020年6月3日星期三,数据挖掘导论,4,基于规则的分类器的使用,规则r覆盖实例x，如果该实例的属性满足规则r的条件r1：（胎生=否）（飞行动物=是）鸟类r2：（胎生=否）（水生动物=是）鱼类r3：（胎生=是）（体温=恒温）哺乳类r4：（胎生=否）（飞行动物=否）爬行类r5：（水生动物=半）两栖类规则r1覆盖“鹰”=鸟类规则r3覆盖“灰熊”=哺乳类,2020年6月3日星期三,数据挖掘导论,5,规则的质量,用覆盖率和准确率度量规则的覆盖率（coverage）:满足规则前件的记录所占的比例规则的准确率（accuracy）:在满足规则前件的记录中，满足规则后件的记录所占的比例规则:(Status=Single)NoCoverage=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,2020年6月3日星期三,数据挖掘导论,6,如何用规则分类,一组规则r1：（胎生=否）（飞行动物=是）鸟类r2：（胎生=否）（水生动物=是）鱼类r3：（胎生=是）（体温=恒温）哺乳类r4：（胎生=否）（飞行动物=否）爬行类r5：（水生动物=半）两栖类待分类记录狐猴触发规则r3,它分到哺乳类海龟触发规则r4和r5-冲突狗鲨未触发任何规则,2020年6月3日星期三,数据挖掘导论,7,规则的分类器的特征,互斥规则集每个记录最多被一个规则覆盖如果规则都是相互独立的，分类器包含互斥规则如果规则集不是互斥的一个记录可能被多个规则触发如何处理?有序规则集基于规则的序vs基于类的序无序规则集使用投票策略,2020年6月3日星期三,数据挖掘导论,8,规则的分类器的特征,穷举规则集每个记录至少被一个规则覆盖如果规则集涵盖了属性值的所有可能组合，则规则集具有穷举覆盖如果规则集不是穷举的一个记录可能不被任何规则触发如何处理?使用缺省类,有序规则集,根据规则优先权将规则排序定秩（rank）有序规则集又成决策表（decisionlist）对记录进行分类时由被触发的，具有最高秩的规则确定记录的类标号如果没有规则被触发，则指派到缺省类,2020年6月3日星期三,数据挖掘导论,10,规则的排序方案,基于规则的序根据规则的质量排序基于类的序属于同一类的规则放在一起基于类信息（如类的分布、重要性）对每类规则排序,2020年6月3日星期三,数据挖掘导论,11,如何建立基于规则的分类器,直接方法:直接由数据提取规则把属性空间分为较小的子空间，以便于属于一个子空间的所有记录可以使用一个分类规则进行分类间接方法:由其他分类模型提取规则(例如，从决策树、神经网络等)例如:C4.5rules,2020年6月3日星期三,数据挖掘导论,12,规则提取的直接方法:顺序覆盖,基本思想依次对每个类建立一个或多个规则对第i类建立规则第i类记录为正例，其余为负例建立一个第i类的规则r，尽可能地覆盖正例，而不覆盖负例删除r覆盖的所有记录，在剩余数据集上学习下一个规则，直到所有第i类记录都被删除,2020年6月3日星期三,数据挖掘导论,13,直接方法:顺序覆盖,顺序覆盖（sequentialcovering）算法1：令E是训练记录，A是属性值对的集合(Aj,vj)2：令Yo是类的有序集y1,y2,.,yk3：令R=是初始规则列表4：for每个类yYoykdo5：while终止条件不满足do6：rLearn-One-Rule(E,A,y)7：从E中删除被r覆盖的训练记录8：追加r到规则列表尾部：RRr9：endwhile10：endfor11：把默认规则yk插入到规则列表R尾部,2020年6月3日星期三,数据挖掘导论,14,顺序覆盖:例,(a)Originaldata,(b)Step1,(c)Step2,(c)Step3,2020年6月3日星期三,数据挖掘导论,15,Learn-One-Rule函数,Learn-one-rule函数的目标是提取一个分类规则，该规则覆盖训练集中的大量正例，仅覆盖少量反例。规则增长实例删除规则评估停止准则规则剪枝,2020年6月3日星期三,数据挖掘导论,16,规则增长,两种策略一般到特殊从初始规则r:y开始反复加入合取项，得到更特殊的规则，直到不能再加入特殊到一般随机地选择一个正例作为初始规则反复删除合取项，得到更一般的规则，直到不能再删除问题加入/删除合取项有多种选择，如何选择？何时停止加入/删除合取项？需要评估标准,2020年6月3日星期三,数据挖掘导论,17,规则增长:例,特殊到一般,一般到特殊,2020年6月3日星期三,数据挖掘导论,18,规则评估(续),常用的度量准确率、似然比、Laplace、M-estimate、FOIL信息增益准确率Accuracy，n:被规则覆盖的实例数，nc:被规则正确分类的实例数问题：准确率高的规则可能覆盖率太低似然比（越高越好）k是类的个数fi是被规则覆盖的类i的样本的观测频度ei是规则作随机猜测的期望频度,2020年6月3日星期三,数据挖掘导论,19,规则评估:例,例:60个正例和100个反例规则r1：覆盖50个正例和5个反例(acc=90.9%)；规则r2：覆盖2个正例和0个反例(acc=100%)使用准确率,r2好使用似然比r1:正类的期望频度为e+=5560/160=20.625;负类的期望频度为e=55100/160=34.375r2:正类的期望频度为e+=260/160=0.75;负类的期望频度为e=2100/160=1.25R(r1)=250log2(50/20.625)+5log2(5/34.375)=99.9R(r2)=22log2(2/0.75)+0log2(0/1.25)=5.66r1比r2好,2020年6月3日星期三,数据挖掘导论,20,规则评估(续),考虑规则覆盖率的评估度量n是规则覆盖的样例数，f+是规则覆盖的正例数，k是类的总数，p+是正类的先验概率当规则的覆盖率很高时，两个度量都渐近地趋向于规则的准确率f+/n继续前例r1的Laplace度量为51/57=89.47%，很接近它的准确率r2的Laplace度量（75%）比它的准确率小很多,2020年6月3日星期三,数据挖掘导论,21,规则评估(续),考虑规则的支持度计数的评估度量规则的支持度计数对应于它所覆盖的正例数FOIL信息增益（FirstOrderInductiveLeanerinformationgain）设规则r:A+覆盖p0个正例和n0个反例;规则r:AB+覆盖p1个正例和n1个反例.扩展后规则的FOIL信息增益定义为该度量与p1和p1/(p1+n1)成正比，所以它更倾向于选择那些高支持度计数和高准确率的规则继续前例r1和r2的FOIL信息增益分别为43.12和2，因此规则r1比r2好,2020年6月3日星期三,数据挖掘导论,22,规则剪枝,停止条件计算增益如果增益不显著,则丢弃新规则规则剪枝类似于决策树后剪枝降低错误剪枝:删除规则中的合取项比较剪枝前后的错误率如果降低了错误率,则剪掉该合取项,2020年6月3日星期三,数据挖掘导论,23,直接方法:RIPPER,对于2类问题,选定一个类为正类，另一个为负类从正类学习规则负类时缺省类多类问题按类的大小（属于特定类的实例所占的比例）对诸类排序从最小的类开始学习规则，其余类都看做负类对次小类学习规则，如此下去,2020年6月3日星期三,数据挖掘导论,24,直接方法:RIPPER(续),规则增长:由空规则开始只要能够提高FOIL信息增益就增加一个合取项当规则不再覆盖负实例时就停止剪枝剪枝度量:v=(pn)/(p+n)p:验证集中被规则覆盖的正实例数n:验证集中被规则覆盖的负实例数剪枝方法:如果剪掉合取项可以提高v就剪,2020年6月3日星期三,数据挖掘导论,25,直接方法:RIPPER(续),建立规则集:使用顺序覆盖算找出覆盖当前正实例的最佳规则删除被规则覆盖的所有正实例和负实例当一个规则加入规则集时，计算新的描述长度当新的描述长度比已经得到的描述长度多d位时，就停止增加新规则,2020年6月3日星期三,数据挖掘导论,26,直接方法:RIPPER(续),优化规则集:对规则集R中的每个规则r考虑2个替换的规则:替换规则(r*):重新增长新规则编辑的规则(r):把一个新的合取项增加到规则r比较替换前后的规则集选择最小化MDL的规则集对剩下的正实例，重复规则产生和优化,2020年6月3日星期三,数据挖掘导论,27,规则提取的间接方法,决策树从根结点到叶结点的每一条路径都可以表示为一个分类规则路径中的测试条件构成规则前件的合取项，叶结点的类标号赋给规则后件,2020年6月3日星期三,数据挖掘导论,28,间接方法:C4.5rules(续),从未剪枝的决策树提取规则规则产生对每个规则r:Ay,考虑替换规则r:Ay其中A由删除A的一个合取项得到比较r与所有r的悲观误差如果r的悲观误差小，则剪枝重复该过程，直到不能改进,2020年6月3日星期三,数据挖掘导论,29,间接方法:C4.5rules,