（计算机软件与理论专业论文）失衡样本分类问题的自动过滤算法的研究.pdf

t h e s i sf o rm a s t e rd e g r e ei n2 0l l i i | i l i l l i l l | i i | | l i i i i i l | i m l | | l i l i | | l 洲 y 19 0 4 15 1 u n i v e r s i t yc o d e ： l0 2 6 9 r e g i s t e rn u m b e r ：5 l0 8l5 0 0 0 0 5 ea s tc h i n an 0 1 ：m a lu n i v e r s i t y a n a u t o m a t i c a l l yf i l t e ra l g o r i t h mf o ri m b a l a n c e dd a t as e t s c l a s s i f i c a t i o n c o l l e g e ：曼q l ! 堕垦! 曼星n g i n 曼曼! i 塾g ! 塾墨! i 地! 曼 m 句o r f i e l d ： g q 塑卫坠! 曼! s q 鱼婴垦! 曼鱼塾亟! h 星q ! x s p e c i a l t y ：丛鱼堡垒i 垒曼l 星旦! 卫i 坠g 垦堕亟旦垦! 旦丛i 堕i 望g a d v i s o r ： g r a d u a t e ： ! 塑q y i 旦gz b q 旦，里! q h 垫g 圣垦il 堕q 鳖i 鱼q 旦g m a y ，2 0 1 1 郑重声 师范大学攻 华东师范大学学位论文原创性声明 的学位论文失衡样本分类问题的自动过滤算法的研究，是在华东 请勾选) 学位期间，在导师的指导下进行的研究工作及取得的研究 成果。除文中已经注明引用的内容外，本论文不包含其他个人已经发表或撰写过的研究成果。 对本文的研究做出重要贡献的个人和集体，均已在文中作了明确说明并表示谢意。 作者签名：日期：沙年，月；p 日 华东师范大学学位论文著作权使用声明 失衡样本分类问题的自动过滤算法的研究系本人在华东师范大学攻读学位期间在导师 指导下完成的亟旦博士( 请勾选) 学位论文，本论文的研究成果归华东师范大学所有。本人 同意华东师范大学根据相关规定保留和使用此学位论文，并向丰管部门和相关机构如国家图书 馆、中信所和“知网”送交学位论文的印刷版和电子版；允许学位论文进入华东师范大学图二转 馆及数据库被查阅、借阅；同意学校将学位论文加入全国博士、硕上学位沦文共建单位数据库 进行检索，将学位论文的标题和摘要汇编出版，采用影印、缩印或者其它方式合理复制学位论 文。 本学位论文属丁二( 请勾选) () 1 经华东师范大学相关部门审查核定的“内部”或“涉密”学位论文幸， 于 年月日解密，解密后适用上述授权。 | ( 叫2 不保密，适用上述授权。 导师签名本人签名 龚薇 弘1 年，月口日 “涉密”学何论文麻是已经华东师范人学学位评定委员会办公室或保密委员会审定过的学位论文( 需 附获批的华东师范大学研究生申请学位论文“涉密”审批表方为有效) ，未经上述部门审定的学 位论文均为公开学位论文。此声明栏不填写的，默认为公开学位论文，均适用上述授权) 。 龚夔硕士学位论文答辩委员会成员名单 姓名职称单位备注 王晓玲教授华东师范大学主席 软件学院 钱卫宁副教授华东师范大学 软件学院 金澈清副教授华东师范大学 软件学院 摘要 失衡样木，即不平衡的数据集，是指在一个数据集中不同类样木的数量相差 悬殊。研究表明不平衡数据集严重影响了很多传统机器学习算法的分类性能，特 别是少数类的分类性能可能很差。同时，不平衡数据集还导致训练分类器的速度 过慢。然而在现实世界中，许多数据集都是不平衡的，甚至不平衡的程度很严重： 有些数据集中只有3 5 的少数类样本，例如多媒体语义分类，信息检索，医 疗检测等。此外，人们通常更关心数据集中的少数类样本，例如信息检索中与关 键字相关的文档总是占很少数，所以人们更希望少数类有很好的分类性能。由于 传统的机器学习分类算法不能满足在现实中的分类应用性能良好，因此失衡样本 问题迫切需要得到解决。 为了解决失衡样本所带来的以上问题，本文首先提出了过滤数据集中的样 本以平衡数据集的思想。这个思想希望通过过滤失衡样本中的对分类没有帮助的 多数类样木，从而拉小两类样本数量的差异，使数据集平衡并提高机器学习算法 的效果。 为了实现这个思想，本文又提出了一个新颖的过滤规则提取算法。该算法自 动从失衡的训练集中提取规则，这些规则能有效的去除样本空间中远离分类边界 的没有用的多数类，尽量保留少数类，最后使得数据集平衡。 在实验中，首先提取过滤规则，之后使用提取的规则过滤失衡数据集，最后 用s v m 对过滤后的训练集训练分类器。此外，木文还将该思想和算法应用于自 动提取新闻图片中。从实验结果可以看出： 1 ) 木文提出的过滤样木平衡数据集的方法是可行的、有效的。 2 ) 自动规则提取算法提取出的规则能有效的过滤失衡样本中无用的多数类， 几乎不过滤少数类，最后达到平衡数据集的效果 3 ) 不平衡数据集使用规则过滤后，再使用s v m 进行分类，能提高其分类 性能，同时明显降低训练分类器的时间。 4 ) 实验还证明了使用规则过滤后分类数据集比代价敏感学习方法无论在分 类性能还是在洲练时间上都更具优越性。 5 ) 最后，实验显示，本文提出的过滤规则提取算法能在自动提取新闻图片 的应用中使用并得到好的性能。 关键字：机器学习，分类，失衡样本，s v m ab s t r a c t i m b a l a n c e dd a t as e t sm e a n st h a tt h en u m b e r so fs 锄p l e s 仔o md i f 托r e n tc a t e g o d e s l a r g e l yd i 仃e r t h ei m b a l a n c e dd a t as e th a sb e e nr e p o r t e dt oh i n d e rt h ec l a s s i f i c a t i o n p e r f o m a n c eo fm a n ym a c h i n e l e a m i n ga l g o r i t h m s ，e s p e c i a l l yt ot h em i n o r i t yc l a s s o nm eo t h e rh a n d ，t h ei m b a l a n c e dd a t aa l s os i g n i f i c a n t l yr e d u c et h et r a i n i n gd a t a h o w e v e r ，i nt h er e a lw o r l d ，e x t r e m e l yi m b a l a n c e dd a t as e t s ( 3 5 p o s i t i v es 锄p l e s ) a r ec o m m o nf o rm a n ya p p l i c a t i o n s ，s u c ha sm u l t i m e d i as e m a n t i cc l a s s i f i c a t i o n ， i n f o 咖a t i o nr e t r i e v a la n dm e d i c a lp r e d i c t i o n i na d d i t i o n ，p e o p l ea r ea l w a y sm u c h m o r ec a r ea b o u tt h em i n o r i t yc l a s s ，f o re x 锄p l e ，t h ek e y w o r dr e l a t e dd o c u m e n t s o n l y t a k el i t t l ep a r to fa l lt h ed o c u m e n t si nl n f o 肌a t i o nr e t r i e v a l 印p l i c a t i o n h o w e v e r ，t h e t r a d i t i o n a lm a c h i n el e a m i n ga l g o r i t h m sh a v ep o o rp e r f o m l a n c eo nc l a s s i 聊n g m i n o r i t ys 砌p l e s ，t h e r e f o r e ，t h ep r o b l e mo fl m b a l a n c e dd a t as h o u l db es o l v e d i m m e d i a t e l y t or e s o l v et h i sp r o b l e m ，i nt h i sp 叩e rw ep r o p o s e 肌印p r o a c ht h a ta u t o m a t i c a i l y i i e m o v e ss 锄p l e st h a th a v en oo rn e g a t i v ee f r e c t so nc l a s s i f y i n g a r e rc u t t i n gt h e s e u s e l e s ss a l t l p l e s ，t h ed a t as e t sw i l lb er e b a l a n c e d m e a n w h i l e ，t h ep e r f o m a n c eo f c l a s s i f y i n gw i l la l s ob ei m p r 0 v e d t ba c h i e v et h i si d e a ，w ep r o p o s ean o v e la u t o m a t i cf l l t e ra l g o d t h mt h a tc a ne x t r a c t f i l t e rm l e s f 如m t r a i n i n g d a t a b yu s i n g t h e s er u l e s ，m o s t e a s y - t o c l a s s i f y d o m i n a n t c l a s ss a m p l e si ni m b a l a n c e dt r a i n i n gs e tw i l lb ee i i m i n a t e da u t o m “c a l l y a sar e s u l t ，t h er a t i oo fm i n o r i t ys 锄p l e si si n c r e a s e ds i g n i f i c a n t l y ，m a k i n gi tm o r e s u i t a b l ef o rc l a s s i f i c a t i o na l g o n t h m s i nt h ee x p e r i m e n t s ，w ee x t r a c tf i l t e rm l e r sf i r s t ，a n dt h e nu s et h e s em l e sb a l a n c e t h et m i n i n gd a t as e t a tl a s t ，c l a s s i f i 酹w i l lb et r a i n e do nt h en e wd a t as e t su s i n gs v m 0 u r e x p e 订m e n t ss h o w t h a t ： f i r s t l y ；t h er u l e b a s e df i l t e ri d e ai sp r a c t i c a la n de 伍c i e n t s e c o n d ly ，t h em l e se x t r a c t e db yf i l t e ra l g o “t h mc a n6 l t e rl o t so fm a j o r i t ys a m p l e s a n df e wm i n o r i t ys 锄p l e s ，a n dt h e nt h ed a t es e tw i l lb em o r eb a l a n c e dt h a nb e f o r e t h i r d l y ，a r e rt h ei m b a l a n c e dd a t as e tb e i n gf i l t e r e db yo u rf i l t e n ga l g o r i t h ma n d c l a s s i f i e db ys v mm e t h o d ，t h ep e r f b 啪a n c eh a sb e e ni m p r o v e da n dt h et i m ec o s t d e c r e a s es i g n i f i c a n t l y f o u r t h l y ，t h ec l a s s i f i c a t i o np e r f o m a n c ei sb e t t e rb yu s i n ga u t o m a t e df i l t e r i n g a l g o r i t h mt h a nt h ep e r f o m l a n c eo fu s i n gc o s ts e n s i t i v em e t h o d a n dt r a i n i n gt i m ec o s t i sa l s os m a l l e rb yu s i n ga u t o m a t e dc l a s s i f 妒n ga l g o r i t h m f i n a l l y ，o u rf i l t 谢n ga l g o r i t h mc a nb ea p p l i e dt oar e a lw o r l da p p l i c a t i o n e x t r a c t n e w si m a g e sa u t o m a t i c a l l y ，a n dt h ee x p e r i m e n tr e s u l t ss h o wt h ep e r f o m a n c ei s g o o d k e y w o r d s ：m a c h i n el e a m i n g ，c l a s s 讯c a t i o n ，i m b a l a n c e dd a t as e t ，s v m 目录 摘要。i a b s t r a c t 。u i 第一章绪论。1 1 1 研究背景。1 1 2 1 3 1 3 1 4 研究现状2 本文提出的解决方法4 本文的日标和贡献7 本文结构8 第二章自动过滤规则提取算法1 0 2 1过滤规则提取算法。1 0 2 1 1算法思想1 0 2 2算法实现1 2 2 2 1单维规则的提取1 2 2 2 2多维规则的提取1 4 2 2 3 算法复杂度1 4 2 2 4 例子l5 第三章实验验证1 7 3 i 3 2 实验准备1 7 实验过程1 8 3 2 1 实验步骤1 8 3 2 2 性能评价：18 3 3 实验结果2 0 3 3 1 不r 甲衡情况不发生逆转2 0 3 3 2不平衡情况发生逆转2 9 3 4 实验总结3 2 第四章过滤算法的应用。3 4 4 1 处理不甲衡数据集的流程3 4 4 2 自动提取新闻图片3 4 4 2 1 目的一：? 3 5 4 2 2 特征提取3 5 4 2 3 自动提取新闻图片的性能3 7 第五章 总结和展望3 9 参考文献。4 0 后记。4 4 p 忖录。4 6 第一章绪论 1 1 研究背景 目前，机器学习技术特别是分类技术已广泛应用与多个学科领域，除了我们 所熟知的人工智能领域，工业界、商业界等也在广泛采用。在现实世界中，有许 多问题可以通过分类技术完成，比如多媒体语义分析【1 7 】、自然语言处理 3 】，经 济预测 4 】，医疗诊断 5 】等等。显然，分类的性能直接影响到这些应用的效果。 在现实应用中，大量数据集比如信息检索、新闻图片和卫星图片检测漏油等，通 常是不平衡的，这样的数据集称为不平衡数据集，即失衡样本。失衡样本中一类 样本数量上和别的类样本相差悬殊，甚至有些数据集不同类之间的比例达到 l o o ：l 或者更多【l ，2 】。 研究表明， 许多机器学习算法在处理失衡样本时分类性能不理想 6 ，7 ，1 8 ， 2 l 】。导致分类效果不佳的原因是传统的机器学习分类算法大多基f3 个假设： 1 ) 以整体分类准确率最高为目标； 2 ) 每个类的错分代价相同； 3 ) 数据集中的各类样本大致是均匀分布的。 基于这些假设的分类算法在对不平衡的样本分类时会导致许多问题： 1 ) 首先，目前大多数分类算法趋向于使得不平衡数据集中少数类的召回率 值很低。因为传统分类算法在设计时都做了一个假设：希望分类得到最高的准确 率。该设计会导致这样的问题：比如一个数据集非常不平衡，有9 9 的样木足属 于一类( 可行的学习算法分类结果很难达到9 9 的准确率) ，基于以上这个假设， 我们的分类算法将会趋丁二将所有样木都判为多数类，而忽略少数类。于是分类算 法就很可能得到一个将所有样本部归于多数类的毫无意义的分类器，虽然这时分 类的准确率达到了9 9 。但是在大多数情况下，少数类才是有意义的数据，我们 的许多应用部希望得到的是少数类。在判断失衡样木的分类性能时，我们应该用 少数类的准确率和召咧率来衡量分类的性能。 例如，在新闻图片数据集中 8 】， 我们希望得到的是与新闻相关的图片，而占大多数的广告图片、l o g o 图片、网页 框架元素图片和链接到其它新闻的图片是我们在这个应用中所不关心的样木。如 果生成的分类器使得少数类的召同率非常低，那么这个分类器对f 希望得到少数 类的应用就没有作用了。 2 ) 其次，不平衡数据可能导致分类算法的训练时间过长。这足因为正样本 ( 少数类样本) 太少而不能提供足够多的信息来构造分类模型。分类算法很难在 这么少的数据中发现规律。 3 ) 最后，由于少数类太少，分类器很难区分少数类和噪音的区别，因此有 可能将少数类判断为噪音。 由于在现实世界中，大多数的数据集都是不平衡的，甚至两个类之间数量相 差悬殊。比如在卫星检测漏油 9 的应用中，整个数据集是卫星连续拍下的地球 各地的图片，而在这些图片中，只会有极少数的图片反应地球某处有漏油现象； 在医疗检测的应用的，数据集是选取作为测试样本的人。正常情况下，在这些样 本人群中，存在某种疾病的人的数量和没有这种疾病的人的数量足相差非常大 的。然而在绝大多数失衡样本中，少数类样本才是人们所关心的数据。传统分类 算法趋向于把所有的少数类都误判为多数类同样得到很高的准确率。这样训练出 的模型是没有仟何意义。例如在卫星检测漏油的例子中，检测的结果将是地球上 没有一处有漏油现象，这个结果是没有意义的；而医疗检测的结果将是所有人都 没有患某种疾病，这个结果足不能被接受的。所以当处理不平衡数据集时，应该 联合考虑少数类的精度和召回率作为判断分类结果好坏的标准。本文中定义正样 本为少数类样本，负样本为多数类样本。 1 2 研究现状 学习是人类独特的特性。人类能通过学习现有的知识，观察和经验，提高和 改进自己的能力。而机器学习是希望计算机也有像人类一样的学习能力，能够从 现有的数据中不断总结归纳完善模型，该技术被广泛的应用于研究，医学和工业 领域。机器学习是一个很大的范围，其中分类技术是最为广泛的技术之一，比如 文本分类，信息检索，视频和图片处理，医疗诊断等等应用于现代科技的各个方 面。分类性能的好坏直接影响了这些应用的效果和价值，比如医疗诊断，对患病 和无病的分类的准确率需要非常高，且不同的应用有不同的分类原则，比如说 患病的诊断，患病这一类的召回率( r e c a u ) 需要几乎为1 0 0 ，才能保证所有患 病的人被检测出，当然也要有比较高的精确率( p r e c i s i o n ) 。在这些大量的应用 中，很多数据集都是不平衡的，并且我们关心的通常都是少数类样本，比如患病 的人，在一般情7 兑下只有少数人患病。下面总结了4 点为什么研究不平衡数据集 很重要。1 ) 现实应用中的数据集大多是不平衡，且不平衡程度很严重；2 ) 人们通 常更关心少数类；3 ) 数据集大小，数据集的复杂程度，分类算法等等都会影响分 类性能。在这些原因中不平衡数据集严重影响了分类性能，且少数类的性能通常 很差；4 ) 分类性能决定了现实应用的成功与否。因此现在不平衡数据集的分类 问题已成为机器学习和模式识别领域的热点问题。 目前有许多研究讨论关于样本失衡问题 1o ，1 3 ，1 8 ，2 l ，2 9 】。n a t h a l i e j 印k o w i c z 和s h 可us t e p h e n 在【1 3 】中分析了不同的f | 练集大小和不同的不平衡程 度的数据集对分类算法( 决策树c 5 0 ，m l p 和s v m ) 的影响。h a i b oh e 和e d w a r d o 在【6 】中分析了样本失衡带来的科，种问题，并介绍了如何评价失衡样木分类的性 能，等等。在提出问题的同时，有人提出了一些解决方法【“，1 9 ，2 5 ，2 6 ，3 0 】， 有人提出采样的方法，有人提出代价敏感学习方法，还有人提出好的特征选择能 提高分类性能 3 l ，3 2 ，2 7 】。这些解决方法大致有两类，一类是对失衡的数据集 进行处理，使该数据集趋于平衡。方法有随机上采样、集中的随机上采样，随机 下采样，集巾的随机下采样等。另一类是改进现有的分类算法使之处理失衡样本 有更好的性能。方法有代价敏感学习，单类学习分类，或使用对不平衡样本不太 敏感的算法，如s v m 。下面将介绍一些解决样木失衡的分类问题的方法：上采 样，下采样，代价敏感。 1 ) 上采样【2 2 】分为随机上采样和集中的随机上采样。随机上采样是指随机增 加正样本，即随机的复制正样本添加到样本集中，最后使正负样木数相同。集中 的随机上采样是指集中增加样本空间中靠近分类边界的正样本，最后使正负样本 数相同。 2 ) 下采样分为随机下采样和集中的随机下采样。随机下采样是指随机减少 负样本，即随机的从样木集中删除负样本，最后使正负样本数相同。集中的随机 下采样是指集中随机的删除远离样本空间分类边界的负样木，最后使正负样本数 相同。 3 ) 代价敏感学习方法 2 3 ，2 4 】是指对正样本和负样本设置不同的错分代价， 以此来补偿数据集中不平衡的比例。例如，如果一个数据集中的正样木和负样木 的比例是i ：5 0 ，那么代价敏感方法可以把正样本的错分代价设置为负样本错分代 价的5 0 倍。 在【1 3 】中，作者使用这三种方法对几个有不同程度失衡的样木使用决策树， m l p 和s v m 进行分类，并比较了其性能，实验结果表明： 1 ) 失衡样本问题与数据集的不平衡程度，数据集的复杂程度，i l 练集大小， 以及分类器都有关系。 2 ) 上采样，下采样和代价敏感三种方法都在一定程度上提高了决策树c 5 0 的性能，但是在不同的不平衡程度和不同的训练数据集大小的情况下，各个方法 3 提高性能的程度不同。 3 ) 不平衡数据集对决策树c 5 0 的影响最大，之后足m l p ，最后是s v m 虽然上采样，下采样和代价敏感学习方法都能提高分类性能，但是它们都 各自的缺点： 1 ) 首先，上采样将增加样本数据集的数量，使得训练模型的难度和时间增 加，从而影响分类的性能。 2 ) 其次，下采样删除一些负样本，可能导敛删除一些对建立模型有用的样 本信息，而使分类性能下降。 3 ) 最后，试验表明，在真实数据集的大多情况下，代价敏感比一卜采样和下 采样的效果好，但足对于每个不同的数据，算法很难确定一个好的错分代价。 除了以上这些方法，许多研究者还提出了一些改进的方法，如t o m e kl i n k s 【3 4 】 方法，该方法通过判断样本问的距离，找出为噪旨或者在两类边界上的样本，然 后用类似于下采样的方法将找到的样本删除，这样会使分类边界范围更加扩大， 更为清楚，最后达到易于牛成分类器的效果。该方法中定义样本的距离足个难点。 另外还有个方法为压缩最近邻 3 5 】，即c o n d e n s e dn e a r e s tn e i g h b o rm l e ( c n n ) ， 该方法通过寻找样本的一致子集，保留多数类边界样本，去掉多数类远离分类边 界的样本，这样也是一种下采样方法。还有很多方法如c n n + t o m e kl i n k s 1 0 】， o n e s i d e ds e l e c t i o n ( o s s ) 【3 6 】，n e i g h b o r h o o dc l e a n i n gr u l e ( n c r ) 【3 7 】，s m o t e 2 2 】 等等。在文章 1 0 】中比较了这些方法。 这些方法在不同程度上解决了失衡数据集的分类问题，但效果并不十分理 想：它们没有提取任何数据集中的潜在信息，而足使用同样的方法对待千差万别 的各种数据集。 1 3 本文提出的解决方法 前面已经介绍在目前的研究中，提出的解决样本失衡问题的解决方法如上采 样，下采样和代价敏感学习都有各自的缺陷。并且，这些算法都没有考虑各个数 据集特征空间的内部特性，对每个失衡数据集使用单一的方法进行处理。本文提 出的自动规则过滤算法希望使用统一的方法，但目j 能考虑每个数据集各自内部不 同的样本空间特点。所以，接下来将介绍失衡样本特征空间特点，正是基于失衡 样本空间的以下特点，我们才提出了过滤样本平衡数据集的思想。 4 通过对多个失衡数据集的观察和分析，不难发现在大多情况下，失衡样本的 特征空间有如图1 所示的特性：在这个图中，圆圈表示正样木，叉和长方形表 示负样本。用叉表示的负样本代表了没有用的多数类数据，这类数据容易被分类 器识别，所以对建立分类模型很可能没有意思。用长方形表示的是靠近分类边界 的负样本，这类样本难以判定正负，因此它们是对建立分类模型有作用的多数类 数据。由于这些没有用的负样本很可能在训练分类器时产牛下扰，而影响分类性 能和训练时间，因此我们希望能自动的除去这些无用的负样本，从而提高分类算 法的性能。因此，本文提出了一个思想：使用规则过滤掉特征窆间中尽量多的没 有用的负样本，同时保留对建立分类模型有作用的正样本和有意义的负样本。又 因为除去了的负样木数量远远多于正样木数量，所以被过滤后的不平衡数据集的 样本之间的数量会趋于平衡。 为了得到这些规则，本文中提出了过滤规则提取算法，该算法是基于以下观 察：不平衡数据集的正样木集中在样本特征空间中相对小的范再i 内，而负样本则 比较均匀的分布在整个特征空间。因此，在每个特征维的一头或者两头，正样本 的密度通常很低。基于这个观察，如果算法能将样本空间中正样本密度非常低的 区域删除，那么许多没有用的负样本将会从训练集中除去。 无用的负样本 图l 样木空间 s o )，bk， 因此，总的来说，本文基于以上的观察和分析，提出了这样的解决样本失衡 的方法：使用规则将样本集中的负样本除去，保留正样本，同时这些规则又要保 证去掉的负样本尽量足那些对建立分类器没有什么作用的样本。为了得到这样的 规则，我们又提出了一个自动过滤规则提取算法，该算法能从失衡样本中自动的 提取规则，提取出的规则能将样本集中的对建立分类器没有用的负样本删除，保 留其它的负样本和正样本。使用规则过滤失衡样本之后，样本集会变得平衡，这 时候使用大多数的机器学习算法处理平衡后的数据集能得到好的性能。 为了应用以上提出的思想和算法，我们使用图2 所示的系统框架来处理真 实的失衡样本数据集。该系统利用过滤算法将失衡数据集转变成一个较之原来平 衡的样本，希望传统分类器的分类性能提高。 这个系统分类三个部分，第一部分为数据集中得到分类器：首先，将每个样 本随即分为训练集和测试集，训练集用来训练分类器，测试集用来收集性能评价。 然后，自动规则提取算法自动从洲练集中提取过滤规则，将过滤规则应用于训练 集和测试集，这时有一部分的样本被过滤规则过滤掉。第三，使用s v m 训练经 过过滤算法过滤后的训练集，得到分类器。第二部分为性能评价部分：首先用测 试集使用过滤算法过滤，得到过滤掉的样本和一个新的测试集，过滤掉的样本在 我们的系统中都被分类为负样本，所以如果删除的样本中包括了正样本，那么这 些正样本就被错误的分类为了负样本；然后用分类器分类新的测试集，最后在测 试集上得到分类性能，这个性能足包括分类器的分类结果和过滤算法过滤掉的样 本的全局性能，也就是说，最后的性能评价不止考虑分类器的分类性能评价，还 包括过滤算法正确删除的负样本和错误删除的正样本。第三部分为实时分类样本 的过程：首先当有个新的样本需要被分类时，我们先用过滤算法过滤，如果被 过滤掉，则表示该样本为负样本，如果没有被过滤，则使用分类器分类，如果分 类为正样本，则判断这个新的样本为正样本，否则为负样本。这个部分是作为实 际应用的分类过程。 6 e 训练集 过滤 ， s v m i _ _ _ 一 图2 系统框架 这样，通过以上方法将过滤算法和现有的机器学习技术有效的结合起来：过 滤算法弥补了机器学习算法分类失衡样本低性能的不足之处，通过过滤的方法有 效的将失衡样本转化为平衡样本，这样再使用传统的机器学习算法处理就能得到 好的分类型能。 1 3 本文的目标和贡献 本文中，深入分析和研究了样本失衡问题。由于a ) 大多数分类器在分类失 衡的数据集时，对少数类的分类性能不佳，b ) 现实世界中，大部分的数据集均 不平衡，c ) 人们关心的样本通常是少数类样本。 因此，本文的目标是a ) 研究失衡样本特性和问题，b ) 提出一个可以解决不 平衡数据集的方法。整理该算法的思想和算法实现细节：本文提出了一种自动提 取规则的过滤算法，该算法能自动的从训练数据集中生成对应的规则，再用这些 规则去掉数据集中的无用的多数类样木，使样本比例趋于平衡。这样使用现有的 机器学习算法i | 练过滤后的数据集能得到好的性能。c ) 通过分析和实验，证明 该算法对解决失衡样本问题是可行的，有效的和健壮的。下面，将总结本文的贡 献： 。 1 本文提出了自动过滤不平衡数据集中对分类器训练效果不好或甚至有负 效果的多数类样本以平衡数据集、提高机器学习效果的方法。与传统的 失衡样本训练方法相比，该方法能充分利用训练数据集各自木身的样木 7 空间特性，从而有针对性地平衡洲练数据，可以更好地帮助机器学习算 法提高学习性能。 2 本文提出了自动规则提取算法以自动过滤不平衡数据集。该算法能自动 的从不平衡数据集的训练样本中提取一组规则，这些规则一方面过滤大 多数的多数类样本，同时保留绝大多数的少数类样本。过滤掉的多数类 样本是对建立分类器几乎没有作用的样本，即远离分类边界的样本。过 滤之后的数据集较之过滤前的数据集在正负样本的比例上要更平衡一 些。 3 本文还通过大量的实验证明了以上思想和算法的有效性。使用过滤算法 得到的规则能有效的过滤不平衡数据集中的多数类，不过滤少数类，最 后得到一个比较平衡的数据集。使用过滤算法过滤后的数据集通过s v m 分类后比直接用s v m 分类或使用代价敏感s v m 分类都有有更好的分类 性能，并且训练分类器的时问大大减少了。在一些情况下，过滤算法已 经是一个效果很好的分类器，而且比s v m 训练数据集的时间要少的多： 一些不平衡数据集经过滤算法过滤后，能把所有的多数类都除去，而保 留少数类。 4 最后我们将所提出的算法使用到实际应用中，在新闻图片的自动提取中 得到了好的效果：我们创建了一个新闻图片数据集 8 】 3 3 】，在【3 3 】中有详 细的该数据集的用法和介绍。本文中的第四章介绍了怎样从新闻网页中 收集新闻图片的数据集并提取了一系列的特征。我们从2 0 0 0 个中英文网 页中提取出所有的图片，并人工标记出了正负样本。这个数据集是不平 衡的( 不s f 衡的比例大约为正负l ：2 0 ) 。同时本文提出了处理失衡数据集 的一套有效的系统，该系统使用过滤算法，能应用到不平衡类处理问题 上。使用这个系统，能快速有效的从新闻网页中抓取出与新闻相关的图 片。因此过滤算法能很好的应用于实际应用中。 1 4 本文结构 本文共分六章，第一章对样本失衡问题的研究背景和相关工作进行介绍，并 指出了决解该问题的重要性：第二章中，提出了自动提取过滤规则算法，对算法 思想和实现细节进行了说明。第三章中是实验的准备和步骤和实验的结果和分 析：第四章介绍了自动规则过滤算法的一个实际应用：自动的提取新闻图片。在 这章中介绍了怎样收集新闻图片数据集。同时在这章中提出了一个处理这样的不 8 平衡数据集应用的系统，该系统可应用于新闻图片数据集，也可用于任何不平衡 数据集；最后第五章是本文的总结和展望。 9 第二章 本章将具体介绍提出的过滤 2 1 过滤规则提取算法 2 1 1 算法思想 在前面一章中，本文分析了 数类分布的空间。通过裁剪这些空间，即可过滤掉大多数负样本。 通过以上的观察，过滤算法如下： 设石是样本窄间集x x 的第f 维特征。在石七的一维规则，也叫简单规则如 公式( 1 ) 所示：如果一个样本的第x 维特征值大于或等于常量c ( 或者小于或 等于常量c ) ，那么这个样本匹配规则r i ，于足这个样本就被过滤算法判定为无 用的负样本被删去。复杂规则是指多维规则，它由不同特征维上的多个简单规则 逻辑与组成，如公式( 2 ) 所示。 弓兰c ) d ，b 三c ) ( 1 ) 弓三 人气 & ( 2 ) 从数据集o 中，可以得到许多这样的复杂和简单规则。但是因为不是每个 规则都能得到好的分类性能，所以大多数的规则都足无用的。一个好的规则必须 满足以下条件： 1 ) 该规则能满足尽量少的正样本。 2 ) 该舰则能满足尽量多的负样本。 本文提出的过滤规则算法通过使用公式3 从所有的可抽取的规则中选择满 足以上两个条件的候选规则。 础沪矧锄蹦 1 0 其中q 为训练样本集，q + 为q 中的正样本集；q 一为q 中的负样木集； q + ( r ，) 为q 中满足规则吩的正样木集；q 一( 尺，) 为q 中满足规则尺，的负样本集。 o 彩 l 是一个常量。由公式( 3 ) 挑选的规则可以保证满足该规则的样木集的 负样本比例比训练集中负样木的比例要高，高多少由决定。则因此，删除训 练集中满足选择出的规则的样木可以使得训练集的负样本比例降低，使数据集的 不平衡程度降低。当越小，越接近0 ，越能保证删除尽量少的正样本，但是此 时删除的负样木也会随之减少。 尽管通过公式( 3 ) 选择规则可以保证提高训练集的正负样本比例，但不是 所有的规则都可以用来作为过滤条件：有些规则是其它规则的子集，如公式( 4 ) 所示 q ( b 。) q ( 吩：) 满足规则吩。的样本是满足规则凡的样本的一部分；所以挑选规则时还需要满足 公式( 5 ) ， 尺= a r g m a x 忙( 刚) ( 5 ) 它保证每次挑选出的规则能够删除数量最多的负样本。当存在多条规则，同时满 足公式( 5 ) ，也就是它们能删除的负样本数相同，则使用公式( 6 ) 选择维数最 低的规则。 尺= a r g 唧帜，z ( 尺刊( 6 ) 挑选出规则后，将其应用到训练集中，并使用公式( 7 ) 更新训练集。即使 用规则过滤l l 练集，再将过滤之后的l l 练集替代原有的洲练集。接着从更新后的 训练集中继续挑选规则。公式( 5 ) 和公式( 7 ) 共同保证了挑选的规则不会出现 包含的情况。当循环进行到后面时可能挑选出的候选规则仪能去掉少数几个样本 ( 虽然这个规则已经是当前能去掉最多负样木的规则) ，这样的规则我们当然不 能选择，如果选择了这样的规则来过滤样本，那么就会出现过度拟合的情况。因 此我们规定了当挑选出的规则满足公式( 8 ) 时循环结束，a 为常量阈值，当规 则能过滤的样本数小于a 时，不再继续提取规则。这个公式保证了选择规则不会 过度拟合。 q 卜q q ( 尺) p ( 天杠 ( 7 ) ( 8 ) 通过以上算法得到的过滤规则集可删除大量多数类样本，但是存在一个问 题：该过滤算法删除了大量多数类样本后数据集的不平衡关系可能发生移转，即 原来的多数类样本变为少数类样本，而少数类样本成为多数类样本。解决该问题 的方法是：将过滤后的样本当作一个新的不平衡数据集( 这时原来的多数类变为 少数类，少数类变为多数类) 继续使用过滤算法，直到最终的数据集趋于平衡。 通过实验发现甚至可能出现过滤算法将所有的多数类样本删除，只剩下少数类样 本的情况，这时尤需再用其它分类器分类数据集：过滤算法在这种情况下已经足 个很好的分类器。 2 2 算法实现 同时，还存在另外一个问题：特征空间上一维的特征可以是连续或者离散的， 当特征是连续时，从公式( 1 ) 能得到无穷个可能的规则，一个个测试这些规则 是不可能的。但足，样本数足有限的。因此，如果用适当的算法搜索规则，那么 尽管特征是连续的也可以得到有限个可能的规则。在本节中，将介绍得到单维规 则和多维规则的搜索算法。 2 2 1 单维规则的提取 为了高效地从第i 维连续或离散特征中选取出适当的规则，本文提出的算法 如下： 1 ) 将整个样本集按照石升序排序。排序后的集合可以表示为一个样本序列 1 ，惕如，】，与之联系的特征序列为瞰v a 石( v 2 ) ，z ( 均) 石( ) 】，其中石( 吁) 是指样本吁的第f 维特征的值。在这个步骤中，排 序的原因足，前面已经说过，每个特征维的一头或者两头，正样本的 比例通常很低，所以排序之后的特征在头和尾的地方是最可能找到规 则的。 2 ) 对特征序列昕( 1 ，a 似) ，似v j ) 似) 】按顺序或逆序逐一扫描，扫描 过程中用计数器记录负样本和正样本的数量。顺序和逆序扫描的方法 一样，因为在特征维的两头都有可能找到规则。 3 ) 当第j 维样本满足以下公式( 9 ) 或扫描完所有样本时，结束扫描。如 图3 所示，图l l 以j j 顷序扫描为例， 样本在上面那一头的分布将会是： 当哉们将训练集按z 排序后，正负 大多数的样本为负样本，只有非常 少的样本为正样本。事实上我们每一步的扫描都会得到一个规则尺= 石= c ，c 为当前扫描到的特征的值，如果这个规则满足公式( 3 ) 则表示这 是一条候选规则。公式( 3 ) 是为了保证选取的规则能删除大量的负样 本，几乎不删除在正样木。 渊 彩斟，渊彩剐 当扫描在满足公式( 9 ) 时停止，则表明找到了候选规则。公式( 9 ) 是指 当前扫描到了样木j ，这时候计数器记录的正负样本比例满足公式( 3 ) ， 同时如果扫描到了样本i + 1 ，则计数器记录的正负样木比例不满足公式 ( 3 ) ，这时表示找到了一个候选规则。对于任意c z ( 1 ，；+ 。) ，一条规则满 足公式( 3 ) 则可以由公式( 1 ) 定义成一条合法的候选规则。由于如 果c l 巴 z ( 1 ，+ i ) ，那么满足规则尺，三c ：) 的样本集将会包含满足规 则尺，三q ) 的样木集。为了防止算法挑选出的规则存在包含情况， 文中提出的算法只将当前扫描过程中可以满足最大样本集的规则加入 候选规则中，该规则中的常量c 为五! 生! ! 堑! 。