网络信息的检索与挖掘回顾

程学旗，郭嘉丰，靳小龙

(中国科学院 计算技术研究所，北京 100190)

1 引言

随着互联网在人们日常生活与工作中的广泛普及和各种互联网应用的层出不穷，爆发式增长的网络信息已经使互联网成为了人类迄今为止规模最大的数据资源。据Google声称，他们在2008年索引的网页数据量已经达到1万亿，而社交网站Twitter在2011年上半年每天生成的tweet数据就高达2亿条。互联网上的海量信息，既包括了传统意义上的网页内容数据，例如，来自新闻、博客、微博、社区、论坛上的各类文本、图片、音频、视频数据，也包括了大量的用户行为数据，例如，用户的查询、浏览、打分、评论等行为产生的数据，还包括了各类结构关系数据，例如，链接关系、跟随关系。海量的网络信息是一把双刃剑，它既是超大规模的人类知识宝库，具有难以估量的价值，同时如何从非结构化、富噪声、高维稀疏的海量网络信息中发现有价值的知识，已经成为了网络信息处理与服务领域面临的巨大挑战。围绕着日益庞大的网络信息，检索与挖掘成为了这个领域研究的工作重点。回顾互联网发展的近30年，有大量的研究与应用工作沿着这个方向在不断探索发展并取得了一些重要的成果。

在网络信息的检索与挖掘领域，相关工作大致可以分为三个方向，即信息表达、信息挖掘以及信息检索。对信息表达的研究是信息检索与挖掘的基础。为了能够更好的让网络信息为用户服务，人们首先需要理解信息，进而正确地表达信息；对信息挖掘的研究，则主要关注如何从海量网络信息中发现内在规律，挖掘其蕴含的知识；而对信息检索的研究，则关注如何帮助用户快速高效的从海量信息中获取相关内容，以满足用户需求。

本文从这三个方向入手，简要回顾相关研究工作的进展，尝试厘清其发展变化的历程和趋势，一起回顾并总结在网络信息探索研究的道路上，我们已经走了多远？我们未来将走向何方？

2 信息表达

信息表达的方式代表了人们对信息的理解和认识程度，良好的信息表达形式是机器来求解问题的基本前提，对问题的有效解决起着举足轻重的作用。当前，虽然网络上各种类型的信息(包括文本、图片、音频、视频等)呈现出爆炸性的增长趋势，但文本仍然是信息交流和传播的主要载体，因此本文主要关注如何对文本信息进行表示建模。对文本信息进行表示和建模其目的是让计算机能够正确理解人类的语言，能够分析和表达出其中的语义信息，这是一个非常有趣但又极具挑战的问题。文本信息的表达经历了从浅层词语表达方式到深层语义表达方式这样一个历程，其中代表性的工作包括了向量空间表示(VSM)[1]、隐语义索引(LSI)[2]和概率话题模型(PLSA、LDA)[3-4]等。

早在1975年就已被提出的向量空间表示，就是将文档表示成具有代表性关键词的向量形式，这组关键词称为索引词项。向量中的每一个分项对应一个索引词项，每个分项的数值定义为权重。这样，文档就可以看成是由索引词项所构成的向量空间中的一个点。索引词项的权重体现了该词项描述文档语义内容的能力和重要程度，具有多种计算方式。经典的计算方式的是Salton等人[5]提出的TF-IDF权重，其中TF (Term Frequency)是词项频率，即词项在文档中的出现频率，体现了词项对文档的重要程度；IDF(Inverse Document Frequency)是逆文档频率，体现了词项对文档的区分程度。TF-IDF这种计算模式在一定程度上体现了类内聚合性和类间差异性，在文本检索和挖掘领域内得到了广泛的应用并取得了显著的效果。正所谓“瑕瑜互见”，向量空间表达方式虽然具有很多优点，但是没有能力处理自然语言的两个经典问题： 一义多词(synonymy)和一词多义(polysemy)。另外，向量空间表达方式容易产生高维稀疏性问题。

