（计算机应用技术专业论文）中文文本过滤技术的研究与实现.pdf

摘要 i n t c m e t 技术的迅猛发展和空前普及给人们带来了诸多方便的同时，也带来 了很多问题。网络在传播有用知识和信息的同时，也正在被不法分子、反动敌对 势力等信息内容的发布者所利用，传播各种敏感政治言论和不益于青少年成长的 不良信息。因此，不良信息过滤受到了社会各界的关注和重视，特别是自然语言 处理领域的专家学者们，而文本过滤又是信息过滤研究中的一个重要分支。 本文全面分析文本过滤技术当前的发展状况及文本过滤方法的基础上，深入 讨论了文本过滤的相关理论和技术，详细分析研究了各种特征抽取方法、文本表 示方法和分类算法。在此基础上，阐述了基于l s i 和l a m 的文本分类技术，并 采用以上方法实现了一种基于l s i 和k n n 两类文本分类的过滤技术。 同时，本文还探讨了在内容过滤中广泛应用的串匹配技术。全面分析研究了 各种常用的单模和多模匹配算法。在此基础上，深入研究基于w um a n b e r 的多 模匹配算法并分析其匹配过程，提出一种改进的w um a n b e r 多模匹配算法，充 分利用第一个匹配成功且在模式串中只出现一次的块字符在模式串中的位置信 息，在不大于最小模式串长度的情况下，选择其和不良块字符的转移距离中的较 大值进行转移。实验数据表明，在绝大多数情况下改进算法可以减少匹配次数， 增加转移距离，提高算法匹配效率 最后，将改进的w um a n t 脚多模匹配算法和基于l s i 和k n n 的两类文本分 类技术相结合，设计出一种新的文本过滤方法，并实现一个基于新方法的校园网 页文本过滤原型系统。在收集的语料库上对基于新方法的系统和单独使用基于 l s i 和k n n 文本分类的过滤方法的系统进行实验，结果显示，通常情况下前者 的性能优于后者。 关键词文本过滤：串匹配；潜在语义索引；多模式串匹配 a b s t r a c t a si n t e m e ti si n c r e a s i n ga taf a s t e ds p e e da n dw i d e s p r e a d , i tb r i n g su 8t om u e l a c o n v e n i e n c e 。b u ti ta l s ob r i n g su st om a n yp r o b l e m s w h e nh i t 黜ti sp r o p a g a t i n g u s e f u li n f o r m a t i o n , i ti su s e dt op r o p a g a t es e m i d v ep o l i t i c a lr h e t o r i ca n db a d i n f o r m a t i o nt h a ti sn o tb e n e f i tt oy o u n gp e o p l eb yl a w l e s se l e m e n t sa n dh o s t i l ef o r c e s s ob a di n f o r m a t i o nf i l t e r i n gb l x 3 0 l n e sv e r yi m p o r t a n ta n di sp a i da t t a a t i o t lt ob ym a n y p e o p l e ，e s p e e i a u ye x p e r t si n t h ef i e l d so fn a t u r a ll a n g u a g ep r o c e s s i n g a d dt e x t f i l t e r i n gi s 趾i m p o r t a n tb r a n c hi at h ef i e l do f i n f o r m a t i o nf i l t e r i n g t h i sp a p e rc o m p l e t e l ya n a l y z e sp r e s e n ts t a t u so fr c s e a r e l aa n dm e t h o do ft e x t f i l t e r i n g ，a n dt h e nd e e p l yd i s c u s s e s t h et h e o r i e sa n dk e yt e c h n o l o g y t h ep a p e r a n a l y z e sa n ds t u d i e sk i n d so fm e t h o d so ff e a t u r ee x l x a c t i o n , r e p r e s e n t a t i o no ft e x t , t e x tc l a s s i f i c a t i o n a c c o r d i n gt ot h i s ，t h ep a p e rs h o w st h es t e po f t e x tc l a s s i f i c a t i o nb y u s i n gl s ia n dk n n ，a n dt h e ni m p l e m e n t ei tb yt h ea b o v em e t h o d s a l s o , t h ep a p e rs t u d i e so fs t r i n gm a t c h i n gt e c h n o l o g yw i d e l ya p p l i e di nc o n t e n t - f i l t e r i n g w ec o m p l e t e l ya n a l y z em a i na l g o r i t h m su s e di ns i n g l ep a t t e r nm a t c h i n ga n d m u l t i p l ep a t t e r nm a t c h i n g ，e s p e e i a n yw u m a n b e ra l g o r i t h m a c c o r d i n gt ow um a n b e r a l g o r i t h m w ep r o p o s ea ni m p r o v e dw um a n b e ra l g o r i t h m , t h a tm a k e sf u l lu s eo f b l o c ko fc h a r a c t e r sw h i e l ai st h ef i r s tt ob em a t c hs u c c e s s f u l l ya n dt h eo n l yi n p a t t e r n s u n d e rs h i f td i s t a n c eo f b l o c ko f c h a r a c t e r sa n dg o o dc h a n l c t c ri ss m a l l e rt h a n l e n g t ho fm i n i m u mp a t t e m , t l a ei m p r o v e da l g o r i t h ms h i l lw i n d o wb a s e d0 ns m a l l e r v a l u eo ft h e l n t h ee x p e r i m e n ti n d i c a t e , t h ei m p r o v e da l g o r i t h mu s u a l l yg a i n sl e s s m a t c h i n gf r e q u e n c y , i n c r e a s e ss h i f td i s t a n c ea n di m p r o v ee f f e c to f m a t c h i n g a tl a s t , t h ep a p e rd e s i g nan e wt e x tf i l t e r i n gm e t h o d , t h a tc o m b i n e st h ei m p r o v e d w um a n b e ra l g o r i t h mw i t ht e x tc l a s s i f i c a t i o nm e t h o db a s e do nl s ia n dk n n a c , c o r d i n gt ot h ei i c wm e t h o d ，w ei m p l e m e n t e 觚a r c h e t y p a lt e x tf i l t e r i n gs ) r s c e m b a s e do i lc a m p u sw e ba n dt e s ti to nt h ec o l p l l l st h a tw ec o l l e c t e d t h er e s u l ts h o wt h a t t e x tf i l t e r i n gs y s t e mb a s e do nt h en e wm e t h o di su s u a l l yb e t t e rt h a nt e x tf i l t e r i n g s y s t e mo n l yb a s e do i ll s ia n dk n n t e x tc l a s s i f i c a t i o nt e c h n o l o g yi np e r f o r m a n c e k e y w o r d s t e x tf i l t e r i n g ；s t r i n gm a t c h i n g ；l a t e n ts e m a n t i ci n d e x i n g ；m u l t i - p a t t e r n m a t c h i n g 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意 签名：麴垫基日期：卫丑6 ：岔 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文 ( 保密的论文在解密后应遵守此规定) 第1 章绪论 1 1 研究背景 第1 章绪论 近些年来，随着i n m n c t 技术在我国的迅猛发展和空前普及，互联网逐渐渗 入到人们生活的各个角落，成为人们生活中的重要组成部分。它给人们提供了大 量的信息，为人们的工作、学习和生活带来了极大的便利，为青少年的成长与发 展提供了广阔的空间。然而由于网络的开放性、匿名性和无国界性，网络在传播 有用知识和健康信息的同时，也正在被一些不法分子、反动敌对势力等信息内容 的发布者所利用，传播各种反动、迷信、色情、暴力等不良信息。 中国互联网络信息中心( c n n l c ) 2 0 0 5 年7 月2 1 日发布的“第1 6 次中国 互联网络发展状况统计报告”显示，截至2 0 0 5 年6 月，我国上网用户总数已达 1 0 3 0 0 万，其中年龄在2 4 岁以下的青少年占5 3 5 ，是网络用户的主体。 由此可见，青少年们既是网络的最大受益群体，同时也是网络的最大受害群 体。青少年们身心尚未成熟，自我保护意识和防范侵害能力相对薄弱、分析判断 能力不强，最容易受不良信息的影响。概括起来，网络不良信息给他们带来的负 面影响主要体现为： ( 1 ) 反动敌对势力加大反动腐朽思想文化的侵蚀境内外反动敌对势力利 用网络进行反动渗透，直接危害国家的安全和人民的根本利益，特别是毒害青少 年一代。一是邪教组织建立网站，传播歪理邪说，极力宣扬种族歧视，煽动民族分 裂，破坏民族团结，煽动不明真相的群众闹事，扰乱社会秩序；二是西方资本主义 国家在网上进行和平演变，有材料说，国际互联网上传输的信息，9 0 以上来自西 方资本主义国家，其中8 5 来自美国，他们通过网络向发展中国家输出其资本主义 国家的政治思想，诋毁、侵蚀着社会主义国家的意识形态，传播他们的价值观、 人生观和生活方式等。妄图对网民特别是思维活跃而涉世未深的青少年产生潜 移驮化的影响。 ( 2 ) 黄色信息泛滥，毒害校园学子们的身心健康随着互联网的高速发展， 网络黄毒也随之泛滥。美国一家公司n 2 h 2 发现，与色情相关的网页已经从1 9 9 8 年的1 4 0 0 万增至2 0 0 3 年的近2 亿6 0 0 0 万，互联网过滤评估机构估计，全球大 概有4 2 0 万个色情网站，占所有网站总数的1 2 。现实生活中。少而不宜”的 东西在网上随处可见。有一项调查表明，被抽取的三千名大中学生中，曾光顾色情 网站的占4 6 ，美国色情杂志“花花公子”网址一周内的访问者多达4 7 0 万人次， 其中青少年占了相当大的比重这对青少年的身心健康造成了极大的摧残，使部 北京工业大学工学硕士学位论文 分青少年深陷其中不能自拔，不仅荒废学业，浪费时间，而且消磨其意志，败坏 其道德品质，危害社会 ( 3 ) “网络暴力”容易扭曲青少年的心灵，甚至误导青少年们走上违法犯罪 的道路“网络暴力”常常是通过言语抨击、枪战、暗杀、绑架、帮派行会等方 式表现出来。随着网络技术的不断发展，论坛、b b s 、网络游戏等相关网站随之 出现，这些网站中很多含有网络暴力内容。据德国西蒙维森塔尔中心在2 0 0 5 年7 月8 日公布的网络暴力和种族主义问题调查报告显示自从2 0 0 4 年“9 1 1 ” 事件以来，互联网上关于自杀性炸弹和暴力的宣传及类似内容的游戏显著增加。 这样，网络用户特别是青少年们，成为了网络暴力的受害者。一方面，他们成为 暴力行为和语言的攻击对象，轻则遭致谩骂、诋毁，重则被诈取钱财。另一方面， 他们本人也受到了不良影响，如迷恋暴力内容的电子游戏，萌生或增强暴力倾向； 看到大量暴力图片、节目和文字，并模仿那些语言和行为；还有就是出于报复心 理，对他人进行人身攻击甚至去诱骗他人，就这样，许多网络上的虚拟暴力最终 以另一种方式变成了现实的暴力。 因此，过滤不良信息，为青少年们提供一个“绿色”的网络空间成为一个全 社会普遍关注的急需解决的问题。由于目前网络上的信息9 0 以上都是文本信 息，因此文本信息的过滤就成为了技术的焦点。随着网络文本信息的日益增多， 文本过滤技术已经成为信息处理领域中的一个相当活跃的分支。 1 2 文本过滤的研究现状 1 2 1 国外研究现状 1 9 8 2 年，d e n n i n g 首次提出了“信息过滤”概念【“，并描述了一个信息过滤 的需求例子：对于实时的电子邮件，利用过滤机制，识别出紧急的邮件和一般例 行邮件。他采用了一个。内容过滤器”来实现过滤功能，其中采用了层次组织的 邮箱，独立的私人邮箱、阈值接收、资格认证等主要技术。 1 9 8 7 年m a l o n e 等在c a c m 上发表了相关方面较有影响的文章田，构造了名 为“i n f o r m a t i o nl e n s ”的系统，提出了三种信息选择模式：认知、经济、社会 其中认知模式相当于d e n n 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 n n 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 r p a 资助的 。m e s s a g eu n d e r s t a n d i n gc o n f e r e n c e ”极大地推动了信息过滤的发展。他在将自 2 第1 章绪论 然语言处理技术引入文本过滤研究方面进行了积极的探索，用信息抽取技术支持 了信息的选择；1 9 9 0 年，d a r p a 建立了t i p s t e r 计划，目的在于利用统计技 术进行消息预选，然后再应用复杂的自然语言处理。 之后的1 9 9 2 年，n i s t ( 美国国家标准和技术研究所) 又与d a r p a 联合赞 助了每年一次的t r e c ( t e x tr e t r i e v a lc o n f e r e n c e 文本检索会议) 对文本过滤的 形成和发展提供了强有力的支持。目前t r e c 的过滤任务要求用户的信息需求白 适应地、实时地从具有时序的文本流判断每篇文本是否相关，主要是模拟时间要 求很高的文本过滤应用。 随着因特网的迅速发展，需求的不断增加，在文本过滤以及相关技术方面， 取得了长足的进步，成为信息产业新的增场点，许多文本过滤系统相继开发完成。 s t a n f o r d 大学的t a k w y a n 和h e c t o r g a r c i a - m o l j 1 a 开发了基于内容的过滤系 统s i f t ( s t a n f o r di n f o r m a t i o nf i l t e r i n gt 0 0 1 ) ，该系统用于因特网上新闻组的过滤， 它使用向量空间模型来实现用户信息需求与新闻资料之间的匹配，它的用户需求 信息，即用户模型( u s e rp r o f i l e ) ，是由用户通过提交喜欢的词汇和想要避免的 词汇手工建立的，并且可以自我更新。s i f t 提供了一个高效的过滤算法。由于 将大量的用户模型与中心服务器上的因特网上的每条新闻相比较，工作量很大， 有效的方法是将用户模型分组，分组处理模型比起单个处理显然效率更高，这样 可以将一组文本分配给一组兴趣相同的用户1 3 1 。 s t e v e n s 研制了i n f o s o o p e 系统，它采用了自动用户兴趣模型机制，降低通过 上下文环境构造用户模型的复杂度，它是基于准确匹配规则的系统，通过观察用 户阅读行为，如阅读花费的时间，是否选择保存等，提出相应的过滤规则。 i n f o s c o p e 的机器辅助用户模型学习机制、用户可控的提取机制、隐式的用户反 馈使它成为基于内容过滤的典型例子跚。 m i n n e s o t a 州立大学计算机系的r o b e r tc o o l e y 等人开发了w e b s i f tw e b 站 点信息过滤系统 4 1 。该系统使用站点的内容和结构信息来自动生成信念集，利用 信念集确定潜在兴趣系统采用w e b m i n e r 原型方法将w e b 挖掘过程分为三 个主要部分，即预处理、挖掘算法和模式分析。文中假设内容与结构数据是w e b 站点主要知识的载体，并且网页之问的连接说明网页之间是有关的，结果用支持 度表示。实验结果表明：在过滤发现规则中，即使最简单的结构信息，在表示主 要信息时的效率也是很高的。 n i c h o l s 等人开发的t a p e s t r y 系统是第一个协作过滤的实例嘲。t a p e s t r y 系统 用来过滤个人电子邮件、新闻组信息等。用户手工构造用户模板，不仅根据文本 内容，也可以参考其他用户对于同一文本的评价，这些评价即用户对文本相关的 明确判断，“是”或“否”t a p e s t r y 依赖团体中每个人明确的观点进行协作过滤， 但该方法的前提是团体中每个人相互了解。t a p e s t r y 允许用户为每条规则进行打 分，通过比较规则的得分情况，可以生成排序的输出文本。这个处理过程分为两 3 北京工业大学工学硕士学位论文 个步骤，实现时采用客户服务器方式。首先由服务器确定哪些文本满足哪些用 户模型，传递给相应的用户，然后在客户端进行更为负责的规则匹配任务，产生 最终的排序输出。实验表明，对于众多具有相同兴趣的用户，采用协作过滤效率 较高。 c - r o u p l e n s 是m i l l e r 等人开发的u s c n c tn e w s 协作过滤系统 6 1 ，它建立在客户 服务器模式上，它采用了两种服务器，一是内容服务器，即标准的因特网新闻 服务器；二是评注服务器。系统设计允许复制内容服务器和评注服务器，以便使 每个服务器服务于一定数量的用户。g r o u p l e n s 的评注是5 级的确定性判断，评 注服务器收集用户的评价级别，依据它预测用户对新文本的接受程度，并把这些 文本发送给客户端。在g r o u p l e n s 系统的客户端还可以监视用户阅读文章所用的 时间，并以此获得一个隐含的兴趣级别反映用户对文章的喜欢程度。g - r o u p l c n s 对于协作过滤的贡献在于分布式评价服务器和模型学习机制。 还有一些过滤方案试图将内容过滤和协作过滤相结合。如f a b 系统1 7 1 就是结 合了内容过滤和协作过滤两种模式的典型系统，该系统用于推荐网页；m a r y l a n d 大学的i a n m s o b o r o f f 和c h a r l e s k n i c h o l a s 介绍了一种结合内容和协作过滤的技 术 s l 。 1 2 2 国内研究现状 我国在信息过滤领域的研究起步相对较晚，近年来，随着自然语言处理技术 研究的日益深入，文本过滤作为新一代的个性化信息获取手段，才被迅速的推向 历史舞台，成为各类研究的关注热点。其中最有代表性的研究来自复旦大学黄萱 菁等研究人员基于向量空间模型的文本过滤系统i q 。2 0 0 0 年，该系统参加了 t r e c 9 会议的f i l t e r i n g 子项目，利用t r e c 提供的规范语料库，他们从主题描 述和正例文档中抽取特征向量作为用户的初始需求模型，在与训练集的交互( 即 计算相似度) 中获取关于每个主题的初始阈值。之后再与测试集进行交互，判断 测试集中的文档是否大于某主题的阈值条件，如果满足条件，则将其归入正例文 档集，否则归入反例文档集，然后从正、反例文档集中抽取特征向量，以更新初 始需求模型，其中包含对阈值的动态调整【1 0 1 。 东北大学的姚天顺教授和林鸿飞博士等人进行了中文文本过滤技术的研究 ( 使用新闻资料作为其语言语料库) ，在他们提出的中文文本过滤模型中，用户 需求采用基于示例文本的主题词表示，文本表示采用向量空间模型，需求与文本 的匹配技术采用向量夹角余弦作为相似系数，为了更好的排列满足阈值要求的文 本，在对文本进行索引的时候，他们引进文本结构分析技术，从文本中获取逻辑 层次信息，以期提高文本片断检索时文档与查询的匹配效掣“1 另外，他们还进 行了基于混合模式的文本过滤模型1 1 2 1 ，其基本思想是将基于内容过滤方法和协作 4 第1 章绪论 过滤方法结合起来，给出了用户评注的权威性和一致性度量，以便更好的运用用 户的评注信息。在此基础上，结合用户的个人兴趣，给出了文本特征抽取机制、 文本推荐机制、文本与信息需求模型的匹配机制。 来自中科院声学所的晋耀江等研究人员( 2 0 0 3 ) 在文本过滤语义模型的研究 上做出了积极贡献1 1 3 1 。他们利用文本形式化的语义模型一语境框架i “】( h n c ) ，将 文本内容抽象成领域( 静态范畴) 、情境( 动态描述) 、背景( 褒贬、参照等) 三个框 架。根据语境相似度的计算，把文本过滤问题转换成语义框架的匹配问题，有效 地处理了语言中的褒贬倾向、同义、多义等现象。复旦大学吴立德课题组( 2 0 0 4 ) 在文本语义分析上的另一项探索是：以知网为语义知识库【1 5 1 。试验表明，基于语 义信息的文本特征项抽取方法，比单纯词汇信息更能体现文本的概念特征，从而 获得较优的过滤性能。 1 2 3 目前的文本过滤方法 自d e n n i n g 首次提出了“信息过滤”概念到现在，国内外许多学者对文本过 滤技术和文本过滤系统进行了研究。纵观这些文本过滤的解决方案和实现技术， 文本过滤方法分为：基于内容的过滤( c o n t e n t - b a s e df i l 删和协作过滤 ( c o l l a b o r a t i v ef i l t e r i n g ) ( 1 ) 基于内容的过滤方法也称为认知过滤，这种方法按照信息内容的特 征做出选择，主要采用了自然语言处理、人工智能、概率统计和机器学习等技术 进行过滤。过滤系统把每个用户的信息需求表示成一个用户需求模板，利用关键 词将进入的信息流与用户需求模板进行相似度匹配计算i l 司。过滤的结果作为反馈 更新用户需求模板。内容过滤能够监测现有信息的内容特征，为用户提供与其曾 经感兴趣信息相似的信息，但不能为用户发现新的兴趣信息。目前，分配列表和 关键词匹配是最基本的基于内容的过滤形式。 ( 2 ) 协作过滤又称作社会过滤( s o c i a lf i l t e r ：i n g ) 1 7 1 ，是“相似”用户间的 相互合作过程。通过分析用户兴趣，在用户群体中找到与指定用户兴趣相同或相 似的用户，综合这些相同或相似用户对某一信息的评价，形成系统对该指定用户 对此信息的喜好程度预测i l q 。在协作过滤系统中，用户的目标、经验、职业、兴 趣爱好以及思想观念等对于过滤任务是相当重要的。然而正是因为这些，即使用 户对同一领域感兴趣，对待某一信息的态度也不一定相同。 在这两种文本过滤方法中，基于内容的过滤是目前最主要，也是研究最多的 过滤技术。而且目前基于内容的文本过滤算法的研究主要是基于统计的过滤方 法、基于知识的过滤方法和基于模式串匹配的过滤方法。 ( 1 ) 基于统计的过滤方法这种方法主要延续了传统信息检索和自然语言 处理中的理论和方法，尤其在对信息内容的理解和表示方面。用此类方法实现的 北京工业大学工学硕士学位论文 过滤系统通常将用户需求以用户模板的形式来描述，通过在过滤模块中实现一个 基于统计的算法，来计算用户模板与文档向量间的相似度，比如检索中的c o s i n e 方法就是其中最为通用的相似度计算方法。对评估过相似度的文档，依照一定的 算法进行排名，然后再根据事先定义的规则判断是否过滤该信息。过滤系统还将 通过用户的相关反馈实现一个学习过程，从而更新用户模板，为新一轮的过滤提 供更好的用户需求表达。构造新的用户模板时通常会考虑模板中原有的查询项在 相关文档和无关文档中的频率【l q ，赋予它们新的权值，或者从检出文档中选择新 的查询项对原有模板进行扩充。 基于统计的过滤算法，主要有文本的自动分类算法。文本的信息过滤本质上 可以看成对信息进行分类的问题。一般，可将所有文本分为包含用户感兴趣敏感 信息，即需要过滤出的一类，及用户不感兴趣的一类。因此，自动文本分类技术 是信息过滤中应用较多的技术，这种技术主要是基于统计的。如最近邻居法，贝 叶斯算法，支持向量机等。 ( 2 ) 基于知识概念的过滤方法基于知识概念的过滤方法使用了人工智能 中的相关技术，如规则生成( p r o d u c t i o n - r u l e s ) 、语义网( s e m a n t i c - n e t ) 和神经网络 ( n e u r a l - n e t w o r k s ) 。在基于知识概念的过滤算法中，知识论以词语所代表的概念 为描述对象，发现概念与概念之间以及概念所具有的属性之间的关系，形成一个 包含若干接点和连线的网状结构的知识模板。采用这些技术的应用更加注重对信 息内在含义的理解，挖掘信息之间的内在联系。基于知识概念的过滤系统使用它 们来构造用户模板，从而进一步实现过滤和学习的功能。 ( 3 ) 基于模式串匹配的过滤方法模式串匹配算法是内容过滤和内容检测 系统中的一类很重要的分析方法。在基于模式串匹配的过滤算法中，用户输入代 表自己兴趣的一个或者多个特征关键词作为过滤关键词，然后逐字扫描文本内容 并和预定义的过滤关键词进行比较，如果文本中包含了一定数目的过滤关键词， 则过滤该文本。这种方法计算量很小，处理速度快，易于实现，适合明显含有用 户感兴趣的关键词的文本内容过滤。然而这种过滤方法也存在着问题，因为关键 词是人们常用的词，有些敏感信息内容的发布者为了避免被发现，他们使用其他 的词或者使用关键词的变型来代替，使得基于关键词的文本过滤机制不能识别。 1 3 课题来源 本课题来源于北京市科委资助项目“基于校园网的可信运行保障系统研究” ( 编号：y 0 1 0 5 0 0 7 0 4 0 1 2 1 ) 。在项目中，本课题在校园网页文本内容的检测和过 滤方面做了一定的研究和实现。目前，基于校园网的可信运行保障系统研究项目 完成了安全管理控制门户、基于8 0 2 i x 的内网安全控制、基于s n m p 的内网安 全控制、校园网网络追踪以及校园网网页内容检测过滤各模块的研究与实现，并 6 第1 章绪论 且已经被北京市科委成功验收。 1 4 本文研究内容及结构 目前，很多在文本过滤方面的研究主要集中在对基于统计的过滤方法、基于 知识的过滤方法和基于模式串匹配的过滤方法中任意一种的研究和，本文研究了 文本过滤的关键技术，着重研究并实现了基于l s i 和k n n 的中文文本分类技术， 同时研究改进并实现了一种基于w um a n b e r 的多模匹配改进算法。然后针对不 良文本信息过滤提出一种新的文本过滤方法，即将基于改进的w um a n b e r 多模 匹配算法和基于l s i 和k n n 两类文本分类技术相结合的文本过滤方法，并实现 一个校园网页文本过滤原型系统 本文的内容结构安排如下： 第一章首先介绍了课题研究的背景，引出进行文本过滤的必要性，其次总结 了当前文本过滤技术在国内外的研究状况以及主要的且研究较多的文本过滤方 法，然后说明课题的来源，最后介绍论文的主要研究内容及结构安排。 第二章介绍了文本过滤相关理论和关键的技术。首先讨论了文本过滤基本原 理和文本过滤模型，在了解文本过滤基本理论的基础上详细讲述了文本过滤的关 键技术：文本分词技术和文本分类技术，着重讲述了文本分类中涉及的关键技术： 特征抽取、文本表示和文本分类算法，最后研究了基于潜在语义索引( l s i ) 的 文本分类技术，并阐述了基于l s i 和k n n 的文本分类技术。 第三章研究了串匹配文本过滤技术。首先介绍了串匹配技术的相关概念及其 应用领域，它被广泛地应用于内容过滤系统中。然后分析了常用的单模式串匹配 算法和多模式串匹配算法，深入分析研究了w um a u b e r 多模匹配算法，并提出 了一种改进的w um a n b e r 多模匹配算法。 第四章给出了校园网页文本过滤系统的总体设计。首先给出通常的文本过滤 系统的框架，然后提出本系统的设计思想，并给出本系统的体系结构，最后阐述 了整个系统的两大主要模块的详细设计：多模式串匹配模块和基于l s i 和k n n 的文本分类模块。 第五章详细阐述了本系统的具体实现并对其进行实验分析。首先详细介绍了 构成系统的两大主要模块的实现方法，然后在收集的语料库上对本课题实现的两 项文本过滤技术及其系统进行实验。 最后为结束语，总结本文的工作，探讨下一步的研究工作。 7 第2 章文本过滤相关理论及关键技术 第2 章文本过滤相关理论及关键技术 在了解文本过滤的研究现状及文本过滤方法的基础上，本章将深入讨论文本 过滤相关理论和关键技术，并详细阐述基于l s i 和k n n 进行文本分类的详细过 程。 2 1 文本过滤基本原理 文本过滤基本原理如图2 1 所示： 图2 - 1 文本过滤基本原理 f i g u r e 2 1e l e m e n t a r yp r i n c i p l eo f t e x tf i l t e r i n g 文本过滤的基本原理是：根据用户的兴趣创建用户兴趣模板，将信息源中的 文本有效地表示出来，然后根据一定的文本匹配规则，从动态的文本流中将满足 用户兴趣的文本挑选出来，显示给用户，并根据一定的反馈机制，不断地调整用 户兴趣模型，以提高过滤效果。在整个过程中的工作可总结为： ( 1 ) 构建用户兴趣模板用户兴趣模板( u s e rp r o f i l e ) 用于揭示一个或一组 用户长期的信息需求。用户需求模板是信息过滤的基础，模板的准确性、实效性 直接决定过、滤系统的性能的优劣。对于用户的信息需求，可以要求用户填写表 单、评价固定文档集和跟踪用户的网络行为等方面来获取；对于用户的需求模板 既可以从正面揭示，也可以从反面解释，也就是说，既可以描述用户需要的感兴 趣的信息，也可以描述用户不需要的不感兴趣的信息。多数方法通过抽取与兴趣 相关的特征词列表来表达用户需求模板，并借助学习算法，动态调整特征项权值 以适应用户兴趣的变化。由于特征词在语义上的多义性，使得一开始就很难选择 出与用户兴趣完全一致的特征项。所以，模板的扩张和自适应的调整是该任务中 的主要难点，许多研究目前都着眼于解决模板准确性问题上鳓。 ( 2 ) 文本表示在文本过滤系统中，要将动态的文本流表示成为结构化的 信息( 如：特征向量) ，以便为下一步的过滤过程做好准备。一个好的文档信息描 述可以在一定程度上揭示文档的主题信息。经常出现的情况是，过滤系统选择出 9 北京工业大学工学硕士学位论文 一篇相关文档，仅仅因为文档中存在与用户模板一致的特征项这种单纯的字符 串匹配极大地限制了滤出文档的可用性。所以，在文档信息描述中引入浅层的语 义分析，试图揭示出更多的文档主题信息是解决这一问题的有效途径口”。 文档信息的描述模型有多种，目前常用的文档表示模型有布尔逻辑模型、概 率模型、向量空间模型和潜在语义索引模型。 ( 3 ) 用户模板和文本间的匹配用户模板和文档间的匹配在过滤处完成， 这个过程也是文本过滤的核心步骤。过滤部分接收文本流中经过预处理的文本信 息，以及已经构建好的用户需求模板，并调用相应匹配算法比较两者的相似程度， 以确定文档是否满足用户需求。匹配算法的选择与用户需求模板的描述方法、文 档的描述方法是相互联系的。算法既可以做出简单的二值判断，即相关或无关的 判断，并按相关性的大小提供排名列表给用户，由用户自己决定阈值来选择最终 的滤出文档。 目前常用的匹配模型有布尔模型、向量空间模型、概率模型、基于知识的表 示模型以及混合模型等。 ( 4 ) 实现反馈的学习和模板的更新用户的信息需求有一个逐渐明确的过 程，而且处于动态变化过程中，因此，为了提高过滤的效率，系统还需根据用户 对过滤结果的评价，通过反馈机制作用于用户和用户需求模板，使用户逐渐明晰 自己的信息需求，使用户需求模板的描述变得越来越明确、具体。过滤系统调用 用户反馈进行学习，一旦确认更新策略就将这种更新反应到用户建模部分。用户 模板的更新周期以及更新策略的选择是实现自适应文本过滤系统的关键试验证 明，在模板更新趋于稳定阶段及时停止对反馈的学习，对减少噪音对系统的影响 有很好的效果瞄】。 在现有技术条件下，为了提高系统的实用性，往往会对关键部分进行必要的 人工干预，如对动态的文本流先做预处理、人工修改用户需求模板等等。 2 2 文本过滤模型 信息检索模型是将文本表示、查询以及它们之间的关系进行建模的框架。目 前常用的信息检索模型有：布尔模型、概率模型、向量空间模型、潜在语义索引 模型、神经网络模型。由于信息过滤和信息检索的关系类似于一个硬币的两个侧 面，是处于一个统一体的不同侧面例，所以文本检索模型也适用于文本过滤。 2 2 1 布尔模型 布尔模型( b o o l e a am o d e l ) 是最广泛使用的模型之一在布尔模型中，首 先建立一个二值变量的集合，这些变量对应于文本的特征项。文本用这些特征项 l o 第2 章文本过滤相关理论及关键技术 变量来表示，如果出现相应的特征项，则特征变量取“t r u e ”，否则，特征变量 取“f a l s e ”。查询采用特征项和逻辑运算符“a n d ”，“o r ”和“n o t ”组成。 文本与查询的匹配规则遵循布尔运算的法则。 布尔模型的主要优点是：速度快，易于表达一定程度的结构化信息，如同义 关系( 电脑o r 微机o r 计算机) 或词组( 文本a n d 过滤a n d 系统) 其缺点 是：把布尔模型作为文本的表示很不精确，不能反映特征项对于文本的重要性， 缺乏定量的分析，过于严格，缺乏灵活性。 2 2 2 概率模型 概率模型是基于提问词在相关和非相关文档中的分布概率的，其基本思想就 是根据关键词在相关文档中出现的概率和无关文档中出现的概率来判断该关键 词的权重。其计算方法如式( 2 - 1 ) 所示： = l o g ( r c r r ) ) 一，) ( 一打一震+ ，) ) ( 2 1 ) 式中 词f 在提问- ，中的权重； ，提问，所得到的相关文献中包含标引词i 的文档数量： 胄与提问，相关的文档总数； 以用于检索的所有文档中包含标引词i 的文档数量； 文档集中包含的文档数目。 概率模型的特点是：首先，应用模型去预算相关性；其次，应用需求中不同 词的权值为线索判断相关性。它通过应用概率方法减低了相应的文本排列问题的 困难。 概率模型具有如下优点： ( 1 ) 采用严格的数学理论为依据，提供了一种数学理论基础来进行检索； ( 2 ) 采用相关反馈原理，可开发出理论上更为坚实的方法。 概率模型的主要缺点是： ( 1 ) 增加存储和计算资源的开销； ( 2 ) 参数估计难度较大 2 2 3 向量空间模型 向量空间模型( v e c t o rs p a c em o d e l ) 是已被人们普遍认可的一种非常有效的 检索模型。在这种模型中，文档和用户需求模板都用关键字来描述，并被表示成 多维空间中的向量。每个关键字被赋予一个权重，代表了其重要性程度。文档和 用户需求模板之间相似程度的度量是通过比较它们对应的向量来进行的，比如余 北京工业大学工学硕士学位论文 弦相似度或者内积。 向量空间模型具有如下优点： ( 1 ) 向量空间模型使得对查询向量中关键词权重的赋值成为可能； ( 2 ) 利用计算得到的相似度可以对获取的文档按照相关度排序； ( 3 ) 许多实验表明：向量空间模型比布尔模型能够得到更加正确的结果。 向量空间模型也存在一些不足： ( 1 ) 向量空间模型没有考虑关键字的排序。例如，像这样的文档：。一匹马 比一辆车好”和“一辆车比一匹马好”被认为是一样； ( 2 ) 向量空间模型不能表示语义方面，关键词之间的依赖并不存在。例如， 。t a k eo f f y o u rs h o e s ”和“r e m o v et h ef o o t w e a r ”，被认为是不同的，而实际上这 两句话表达的是同一个意思； ( 3 ) 在查询中，不能像布尔模型一样使用关键词之间的逻辑关系。 2 2 4 潜在语义索引模型 潜在语义索引模型( l a t e n ts e m a n t i c 瑚双i n gm o d e l ，简称l s i ) 用概念表 达文档，它要求对整个文档进行研究，来抽取关键词和文档之间的关系。l s i 模 型应用一种强大的、完全自动化的统计方法来计算和模拟这些关系，即奇异值分 解( s i n g u l a r - v a l u ed e c o m p o s i t i o n ，简称s v d ) 洲。与前两种模型相比，l s i 模 型挖掘了文档的内在语义信息，其性能要优于前面两种技术。因为l s i 是根据用 户需求模板与文档的语义相近与否来确认该文档是否满足用户信息需求，即只要 被考查文档与用户需求模板的语义相近度高，就认为符合用户需要并将其递送给 用户。但有时反而适得其反，比如有些文档只是与用户以前阅读的文档稍有不同， 用基于l s i 模型的过滤系统来分析，会得出这些文档与用户需求模板的语义相近 度极高，然而用户并不想反复阅读内容如此相近的文档。 2 2 5 神经网络模型 神经网络中创建的神经元之间的连通机制也适用于信息获取。一个神经网络 由一系列的简单处理单元神经元组成。这些神经元之间通过在大量带权的网络 连接上相互发送信号来通信。每个神经元只接受信号和计算，然后得到一个即将 传播给其他神经元的输出对于信息获取系统来说，每个关键词与一个输入神经 元关联，而每个文档与一个输出神经元相关联。一个查询通过激活与其期望的关 键词所对应的神经元而进入该网络，然后该网络计算输出信号。那些激活的输出 神经元就是与所期望得到的文档相关的。 神经网络模型具有如下优点： 第2 章文本过滤相关理论及关键技术 ( 1 ) 该模型具有学习的功能； ( 2 ) 隐含层考虑了关键词之间的相关性。 信息获取的神经网络模型在实际中很少直接应用，这主要是由于需要太多的 神经元来表示信息库中的文档和关键词以及因而产生的大量计算，尤其在网络训 练阶段。 2 3 文本分词技术 无论是文本内容的表示还是用户模板的建立，都毫不例外地需要对中文的 。词”进行分析，这必然首先涉及到中文的分词问题，可见，文本分词是文本过 滤的基础性工作对于一句话，人们可以通过自己的知识来明白哪些是词，哪些 不是词，但是如何让计算机也能理解呢? 这个处理过程就是分词过程。众所周知， 英文是以词为单位的，词和词之间是靠空格隔开的，而中文是以句子为单位，句 子又是以字为单位的，句间用标点隔开，旬内字词则是连续排列的，之间没有任 何分隔。对于英文，计算机可以很简单地通过空格来区分出一个一个的单词，但 是对于中文来说，计算机并不知道某两个或者多个字合起来才能表示一个词。因 此，如果要对中文文本进行分类、检索等基于词的处理，需要首先对中文文本进 行词条切分处理( 简称分词) ，才能正确