1主讲人：丁兆云第七课 规则和最近邻分类器 17607310865 https:/ 基于规则的分类l使用一组“ifthen”规则进行分类l规则:(Condition)yl其中 Condition 是属性测试的合取 y 是类标号l左部:规则的前件或前提（Rule antecedent）l右部:规则的结论（Rule consequent）l分类规则的例子:(Blood Type=Warm)(Lay Eggs=Yes)Birds(Taxable Income 鸟类名称体温表皮覆盖胎生水生动物飞行动物有腿冬眠类标号鹰灰熊 恒温恒温羽毛软毛否是否否是否是是否是？6根据规则集，灰熊属于什么类别鸟鱼哺乳爬行ABCD提交r1：（胎生=否）（飞行动物=是）鸟类r2：（胎生=否）（水生动物=是）鱼类r3：（胎生=是）（体温=恒温）哺乳类r4：（胎生=否）（飞行动物=否）爬行类r5：（水生动物=半）两栖类单选题1分71.1 基于规则的分类：例l规则 r 覆盖 实例 x（记录），如果该实例的属性满足规则r的条件r1：（胎生=否）（飞行动物=是）鸟类r2：（胎生=否）（水生动物=是）鱼类r3：（胎生=是）（体温=恒温）哺乳类r4：（胎生=否）（飞行动物=否）爬行类r5：（水生动物=半）两栖类l规则r1覆盖“鹰”=鸟类l规则r3 覆盖“灰熊”=哺乳类名称体温表皮覆盖胎生水生动物飞行动物有腿冬眠类标号鹰灰熊 恒温恒温羽毛软毛否是否否是否是是否是？81.2 规则的质量 l用覆盖率和准确率度量l规则的覆盖率（Coverage）:l满足规则前件的记录所占的比例l规则的准确率（Accuracy）:l在满足规则前件的记录中，满足规则后件的记录所占的比例l规则:(Status=Single)NolCoverage=40%,Accuracy=50%TidRefundMarital StayusTaxable IncomeClass12345678910YesNoNo YesNoNo YesNoNo NoSingleMarriedSingleMarriedDivorcedMarriedDivorcedSingleMarriedSingle125K100K70K120K95K60K220K85K75K90K NoNoNoNoYesNoNoYesNoYes91.3 如何用规则分类l一组规则r1：（胎生=否）（飞行动物=是）鸟类r2：（胎生=否）（水生动物=是）鱼类r3：（胎生=是）（体温=恒温）哺乳类r4：（胎生=否）（飞行动物=否）爬行类r5：（水生动物=半）两栖类l待分类记录l狐猴触发规则 r3,它分到哺乳类l海龟触发规则r4和 r5 冲突l狗鲨未触发任何规则名称体温胎生飞行动物水生动物类狐猴海龟狗鲨 恒温冷血冷血是否是否否否否半水生是？10l互斥规则集l每个记录最多被一个规则覆盖l如果规则都是相互独立的，分类器包含互斥规则l如果规则集不是互斥的l一个记录可能被多个规则触发l如何处理?有序规则集 基于规则的序 vs 基于类的序 无序规则集 在无序规则方案中，允许一条记录触发多条规则，规则被触发时视为对其相应类的一次投票，然后计算不同类的票数（可以使用加权方式）来决定记录的类所属。
1.4 规则分类的特征r1：（胎生=否）（飞行动物=是）鸟类r2：（胎生=否）（水生动物=是）鱼类r3：（胎生=是）（体温=恒温）哺乳类r4：（胎生=否）（飞行动物=否）爬行类r5：（水生动物=半）两栖类海龟触发规则r4和r6冲突111.4 规则分类的特征l穷举规则集l每个记录至少被一个规则覆盖l如果规则集涵盖了属性值的所有可能组合，则规则集具有穷举覆盖l如果规则集不是穷举的l一个记录可能不被任何规则触发l如何处理?使用缺省类12规则分类具有下列哪些特征互斥规则集非互斥规则集穷举规则集非穷举规则集ABCD提交多选题1分131.4.1 有序规则集l根据规则优先权将规则排序定秩（rank）l有序规则集又成决策表（decision list）l对记录进行分类时l由被触发的，具有最高秩的规则确定记录的类标号l如果没有规则被触发，则指派到缺省类r1：（胎生=否）（飞行动物=是）鸟类r2：（胎生=否）（水生动物=是）鱼类r3：（胎生=是）（体温=恒温）哺乳类r4：（胎生=否）（飞行动物=否）爬行类r5：（水生动物=半）两栖类名称体温胎生飞行动物水生动物类海龟冷血否否半水生？141.4.2 规则定序方案l基于规则的序l根据规则的质量排序（覆盖率(coverage)和准确率(accuracy)）l基于类的序l属于同一类的规则放在一起l基于类信息（如类的分布、重要性）对每类规则排序基于规则的排序（表皮覆盖=羽毛,飞行动物=是）鸟类（体温=恒温,胎生=是）哺乳类（体温=恒温,胎生=否）鸟类（水生动物=半）两栖类（表皮覆盖=鳞片,水生动物=否）爬行类（表皮覆盖=鳞片,水生动物=是）鱼类（表皮覆盖=无）两栖类 基于类的排序（表皮覆盖=羽毛,飞行动物=是）鸟类（体温=恒温,胎生=否）鸟类（体温=恒温,胎生=是）哺乳类（水生动物=半）两栖类（表皮覆盖=无）两栖类（表皮覆盖=鳞片,水生动物=否）爬行类（表皮覆盖=鳞片,水生动物=是）鱼类 151.5 如何建立基于规则的分类器l直接方法:l直接由数据提取规则l例如:RIPPER,Holtes 1Rl间接方法:l由其他分类模型提取规则(例如，从决策树等).l例如:C4.5rulesWilliam W.CohenRobert Holte161.5.1 直接方法：顺序覆盖l基本思想l依次对每个类建立一个或多个规则l对第i类建立规则第i类记录为正例，其余为负例建立一个第i类的规则r，尽可能地覆盖正例，而不覆盖负例（即构建一个正例的规则）删除r覆盖的所有记录，在剩余数据集上学习下一个规则，直到所有第i类记录都被删除17l顺序覆盖（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尾部 2.1 直接方法:顺序覆盖181.5.1 直接方法：顺序覆盖(a)Original data(b)Step 1(c)Step 2(c)Step 3191.5.2 删除实例名称体温表皮覆盖胎生水生动物飞行动物有腿冬眠类标号人类蟒蛇鲑鱼鲸青蛙巨蜥蝙蝠鸽子猫虹鳉美洲鳄企鹅豪猪鳗鲡蝾螈 恒温冷血冷血恒温冷血冷血恒温恒温恒温冷血冷血恒温恒温冷血冷血 毛发鳞片鳞片毛发无鳞片毛发羽毛软毛鳞片鳞片羽毛刚毛鳞片无 是否否是否否是否是是否否是否否 否否是是半否否否否是半半否是半 否否否否否否是是否否否否否否否 是否否否是是是是是否是是是否是 否是否否是否是否否否否否是否是 哺乳类爬行类鱼类哺乳类两栖类爬行类哺乳类鸟类哺乳类鱼类爬行类鸟类哺乳类鱼类两栖类 r1：（胎生=否）（飞行动物=是）鸟类r2：（胎生=否）（水生动物=是）鱼类r3：（胎生=是）（体温=恒温）哺乳类r4：（胎生=否）（飞行动物=否）爬行类r5：（水生动物=半）两栖类201.5.2 删除实例名称体温表皮覆盖胎生水生动物飞行动物有腿冬眠类标号人类蟒蛇鲑鱼鲸青蛙巨蜥蝙蝠鸽子猫虹鳉美洲鳄企鹅豪猪鳗鲡蝾螈 恒温冷血冷血恒温冷血冷血恒温恒温恒温冷血冷血恒温恒温冷血冷血 毛发鳞片鳞片毛发无鳞片毛发羽毛软毛鳞片鳞片羽毛刚毛鳞片无 是否否是否否是否是是否否是否否 否否是是半否否否否是半半否是半 否否否否否否是是否否否否否否否 是否否否是是是是是否是是是否是 否是否否是否是否否否否否是否是 哺乳类爬行类鱼类哺乳类两栖类爬行类哺乳类鸟类哺乳类鱼类爬行类鸟类哺乳类鱼类两栖类 r1：（胎生=否）（飞行动物=是）鸟类r2：（胎生=否）（水生动物=是）鱼类r3：（胎生=是）（体温=恒温）哺乳类r4：（胎生=否）（飞行动物=否）爬行类r5：（水生动物=半）两栖类211.5.2 删除实例名称体温表皮覆盖胎生水生动物飞行动物有腿冬眠类标号人类蟒蛇鲑鱼鲸青蛙巨蜥蝙蝠鸽子猫虹鳉美洲鳄企鹅豪猪鳗鲡蝾螈 恒温冷血冷血恒温冷血冷血恒温恒温恒温冷血冷血恒温恒温冷血冷血 毛发鳞片鳞片毛发无鳞片毛发羽毛软毛鳞片鳞片羽毛刚毛鳞片无 是否否是否否是否是是否否是否否 否否是是半否否否否是半半否是半 否否否否否否是是否否否否否否否 是否否否是是是是是否是是是否是 否是否否是否是否否否否否是否是 哺乳类爬行类鱼类哺乳类两栖类爬行类哺乳类鸟类哺乳类鱼类爬行类鸟类哺乳类鱼类两栖类 r1：（胎生=否）（飞行动物=是）鸟类r2：（胎生=否）（水生动物=是）鱼类r3：（胎生=是）（体温=恒温）哺乳类r4：（胎生=否）（飞行动物=否）爬行类r5：（水生动物=半）两栖类221.5.2 删除实例名称体温表皮覆盖胎生水生动物飞行动物有腿冬眠类标号人类蟒蛇鲑鱼鲸青蛙巨蜥蝙蝠鸽子猫虹鳉美洲鳄企鹅豪猪鳗鲡蝾螈 恒温冷血冷血恒温冷血冷血恒温恒温恒温冷血冷血恒温恒温冷血冷血 毛发鳞片鳞片毛发无鳞片毛发羽毛软毛鳞片鳞片羽毛刚毛鳞片无 是否否是否否是否是是否否是否否 否否是是半否否否否是半半否是半 否否否否否否是是否否否否否否否 是否否否是是是是是否是是是否是 否是否否是否是否否否否否是否是 哺乳类爬行类鱼类哺乳类两栖类爬行类哺乳类鸟类哺乳类鱼类爬行类鸟类哺乳类鱼类两栖类 r1：（胎生=否）（飞行动物=是）鸟类r2：（胎生=否）（水生动物=是）鱼类r3：（胎生=是）（体温=恒温）哺乳类r4：（胎生=否）（飞行动物=否）爬行类r5：（水生动物=半）两栖类231.5.2 删除实例名称体温表皮覆盖胎生水生动物飞行动物有腿冬眠类标号人类蟒蛇鲑鱼鲸青蛙巨蜥蝙蝠鸽子猫虹鳉美洲鳄企鹅豪猪鳗鲡蝾螈 恒温冷血冷血恒温冷血冷血恒温恒温恒温冷血冷血恒温恒温冷血冷血 毛发鳞片鳞片毛发无鳞片毛发羽毛软毛鳞片鳞片羽毛刚毛鳞片无 是否否是否否是否是是否否是否否 否否是是半否否否否是半半否是半 否否否否否否是是否否否否否否否 是否否否是是是是是否是是是否是 否是否否是否是否否否否否是否是 哺乳类爬行类鱼类哺乳类两栖类爬行类哺乳类鸟类哺乳类鱼类爬行类鸟类哺乳类鱼类两栖类 r1：（胎生=否）（飞行动物=是）鸟类r2：（胎生=否）（水生动物=是）鱼类r3：（胎生=是）（体温=恒温）哺乳类r4：（胎生=否）（飞行动物=否）爬行类r5：（水生动物=半）两栖类241.5.2 删除实例名称体温表皮覆盖胎生水生动物飞行动物有腿冬眠类标号人类蟒蛇鲑鱼鲸青蛙巨蜥蝙蝠鸽子猫虹鳉美洲鳄企鹅豪猪鳗鲡蝾螈 恒温冷血冷血恒温冷血冷血恒温恒温恒温冷血冷血恒温恒温冷血冷血 毛发鳞片鳞片毛发无鳞片毛发羽毛软毛鳞片鳞片羽毛刚毛鳞片无 是否否是否否是否是是否否是否否 否否是是半否否否否是半半否是半 否否否否否否是是否否否否否否否 是否否否是是是是是否是是是否是 否是否否是否是否否否否否是否是 哺乳类爬行类鱼类哺乳类两栖类爬行类哺乳类鸟类哺乳类鱼类爬行类鸟类哺乳类鱼类两栖类 r1：（胎生=否）（飞行动物=是）鸟类r2：（胎生=否）（水生动物=是）鱼类r3：（胎生=是）（体温=恒温）哺乳类r4：（胎生=否）（飞行动物=否）爬行类r5：（水生动物=半）两栖类251.5.2 删除实例名称体温表皮覆盖胎生水生动物飞行动物有腿冬眠类标号人类蟒蛇鲑鱼鲸青蛙巨蜥蝙蝠鸽子猫虹鳉美洲鳄企鹅豪猪鳗鲡蝾螈 恒温冷血冷血恒温冷血冷血恒温恒温恒温冷血冷血恒温恒温冷血冷血 毛发鳞片鳞片毛发无鳞片毛发羽毛软毛鳞片鳞片羽毛刚毛鳞片无 是否否是否否是否是是否否是否否 否否是是半否否否否是半半否是半 否否否否否否是是否否否否否否否 是否否否是是是是是否是是是否是 否是否否是否是否否否否否是否是 哺乳类爬行类鱼类哺乳类两栖类爬行类哺乳类鸟类哺乳类鱼类爬行类鸟类。