因而在1990年，Deerwester等人[2]提出了隐语义分析(Latent Semantic Analysis, LSA)。LSA的基本思想是将文档由高维表示空间映射到低维表示空间上。具体来说，就是通过奇异值分解(SVD)，将文档从词项空间映射到隐语义空间上。LSA的最终目的是为了表现词语与文档，词语与词语，以及文档与文档在隐语义空间内的语义关系。LSA在很多文本挖掘的实际问题中得到了应用，已经被证明是一个很有效的分析方法。但是，LSA方法的理论基础不完整，不能令人满意。另外，通过LSA方法得到的隐语义层无法得到很好的解释，而且不能真正解决一词多义的现象。

为此，在20世纪90年代末，Hofmann[3]提出了概率隐语义分析(Probabilistic Latent Semantic Analysis, PLSA)。PLSA的基本假设是文档中含有多个潜在的话题，并且文档中的每个词语产生于混合话题模型，其中话题用词语的多项式分布来表示。通过PLSA可以使用隐语义空间表示文档，其中隐语义空间的每一维就对应一个话题，所以 PLSA 也能够起到降维作用。相比于LSA，PLSA具有更为坚实的理论基础，对话题也有清晰合理的解释，同时也解决了一词多义的现象。然而PLSA并不是一个真正的产生式概率模型，因为话题的选择同具体的文档相关，同时也带来了待估参数过多的问题。

为了解决上述问题，Blei等人[4]在2003年提出了LDA话题模型。该模型的基本假设是文档的话题选择从一个先验分布(Dirichlet)中产生，因此它是一个贝叶斯模型。LDA具有了对新文档话题预测的能力，同时LDA模型也解决了PLSA模型需要估计的参数过多的问题。

概率话题模型(如PLSA和LDA)的提出，对网络信息检索与挖掘具有重要的意义。随着研究不断深入，话题模型被广泛的应用在各个领域，包括文本挖掘[6]，文档检索[7]，引用分析[8]，社会网络分析[9]以及情感分析[10]等。国内近几年对于信息表达方面的研究也取得了不少成果，很多研究工作提出了改进的话题模型[11-12]，以增强已有话题模型的学习能力，解决其跨领域的问题等等，从而使其能更好地应用于文本信息的表达。

尽管对信息表达的研究历经了很长的时间，但是对于海量网络信息的建模还面临着很多新的挑战。例如，对于海量文本信息的建模，我们需要模型能够对更大规模的参数空间进行有效的学习，需要能够有效的建模并解决信息的稀疏性所带来的问题，需要能够对动态演化的网络信息进行合理的表达。此外，对于图片和多媒体信息数据，我们也需要进一步探索其建模与表达方式，以便能够更加有效的表达其内在的语义信息。

3 信息检索

作为用户与数据进行交互的主要手段之一，信息检索的目的在于让用户更加容易的访问到所需要的信息。信息检索融合了数据的表示、组织、存储与检索等多个方面，包括了信息获取、信息索引、查询处理、信息排序、结果反馈等基本环节。为了能够提高信息检索的质量与效率，研究人员对各个基本检索环节都展开了深入的研究，其中包括了如何实现对海量网络数据高效友好的抓取[13]、对索引结构的不断优化[14]、对用户查询的处理与分析[15]、对结果排序质量的不断提高[16-17]等等。此外，还包括了对相关反馈的探索、对检索性能评价、跨语言检索、多媒体检索等研究。尽管信息检索领域涉及的研究工作十分广泛，但其围绕的核心问题始终是如何使用户需求和数据实现更好的匹配。检索模型作为用户查询与数据进行匹配过程的形式化表示，可以说是解决该核心问题的关键点。由于篇幅所限，我们下面就以检索模型的演化来窥视信息检索技术的发展。

