（计算机软件与理论专业论文）基于自学习机制的信息过滤模型研究与实践.pdf

山东师范大学硬士学位论文 摘要 随着以因特网为主体的信息高速公路的迅速发展，信息技术已经渗透到我们社会生 活的方方面面。因特网上的信息呈指数级增长，信息增长带来了双面的效果。一方面， 可以从因特网上获取丰富的、最新的信息。另一方面，网络上信息浩繁，内容庞杂，而 且由于因特网信息的开放性、个人化，一些不法分子利用计算机网络复制、传播和查阅 一些色情的、种族主义的、暴力的、封建迷信或有明显意识形态倾向的信息，这些信息 对社会的危害是很大的。如何过滤掉与自己需求无关的信息，快速准确的获得所需信息 并免受非法信息侵扰，已经成为当前互联网发展研究的一个重点。 本文主要研究i n t 锄e t 上非法信息的过滤问题，内容涵盖了信息过滤的各个处理阶 段，围绕信息过滤模型的过滤精度和过滤速度两个主要指标，在如下几个方面进行了研 究和探讨： 1 对现有的信息过滤模型以及机器学习在模型中的应用进行了深入分析 本文首先阐明了信息过滤技术的发展过程和发展趋势，分析了信息过滤模型涉及的 关键技术及相关知识。在此基础上，分析了当前信息过滤模型存在的不足之处，如由于 i n t e r n e t 信息的复杂性和非法文档特征的不断改变，现有的信息模型自我学习、自我 调整以适应环境变化的能力不足等；然后，从模型优化的角度考察了模型中能够使用机 器学习进行改进的环节。 2 提出了基于统计的停用词表产生方法和基于遗传算法的特征提取优化算法 分词和特征提取是信息过滤模型中非常重要的两个方面，本文分析了停用词的特 点，提出了基于用户反馈的停用词表产生方法，进一步提高了分词的准确性；另外，本 文构造了两级特征库并基于遗传算法对中心层特征库进行了优化，提出了一种新的特征 提取优化算法。 3 提出一个新的基于自学习机制的信息过滤模型 信息过滤的核心技术主要包括分词、特征提取、文档表示和文本分类四个部分。本 文针对现有特征项权值统计能力不足，特征项数目和权值确定困难，特征项权值与分类 算法阈值臼联系不足等问题，研究了r 丑c c h i o 方法、决策树方法、基于实例的学习方法 以及神经网络方法等机器学习方法在信息过滤中的应用，提出了一种新的基于自学习机 制的信息过滤模型。 4 提出了分层、分级、分策略的信息过滤技术 信息过滤技术是网络安全技术的一个重要方向，本文将安全规则建立和信息过滤实 现模型的调整、优化相结合，面向应用提出了分层、分级、分策略的信息过滤技术，从 而提高了信息过滤模型的适应能力和过滤速度。 山东师范大学硕士学位论文 5 基于新的过滤模型设计开发了一种新型的信息过滤系统 本文应用基于自学习机制的信息过滤模型和分层、分级、分策略的信息过滤技术， 初步设计实现了一个新型的信息过滤系统。实验表明，此系统能够根据非法文档特点选 择合适的过滤策略，具有良好的可重用性、可扩展性、可适应性，从而大大提高了信息 过滤的过滤速度和过滤精度。 关键词：信息过滤模型，机器学习，神经网络，阈值，相关反馈 分类号：t p 3 0 9 山东师范大学硕士学位论文 a b s t r a c t w i 也t l = 【cr 印i dd e v e l o p m e n to fn i ib 嬲e do n 血eh e m e t ，i 砸d m l a t i o nt e c l i l o l o g yh a s b e e nw a l k e d i m oe v e r ya s p e c ti l l0 1 1 rl i f e t h e 幽n i l a t i o ni nn l ci n t e 】m e tr i si ne x p o n e n t i a l w a yt h ei n c r e a s eo fi n f o m l a t i o nh a st 、v oe f f e c t s ，o i l ei si tm a k e sp e o p l eg e t 北衄1 d a n t 趾d r c c e mi n f o r i n a t i o ne 船i l y 也eo t h 肛i ss o m ei n f 湎a t i o ns u c ha se r o t i c i s m 、v i 0 1 e n c e 、e v i l r c l i g i o nc t ci sh a 劬l t oo l l rh e a n a sar e s u h ，h o wt 0f i l e r 1 em f o n n a t i o ni r r e l e v a t 协o u r d e m a n da n dp i c ku p 廿l ei n f b 蛐撕o nw en e e di sg e n i n gm eh o t s p o “nt l l er e s e a r c ho ft h e i n t c m e t t h j sp 印e rm a i 】1 l ys t u d i e st 1 1 cl a w l e s si 蚰) m a t i o nf i l t c r i n 函t l ：l cc o i 她n t si n c l u d ee v e r y p h a s eo fi n f o n n a t i o nf i l t e r i n 舀t h ef o l l o 、椭n gq u e s 6 0 n sa r c 协er e s e a r c hk e y s t o n e 盯d u n dt h e t w oa s p e c t s ，p r e c i s i o a n dv c l o c i 何 l 、t h ea n a l y s i so fi n f b 彻a t i o nn l t e d l 培m o d e l i ne x i s t e n c ea 1 1 d 吐l ea p p l i c a d o no f m a c h i i l e l e a n i n gi n 也e s em o d e l s f i 做l y ，a n a l y z e st h ed e v e l o p m e 呲p r o c e s sa n dd e v d o p m e n t 扛e n do fi n = f 豳a t i o nm t e j 血g m o d e l ，s e c o n d ，a n a l y z e st l ec r i t i c a lt e c i l i l i q u ea n dt h er e l e v a mk n o w l e d g e ，t h i r d l y ，p o i m so m t h ed e f h u l t si n 1 ec u i t 眦i n f 0 h n 撕o nf i h e r i n gs y s t c m ，s u c ha st h ed e f i c i e n c yo fs e l f - l e a n i n g a n ds e l f _ a d j u s ti nc o n s t a n tv a r y i n ge r i m n m e m ，a tl a s t ，d i s c l l s s e sw 1 1 i c hp h a s ei nt h ep r o c e s s o fi n f b 加a t i o nf i l t e r i n gc a l lb eo p t i m i z e d b ym a c h i n el e a 血n 晷 2 、m s p a p e rp u t sf o n = v 盯dm em e m o do f c r e a t i n gm es t o p w o r d 忸b l eb 踮e do ns 枷s t i c s a n dt h eo p t i c a la i g o r i t 陆o ff b a n 聪sp i c k 一叩b a s e do ng e n e t i ca l g o r i t h l n s p l i 雠i n gw o r d sa i l df e a t u r ep i c l 【i n gu pa 托t w oi m p o r t a n ts i d e si ni i l f o r 玎隐d o nf i l t c r i n g m o d e l f i r s t ，m i sp a p e ra i l d i y z e st h ec h a r a c t e r i s t i co fs t o p w o r d ，s e c o n dp u t sf o m da m e m o do fg e n e r a t i n gs t o p w o r dt a b l eb a s e do nf c e d b a c k ，1 i sm e 血o di m p m v et h ep r c c i s i o n o fs p l m i n gw o r d s a d d i t i o i l a u y ，t oi m p r o v e 也ep r e c i s i o nt of b a t u r ep i c k i n gu p ，t 1 1 i sp 印e r c o n s t r u c t st w ol e v e lc h a r a c t e rd a t a b a s ea n do p t i m i z e s 也ec e n 缸a lc h 撇c t e rd a t a b a s eb y g e n e t i ca l g o r i t l l ma n dg i v e san e wf 宅a t u r ep i c k i n gu po p t i c a la l g o r i t l l m 3 、a n e w i 1 0 n n a t i o n f i h e r i n g m o d e lb a s e d o ns e l f 咖d y i n g m e c h a l l i s m i s p u t f o r w 砌 t h ec o r e 把c h n i q u eo fi n f b r i n a t i o nf i h e 血gi n c l u d e ss p l i n i n gw o r d s ，f e a t u r ep i c k 协gu p ， d o c 啪e md e n o t a t i o na n dd o c 啪e n tc l a s s i 母i n g t h e r ei sm a n yp m b l e m si nm f o m l a t i o n f i l t e r i n g ，s u c ha sc h a r a c t e ri t e m sw e i g h th a sl e s sc 印a b i l i t yo fs 乜t ，d i m c u l t yo fa s c e n a i l l i n g 血en u m b e ro fc h a r a c t e r “e m s ，l e s sr e l a t i o nb c 铆e e nc h i r a c t e ri t e m sw e i g h ta n dt 1 1 ev a l v e v a l u eo fc l a s s i 母i n ga l g o r i m m a sar e s l l l to ft h eu p p e rp r o b l e m s ，t 1 1 i sp a p e rs 砌i e sh o wt o u s er a c c 场om e t h o d 、d e c i s i o n m a k i n g 订e em e m o d 、l e 础gm e t h o db a s e do ne x a m p l e 、a n n m e 也o de t ct oo p t i m i z en l ei i 】f o m l a t i o nf i h e r i i 培m o d e l 山东师范大学颈士学位论文 4 、1 1 l i sp a p e rp u t sf b n a r dai a y e rc l a s s 嫡e d 、i e v e ic i a s s i 丘e d 、s 妇t e g yc l a s s 饭e d i n f o 衄a t i o nf i l t e r i n gt e c h 血q u e 1 1 1 i sp 印e ra l l a l y z e st t l ei d e m i 行e rr e c o 鲥虹0 n 妣l l n i q u e 、a c c e s sc o n 仃0 lt e c h n i q u ea n d a u d i tt e c h n i q u e t h e ni tp u 乜f b n v a r dal a y e rc l 嬲s 讯e d 、l e v e lc l a s s i f i e d 、s 廿a t e g yc l a s s i 矗e d i i l f b 衄a t i o n 矗i 蜘n gt e c h n i q u eb yc o m b i n i l l gt 1 1 eg e n e r a t i i l go f s a 尼r u i ea n dt h eo 删z a 正i o n o fm f 0 锄a t i o nf i l t e r i i 唱m o d e l t h en e wt e d m i q u ei l n p r o v e s 也e a d a p t e dc a p a b i l i t ya n d f i l t e 血gv e l o c i 够 5 、an e wi n f o m l a t i o n 丘l t e r i n gs y s t e mi sd e v e l o p e db a s e do nt h en e wi n f o 珊a t i o n 蛐e r i n gm o d e 】髓en e ws y s t e ma d o p t s 岫l a c l a s s i 矗e d 、l e v e lc l a s s 弧c d 、s 们t e g y c l a s s i f i e dm e l o d 1 th a sg o o dp r o p e r t yo fr e u s e ，e x t e n s i b i l i 毋a i l da d a p 诅b i l i t y a st h e e x p e r i m e n ts h o w s ，t h es y s t e mc a nc h o o s ea p p m p r i 砒ec a t e g o r ya l g o r i t h l ：nb yt h cc t e ro f l a 、v l e s sd o c u m e m ，s oi ti m p r o v et 1 1 ep r o b a b i l 时o f p r e c i s i o na 1 1 dc o m p l e t e n e s s k e y w o r d s ：i n f o r m a t i o nf i l t e 血gm o d e l ， m a c h i l l el e 锄i n 岛 a n n ， v a l v ev a l u e r e k v a n tf b e d b a c k c l a s s i f i c a t i o ：t p 3 0 9 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经 发表或撰写过的研究成果，也不包含为获得( 注：如没有其他需要 特别声明的，本栏可空) 或其他教育机构的学位或证书使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 迟艘 导师签字 学位论文版权使用授权书 够易 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权 数可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权 书) 学位论文作者签名：送萄遵 导师签字f 0 掘办 签字日期：2 0 0 年月 日签字日期：2 0 0年月日 山东师范大学硬士学位论文 第一章绪论 本章首先介绍了本文的研究背景，然后介绍了信息过滤的发展及研究现状，分析了 目前信息过滤中存在的问题，最后，根据目前研究以及现有的模型存在的不足，简要介 绍了本文的主要工作及组织结构。 1 1 研究背景 近年来，随着以因特网为主体的信息告诉公路不断普及和发展，信息技术已经渗透 到我们社会生活的每个角落，它正在以前所未有的速度和能力改变着我们的生活和工作 方式，我们已经进入了一个“信息爆炸”的时代。因特网上的信息呈指数级增长，信息 增长带来了双面的效应。一方面，用户可以从因特网上获取丰富的、最新的信息；另一 方面，由于因特网信息的开放性、个人化，一些不法分子利用计算机网络复制、传播和 查阅一些色情的、种族主义的、暴力的、封建迷信或有明显意识形态倾向的信息，这些 信息对社会的危害是很大的。如何过滤掉与自己需求无关的信息，快速准确的获得所需 信息并免受非法信息侵扰，已经成为当前互联网发展研究的一个重点。 要解决这一问题，目前主流的信息安全网络防火墙软件通常采用地址过滤的方法， 对一些非法网址和有害信息进行屏蔽，帮助用户处理这些信息。这类软件通常会设计一 个地址列表，当收到报文后判断其源地址是否在列表中，如果在就屏蔽掉，如果不在就 放行。这一技术在网络层对数据进行过滤，实现起来比较简单。但是，目前这种方法效 果不是很理想，首先，网络中提供非法信息的网站数量巨大，并且经常利用变换主机地 址、域名等方式来逃过防火墙的眼睛，这就不可避免的带来两方面的问题，首先，数据 库中非法地址列表不断增大而且不能及时动态更新；其次，大量的非法网站层出不穷， 如何判定并记录这些非法网站是一项十分艰巨的工作。究其原因，我们不难发现，出现 这些问题的关键是这种技术没有实现计算机对信息本身的内容的深入的理解。而要实现 这些目标，需要用到信息检索、机器学习、分布式处理、数据库、数据挖掘和自然语言 理解等多领域的理论和技术。在技术的发展过程中出现了希望达到更好目标的新技术 如：信息过滤( i n f 0 h n a t i o n f i l t e r i n g i f ) 、“推”式技术等。 信息过滤( i n f o n t l a 廿o nf i l t e r i n g ) ，也就是所谓的信息的选择性传播。就是根据用户 的需求，在动态的信息流中，搜索用户感兴趣的信息，屏蔽其它无用和不良的信息。与 信息检索不同，信息过滤关注用户的长线需求( 指在一段时间内，比较固定的信息需求) ， 山东师范大学硕士学位论文 是为非结构化及半结构化的数据设计的，主要用来处理文本信息，其晷标是帮助用户处 理大量的信息，对动态的信息流进行筛选，着重于排除用户不希望得到的信息。 1 2 研究内容及现状 1 2 1 信息过滤的发展历程 1 9 5 8 年，l u l l l l 提出了“商业智能机器”的设想，在这个概念框架中，图书馆工作 人员根据每个用户的不同需求，建立相应的查询模型，然后通过精确匹配的文本选择方 法，为每个用户产生一个符合其查询需求的新文本清单。同时记录用户所订阅的文本以 用来更新用户的查询模型。它的工作涉及到了信息过滤的每个方面，为文本过滤的发展 奠定了有力的基础。 19 6 9 年，人们对s d i ( s e l e c t i v ed i s s e m i l l a t i o no fi n f o r n l a t i o n ) 选择性信息发布系统 引起了广泛兴趣。当时大多数系统都遵循l u h n 模型，只有很少的系统能够自动更新用 户查询模型，其它大多数依然依靠职业的技术人员或者由用户自己维护。 1 9 8 2 年，d e n i l i n g 提出了“信息过滤”的概念。他描述了一个信息过滤的需求例子， 对于实时的电子邮件，利用过滤机制，识别出紧急的邮件和一般例行邮件。之后m a l o n e 等人发表了较有影响的论文，并且研制了系统“i n f o m l a t i o nl e n s ”，提出了三种信息选 择模式，即认知、经济、社会。所谓的认知模式即基于内容的过滤( c o n t e n t b a s e d f i l t e r i n g ) ；经济模式来自于d e n f l i n g 的“阈值接收”思想；其中社会模式是他最重要的 贡献，在社会过滤系统中，文本的表示是基于以前读者对文本的标注，通过交换信息， 自动识别具有共同兴趣的团体。 1 9 8 9 年，在这个时期信息过滤获得了大规模的政府赞助。由美国d a 砌) 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 i l c e ”，极大的推动了信息过滤的发展。在将自然语言处 理技术引入文本过滤研究方面进行了积极的探索，1 9 9 0 年，d a 础) a 建立了t i p s t e r 计划，目的在于利用统计技术进行消息预选，然后再应用复杂的自然语言处理技术。 1 9 9 2 年，n i s t ( 美国国家标准和技术研究所) 与d 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 文本检索会议) ，对于文本检索和文本过滤倾注了极大 的热情。砸c 在最近的几次会议中，着重于文本过滤的理论和技术研究以及和系统测 试评价方面，对文本过滤的形成和发展提供了强有力的支持。 山东师范大学硬士学位论文 1 2 2 信息过滤的研究内容及现状 当前信息过滤的研究以t r e c 会议为核心。n 冱c 会议有两个基本的任务。一个类 似于信息检索的a dh o c 任务，另外一个是类似于信息过滤的分流( r 0 u t i n g ) 任务。两 个任务的流程图如图1 1 所示。 图1 1t r e c 任务 左边是分流任务，分流任务包括两个过程：1 ) 参加测试的人将获得数个主题( t 0 p i c ) 以及已知的与主题相干的文档集。主题中包含了自然语言描述的用户信息需求文本。这 些主题被用于自动生成一组查询，即图1 1 中的q 1 。那些己知的、与主题相关的文档 集被用于训练q 1 ，训练的结果即q 2 。2 ) 使用q 2 ，在一个未告知结果的文档集上选择 与主题匹配的文档。图1 1 的右边是a dh o c 任务，与分流任务不同，它没有学习过程， 测试的参与者被直接给予一系列主题，程序在一个未知结果的文档集上工作。 信息过滤可分为文档内容过滤和合作过滤两个方面。按内容过滤是按照信息内容的 特性作出选择，需要研究文档的表示，涉及到自然语言理解领域，一般采用基于关键词 的方法，将进入信息流和用户模型( u s e rp m f i l e ) 或非法文档模板进行匹配计算，利用 一些基于规则的智能a g e m 来观察用户的使用风格、检测信息的内容特征、判定其是否 是用户感兴趣的，并向用户提出建议，这种方法比较适合于文本信息过滤。合作过滤又 称为社会过滤，在合作过滤中，一个文档的表示基于前面用户的评注，通过这些评注或 者用户对信息的访问，识别兴趣类似的团体，可根据其它合作用户对信息的访问判断特 定用户对特定信息是否感兴趣。合作过滤的好处在于不需要考察文章的内容，并且可以 山东师范大学硕士学位论文 兼顾用户的偏好与信息的质量因素。 国内有关信息过滤的研究目前以核心算法为主。算法研究集中在特征抽取、学习算 法和过滤算法。特征抽取的目的在于使用最少的特征表示出文档的含义，而概念学习的 目的在于使用最少的学习文档获取最好的用户模型( u s e rp r o 丘l e ) 。用户模型是一个数 据结构，通常包括一组主题，用以描述用户感兴趣的主题，在本文中主要描述非法文档的 特点。算法研究主要有两个趋势：第一个趋势是传统的关键词匹配方法逐渐地被较为复 杂地自然语言处理技术所取代，词语字典、语法知识、语义知识被用到信息过滤中。第 二个趋势是用户模型的手动输入逐渐的被自动的机器学习所取代，这种研究模式来源于 对信息过滤中用户行为特征和文档内容特征的观察：通常用户会在上网过程中表现出哪 些信息是自己想取得的，哪些是要摒弃的，但是自己却不能描述需要信息的特点。而机 器学习能够记录用户的行为特征和反馈信息，通过各种机器学习构建用户兴趣模型、调 整用户兴趣模型，很好的反映用户兴趣。 1 3 本文的内容及主要工作 围绕信息过滤模型的查准率和查全率两个主要技术指标，针对当前信息过滤模型中 存在的问题，本文对信息过滤各阶段的关键技术进行了深入研究；详细论述了信息过滤 模型的结构、关键技术和理论，深入分析了已有信息过滤模型的主要优缺点；然后，结 合机器学习理论，对模型中的几个关键技术进行了改进，提出了一个基于自学习机制的 信息过滤模型。最后基于该模型设计并实现了面向互联网的、分层、分级、分策略的信 息过滤系统并对其过滤效果进行了验证，验证结果表明，基于自学习机制的信息过滤模 型比传统的信息过滤模型效率更高。 本文涵盖了信息过滤的各个阶段，论文的基本组织如下： ( 1 ) 第二章探讨了当前常见的信息过滤模型及其关键技术：信息特征表示、特征 提取、文本表示模型和文本分类算法等，分析了当前过滤模型存在问题及其在模型中的 位置。 ( 2 ) 第三章分析了机器学习理论在信息过滤模型中的可能性、可行性；以此为基 础，提出了一种新的基于自学习机制的信息过滤模型；然后对模型中网络文档和用户兴 趣的表示，用户模型参数的优化，学习算法的选择，样本的组织，信息的表示和存储等 关键技术进行了深入研究。 ( 4 ) 第四章基于新的过滤模型设计实现了一个“面向互联网的信息过滤系统”，此 4 山东师范大学硕士学位论文 系统将信息过滤按层次、级别进行划分，不同的层次、级别采取不同的过滤策略；另外， 阐述了系统的设计思想、功能模块、核心算法和基本界面。最后，与现有的信息过滤系 统进行了比较并给出了比较结果。 ( 5 ) 第五章是全文的总结和下一步的工作。 山东师范大学硕士学位论文 第二章信息过滤模型及关键技术 本章首先给出了目前使用的典型的信息过滤模型，然后简要介绍了模型中的关键技 术：文本预处理、特征提取、文本表示模型和分类算法的研究内容和研究现状，最后分 析了现有模型存在的问题。 2 1 传统信息过滤模型 正如第一章中提到的，目前网络以前所未有的速度快速增长，信息共享应用日益 广泛和深入。但是网络是把“双刃剑”，它在给人们带来方便和快捷的同时，也带来 了各种各样的问题。不良网站的泛滥，非法信息的传播等令人们防不胜防，网络信息 安全问题越来越引起人们的关注。采用相应过滤技术过滤非法信息已经成为未来网络 技术发展的当务之急。 为了实现过滤信息的目的，每个信息过滤系统都有各自的实现方法，但它们有共 同的基本处理模块，可以抽象为一个共同的系统模型。下图就是一个目前使用的典型 的信息过滤模型。 6 图2 1 目前典型的信息过滤模型 从图2 1 中我们可以看出：信息过滤包括分词、特征提取、权值计算、文档向 量表示和分类比较几个过程，它关注用户的长期的信息需求，这种需求是相对稳定 的，所以需要保存和维护，以此更新和改善效果：信息过滤所面对的信息源是动态 的，而且与信息检索相比更需要用户的反馈，通过用户的反馈，增强表达的能力， 提高过滤效率。 山东师范大学硕士学位论文 2 2 文本预处理 在对文档进行特征提取前，需要先对文本进行预处理。而在网络文档中，词是最 小的、能独立活动的、有意义的语言成分，在信息过滤中，如能对文本进行分词，就 会大大提高信息过滤的准确性。对于英文来讲，词与词之间已经用空格分开，无须再 进行分词处理；而对于中文来讲，词与词之间没有明显的分隔符( 空格) ，需要进行 分词处理。近二十年来，汉语自动分词研究取得了很大成就，提出了许多分词算法， 其中有一定代表性的主要有：最大匹配法( 又可分为正向、逆向、双向三种) 、最优 路径法、最少分词法、特征词库法、邻接约束法、人工神经网络方法、无词典分词法 等。可以将这些算法分为三类：基于字符串匹配的分词方法、基于理解的分词方法和 基于统计的分词方法，而这其中，基于字符串匹配的分词方法最为常见。 基于字符串匹配的分词方法又叫做机械分词方法，它是按照一定的策略将待分析 的汉字串与一个充分大的机器词典中的词条进行匹配，若在词典中找到某个字符串， 则匹配成功。按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向匹配； 按照不同长度优先匹配的情况，可以分为最大匹配和最小匹配；按照是否与词性标注 过程相结合又可以分为单纯分词方法和分词与标注相结合的一体化方法。常用的几种 机械分词方法如下： 1 正向最大匹配 2 逆向最大匹配 3 最少切分( 使每一句中切出的词数最小) 分词之后要去除停用词，停用词一般是虚词、介词、代词等。 2 3 常用的文本表示模型 计算机并不具有人类的智能，人在阅读文章后根据自身的理解能力可以产生对文 章内容的模糊认识，而计算机并不能轻易地读懂文章，从根本上说，它只认识o 和1 ， 所以必须将文本转换为计算机可以识别的格式。根据贝叶斯假设，假定组成文本的字 或词在确定文本类别的作用上相互独立，这样就可以使用文本中出现的字或词的集合 来代替文本。不言而喻，这将丢失大量关于文章内容的信息，但是这种假设可以使文 本的表示和处理形式化，并且可以在文本分类中取得较好的效果。 信息过滤的主要工作是比较用户请求的原始信息空间和要过滤的非法信息空间 匹配程度，为此，一般采用模型化的方法表示信息空间。目前常用的的文本表示模型 有布尔逻辑模型，向量空间模型，潜在语义索引模型，概率模型四种，下面将分别予 以介绍。 山东师范大学硕士学位论文 2 3 1 布尔逻辑模型 布尔逻辑模型( b 0 0 l e a nl o g i c a lm o d e l ) 又称为完全匹配模型，是一种比较简单 的表示模型，它使用一系列从文档中抽取出来的具有二值逻辑的特征变量如：关键词 等描述文档的特征，特征变量之间用与、或、非三种关系连接起来。如若一个特征向 量在文中出现，则值为真，若否，则为假，特征变量之间的组合的结果通过布尔操作 符的运算公式得出。 这种传统的信息过滤技术也存在一些不足之处： ( 1 ) 对于一个给定的查询很难控制它的输出结果。有对会得出很多结果，可与用 户个性兴趣相一致的却很少。相反，有时却得不到任何信息。 ( 2 ) 在一次查询中，不能描述文档与用户个性兴趣的近似程度。 ( 3 ) 对于关键词来说，没有标示其对文档或查询的重要程度的重要因子或者权重。 所有关键词都处于相同重要的地位，这显然是不合适的。 2 3 2 向量空间模型 向量空间模型( v e c t o rs p a c e o d e l ) 是由s a l t o n 提出的关于文本表示的模型， 使用由词语构成的向量表示文档信息与净化信息，并在c o r n e l l 研究出基于向量空间 的s 凇r t 实验系统8 1 。该模型己被人们普遍认为是一种非常有效的信息净化模型， 它以特征项作为文本表示的基本单位，特征项可以由字、词或短语组成。所有的特征 项构成特征项集。一篇文献可以表示为一个向量，即可被定义成一系列字项的组合， 该向量的维数是特征项集的个数，并且根据统计结果，该向量的每个分量都被赋予一 个权值以表明它对于这篇文献的重要性。具体定义如下所示： 假设文档集d = ( d 。) ，= s ( 1 d i 表示集合d 中元素的个数) ，特征项集t 2 0 ， = m 。定义特征项f ，在文档z 中的权重为： 旷，l j s ，删 ( 2 1 ) 其中，砺为特征项，在文档z 中出现的频率，称为项频；奶是文档集d 中出现特征 项r ，的文档的数量，称为文档频率。一般来说，如果特征项r ，在文档d ，中的作用较大， 必然有较高的项频和相对较低的文档频率，故其权重w 口也较大。 山东师范太学硕士学位论文 在此基础上，建立文档的向量空间模型，以f 。，：，o 为坐标轴，把文档d ，表示 为m 维向量( 。，w f ：，) 。 对于两个m 维向量4 = ( w i 。，w 。，w 。) 和d ，= ( w 小m ：，) ，它们对应分量的乘 积之和称之为这两个向量的内积。记作： ( 如嘭) = w f _ 1 + ：z + 一5 善( 2 2 ) 一个向量自身内积再开方就得到该向量的模。记作： i 口i 在m 维欧氏空间中两个向量d 。= ( w i 。，2 ，) 和以= ( w m 一：，w 彤) 的夹角余 弦为： c o s 口= i = 1 ：堕生! ( 2 3 ) = ：一 lz jj d ，i 其中，日是向量d ，和d ，之间的夹角，1 i i ，1 j m 那么，文档d ，和d ，之间的相似程度s i m ( 哦，嘭) 可以表示为 c z 一，2 彻口。黼 ( 2 4 ) 向量d 和d 之间的夹角占的余弦值越大表明它们的相近度也就越大，反之则越小。 信息过滤的效率以查准率和查全率来衡量，这是要靠一段时间内得到的文档集来判 断的，如果特别要保证达到高准确率，即所查到的文档都是和用户的个性兴趣相符的， 那么查全率必然受到影响，必有一些相关的文档没有查出来；如果要达到较高的查全率， 即把所有相关的文档都查出来，在所查出的文档中必有一些文档是不相关的，则准确率 就会降低。阈值概念的提出，是对查全率和查准率进行了综合考虑，以求得较高的过滤 效率。对于一用户兴趣趋向和一相关闽值日，则对于任意返回的文档，它的相关度必为： s i m ( d ，p ) 口 ( 2 5 ) 其中，d 是文档的兴趣趋向向量表示，p 是返回文档的向量表示。但是阈值的设定一般 由用户手动设定，没有固定的标准，从而使判别的准确性没有理论依据，降低了过滤系 山东师范大学硕士学位论文 统的效率。 向量空间模型是目前使用最为广泛的文本表示模型，它具有自然语言界面，易于使 用。该文本表示模型的缺点主要有三点：一是没有考虑关键词之间的相互关系和关键词 的语义理解：二是向量空问模型在计算特征项权值时基于这样一种假设：对区别文档最 有意义的词语应该是那些在文档中出现频率足够高的，但在整个文档集合的其它文档中 出现的频率足够少的词语。而这种假设并没有充分的理论支持。三是使用向量空间模型 进行过滤时，阂值口需要人为指定，没有考虑特征项出现频率与闽值曰之间的关系。 2 3 3 潜在语义索引模型 潜在语义索引模型( l a t c ms e m a n t i ci n d e x i n g ，l s i ) 已被广泛地应用到信息过滤领域 中，它是利用字项与文档对象之间的内在关系形成信息的语义结构。这种语义结构反映 了数据间最主要的联系模式，忽略了个体文档对词的不同的使用风格。这是挖掘文档的 潜在的语义内容，而不仅仅是使用关键字的匹配，是对字项文档矩阵使用奇异值分解 ( s i n g u l 廿v 酊u ed e c o m p o s i t i o n ，s v d ) 方法来实现的，把小的奇异值去掉。文献1 中 使用l s l 技术对n e 协e w s 上的文档进行信息过滤，并就使用l s i 技术与使用关键字匹配 进行信息过滤的性能进行了比较。对于奇异值分解来实现信息过滤的原理是：给定一个 字项文档矩阵x ，x 有，( 表示文档集中关键字项的个数) 行c ( 文档集中文档的数量) 列。对z 进行奇异值分解得： x = 瓦晶d 0 1 ( 2 6 ) 式中瓦是，川矩阵，称其标准正交列为左奇异向量；岛是肌m 的对角阵，& 中的正 奇异值是以递减的顺序排列的；d 0 是m c 矩阵，d 0 的标准正交列可称为右奇异向量； m 是矩阵j 的秩。对矩阵矗，氐和d 0 的处理是x 矩阵被重构。l s i 技术的关键在于只 取矩阵鼠的七个奇异值，其它值置零。值七是一个设置参数，一般情况下经常设置在 l o o 2 0 0 之间。原始矩阵x 可近似表示为x = 疆矿，其中丁是具有标准正交列的r 七 矩阵，s 是一个的对角阵，d 也是具有标准正交列的c 矩阵。无论是在l s 【 还是在关键字向量匹配方法中，文档都是以多维向量来表示的。关键字向量中的值表 示字在文档中出现的频率，l s i 向量中的值是通过s v d 分解得到的缩减了的值，内容 相近文档的向量也是相近的，这就是信息过滤中的本质所在。 1 0 山东师范大学硕士学位论文 2 3 4 概率模型 r o b e r t s o n 提出了基于检索词和文档相关关系的概率检索模型，概率方法基于两 个主要的参数，文档的相关概率p r ( r e l ) 和不相关概率p r ( n o n r e l ) ，以及两个费用系数q 和口2 。q 表示由于检索不相关的文档造成的损失，呸表示错过检索相关文档所造成的 损失。因为检索不相关的文档产生的损失为q + 【1 - p r ( n o i 雠1 ) 】 ，错过相关文档所造成 的损失为口：+ 【1 p r ( r e l ) 】 ，因此应该检索的文档应符合下式： q + p r ( ，e ，) q + p “胛d 疗，e ，) ( 2 7 ) 检索相关函数可定义为： 。：! ! ( 堡垒一旦 6 1 一p “，v ，)口2 ( 2 8 ) 检索结果为相关函数g 值大于o 的文档记录。g 值无法计算出来，文档的相关特性与 其中包含的检索词相关。使用贝叶斯定理，并假设q = 口2 ，可得到： c 州。g 器仙g 嵩泣。， 其中p r ( r e l ) 和p r ( n o n r e l ) 为相关及不相关的先验概率，用p “薯i 憎d 以及p r ( 葺l 聊棚d 来 表示。对于信息过滤来讲，由于具有学习过程，p “薯| ，e z ) 和p r ( h d 丹r 8 z ) 可以通过学 习获得。 2 3 5 小结 一般情况下，b o o l e a n 模型被认为是功能最弱的方式，概率模型是否比v s m 好还 存在争议，但是现在向量空间模型应用的比概率模型更广泛；而且，在向量基础上实 现机器学习、神经网络的各个算法比较方便，能够更好的处理复杂的信息。 山东师范大学硕士学位论文 2 4 特征提取 2 4 1 空间降维 构成文本的词汇数量是相当大的，因此，表示文本的向量空间的维数也相当大， 可以达到几万维，对于许多学习算法，特征过多会导致计算不可行。例如，很少有神 经网络可以处理如此多的输入节点，如贝叶斯网络在未给出特征独立的假设情况下， 计算是指数级的。因此需要进行维数压缩的工作，这样做的目的主要有两个，第一， 为了提高程序的效率，提高运行速度。第二，所有几万个词汇对文本分类的意义是不 同的，一些通用的，各个类别都普遍存在的词汇对分类的贡献小，在某特定类中出现 比重大而在其他类中出现比重小的词、汇对文本分类的贡献大。为了提高分类精度，对 于每一类，应除去那些表现力不强的词汇，筛选出针对该类的特征项集合。 2 4 2 特征提取 特征提取就是将文本离散成特征的集合，特征提取的好坏直接关系到整个过滤结 果的优劣。它的基本思想是构造一个评价函数，对特征集中的每个特征进行独立评估， 每个特征都将获得一个评估分( 称之为权值) ，然后对所有的特征按照其权值大小排 序，选取预定数目的最佳特征作为结果的特征子集。这样做的目的是排除那些被认为 是无关或关联性不大的特征。存在多种筛选特征项的算法，目前特征提取的方法主要 有以下五种：文档频率( d f ，d o c u m e n tf r e q u e n c y ) 、信息收益( i g ，i n f o r m a t i o ng a i n ) 、 互信息( m i ，m u t u a li n f o r m a t i o n ) 、开方拟合检验( c h i ，z 2 一t e s t ) 、术语强度 ( t s ，t e r ms t r e n g t h ) ，提取效率的高低为c h i ，m i d f t s i g 。 1 文档频率阈值( d f ) 特征空间的一个术语的文档频率是指出现了该术语的文档的个数。通过为训练语 料库中的每个单独的术语计算它的文档频率，可以从特征空间中除去那些文档频率低 于某个预定义阈值的术语。这一做法的基本假设是：低频词要么对分类预测不起作用， 要么对整体性能没有大的影响，通过除去低频词可以减少特征空间的维数。 文档频率闽值是最简单的减少词汇量的技术，它的计算复杂度与训练文档的数量 是线性关系，所以很容易被扩展用于处理大的语料库。然而，文档频率阙值通常被认 为是一种提高效率的方式，而不是一个好的用于选择特征的准则。 2 信息收益( i g ) 信息收益是机器学习领域中常用的被用作评判术语好坏的准则，它通过一个术语 山东师范大学硕士学位论文 是否出现，度量在分类预测中获得的信息量。令 q ) ( 。) ”表示类别集合，而术语f 的信 息收益定义如下： g ( f ) = 一p ( q ) l o g p ( c i ) 十尸o ) p ( c l l r ) l o g p ( q i f ) + p 尸( q | 7 _ ) l o g 尸( c ；l _ ) j = li _ 1= 1 ( 2 1 0 ) 由于文本分类问题通常处