（计算机软件与理论专业论文）基于用户兴趣度的网络信息过滤模型研究.pdf

山东师范大学硕士学位论文 摘要 随着信息技术的飞速发展，互联网技术已经成为人们日常生活中的一部分。人们用越 来越多的时间通过互联网进行信息查询、学习以及休息娱乐。虽然互联网上蕴涵了丰富的、 最新的信息，但是互联网的信息量过大，各种信息泛滥，人们在进行信息的查询时往往得 到的结果与自己的兴趣不一致。面对海量信息，如何帮助用户选择自己感兴趣的信息成为 研究与应用关注的重点。文本过滤旨在帮助用户获取自己感兴趣的文本，实现信息服务的 个性化，因此它具有广泛的应用背景和较高的实用价值。 文本过滤从形式上可以分为三种，即：内容过滤、协作过滤和价值过滤。内容过滤主 要采用自然语言处理、人工智能、概率统计等技术对文本进行内容分析，然后与用户模型 进行相似度计算，主动将相似度高的文本发送给该用户模型的注册用户，但是内容过滤难 以区分同一主题过滤结果的内容质量好坏，不能为用户发现新的感兴趣的信息另外一种 方法，协作过滤主要利用兴趣相似用户的评价进行预测和推荐。目前它已经被成功的应用 到个性化推荐系统中，但随着系统规模的扩大，它的性能会逐渐降低，暴露出一些问题， 比如矩阵稀疏性、扩展性以及早期级别等问题。而价值过滤基于不选择某个主题的代价大 于选择某个主题的代价，虽然前景很好，但是目前应用还不是很广泛。 本文围绕信息过滤模型的查准率技术指标，对于网络信息过滤的研究背景和研究现状 做了分杯指出现在基于兴趣度的信息过滤研究的重点在于用户兴趣模型的形成、更新以 及内容过滤、协作过滤和价值过滤的结合。 在前人工作的基础上，本文的主要研究工作及创新如下： ( 1 ) 对网络信息过滤的研究背景和现状做了分析，通过对国内外研究现状的分析，指 出用户模型的建立、更新，以及内容过滤、协作过滤和价值过滤的结合是当前研究的重点 ( 2 ) 对网络信息过滤关键技术进行研究，如：网络信息过滤系统基本组成、中文分词、 特征提取以及分类算法等。 ( 3 ) 针对基于用户兴趣的信息过滤，提出了一种新型的用户兴趣模型建立、更新方法， 使用户模型可以更好的兼顾用户的长期兴趣和短期兴趣。 ( 4 ) 提出将内容过滤与用户行为结合来形成用户兴趣度的计算方法，使其能及时的捕 捉到用户兴趣的变化，比较准确的反映用户对所搜索信息的感兴趣程度。 ( 5 ) 分析了内容过滤、协作过滤以及价值过滤结合的必要性，提出三者结合的过滤方 法及模型，此模型可以扬长避短，解决单纯使用任何种方法的缺点，并且可以提高过滤 的准确度。 关键词：内容过滤，协作过滤，价值过滤，用户兴趣 中图分类号：t p 3 0 9 山东师范大学硕e 学位论文 a b s t r a c t w i t ht h ed e v e l o p m e n to fi n t e m e ta n dw e bt e c h n o l o g y , i n t e m e th a sb e e nag i g a n t i cs p a c eo f i n f o r m a t i o ne x c h a n g e f a c i n gt h eg i g a n t i ci n f o r m a t i o n , p e o p l eo f t e nl o s et h e i rd i 删w h e n t h e yl o o kf o rt h e i rr e q u i s i t ei n f o r m a t i o n h o wq u i c k l ys e a r c h i n gf o rt h e i rr e q u i s i t ei n f o r m a t i o n f t o mg i g a n t i ci n f o r m a t i o n1 e s o r r c eh a sb e e nad i f f i c u l tp r o b l e mo f p e r p l e x i n gt h eu s e r g i v e nt h e h i g hm t eo ft h ev o l u m eo fd a t aa v a i l a b l eo nt h ei n t e m e t , f i n d i n gu s e f u li n f o r m a t i o ni ns u c ha l a r g ea m o u n to fd a t ab e c o m e sam o d i f f i c u l tp r o c e s se v e r yd a y t h e r e f o r eh o w t op r o v i d et h e p e r s o n a li n f o r m a t i o nt op e o p l ei sb e c o m i n gt h ei m p o r t a n tp r o b l e mt h a tr e s e a r c h e r sc a r ef o r t e x t f i l t e r i n gi so f g r e a tv a l u ea n d u s e dw i d c l yw i t h t h ei n c r e a s i n gt e x ti n f o r m a t i o nb e c a u s ei tc a n h i i p u s 豇 sg e ti n f o r m a t i o nw h i c ht h e ya r ei n t e r e s t e di na n dr e a l i z ep e r s o n a l i z e di n f o r m a t i o ns e r v i c e t h e r ea r ct h r e ek i n d so ft e x tf i l t e r i n g ：c o n _ i c n t - b a s o df i l t e r i n g , c o l l a b o r a t i v ef i l t e r i n ga n d v a l u ef i l t e r i n g c o n t e n t - b a s e df i l t e r i n gm a i n l ya d o p t ss o m e t e c h n o l o g i e ss u c ha sn a t u r a ll a n g u a g e p r o c e s s i n g , a r t i f i c i a li n t e l l i g e n c ea n dp r o b a b i l i t ys t a t i s t i ct oa n a l y z et e x tc o n t e n t , t h e nc a l c u l a t e d e g r e eo fs i m i l a r i t yb c l ：w e e nc o n t e n tv e c t o ra n du s e rp r o f i l e sv e g t o ra n ds e l e c tl l i g hc o r r e l a t i v e t e x tt o r e g i s t e r e du s e r s c o l l a b o r a t i v ef i l t e r i n gm a i n l ym a k e su s eo ft l s e r s o p i n i o n st h a th a v e s i m i l a ri n t e r e s tt op r e d i c ta n dr e c o m m e n d n o wi th a sb e e nu s e di np e r s o n a l i z e dr e c o m m e n d a t i o n s y s t e m b u tw i t ht h es y s t e ms c a l ee n l a r g i n g i t se f f i c i e n c yg m d u a l l yd e c l i n e sa n ds o m ep r o b l e m s s u c h 瑟s p a r s em a u i x , s c a l a b i l i t ya n de a r l yn i t e rw i l la p p e a r v a l u ef i l t e r i n gm a yb ef o r m a l i z e da s ad e c i s i o nr u l e ：s e l e c tam e s s a g ei f a n do n l yi f t h ec o s to f s e l e c t i n gam e s s a g ef o re x a m i n a t i o ni s l o w e rt h a nt h ec o s to f 蛹e c t i n ga m e s s a g e - t h a ti s ，c h o o s i n gn o tt o m i n eam e s s a g e i nt h i s p a p e r , t h er e s e a r c hb a c k g r o u n da n dc u r r e n ts i t u a t i o no ft h en e t w o r ki n f o r m a t i o n f i l t e r i n gh a sb e e na n a l y z e d , p o i mo u tt h ek e y so fi n f o r m a t i o nf i l t e r i n gb a s e do nt h eu s e f i n t e r e s t , t h a ti su s e ri n t e r e s tp r o f i l e , t h eu p g r a d eo fu s e ri n t e r e s t ，a n dt h eu n i o no fc o 】吐翻1 t - t 暇s e d f i l t e r i n g ，c o l l a b o r a t i v ef i l 衄i n ga n dv a l u ef i l t e r i n g b a s e do np r e v i o u sr e s e a r c h , t h em a j o rr e s e a r c hw o r k sa n di n i t i a t i v ep o i n t si nt h i sa r t i c l e 鼬： f i r s t , a n a l y s e st h er e s e a r c hb a c k g r o u n da n dc u r r e n ts i t u a t i o no ft h en e t w o r ki n f o r m a t i o n f i l t e r i n g ，p o i n t so u tt h ek e yo fr e s e a r c ht h a ti st h ee s t a b l i s h m e n t , u p g r a d ea n dt h eu n i o no f c o n t e n t - b a s e df i l t e r i n g ，c o l l a b o r a t i v ef i l t e r i n ga n dv a l u e s e c o n d ，t h ek e yt e c h n i q u e si nc o n t e n t - b a s e di n f o r m a t i o nf i l t e r i n ga r p a r t i c u l a r l yd i s c u s s e d , t h a ti sh o wt os e g m e n tc h i n e s ew o r d s ，h o wt oe x u a c ts u i t a b l ef e a t u r e sf r o md o c u m e n t s ，a n dh o w 幻c l a s s i f y t h i r d , i nv i e wo fi n f o r m a t i o nf i l t e r i n gb a s e do nt h eu 晰i n t e r e s t , p r o p o s e so n ek i n do fn e w u s 盯i n t e r e s tp r o f i l e 。t h eu p g r a d em e t h o d , w h i c he n a b l e st h eu s e fp r o f i l et ob ep r o p e rt ob o t h u s e r sl o n g - t e r mi n t e r e s ta n dt h e s h o r t - t e r mi n t e r e s t i 山衷师范大学颤十学位论文 f o u r t h ，t h ep a p e rs u g g e s t st h em e t h o do f i n t e r e s td e g r e eo f u s e r t h em e t h o di sb a s e do nu s e r v i e w e dc o n t e n ta n dc o m b i n i n gw i 山a n a l y s i so fu s e r sb e h a v i o r i tc a na d a p tt h ec h a n g e so fu s e r i n t e r e s t sq u i c k l y , a n dp r e s e n tt h eu s e ri n t e r e s td e g r e et ot h ei n f o r m a t i o n f i n a l l y , t h r o u g ha n a l y z i n gt h eu n i o nn e c e s s i t yo fc o n t e l l t b a s e d , c o l l a b o r a t i v ef i l t e r i n ga n d v a l u ef i l t e r i n g ，p r o p o s e sa l li n f o r m a t i o ns y s t e mb a s e do nt h r e ek i n d so fi n f o r m a t i o nm e t h o d s t h i sm o d e lm a ye n h a n c es t r o n gp o i n t sa n da v o i dw e a k n e s s e s , a n dm a ya l h a n c ct h ea c c u r a c yo f t h ei n f o r m a t i o n k e y w o r d s ：c o n t e n t b a s e df i l t e r i n g ，c o l l a b o r a t i v ef i l t e r i n g , v a l u ef i l t e r i n g , u s e ri n t e r e s t c l a s s i f i c a f i o n ：t p 3 0 9 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写 过的研究成果，也不包含为获得( 注：如没有其他需要特别声明的，本栏 可空) 或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 王籽 翮棒彬 学位论文版权使用授权书 本学位论文作者完全了解! | 兰撞有关保留、使用学位论文的规定，有权保留并向国家有 关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权! 墩可以将学 位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名王浑辛 导师签字 “移畛 签字同期：2 0 0 7 年午月审日签字日期：2 0 0 7 年牛月习日 山东师范大学硕士学位论文 第一章绪论 1 1 信息过滤产生的背景 随着信息科学的进步和因特网的发展，网络信息资源越来越丰富，网上信息呈爆炸式 增长。信息技术已经渗透到我们社会生活的各个角落，正以前所未有的速度和能力改变着 我们的生活和工作方式，我们真正处于一个“信息爆炸”的时代这一方面给用户发现信 息、利用信息带来了方便，另一方面，无序、极其庞大的信息世界和成千上万的超级链接， 又常常使用户在查找其所需信息时感到力不从心。 目前解决这个矛盾的方法大致可分为两种：信息检索和信息过滤。所谓信息检索，是 指对有序化知识信息的检索查找，本质上是一种“人找信息”的服务形态，每次检索时要 求用户一次性提交一个或几个查询关键词由于无法全面准确地描述用户真正的信息需求， 传统信息检索技术已经远远不能满足需要，网络信息过滤技术应运而生。 网络信息过滤，就是根据用户的信息需求，利用一定的工具从大规模的动态信息流中 自动筛选出满足用户需求的信息，同时屏蔽掉无用的信息的过程广义的信息过滤包括对 文本、音频、图像、视频等多种信息存在形式的过滤处理，狭义的信息过滤是特指对文本 信息的过滤处理。由于目前在因特网上主要的信息载体为文本形式，文本信息过滤技术首 先成为研究焦点，本文主要探讨文本信息的过滤技术。 网络信息过滤具有重要的现实意义和巨大的应用价值信息过滤可以克服重复查询， 网络信息是时常变化的，用户关心这种变化，在搜索引擎中用户只能不断地在网络上查询 同样的内容，以获得变化的信息，这花费了用户大量的时间：信息过滤是实现信息的个性 化主动服务的前提。个性化服务的实质是针对性，即针对不同的用户采取不同的服务策略， 提供不同的服务内容。主动服务的实质是主动性，即系统自动按照用户的信息需求提供相 应的服务。个性化主动服务将使用户通过尽可能小的投入获得尽可能好的服务回报【l 】。信 息过滤能实现有害信息的过滤，比如一些反动言论、谣言和色情内容；能实现垃圾信息过 滤，比如常见的垃圾邮件；能实现有用信息推荐，比如可以根据不同用户之间需求的相关 性来推荐信息。 1 2 国内外研究现状 1 9 8 2 年，d e n n i n g 提出信息过滤( i n f o r m a t i o nf i l t e r i n g ) 的概念【2 】他描述了一个信息 过滤的实例，在电子邮件系统中，利用过滤机制区分紧急的邮件和一般的例行邮件，同时 根据用户需要限制例行信息的显示方式为了解决这个问题，d e n n i n g 构造了一种“内容过 滤器”，其中采用的主要技术包括有层次组织的邮箱、独立的私人邮箱、特殊的传输机制、 阈值接受、资格认证等。 在此后的十年间，关于信息过滤的应用研究逐渐开展起来，研究领域也从最初的电子 邮件延伸到其他相关领域，出现了许多研究成果，其中最有影响的是m a l o n e 和他的同事在 l 山东师范足学硕士学位论文 1 9 8 7 年发表的论文p 】。他们提出了三种信息选择模式，即认知模式经济模式和社会模式， 并研制了i n f o r m a t i o n i 彻s 系统。 在这一期间，信息过滤研究得到了大规模的政府资助。1 9 8 9 年，美国国防高级研究项 目署( d e f c n s ea d v a n c e dr e s e a r c hp r o j e c ta g e n c y ，d a r p a ) 资助了第一届。m e s s a g e u n d e r s t a n d i n gc o n f e r e n c e ” 4 1 ，极大地推动了信息过滤的发展。 1 9 9 2 年，n i s t ( 美国国家标准和技术研究所) 与d a r p a 联合赞助了每年一次的文本 检索会议( t e x tr e t r i e v a l ，t r e c ) ，对于文本检索和文本过滤倾注了极大的热忱【5 】。t r e c 旨芷通过提供规范的大规模语料( g b 级) 和对文本检索系统性能进行客观、公正的评测， 来促进技术的交流、发展和产业化；促进政府部门、学术界、工业界之间的交流和合作， 加速技术的产业化；发展对文本检索系统的评测技术。这对文本过滤技术的形成和发展提 供了强有力的支持。 随着因特网的迅速发展，需求的不断增加，在文本过滤以及相关技术方面，取得了长 足的进展，成为信息产业新的增长点，许多文本过滤系统相继开发完成。如s t a n f o r d 大学 开发的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 ) 系统嘲、s t e v e n s 研制的i n f o s c o p e 系统【，1 、基 于协作过滤的系统t a p e s t r y t 8 9 】和g r o u p l e n s 1 0 一1 1 。也有一些过滤方案试图将内容过滤和协 作过滤相结合，如f a b 系统【1 2 】就是结合了内容过滤和协作过滤两种模式的典型系统，该系 统用于推荐网页。 m a r y l a n d 大学的l a nm s o b o r o f f 和c h a r l e sk n i c h o l a s 介绍了一种结合内容和协作过滤 的技术。该技术使用潜在语义索引l s i ( 1 a t e n ts e m a n t i ci n d e x i n g ) 方法来生成用户兴趣模 型，这些用户模型是由与用户信息需求相关的文档中的词构成的向量。该技术中过滤出的 文档根据与l s i 中的用户模型的相似性还进了顺序排列【1 3 】。 p r o b u i l d e r 系统也结合使用了内容过滤和协作过滤技术，也用于推荐网页。用户被提供 了一个单独的交互界面，有两列被推荐的网址。一列是由协作过滤生成的推荐网址，另一 列是有内容过滤生成。但是两列是相互独立的，没有结合在一起形成一列结合的推荐网址， 也未给出每种过滤预测的相对重要性，以便用户从两列网址中选择最好的推荐网址【1 4 1 。另 外，美国n e c 公司附属的n e c i 研究所子1 9 9 7 年开发研制了r e s e a r e h l n d e x 科技文献电子 图书馆系统【1 5 】。该系统的整体设计思想主要是借鉴了s c i ( s c i e n t i f i cc i t a t i o ni n d e x i n g ) 对 科技文献的组织和评价方法，特别是通过对文献引文的详尽分析，实现了科技文献全自动 的引文索引。 在国内，东北大学的姚天顺教授和林鸿飞博士等人进行了中文文本过滤技术的研究( 使 用新闻资料作为其语言语料库) ，在他们提出的中文文本过滤模型中，用户需求采用基于实 例文本的主题词表示，文本表示采用向量空间模型，需求与文本的匹配技术采用向量夹角 余弦作为相似系数，为了更好的排列满足阈值要求的文本，在对文本进行索引的时候，他 们引进文本结构分析技术，从文本中获取逻辑层次信息，以期提高文本片断检索时文档与 查询的匹配效率切。另外，他们还进行了基于混合模式的文本过滤模型【1 引，其基本思想 是将基于内容过滤方法和协作过滤方法结合起来，给出了用户评注的权威性和一致性度量， 以便更好的运用用户的评注信息。在此基础上，结合用户的个人兴趣，给出了文本特征抽 2 山东师范大学硕士学位论文 取机制、文本推荐机制、文本与信息需求模型的匹配机制。 复旦大学吴立德教授和黄萱菁博士等人参加了t r e c 9 会议德f i l t e r i n g 子项目，利用 t r e c 提供的规范语料库，他们从主题描述和正例文档中抽取特征向量作为用户的初始需 求模型，在与训练集的交互( 即计算相似度) 中获取关于每个主题的初始阈值。之后再与 测试集进行交互，判断测试集中的文档是否大于某主题的阙值条件，如果满足条件，则将 其归入正例文档集，否则归入反例文档集，然后从正、反例文档集中抽取特征向量，以更 新初始需求模型，其中包含对阈值的动态调整【1 9 1 。 清华大学自动化系的李衍达教授和卢增祥博士等人提出潜在语义标引技术进行双语过 滤( 使用新闻资料作为其实验语料库) 和最大间距法进行信息过滤的匹配算法，目的是为 他们的b o o k m a r k 服务系统提供技术支持 2 0 , 2 1 1 。他们也进行了协作过滤的初步研究，探讨协 作过滤的发展方向吲。 中国科学院软件研究所的阮彤等博士进行了信息过滤研究，提出了基于贝叶斯网络的 信息过滤模型b m i f ，描述了信息过滤的基本结构，提供了6 种节点用于描述影响信息过滤 的事件之间的关系，在此基础上，提供了b m i f 的各种使用方法，将词法知识用b m i f 表 示，以及将自动学习与手动交互结合，将协作过滤与内容过滤结合等嘲 1 3 论文的组织结构 本文共分五章，大致结构如下： 第一章介绍论文的研究背景和研究意义，阐述信息过滤相关信息，并给出了信息过滤 的定义和任务描述。 第二章研究网络信息过滤的基本问题，介绍了信息过滤的关键技术，如中文分词、特 征提取以及分类算法等。 第三章描述了用户兴趣的含义，以及用户兴趣获取的方法，常用兴趣模型的建立方法， 针对基于用户兴趣的信息过滤，提出了一种新型的用户兴趣模型建立、更新方法，使用户 模型可以更好的兼顾用户的长期兴趣和短期兴趣。提出将内容过滤与用户行为结合来形成 用户兴趣度的计算方法，使其能及时的捕捉到用户兴趣的变化，比较准确的反映用户对所 搜索信息的感兴趣程度。 第四章介绍了传统的信息过滤方法，分析了内容过滤、协作过滤、价值过滤结合的必 要性，提出了三种过滤结合的方法，设计了三种过滤方法结合的过滤系统模型，对于其中 的内容过滤与协作过滤结合的部分进行了实验，并与单纯的内容过滤与协作过滤方法做了 比较。 第五章对全文进行总结，并提出未来的研究工作方向。 3 山东帅范夫学 碘f 学位论文 第二章网络信息过滤系统关键技术 2 1 信息过滤系统基本组成 一个最简单的过滤系统包括四个基本组成部分：信息源、过滤部分、用户、用户需求 模板信息源向过滤器提供需过滤信息，信息过滤器处于信源与用户之间，通过用户需求 模板获取用户的兴趣信息，并据此检验信源中的信息，将其中与用户兴趣相关的信息递送 给用户。反过来，用户也可以向信息过滤器发送反馈信息以说明哪些信息的确符合他们的 信息需求，通过这种交互行为使得过滤器不断进行学习，调整自身的过滤操作，进而能在 以后提供更多更好满足用户兴趣的信息。 一厂 (用户) _ 一反馈学习部分l 丫乡 图2 1 信息过滤基本组成图 2 2 信息过滤系统的一般模型 网络信息过滤系统主要处理的是半结构化的和非结构化的数据，为用户在工作、学习 和生活中产生的信息需求提供服务。通常，这种信息需求在较长的一段时间里是相对稳定 的，变化较慢的。要以计算机能够理解的形式揭示用户的信息需求，就是用户需求模板( u s e r p r o f i l e s ) ，也叫做用户个性化文件、过滤模板。它是对用户兴趣的一种描述，表明了用户对 什么样的内容感兴趣，对什么样的内容不感兴趣。也就是说，对用户需求模板的描述可以 是正向的，也可以是逆向的，既可以揭示用户希望得到的信息，也可以描述用户希望剔除 的信息。一般情况下，系统不对动态的网络信息流作预处理，只是当信息流经过时才运用 特定的技术将信息揭示出来过滤匹配算法与用户需求模板的描述方法、信息的揭示方法 是相互联系的，常用的模型主要有布尔模型、向量空间模型、概率模型、潜在语义索引模 型等，主要任务是将信息与用户需求模板进行比较，根据比较结果滤掉不相关信息，选出 用户需要的信息，并以合适的形式递送给用户，比如将过滤结果按相关性大小排序输出。 为了提高过滤过程的效率和精度，系统还根据过滤的结果提供了相应的反馈机制作用于用 户和用户需求模板，使用户的信息需求越来越明确，越来越具体。 4 山东师范大学颂十学位论文 图2 - 2 信息过滤系统的一般模型图 2 3 常用中文分词方法 中文分词技术属于自然语言处理技术范畴，是语义理解过程中最初的一个环节，它将 组成语句的核心词提炼出来供语义分析模块使用。在分词的过程中，如何能够恰当地提供 足够的词来供分析程序处理，并且过滤掉冗余的信息，这是后期语义分析的质量和速度的 重要前提，本文系统中需要处理的对象主要是网页中的中文文本信息，无论是文本内容的 表示还是用户模板的建立，都毫无例外地需要对中文的“词”进行分析，这必然首先涉及 到中文的分词问题 现有的分词算法可分为三大类：基于字典、词库匹配的分词方法、基于词的频度统计 的分词方法和基于知识理解的分词方法。 2 3 1 基于字典、词库匹配的分词方法 这种方法按照一定策略将待分析的汉字串与一个“充分大的”机器词典中的词条进行 匹配，若在词典中找到某个字符串，则匹配成功( 识别出一个词) 。根据扫描方向的不同分为 正向匹配和逆向匹配；根据不同长度优先匹配的情况，分为最大( 最长) 匹配和最小( 最短) 匹 配；根据与词性标注过程是否相结合，又可以分为单纯分词方法和分词与标注相结合的一 体化方法。常用的方法如下： ( 1 ) 正向最大匹配法( v i a x i l n u l nm a t c h i n gm e t h o d ) 通常简称为m m 法其基本思想为：设d 为词典，m a x 表示d 中的最大词长，s t r 为 待切分的字串。m m 法是每次从s t r 中取长度为m a x 的子串与d 中的词进行匹配。若成功， 则该子串为词，指针后移m a x 个汉字后继续匹配，否则子串逐次减一进行匹配。 ( 2 ) 逆向最大匹配法( r e v e r s em a x i m u mm a t c h i n gm e t h o d ) 通常简称为r m m 法r m m 法的基本原理与m m 法相同，不同的是分词的扫描方向， 它是从右至左取子串进行匹配。统计结果表明，单纯使用正向最大匹配的错误率为1 1 6 9 ， 单纯使用逆向最大匹配的错误率为1 2 4 5 , 显然r m m 法在切分的准确率上比m m 法有很 大提高 ( 3 ) 双向匹配法 从最大匹配法出发导出的。双向最大匹配法”，即m m + r m m 。s u n l v l s a n db e n j a m i n k t ( 1 9 9 5 ) 注意到：汉语文本中9 0 o 左右的旬予，m m 和r m m 的切分完全重合且正 5 山东师范大学硕士学位论文 确，9 o 左右的句子m m 和r m m 切分不同，但其中必有一个是正确的( 歧义检测成功) ， 只有不到1 0 的句子，或者i v i m 和r v i m 的切分虽重合却是错的，或者m m 和r m m 切 分不同但两个都不对( 歧义检测失败) 。这正是双向最大匹配法在实用中文信息处理系统中 得以广泛使用的原因所在。但是，双向最大匹配法存在着切分歧义检测盲区，这种方法只 有检错功能，却不能自动进行校正，给出正确结果。 ( 4 ) 最少切分法 此方法的思想是使每一句中切出的词数最小。歧义检测能力较双向最大匹配法要强些， 产生的可能切分个数仅略有增加。 2 3 2 基于词的频度统计的分词方法 这种方法首先切分出与词表匹配的所有可能的词，运用统计语言模型和决策算法决定 最优的切分结果。它的优点在于可以发现所有的切分歧义，但是统计语言模型的精度和决 策算法在很大程度上决定了解决歧义的方法。需要大量的标注语料，并且分词速度也因搜 索空间的增大而有所缓慢。根据测试结果，其正确率为9 6 2 5 2 。分词速度为：4 0 ，0 0 09 分钟。实际应用的统计分词系统都要使用一部基本的分词词典( 常用词词典) 进行串匹配分 词，同时使用统计方法识别一些新的词，即将串频统计和串匹配结合起来，既发挥匹配分 词切分速度快、效率高的特点，又利用了无词典分词结合上下文识别生词、自动消除歧义 的优点。 2 3 3 基于知识理解的分词方法 该方法主要基于句法、语法分析，并结合语义分析，通过对上下文内容所提供信息的 分析对词进行定界，它通常包括三个部分：分词子系统、句法语义子系统、总控部分在 总控部分的协调下，分词子系统可以获得有关词、句子等的句法和语义信息来对分词歧义 进行判断。这类方法试图让机器具有人类的理解能力，需要使用大量的语言知识和信息。 由于汉语语言知识的笼统、复杂性，难以将各种语言信息组织成机器可直接读取的形式， 因此目前基于知识的分词系统还处在试验阶段对于任何一个成熟的分词系统来说，单独 依靠某一种算法都不可能实现，需要综合不同的算法。 2 4 特征选择方法 训练集中包含了大量的词汇，如果把这些词都作为特征，将带来一系列问题。首先是 向量的维数太大，给计算带来了非常大的压力，存储空间大、处理速度慢。其次是这些词 中实际上有很大一部分是与类别无关的，对分类作用不大。因此，我们要降低向量的维数， 选择那些有代表意义的词作为特征。先对文本进行预处理，去掉那些常用的对分类用处不 大的词( 称为停用词，s t o pw o r d ) ，然后采用某种特征选择方法对所有的词排序，选出排在前 面的一定数量的词作为特征。常用的特征选择方法有： 6 山东师范大学硕十学位论文 2 4 i 文档频率 词条的文档频率( d o c u m e n tf r e q u e n c y ) 是指在训练语料中出现该词条的文档数采用 d f 作为特征抽取基于如下基本假设：d f 值低于某个阈值的词条是低频词，它们不含或含 有较少的类别信息。将这样的词条从原始特征空间中移除，不但能够降低特征空间的维数， 而且还有可能提高分类的精度。 文档频率是最简单的特征抽取技术，由于其具有相对于训练语料规模的线性计算复杂 度，它能够容易地被用于大规模语料统计。但是在信息抽取( i n f o r m a t i o nr e l r i e v a l ) 研究中 却通常认为d f 值低的词条相对于d f 值高的词条具有较多的信息量，不应该将它们完全移 除。 2 4 2 互信息 互信息即m u t u a li n f o r m a t i o n ，简称m i ，定义如下： 蚴= * 等 ( 公式2 1 ) p ( q ) 表示第i 类文本在训练文本集合中出现的概率，p ( t ) 表示词t 在训练文本集合中出现 的概率，p ( t c i ) 表示在第i 类的文本中t 的出现概率m i 越大，词和类的共现程度越大 2 4 3 信息增益 信息增益即i n f o r m a t i o ng a i n ，简称i g ，定义如下： 佑( f ) ：芝，“) l o g 户“) + p ( r ) 艺p 如l f ) l 。g ，“l f ) + p ( ；) 芝尸( c ，l ；) l o g p j 刁 ( 公式2 2 ) i g 啪反映了该词为整个分类所提供的信息量。 上式中，p ( _ ) 表示词f 不出现的概率，p b p ) 表示词，出现的情况下文本属于q 类的概率， 砟，田表示词r 不出现的情况下文本属于c l 类的概率 2 4 4 工：统计量 邝咖两者精蒜丽 ( 公式2 3 ) 7 山东师范大学硕士学位论文 l c i z 2 w ( f ) = 艺p ( q 拓2 ( r ，c 。) 一l a ，b ，c ，d 均表示文本数量，如表2 1 所示，n = a + b + c + d 。 c ；类文本集合 非c i 类文本集合 t 出现a b t 不出现 cd ( 公式2 4 ) 表2 - 1 文本分类表 工2 统计量度量词和类别独立性的缺乏程度，x 2 越大，独立性越小，相关性越大x 乞表 示对所有类别求平均的x 2 统计量。 2 4 5 相对熵 凹= 弘。s 等 。蚴国 也称为k l 距离( k u l l b a c k - l e i b l e r d i ve r g e n e e ) , 反映了文本类别的概率分布和在出现了 某个词的条件下文本类别的概率分布之间的距离，该值越大，词对文本类别分布的影响也 大。 2 4 6 优势率 即o d d sr a t i o ，用于二类分类问题： 删刊o s 器渊 2 4 7 特征频度 ( 公式2 6 ) 特征频度( t e r mf r e q u e n c y ，t o 指训练集中特征k 出现的次数。这是一种简单的特征 选择方法。直观上，特征在文本集中出现的次数越多，对文本分类的贡献越大由予原始 特征集中绝大部分是低频特征，因此，设定西阈值对过滤低频特征非常有效，可以获得很 大的降维度。就高频特征而言，特征的统计分布决定了文本分类的准确率，即当高频特征 均匀地分布在所有文本中时，对分类的作用将是有限的。因此，仃主要用在文本标引时直 接删除某些低频特征。 窖 山东师范大学硕士学位论文 2 4 8 特征权 t s ( t e r ms t r e n g t h ，t s ) 则基于完全不同的思想来度量特征的重要性。它首先定义“相 关文本”，然后认为同时在多个“相关文本”中出现的特征是重要特征，具有较大的强度。 特征项k 的权如下： 舔纯) = p ( f 。, o , i t 。e 出) ( 公式2 7 ) 其中，d 】【、d y 为任意“相关文本”对。在特征权统计量中，没有类型信息，特征权完 全基于文本之间的相关性来度量它的理论依据是基于特征t k 在邻近相关文本中出现的概 率来测试特征的效率。进行特征选择时，选择t s 值较大的特征 以上方法各有利弊文【2 4 】对d f 、m i 、i g 、c h i 及t s 五种特征选择方法进行了比较 结果显示，d f , i g 和c h i 要优于m i 和t s ，而且，d r , i g 和c h i 之间存在很大的相关性 借助于降维统计量，特征选择方法可以取得很大的降维度而不使分类效果下降。 2 5 常用的文本表示模型 目前常用的文本表示模型有布尔逻辑模型、向量空间模型、概率模型、潜在语义索引 模型等。 2 5 1 布尔逻辑模型 布尔逻辑模型( b o o l e a nl o g i c a lm o d e l ) 也称为完全匹配模型，是一种相对简单的信息 过滤模型在过滤时，它以文档中是否包含关键词作为取舍的标准。利用布尔逻辑模型进 行信息过滤，就是给定一系列的具有二值逻辑的特征变量。这些变量是从文档中抽取出来 的，用来描述文档的特征比如：关键字或索引词等，有时也可以是时间、作者的姓名等 个性信息通过布尔操作符把表示文档信息的特征变量构成布尔表达式，此即为一查询。 当在一个查询中，两个查询关键词之间用布尔操作符a n d ( 与) 相关联，则表示对于这两 个关键词，应该都包含在非友善文档中如果两个查询关键词之问用布尔操作符o r ( 或) 相关联，则表示对于这两个关键词，其中有一个包含在查询文档中即可 基于布尔逻辑模型的信息过滤技术特点是实现容易、用户操作方便、易接受，而且查 全率比较好但布尔模型的结果非真即假，限制性过强。从直观上说，如果查询有n 个词， 而用户请求的文档中出现了其中的n - 1 个词，通常我们可认为该文档比较符合查询的条件， 是非友善文档，应被滤掉，但是基于布尔逻辑模型的信息过滤技术却判定该文档是友善文 档，因而会导致漏判 鉴于传统的布尔逻辑模型存在这些不足，g e r a r ds a l t o n 给出了扩展的布尔模型信息过滤 系统，或称为p 标准( p - n o r m a l ) 模型。这个布尔模型信息过滤系统是介于布尔查询和向 量处理模型之间。它的查询构架还是以布尔模型为基础，只是同时增加了关键词相对于查 询或文档的重要程度，也称为权重在该模型中，文档d ( 被表示为d = 碣，面，屯) ) o 山东师范大学硕十学位论文 与查询q ( 被表示为文档向量中特征的与关系和或关系) 之间的相似度， 式( 2 9 ) 所示，其中参数p 的最佳值通常由经验确定，一般在2 到5 之间。 删d ) _ l 一【咝幽半 盟型】，脚忡) 州崛) = p 掣r 脚川 2 5 2 向量空间模型 如公式( 2 8 ) 和公 ( 公式2 8 ) ( 公式2 9 ) 向量空间模型( v e c t o rs p a c em o d e l ) 是由s a l t o n 提出的关于文本表示的模型，使用由 词语构成的向量表示文档信息与过滤信息，并在c o r n e l l 研究出基于向量空间的s m a r t 实 验系统。该模型已被人们普遍认为是一种非常有效的信息过滤模型，它以特征项作为文本 表示的基本单位，特征项可以由字、词或短语组成。所有的特征项构成特征项集。一篇文 献可以表示为一个向量，即可被定义成一系列子项的组合，该向量的维数是特征项集的个 数，并且根据统计结果，该向量的每个分量都被赋予一个权值以表明它对于这篇文献的重 要性。具体定义如下所示： ( 1 ) 假设文档集d = 弘 ，俐= s ( 1 d | 表示集合d 中元素的个数) ，特征项集r = ， ， i “ 阳。”。定义特征项f ，在文档西中的权重为： 嘞= 胚汹肛，肘 ( 公式2 1 0 ) 其