相关性是信息检索中最基本的概念，它反映了用户对于检索结果的最基本的要求。因此检索模型的首要任务是如何定义相关性。早期的布尔模型[18]认为相关性是二值的，查询用布尔表达式表示，待检索对象构成一个集合，对集合中的每个对象采用完全匹配。布尔模型的优点在于形式简单，便于实现，但缺陷也是显而易见的，模糊的查询需求有时很难转换为精确的布尔表达式，检索结果的数量也不可控。向量空间模型[1]可以很好的解决这些问题，它认为文档和查询都可以表示为索引词构成的向量，用两个向量间的相似度来估计文档对于给定查询的相关性，从而克服了二值相关性假设带来的缺陷。向量空间模型能够反映不同索引词在文档中的重要程度，可以根据与查询的相似程度对文档进行排序，从而控制输出结果的数量，其不足之处在于文档表示形式的假设，认为表示文档的索引词之间是相互独立的，这一假设实际上不符合自然语言表达的实际情况，未能揭示词语之间的关系。这些经典的检索模型成为20世纪80年代人们的研究重点。

从20世纪80年代末开始，以BM25[19]为代表的概率模型出现，它将检索问题归结为求条件概率问题，有严格的数学理论基础，可以根据相关概率来排序从而控制检索结果的数量。但这类模型的相关性定义是抽象的，仍旧没有考虑关键词间的关系，需要手动选择最优参数。与传统的概率模型不同，统计语言模型[20]给出了相关性地清晰定义，认为每个文档对应一个统计语言模型，用该语言模型生成查询的概率来估计该文档与查询相关的程度。该模型摒弃了向量空间模型中的索引词集合的假设，利用语言模型建模关键词之间的上下文关系，n-gram模型[21]便是其中的典型代表。这类模型的共同缺点是计算量大，需要运用平滑技术来处理数据稀疏性问题，而数据稀疏性目前还没有一个放之四海皆准的解决方案。

近十年来，越来越多的研究工作关注排序学习算法。它将文档表示为特征项向量，利用成熟的机器学习算法自动从训练数据中学习出排序函数。其中的特征项既可以是文档的各种元数据信息，也可以是PageRank、BM25等传统检索模型的得分。它以损失函数为优化目标，寻找在检索领域中常用的评价准则(平均准确率(MAP)、归一化折扣累计增益(NDCG))下最好的排序函数。根据损失函数所定义的基本单位的不同，常见的排序学习算法可以分为逐点的(Pointwise，如McRank[22])，逐对的(Pairwise，如Ranking SVM[16]、RankBoost[17]、RankNet[18])和逐列的(Listwise，如ListMLE[19]、ListNet[20]、RankCosine[21]、AdaRank[22]、SVMMAP[23]、SoftNDCG[24])三类。排序学习算法避免了排序函数的定义过分依赖于经验以及人工调参数时可能带来的过拟合问题，便于融合一些优秀的检索模型。而且，尽管它使用的特征和学习算法都不是很复杂，但在检索效果上和目前可见的性能最好的检索算法相当，甚至更好。另外，在理论方面，使用统计机器学习理论的有效工具，排序学习问题的理论研究也得到了深入的发展，可以保证排序学习算法的整体性能。它的主要缺点在于学习是一个耗时的过程需要离线进行，算法的性能依赖于训练数据的质量。

对检索模型的研究也一直是国内信息检索领域的研究热点，包括清华大学、哈尔滨工业大学、大连理工大学、南开大学、中国科学院计算技术研究所在内的多个高校和科研机构都开展了很多相关的研究工作。这些研究工作包括有对现有排序学习算法的直接改进，如通过加入pointwise损失函数来改善pairwise方法的性能的排序学习方法[25]，分析排序学习算法对检索结果的有效性[26]等。

虽然现有的检索模型能够灵活有效地建模用户需求与数据之间的匹配关系，但对实际数据和用户需求的建模还存在很多不足。例如，用户需求往往是复杂多样的，因此相关性不应该是对于排序结果的唯一要求，需要结合多样性、重要性等多个不同的目标进行排序；而且实际数据往往多源异构且含有大量噪音，因此像排序学习这样对训练数据的质量有重大依赖的算法，必须要基于能够抗噪的检索模型。此外，用户需求通过简短的关键词查询来表达，所以对用户查询的深入理解、分析进而掌握用户的真实查询意图，将是检索成功的重要前提。

4 信息挖掘

