（计算机软件与理论专业论文）信息过滤系统中特征选择算法的研究.pdf

山东师范大学硕士学位论文 摘要 随着i n t e m e t 的迅速发展和日益普及，电子文本信息迅速膨胀，如何有效地组 织和管理这些信息，并快速、准确、全面地从中找到用户所需要的信息就是当前 信息科学技术领域面临的一大挑战。网络信息过滤技术作为处理和组织庞大的网 络信息的关键技术，可以在较大程度上解决信息杂乱的现象，方便用户准确地定 位所需信息。目前，对于信息过滤技术的研究，大多数研究者的精力主要放在各 种不同分类方法的研究与改进上。然而，特征选择一直是网络信息过滤中的基础 性工作，而且是一项瓶颈技术。因此，对特征选择算法的研究也是十分必要的。 目前常用的特征选择算法都直接利用了特征之间的条件独立性假设，通过构 造一个评价函数，单独对特征集的每个特征进行评价，但是由于没有直接考虑特 征的类别相关性，也没有考虑特征子集的冗余性，这些方法选择的特征子集在类 别区分能力上往往存在着冗余，导致最终分类效果不佳。 本文主要针对信息过滤系统中特征选择算法的相关问题，在如下几个方面进 行了研究和讨论： 1 、对常用的特征选择方法的优点和缺点进行了分析，并针对存在的不足之处 指出了相应的改进方向。 本文首先对特征选择技术做了综合分析，并着重介绍了特征选择技术的框架。 目前常用的几种特征选择方法各有所长，亦各有所短，文中从计算复杂度和分类 效果出发，分析了它们的优缺点，并指出了可能导致的原因所在。另外，根据相 关文献资料，列举出了常用特征选择算法的对比实验结论。这与本文最后的实验 结果大致相同。 2 、从特征相关性和冗余性定义出发，提出了一种特征选择框架f s b c ( f e a 眦 s e l e c t i o nb a s e do nc o 玎e l a t i o n ) ，即把特征选择过程分两步进行：第一步选取类别相 关的特征子集；第二步通过冗余分析，去除候选特征子集中的冗余特征，最终获 得优化特征子集。 首先，选取类别相关特征时，本文根据这样一个原则构造评价函数来选取特 征项：如果一个特征项t 在一个类别的文档中频繁出现，而在其它类别中很少出现 的话，那么该特征项t 能够很好的代表这个类别，这样的特征项应该赋予较高的权 值，并选来作为该类别的特征词，以区别于其它类别的文档。另外，文中引入了 t f i d f 权重计算的思想，考虑将词频和文档频率结合起来共同作为评价特征项的 依据。 其次，进行冗余分析时，本文采用聚类方法中常用的k m e a i l s 算法作为去冗 余的核心算法，针对该算法中的初始簇中心的选择及初始簇个数的设置问题进行 山东师范大学硕士学位论文 了相应的改进，使类k m e a n s 算法更有效的减少特征集的冗余性。 3 、最后，将所提出的特征选择策略在网络信息过滤平台上进行了实验测试， 并取得了令人满意的测试效果。 本文将特征选择框架f s b c 应用于网络信息过滤系统，并与信息增益( i g ) 和c h i 统计方法进行了实验对比。实验表明，f s b c 方法在准确率和查全率上要好 于其它两种方法，尤其在特征维数较高时取得了不错的实验效果。 关键词：信息过滤；特征选择；分词；文本分类；聚类 分类号：t p 3 9 1 山东师范大学硕士学位论文 r e s e a r c ho nf e a t u r es e l e c t i o nm e t h o d si ni n f o r m a t i o nf i l t e r i n g s y s t e m a b s t r a c t w i t ht h er a p i dd e v e l o p m e n ta n dt h es p r e a do fi n t e m e t ，e l e c t r o n i ct e x ti n f o n n a t i o n g r e a t l yi n c r e a s e s i ti sag r e a tc h a l l e n g ef o ri n f o r n l a t i o ns c i e n c ea 1 1 dt e c h n o l o g yt h a th o w p e o p l eo 唱a n i z ea 1 1 dp r o c e s sl a 唱e 锄o u n to fd o c 啪e n td a t a ，a n df i n dt h ei n t e r e s t i n g i n f o n l l a t i o nf o ru s e r sq u i c k l y ，e x a c t l ya 1 1 df h l l y a st h ek e yt e c l l n 0 1 0 9 yi no r g a n i z i n ga n d p r o c e s s i n gl a r g e 撇o u l l to fd o c u m e n td a t a ，n e t w o r ki n f o n n a t i o nf i l t e r i n gt e c h n o l o g y c a ns o l v et h ep r o b l e mo fi n f o n n a t i o nd i s o r d e rt oag r e a te x t e m ，a n di sc o n v e n i e n tf o r u s e r st of i n dt h er e q u i r e di n f o n n a t i o nq u i c k l y r e c e n t l y ，f o rt h es t u d yo fi n f o 姗a t i o n f i l t e r i n gt e c h n o l o g y ，r e s e a r c h e r sm o s t l yf o c u so nt h ee x p i o r a t i o na n di m p r o v e m e n to f d i 舭n e n tc l a s s i f i c a t i o na l g o 打t h m s h o w e v e r ，t h e 诧a t u r es e l e c t i o nh a sa l w a y sb e e na b a s i cw o r ka i l da b o t t l e n e c kt e c h n o l o g yf u r t h m o r eo fn e t w o r ki n f o n i l a t i o nf i l t e r i n g s o ， i ti sn e c e s s a r yt os t u d yf e a t u r es e l e c t i o na l g o r i t h m s a tp r e s e n t ，c o m m o nf e a t u r es e l e c t i o na l g o r i t sd i r e c t l yu s e st h ec o n d i t i o n so f i n d e p e n d e n c ea s s 啪p t i o n s 锄o n gf e a t u r e s ，e v a l u a t e ss e p a r a t e l ye a c hf e a t u r ei n t h e f e a t u r es e tt h r o u 曲c o n s t r u c t i n gae v a l u a t i o nf u n c t i o n b u td u i n gt oi nt h ea b s e n c eo ft h e r e l e v a n tc a t e g 谢e so ff e a t u r e sa n dr e d u n d a n c yo ff e a t u r es u b s e t s ，t h ef e a t u r es i l b s e t s s e l e c t e db yt h e s em e t h o d se x i s tr e d u n d a n c ys o m e t i m e si nt h ea b i l i t ) rt od i s t i n g u i s h b e t 、e e nc a t e g o r i e s ，a j l dt h u sl e a dt oaf i n a ic l a s s i f i c a t i o ni n e f 王i e c t i v e i nt h i sp a p e r ，f o rt h er e l a t e di s s u e so ff e a t u r es e l e c t i o na l g o r i t h mi nt h ei o 册a t i o n f i l t e r i n gs y s t e m ，t 1 1 ef o l l o w i n ga s p e c t sw e r es t u d i e da n d d i s c u s s e d ： 1 t h es t r e n g t h sa n dw e a k n e s s e so ff e a t u r es e l e c t i o nc o m m o n l yu s e dw e r e a l l a l y s i z e d ，a n di m p r o v e m e n to fd i r e c t i o nw a l sp o i n t e do u tf o rt h ew e a k n e s s e s t h i sp a p e rf i r s t l yg i v e dt h ec o m p r e h e n s i v ea 1 1 a l y s i so ff e a t u r es e l e c t i o nt e c l l l l o l o 鼢 a n de m p h a t i c a l l yi n 仃o d u c e dt h ef m m e w o r ko ff e a t u r es e l e c t i o nt e c l l l l o l o g y a tp r e s e n t ， s e v e r a lf e a t u r es e l e c t i o n sc o m m o n l yu s e dh a v et h e i rs t r o n gp o i n t sa i l dw e a l ( p o i n t s w e a n a l y z e dt h e i ra d v a n t a g e sa j l dd i s a d v a i l t a g e s 缸o mt h ec o m p u t a t i o n a lc o m p l e x 毋a n d c l a s s m c a t i o ne a e c ti nt l l i sp a p e r a i l dp o i n t e do u tt h er e a s o nt h a tm a yl e a dt oi t i n a d d i t i o n ，a c c o r d i n gt o t h el i t e r a t u r ed a t a r e l a t e d ， w ed e s c r i b e dt h ee x p e r i m e n t c o n c l u s i o n s t h i sc o n c l u s i o n sw e r es a m et ot h ef i n a l l ye x p e r i m e n t a l r e s u l t s 2 af e a t u r es e l e c t i o n 仔a m e w o r kf s b c ( f e a t u r es e l e c t i o nb a s e do nc o l l r e l a t i o n ) w 舔 p r o p o s e d 疗o mt h ed e f i m t i o no ff e a t u r er e l a t i v i t ya 1 1 dr e d u n d a i l c y ，t 1 1 a ti st h ep r o c e s so f f e a t u r es e l e c t i o nw a ss e p a r a t e di n t ot w o s t e ps e c t i o n ：f i r s t ，s e l e c t i n gt h ef e a _ t u r es u b s e t t h a tw a sr e l a t e dt oc a t e g o r i e s ；s e c o n d l y ，r e m o v i n go u tt h er e d u n d a j l tf e a t u r ei t e mi nm e c h o o s e l yf e a _ m r es u b s e tt h r o u 曲t h er e d u n d a l l c ya n a l y s i s ，a 1 1 df i n a l l yg o tt h e0 p t i m i z e d 山东师范大学硕士学位论文 f e a t l l r es u b s e t f i r s t l y ，f o rm es e l e c t i n gf b a 劬e r e l e v a n to fc a t e g o 吼t h i sp a p e rc o n s t m c t sa e v a l u a t i o nf u n c t i o nt os e l e c t i n gf e a t u r ei t e ma c c o r d i n gt ot h ep r i n c i p l e ：i faf e a t u r ei t e m t 厅e q u e n t l ya p p e a r i nt l ed o c u m e n tb e l o n g i n gt oo n ec a t e g o r y ，b u tf e wi no t h e r c a t e g o r i e s ，t h e nt h ef e a t u r ei t e m tc a n 、v e l lr e p r e s e n t et h i sc a t e g o r y ，a n ds h o u l db e 西v e n ah i 曲e rw e i g h t ，a n ds h o u l d b es e l e c t e da st h ec a t e g o r i e so ff e a t u r ew o r d st o d i s t i n g u i s h e df r o mo t h e rc a t e g o r yo fd o c u m e n t s i na d d i t i o n ，t h i sp a p e ri n t r o d u c e st h e i d e ao fw e i g h tc o n l p u t i n gt f i d f ，a n dc o n s i d e r sc o m b i n i n gt h ew o r df e q u e n c ya n dt h e d o c u m e n tf r e q u e n c ya st h eb a s i sf o rt h ee v a l u a t i o no ff e a t u r e s s e c o n d l y ， f o rt h er e d u n d a n c ya i l a l y s i s ， t h i s p a p e ra d o p t s t h ea l g o r i m m so f k m e a n sc o m m o n l yu s e di nt h ec l u s t e r i n gm e t h o da l sc o r ea l g o r i t h mt or e m o v i n g r e d u n d a n c v f o rt h es e l e c t i o no ft h ec e n t e ro fi n i t i a lc l u s t e ra n dt h en u m b e ro ft h ei n i t i a l c l u s t e ri n t h i sa l g o r i t h m ，t h i sp a p e rh a si m p r o v e dt h o s ei s s u e si no r d e rt om a k i n g s i m i l a r yk m e a i l sa l g o r i t l l r nr e d u c et h er e d u n d a n c yo ff e a t u r e ss e te 肮c t i v e l y 3 f i n a l l y ，t h ep r o p o s e df 色a t u r es e l e c t i o ns t r a t e g yw a sa p p l i e di n t h ep l a t f o mo f n e t w o r ki n f o 肌a t i o nf i l t e r i n g ，a n da c h i e v e ds a t i s t i s 所n ge x p e r i m e n t a le 虢c t t h i sp a p e ra p p l i e dm ef e a t u r es e l e c t i o nf r 锄e w o r ko ff s b ci n t on e t w o r k i n f 0 硼a t i o nf i l t e r i n gs y s t e m ，a n dd i de x p e r i m e n t a lc o m p a r s i o nf o ri n f o m l a t i o n g a i n ( i g ) a n dc h is t a t i s t i c a lm e t h o d s e x p e r i m e n t ss h o wt h a tf s b cm e t h o di sb e t t e r t h a nt h eo t h e r “v om e t h o d si na c c u r a c ya n dr e c a l lr a t e ，a n di tc a nm a k eg o o d p e r f o n n a n c ee s p e c i a l l yi nt h eh i 曲e rd i m e n s i o n k e yw o r d s ：i n f o r m a t i o nf i l t e r i n g ；f e a t u r es e l e c t i o n ；w o r ds e g m e n t a t i o n ；t e x tt e g o r i z a t i o n ； c l u s t e r i n g c l a s s i 6 c a t i o n ：t p 3 9 1 山东师范大学硕上学位论文 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得( 注：如没 有其他需要特别声明的，本栏可空) 或其他教育机构的学位或证书使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表 示谢意。 学位论文作者签名：王殳南 导师签字： 学位论文版权使用授权书 冲膨 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保留 并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本 人授权堂撞可以将学位论文的全部或部分内容编入有关数据库进行检索，可以 采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密 后适用本授权书) 学位论文作者签名：王炙艿 签字日期：2 0 0 吕年 月加目 导师粹、球幼 导师签字：沸缘 签字日期：2 0 0 影年多月孑口日 山东师范大学硕士学位论文 第1 章绪论 本章介绍了网络信息过滤系统的研究背景和现状，并对信息过滤系统中的基 础环节特征选择技术进行了综合分析。包括相关定义、存在的问题以及解决 的途径等。最后，针对目前特征选择技术所存在的问题，提出了本文主要研究工 作。 1 1 网络信息过滤概述 1 1 1 研究背景 随着i n t e m e t 及其相关技术的飞速发展，互联网上出现了海量的、异质的w r e b 信息资源，在这些庞大的信息资源中，蕴含着具有巨大潜在价值的知识。网络信 息资源越来越丰富，网上信息呈爆炸式增长。信息技术已经渗透到我们社会生活 的各个角落，正以前所未有的速度和能力改变着我们的生活和工作方式，我们真 正处于一个“信息爆炸”的时代。这一方面给用户发现信息、利用信息带来了方 便，另一方面，无序、极其庞大的信息世界和成千上万的超级链接，又常常使用 户在查找其所需信息时感到力不从心。据统计，网络信息量虽然巨大，但是对9 9 的用户来说9 9 的信息都是无用信息，所以要想在网络中通过相关链接来找到所 需的信息无异于大海捞针。 面对如此庞大而且急剧膨胀的信息海洋，如何有效地组织和管理这些信息， 并快速、准确、全面地从中找到用户所需要的信息是当前信息科学和技术领域面 临的一大挑战。人们迫切需要能够从w | e b 上快速、有效地发现资源和知识的工具 。目前解决这个问题的方法大致可分为两种：信息检索和信息过滤。 信息检索乜1 是用来描述寻找符合人们兴趣的信息的处理过程，也就是从大量的 动态产生的信息中找出最忠实地满足用户真实所需的信息，且屏蔽其它无用的信 息。它本质上是一种“人找信息”的服务形态，每次检索时要求用户一次性提交 个或几个查询关键词。由于无法全面准确地描述用户真正的信息需求，传统信 息检索技术已经远远不能满足需要。 网络信息过滤一直是伴随着信息检索而长期被人们研究。信息过滤根据信息 内容本身可分为文本信息过滤和非文本信息过滤。文本信息过滤口1 就是依据用户的 信息需求模型，在动态的文本流中，搜索用户感兴趣的文本，它可以分为基于内 容的过滤和合作过滤，前者主要适合用于文本过滤，后者由于可以根据相同或相 山东师范大学硕士学位论文 近兴趣的用户对有关文本所做的评注而相应的做出过滤的判断，具有不依赖内容 的特点，故不仅适用于文本过滤，也可以广泛应用于非文本格式( 如图像、a u d i o 和v i d e o 等) 。由于目前在因特网上主要的信息载体为文本形式，所以本论文只讨 论文本形式的信息过滤技术。 网络信息过滤具有重要的现实意义和巨大的应用价值。网络信息是时常变化 的，用户关心这种变化，在搜索引擎中用户只能不断地在网络上查询同样的内容， 以获得变化的信息，这花费了用户大量的时问，而信息过滤可以有效的克服重复 查询的问题。另外，信息过滤是实现信息的个性化主动服务的前提。个性化服务 的实质是针对性，即针对不同的用户采取不同的服务策略，提供不同的服务内容。 主动服务的实质是主动性，即系统自动按照用户的信息需求提供相应的服务。个 性化主动服务将使用户通过尽可能小的投入获得尽可能好的服务回报。信息过滤 能实现有害信息的过滤，比如一些反动言论、谣言和色情内容；能实现垃圾信息 过滤，比如常见的垃圾邮件；能实现有用信息推荐，比如可以根据不同用户之间 需求的相关性来推荐信息。 1 1 2 研究现状 文本信息过滤属于信息过滤的一个分支，它主要是根据因特网上信息表现形 式大多是文本的方式，将信息过滤技术应用于其上，依据用户的信息需求模型， 在动态的文本流中，搜索用户感兴趣的文本。文本信息过滤包括将用户感兴趣的 信息从动态文本流中抽取出来或者将用户不感兴趣的信息从中剔除。文本信息过 滤涉及的知识范围非常广泛，它综合了知识论、人工智能、自然语言理解等等领 域的知识，文本信息过滤通常分为基于内容的过滤( c o n t e n t b a s e df i l t 谢n g ) 和社会 过滤( s o c i a lf i l t e r i n g ) 两种，而基于文本内容的安全信息过滤技术早期主要采用如 下两种方法来实现过滤和拦截不良信息h 1 ： 1 、构造i p 黑名单数据库，把已经发现的散播不良信息网站的网络i p 地址添 加到i p 黑名单数据库中，如果用户在浏览网页时访问了该数据库中非法i p 地址， 则此次浏览被取消。该方法严重依赖于i p 黑名单数据库是否完备，由于非法网站 的数量每天都在增长，非法网站可以修改主机地址或者屏蔽i p 地址，并且如何严 格准确地确定一个网站是否是非法网站都存在一些问题，因此该方法从技术发展 角度来说不能作为过滤和拦截不良信息的根本手段。 2 、特征词识别的方法，将一些和非法信息有关的特征词存入列表中，通过检 测信息中是否包含这些特征词来决定此次浏览是否被取消。该方法虽然表述简单， 但其涉及的知识范围广泛，研究人员在不断地研究，试图将自然语言理解、人工 智能等领域的知识用于该种方法，以期提高过滤和拦截的性能。 在信息过滤的应用中，最初过滤的对象是定置邮件与新闻组，下面对有关信 2 山东师范大学硕士学位论文 息过滤( 包括文本信息过滤) 的研究历史做一个整体的回顾m 3 。 1 9 5 8 年，l u l l 提出了“商业智能系统”的概念，在这个构想中，图书馆的工 作人员为每个用户创建一个用户配置文件，对于动态到来的新文档，通过精确匹 配的文本选择方法，为每个用户产生一个符合信息需求的新文本清单，同时记录 下用户所订阅的文本用于更新用户的需求模型。虽然缩微胶片和打印机技术的发 展，使得最终实现的物理细节有所不同，但他的工作涉及到了信息过滤系统的每 一个方面，为文本过滤的发展奠定了有力的基础。 1 9 6 9 年，对s d i ( s e l e c t i v ed i s s e m i n a t i o no f i n f o m a t i o n 选择性信息分发系统) 的广泛兴趣导致了美国信息科学协会( a m e r i c a ns o c i e t yo f i n f o m a t i o ns c i e n c e ) 创建 了s i g s d i ( 选择性信息分发特别兴趣小组s p e c i a li n t e r e s tg r o u p ) 。h o u s e m a l l19 6 9 年对该组织的调查中，研究了6 0 个可运行的系统，其中有9 个系统的用户在1 0 0 0 个以上，这些系统大多数都遵循l u i m 模型，只有很少的系统能够自动更新用户的 需求模型，其它大多数都依靠专门的技术人员或用户自己维护。s d i 兴起的主要原 因是实时电子文本的可用性和用户需求模型与文本匹配计算的可实现性。 1 9 8 2 年，d e 皿i n g 在3 月的c a c m 中首次提出了“信息过滤 的概念，其目 的在于拓宽传统的信息生成与信息收集的讨论范围。他描述一个信息过滤的需求 例子，对于实时的电子邮件，利用过滤机制识别紧急的邮件和一般例行的邮件， 他采用了一个“内容过滤器”来实现，其中采用的主要技术有层次组织的邮箱、 独立的私人邮箱、特殊的传输机智、阈值接收和资格验证等。 d e m l i n g 的文章只涉及了电子邮件，而后来的文章又涉及到了新闻组、u s e n e t 、 以及其它一些网络资源。这期间最有影响的文章是m a l o n e 等人于1 9 8 7 年发表在 c a c m 上的文章。m a l o n e 构造了名为“i n f o n n a t i o nl e n s ”的系统，提出了三种信 息选择模式：认知、经济、社会。所谓的认知模式相当于d e l l i l i n g 的“内容过滤 器”，即后来的基于内容的过滤( c o n t e n t b a s e df i l t e r i n g ) ；经济模式来自于d e l h l i n g 的阈值接收思想，即考虑了信息的价格因素；m a l o n e 及其同事最大的贡献在于提 出了社会模式，目前也称之为合作过滤( c o l l a b o r a t i v ef i l t e r i n g ) 。在社会过滤系统 中，文本的表示是基于以前读者对于文本的标注，通过交换信息，自动识别具有 共同兴趣的团体。但是，目前基于内容的过滤与社会过滤之间的结合仍然是一个 未解决的问题瞄。 1 9 8 9 年，在这个时期信息过滤获得了大规模的政府赞助。由美国d a 船a 资 助的m u c ( m e s s a g eu n d e r s t a l l d i n gc o n f e r e n c e ) ，极大地推动了信息过滤的发展， 它利用信息抽取技术支持信息的选择，在将自然语言处理技术引入文本过滤研究 方面进行了积极的探索。1 9 9 0 年，d a r p a 建立了t i p s t e r 计划，支持m u c 会 议参与者的研究工作，其目的在于利用统计技术进行消息的预选，然后再应用复 杂的自然语言处理，这个文本预选过程称之为“文本检测”。 1 9 9 2 年，美国国家标准和技术研究所n i s t ( n a t i o n a li n s t i t u t eo f s t a i l d a r d s 觚d 3 山东师范大学硕士学位论文 t e c h n o l o g y ) 与d a 刚) a 联合赞助了每年一次的文本检索会议t r e c ( t e x tr e t r i e v a l c o n f e r e n c e ) ，对于文本检索和文本过滤的发展给予了极大的支持。t i 也c 会议有 两个基本任务畸3 ，一个是类似于信息检索的a dh o c 任务，用新的主题在相对静止 的信息源中搜索；另外一个是类似于信息过滤的分流( r o u t i n g ) 任务，用相对不变的 查询在动态信息源中搜索。 在1 9 9 1 年11 月，b e l l c o r e 与a c m 办公信息系统特别兴趣小组( s i g o i s ) 共同 支持了一个“h i 曲p e r f o n n a n c ei n f o 咖a t i o nf i l t e 血g ”会议，将已有的许多研究工 作综合在一起，为信息过滤研究构造了一个坚实的基础，一年后，在c a c m 的第 1 2 期上出版了该会议的专干i j 。 1 1 3 常用的信息过滤系统 根据过滤信息的原理可以将目前国内外出现的常用的信息过滤系统分为基于 内容的过滤系统和基于社会的过滤系统。基于内容的过滤系统口1 有p e r s o n a l w 曲w a t c h e r 、s y s “l l & w 曲e r t 、l e t i z i a 、c i t e s e e r 、i 州曲、s i f t e r 、p v a 、w e b m a t e 等；基于合作的过滤系统有g r o u p l e n s 、l e t sb r o w s e 、f i r e n y 、s e l e c t 、l i k e m i n d s 、 c y b e r s i t t e r ( s o l i do a ks o r w a r e ) 、n 2 h 2 、s m a n f i l t e r ( s e c u r ec o m p u t i n g ) 、w r e b i n s p e c t o r ( e l r o ns o r w a r e ) 、x s t o p ( l o g o nd a t ac o r p o r a t i o n ) 等等。j j 也外，还有大众 型的过滤软件，如c y b e 啦a t r o l ( m i c r o s y s t e ms o r w a r e ) 、“冲浪守护神”、“家长控制” 等。 国产的过滤软件主要有：北京即时通科技有限公司的“中华滤剑信息过滤软 件 ，北邮信息科技发展有限责任公司的“智能网络信息过滤系统”，北京世纪瑞 达存储技术有限公司的“网络保姆”，上海康能( 集团) 有限公司和宁夏回族自治区 公安厅的“网络卫士”，珠海捷朗菱网络科技有限公司的“过滤王”，北京恒创伟 业科技有限公司的“超级网管2 0 0 0 ”，大连宏微网络科技有限公司的“超级网管校 园版 ，北京慧峰佳业科技有限公司的“慧峰智能信息过滤系统 ，北京甲骨蓝科 技有限公司“蓝眼睛智能信息过滤系统软件 ，北京清华泰豪智能科技有限公司的 “科教2 0 0 0 校园卫士系统”，中软北京同天网安公司的“同天网安过滤系统”，上 海优异科技有限公司的“校校通信息过滤平台”，郑州美萍软件工作室的“美萍过 滤系统”，趋势科技的“i n t e r s c a nw 如m a i l a g e r 网站安全管理系统”，一妞淘软件工 作室“护花使者”等等。 4 山东师范大学硕士学位论文 1 2 特征选择的提出及研究现状 1 2 1 问题的提出 特征选择算法的研究是网络信息过滤系统的基础研究，通过特征选择获得最 能代表问题空间的特征子集，这将为信息过滤奠定坚实的基础。下面介绍一下特 征选择的相关知识。 特征选择，即从输入特征集合中选择使某种评估标准最优的特征子集。特征 选择是统计学领域的经典问题，自上个世纪6 0 年代起就有学者对特征选择问题 进行研究，但当时主要是从统计学以及信息处理的角度进行研究，而且通常所涉 及的特征数目不多。 特征选择也是机器学习领域的重要问题，对机器学习领域的所有问题都有重 大意义，包括文本分类，数据挖掘，生物信息学，计算机视觉，信息检索，时问 序列预测等。在一个学习算法通过训练样本对未知样本进行预测之前，必须决定 哪些特征应该采用，哪些特征应该忽略。在机器学习领域，学习算法方面已经开 展了大量的研究，但特征选择方面的研究则相对较少。自9 0 年代以来，特征选 择方面的研究引起机器学习领域学者前所未有的重视，主要原因有以下两个方面： l 、许多学习算法的性能受到不相关或冗余特征的负面影响。已有的研究结果 表明，大多数学习算法所需训练样本的数目随不相关特征的增多呈指数性增长 明n 引。l a n g l e y 等的研究表明最近邻法的样本复杂度随不相关特征成指数增长， 其他归纳算法也基本具有这一属性。例如，决策树对于逻辑与概念的样本复杂度 随不相关特征线性增加，但对于异或概念的样本却是呈现指数增长；贝叶斯分类 器虽然对不相关特征的存在不敏感，但其性能却对冗余特征的存在很敏感啤3 。因此， 特征选择对不同情况下的学习算法都有不可忽视的作用。选择好的特征不仅可以 减小计算复杂度，提高分类准确度，而且有助于寻找更精简更易理解的算法模型。 2 、大规模数据处理问题的不断出现。所谓大规模，一方面指样本数目的庞大， 另一方面指描述样本的特征维数高。数据挖掘的发展对大规模数据处理的研究提 出了迫切的要求，如信息检索、遗传基因分析等d 儿1 0 1 。特征空间的维数不宜过高， 这已经是机器学习领域中一条经验性的“公理”，因此，就迫切需要特征选择算法 对高维数据进行降维，而高维数据的特征选择也对已有的特征选择算法提出了严 峻的挑战。 由于上述原因，特征选择成为机器学习领域重要的研究方向，引起越来越多 的机器学习领域学者的兴趣。国内外的各大研究机构如c m u ，s t a n f o r d ， w a s h i n g t o n ，南京大学，哈尔滨工业大学，北京工业大学等都开展了相关研究 【l l 儿1 2 】1 3 】【l4 】 5 山东师范大学硕士学位论文 因此，本文针对特征空间的高维问题，重点研究了如何选取与类别相关的特 征集，并去除特征集中的冗余特征，得到能代表类别空间的特征集。 1 2 2 研究现状 最早的特征选择研究是6 0 年代初开始的，当时的研究通常集中于统计学及 信号处理问题，而且一般涉及到的特征较少，并且通常假定特征问独立。 上个世纪9 0 年代以来涌现的大规模机器学习问题h m 诲1 ，使得已有的特征选 择算法受到严峻的挑战，迫切需要适应大规模数据的准确性和运行效率等综合性 能较好的特征选择算法。特征选择引起机器学习领域学者广泛的研究兴趣n 肌2 m 6 1 。 近十年来，特征选择研究呈现出多样化和综合性的趋势。各种新搜索算法和 评估标准都应用到特征选择算法中。如粗糙集算法n7 i ，神经网络剪枝法n 引，支持 向量机的评估标准n 明髓引，特征集的模糊熵评价瞳，马尔可夫算法等乜2 j 。并且除监 督式学习的特征选择研究外，也开展了关于非监督式学习的特征选择研究。另 外还出现了关于特征选择的算法融合性的研究，如关于f i l t e r 方法和w a p p e r 方 法结合的研究心引，以及特征选择和样本选择的组合研究瞳5 1 。 1 3 本文的主要工作及内容安排 目前，很多对信息过滤领域的研究工作都集中在其学习算法的改进和创新上， 但是特征选择是学习算法的基础工作，如果基础工作不踏实，即使学习算法再优 秀，其效果也不会很理想。因此，本论文将研究重点放在选取最优特征子集上， 从特征类别相关性和冗余性的定义出发，提出了一种特征选择框架，最后将所提 出的特征选择策略在网络信息过滤平台上进行了实验测试。 本文共分五章，大致结构如下： 第一章绪论部分主要介绍了论文的研究背景和意义，并对信息过滤系统以及 特征选择技术的相关领域内的研究现状和存在的问题进行了阐述，最后给出了本 文的主要研究内容和结构安排。 第二章介绍了网络信息过滤中的相关技术，包括数据包捕获、分词、特征选 择以及文本分类方法等，并着重对本文的研究重点特征选择技术做了综合分析， 详细介绍了特征选择技术的框架和常用的几种特征选择方法。 第三章针对特征选择方法中存在的问题进行了研究和改进，提出了一种特征 选择框架，即把特征选择分两步来进行：首先选取类别相关的候选特征集，将t f i d f 权重计算的思想引入进来，考虑将词频和文档频率共同作为评价依据，然后构造 评价函数来选取类别相关的特征项；然后通过聚类方法剔除候选特征集中的冗余 信息，最终得到优化的特征子集。 6 山东师范大学硕士学位论文 第四章介绍了网络信息过滤系统框架，将文中提出的特征选择策略应用于信 息过滤系统，并对改进算法的有效性进行了验证和分析评价。 第五章对全文进行了总结，并针对不足之处提出了未来工作的研究方向。 7 山东师范大学硕士学位论文 第2 章网络信息过滤的相关技术 本章详细介绍了网络信息过滤的关键技术，如数据包捕获、分词技术、特征选 择方法、文本分类方法。并着重介绍了特征选择技术的框架，然后归纳分析了目 前常用的几种特征选择方法。 2 1 数据包捕获 网络封包的截获技术分为几种，例如，t d i 过滤驱动程序，n d i s 中间驱动程 序以及w i n s o c k 2s p i 截取技术等等。其中以w i n s o c k 2 使用最为广泛，在本系统 中就采用了w i n s o c k 2s p i 进行应用层封包过滤技术。下面简单介绍一下该技术。 w i n s o c k 2 引入了一种新的编程接口，称为服务提供者接口( s e r v i c ep r o v i d e r i n t e r f a c e ，s p i ) 。w i n s o c k2s p i 除了有完成网络传输的传输服务提供者，还有 提供友好名字服务的名字空间服务提供者。其中，传输服务提供者能够提供建立 通信、传输数据、流量控制和错误控制等服务。各种服务提供者是w i n d o w s 支持的 动态链接库( d 1 1 ) ，挂靠在w i n s o c k2 的w s 2 3 2 d 1 1 模块下。s p i 以动态链接库的形 式出现，工作在t c p i p 协议的应用层，对基于应用层的数据包，如f t p 、h t t p 、s m p 等，s p i 都可以截获其数据包，并为上层a p i 调用提供接口函数。 2 1 1 封包截获 用户在进行数据封包截获时，需将自己编写好的s p i 程序安装到系统上，这时， 所有的w i n s o c k 请求都会首先发送到这个预先编好的s p i 程序中。在这个程序中， 用户可以加上自己的处理程序段，如对封包进行协议解析、信息过滤等功能，然 后回调系统函数，由系统函数完成网络传输功能。 具体实现方法是：传输服务提供者作为一个标准w i n d o w s 平台下的d l l ，它对 外只有一个引出函数一w s p s t a r t u p ，这个函数是w i n d o w ss o c k e t2 应用程序调用 s p i 程序的初始化函数，也就是入口函数：w s p s t a r t u p 的参数l p w s a p r o t o c o l i n f o w 指针提供应用程序所期望的协议信息，然后通过这个结构指针可以从注册 表中查到所保存的系统服务提供者的d l1 名称和路径，加载系统服务提供者。查找 到系统s p i 程序的w s p s t a r t u p 函数的指针，通过这个指针，就可以将自己服务提供 者的w s p s t a r t u