信号与信息处理专业毕业论文-基于统计滚雪球模型的知识挖掘理论与方法

1、中国科学技术大学博士学位论文作者姓名：余 山学科专业：生物物理导师姓名：周逸峰 教授 马原野 教授完成时间：二五年六月二日基于统计滚雪球模型的知识挖掘理论与方法作者姓名：余 山学科专业：生物物理导师姓名：周逸峰 教授 马原野 教授完成时间：二五年六月二日作者姓名：余 山学科专业：生物物理导师姓名：周逸峰 教授 马原野 教授完成时间：二五年六月二日作者姓名： 刘晓江学科专业： 信号与信息处理导师姓名： 俞能海 教授 李明镜 教授完成时间： 二一一年六月三日University of Science and Technology of ChinaA dissertation for doctors

2、 degreeKnowledge MiningBased onStatistical Snowball ModelsAuthor： Xiaojiang LiuMajor： Signal and Information ProcessingAdvisor： Prof. Nenghai Yu Prof. Mingjing LiFinished time: June 3rd, 2011基于统计滚雪球模型的知识挖掘理论与方法二六系刘晓江中国科学技术 大学摘 要 III中国科学技术大学学位论文原创性声明本人声明所呈交的学位论文,是本人在导师指导下进行研究工作所取得的成果。除已特别加以标注和致谢的地方外，

3、论文中不包含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确的说明。作者签名：_ 签字日期：_中国科学技术大学学位论文授权使用声明作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入中国学位论文全文数据库等有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内容相一致。保密的学位论文在解密后也遵守此规定。公开 保密（_年）作者签名：_ 导师签名：_签

4、字日期：_ 签字日期：_摘 要随着互联网技术的迅猛发展，互联网已成为一个巨大的信息源，其中含有大量的关于现实世界命名实体的信息。这些命名实体包括机构、地点和人物等，既涵盖了名人也涉及日常生活中的普通人。命名实体搜索引擎从大量的网页中挖掘出命名实体，并总结出与用户查询的命名实体相关的知识，直接返回给用户。与普通搜索引擎返回的非结构化网页相比，这种搜索引擎更快捷、更直观，已成为工业界和学术界关注的热点之一。要构建既快又准的命名实体搜索引擎，就必须对命名实体知识进行深度挖掘。从网页中自动识别命名实体、对命名实体进行摘要和为命名实体建立联系并挖掘出其关系是实体知识挖掘的三个关键科学问题。本文围绕构建命

5、名实体搜索中的这三个科学问题展开了深入的研究，提出了一个基于统计学习的自学习模型统计滚雪球模型，弥补了现有自学习模型的不足。具体来说，本文的主要研究成果和创新之处如下：分析互联网搜索的需求，充分调研了互联网知识挖掘的特点，重点讨论了基于自然语言特征的有监督学习模型和基于模板的自学习模型的知识挖掘算法；分析了这两类方法的基本思想，讨论了每类模型代表性的工作，并发现了其中的不足之处。提出了一种基于自学习的关系抽取模型：统计滚雪球模型。该模型使用基于统计的模板评价函数替代传统的基于手动构造的模板评价函数，使之能采用更高效的模板特征；同时采用马尔可夫逻辑网络作为底层的统计模型，从而融入各级关系联合抽取

6、，充分地利用信息达到提高抽取性能的目的。在互联网真实数据上的关系抽取实验表明，相对于传统的自学习方法，统计滚雪球方法能在保持相同准确率的前提下，明显提升抽取的召回率。提出了一种迭代式命名实体识别和关系抽取的联合抽取模型。该模型扩展了实体识别的条件随机场模型，将基于关系抽取的特征加入到实体识别的过程中，从而提高实体识别的性能；同时采用迭代挖掘的方法，在命名实体识别和关系抽取两个任务之间建立联系，使各自的结果能被另一个任务在决策时使用。在互联网真实数据下的实验表明，相对于传统的顺序式知识挖掘模型，联合挖掘模型对实体识别和关系抽取任务的性能都有较大提高。提出了一种基于统计滚雪球模型的命名实体摘要模型