信息挖掘是人们从海量的网络信息中发现其内在规律、获取其蕴含的知识的基本手段，它为构建更高智能的应用提供了基本信息原料。信息挖掘的研究历经了从早期围绕关系数据库中的数据信息，到如今面向海量的半结构甚至非结构化数据信息、用户产生数据信息的研究；从早期关注于挖掘数据信息的内在模式和规则，到如今更关心挖掘数据信息中包含的话题、实体、关系等多种类型的知识；在研究的对象、内容、方法上经历了一系列的演变，涌现出很多经典的模型和方法，但也正面临着很多新的挑战。

模式挖掘是早期信息挖掘的主要目标，即发现数据信息中隐藏的模式。20世纪90年代早期，随着关系数据库的流行，商业应用中出现了大量事务型数据信息，如何从中发现有价值的模式，成为商业智能亟需解决的问题。1993年，IBM的Agrawal等人提出了通过挖掘频繁项集来生成关联规则并支持决策的里程碑技术(Apriori算法)[27]。例如，将关联度高的啤酒和尿布摆放在一起，可以同时提高二者的销量。由于关联规律的普遍性和有用性，频繁项集成为最重要的模式之一。为解决频繁项集的挖掘问题，涌现了很多的挖掘算法。特别地，Han等人所提出的FP-Growth算法[28]，挖掘过程只需扫描数据库两次，从而有效地解决了Apriori算法需要多次扫描数据库所以难以处理大规模数据的问题，成为一种经典算法。

对频繁项集进行高效挖掘的研究如火如荼地持续到了21世纪初，从一开始挖掘压缩的频繁项集(如极大频繁项集挖掘[29]、频繁闭项集挖掘[30]和Top-K频繁项集[31])，到后来挖掘兴趣度高的频繁项集。频繁项集不仅可以用来计算关联规则，还成为聚类、分类以及众多数据分析应用的基础。随着信息技术的高速发展，涌现出各种海量的非事务型数据信息，包括文本数据、多媒体数据、空间数据、流数据、图数据、Web数据等，频繁项集的成功促使人们去发现其中特有的频繁模式。对于网络信息，频繁模式主要从三个方面进行挖掘： 结构数据 (如页面布局结构和超链接)、内容数据(如页面中文本、图片和多媒体数据)和用户使用数据信息(如Google对查询日志的频繁模式分析，Yahoo!基于频繁模式从社会标注数据中挖掘用户兴趣)。

近年来，对于网络信息的挖掘，人们更加关心的是如何从海量信息中获取其蕴含的内在知识，这样的知识包括了对命名实体、实体关系的挖掘等等。命名实体是现实世界中的具体或者抽象但具有特定意义的实体，例如，人、地点、组织等。在文本中，命名实体往往是信息的主要载体，是文本的核心语义单元，也是人们正确理解文本的基础。早期的命名实体挖掘研究主要集中在自然语言处理领域，是该领域的一项重要技术。随着Web上信息爆炸式的增长以及人们应用需求的增加，人们所关注的类型越来越多，粒度也越来越细，例如，电影、小说、游戏、科学家和政治家等等。

早在1991年，Rau[32]描述了一个能够抽取和识别公司名称的系统，该系统主要基于人工编写的启发式规则。但是手工编写规则需要有丰富的领域知识和语言学知识，同时还需要大量的人工分析来进行总结归纳，是一项非常耗时又费力的工作。伴随着机器学习的不断发展，相应的学习方法被引入了命名实体挖掘领域，包括监督式学习[33-34]，半监督式学习[35]和无监督式学习[36]，促进了命名实体挖掘技术的快速发展。随着大量用户行为数据信息(如查询日志)的积累，近年来有不少实体挖掘的研究工作专门针对这类数据展开(如文献[11，37])。

对实体关系挖掘的主要目标是发现不同类型实体之间的关系。实体关系包括二元实体关系和多元实体关系，大多数研究工作更加关注二元实体关系的挖掘。针对实体关系挖掘，研究人员提出了各种解决方法，包括了基于规则的方法[38-39]和基于机器学习的方法[40-42]。2007年，马里兰大学的Getoor等人提出了统计关系学习[43]，成为关系挖掘领域的里程碑技术。传统统计模型都是基于独立同分布的，它包含有两个基本假设，即统计模型的对象是同类型的，统计模型中的对象是不相关的。统计关系模型否定了这两个假设，认为模型中的对象类型不同且彼此之间有联系，因此统计关系学习可以更全面地表达领域知识。实体关系挖掘的研究工作同MUC、ACE等一系列评测会议和项目计划密切相关，这些评测会议对实体关系挖掘技术的发展起到了积极的推动作用。

