（计算机软件与理论专业论文）面向web信息检索的知识挖掘.pdf

摘要 摘要 随着互联网络的快速发展，搜索引擎成为人们获取日常所需信息的重要工 具。目前主流的信息检索系统以传统的关键词匹配技术作为核心，该技术在一定 程度上满足了用户的信息需求。但是用户查询通常都很简短，不具备严格语法 而且富于歧义，这些给当前的信息检索技术带来了极大挑战。因此，如何通过 从互联网络数据中挖掘知识来改善w e b 信息检索的性能以及构建w e b 信息检索 相关服务，更好地为互联网络用户提供服务成为当前的一个研究热点。 本文以提高w e b 信息检索的性能和构建w e b 信息检索相关服务为背景，基 于用户查询r 志和w e b 两类大规模互联网络数据开展了知识挖掘研究，其中包 括基于用户查询日志的查询分类、基于用户同志的命名实体挖掘和基于w e b 的 实体关系挖掘： 1 基于用户查询日志的查询分类 我们首先开展了基于用户查询日志的查询分类的研究。该研究针对用户查 询特征少和多话题的特性，提出了一个基于修正关联话题模型的分类框架，该 框架通过中间分类体系和概率模型来获取用户查询和目标分类体系之间的关 系，此外该框架中还通过语义扩展的方法来丰富用户查询和目标类别的语义信 息。在k d d c u p2 0 0 5 评测数据集上的实验表明，我们提出的基于修正关联话题 模型的概率分类框架显著地优于其它参评方法，具有更加优越的查询分类性能。 2 基于用户查询日志的命名实体挖掘 我们进一步研究了针对大规模用户查询日志中丰富的命名实体的挖掘技 术。用户查询通常都很简短( 往往只有2 - 3 个词) ，并且不具备严格的语法，语 义很模糊，因此文本领域中的命名实体挖掘技术不能直接有效地应用到查询上。 这给基于用户查询的命名实体挖掘的研究工作提出了新的挑战。我们分别尝试 采用弱监督的学习方法和监督的学习方法来从查询日志中进行命名实体挖掘， 这两个方法分别从不同的角度来形式化查询同志中命名实体挖掘所面临的问 题。在大规模实际用户查询日志数据集上的实验表明，我们提出的基于修正关 联话题模型的命名实体挖掘框架和基于转移学习的命名实体挖掘框架都显著地 优于其它参评方法，具有更加优越的命名实体挖掘性能。 3 基于w e b 的实体关系挖掘 区别于传统文本领域中的实体关系抽取，我们这里的实体关系挖掘所关注 的是t r e c2 0 0 9 提出一个关联实体查找评测任务。关联实体查找任务的目标是 根据用户提交的查询在w e b 数据集中找到与查询相关联的目标实体返回给用 户。该任务是为了解决用户通常的实体查找需求而提出的，但并没有像传统的 t 摘要 a dh o c 文本检索任务那样有很好的形式化建模。该任务的关键是如何构建能高 效处理大规模语料的检索框架，以及如何构建实体间的关系模型。我们提出了 一个基于概率模型的实体查找框架，该框架通过概率的方法建模实体问的关系 来进行实体排序。在t r e c2 0 0 9 关联实体查找任务数据集上的评测结果显示， 基于概率模型的实体查找框架具有非常优越的性能。 面向w e b 信息检索的知识挖掘的研究近年来才刚刚兴起，本文的研究工作 对推动这个研究方向的发展起到了重要的作用。同时基于知识挖掘来改善信息 检索的性能和构建信息检索相关服务还需进一步研究。 关键词：信息检索用户查询日志查询分类命名实体挖掘实体关系挖掘 话题模型语义扩展知识挖掘转移学习无监督学习弱监督学习 a b s t r a c t 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 to fi n t e r n e t ，s e a r c he n g i n eh a sb e c o m ea ni m p o r t a n t t o o lf o rp e o p l et og e tt h ei n f o r m a t i o nt h e yn e e d n o w a d a y s ，t h ec o r et e c h n i q u eo f m o s ti n f o r m a t i o nr e t r i e v a l ( i r ) s y s t e m si sk e y w o r dm a t c h i n g ，w h i c hh a ss a t i s f i e d u s e r sr e q u i r e m e n tt oac e r t a i nd e g r e e h o w e v e r , u s e r s q u e r i e sa r eu s u a l l ys h o r t ， i n f o r m a t i v ea n da m b i g u o u s ，w h i c hg r e a t l yc h a l l e n g e sc u r r e n ti rt e c h n o l o g y t h u s ，i t h a sb e c o m eah o tr e s e a r c ht o p i ct om i n ek n o w l e d g ef r o mw e bd a t at oi m p r o v et h e p e r f o r m a n c eo f i ra n db u i l di rr e l a t e ds e r v i c e i nt h i sp a p e r ，w ef o c u s e do nm i n i n gk n o w l e d g ef r o mu s e rq u e r yl o g sa n d w e b p a g e sa i m i n gt oi m p r o v et h ep e r f o r m a n c eo fi ra n db u i l di rr e l a t e ds e r v i c e ， w h i c hi n c l u d e sq u e r yc l a s s i f i c a t i o nb a s e do nq u e r yl o g s ，n a m e de n t i t ym i n i n gf r o m q u e r yl o g sa n de n t i t yr e l a t i o nm i n i n gf r o mw e b p a g e s ： 1 q u e r yc l a s s i f i c a t i o n ( q c ) b a s e do nq u e r yl o g s w ef i r s t l ys t u d i e dt h ep r o b l e mo fq c s i n c eq u e r i e sa r eu s u a l l ys h o r ta n d a m b i g u o u s ，aq cf r a m e w o r ki sp r o p o s e db a s e do nr e g u l a r i z e dc o r r e l a t e dt o p i c m o d e l ( r c t m ) t oa d d r e s st h e s ep r o b l e m s t h i sq cf r a m e w o r kc a p t u r e st h e r e l a t i o n s h i pf r o mq u e r i e sa n dt a r g e tc a t e g o r i e sb ya ni n t e r m e d i a t et a x o n o m ya n da p r o b a b i l i s t i ct o p i cm o d e l i na d d i t i o n ，t h i sq cf r a m e w o r kp r e s e n t e daf e a t u r e e x p a n s i o nm e t h o dt o e n r i c ht h es e m a n t i c so fq u e r i e sa n dt a r g e t c a t e g o r i e s e x p e r i m e n t so nt h ek d d c u p 2 0 0 5d a t as e ts h o wt h a to u rq cf r a m e w o r kb a s e do n r c t mo u t p e r f o r m so t h e rb a s e l i n em e t h o d s 2 n a m e de n t i t ym i n i n g ( n e m ) f r o mq u e r yl o g s w ef u r t h e rs t u d i e dt h ep r o b l e mo fm i n i n gn a m e de n t i t i e sf r o mq u e r yl o g s s i n c e q u e r i e sa r eu s u a l l ys h o r t ( e g ，2 - 3w o r d s ) a n da m b i g u o u s ，t h em e t h o d si nn a m e d e n t i t yr e c o g n i t i o na n dc l a s s i f i c a t i o n ( n - e r c ) c a nn o tb ed i r e c t l ya n de f f e c t i v e l y a p p l i e dt om i n en a m e de n t i t i e sf r o mq u e r yl o g s a l lt h e s es t r o n g l yc h a l l e n g et h e r e s e a r c ho nm i n i n gn a m e de n t i t i e sf r o mq u e r yl o g s w ea t t e m p t e dw e a k l y - s u p e r v i s e d l e a r n i n ga n ds u p e r v i s e dl e a r n i n gm e t h o d st om i n en a m e de n t i t i e sf r o mq u e r yl o g s t h et w om e t h o d sa r ep r o p o s e df r o md i f f e r e n tm o d e l i n gm e t h o dt oa d d r e s st h e p r o b l e mo fm i n i n gn a m e de n t i t i e sf r o mq u e r yl o g s t h ee x p e r i m e n t a le v a l u a t i o n so n r e a lq u e r yl o g ss h o wt h a tt h et w om e t h o d sc a nm i n en a m e de n t i t i e se f f e c t i v e l yf r o m q u e r yl o g sa n dg r e a t l yo u t p e r f o r m so t h e rb a s e l i n em e t h o d s i i i a b s t r a c t 3 e n t i t yr e l a t i o nm i n i n g ( n e m ) f r o mw e b p a g e s d i f f e r e n tf r o m e n t i t yr e l a t i o ne x t r a c t i o ni nt e x t ，w es t u d i e dt h ep r o b l e mo f r e l a t e de n t i t yf i n d i n g ，w h i c hw a sp r o p o s e db yt r e c2 0 0 9e n t i t yt r a c k t h eo v e r a l l a i mo fr e l a t e de n t i t yf i n d i n g ( r e f ) i st op e r f o r me n t i t y - r e l a t e ds e a r c ho nw e bd a t a ， w h i c ha d d r e s sc o m m o ni n f o r m a t i o nn e e d st h a ta r en o tt h a tw e l lm o d e l e da sa dh o c d o c u m e n ts e a r c h t h em a i nc h a l l e n g e so fr e fa r eh o wt ob u i l da ne f f e c t i v e f r a m e w o r kt op r o c e s sh u g ed a t a s e ta n dh o wt om o d e lt h er e l a t i o nb e t w e e ne n t i t i e s i nt h i s p a p e r , an o v e lf r a m e w o r kw a sp r o p o s e db a s e do nap r o b a b i l i s t i cm o d e lf o r r e fi naw e bc o l l e c t i o n i nt h i sf r a m e w o r k ，ap r o b a b i l i s t i cm o d e lw a sb u i l tt om o d e l t h ee n t i t yr e l a t i o na n dr a n kc a n d i d a t ee n t i t i e s t h ee x p e r i m e n t a le v a l u a t i o n so n t r e c2 0 0 9e n t i t yt r a c kd a t a s e ts h o wt h ee f f e c t i v e n e s so fo u rr e ff r a m e w o r k b a s e do nt h ep r o b a b i l i s t i cm o d e l s i n c et h er e s e a r c ho nw e bi n f o r m a t i o nr e t r i e v a lo r i e n t e dk n o w l e d g em i n i n g b e g i n sv e r yr e c e n t l y , o u rw o r kp r o m o t e st h ed e v e l o p m e n to ft h i sr e s e a r c hf i e l d w h i l ei tn e e df u r t h e rs t u d yt oi m p r o v et h ep e r f o r m a n c eo fi ra n db u i l di rr e l a t e d s e r v i c eb a s e do nk n o w l e d g e m i n i n g k e yw o r d s ：i n f o r m a t i o nr e t r i e v a l ，q u e r yl o g ，q u e r yc l a s s i f i c a t i o n ，n a m e de n t i t y m i n i n g ，e n t i t yr e l a t i o nm i n i n g ，t o p i cm o d e l ，s e m a n t i ce x p a n s i o n ， k n o w l e d g em i n i n g , t r a n s f e rl e a r n i n g ,s u p e r v i s e dl e a r n i n g ， w e a k l y - s u p e r v i s e dl e a r n i n g i v 图目录 图目录 图1 1w e b 网站数目随时间增k 趋势图1 图1 2 搜索引擎系统简图2 图2 1 查询日志中“c l i c k t h r o u g hd a t a ”构成的二部图1 7 图2 2 查询会话，查询词和文档词2 0 图2 3 查询词和文档词概率关系图2 1 图3 1 基于中间分类目录的分类框架3 4 图3 2r c t m 的图模型。3 5 图3 3r c t m 变分推导示意图3 7 图3 4o d p 目录和目标目录示例4 0 图3 5 查询长度分布图4 1 图3 6 查询的标注数目分布图4 1 图3 7p e r p l e x i t y 随观测文本比例变化比较4 4 图4 1 基于修正关联话题模型的命名实体挖掘流样图5 2 图4 2w i k i p e d i a 文档示例。5 3 图4 3 基于转移学习的命名实体挖掘流程图5 5 图4 4 基于差异性的转移方法( d b 册订) 在各类别下的精确率随选取特征比例变化的 曲线。6 4 图4 5 基于差异性的转移方法( d b l m ) 在各类别下的f l 随选取特征比例变化的曲线 6 1 ； 图5 1 基于概率模型的关联实体查找框架7 1 图5 2 关联实体查找流科图7 7 图5 3t r e c2 0 0 9e n t i t y 任务参评方法的评价结果8 0 图5 4t r e c2 0 0 9e n t i t y 任务参评方法的评价结果( h pw p ) 8 0 v i i 表目录 表目录 表1 1 搜狗用户日志的组成3 表1 2 搜狗用户日志的示例3 表3 1 查询示例3 2 表3 2 人上标注的查询示例3 9 表3 3 不同w e b 搜索结果数目设置下查询分类性能4 3 表3 4 查询分类性能结果比较。4 3 表3 6 不同p 设置下h o t p 4 4 表3 5 各类别前1 0 的词比较4 5 表4 1 查询示例5 7 表4 2 目标类别以及相应种子命名实体5 8 表4 3 各类别下准确率p n 对比6 0 表4 4 各类别下前5 个查询模板对比6 0 表4 5 各方法的准确率6 3 表4 6 各方法的p r e c i s i o n ( p ) ，r e c a l l ( r ) 和f 1 6 3 表4 7 “p e r s o n ”类别下p t l 0 ，u 1 和c t l 0 对比6 5 表5 1t r e c2 0 0 9e n t i t y 任务参评方法的评价结果7 9 表5 2t r e c2 0 0 9e n t i t y 任务参评方法的评价结果( h p1 】y p ) 7 9 表5 3 基于单个话题的性能评价结果8 1 v i i i 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的 成果。除已特多l , j ) j n 以标注和致谢的地方外，论文中不包含任何他人已经发表或 撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作 了明确的说明。 作者签名：驰 签字日期：竺! 呈：圭：三垒 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学 拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构 送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入中 国学位论文全文数据库等有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内 容相一致。 保密的学位论文在解密后也遵守此规定。 l 圈公开口保密( 年) 名：弛 跏躲盟堡 签字日期：至! 止：竺：三兰 签字日期：型竺：! ：! ! ， 第1 章引言 1 1研究背景 第1 章引言 随着信息技术的快速发展，传统的纸质文档逐步被数字化，电子文档、数 字图片、数字视音频等等内容信息在互联网上急速膨胀。互联网网站数目也随 时间的推移呈指数级增长( 图1 1 ) ( z a k o n2 0 0 9 ) 。2 0 0 5 年底著名的搜索引擎 g o o g l e l 公布其索引规模已经达到了8 2 亿个网页。而据国内的搜索引擎百度2 公 布的数据，目前中文不重复网页数量已经超过6 0 亿。 图1 1w e b 网站数目随时间增长趋势图 随着互联网络上电子文档的急剧增长，互联网络成为人们获取知识的重要 来源。面对海量的文本信息，人们首先需要对其进行有效的存储管理，其次需 要从海量信息中快速获取自己所需信息。搜索引擎作为一种信息组织和访问的 有效工具应运而生。搜索引擎系统可以简单地划分为采集器、分析器、索引器、 搜索器和用户代理五大功能模块，其工作流程可以描述为( 图1 2 ) ：首先利用 采集器进行网页采集，并采用分析器对收集的网页进行分析抽取目标内容，同 时通过索引器对抽取内容建立索引进行存储，然后接受用户代理发送过来的查 询请求并转发到搜索器，最后搜索器通过计算网页和用户查询的相关度，返回 相关网页排序结果列表给用户。通常来说，搜索引擎是一种采用关键词技术对 w e b 信息进行组织和访问的工具，而用户搜索的过程，则是通过查询表达信息 需求来获取他们所感兴趣的信息的过程。目前，搜索引擎已经成为一种重要的 信息获取工具，为广大的互联网络用户所使用。 1 h t t p ：w w w g o o g l e t o m 2h t t p ：w w w b a i d u c o m 第1 章引言 图1 2 搜索引擎系统简蚓 一方面，在用户和搜索引擎交互的过程中，查询是用户表达其信息需求的 主要手段。在理想的情况下，搜索引擎能够正确地理解用户的查询，并在此基 础上采取合适的检索方式，返回相应的结果来满足用户的信息需求。然而就如 同计算机对自然语言的理解存在困难一样，查询作为用户与信息检索系统交互 的语言，检索系统对于查询的理解也同样面临巨大的挑战。尽管已有的信息检 索技术从一定程度上满足了用户的信息检索需求。但是用户查询通常都是基于 关键侧的、比较简短、不具有严格的语法特征，而且同一查询可能暗含不同的 用户信息需求等等，这些都极大的挑战着当前的检索技术。因此，通过从互联 网络数据中挖掘知识来改善w e b 信息检索的性能以及构建w e b 信息榆索相关服 务，更好地为互联网络用户提供服务成为当前的一个研究热点。 近年来，用户查询日志作为一种新型的互联网络数据资源在知识挖掘领域 得到了1 泛的研究。用户查询日志是大量用户长期使用搜索引擎产生的数据资 源，它记录了用户使用搜索引擎时的查询行为，并以结构化的数据格式进行存 储( 表1 1 和表l2 分别给出了搜狗3 用户查询日志的组成和示例) 。具体而言， 用户查询日志记录了用户向搜索引擎提交查询、浏览和点击返回结果等等一系 列行为，其巾蕴含了丰富的知识。例如，通过分析用户查询日志，我们可以了 解用户在搜索些什么内容、用户是如何搜索的、用户对哪些w e b 页面感若趣、 用户鸯询的话题足怎么随时口j 变化的等等。由此可见，查询n 志作为一种群体 查询活动的记录，是一种大众智慧( t h ew is d o mo fc r o w d s ) 的体现。 此外，用户查询日志和传统的w e b 数掘有着很大的区别。一方面，用户查 询h 志不再是由少量的专业编辑人员发靠的数据，而是由大量的普通用户进行 查询时产生的数据。据报告，到2 0 0 5 年底，已有近8 91 互联网用户使用过搜 h m w ”g o “c o r n 第1 章引言 索引擎业务。这些互联网络用户来自社会的各行各业，往往具有不同的知识背 景、兴趣爱好和信息需求。另一方面，由于大量用户广泛使用搜索引擎，搜索 引擎己然成为新一代的互联网络门户。目前主流的搜索引擎每个月的查询同志 数据已经达到t b 规模。相对于传统的由编辑人员发布w e b 数据的方式，用户创 造数据所需要的代价要小得多，这使得数据产生的速度有了大幅的提升。 综上所述，用户查询r 志是一类海量的蕴含大众智慧的互联网络数据资源， 它已经成为了信息检索、数据挖掘、机器学习和自然语言处理等领域重要的研 究资源。从用户查询日志挖掘知识来改善w e b 信息检索的性能以及构建w e b 信 息检索相关服务成为近年来广大研究人员研究的热点，也是本文研究工作的主 要研究对象。 表1 1 搜狗用户日志的组成 名称记录内容 u s e r l d 由系统自动分配的用户标识号 查询用户提交的奄询 排名该u r 陇返同结果中的排名 用户点击的顺序号，这是用户点击的第 点击序号 几个页面 点击链接用户点击的链接 点击时间用户点击发生的时间 表1 2 搜狗用户日志的示例 u s e r l d查询捧名 点击序号 点击链接时间 湖南卫 4 1 4 4 9 9 9 9 6 3 5 1 9 6 6 6 11w w w h u n a n t v c o m l o ：1 1 视 0 2 4 3 9 5 0 0 3 5 3 9 7 2 5 8 4 6 人民网 11 w w w p e o p l e t o m c n 1 i ：2 7 哈利波 8 3 1 9 8 9 7 4 3 5 2 9 6 1 6 6 7 1 w w w m y 2 8 5 c o m c x s j h l b t 6 1 6 ：0 5 特6 木马克 9 1 1 0 4 6 3 8 8 5 6 6 9 8 1 5 7 2w w w i t c o m c n f h o t w e b 0 5 3 3 1 9 4 2 1 2 h t m 2 1 ：4 4 星 另一方面，在传统的信息检索系统中，对用户提交的基于关键词的查询， 系统返回一个文档结果列表给用户，用户通过浏览结果列表中的部分网页来获 取其所需信息。然而，现实中用户的信息需求非常的多样化，用户往往很难通 过简单的几个关键词来准确地描述其信息需求，并且文档列表的结果返回方式 要求用户浏览大量的网页来获取所需信息，这些都极大地挑战着当前的信息检 索技术。例如，用户想知道犹他州的国家公园在哪里( w h e r ei st h en a t i o n a l 3 第1 章引言 p a r ki nu t a h ? ) ，他( 她) 可能会向搜索引擎提交查询“u t a hn a t i o n a lp a r k 。 然而传统的搜索引擎只是进行文档检索，它返回给用户相关文档而非直接相关 的信息。用户仍然需要在搜索引擎返回的相关文档中寻找问题的答案( 游斓等， 2 0 0 5 ) 。 问答系统( q u e s t i o na n s w e r i n gs y s t e m ，q a ) 是真正意义上的信息检索系统， 它能够精确地回答用户用自然语言。提出的问题，并以信息点而不是相关文档作 为返回结果( 许洪波2 0 0 3 ) 。简单来说，q a 系统的目标就是要为问题找到准确 的答案。在q a 系统中，对用户用自然语言提出的问题，系统将会在庞大的语料 库中找到这个问题的若干个答案，然后依据某种算法对所有的答案进行打分，并 将最好的答案反馈给用户。早在1 9 6 1 年，g r e e n 等人( g r e e ne ta 1 1 9 8 6 ) 就 开发了第一个q a 系统，来回答当季美国职业棒球大联盟比赛的相关问题。近年 来，互联网络的快速发展推动了问答系统的广泛研究。当f j 主流的q a 系统采用 基于关键词的技术或基于问题形式化的技术。具体来说，基于关键词技术的q a 系统的流程是：首先从用户提交的问题中提取关键词构造查询，并采用传统的 文档检索技术获取关联文档集合；然后通过关键词技术从关联文档中找到候选 段落或句子，并根据预期答案的类型来过滤候选文本；最后基于候选文本与用 户查询的相似度来排序候选文本，并返回结果给用户。基于问题形式化的q a 系 统则是对特定的问题通过制定相应的匹配规则来抽取答案。然而，已有的关键 词技术和问题形式化技术远远不能满足q a 的性能需求。近年来，大量的研究工 作开始尝试引入数据挖掘、机器学习和自然语言处理等方面的技术来解决q a 中 的问题，而实体关系挖掘作为其中的一项关键技术，在q a 系统中得到了广泛研 究和应用。 此外，近年来随着互联网的快速发展，互联网上的文本信息急剧增长，从 文本中自动挖掘知识的技术受到广泛关注。实体关系挖掘是文本知识挖掘中最 普遍的任务之一。以此技术为基础构建的系列新型互联网络信息服务受到广 大互联网络用户的青睐，例如人立方4 。人立方是微软公司面向广大互联网络用 户完全免费提供的一个关系搜索的网站，它从大规模的中文网页中自动地抽取 出人名、地名、机构名以及中文短语，并且通过算法自动地计算出它们之问存 在关系的可能性，同时还自动地找出人名之间最可能的关系描述词、与人名最 可能相关的称呼、作品等词条。实体关系挖掘是构建这类新型网络信息服务的 关键技术( z h ue ta 1 2 0 0 9 ) 。 由此可见，实体关系挖掘已然成为解决信息检索问题的关键技术，同时以 实体关系挖掘为基础构建新型互联网络信息服务也得到了广泛的关注。总而言 4 h t t p ：r e n l f f a n g i n s r a c n 4 第1 章引言 之，实体关系挖掘作为知识挖掘任务中的一个重要研究课题，它与信息检索、 问答系统、信息浏览和信息过滤等领域的研究紧密相联，同时对自动文摘、机 器翻译、内容理解、语境生成、文本分类和聚类等领域的研究都具有十分重要 的意义( 何婷婷等，2 0 0 6 ) 。正因如此，实体关系挖掘的研究已经成为自然语 言处理和相关领域的研究热点，也是本文研究工作的主要研究对象。 1 2 研究现状 本文面向w e b 信息检索的知识挖掘研究工作主要包括三个方面的内容：基 于用户查询日志的查询分类、基于用户查询同志的命名实体挖掘和基于w e b 的 实体关系挖掘。其中基于用户查询日志的查询分类和基于用户查询日志的命名 实体挖掘两个研究工作是基于用户查询日志展丌的，这里首先对基于用户查询 日志的研究现状进行概述，随后对基于w e b 的实体关系挖掘的研究现状进行了 概述，相关研究所采用的具体技术和算法将在第二章的相关工作中进行详细介 绍。 用户查询日志作为一种新型的互联网络数据资源在信息检索领域得到了广 泛的研究，这些研究工作主要面向通用搜索引擎的同志数据展开，这些日志资 源主要包括英文的y a h 0 0 5 、g o o g l e 、l i v es e a r c h 6 、a l t a v i s t a 7 、e x c i t e 8 、a o l 9 、 v i v i s i m 0 1 0 等和中文的“搜狗”、“天网1 1 等的查询日志。迄今为止，很多大学、 科研机构以及著名的i t 企业都展开了对查询日志的分析与研究。著名的搜索引 擎如y a h o o 、m i c r o s o f t 、g o o g l e 以及国内的百度、搜狗、腾讯1 2 等都投入了大 量的人力物力，致力于开展对查询同志的分析与研究，来改善他们提供的检索 服务。同时，很多科研机构和大学也通过与i t 企业的合作，投入到查询日志的 研究中来，其中包括卡内基梅隆大学( c m u ) 、宾夕法尼亚州立大学( p s u ) 、加 州大学洛杉矶分校( u c l a ) 、麻省大学( u m a s s ) 、北德州大学( n o r t ht e x a s u n i v e r s i t y ) 、清华大学、中国科学技术大学、中国科学院计算技术研究所、北 京大学、上海交通大学、南开大学等等。此外，国内外一些重要的学术会议如 国际万维网会议( t h ei n t e r n a t i o n a lc o n f e r e n c eo fw o r l dw i d ew e b ) 、国际 信息检索大会( s i g i r ) 、k d d ( k n o w l e d g eo i s c o v e r ya n dd a t am i n i n g ) 、c i l ( m h t t p ：w w w y a h o o c o m h t t p ：w w w 1 i v e c o r n h t t p ：w w w a l t a v i s t a c o r n h t t p ：w w w e x c i t e c o i n h t t p ：w w w a 0 1 c o r n h t t p ：v i v i s i m o c o n y h t t p ：w w w t i a n w a n g c o l n h t t p ：w w w s o s o c o m 5 第1 章引言 ( c o n f e r e n c eo ni n f o r m a t i o na n dk n o w l e d g em a n a g e m e n t ) 和国内的全国信 息检索学术会议、计算语言学学术会议等都开辟了专门的s e s s i o n 致力于推动 这方面的研究。 早期对于查询同志的研究主要关注数据本身的一些基本分析，这些工作主 要是统计分析查询的分布和用词特点，来帮助搜索引擎更好地制定检索和缓存 策略，或通过分析和挖掘用户搜索行为的特点，来改进搜索策略提高用户的查 询体验等等。早在1 9 9 8 年，j a n s e n 、s p i n k 等人首先针对e x c i t e 查询日志开 展了一系列的研究工作( j a n s e ne ta 1 1 9 9 8 ：j a n s e ne ta 1 2 0 0 0 ：s p i n ke t a 1 2 0 0 1 ：s p i n ka n do z m u l t u2 0 0 2 ) 。他们的工作主要包括分析用户查询的分 布、查询的用词特点、用户查询的话题等等。通过这些工作，人们对于用户的 日常查询行为有了初步的认识。 随后，基于查询同志的研究工作得到迅速扩展，研究内容也越加丰富，这 些研究工作主要包括：基于查询日志进行查询分类，目的是深入分析用户的查 询意图；面向查询同志的数据挖掘，目的是从查询日志中获取所需知识；基于 查询日志进行查询推荐，是为了提高w e b 搜索的效率和用户的查询体验；基于 查询同志进行查询扩展，目的是进一步提高检索的相关性；基于查询同志进行 查询优化，是为了解决查询与目标文档的词不匹配问题；利用查询同志优化排 序算法，则是为了提高检索结果的相关度。由此可见，用户查询日志极大地推 动了信息检索领域的研究工作，同时也开拓了很多新的研究方向。特别是近几 年，随着搜索技术需求的提高和研究的深入，利用用户查询日志来改善搜索性 能和提供相关服务成为研究热点，相关研究工作层出不穷。当前基于用户查询 同志的研究和相关应用的成功，充分验证了查询日志在解决检索领域相关问题 中的重要意义。 随着互联网络的迅猛发展，互联网上的文本信息急剧增长，人类面对信息 极大丰富而知识相对匮乏的问题，从文本中自动挖掘知识的技术越来越被关注。 具体来说，知识挖掘的目标是从特定领域的文本文档中识别预定义类型的知识 要素，并将它们以结构化形式进行存储。知识挖掘任务在挖掘目标、底层算法 和所采用的工具上各有不同，但通常都包含两个普遍存在并且密切关联的子任 务：实体识别和关系抽取( 徐健等，2 0 0 8 ) 。 关系抽取任务是由美国国防高级研究计划委员会( d e f e n s ea d v a n c e d r e s e a r c hp r o j e c t sa g e n c y ) 资助的消息理解大会( m e s s a g eu n d e r s t a n d i n g c o n f e r e n c e ，m u c ) 首先提出1 3 。m u c 会议对关系抽取这一研究方向的确立和发 展起到了巨大的推动作用，它制定了实体关系抽取任务的各种规范并给出了相 ”h t t p ：w w w i t l n i s t g o v i a u i 8 9 4 0 2 r e l a t e d _ p r o j e c t s r o u t 6 第1 章引言 应的评价体系。在m u c 之后，美国国家标准技术研究院( n i s t ) 组织的自动内容 抽取( a u t o m a t i cc o n t e n te x t r a c t i o n ，a c e ) h 评测也加入了实体关系识别任 务。在m u c 和a c e 的促进下，关系抽取技术取得了较大进步，研究热点从早期 应用简单的基于语言学规则发展到使用自然语言处理技术和机器学习方法来解 决关系抽取的问题，同时关系抽取性能也取得了大幅提升( 徐健等，2 0 0 8 ) 。 同时，国内外的大学和研究机构以及著名的i t 企业，都积极进行实体关系 抽取的研究和开发工作。著名的国外企业如g o o g l e 、y a h o o 、m i c r o s o f t 、i n t e l 、 i b m 等都投入了大量人力物力致力于开展实体关系抽取的研究，来改善w e b 搜 索和构建新型的信息检索服务，其中m i c r o s o f t 推出的人立方受到互联网络用 户的广泛青睐。此外，很多科研机构和大学相继投入到实体关系抽取的研究中 来，其中包括国外著名的斯坦福大学( s u ) 、麻省理工学院( m i t ) 、宾夕法尼亚 州立大学( p s u ) 、宾夕法尼亚大学( u p e n n ) 等等。国内关于实体关系抽取的研 究起步较晚，i n t e l 中国研究中心在2 0 0 0 年参加了a c l 会议，并展示了他们开 发的一个抽取中文命名实体以及实体问关系的信息抽取系统( z h a n ga n dz h o u 2 0 0 0 ) 。近年来，中国科学院计算技术研究所、哈尔滨工业大学、清华大学、上 海交通大学等研究团队陆续开始这方面的研究，为这个领域的快速发展做出了 巨大贡献。 1 3 本文的工作 1 3 1研究内容和目标 本文以提高w e b 信息检索的性能和构建w e b 信息检索相关服务为目标，基 于用户查询日志和w e b 两类大规模互联网络数据开展了知识挖掘的研究。其中 包括基于用户查询日志的查询分类、基于用户查询r 志的命名实体挖掘和基于 w e b 的实体关系挖掘三个方面的研究内容，针对每个具体的问题，文中进行了 深入分析并给出了相应的解决方案和算法。具体内容如下： 1 基于用户查询日志的查询分类 查询分类研究的目标是通过自动化方法根据用户查询的话题将其分类到一 个或多个预先给定的类别，从而识别出用户的查询意图来提高w e b 检索的性能 或构建w e b 检索的相关应用，比如个性化检索、垂直搜索、在线广告等。然而 由于查询通常都很简短( 2 - 3 个词) 、语义很模糊，并且目标分类体系是按具体 7 第1 章引言 需求的不同而随时制定的，此外该任务没有提供训练数据，这些都极大地挑战 查询分类的研究。已有研究没能很好地处理这些问题，性能和实用性上都存在 缺陷。我们提出了基于概率话题模型的查询分类框架可以很好地解决上述问题， 并且具有优越的分类性能。 2 基于用户查询同志的命名实体挖掘 我们基于用户查询同志展开了查询中命名实体挖掘的研究。已有研究通过 分析用户查询日志发现，大约有7 1 的用户查