数据挖掘Chapter5

数据挖掘导论Pang-ningTan,MichaelStieinbach,andVipinKumar著PearsonEducationLTD.范明等译人民邮电出版社第5章分类:其他技术基于规则的分类最近邻分类贝叶斯分类神经网络支持向量机组合方法不平衡类问题多类问题5.1基于规则的分类器2019年10月21日星期一数据挖掘导论4基于规则的分类器使用一组“if…then…”规则进行分类规则:(Condition)y其中Condition是属性测试的合取y是类标号左部:规则的前件或前提右部:规则的结论分类规则的例子:(BloodType=Warm)(LayEggs=Yes)Birds(TaxableIncome50K)(Refund=Yes)Evade=No2019年10月21日星期一数据挖掘导论5基于规则的分类器:例脊椎动物数据集名称体温表皮覆盖胎生水生动物飞行动物有腿冬眠类标号人类蟒蛇鲑鱼鲸青蛙巨蜥蝙蝠鸽子猫虹鳉美洲鳄企鹅豪猪鳗鲡蝾螈恒温冷血冷血恒温冷血冷血恒温恒温恒温冷血冷血恒温恒温冷血冷血毛发鳞片鳞片毛发无鳞片毛发羽毛软毛鳞片鳞片羽毛刚毛鳞片无是否否是否否是否是是否否是否否否否是是半否否否否是半半否是半否否否否否否是是否否否否否否否是否否否是是是是是否是是是否是否是否否是否是否否否否否是否是哺乳类爬行类鱼类哺乳类两栖类爬行类哺乳类鸟类哺乳类鱼类爬行类鸟类哺乳类鱼类两栖类2019年10月21日星期一数据挖掘导论6基于规则的分类器的使用规则r覆盖实例x，如果该实例的属性满足规则r的条件r1：（胎生=否）（飞行动物=是）→鸟类r2：（胎生=否）（水生动物=是）→鱼类r3：（胎生=是）（体温=恒温）→哺乳类r4：（胎生=否）（飞行动物=否）→爬行类r5：（水生动物=半）→两栖类规则r1覆盖“鹰”=鸟类规则r3覆盖“灰熊”=哺乳类名称体温表皮覆盖胎生水生动物飞行动物有腿冬眠类标号鹰灰熊恒温恒温羽毛软毛否是否否是否是是否是？？2019年10月21日星期一数据挖掘导论7规则的质量用覆盖率和准确率度量规则的覆盖率（coverage）:满足规则前件的记录所占的比例规则的准确率（accuracy）:在满足规则前件的记录中，满足规则后件的记录所占的比例规则:(Status=Single)NoCoverage=40%,Accuracy=50%TidRefundMaritalStatusTaxableIncomeClass1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes102019年10月21日星期一数据挖掘导论8如何用规则分类一组规则r1：（胎生=否）（飞行动物=是）→鸟类r2：（胎生=否）（水生动物=是）→鱼类r3：（胎生=是）（体温=恒温）→哺乳类r4：（胎生=否）（飞行动物=否）→爬行类r5：（水生动物=半）→两栖类待分类记录狐猴触发规则r3,它分到哺乳类海龟触发规则r4和r5----冲突狗鲨未触发任何规则名称体温胎生飞行动物水生动物类狐猴恒温是否否?海龟冷血否否半水生?狗鲨冷血是否是?2019年10月21日星期一数据挖掘导论9规则的分类器的特征互斥规则集每个记录最多被一个规则覆盖如果规则都是相互独立的，分类器包含互斥规则如果规则集不是互斥的一个记录可能被多个规则触发如何处理?有序规则集基于规则的序vs基于类的序无序规则集–使用投票策略2019年10月21日星期一数据挖掘导论10规则的分类器的特征(续)穷举规则集每个记录至少被一个规则覆盖如果规则集涵盖了属性值的所有可能组合，则规则集具有穷举覆盖如果规则集不是穷举的一个记录可能不被任何规则触发如何处理?使用缺省类2019年10月21日星期一数据挖掘导论11有序规则集根据规则优先权将规则排序定秩（rank）有序规则集又成决策表（decisionlist）对记录进行分类时由被触发的，具有最高秩的规则确定记录的类标号如果没有规则被触发，则指派到缺省类r1：（胎生=否）（飞行动物=是）→鸟类r2：（胎生=否）（水生动物=是）→鱼类r3：（胎生=是）（体温=恒温）→哺乳类r4：（胎生=否）（飞行动物=否）→爬行类r5：（水生动物=半）→两栖类名称体温胎生飞行动物水生动物类海龟冷血否否半水生?2019年10月21日星期一数据挖掘导论12规则定序方案基于规则的序根据规则的质量排序基于类的序属于同一类的规则放在一起基于类信息（如类的分布、重要性）对每类规则排序基于规则的排序（表皮覆盖=羽毛,飞行动物=是）鸟类（体温=恒温,胎生=是）哺乳类（体温=恒温,胎生=否）鸟类（水生动物=半）两栖类（表皮覆盖=鳞片,水生动物=否）爬行类（表皮覆盖=鳞片,水生动物=是）鱼类（表皮覆盖=无）两栖类基于类的排序（表皮覆盖=羽毛,飞行动物=是）鸟类（体温=恒温,胎生=否）鸟类（体温=恒温,胎生=是）哺乳类（水生动物=半）两栖类（表皮覆盖=无）==＞两栖类（表皮覆盖=鳞片,水生动物=否）爬行类（表皮覆盖=鳞片,水生动物=是）鱼类2019年10月21日星期一数据挖掘导论13如何建立基于规则的分类器直接方法:直接由数据提取规则例如:RIPPER,CN2,Holte’s1R间接方法:由其他分类模型提取规则(例如，从决策树、神经网络等).例如:C4.5rules2019年10月21日星期一数据挖掘导论14直接方法:顺序覆盖基本思想依次对每个类建立一个或多个规则对第i类建立规则第i类记录为正例，其余为负例建立一个第i类的规则r，尽可能地覆盖正例，而不覆盖负例删除r覆盖的所有记录，在剩余数据集上学习下一个规则，直到所有第i类记录都被删除2019年10月21日星期一数据挖掘导论15直接方法:顺序覆盖顺序覆盖（sequentialcovering）算法1：令E是训练记录，A是属性—值对的集合{(Aj,vj)}2：令Yo是类的有序集{y1,y2,...,yk}3：令R={}是初始规则列表4：for每个类y∈Yo{yk}do5：while终止条件不满足do6：r←Learn-One-Rule(E,A,y)7：从E中删除被r覆盖的训练记录8：追加r到规则列表尾部：RRr9：endwhile10：endfor11：把默认规则{}→yk插入到规则列表R尾部2019年10月21日星期一数据挖掘导论16顺序覆盖:例(a)Originaldata(b)Step1(c)Step2(c)Step32019年10月21日星期一数据挖掘导论17删除实例为什么要删除实例?否则,下一个规则将与前面的规则相同为什么删除正实例?确保下一个规则不同为什么删除负实例?防止低估规则的准确率比较图中的规则R2和R3class=+class=-++++++++++++++++++++---------------------+++++++R1R3R2++2019年10月21日星期一数据挖掘导论18Learn-One-Rule规则增长实例删除规则评估停止准则规则剪枝2019年10月21日星期一数据挖掘导论19规则增长两种策略一般到特殊从初始规则r:{}→y开始反复加入合取项，得到更特殊的规则，直到不能再加入特殊到一般随机地选择一个正例作为初始规则反复删除合取项，得到更一般的规则，直到不能再删除问题加入/删除合取项有多种选择，如何选择？何时停止加入/删除合取项？需要评估标准2019年10月21日星期一数据挖掘导论20规则增长:例一般到特殊体温=恒温，表皮覆盖=毛发，胎生=是，水生动物=否，飞行动物=否，有腿=是，冬眠=否=哺乳类表皮覆盖=毛发，胎生=是，水生动物=否，飞行动物=否，有腿=是，冬眠=否=哺乳类体温=恒温，表皮覆盖=毛发，胎生=是，水生动物=否，飞行动物=否，有腿=是=哺乳类{}=哺乳类表皮覆盖=毛发=哺乳类体温=恒温=哺乳类有腿=否=哺乳类体温=恒温，有腿=是=哺乳类体温=恒温，胎生=是=哺乳类特殊到一般2019年10月21日星期一数据挖掘导论21规则评估常用的度量准确率似然比LaplaceM-estimateFOIL信息增益2019年10月21日星期一数据挖掘导论22规则评估(续)准确率Accuracyn:被规则覆盖的实例数nc:被规则正确分类的实例数问题：准确率高的规则可能覆盖率太低似然比（越高越好）k是类的个数fi是被规则覆盖的类i的样本的观测频度ei是规则作随机猜测的期望频度nnckiiii)/e(ffR1log22019年10月21日星期一数据挖掘导论23规则评估:例例:60个正例和100个反例规则r1：覆盖50个正例和5个反例（acc=90.9%）规则r2：覆盖2个正例和0个反例（acc=100%）使用准确率,r2好使用似然比r1:正类的期望频度为e+=5560/160=20.625负类的期望频度为e=55100/160=34.375r2:正类的期望频度为e+=260/160=0.75负类的期望频度为e=2100/160=1.25R(r1)=2[50log2(50/20.625)+5log2(5/34.375)]=99.9R(r2)=2[2log2(2/0.75)+0log2(0/1.25)]=5.66r1比r2好2019年10月21日星期一数据挖掘导论24规则评估(续)考虑规则覆盖率的评估度量n是规则覆盖的样例数，f+是规则覆盖的正例数，k是类的总数，p+是正类的先验概率当规则的覆盖率很高时，两个度量都渐近地趋向于规则的准确率f+/n继续前例r1的Laplace度量为51/57=89.47%，很接近它的准确率r2的Laplace度量（75%）比它的准确率小很多knfLaplace1-fkpMestimatenk2019年10月21日星期一数据挖掘导论25规则评估(续)考虑规则的支持度计数的评估度量规则的支持度计数对应于它所覆盖的正例数FOIL信息增益（FirstOrderInductiveLeanerinformationgain）设规则r:A→+覆盖p0个正例和n0个反例;规则r’:AB→+覆盖p1个正例和n1个反例.扩展后规则的FOIL信息增益定义为该度量与p1和p1/(p1+n1)成正比，所以它更倾向于选择那些高支持度计数和高准确率的规则继续前例r1和r2的FOIL信息增益分别为43.12和2，因此规则r1比r2好000211121loglognppnpppnFOILinfGai2019年10月21日星期一数据挖掘导论26停止条件与规则剪枝停止条件计算增益如果增益不显著,则丢弃新规则规则剪枝类似于决策树后剪枝降低错误剪枝:删除规则中的合取项比较剪枝前后的错误率如果降低了错误率,则剪掉该合取项2019年10月21日星期一数据挖掘导论27直接方法:RIPPER对于2类问题,选定一个类为正类，另一个为负类从正类学习规则负类时缺省类多类问题按类的大小（属于特定类的实例所占的比例）对诸类排序从最小的类开始学习规则，其余类都看做负类对次小类学习规则，如此下去2019年10月21日星期一数据挖掘导论28直接方法:RIPPER(续)规则增长:由空规则开始只要能够提高FOIL信息增益就增加一个合取项当规则不再覆盖负实例时就停止剪枝剪枝度量:v=(pn)/(p+n)p:验证集中被规则覆盖的正实例数n:验证集中被规则覆盖的负实例数剪枝