7、：摘要滚雪球。该模型充分利用互联网数据中命名实体的事实与摘要之间的对偶性，同时完成命名实体的事实挖掘与摘要排序；同时采用自学习统计滚雪球框架，可以从少量种子出发，迭代式地同时增加命名实体事实与摘要。在互联网真实数据上的实验和用户调研表明，该模型在事实挖掘与摘要排序问题上都取得了明显改进，也证明了统计滚雪球模型具有很广的适用性。构建了基于10亿网页的中文命名实体搜索引擎人立方和基于30亿网页的英文命名实体搜索引擎EntityCube。这两个命名实体搜索引擎能够在大规模互联网数据中挖掘出关于命名实体的各种有用信息，获得了巨大的成功和很好的反响。本文提出的关系抽取方法已经应用到实际系统之中，其它方法

8、也都经过了真实系统数据的验证。最后，对全文工作进行了总结，并对下一步的研究方向进行了展望。关键词：知识挖掘，命名实体搜索，自学习，关系抽取，命名实体识别，命名实体摘要Abstract ABSTRACTWith the rapid development of Internet technologies, the World Wide Web has been growing rapidly as a huge knowledge repository, containing various kinds of valuable information about real-world named

9、 entities. These named entities contain organizations, locations and persons, covering from celebrities to the everyday individuals. Named entity search engines automatically mine the named entities from Web pages, and summarize knowledge for them based on the their Web appearances, which could be d

10、irectly returned to users. Compared with the general search engines which can only return the unstructured Web pages, this type of search engines provides faster and more direct user experience, and has become a great research and development area in both industry and research area.In order to build

11、 a fast and accurate named entity search engine, deep knowledge mining on named entities from the Web is required. There are three key knowledge mining problems in building named entity search engines: named entity recognition, named entity summarization and named entity relationship mining. Focusin

12、g on these three key problems, this dissertation proposes a statistical unsupervised learning framework named StatSnowball, which has overcome the disadvantage of state-of-the-art unsupervised learning models. The main contents and contributions of this dissertation are as follows: Discuss the state

13、-of-the-art Web-scale knowledge mining systems. Mainly focus on supervised methods based on the natural language features and the state-of-the-art self-supervised methods based on the extraction patterns. These methods have been widely used in different tasks of knowledge mining. The emphasis of our

14、 analysis is the basic idea behind these two types of methods, and typical models.Propose an unsupervised learning model: StatSnowball (Statistical Snowball) for the relationship extraction. Our model adopts the bootstrapping framework and uses the general statistical model Markov logic networks as

15、the underlying extraction model. By using the statistical pattern evaluation and selection methods, StatSnowball can incorporate all kinds of patterns. By adopting MLN, StatSnowball accomplishes various levels of joint inference in relationship extraction. Experiments on both small but fully labeled

16、 data and large scale Web data have shown the effectiveness of our methods.Propose a uniform named entity recognition and relation extraction model based on iterative framework: EntSum. Our model extends conditional random field model used by named entity recognition, which enables relationship feat

17、ures to be added to the model. Joint model adopts the iterative framework to build bidirectional connection between two tasks, in which both results can be used in the others decision making process. Experiments on the real Web data have shown the increase to the performance on both two tasks.Propos

18、e an entity summarization model: BioSnowball, which can be considered as an extension to the basic StatSnowball model. By using the Fact-Bio duality, BioSnowball adopts the bootstrapping framework, and starts from only a small set of samples to jointly complete two different types of summarization.

19、Our model can jointly complete the fact extraction and biography ranking for Web entities. Experiments on the real Web data and the user study have shown the effectiveness of our model on both problems. The success of BioSnowball has also shown the generality of the basic StatSnowball model.Build tw

20、o public available named entity search engines named Renlifang and EntityCube, which the author has participated in as the main researcher and developer. These two search engines automatically mine knowledge from billions of Chinese and English Web pages respectively and build an entry page for ever