目前，网络信息挖掘领域仍是互联网研究界最受关注的领域之一，有很多亟待解决的问题摆在人们面前。例如，对于频繁模式挖掘，我们面临的主要挑战是如何提高挖掘结果的有用性和可理解性；在实体和关系的挖掘方面，我们不但需要实现对互联网上开放领域的实体和关系的挖掘，而且需要解决对不断涌现的新的实体和关系的挖掘问题。此外，我们还需要进一步考虑如何能够更好的组织、管理通过信息挖掘所获取的知识，如何构建大规模高效率的知识库、本体库和语义网络等等。

5 总结与展望

综上所述我们可以看到，在面向海量网络信息的研究领域，为了能够让网络信息更好地为用户服务，人们分别从信息表达、信息检索、信息挖掘三个方向展开了广泛而深入的研究。通过结合统计分析、机器学习等方法，人们对非结构、富噪声、高维稀疏的网络信息进行了更好地建模与分析。通过这些研究工作，人们对信息的表达更加准确，对语义的理解不断深化。在此基础之上，人们应用于信息检索与挖掘的技术愈加的智能有效，从而也催生了很多成功的应用与服务。

回顾历史，我们很高兴地看到，海量网络信息检索与挖掘领域在过去的三十年里不断的发展壮大，取得了累累的硕果。然而真正利用海量网络信息，为人们提供智能应用，服务于人们的信息需求，人们还面临着很多实际的挑战，包括数据规模带来的复杂度和可扩展性的挑战，数据的多源异构带来的融合分析的挑战，数据的动态演化带来的适应性的挑战等等。正如2008年Nature杂志以“Big Data”为主题的专刊提到，互联网中蕴含着人类有史以来可访问的最大量信息，如何通过对海量信息的融合分析，充分发掘其信息价值为用户提供服务，将是我们面临的巨大机遇与挑战。鉴于已经取得成果，我们有理由相信对于网络信息检索与挖掘的研究，必将会有越来越广阔的空间。

[1] G. Salton, A. Wong, C. S. Yang. A vector space model for automatic indexing[J]. Communications of the ACM, 1975，41(6)：613-620.

[2] S. Deerwester, S. T. Dumais, G. W. Furnas, et al. Indexing by latent semantic analysis[J]. Journal of the American Society for Information Science, 1990，41(6)： 391-407.

[3] Thomas Hofmann. Probabilistic latent semantic indexing[C]//Proceedings of the 22ndannual international ACM SIGIR conference on Research and development in information retrieval, SIGIR’99, 1999: 50-57.

[4] David M. Blei, Andrew Y. Ng, Michael I. Jordan. Latent Dirichlet allocation[J]. Journal of machine learning research, 2003， 3：993-1022.

[5] Gerard Salton, Edward A. Fox, Harry Wu. Extended Boolean information retrieval[J]. Communications of the ACM. 1983，26(11)： 1022-1036.

[6] Cheng Xiang Zhai, Atulya Velivelli, Bei Yu. A cross-collection mixture model for comparative text mining[C]//Proceedings of the 10th ACM SIGKDD international conference on Knowledge discovery and data mining, KDD ’04, 2004: 743-748.

[7] Xing Wei, W. Bruce Croft. LDA-based document models for ad-hoc retrieval[C]//Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, SIGIR ’06, 2006: 178-185.

[8] Laura Dietz, Steffen Bickel, Tobias Scheffer. Unsupervised prediction of citation influences[C]//Proceedings of the 24th international conference on Machine learning, ICML ’07, 2007: 233-240.

[9] Qiaozhu Mei, Deng Cai, Duo Zhang, et al. Topic modeling with network regularization[C]//Proceeding of the 17th international conference on World Wide Web, WWW ’08, 2008: 101-110.

[10] Yue Lu, Chengxiang Zhai. Opinion integration through semi-supervised topic modeling[C]//Proceeding of the 17th international conference on World Wide Web, WWW’08, 2008, 121-130.

