（计算机应用技术专业论文）信息自适应过滤的效用指标优化方法.pdf

大连理工大学硕士学位论文 摘要 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 的重要任务之一，自适应过滤是过滤任务的最重要的子任务。对t r e c 指标函数 的优化是一个包括优化时机、优化策略、优化幅度等因素的复杂的过程，是自适应过滤 中非常重要的研究方向。利用极大似然估计法( 记为m l ) 对评测指标进行优化在 t r e c 9 中取得了第一名的成绩。m l 是一种全局优化的方法，它对文档得分( 相似度) 分布参数估计偏差最小，能够较精确的反映语料集的整体特征。但是m l 是一种全局性 的方法，它对语料库的局部( 每一反馈区间) 特征反应“不敏感”，尤其是到了过滤中 后期由于过滤的累积效应，m l 对阈值的调整有滞后作用，这样就降低了过滤系统的性 能。 本文主要解决的是m l 方法对语料库局部反应“不敏感”的问题，在m l 方法的基 础上对t r e c 效用指标函数再进行局部优化，本文把这种方法叫做基于极大似然估计法 的局部优化方法( 记为m m l o r ) 。m m l o r 不是对m l 方法和局部优化方法简单的相 加，它是一个复杂的逐步迭代的过程。m m l o r 方法以m l 方法为主线，又根据每一反 馈区间对t r e c 效用指标函数的增益情况对阈值进行局部优化，从而增加过滤系统对局 部的敏感度。因此，m m l o r 方法不仅可以反应语料库的整体分布特征，还可以反应出 语料库的局部特征，对效用指标函数起到全面优化的作用。 本文在相同的过滤环境下对m m o l o r 、m l 、局部优化的方法的进行了比较，实 验结果表明采用m m l o r 方法对t r e c 效用指标函数进行优化的效果最好，从而证明 了m m l o r 优化方法比m l 和局部优化方法更合理、更有效。 关键词：自适过滤；阈值调整；局部效用指标优化；m l ；m m l o r 信息自适过滤的效用指标优化方法 o p t i m i z a t i o n m e t h o do f a d a p t i v ef i l t e r i n gu t i l i t yt a r g e t a b s t r a c t 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 li s t h em o s ti m p o r t a n tc o n f e r e n c ei ni rf i e l d a d a p t i v e f i l t e r i n gt r a c ki so n eo ft h em o s ti m p o r t a n tt a s k si nt r e c e v a l u a t i o nm e a s u r eo p t i m i z a t i o n w i t ht h r e s h o l di so n eo ft h em o s ti m p o r t a n tr e s e a r c ha r e a si na d a p t i v ef i l t e r i n g t 1 1 i sp a p e r t a k e st r e ce v a l u a t i o nm e a s l l r ea so u rt a r g e tf i m c t i o n a n dt h e nc o l n p a r e sm a x i m u ml i k e l i h o o d e s t i m a t i o ni nt h et h r e s h o l dt u n i n g ( m e ) 埘ml o c a lt a r g e to p t i m i z a t i o n ，t h e np r o p o s e sl o c a l o p t i m i z a t i o nm e t h o do fa d a p t i v ef i l t e r i n gu t i l i t yt a r g e tb a s e do nm a x i m u ml i k e l i h o o d e s t i m a t i o nf m m l o r ) m li st h eb e s tm e t h o df o rt h r e s h o l di na d a p t i v ef i l t e r i n gi np a s tt r e c m li sa nm a b i a sm e t h o dw h i c h i o i n t l ye s t i w l a t e st h ep a r 锄a e t e r so f t h ed e n s i t yd i s t r i b u t i o n sf o r r e l e v a n ta n dn o n r e l e v a n td o c u m e n t sa n dt h er a t i oo f t h er e l e v a n td o c m n e n ti nt h ec o r p n s m m l o rt a k e st h ea d v a n t a g eo f m la n dc o m b i n e sa1 0 c a lo p t i m i z a t i o nm e t h o d h n 4 io r r e p r e s e n t s n o to n l yt h ec h a r a c t e ro fh o l i s t i cc o r p u sb u ta l s ot h ec h a r a c t e ro fl o c a l c o r p u s m m l o rc a r lt u n et h ef l a r e s h o l da c c o r d i n gt ot h ec h a r a c t e ro f1 0 c a lc o r p u s h n o ri sb a s e d o nm la n dt u n e st h et h i - e s h o l da c c o r d i n gt ot h en e e do fl o c a lc o m u s 1 o ri sn o tp u tt w o m e t h o d s t o g e t h e rac o r n p l e xi t e r a t i v ep r o c e s ss i m p l y m m l o ro v e r c o m e s t h es h o r t c o m i n g so f s i n g l em e t h o d i tp r o v e st h a tt h i sm e t h o d i se f f e c t i v ei ni m p r o v i n gt h eq u a l i t y o f f i l t e r i n g i no r d e rt op r o v et h a tm m l o ri sb e t t e rt h a n 匝a n dl o c a lt a r g e to p t i m i z a t i o n t h i sp a p e r p u t t h r e em e t h o d si n t ot h es a m ef i l t e r i n gc o n d i t i o n i na d d i t i o n ，t h i s p a p e ra m e l i o r a t e s l c t c l a s i c t c l a si sas y s t e mo f s e g m e n t a t i o n a n d t h i sp a p e rm o d i f i e st h er o c c h i om e a n s i no r d e rt o1 i l a k ei tf i tt h ec o r l ： u sb e t t e r k e yw o r d s ：a d a p t i v ef i l t e r i n g ；t h r e s h o l d s ；l o c a lt a r g e to p t i m i z a t i o n ；m l ；m m l o r i i 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究 工作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 大连理工大学或其他单位的学位或证书所使用过的材料。与我一同工作 的同志对本研究所做的贡献均已在论文中做了明确的说明并表示了谢 意。 作者签名：4 j 建盘日期：圣坚：兰 大连理t 大学硕十学位论文 引言 信息过滤就是在动态的信息流中，搜索用户感兴趣的信息( 相对稳定) ，屏蔽掉其他 无用的信息，用户的兴趣一般在较长时间内不会改变( 静态) 。信息过滤是建立在文本 检索的基础上的，但检索中用户兴趣是暂时的，易变的，文本检索的文档是相对稳定、 长期的【1 。 信息过滤是t r e c 的重要任务之一，它的主要任务就是自适应过滤。自适应过滤 2 的主要任务是根据给定的用户查询和与主题相关的训练文档，构造过滤模板，然后过滤 有序的测试语料集合，输出与查询主题相关的文档。每个查询主题仅提供少量的初始训 练文档和一个训练集，训练中不能使用任何测试集的统计信息。测试语料集为有序文档 流，每个文档只被评价一次，如果与主题相关则输出，否则被抛弃。 自适应学习过程中，只能使用过滤得到与主题相关的文档进行反馈，且测试与学习 过程应自动完成，无人干预。用户对检出的文档进行相关性的确认，根据用户的反馈情 况对p r o f i l e 进行调整。自适应过滤环境是最接近实际应用的环境，因此研究具有重要的 意义，它也是最困难的一种过滤。实现时我们可以根据主题描述的相关信息和少量的正 例文档( 相关文档) 产生一个初始阈值0 ，作为过滤检出的门槛。显然，阈值0 对于自 适应过滤来说是非常重要的，如果对闽值设得过高就会检出很多不相关的文档，如果设 得太低就会漏掉相关的文档。对阈值进行调整是自适应过滤的关键技术之一。 t r e c 鼓励参加者提交针对评测指标进行的优化方法【3 】，由于对t r e c 指标函数的 优化是一个包括优化时机、优化策略、优化幅度等因素的复杂的非线性系统，要获得良 好的优化效果比较因难，因此成为过滤任务研究的重点和难点之一。近年来也有不少关 于针对t r e c 评测指标进行闺值优化的方法，这些方法中极大似然估计法在t r e c 9 中 取得了第一名的成绩，但是极大似然估计法对闽值调整有滞后作用，到了过滤中后期对 闽值的调整不及时，影响了过滤效果。 本文主要介绍我们对m l 方法的改进方法：m m l o r 优化算法。m m l o r 方法改进 了极大似然估计法对闽值调整滞后的问题，加强了闽值调整的实时性，提高了极大似然 估计法的“敏感度”，并通过实验来证明m m l o r 方法的合理性和有效性。 1 信息自适过滤的效用指标优化方法 1 绪论 1 1 论文背景 长期以来，在信息检索科学领域，文本过滤和分类都是自然语言处理的个重要的 应用领域。实是上，人们早从6 0 年代早期就开始了文本分类和文本过滤的研究。例 如，图书馆的工作人员按照一定的分类体系将各种图书按照内容分到不同的类别中，人 们当时主要采用的是知识工程的分类方法，即人们根据各种领域知识，手工为每个类别 定义了很多条分类规则，然后根据规则手工分类各类文档。人工分类需要大量的工作， 并且要求分类人员具有较多经验和专门知识。在这类系统中，其中最著名的系统是路透 社开发的c o n s t r u e 系统 4 】。然而，这类系统的缺陷是分类质量有时得不到保证，由于 是传统的手工分类，周期长、费用高、效率低，而且往往需要具有专业知识的人员才能 胜任，难以满足当今的实际需要。因此，在人工分类文本中存在大量的问题，主要体现 在精确度和时间代价上。 1 1 i 信息过滤是海量信息的需要 进入九十年代以来，人类社会以进入了信息时代。随着i n t e m e t 网络在全球的迅速 蔓延以及计算机软、硬件技术的飞速发展，人们利用信息技术生产和搜集数据能力的大 幅度提高，大规模的文本库不断涌现，有些已经达到t b 级。“新摩尔定律”指出： i n t e r n e t 上的信息正以每六个月翻一番的速度爆炸般地产生。它使任何上网寻求信息的 人都难以选择。人们已经从信息缺乏到信息过多，乃至淹没在海量的信息中。 面对汹涌而来的信息，人们没有必要而且也没有足够的时间和精力去阅读所有的这 些信息，越来越多的用户只希望看到自己感兴趣的信息，人工过滤的方法显然对海量的 文档和数据无能为力。这就使人们产生了这样的迫切心情，要求能借助于某些工具，自 动对这些信息进行过滤并自动滤除不需要的信息，从而能直接获取有价值的情报和知 识。可以想象，如果没有一个强有力的工具来帮助人们寻找、发掘有用的信息，人们就 会被淹没在信息的海洋中，迷失方向。如何在海量文本库中搜寻、过滤、和管理己经成 为个目前亟待解决的问题。 1 1 2 信息过滤是保障信息安全需要 一 功能强大的信息网络的崛起与发展，在给社会生活带来巨大进步的同时，也带来了 一些新的问题。从国家安全的大视野来看，随着全球网络的普及，传统的国界的概念首 先受到冲击，逐渐趋于淡化。以现在建成的世界上影响最大、用户最多，信息资源最丰 一2 - 寓的懒i h 联t q 络为例，j 战魁个没有边界、没宙条约“新大陆”，是个丰具姚模 仇尚未最后形成的朦胧f 【i ：羿。这就a 接涉及到维捌司家“通信丰权”硐i “信息? 1 1 权”， 保，1 。h d 荔i4 ：l 掉l ：毫争。系步0 l0 题 特刚并小足个舆。环境，它伽删一把x 义刃利剑，狂给人类造梢川i 洲十，也带来 了 系列的社会叫题。舡小州的社会制度、信息环境、文化背擐和宗教信仰f l q 影响下各 幽川户在这+ 际h 耋 空m 从。m ! i 息发川传递和使川n 勺过黜h 表现 不l 训m 行为规 范用| j 煎德准则。于ij ，j i + - 1 家网络川1 一从洲特网创：之初就一直尜行“高沦h ”的原 则，刈仃f f 形式的域j ni i 竹j ； i ! 凇阿：有抵触f 。绪，w 加i ：网络仁f ：质已经从1 j 事、学术 阳商业化 0 变，使褂人们j , j 以j ：扦种州j 地红l i i rn i 发们和传递信息，给违法、有 f i i ：$ u 儿川竹息n 0 传播捉供j - 机会，给特| ；( 】9 l + 内信息环境造成j 7 。定程度n 0 污染，妨缁j 人f fj 划! ；_ f i i 息i 门干4 h ，造成j ，1 i l 辽n q 1 会自 ；j 4 q 。 信息产, i k k t ：较发达巧川q 家，捌川信息技术优势，人刖j = 布和传摘他, f i ：j i r l 0 政治 i 张羽i 价他观，眭命诋毁和搦。；他闭形鲰i 涉别i 内政，j ，l , d j j ：l ： f i b f f , i 家内部、闭家之 i t i j 、l t 族j j 教之l in j f r j 矛所，一i 断以魁浠视听的胜似价i 。臼册j 造混i r i l 。：羿j 螳【七族、宗 教刚体、政 f 7 党派、极端组织叱通过符种架通f 。搬足政治： ! k ，刈周家政治观念利个人 j l ! i 想造成j - 姒烈旧冲洲此，我们必需矬设术i ：j i l # 效的信息边界，采墩! 西业l ：f c j 防护措 施以砷保安个。 列我川米波，我信息i q t f f f i , j 发j 陡还川川起步，俎然已经建立起全闻公l 数字数搬 通信h 、i 川日教仃和科i i j j = l 硼，i l l 科院科研h 等众多信i ，心叫络，i i = l ) l j y i1 0 0 0 多个数捌 库，f h 背遍存在? j ： i ：t 息资源规模小、范| i i + 1 窄、质蜒麓等刚题，影响信，心网络功能n q 发 摊，也造成j 订! 找刚信息川络老水灶跑“洋1 _ = t ，硐f 送“洋货”f | q 局而。埘吲外信息资 源的过分依赖，使搿方文化渗透f i t j 避免，仆给删络信息安全带 求更人矧憩忠。 f 1 - j , 个 i ：会1 义人川如何倮 i 我的能心外“i i 个极其紧迫利严峻j 门任 务。n i 例特仃i 息i i ：界f - f 处漩防、如p 设防，以促进一! i i l i t l j i f 效f 占息i n _ ；f ：“敝1 j 4 f d 射，防 盹鸵洲缘负的无效的、挞伞仃藩能也的传播，这足对州家信息安个和1 ：权完懿，| i 死攸 关的题t 婴保断叫 ? 吲i q 络 旷卜安，关键足蛩筑起刚卜欧城。研究何开发大规模信 息过滤系统i r 是解决这问题的芙锼韭所存。 l ，1 3 过“b 技术的i 托要心义 文术一动过滤技术足信息榆索领域的。疆篮研究课题，在人舰模文本信息处驯中具订 彳i i ；i f i t ：要旧意义。从俯，也处_ j ；! i i i l ：j 们度j i 雨文本过滤柯如f 儿个戍，领域【6 】 7 l ： 一3 信息且通过滤的效用指标优化方法 提供选择性信息服务的企事业单位可以根据用户的信息需求过滤新闻信息，并且把 用户可能感兴趣的内容发送给用户。这类似于图书馆和科技情报机构等提供的定题服 务。 ( 1 ) 在档案管理领域，文本过滤系统可自动地确定档案所属的类别 ( 2 ) 对终端用户而言，可以用具有文本过滤功能的代理程序来接受原始文本流( 如 e m a i l 和n e w s f o u p ) ，并从中选择用户可能感兴趣的内容。 ( 3 ) 研究与开发具有自主版权的信息过滤系统，对于提高我国的网络和人工智能的 研究和应用水平、保障围家信息安全、促进i n t e m e t 技术在我国的健康发展也有着重要 的意义。 1 2 文本过滤的研究现状 1 2 1 文本过滤发展概述 文本过滤随着计算机应用的发展从设想变为现实，并不断地完善自身的功能，经历 了很长的发展时期，并在因特网目益普及的今天，在信息发掘方面发挥着越来越大的作 用 8 】 9 】。 1 9 5 8 年，l u h n 提出了“商业智能机器”的设想f 5 ，在这个概念框架中，图书馆工 作人员为每个用户建立用户需求模型，然后通过精确匹配的文本选择方法，为每个用户 产生一个符合用户信息需求的新文本清单。同时记录下用户所订阅的文本用于更新用户 的需求模型。虽然微缩胶片和打印机技术的发展，使得实现的物理细节有所不同，但他 的工作涉及到了信息过滤系统的每一个方面，为文本过滤的发展奠定了有力的基础。 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 fi n f o r m a t i o n 选择性信息分发系统) 1 0 】引起 了人们的广泛兴趣，导致了美国信息科学仂会成立了s i g s d i ( 选择性信息分发系统兴趣 小组) 。但是大多数系统都遵循l u h n 模型，只有很少的系统能够自动更新用户需求模 型，其他大多数仍然依靠专门的技术人员或者由用户自己维护。s d i 兴起的两个主要的 原因是实时电子文本的可用性和用户需求模型与文本匹配计算的可实现性。 1 9 8 2 年，d e m z i n g 提出了“信息过滤”的概念 1 1 ，他的目的在于拓宽传统的信息 生成与信息收集的讨论范围。他描述了一个信息过滤的需求的例子，对于实时的电子邮 件，利用过滤机制；识别出紧急的邮件和一般例行邮件。他采用了一个“内容过滤器” 来实现过滤。其中采用的主要技术有层次组织的邮箱、独立的私人邮箱、特殊的传输机 制、资格验证等。 d 人近驯一i 人学坝h 学似论义 1 9 8 7 年m a l o n e 等人发表较订影响的渔文 1 2 1 _ ： f ：研制了系统“i n f o r m a t i o n l e n s ”捉h i 丁俐，竹息选择模式，即认知、经济、社会。所州的认知模式棚当于 d e n n i n g 的“内椿过滤器”，【! | _ jj i l0 二内窑的过滤( c o m e n t b a s e df i l t 耐n g ) ；经济模式米自于 d e n n i n gi ：l q “闽值接收”i ! _ l 想；社会梭j 弋魁他最重婴的贡献。hl 讨也称为“合作过滤”。 谯社会过滤h 文本l f ，j 表示足) 二_ 二以前读兹+ 划。予文小的标注，迎过交换信息，闫动识别 ! t # j - j u 兴趣n 勺i a l l 4 1 = 。 1 9 8 9 年，m 这个时；| i j 化息j = ：滤获得j 7 人川模i 0 政府赞助。1 荚hd 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 ”，檄人地推动1 i 息过滤的发展。他川信息抽墩 披术支持俯，j l ：i , f 1 9 选扦，钉：将然语，处州技术j ，f 入史小过滤研究方1 0 i 进行了积极的探 索，1 9 9 0f r ，d a r p a 建奠：厂t i p s t e r 小虬的在j ：利用统计技术进行消息预选， 然肝_ | 怔1 , ! lj 1j 复j 0 的i f 然讯青处肌。这个文小预选过程称之为“文水检测”。 1 9 9 2 4 1 2 ，n i s t ( 美旧：家标准和技术岗) jd a r p a 联合赞助j 7 每年次的 t r e c 1 3 】( t e x tr e t r i e v a lc o n f e r e n c e 文术检索会议) ，列文本检索和文本过滤倾j ! = j ：j 极犬 的热忱。迄今为i ：已经，浮办1 4 删，t r e c 1 4 】旨和趔过挝供她l 范的火规模语判( g b 级) 和刈文_ 小= 检索系统性能的铎剐、公小的开测，求促进披术的交流、拨胜平产_ k 化：促进 政府部、0 术界、_ i ) l k 界问1 1 4 交“冲l 合i t ，加述技术的产业化；发展埘文本检紫系统 n 勺i ：l 洲技术。埘文木过滤的形成乖i 发胜提供j 强l r 力的支持。 i i | ；i f f 翁l 矗l 特j 叫的迅迷发眨，滞求小断增加，限史小过滤以及干荚技术方，取得 了氏足的进展，成为信息产、新的增长t i 、 1 2 2 文小过滤的佰务捕述 文水过滤火致f i 以分为两类：蟾1 二内铎i 伯过滤( c o n t e n t - b a s e df i l t e r i n g ) $ 1 1 合作过滤 ( c o l l a b o r a t i v ef i l t e r i n g ) 。合作过滤叉称社会过滤 1 5 1 6 】 17 】。扫满川：内豁f i j 过滤模j “h 呼个j i j ) 、f | j 2 定足十o ：独洲浆 f iz l i ( j 。1 ) 4j l 七，文小农示仪仪依赖j i 从文本内棒所铁驭的 倍，u , 1 8 。合作过滤的发_ 在州肼u 人兴趣小是孤由的，成处 二某个群体当i h 在 r 川0 牛i 川，人们接受的能批什足川i i ；1 人推荐的绌果。冈此，十l d j i ) r l i 同或齐：近必越 f f ，川，、列棚应义术做m 的玎渖，i f , j 3 c 他j ij ) r 迸伯：推荐。i i | j ：彳j 依赖r 内存，运种模式彳i 仪通川j 二文小格式，也4 i _ r 以广泛应j i j3 。m 文术介质的i 乜f 媒介，如m p 3 、图像、v i d e 。 等。小：史的 ：们：集仡撼n 弈的文小过滤j ：。 作为 个崭相? i 1 9 6 ) i ：究领域，文术过滤的仟务定义谢程逐渐演化，难度越来越人， 以蜓女r 地模拟e 史环境。以著织的博悯、义水拎索会议t r e c 为例：从1 9 9 7q - f 1 9t r e c 一 6 开始，义术过滤的l - 要仃务逐渐蚓定r 米。以f 、 止f l 从t r e c 9 至今的史水过滤项i ：i 的 一5 信姐。r 1 通过豇帕效圳= | j 彳i | ；_ | ：优f l d 妇、 任务定义【19 】【2 0 ：给定个1 ：题批1 1 述( 驯j j 户甜；求) ，建立个能从文本流中自动选择蚊 相关文本的过滤模板( f i l t e r i n gp r o f i l e l 随着文水流的逐渐进入，过滤系统m 功地接受或 拒绝文术，_ j = 得到史水牛廷。j 否帕反锃越能翅、。再袱据及坝仔漶适应地修正过滤摸板。 “史水过滤顺| | 包禽i 个r 托务：分流、批过滤、i l 适应过滤。 ( 1 ) 分涕l ( r o u f i n g ) 厂f 务：j l 丑i 求定，捉供刈成j ：该“j j 、。；府求的训练文本集叶t i 竹帆i 关文小，从川p 衙求构造询讲彳l j 术在咖测试文水集。 ( 2 ) 批过滤( b a t c hf i l t e r i n g ) ：川户什j 求朋定，捉f j i 对j 域j 二该1 。需求的训练文水集t | ， 的川：文本。构造过滤系统，埘测试艾小集i i q 4 q ：义水做接受或拒绝的决策；_ i 州 的魁分流仃务要求按州似度从人剑小删l | ! ； j 榆。数吣批文小，m 批过滤则要求将文小分 成帆i 荧利小1 1 i 父州类 ( 3 ) 自通应过滤( a d a p t i v ef i l t e r i n g ) ：它坚求仪仪从i - 题狲述发小挺供或 摊供 很少的训练文术逐判断输入史木流t t i f 门文小灶7 i 棚关。刈“接受”的义木，能得到 川j t 的反馈竹息，川以r 1 适j 衄地修l i ：过滤楼板。做“抓绝”的文水足不提供反馈t ! i 息 的。这是坡接近贞实川i 境也址蛾舶| ，jj ，f e 务。 1 2 3 文水过滤似殳小榆索n 勺哭系 文本过滤和文小分类及文本检索仃1 徽火的年似之处。文术分类就址将义术u1 5 1 q h , ：t 个类别“1 - 。_ ：史小分类过剃t i t ，：迎_ i 的类别t j 。以足颅儿给定的，也，j 以足小确定的。曲 高对心自动分类中的l ，_ i 动9i 类，衍轲刈j 皿i 1 动分类t q j i i 动聚类。一动| 类是分析铍分 炎对琢f i q 特征j f j 符利i 类刖一l t 时级所i i 仃的兆嗣特征( 或定的分类标准、分类参数) 进行比较，然j 再将剥象划* i 为特“i ：最接近的类( 或最符合怕；7 1 l i 参数的。类) ，并赋r 千h 应的分类号。仵文水过滤一i 一削断文书址t 潲：台川j 、前求w 以番f i ：址个两类( 址仃) 的 分类0 d 题。 酬样，文小过滤j 给定检索, t , t d t ，从文小h i f l 艘索杜l 荚文术们文小检索过釉地是非 常水l c j f l j ；s i ) i 小川的灶文奉榆索7 r 相l x , i - i , ! i 1 定| 1 | 文本_ l i 渊忏变万化晌检索需求，而史小过 滤则有着棚剥川定的1 需求和动态变化f | q 史小流。呵以蜕。义小过滤利义水榆索足刚 硬币的j r 及阿面。 文水过滤和义术检索_ 仃料密切i i ，j 联系。过滤实际i ：址建立在榆索f l , i t f i l l l 之j ：的，因 为它借豁j 许多捻_ 裘的袭“办法利技术。文小榆索就琏, f 1 7 4 j , ! u 伽- 摊f “f | ：j 腆体查柏i 犬 量相对稳定的史水源一1 t ，检索t i l t ：? 俞川j ，夼洵条4 - 1 ：的文水，j | 披其满足镬询的翟l ! 艘 l l j 弘 列。 ，6 大连理工大学硕士学位论文 文本过滤建立在文本检索的基础上，但又有其自己的应用背景和处理技术。文本检 索和文本过滤的相互关系类似于一个硬币的两面，是统一体的两个不同侧面。认清文本 检索和文本过滤各自不同的特点，对于我们在设计文本过滤的逻辑模型过程中充分利用 成熟的检索技术以及消除它存在的局限性是十分必要的。主要不同之处表现在如下几个 i 方面【2 1 】： ( 1 ) 文本过滤的用户需求是相对稳定的、长期的查询；而文本检索的用户查询则是 随机的，易变的： 文本过滤所面对的文档是新的、动态的：而文本检索所面对的文档是相对稳定 增长的； ( 3 ) 文本过滤的用户需求是相对稳定的，所以需要保存和维护，依此更新和改善效 果；而文本检索的用户查询则是短暂的，不必保存和维护； ( 4 ) 文本过滤较之文本检索更需要用户的反馈，通过用户对于提供的文档的反馈， 采用机器学习等方法，增进需求的表达能力，改进过滤效率。 1 3 向量空间模型简介 计算机并不具有人的智能，人在阅读文章后，根据自身的理解能力可以产生对文章 内容的模糊认识，而计算机并不能轻易地“读懂”文章。因此文本自动过滤遇到的基本 问题是如何对文本按照计算机可以“理解”的方式进行有效的表示，从而在这个表示的 基础上进行信息过滤。当前文本过滤中主要应用的模型是文本的向量空间模型( v e c t o r s p a c em o d e l ，v s m ) 。向量空间模型是由s a l t o n 等人于上世纪6 0 年代末提出，并成功地 应用于著名的s m a r t ( s y s t e m f o rt h em a n i p u l a t i o na n dr e t r i e v a lo f t e x t ) 系统。该模型及 其相关的技术，包括项的选择、加权策略，以及采用相关反馈进行查询优化等技术，在 文本过滤、自动索引、信息检索等许多领域得到了广泛的应用。 2 2 1 1 2 3 v s m 己成为最 简便高效的文本表示模型之一。 1 3 1v s m 的几个基本概念 v s m 的几个基本概念的几个概念如下： ( 1 ) 文档( d o c u m e n 0 泛指一般的文本或文本中的片断( 段落、句群或句子) ，一般指 一篇文章。尽管文档可以是多媒体对象，但在下面的讨论中我们只认为是文本对象，并 且对文本与文档不加以区别。 ( 2 ) 项( t e r m ) 文档的内容特征常常用它所含有的基本语言单位( 字、词、词组或短 语等1 来表示，这些基本的语言单位统称为“项”，即文档可以用项集( t e r mu s o 表示为 信息自适过滤的效用指标优化方法 d ( t i ，t 1 砖，其中t k 是硕，is k 曼n 。对于含南n 令颐钓艾栏d 。l 曲，颂坛谍篙 被赋予一定的权重，表示它们在文档d 中的重要程度，d = 矗 w ，i 如w 2 7 ”_ v j ， 简记为d = d 阳， w 2 , w 。其中w k 为靠的权重， j 。 ( 3 ) 向量空间模型( v s m ) 给定一自然语言文档d = dp 如，t u ) ，由于“在文档中既 可以重复出现又应该有先后次序的关系，分析起来仍有一定的难度。为了简化分析，可 以暂不考虑t k 在文档中的先后顺序并要求“互异( 即没有重复) 。这时可以把f t 2 , “看 成个n 维的舶标系，而w w 2 , w 为相应的坐标值，因而dr w w n ，w d 被看成是 n 维空间中的一个向量( 如图1 1 中的d i ，d 2 ) ，称d 似，j _ h ，n ，w 一为文档d 的向量表示 或向量空间模型。 ( 4 ) 相似度( s i m i l a r i t y ) 两个文档d ，和d 2 之间的( 内容1 相关程度( d e g r e eo f r e l e v a n c e ) 常常用它们之间的相似度s i r e 似d 2 ) 来度量 图1 1 向量空间模型 f i g 2 1v e c t o rs p a c em o d e l w 2 0 1 3 2v s m 的相似度的计算 当文档被表示成向量后，文档与文档间的关系可以表示成文档间的距离，通常用两 个文档向量的内积来表示： s i r e ( d , ，d 2 ) = 彬。+ 。 = l 或夹角余弦来表示 一8 一 大连理工大学硕士学位论文 s i r e ( d 1 ，d 2 ) = c o s o = 彤。4 。 ( 1 2 ) 1 3 3v s m 的优缺点 v s m 的优点在于它把文档内容简化为特征项及其权重的向量表示，把对文档内容 的处理简化为向量空间中向量的运算，使问题的繁杂性大为降低。但过多的简化必然会 丢掉大量的文本结构信息( 如句子中词序的信息：“我打你”和“你打我”的语义是不 同的，但它们都有相同的项集) ，而这在自然语言中是至关重要的。另外，在权重和相 似度的计算中也作了许多简化工作：一是对不同语言单位构成的项大都只考虑其统计信 息并采用统一的权重计算方法，所以计算出的权重未必能反映其真实的重要性。二是很 少考虑项之间的相关性，例如，采用内积相似度意味着不同项之间是正交的( 即t = 以当t 。这显然是不太合理的。目前已有许多改进相似度计算的建议，但效果并 不明显。原因在于语义关系实际上是一个很复杂的运算，采用简单的初等运算替代它， 误差势必难免。 1 4 文本过滤常用方法及逻辑模型 文本过滤的本质是进行模式识别，自动过滤系统就是用计算机实现人的模式识别能 力。模式识别是人类基本的思维形式之一，是认识世界的基本方法。人类为了掌握客观 对象，按对象相似的程度组成类别，模式识别的作用和目的就在于面对某一具体对象时 将其正确地归入某一类别。所渭模式，广义地说，是指存在于时间和空间中的对象特 征，是通过对某个具体对象进行观察所得到的具有时间和空间分布的信息。而模式所属 的类别或同一类中的模式的总体称为模式类( 或简称为类) 2 4 】。 从实现原理上分，有以下两种自动过滤方法： 一是基于数据的机器学习方法( m a c h i n el e a r n i n g ) ，研究从观测样本出发，将一些己 知的并己被成功解决的问题作为范例输入计算机，寻找规律( 即利用一些做好标识的训 练数据自动地构造分类器) ，机器通过学习这些范例总结并生成相应的规则，这些规则 具有通用性，使用它们可以解决某一类的问题。现有机器学习的重要理论基础之一是统 计学。传统统计学研究的是样本数目趋于无穷大时的渐近理论，现有学习方法也多是基 一9 一 信息自适过滤的效用指标优化方法 于大数定律的结论。由于基于相对简单的机制，以及实际环境中所表现出来的良好性 能，而为大部分文本过滤系统所采用。 二是基于规则的方法，一般由知识库和推理机两大基础部分组成。知识库储存了从 专家那里获得的关于某领域的专门知识，推理机具有推理的能力，即根据知识推导出结 论，而不仅仅是简单搜索现成的答案。由于需要由知识工程师手工编制大量的推理规 则，因此其开发费用是相当昂贵的。 文本过滤本质上是一个分类过程，和在其他研究领域所使用的分类器相同，用于文 本过滤的分类器，其目的也是实现从特征空间到类别空间的映射。在文本过滤领域，一 个比较明显的特点是待分类样本维数高，类别可能比较多，而且噪声大。所以分类器的 设计必须要充分考虑到这些特点，以达到较好效果。 中文文本相对于其他语言的文本来说，有其自己的特点，首先是分词问题、未登录 词以及记性标注问题，更进一步包括停用词表的建立、概念词典的建立以及语义分析的 问题，导致中文文本过滤困难重重。参照国外相应的过滤系统，结合中文文本处理的具 体情况，设计的中文文本过滤模型如图1 2 所示： 针对中文文本的特点，在用户信息需求表示和文本表示中，增加许多中文处理的特 性，如分词、停用词处理、概念标注、概念自动扩张等，甚至包括潜在语义索引在内的 复杂语义处理功能。 用户模板空间按照倒排序索引方式存储用户模板，用户模板的方式有关键字表和示 倒文本。 过滤文本集合保存用户确认的相关文本，供用户反馈模块使用，改进用户相应的模 板。 浏览文本模块以可视化的方式浏览过滤引擎提供的结果。 反馈模块提供利用用户反馈改进过滤算法的功能。 过滤引擎是系统的调度核心，它从文本集中取出文本，再与每个用户模板匹配，生 成的结果发送给用户；又将用户对文本的反馈，调用反馈模块，修改相应的用户模板。 这里，用户需求和文档均采用向量空间模型表示，进而，需求与文档的匹配机制， 就是采用常见的相似度计算，并按其大小排列输出给特定用户。 目前的过滤系统一般要经过特征提取、文本表示、过滤模型训练和自适应过滤几个 步骤。训练与过滤算法多是基于向量空间模型的分类算法，如最小距离的分类器， d e c i s i o nt r e e ( c 4 5 ) d n f ，k - n n 近邻) ，n a i v e b a y e s ( 卡l 素贝叶斯) ，n n e t ( 神经网络方 法) ，r o c c h i o 和s v m ( 支持向量机算法) 等等 2 5 2 6 1 1 2 7 。 - l o 大连理工大学硕士学位论文 图1 2 中文文本过滤模型 f i g 1 2f i l t e r i n gm o d e l o fc h i n e s et e x t 1 5 论文的组织结构 全文分为四章，对过滤、自适应过滤的进行了介绍，尤其是对自适应过滤中的目标 优化技术进行了的分析和比较。在对极大似然估计法分析的基础上，提出了它的改进方 法( 桃0 r ) ，及利用m m l o r 算法设计并实现了自适应过滤系统。在相同的过滤环 境下对i v m i l o r 、m l 和局部优化法的试验结果进行了比较，从而证明了i v l m l o r 算法 的优越性。本文的章节层次如下： 第一章绪论，主要介绍课题研究的历史，背景，还对过滤的定义、发展历史和过滤 常用的方法做了介绍。 第二章t r e c 及自适应过滤介绍，主要介绍了n 砸c 会议的发展历史、t r e c 的任 务和数据集；对自适应过滤及当前的评测指标优化方法作了详细的介绍，并对这些方法 进行了比较。 第三章主要是对极大似然估计法、局部优化的方法进行描述和分析，在此基础上对 基于极大似然法的局部效用指标优化算法并进行了详细的说明。 第四章主要是对过滤系统总体描述，系统主要体现了基于极大似然法的局部优化方 法( m m l o r ) 及用户模板初始阈值的确定方法。并对极大似然估计法、局部目标优化和 i v i m l o r 法的试验结果进行了分析比较，证明i v i i v 几o r 的有效性。 最后是对课题研究工作的总结。 - 1 1 信息自通过滤的效用指标优化方法 2 t r e c 及白适应过滤 2 1t r e c 简介 信息时代，网络得到广泛的应用，人们可获得的信息总量以几何级数增长。如此海 量的信息使得可用资源大量丰富，但与此同时，获得有价值的信息就像大海捞针一样， 信息的利用难度也大大增加。在这种情况下，对高速度、高质量的信息检索的需求变得 空前的迫切。而文本检索仍然是其中最基础最常用的部分。 在信息检索中，人们通常用检索精度和褶回率两个表中来衡量系统的性能。但是对 于召回率的评价有个前提，即对于用户查询，在整个文档集合中相应的相关文档都已 确定。但这一点经常无法满足，尤其是在w e b 环境下，相关文档的完整集合不可能找 到。因此如何对结果进行合理评价是一个重要的问题。另外，人们通常通过一个标准的 测试集，对来自不同系统不同检索方法进行合理评价是一个重要问题。而如何构造测试 集合，也是一个重要的问题。文本检索国际评测会议t r e c 1 2 】( t e x t r e t r i e v a l c o n f e r e n c e ) ( h t t p ：t r e c n i s t g o v ) 则是为解决这个问题提供了有效的途径。 w r i c 是由n i s t ( n a f i o n a l i n s t i t u t eo f s t a n d a r d sa n dt e c h n o l o g y ，美国国家标准技术局) 和d a r p a ( t h ed e f e n s er e s e a r c hp r o j e c t sa g e n c y ，美国国防高级研究计划局) 赞助并组织 的文本信息检索领域一个国际性标准评测会议。t r e c 的评测本着公平和公开的原则， 数据集规模大，结果评价方法可行而有效，因此在学术界有着相当的权威性，并成为目 前信息检索领域里规模最大的深有影响的标准评测会议。从1 9 9 2 年至今每年一次，已 经举办了1 3 届。评测分为一些不同的项目( “t r a c k s ) ，包括跨语言检索( c r o s sl a n g u a g e t r a c k ) 、信息过滤( f i l t e r i n