21、y extracted entity. StatSnowball has been already applied to the system, and other methods in this dissertation have also been verified under the data of these two real systems.At the end of this dissertation, we conclude it and prospect the further studies in the future.Key Words: knowledge mining,

22、 named entity search, self-supervised learning, relationship extraction, named entity recognition, named entity summarization目 录目 录 TOC o 1-2 h z t 标题 3,3,标题3,3 HYPERLINK l _Toc292624185 摘 要 PAGEREF _Toc292624185 h I HYPERLINK l _Toc292624186 ABSTRACT PAGEREF _Toc292624186 h III HYPERLINK l _Toc2926

23、24187 目 录 PAGEREF _Toc292624187 h V HYPERLINK l _Toc292624188 图表目录及缩略语 PAGEREF _Toc292624188 h IX HYPERLINK l _Toc292624189 插图目录 PAGEREF _Toc292624189 h IX HYPERLINK l _Toc292624190 表格目录 PAGEREF _Toc292624190 h X HYPERLINK l _Toc292624191 第1章 绪论 PAGEREF _Toc292624191 h 1 HYPERLINK l _Toc292624192 1.

24、1 研究背景与研究意义 PAGEREF _Toc292624192 h 1 HYPERLINK l _Toc292624193 1.1.1 研究背景 PAGEREF _Toc292624193 h 1 HYPERLINK l _Toc292624194 1.1.2 研究意义 PAGEREF _Toc292624194 h 4 HYPERLINK l _Toc292624195 1.2 关键问题与研究任务 PAGEREF _Toc292624195 h 6 HYPERLINK l _Toc292624196 1.2.1 关键问题 PAGEREF _Toc292624196 h 6 HYPERLI

25、NK l _Toc292624197 1.2.2 研究任务 PAGEREF _Toc292624197 h 7 HYPERLINK l _Toc292624198 1.3 研究内容与结构安排 PAGEREF _Toc292624198 h 8 HYPERLINK l _Toc292624199 第2章 统计滚雪球模型 PAGEREF _Toc292624199 h 11 HYPERLINK l _Toc292624200 2.1 简介 PAGEREF _Toc292624200 h 11 HYPERLINK l _Toc292624201 2.1.1 关系抽取任务介绍 PAGEREF _Toc

26、292624201 h 11 HYPERLINK l _Toc292624202 2.1.2 相关工作 PAGEREF _Toc292624202 h 13 HYPERLINK l _Toc292624203 2.2 统计滚雪球模型架构 PAGEREF _Toc292624203 h 14 HYPERLINK l _Toc292624204 2.2.1 关系抽取问题定义 PAGEREF _Toc292624204 h 14 HYPERLINK l _Toc292624205 2.2.2 统计滚雪球模型架构 PAGEREF _Toc292624205 h 15 HYPERLINK l _Toc2

27、92624206 2.3 关系抽取统计模型 PAGEREF _Toc292624206 h 18 HYPERLINK l _Toc292624207 2.3.1 马尔可夫逻辑网络 PAGEREF _Toc292624207 h 18 HYPERLINK l _Toc292624208 2.3.2 联合推理 PAGEREF _Toc292624208 h 21 HYPERLINK l _Toc292624209 2.3.3 加速方法 PAGEREF _Toc292624209 h 25 HYPERLINK l _Toc292624210 2.4 产生和选择模板 PAGEREF _Toc29262

28、4210 h 25 HYPERLINK l _Toc292624211 2.4.1 产生模板 PAGEREF _Toc292624211 h 25 HYPERLINK l _Toc292624212 2.4.2 选择模板 PAGEREF _Toc292624212 h 27 HYPERLINK l _Toc292624213 2.5 实验 PAGEREF _Toc292624213 h 27 HYPERLINK l _Toc292624214 2.5.1 在Sent500数据集上的实验 PAGEREF _Toc292624214 h 27 HYPERLINK l _Toc292624215 2