[11] Jiafeng Guo, Gu Xu, Xueqi Cheng, et al. Named entity recognition in query[C]//Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval, SIGIR ’09, 2009, 267-274.

[12] Fuzhen Zhuang, Ping Luo, Zhiyong Shen, et al. Collaborative Dual-PLSA: Mining Distinction and Commonality across Multiple Domains for Text Classification[C]//Proceedings of the 19th ACM Conference on Information and Knowledge Management, CIKM ’10, 2010, 359-368.

[13] Lee, Hsin-Tsang, Leonard et al. IRLbot: scaling to 6 billion pages and beyond[C]//Proceedings of the 17th international conference on World Wide Web, WWW ’08, 2008: 427-436.

[14] Ruijie Guo, Xueqi Cheng, Hongbo Xu et al. Efficient on-line index maintenance for dynamic text collections by using dynamic balancing tree[C]//Proceedings of the 16th ACM Conference on Information and Knowledge Management, CIKM ’07, 2007: 751-760.

[15] Jiafeng Guo, Gu Xu, Hang Li et al. A unified and discriminative model for query refinement[C]//Proceedings of the 32nd international ACM SIGIR conference, SIGIR ’08, 2008: 379-386.

[16] T. Joachims. Optimizing Search Engines Using Clickthrough Data[C]//Proceedings of the ACM Conference on Knowledge Discovery and Data Mining, KDD ’02, 2002: 133-142.

[17] Yoav Freund, Raj Iver, Robert E, et al. An efficient boosting algorithm for combining preferences[J]. Journal of machine learning research. 2003, 4: 933-969.

[18] F. W. Lancaster, E. G. Fayen. Information Retrieval On-Line[M]. Melville Publishing Co., 1973.

[18] Chris Burges, Tal Shaked, Erin Renshaw, et al. Learning to rank using gradient descent[C]//Proceedings of the International Conference on Machine Learning, ICML ’05, 2005: 89-96.

[19] Karen Sp rck Jones, Steve Walker, Stephen E. Robertson. A Probabilistic Model of Information Retrieval: Development and Comparative Experiments (parts 1 and 2)[J]. Information Processing and Management, 2000， 36(6)： 779-840.

[19] Fen Xia, Tie-Yan Liu, Jue Wang, et al. Listwise Approach to Learning to Rank -Theory and Algorithm[C]//Proceedings of the International Conference on Machine Learning, ICML ’08, 2008: 1192-1199.

[20] J. M. Ponte， W. B. Croft. A Language Modeling Approach to Information Retrieval[M]. Research and Development in Information Retrieval, 1998： 275-281.

[20] Zhe Cao, Tao Qin, Tie-Yan Liu, et al. Learning to Rank: From Pairwise Approach to Listwise Approach[C]//Proceedings of the International Conference on Machine Learning, ICML ’07, 2007: 129-136.

[21] Frederick Jelinek. Markov Models and Linguistic Theory : An Experimental Study of a Model for English[M]. Mouton De Gruyter, The Hague, 1971.

[21] Tao Qin, Xu D. Zhang, Ming F. Tsai, et al. Query-level loss functions for information r etrieval[J]. Information processing and management, 2008， 44(2)： 838-855.

[22] Jun Xu, Hang Li. AdaRank: a boosting algorithm for information retrieval[C]//Proceedings of the 31nd international ACM SIGIR conference, SIGIR ’07, 2007： 391-398.

[22] P. Li, C. Burges, Q. Wu. MCRank: Learning to rank using multiple classification and gradient boosting[C]//Proceedings of Advances in Neural Information Processing Systems, NIPS ’07, 2007.

[23] Y. Yue, T. Finley, F. Radlinski, et al. A Support Vector Method for Optimizing Average Precision[C]//Proceedings of the 31nd international ACM SIGIR conference, SIGIR ’07, 2007: 271-278.

[24] Michael Taylor, John Guiver, Stephen Robertson et al. SoftRank: optimizing non-smooth rank metrics[C]//Proceedings of the international conference on Web search and data mining, WSDM ’08, 2008: 77-86.

