（计算机应用技术专业论文）专家搜索中基于实体相关性的排序优化问题研究.pdf

摘要 摘要 专家搜索是信息检索的重要研究内容之一，属于实体搜索的范畴。目前实 体搜索的研究内容更多关注于实体抽取和排序算法的探索和改进，对实体相关 性的研究也多关注于相关性本身，如实体关系抽取等，没有进一步探讨这种相 关性对专家搜索排序的影响。 专家搜索中发现专家实体之间的相关性，并把这种相关性用于排序结果优 化是一个重要的研究内容。针对上述问题，本文提出了基于实体相关性的排序 优化问题。主要工作包括： ( 1 ) 定义实体向量空间模型，构造专家实体相关性挖掘模型。指出专家实体 所具有的相关性度量量，针对不同的相关性度量量选取不同挖掘算法。 由于不同挖掘算法之间具有相对独立性，进一步把针对不同特征的挖掘 算法线性组合，计算专家实体相关性度量值。 ( 2 ) 根据专家实体相关度矩阵，建立实体关系图。图的每个节点为专家实体， 图的边为实体相关度值。在此基础上定义有效实体关系图及三类关系。 三类关系包括：紧密联系、有联系、无联系。只有紧密联系或有联系的 节点才能提供有效的专家实体相关信息。 ( 3 )定义激活节点，定义优化调整规则。激活节点的选取来自两种调整优化 模型，一种是返回结果集的前n 个节点做为激活节点；另一种选择有效 实体关系图前n 个节点为激活节点，当返回结果中有与激活节点联系的 节点，则触发优化调整规则。 ， 在标准数据集上的实验结果表明，基于实体相关性的排序优化模型对提高 排序结果具有很好的作用，平均准率提高6 2 6 ，b p r e f 提高9 7 1 。 关键词：专家搜索实体实体关系图排序优化实体关系抽取 a b s t r a c t a b s t r a c t e x p e r t s e a r c hi so n eo ft h em o s ti m p o r t a n ts u b j e c t sf o rr e s e a r c ho nt h e i n f o r m a t i o nr e t r i e v a l i tb e l o n g st ot h ee n t i t ys e a r c hc a t e g o r y h o w e v e r , p r e v i o u s w o r k su s u a l l yp a ym o r ea t t e n t i o nt ot h ee n t i t ye x t r a c t i o na n dr a n k i n ga l g o r i t h m so f e x p e r ts e a r c h , a n dt h er e s e a r c ho fe n t i t yr e l a t i o n sm a i n l yf o c u s e so i lt h er e l a t i o n s h i p i t s e l f , s u c ha se n t i t ye x t r a c t i o n , i g n o r i n gt h ei n f l u e n c eo fa s s o c i a t i v er e l a t i o n s h i p si n r a n k i n go ne x p e r ts e a r c h i t i sa l le s s e n t i a lt o p i ct h a tf i n d i n gt h ea s s o c i a t i v er e l a t i o n sb e t w e e ne x p e r t e n t i t i e si ne x p e r ts e a r c ha n du s i n gi tt oi m p r o v et h er a n k i n gr e s u l t s i nt h el i g h to ft h e p r o b l e m sm e n t i o n e da b o v e ，t h i sp a p e rp r o p o s e sar a n k i n go p t i m i z a t i o nm o d e lb a s e d o ne n t i t yr e l a t i o n s t h em a i nw o r ki n c l u d e st h ef o l l o w i n g ： ( 1 ) w ep r o p o s et h ee n t i t yv e c t o rm o d e l ( e v m ) ，c o n s t r u c tt h em i n i n gm o d e lo f e x p e r tr e l a t i o n sa n dp o i n to u ta l lt h ef e a t u r e so ft h er e l a t i o n s b e c a u s eo ft h e i n d e p e n d e n c eo ft h ed i f f e r e n td a t am i n i n ga l g o r i t h m s ，w el i n e a r l yc o m b i n et h e a l g o r i t h m sa n dc a l c u l a t et h ev a l u ew h i c hr e p r e s e n t st h er e l a t i o n sb e t w e e ne x p e r t e n t i t i e s ( 2 ) w ee s t a b l i s ht h ee n t i t yr e l a t i o n sd i a g r a mb a s e do nt h ee n t i t yr e l a t i o n sd e g r e e m a t r i x e a c hn o d eo ft h ed i a g r a mi sa ne n t i t y , t h ev a l u e so ft h ee d g e se q u a l t o t h o s eo fe n t i t yr e l a t i o n s b a s e do nt h i s ，w ed e f i n et h ev a l i de n t i t yr e l a t i o n s d i a g r a ma n dt h et h r e ek i n d so fr e l a t i o n sc o n s i s t i n go fc l o s e - r e l a t i o n , r e l a t i o n , n o r e l a t i o n o n l yt h ef i r s tt w ot y p e so fr e l a t i o n sc o u l dp r o v i d eu s e f u lr e l a t i o n s i n f o r m a t i o n ( 3 1w ed e f i n et h ea c t i v a t e dn o d e s t h ea c t i v a t e dn o d e sa r ed i f f e r e n ti nt h et w o t y p e so fa d j u s t i n gm o d e l s t h ef i r s tm o d e ld i r e c t l yu s e st h ef i r s tn n o d e sa s a c t i v a t e dn o d e sw h i c hc o m ef r o mt h er e t r i e v a lr e s u l t s t h es e c o n dm o d e l r c t q l r l l st h et o pnn o d e sf r o mt h ee n t i t yr e l a t i o n sd i a g r a m i ft h e r ea r es o m e n o d e sw h i c hh a v er e l a t i o n s h i pw i t ha c t i v a t en o d e s ，t h eo p t i m i z i n gr u l e sa r e t r i g g e r e d o u re x p e r i m e n t sb a s e do l lt h es t a n d a r dd a t a s e t ss h o wt h a tt h er a n k i n g o p t i m i z a t i o nm o d e lb a s e do ne n t i t yr e l a t i o n sf o re x p e r ts e a r c hp l a y s ag r e a tr o l ei n i m p r o v i n gt h er a n k i n g r e s u l t s t h em e a na v e r a g ep r e c i s i o ni si n c r e a s e db y6 2 6 a n dt h eb p r e f i si n c r e a s e db y9 7 1 k e yw o r d s ：e x p e r ts e a r c h , e n t i t y , r a n k i n go p t i m i z a t i o n ，e n t i t yr e l a t i o ne x t r a c t i o n m 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名： 年月日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月日 各密级的最长保密年限及书写格式规定如下： 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名： 年月日 第一章绪论 第一章绪论 1 1 引言 过去2 0 年，信息检索领域已经得到了发展和壮大，并且超越了它标引文本 和在某一文档集合中检索出有用文档的最初目标。特别是2 0 世纪9 0 年代，互 联网的发展，彻底改变了人们对信息检索的看法。互联网正在成为人类知识和 文明的全球存储库，这个存储库允许在一个广大范围内实现思想和信息的共享。 越来越多的人通过互联网获得帮助，不断扩张的用户群也带来了新的问题， 拥有不同的背景、兴趣的用户不再仅仅是希望通过互联网获取所关心领域的信 息，同时也希望获知这一领域的权威专家列表。调查显示相比访问某个与查询 非常相关的主题的所有文档而言，用户更期望能与一个在这一领域掌握权威知 识的学者联系n 3 。如何帮助用户通过互联网获得某一领域内的相关专家信息， 成为非常有意义，同时很有挑战性的工作。 专家搜索能帮助用户实现这一需求。专家搜索是给定一个主题或领域，搜索 在这一主题或研究领域内的专家，专家搜索是实体搜索的一种。实体搜索不再 把搜索对象看作网页的集合，而是看作实体的集合，实体搜索中每个网页都是 由一系列的实体组成，如人物、机构、产品等。对专家搜索而言，即为实体类 型是人物( 姓名) 的实体搜索。专家搜索针对用户给定的查询关键字搜索并返 的专家姓名列表集合，专家姓名列表按照与查询关键字的相关程度由高到低排 列。 相比使用通用搜索引擎获取某领域内的专家信息，专家搜索的优点显而易 见。通用搜索引擎返回大量文档需要用户甄别哪些网页中含有相关的专家信息， 而专家搜索返回的专家列表使结果更单一，信息更纵深，更便于用户浏览。专 家搜索不仅可以帮助专业科研人员通过互联网找出所感兴趣领域的专家，也可 以帮助普通用户获得所关心领域的“名人 信息。对专家搜索问题进行深入研 究，建立一个高效的、能客观反映某领域内专家排名的排序模型，会为人们的 学习、交流、科学研究等社会活动带来极大的方便。 第一章绪论 1 2 专家搜索概述 随着信息技术的进步和发展，用户希望借助互联网获取某一领域内所需的 精准信息，专家搜索就是其中需求之一。获知某一领域或某一领域下任何分支 领域内的专家是非常有应用价值的。对于学术研究者，通过了解所在领域内专 家的最新研究成果可以获知最前沿的研究动态；对信息求助者，如医学领域， 可以寻找最权威的医学专家的帮助；而对企业用户，专家搜索可以作为产品决 策和开发的辅助工具，分析重要商业人物动态。这些用户需求推动了专家搜索 研究的发展。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 ) 即文本检索会议从2 0 0 5 年开始 发布专家搜索的任务，专家搜索是信息检索的重要研究内容之一。 1 2 1专家搜索应用背景 信息检索领域已经有科研和商业机构就全文检索做了很多研究工作，并取 得和很好的成果。例如g o o g l e 的全文检索搜索引擎，可以帮助用户在浩瀚的数 字世界中获得想要的信息。但是，但随着搜索服务用户群和互联网网页数量的迅 速增多，新的问题随之产生。截至2 0 0 5 年1 月份，全球网页数量已逾1 1 5 亿之 多瞳1 ，同时网页的增长速度更是惊人，美国从事因特网监测的网器公司2 0 0 8 年 3 月2 8 日宣布，截止2 0 0 8 年2 月底，全球互联网网站数量超过1 6 亿，达 1 6 2 6 6 2 0 5 3 ，较一个月前增加了4 5 0 万，平均每天新增网页超过1 0 0 万口1 。2 0 0 8 年3 月在g o o g l e 上输入“金融领域专家得到9 6 2 ，0 0 0 个相关网页，输入“数 据挖掘领域专家得到2 ，7 7 0 ，0 0 0 个相关网页，输入“成龙得到1 1 ，9 0 0 ，0 0 0 个相关网页，庞大的网页列表超过了人们可以浏览的限度，用户常常没有耐心 和精力从这些众多可能相关的网页中找出自己需要的某一领域的特殊信息，也 无从快速判断自己需要的信息是否包含在检索结果中。此外，通用搜索引擎( 如： g o o g l e ) 一般把满足用户查询需求的权威网页排在前面，但是权威网页不一定 是用户所需要的网页，也许是用户已经浏览过的网页或是久未更新的网页。网 页基数的不断扩大和用户各种喜好和搜索需求的增多使得通用搜索服务的品质 在下降，无法满足用户的个性化需求。 海量数据的出现要求信息检索技术不断改进，目前的趋势是从互联网的海 量信息中抽取实际可操作的规律，并据此计算查询和网页的相关度。网页检索 中检索结果的好坏主要取决于搜索引擎对“查询 结果的响应。现有的信息检 2 第一章绪论 索技术以网页级别来检索数据，无法对应一个多样的查询而返回一个准确的结 果，因而研究“实体 级别的对象来解决这一问题。实体搜索把网页对象从纵 向分割为不同类型的实体，对非结构化的网页数据做了进一步的纵深结构化分 析和处理。相对全文检索获得的“s u r f a c ew e b ”信息而言，实体搜索被认为能够获 取互联网上的 d e e pw e b 信息口1 。 专家搜索作为实体搜索的重要研究内容之一逐渐被研究者所重视。专家搜 索最初的应用是在大型企业内部帮助人们通过网络寻找企业内部某一领域的专 家。随着互联网的发展，专家搜索应用范围专家扩大到在互联网范围内寻找相 关领域的专家，同时应用系统也不再仅仅为技术人员服务，如由s p o c k c o m 提供 的人物搜索服务面向所有用户服务。当用户输入一些常见的搜索字符，比如“博 客 、“演员 甚至具体名字时，网站将能够提供相关人物的搜索数据。 1 2 2 专家搜索研究的主要问题 专家搜索是实体级别信息检索，与文档级别信息检索的区别在于专家搜索 对数据进行预先抽取和处理，经过处理的数据提交给索引器做索引。专家实体 ( 专家姓名) 作为不可再分的整体提交给索引器进行索引。例如：在索引形如 “t o m 硒n g 这样的专家名字时，“n g ”不作为单独的单词处理，“t o mk i n g ” 整个被索引为一个词，此时专家实体与关键字具有同样的索引级别。 专家搜索主要研究工作集中在命名试题抽取和排序模型研究这两个方面， 以下分别介绍这两方面内容。 ( 1 ) 命名实体抽取 实体( e n t i t y ) 是指独立存在的事物。每个实体都具有各自的特征表现，即 不同的实体具有特定的属性，并且可以由此区别于其它的实体。实体名称往往 表示物种，同其它具有概括性质的名词一样。一般来说，人们为每个实体指定 一个名字，实体因此也称命名实体( n a m e de n t i t y , n e ) 任何具体或抽象的事物 都可以称为实体，命名实体( n a m e de n t i t y ) 包括实体( 组织名、人名、地名) 、时 间表达式( 日期、时间) 、数字表达式( 货币值、百分数) 等。针对网页信息的灵 活性和多样性，可以将用户感兴趣的目标定义为实体，例如网页中出现的人物、 机构单位、企业公司、产品、书籍等等都可以定义为实体，进而将含有实体 信息的网页称为实体网页。命名实体抽取包括命名实体识别和命名实体关系抽 3 第一章绪论 取等内容。 命名实体识别最初是在m u c 一6 ( 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 ) 上作为一 个子任务提出的。命名实体( n a m e de n t i t i e s ) 识别任务主要是要识别出文本中 出现的专有名称和有意义的短语并加以归类。 评判一个命名实体是否被正确识别包括两个方面评判标准：一是实体的边 界是否正确，二是实体的类型是否标注正确。前者称之为文本，后者称之为类 型，由此可知文本正确，类型可能错误，反之，文本边晃错误，而其包含了主 要实体词且词类标记可能正确。因此对一个实体识别正确性的定义不是简单的 划分，不同的系统侧重点不同，对其定义也可能不一样。但一个命名实体的识 别系统的识别结果是确定的，有如下三种结果： ( 1 ) 正确( c o r r e c t ) ：系统识别结果和已标注结果相同； ( 2 ) 丢失( m i s s i n g ) ：系统没能识别出已标注的结果； ( 3 ) 错误( e 1 t o i ) ：系统识别的结果不在已经标注的结果之中。 与大多数自然语言处理技术一样，命名实体识别的方法主要分为两大类：基 于规贝1 j ( r u l e - b a s e d ) 的方法和基于统计( s t a t i s t i c - b a s e d ) 的方法。 较早的命名实体 识别方法多采用构造有限状态机的方法，以模式和字符串相匹配。目前应用的 典型系统有用于英语命名实体识别的谢菲尔德大学的l a s i e i i 系统h 1 ，爱丁堡大 学的l t g 系统啼1 ，这些系统主要是采用基于规则的方法。基于规则的方法虽然相 对简单，但缺乏鲁棒性和可移植性，对于每个新领域的文本都需要更新规则来 保持最优性能，而这需要大量的专门知识和人力，代价往往非常大。而基于统 计的方法主要有隐马尔可夫模型( h m m ，h i d d e nm a r k o vm o d e l ) 方法，最大熵 模型( m e ，m a x i m u me n t r o p y ) 方法，决策树方法等等。在对这些方法的评价 中，h m m 的性能是普遍认为比较好的，主要原因是它能较好地捕获命名实体的特 征现象和位置，而且由于经典的v i t e r b i 算法在求取最佳状态序列的高效性，使得 h m m 在该领域中的应用越来越频繁。h m m 也存在缺点，由于其能利用的信息比较 少，因而对复杂命名实体( 由多个词组成的命名实体，如机构名) 的识别效果 并不理想。 虽然基于统计的方法有很多成功之处，但是基于统计的方法获取的概率知 识总是赶不上人类专家的专业知识可靠。基于规则的方法的命名识别方法中规 则知识的获取来自于专家的经验，因此基于统计系统的性能要比基于规则的系 统性能偏低。 4 第一章绪论 实体关系e r ( e n t i t yr e l a t i o n s ) 识别同样是在1 9 9 5 年m u c 会议上首次提出， 实体关系识别的目标是从文本中找到两命名实体间的语义关系，提取命名实体 之间的重要关系( 事实) ，如人名与职务、机构与处所等。例如，若文本中存 在句子，“倒排文档是一种面向单词的标引机制，则通过命名实体语义关系 抽取，得到三元组( 倒排文档，单词，标引机制) ，其中“倒排文档为命名实体 1 ，“单词”为命名实体2 ，“标引机制”为命名实体l 与命名实体2 间的语义关系。 命名实体抽取是目前信息提取中最有实用价值的一项技术。信息处理中对 命名实体识别的技术主要集中在人名、地名、机构名等的识别研究上，其中就 识别的准确率而言，人名最高，地名次之，机构名更次之，原因是不同实体名 称构成规律的可操作程度不同。1 9 9 6 年计算语言学会议的一份研究报告阳3 给出对 中国人名、地名和机构名提取的准确率和召回率分别是( 8 8 0 4 ，9 2 5 6 ) 、 ( 5 0 6 2 ，7 1 9 3 ) 和( 6 1 7 9 ，5 4 5 0 ) 。 本文研究中应用的命名实体识别技术主要是对人名的处理，处理对象是英 文人名。英文人名相比较中文人名的显著特点是有明显的形态变化，行文之间 或者有自然的词的分割或形态标记，如：d z h a n g 或w r i t t e nb yd a nz h a n g 及 空格分割等形态，这些特点使英文人名的识别相对较容易，但是英文人名的一 些结构变化使得人名识别相比中文的结构复杂，英文人名通常有如下复杂之处： 全名缩写。与中国人的习惯不同，英语姓名的一般结构为：教名+ 自取 名+ 姓，但在很多场合中问名往往略去不写。如：g e o r g eb u s h ( 乔治布什) ， 他的姓名全称是g e o r g ew a l k e rb u s h ，也可写为g e o r g e w b u s h 。 昵称派生。呢称包括爱称、略称和小名，是英语民族亲朋好友间常来表 示亲切的称呼，是在教名的基础上派生出来的，英语中许多人习惯用昵称 取代教名。复杂的昵称使得一个同一个人名可能有不同的表现形式。如人 们所熟知的微软创始人比尔盖茨的全名是w i l l i a mh e n r yg a t e s ，也可写做 w ：i l l i 锄h g a t e s ，但我们在各种媒体信息中通常知道的是b i l lg a t e s ，因为 b i l l 是教名w i l l i a m 的昵称，b i l lg a t e s 更符合美国人称呼的习惯。昵称的派 生通常常有如下情况： ( 1 ) 保留首音节，如：d o n a l d = d o n , t i m o t h y = t i m 。如果本名以 元音开头，则可派生出以n 打头的昵称，如：e d w a r d = n e d ； ( 2 ) + i e 或- yj t l - d o n = d o n n i e ，t i m = t i m m y ； ( 3 ) 采用尾音节，如：a n t h o n y = t o n y , b e u b e n - b e n ； 5 第一章绪论 ( 4 ) 由一个教名派生出两个昵称，如：a n d r e w = a n d y & d r e w ； ( 5 ) 不规则派生法，如：w i l l i a m 的一个昵称是b i l l 。 缩写规则不同。英国人习惯上将教名和中间名全部缩写，如a r t h u r a l e x a n d e r w a r d 英国人缩写为a a w a r d ；美国人则习惯于只缩写中间名， 如a r t h u r a l e x a n d e r w a r d 美国人缩写为a r t h u r a w a r d 。 不同文化和习俗的人英文名字的命名规则不同。由于文化和习俗的差 异，人们在使用英文名字时会造成的英文名字差异。如传统的中国人习惯 按照姓在前，名在后的方法翻译自己的英文名字，则吴珊翻译为w us h a n ， 而这个人如果是中国香港人，由于接受了西方文化的一些观念，那么她的 名字可能翻译成s a n d yw u 或s h a nw u 。 ( 2 ) 专家搜索排序模型 排序问题是专家搜索研究的另一个重要内容，专家搜索虽然与全文检索一 样，是以“相似度“计算作为排序的标准，但由于对象的不同，为实体级别， 因而排序模型与全文检索差异很大。专家搜索度量“相似度”的标准是用户输 入的查询与专家命名实体的匹配程度。专家搜索目前的常用排序模型采用两步 语言模型，理论依据在给定查询q 的前提下搜索与q 相关的特定实体e 的问题可 以被定义为估计q 产生每一个实体e 的概率，则依贝叶斯全概率公式得公式1 1 。 从公式1 1 n 知，求解p ( eg ) 的问题，可以被分解为分别求解p ( dg ) 和p ( eid ，g ) 的问题。 p ( e g ) = ：p ( d i q ) p ( e l d ，g ) ( 1 1 ) 了 专家搜索的两步语言模型如图1 1 所示，图中q u e r y 表示用户输入的查询； d o c l ，d o c 2 ，d o c n 表示一系列文档；e l ，e 2 表示专家实体。当用户输入查询( q u e r y ) w e bs e m a n t i c ”，计算的第一步：专家搜索查询器通过检索找出文档中与“w e b s e m a n t i c ”有关的所有文档集合d ，并记录每个文档在排序结果中的权值，称为文 档相关模型，记作尸( p l 力；第二步：在文档集合d 中，计算查询关键词“w e b s e m a n t i c ”与专家实体( 如：d a nc o n n o l l y 等人名) 共同出现的专家实体排序集合， 并记录每个专家实体在排序结果中的权值，记为p ( e l d , q ) 。最后，两步语言模型 依公式1 1 得到每个相对查询的排序权值，计算权值作为返回元组排序依据。结 果为按权值从大到小排列的专家实体元组。 6 第一章绪论 蛳昌 盛；，一 要 函。 图l1 专家搜索两步语言模型 专家搜索的排序可以总结为：针对专家实体的属性信息的定义，建立专家 实体属性信息描述模板，根据专家实体属性信息匹配网页信息并标注。然后根 据查询关键字的描述及其扩展描述找出含有查询关键字的实体网页集合d ( 即网 页内容中包含实体属性信息的网页) ，对网页集合d 中所出现的专家实体信息与 查询关键字进行相关度评价，按照相关程度的高低排序专家实体列表。 1 3 本文的主要研究内容 本文在分析目前专家搜索领域相关排序算法和排序模型基础上，指出专家 搜索中，实体相关性对专家搜索排序结果有重要的影响。提出专家搜索中建立 实体相关度的方法和基于实体相关性的专家搜索排序优化模型。 目前的研究中关注实体相关性或排序的研究主要针对于相关性本身的研 究，针对专家搜索的特点，如何把这种专家实体的相关性用于排序问题上是一 个有研究价值的问题。 针对上述问题，本文提出了基于实体相关性的排序优化问题。拟开展的主 要工作包括： ( 1 ) 引入词之间的相关性的概念，定义实体向量空间模型，构造专家实体相 第一章绪论 关性挖掘模型。指出专家实体所具有的相关性特征，并针对不同的特征 选取不同的特征挖掘算法。由于不同特征挖掘算法之间的松耦合性，进 一步把针对不同特征的挖掘算法线性组合，计算专家实体相关性度量值。 根据专家实体相关度矩阵，建立实体关系图。图的每个节点为专家实体， 图的边为实体相关度值。在此基础上定义有效实体关系图、三类关系。 即不是所有联系都有效，只有紧密联系或有联系的节点才能提供有效的 专家实体相关信息。三类关系包括：紧密联系、有联系、无联系。 根据有效实体关系图，定义激活节点。激活节点的选取来自两种调整优 化模型，一种是不考虑相关性返回结果集的前n 个节点作为激活节点； 另一种是通过有效实体关系图，以打分的方式评选n 个节点为激活节点， 当返回结果中有与激活节点联系的节点，则触发优化调整规则。 建立实验平台，设计比照实验，验证模型有效性。 1 4 本文的章节安排 本文主要研究在专家搜索中如何建立专家实体相关度并利用这种相关性优 化排序结果，全文共分为六章。 第一章是本文绪论部分。本章介绍专家搜索的应用背景和专家搜索研究的 主要问题，在此基础上提出本文研究的主要内容：专家搜索中建立实体相关度 的方法和基于实体相关性的专家搜索排序优化模型。 第二章综述专家搜索的相关技术背景。本章介绍专家搜索与全文检索的不 同之处，给出专家搜索的定义和体系结构以及专家搜索中的实体相关性研究的 意义和研究成果，指出现有研究工作存在的不足之处。 第三章和第四章是本文研究工作的主要论述部分。第三章提出针对专家搜 索的实体相关度挖掘模型。该章先给出实体相关度挖掘模型的描述和体系结构， 在此基础上，介绍其相关的挖掘算法。第四章在第三章内容基础上，详细介绍 实体关系图、有效实体关系图及基于实体相关度的排序优化模型。内容包括， 如何建立有效实体关系图以及利用有效实体关系图实现排序结果的两种优化模 型，最后并比较说明两种模型的特点。 第五章是针对研究内容给出的实验与分析。本章给出研究工作的实验平 台、实验数据集及实验结果的详细介绍。同时，给出实验结果的比照基准及实 8 ) )、， o 厶口u t ( ( ( 第一章绪论 验分析。 第六章是全文总结部分，在此对本文的研究进行归纳总结，并对后续的研 究作进一步展望。 9 第二章相关技术背景 第二章相关技术背景 2 1专家搜索与全文检索的区别 为了有效满足用户需求，信息检索系统必须以某种方式“解释 搜索结果 集合中信息项( 文档) 的内容，并且根据与用户查询( q u e r y ) 的相似度对它们 进行排序，对文档内容的“解释 包括从文献文本中提取语法和语义信息并将 这些信息用语用户查询信息的匹配。由于专家检索和全文检索检索对象的不同， 因而，二者在“解释 信息项时方法有所不同。 全文检索与专家搜索的重要区别在于，相似度度量标准的不同。全文检索 是在文档级别的匹配用户查询，全文检索关注的对象是文档，主要考察文档与用 户查询的相似度。而实体检索是实体级别的相似度匹配，关注的对象是实体实 例主要考察实体实例与用户查询的。 2 1 1全文检索 全文检索的目标是识别出与用户查询相关的文档或段落，返回给用户文档 ( d o c u m e n t ) 级别的信息，主要的方式是通过分析用户输入的查询( q u e r y ) 在 目标文档或段落总的出现来度量。这种度量的方式有很多种，一般有基于统计 的方法：t f i d f 3 0 】，b m 2 5 啪1 ，和语言模型协3 ，及基于机器学习的方法：s v m ，人 工神经网络等。无论采用何种方式，传统的信息检索系统的模型都包括如下的 步骤：网页抓取，索引( 关键字) ，排序模型，图形用户界面等内容。 2 1 2 专家搜索 如前所述，传统的全文检索是文档级别的搜索。专家搜索是实体级别的搜 索，专家搜索的对象是专家实体的集合，实体实例集合是通过对网页数据过滤 获得的具有相同属性的结构化数据。专家搜索系统的功能模块一般包括：网页 抓取，命名实体抽取，索引( 关键字及命名实体) ，排序模型，图形用户界面 等内容。专家搜索在对对象数据的处理上比传统的全文检索增加了命名实体抽 取功能，即预先对数据做抽取和过滤，使得数据更加结构化。专家搜索的特点 1 0 第二章相关技术背景 很明显，数据更加结构化，增加了实体抽取部分；排序模型有了变化，需要考 虑实体级别排序。 2 2 专家搜索问题描述 2 2 1实体搜索及专家搜索的定义 2 2 1 1实体搜索定义 伊利诺伊斯大学的w i s d m ( w e bi n d e x i n ga n ds e a r c h f o rd y n a m i cm i n i n g ) 实体搜索项目小组在s i g m o d2 0 0 7 发表的论文中给出了实体搜索的定义口1 。 实体搜索的数据模型和描述如下： 通常目前的信息检索系统中，网页被认为是文档级别。即互联网是一系列 文档( 网页) 的集合d = d l ，d 2 , ，磊) ；在实体搜索中，互联网被认为是实体级别， 即相应的互联网是实体资源的集合： e = e 1 ，e 2 , ，晶) ，其中e i 是实体类型，代表一种类型的实体( 如电话号码， 电子邮件等) 。每个实体类型都是一系列实体实例的集合，这些实体实例都是从 网页数据中抽取来的，通常定义e i 为蜀的一个实体实例。以电话号码实体为例， 通过电话号码的规则从文档集合d 中抽取出如下的电话号码 “0 1 0 - 8 8 0 0 1 1 2 3 ”， “0 1 0 7 7 0 0 1 1 2 3 ”，则表示为：以# 标识实体类型，则表示为 # p h o n e = 0 1 0 8 8 0 0 1 1 2 3 ，0 1 0 - 7 7 0 0 1 1 2 3 ，) 。 实体搜索的定义可用如下形式化定义表示： 给定：一个实体集合e = 历，如，易) 这个实体集合从网页集合d = d l ，d 2 , d 3 ，磊) 按照抽取获得。 输入：查询( q u e r y ) q = p - a e l ，局局) 局，厶：实体搜索允许用户定义实体类型 局局：用户输入的关键字： 卢：查找返回元组的排序模式 a ：关键字与所要查找的元组匹配模式 输出：元组t = t 为含有关键字墨的某一类型的实体实例。 第二章相关技术背景 实体搜索的目标是帕，x e m 厨k 越样的空间中找出与查询q ( q u e r y ) 匹配的元组t ，并把这些元组按照与查询匹配的程度排序。这些元组按 照0 【模式匹配，按照p 模式排序并返回给用户。 举例说明如下： 输入：q 1 = ( a m a z o n c u s t o m e rs e r v i c e # p h o n e ) 则返回的输出元组如下表2 1 所示： 表2 1 第一列r a n k 为排序序号，第二列p h o n en u m b e r 为电话号码类型实体 ( # p h o n e ) ，第三s c o r e 为其按照b 模式排序所获得的分数，第四列u r 为对应实 体所在网页的链接地址。 表2 1 实体搜索输入元组 r a n kp h o n en u m b e rs c o r e u r l 18 0 0 2 0 1 7 5 7 50 9 a m a z o n c o r n s u p p o r t h i m 28 0 0 9 8 8 0 8 8 6 0 - 8 d e l l c o m s u p p o r t o r s 2 2 1 2 专家搜索定义 专家搜索是给定一个主题或领域，搜索在这一主题或研究领域内的专家专 家搜索属于实体搜索的范畴，是给定实体类型为专家名的实体搜索。专家搜索 的定义可如下描述： 给定：一个专家( 姓名) 集合把= m a r t i nc h a p m a n ，d a n , 一c a r n i eb o u r n e 这个专家集合从网页集合d = d l ，d e , 西磊) 按照人名命名规则抽取获得。 输入：查询( q u e r y ) q = 1 3 - a e l ，玩局局) 用户输入的关键字：k z 筠 p ：查找返回元组的排序模式 q ：关键字与所要查找的元组匹配模式 输出：元组t = t 为含有关键字墨的专家实体实例。 专家搜索的任务是根据用户给定的查询，找出与用户查询相似的专家，并 按照分数排序。具体过程可用下图2 1 所示，用户输入查询q = “d a t am i n g i n g ， 查询提交给搜索引擎，搜索引擎按照a 模式匹配与查询“d a t am “n g 相似的 1 2 第二章相关技术背景 所有元组集合，然后按照p 模式把元组集合排序形成有序专家列表集合 j i a w e i h a n ，j o n a t h a nd a l e ) 返回给用户。 图2 1 专家搜索过程 专家搜索的返回结果的形式举例说明如下： 设用户输入q u e r y = w e bs e r v i c e sc o o r d i n a t i o n ”，则返回结果如下表2 1 所 示，表2 2 第- - y u “r a n k 为搜索结果排序顺序，第二列“e x p e r tn a m e ”为专家实 体实例，第三列“s c o r e ”为通过排序算法给出的专家实体分数，第四列“u r l 为 最能反映查询关键词与专家实体相关的网页地址，第四列u r l 作为辅助信息， 不是必须给出的信息。 表2 2 专家搜索返回结果 ， 强 r a n k e x p e r tn a m e s c o r e u r l i lc a r n i e b o u r n ed 9h tt d ：v r w w w w w 3 c c o m w e b p a g e l h t m i j 2m a r ti nc h a p m a n0 8h t t p ：m w w w 3 c c o m i n d e x 5 h t mi 蠹 2 2 2目前专家搜索系统的体系结构 专家搜索的主要功能模块包括：网页抓取器，实体识别处理器，索引器， 检索器和图形用户接口五部分。比全文搜索的多了实体识别处理器部分功能。 专家搜索的体系结构如下图2 2 所示口1 ，自下而上的各部分功能如下： ( 1 ) 网页抓取器：网页抓取器功能是搜集互联网中的信息。通常它是一个被 称为网络机器人( 或网络蜘蛛) 的计算机程序。网络机器入是一个跨平台程序， 它经过序列化后，由一台服务器传输到另一台服务器，在允许它运行的服务器 上并行运行。程序运行时不停地抓取各种类型的新信息，同时因为互联网上的 信息更新很快，所以还要定期更新已经搜集过的旧信息，以避免死链接和无效 1 3 第二章相关技术背景 链接。目前有两种主要的搜集信息的策略：第一，将w e b 空间按照域名、i p 地址 或国家域名划分，每个搜索器负责一个子空间的穷尽搜索：第二，从一个起始u r l 集合开始，顺着这些u r l 中的超链( h y p e r l i n k ) ，以宽度优先、深度优先或启发 式方式循环地在互联网中发现信息。这些起始u r l 可以是任意的u r l ，但常常是 一些非常流行、包含很多链接的站点。 雠器 黝 排序 搿戳雠戮裙鬻戮巍翻酣嚣张缴群戮毪缓琵爱搿渤搿缓戮 索。】文件及结构化数据 i 索引器 图22 专家搜索体系结构 ( 2 ) 实体识别处理器：实体识月器功能是在对网页数据中的命名实体进行识 别和标注及保存抽取来的结构化数据，对海量网页数据进行命名实体识别和抽 取。完成实体标注和把抽取来的信息生成结构化数据的功能。实体识别处理器 形象的说就像网页过滤器，按照给定的实体信息属性，从网页中滤出结构化的 信息并保存，识别处理器可以在后台离线处理网页数据。 ( 3 )实体识别模型：定义实体识别处理器应用的实体识别模型，有基于统计 和基于规则两种基本模型。两种模型各有特点，基于规则的方法识别比基于统 计的方法准确率要高一些，但灵活性差。 第二章相关技术背景 ( 4 ) 索引器：索引器的功能是理解搜索器所搜索的信息，从中抽取出索引项， 用于表示文档以及生成文档库的索引表。索引表一般使用某种形式的倒排表 ( i n v e r s i o nl i s t ) ，即由索引项查找相应的文档。索引表也可能要记录索引项在文 档中出现的位置，以便检索器计算索引项之间的相邻或接近关系( p r o x i m i t y ) 。索 引项有客观索引项和内容索引项两种：客观项与文档的语意内容无关，如作者 名、u r l 、更新时间、编码、长度、链接流行度( l i n kp o p u l a r i t y ) 等等：内容索引项 是用来反映文档内容的，如关键词及其权重、短语、单字等等。内容索引项可 以分为单索引项和多索引项( 或称短语索引项) 两种。单索引项对于英文来讲是 英语单词，比较容易提取，因为单词之间有天然的分隔符( 空格) ：对于中文等连 续书写的语言，必须进行词语的切分，同时对于停词如：i n 、o r 、o n 等按照停词 表予以消除。在搜索引擎中，一般要给单索引项赋与一个权值，以表示该索引 项对文档的区分度，同时用来计算查询结果的相关度。使用的方法一般有统计 法、信息论法和概率法。短语索引项的提取方法有统计法、概率法和语言学法 叫。索引器可以使用集中式索引算法或分布式索引算法。当数据量很大时，必 须实现即时索l ( i n s t a n ti n d e x i n g ) ，否则不能够