29、.5.2 在Web1M数据集上的实验 PAGEREF _Toc292624215 h 31 HYPERLINK l _Toc292624216 2.5.3 效率 PAGEREF _Toc292624216 h 34 HYPERLINK l _Toc292624217 2.6 本章小结 PAGEREF _Toc292624217 h 34 HYPERLINK l _Toc292624218 第3章 实体与关系的联合抽取 PAGEREF _Toc292624218 h 35 HYPERLINK l _Toc292624219 3.1 简介 PAGEREF _Toc292624219 h 35 HY

30、PERLINK l _Toc292624220 3.1.1 背景介绍 PAGEREF _Toc292624220 h 35 HYPERLINK l _Toc292624221 3.1.2 相关工作 PAGEREF _Toc292624221 h 38 HYPERLINK l _Toc292624222 3.2 问题定义 PAGEREF _Toc292624222 h 39 HYPERLINK l _Toc292624223 3.2.1 命名实体识别任务 PAGEREF _Toc292624223 h 39 HYPERLINK l _Toc292624224 3.2.2命名实体识别与关系抽取联合

31、优化任务 PAGEREF _Toc292624224 h 40 HYPERLINK l _Toc292624225 3.3 顺序模型 PAGEREF _Toc292624225 h 41 HYPERLINK l _Toc292624226 3.3.1 基于条件随机场的命名实体识别 PAGEREF _Toc292624226 h 41 HYPERLINK l _Toc292624227 3.3.2 基于统计滚雪球的关系抽取 PAGEREF _Toc292624227 h 43 HYPERLINK l _Toc292624228 3.4 联合抽取模型 PAGEREF _Toc292624228 h

32、 43 HYPERLINK l _Toc292624229 3.4.1 关系模板特征 PAGEREF _Toc292624229 h 44 HYPERLINK l _Toc292624230 3.4.2 关系抽取特征 PAGEREF _Toc292624230 h 44 HYPERLINK l _Toc292624231 3.4.3 扩展模型 PAGEREF _Toc292624231 h 45 HYPERLINK l _Toc292624232 3.5 实验 PAGEREF _Toc292624232 h 47 HYPERLINK l _Toc292624233 3.5.1 数据集及实验方法

33、 PAGEREF _Toc292624233 h 47 HYPERLINK l _Toc292624234 3.5.2 实验结果及讨论 PAGEREF _Toc292624234 h 47 HYPERLINK l _Toc292624235 3.6 本章小结 PAGEREF _Toc292624235 h 49 HYPERLINK l _Toc292624236 第4章 摘要滚雪球模型 PAGEREF _Toc292624236 h 51 HYPERLINK l _Toc292624237 4.1 简介 PAGEREF _Toc292624237 h 51 HYPERLINK l _Toc29

34、2624238 4.1.1 背景介绍 PAGEREF _Toc292624238 h 51 HYPERLINK l _Toc292624239 4.1.2 相关工作 PAGEREF _Toc292624239 h 53 HYPERLINK l _Toc292624240 4.1.3 摘要滚雪球模型 PAGEREF _Toc292624240 h 54 HYPERLINK l _Toc292624241 4.2 问题定义 PAGEREF _Toc292624241 h 56 HYPERLINK l _Toc292624242 4.2.1 网页块 PAGEREF _Toc292624242 h 5

35、6 HYPERLINK l _Toc292624243 4.2.2 事实和摘要 PAGEREF _Toc292624243 h 57 HYPERLINK l _Toc292624244 4.2.3 联合摘要任务 PAGEREF _Toc292624244 h 58 HYPERLINK l _Toc292624245 4.3 系统架构 PAGEREF _Toc292624245 h 58 HYPERLINK l _Toc292624246 4.3.1 输入部分P1 PAGEREF _Toc292624246 h 59 HYPERLINK l _Toc292624247 4.3.2 迭代总结模型P

36、2 PAGEREF _Toc292624247 h 59 HYPERLINK l _Toc292624248 4.3.2 后处理P3 PAGEREF _Toc292624248 h 60 HYPERLINK l _Toc292624249 4.4 联合摘要模型 PAGEREF _Toc292624249 h 61 HYPERLINK l _Toc292624250 4.4.1 事实抽取 PAGEREF _Toc292624250 h 62 HYPERLINK l _Toc292624251 4.4.2 摘要排名 PAGEREF _Toc292624251 h 63 HYPERLINK l _T