[25] 吴佳金, 杨志豪, 林原, 等. 基于改进Pairwise损失函数的排序学习方法[C]//第六届全国信息检索学术会议论文集, 2010.

[26] Min Zhang, Da Kuang, Guichun Hua et al. Is learning to rank effective for Web search[C]//SIGIR 2009 workshop: Learning to Rank for Information Retrieval. 2009.

[27] Rakesh Agrawal , Tomasz Imieliński , Arun Swami. Mining association rules between sets of items in large databases[C]//Proceedings of the 1993 ACM SIGMOD international conference on Management of data, SIGMOD’93, 1993: 207-216.

[28] Jiawei Han, Jian Pei, Yiwen Yin. Mining frequent patterns without candidate generation[C]//Proceedings of the 2000 ACM SIGMOD international conference on Management of data, SIGMOD ’00, 2000: 1-12.

[29] Douglas Burdick, Manuel Calimlim, Johannes Gehrke. MAFIA: A Maximal Frequent Itemset Algorithm for Transactional Databases[C]//Proceedings of the 17th International Conference on Data Engineering, ICDE’01, 2001: 443-452.

[30] Nicolas Pasquier, Yves Bastide, Rafik Taouil, et al. Discovering Frequent Closed Itemsets for Association Rules[C]//Proceedings of the 7th International Conference on Database Theory, ICDT ’99, 1999: 398-416.

[31] Jianyong Wang, Jiawei Han, Ying Lu, et al, TFP: An Efficient Algorithm for Mining Top-K Frequent Closed Itemsets[J]. IEEE Transactions on Knowledge and Data Engineering, 2005， 17(5)： 652-664.

[32] Lisa F. Rau. Extracting company names from text[C]//Proceedings of Seventh IEEE Conference on Artificial Intelligence Applications, CAIA’91, 1991： 29-32.

[33] Hai Leong Chieu, Hwee Tou Ng. Named entity recognition: a maximum entropy approach using global information[C]//Proceedings of the 19th international conference on Computational linguistics, COLING ’02, 2002, 1: 1-7.

[34] Fabio Ciravegna. Adaptive information extraction from text by rule induction and generalisation[C]//Proceedings of the 17th international joint conference on Artificial Intelligence, IJCAI’01, 2001, 2: 1251-1256.

[35] Ellen Riloff, Rosie Jones. Learning dictionaries for information extraction by multilevel bootstrapping[C]//Proceedings of the 16th national conference on Artificial intelligence, AAAI’99, 1999: 474-479.

[36] Enrique Alfonseca, Suresh Manandhar. An unsupervised method for general named entity recognition and automated concept discovery[C]//Proceedings of the 1st International Conference on General WordNet, 2002.

[37] Marius P. Weakly-supervised discovery of named entities using web search queries[C]//Proceedings of the 16th ACM Conference on information and knowledge management, CIKM ’07, 2007：683-690.

[38] Roman Yangarber, Ralph Grishman. Nyu: description of the proteus/pet system as used for muc-7[C]//Proceedings of the 7th Message Understanding Conference, MUC’98, 1998.

[39] Chinatsu Aone, Mila Ramos-Santacruz. Rees: a large-scale relation and event extraction system[C]//Proceedings of the 6th conference on Applied natural language processing, ANLC ’00, 2000: 76-83.

[40] Dmitry Zelenko, Chinatsu Aone, Anthony Richardella. Kernel methods for relation extraction[J]. Journal of machine learning research, 2003，3： 1083-1106.

[41] Jun Zhu, Zaiqing Nie, Xiaojiang Liu et al. Statsnowball: a statistical approach to extracting entity relationships[C]//Proceedings of the 18th international conference on World wide web, WWW’09, 2009: 101-110.

[42] Takaaki Hasegawa, Satoshi Sekine, Ralph Grishman. Discovering relations among named entities from large corpora[C]//Proceedings of the 42nd Annual Meeting on Association for Computational Linguistics, ACL ’04, 2004.

[43] Lise Getoor， Ben Taskar. Introduction to Statistical Relational Learning[M]. Adaptive Computation and Machine Learning, The MIT Press, 2007.