37、oc292624252 4.4.3 联合摘要 PAGEREF _Toc292624252 h 63 HYPERLINK l _Toc292624253 4.4.4 推理与训练 PAGEREF _Toc292624253 h 64 HYPERLINK l _Toc292624254 4.5 实验 PAGEREF _Toc292624254 h 65 HYPERLINK l _Toc292624255 4.5.1 数据集 PAGEREF _Toc292624255 h 65 HYPERLINK l _Toc292624256 4.5.2 摘要-事实对偶性 PAGEREF _Toc292624256

38、 h 66 HYPERLINK l _Toc292624257 4.5.3 联合摘要模型 PAGEREF _Toc292624257 h 67 HYPERLINK l _Toc292624258 4.5.4 自学习迭代框架 PAGEREF _Toc292624258 h 68 HYPERLINK l _Toc292624259 4.5.5 用户调研：覆盖率 PAGEREF _Toc292624259 h 70 HYPERLINK l _Toc292624260 4.6 本章小结 PAGEREF _Toc292624260 h 71 HYPERLINK l _Toc292624261 第5章 命

39、名实体搜索系统 PAGEREF _Toc292624261 h 73 HYPERLINK l _Toc292624262 5.1 系统功能介绍 PAGEREF _Toc292624262 h 73 HYPERLINK l _Toc292624263 5.2 大规模挖掘算法流程 PAGEREF _Toc292624263 h 77 HYPERLINK l _Toc292624264 5.3 本章小结 PAGEREF _Toc292624264 h 81 HYPERLINK l _Toc292624265 第6章 总结与展望 PAGEREF _Toc292624265 h 83 HYPERLINK

40、 l _Toc292624266 6.1 论文总结 PAGEREF _Toc292624266 h 83 HYPERLINK l _Toc292624267 6.2 未来研究展望 PAGEREF _Toc292624267 h 84 HYPERLINK l _Toc292624268 参考文献 PAGEREF _Toc292624268 h 87 HYPERLINK l _Toc292624269 致 谢 PAGEREF _Toc292624269 h 93 HYPERLINK l _Toc292624270 在读期间发表的学术论文与取得的其他研究成果 PAGEREF _Toc29262427

41、0 h 95 HYPERLINK l _Toc292624271 作者简介 PAGEREF _Toc292624271 h 96图表目录及缩略语图表目录及缩略语插图目录 TOC h z t FIGURE CAPTION c HYPERLINK l _Toc294793074 图1.1 普通搜索引擎与实体级别搜索引擎对比 PAGEREF _Toc294793074 h 2 HYPERLINK l _Toc294793075 图1.2 论文的内容组织 PAGEREF _Toc294793075 h 8 HYPERLINK l _Toc294793076 图2.1 EntityCube自动产生的人物

42、关系页面 PAGEREF _Toc294793076 h 12 HYPERLINK l _Toc294793077 图2.2 统计滚雪球模型架构图 PAGEREF _Toc294793077 h 16 HYPERLINK l _Toc294793079 图2.3自举式关系抽取算法 PAGEREF _Toc294793079 h 17 HYPERLINK l _Toc294793080 图2.4 MLN示例 PAGEREF _Toc294793080 h 19 HYPERLINK l _Toc294793081 图2.5 四个级别关系抽取联系图 PAGEREF _Toc294793081 h 2

43、1 HYPERLINK l _Toc294793082 图2.6 在Sent500数据集上性能随着迭代次数变化图 PAGEREF _Toc294793082 h 30 HYPERLINK l _Toc294793083 图2.7 在Web1M数据集上系统性能随着迭代次数变化图 PAGEREF _Toc294793083 h 32 HYPERLINK l _Toc294793084 图2.8 在Web1M上Open IE任务性能随着迭代次数曲线 PAGEREF _Toc294793084 h 33 HYPERLINK l _Toc294793085 图3.1 命名识别与关系抽取的相互影响 PAG

44、EREF _Toc294793085 h 37 HYPERLINK l _Toc294793086 图3.2 条件随机场标记相关性 PAGEREF _Toc294793086 h 42 HYPERLINK l _Toc294793087 图4.1 EntityCube产生的对查询“Bill Gates”的总结页面 PAGEREF _Toc294793087 h 52 HYPERLINK l _Toc294793089 图4.2 Wikipedia的Bill Gates页面中摘要的第一段 PAGEREF _Toc294793089 h 54 HYPERLINK l _Toc294793090 图

45、4.3 利用VIPS算法产生的3个网页块 PAGEREF _Toc294793090 h 56 HYPERLINK l _Toc294793091 图4.4 摘要滚雪球系统架构图 PAGEREF _Toc294793091 h 58 HYPERLINK l _Toc294793093 图4.5 摘要块去重MMR算法流程 PAGEREF _Toc294793093 h 60 HYPERLINK l _Toc294793094 图4.6 正确抽取数量和准确率随迭代次数变化曲线 PAGEREF _Toc294793094 h 68 HYPERLINK l _Toc294793095 图4.7 正确摘

46、要块数量和准确率随迭代次数变化曲线 PAGEREF _Toc294793095 h 69 HYPERLINK l _Toc294793096 图4.8 用户覆盖率 PAGEREF _Toc294793096 h 69 HYPERLINK l _Toc294793097 图5.1 人立方搜索主页 PAGEREF _Toc294793097 h 73 HYPERLINK l _Toc294793098 图5.2 人立方为查询“刘德华”产生的实体总结页面 PAGEREF _Toc294793098 h 74 HYPERLINK l _Toc294793099 图5.3 人立方为查询“刘德华”产生的关

47、系图 PAGEREF _Toc294793099 h 75 HYPERLINK l _Toc294793100 图5.4 人立方为查询“郭晶晶”到“周星驰”产生的六度关系图 PAGEREF _Toc294793100 h 76 HYPERLINK l _Toc294793101 图5.5 大规模知识挖掘流程图 PAGEREF _Toc294793101 h 77 HYPERLINK l _Toc294793102 图5.6 具体挖掘算法流程图 PAGEREF _Toc294793102 h 80表格目录 TOC h z t TABLE CAPTION c HYPERLINK l _Toc292

48、624300 表2.1 关键词的不同种类，要求和在产生中的例子 PAGEREF _Toc292624300 h 26 HYPERLINK l _Toc292624301 表2.2在Sent500传统抽取的比较评价结果 PAGEREF _Toc292624301 h 29 HYPERLINK l _Toc292624302 表2.3 在Sent500上Open IE任务的比较评价结果 PAGEREF _Toc292624302 h 30 HYPERLINK l _Toc292624303 表2.4 在Web1M上Open IE最终关系类别分布 PAGEREF _Toc292624303 h 34

49、 HYPERLINK l _Toc292624304 表3.1 在Web1M数据上的实验结果(Extr. = 抽取, Est. = 估计) PAGEREF _Toc292624304 h 48 HYPERLINK l _Toc292624305 表4.1 事实类型定义 PAGEREF _Toc292624305 h 62 HYPERLINK l _Toc292624306 表4.2 最常出现的事实种类 PAGEREF _Toc292624306 h 66 HYPERLINK l _Toc292624307 表4.3 不同总结模型在两个任务上的结果比较 PAGEREF _Toc292624307

50、 h 68 HYPERLINK l _Toc292624308 表4.4 利用总结结果完成去除歧义性（“Kerry Webb”） PAGEREF _Toc292624308 h 71中国科学技术大学博士学位论文第1章 绪论第1章 绪论近些年来，随着互联网技术的迅猛发展，互联网已成为一个巨大的信息源，特别是含有大量的关于现实世界命名实体的信息。这些命名实体包括机构、地点和人物等，既涵盖了每天谈论的名人也涉及日常生活中的普通人。命名实体搜索引擎从大量的网页中识别出命名实体，并自动总结出与用户查询的命名实体相关的知识，直接返回给用户。与普通搜索引擎返回的无结构化网页链接相比，这种搜索引擎更快捷、更直

51、观，已成为工业界和学术界关注的一个热点。本章首先将讨论命名实体知识挖掘的研究背景和研究意义。然后给出了其中的关键问题，以及论文的研究任务。最后提出了论文的研究内容与结构安排。1.1 研究背景与研究意义1.1.1 研究背景近些年来，互联网技术飞速发展，从仅仅少数用户能创造内容的Web 1.0到任何用户都能发布信息的Web 2.0，互联网已经成为一个巨大的信息源。据统计72，互联网上至少有400亿网页。如何能从如此巨大的信息库中快速地找到用户需要的信息成为一个巨大的挑战。由此产生了很多互联网搜索引擎，比如必应9、谷歌27及百度84等，它们都取得了非常大的成功。这些搜索引擎利用爬虫将网页从各个网站中

52、抓取到本地服务器上，然后对这些网页进行分析。首先，系统将网页看作一个文本串，去除其中的HTML标记。这个文本串就作为网页的标识，系统对它们使用过滤停用词、分词、取词根等算法，将它们分成有用的词。为了能够快速地进行索引，系统为每个词建立倒排索引，索引到每个词出现的网页的标记。当用户发出一个查询请求时，搜索引擎会用查询中的每个词去倒排索引中查找其出现的网页，并将这些网页的交集作为结果返回给用户。为了能够评价网页的重要性，搜索系统基本使用了类似于PageRank85的算法，利用网页中超链接的性质为网页排序。利用上述基本算法加上大规模分布式运算平台，现在的商业搜索引擎能索引十亿，甚至百亿级别的网页，并

53、在毫秒级别将结果返回给用户，基本满足了用户的查询需求。但是，在这些系统中，网页仅仅被看作是文本串，系统仅对文本进行了分词，并建立索引，并没有用到其中的语义信息。这就使得用户获得了返回的结果后需要自己对网页进行理解和总结才能获得想要的信息。比如，用户在搜索引擎上输入“刘德华生日”，搜索引擎会返回很多同时包含“刘德华”和“生日”的网页，并按照网页的重要性排序。实际上，用户还是需要阅读返回的网页，从网页中自己总结出问题的答案，这个过程浪费了用户的时间。基于这类需求，互联网出现了一类新的搜索引擎：实体级别垂直搜索（Object-Level Vertical Search）。图1.1 普通搜索引擎与实体

54、级别搜索引擎对比实体级别垂直搜索是这样一类搜索，它们专注于某个领域，比如机票、酒店、人物、学术论文等，构建关于实体的知识库，为用户提供直接、快捷的知识回答。以学术论文网站为例，当用户输入某个作者的名字时，网站不是像普通搜索引擎那样返回很多含有作者名字的网页，而是会直接为用户返回已经整理好的关于该作者的信息。这些信息包括作者的所属机构、作者发表的论文、最经常与作者一起合作的研究者、作者论文的引用情况和作者领域的排名等。垂直搜索在各个领域都获得了很好的用户体验和商业成功，比如IT产品网站中关村在线，饭店评价网站大众点评网等。图1.1显示了查询“Bill Gates”在普通搜索引擎和实体级别搜索引擎

55、的对比图。从图中可以看出，普通搜索引擎将信息看作一个普通的文本段，呈现给用户的是很多网页的链接，而在右图的实体级别搜索中，关于查询实体的信息都已经整理好，以条目的形式呈现给用户，用户能更快，更全的找到信息。根据垂直搜索引擎索引的实体规模的大小，网站所使用的技术有很大的区别。当索引的实体规模较小时，比如产品、酒店等，网站大多采用基于手动标记或者模板方法。手动标记是指网站雇佣人手工地收集、标记数据。基于模板的信息收集是指利用模板从某类网页中抽取信息。与普通搜索引擎会对整个互联网进行抓取不同，这类网站只会定向地抓取一些该领域相关的网站。在抓取到有限网站的网页后，垂直搜索会使用模板对这些网站的信息进行

56、抽取，获得较高准确率的信息，并将这些结构化之后的知识加以整合后返回给用户。这类网站的不足之处在于它们只能应用于实体规模较小的领域，而在一些实体规模很大的领域，比如互联网上所有的人物、地点和机构等，这类方法往往无法实用。这类网站还有另一个缺点：信息可能带有偏见性。网站的信息（比如报价、排名等）容易受到不中立的因素影响，比如广告商等，用户容易对网站信息产生不信任。Web 2.0网站允许用户贡献信息，在这个环境下诞生了两类用户参与构建的大规模知识系统。一类是协同编辑平台，最成功的例子是维基百科71。维基百科基于中立观点12的编辑守则，所有的用户都可以随意添加实体，并为这个实体添加一个单独的页面。在这

57、个页面上可以为物体添加各类信息、介绍、图片等34。用户可以随意增加或删减内容，直到页面在各个贡献者之间达到平衡。基于这种协同编辑平台，英文的维基百科已经有超过三百万的物体页面。因为数据全面，信息丰富，观点中立，维基百科已经成为互联网上人们查找知名人物、机构、产品的第一去处。但是，由于中立观点编辑准则的限制，维基百科类的协同编辑很难扩展到普通人上面，因为普通人往往只有很少的人了解，拥有很少编辑者都共同知道的知识，页面很难达到平衡。近些年互联网非常流行的社交网络（Social Network Service，SNS）也成为Web 2.0时代的一个关于人物的巨大信息源，特别是关于普通用户。比较成功的

58、有起源于大学、后来扩展到所有人的Facebook24和职业社交网站LinkedIn41。这些网站通过将人们的社交活动网络化吸引了大批的用户，其所倡导的实名制使这些用户形成了了海量的人物信息库。根据Facebook的统计，到2011年1月，Facebook上账户数量已经达到6亿，其中97%的用户使用了全名。LinkedIn也拥有1亿的账户，很多账户里面包含了大量用户的职业信息。但是由于数据的隐私性和法律约束，很难在网站以外获得并使用这些数据，无法实现真正意义上的大规模命名实体搜索。在这种背景下，大规模数据集下的自动知识挖掘，也就是从互联网海量数据中自动地为现实世界中的实体总结出信息，成为了一个很

59、有前景的研究方向。工业界和研究界都完成了一些尝试性的系统，比如人物搜索Spock和Pipl，研究原型YAGO65和TextRunner76等，它们自动地从网页中挖掘信息：自动地识别人名或者实体名，并且为这些实体之间建立联系，但是这些网站仅仅为物体建立一个含有较少信息的页面，比如相关的网页或新闻等。从这些网站和研究原型上很难获得像维基百科那样丰富快捷的用户体验，无法满足用户的需求。并且这类系统的查询词只能是实体名字，不能是任意的关键字，所以并不是真正意义上的搜索。1.1.2 研究意义大规模实体知识挖掘技术的研究具有重大的研究意义和很高的实用价值。从研究方法上来说，我们的研究可以弥补现在互联网知识

60、挖掘算法的不足。互联网知识挖掘是指从互联网的网页或者文本中挖掘出所需要的信息的过程。相对于普通的知识挖掘，互联网知识挖掘有其特殊之处：互联网数据是半结构化的。不同于结构化的数据库和无结构化的普通文本，互联网数据兼有两者的特性。首先，互联网是有结构的网页树，每个网页的每个元素都是树上的一个节点。这些节点之间有联系，比如网页表格中的一行是兄弟节点等。同时网页节点上的文本是普通文本，所以互联网数据呈现半结构化。互联网数据量很大。在互联网出现以前，普通文本知识挖掘数据量很小，基本是在百万级别以下，而互联网上的网页都是10亿级别的，是以前处理的数据规模的几千倍。在这么大的数据量下，算法复杂性必须得到控制