对基于种子的关系挖掘的经典论文的总结

1、对基于种子的关系挖掘的经典论文的总结摘要：本文主要简要总结了基于种子的关系挖掘的儿篇经典论文。基于种子的关系挖掘, 相对于基于聚类的关系挖掘，其主要特点是在对语料库或网络信息进行处理时，需要少 量种了元组作为输入，在具体算法的处理过程中，通常会用到迭代等方法。从对这几篇 论文的纵向比较可以看出其慕于种了的关系挖掘算法的发展脉络。关键字：关系挖掘 种了元组 模型 迭代算法一、背景介绍随着网络的不断发展,web网已成为一个大的分布式信息空间。关系挖掘就是指 利用各种关系挖掘算法，从信息量很可观的网络中挖掘出两个或多个实体中存在的各种 关系。同其它网络数据挖掘类似，关系挖掘要处理的信息量大。一般都是

2、开放的万维网 或相当大的语料库。处理所得结杲的规模也比较大，否则不具有较高的应用价值。关系 挖掘在关系挖掘领域，已有学者做出大量研究，总结出两大类关系挖掘的算法：基于种 子的关系挖掘算法及基于聚类的关系挖掘算法。这两种算法所采用的机理不同，各有自 己的优势及缺点。基于种子的关系挖掘，相对于基于聚类的关系挖掘，其主要特点是在对语料库或网 络信息进行处理时，需要少量种子元组作为输入。根据其种子元组的关系特点，进行下 一步的关系抽取处理，通常会用到迭代等方法。从具算法的根本思想可以看出，基于种 了的关系挖掘方法对种了元组有一定的依赖。选取的种了元组的优劣，会对最终的抽取 结果产生一定的影响。棊于聚类

3、的关系挖掘，与之相反，则不需要若十元组进行输入，而是利用一定的聚 类算法，対语料库中的各实体対进行分析处理，将关系相近的一类实体对聚成一类，再 利用特定算法，解析出他们的关系，即实现关系挖掘的过程。对于基于种了的关系挖掘，已有很多学者对其进行长时间的研究，其成果也都在发 表的论文中有所体现。关系挖掘领域的若干经典论文，和这些论文提出的算法如 extracting patterns and relations from the world wide web(sergey brin,1997)提出的 dipre 算法，为以后的基于种子的关系挖掘算法奠定了基础。很多后來的研究都是在这些经典 论文的基

4、础之上的。而本文就是对基于种了的关系挖掘的经典论文做出归纳和总结，以 理清关系挖掘领域基于种子的挖掘算法的发展脉络，以为后而的学习与研究提供提示与 参考。本方将要涉及到的经典论文如卜：extracting patterns and relations from the world wide web (in international workshop on the web and database, 1998), snowball: extracting relati ons from large plain -text collect! ons (in in ternatio nal con

5、fere nee on digital libraries, 2000), statsnowball: a statistical approach to extracting entity relationships(ln the proceedings of the 18th international world wide web conference, 2009).这儿篇论文都 是基于种子的关系挖掘方法的经典论文。但其所使用的算法及思想也存在着交义与递 进。本文将以由简到繁，由易到难的顺序依次介绍这儿篇论文。介绍时分别以文章的目 的，思想(算法)，及其做出的探索为改进为线索依次介绍。、

6、经典论文介绍extracting patterns and relations from the world wideweb这篇论文及其提出的dipre算法为后来关系挖掘领域的相关研究奠定了基础。很多 后來基于种了的算法研究都是以这篇论文为基础，进行了扩展和完善。后续的算法虽然 不断改进，但是其根本思想还是由dipre算法沿袭而來。这篇文章主要探索的日标是从 信息量大且信息极其分散的万维网中抽取出具有一定关系且数量可观的元组对。朝着这个目标，作者提出了关系抽取算法一一dipreo在描述这个算法z前，作者首 先讨论了模型与关系两者间的双重对应特点。简而言之，就是如果两个实体（即一对元 组）间存在

7、一定关系，那么在数据量庞大的万维网数据库屮，这两个实体出现时一般情 况下会存在若干个模型与之相对应。而对于两个总是以若干一定模型出现的实体來说， 它们之间很可能存在着某种关系。基丁这个思想，作者引入了利用关系与模型的这种特 点的dipre算法。在具体的算法中，为了算法的最终实现，作者对模型及关系都采用了 数学的方式，进行了精准的定义。算法的大体思想如下：1. 根据已经得到元组（第一次迭代则是手工输入的种子元组），从语料 库屮找到这些种子元组共现的上下文。2. 从这些上下文关系中，根据耍求提取出这些种子元组共现时的模型。3. 根据规则对模型进行筛选，确定出若干可用的模型。4. 将这些模型投入到语

8、料库中，与若干元组进行匹配，根据匹配结果, 得到一些新的、满足所给的种子元组关系的元组对。5. 如果已经得到足够数量的元组对，或者，多次迭代元组数量无显著 增长，则停止算法，否则返回第-步。文章还对算法运行过程中的一些参数或阈值进行了讨论。如在对根据现 上下文所得到的模型进行评估时，引入了特异度参数，来描述这个模型的优劣。值得提 出的一点是，算法运行过程屮，还需要少量的人工干预。根据作者棊于此方法进行的实 验结果可以看出，dipre算法棊木解决了关系二元组的抽取问题，并取得可以接受的右 冋率与准确率。2snowball: extracting relations from large plai

9、n-textcollections这篇论文系统介绍了 snowball系统，这个系统的构造止是基丁的sergey brin的 dipre的算法z上的。上篇论文相比，这篇论文的基本思路及方法没有大的变化。在 具构建成的snowball系统屮，一匸要有两个人的改进措施。一是在弓i入命名标签机制，在 确认实体对的标签之前，首先对各个实体打上属性标签（这一行为可由专门的命名实体 标签工具來做），这样做可以提高产出模型及抽取关系元组的正确率。二是引入了专门 的、具有一定规模的评估模型及元组质量的评价系统。dipre虽然也对模型进行了评价, 但是其评价方式比较粗略耳笼统。从后来的对比实验可以看出，snow

10、ball系统中的评估 系统，可有效提高最后抽取的元组的质量。snowball系统主要曲以下儿个部分构成八h.各部分的功能阐述如下：1. 找到共现对。即根据系统输入时的种子元组，到待进行关系挖掘的语料库中搜索到所有种子元组的共现对。2. 对实体打标签。衣snowball系统中，实体是具有标签的，h.关系挖 掘过程屮所产生的模型也是具冇标签的。在对模型的匹配过程屮，共现实体对不仅 仅耍匹配模型中的上下文定义，而且对应实体的标签属性也要相匹配，才能被认为 是一个模型相匹配。3. 产牛模型。在snowball系统屮，模型被定义为一个五元组，且对应 表示上下文的三个向量（left, middle, ri

11、ght）具有权重，权重体现了每个项目在相对 的上下文屮的重要程度。产生模型的算法，与在dipre算法中的思想基木一致。都 是根据多对共现实体对的上下文相同的部分来产牛模型。4. 对产生的模型进行评估。这是该系统为dipre系统的主要不同。在 本文中，作者引入了多个参数（如可信度，对数可信度），来考察产生的模型及后文 要提到的抽取的元组的质量。在这个评估体系中，作者首先用高质量的种子元组來 评佔模型，得到高质量的模型后，乂反过來用这些模型來评价新抽取得到的元组。5. 抽取元组。即通过经过过滤的模型，放回到语料库中进行元组匹配, 最后得到一定数量的元组。6. 评估元组。在对模型的评价中12经提到，

12、该系统还会对产生的元组 进行评价。在评估元组屮，系统会通过元组与高质量模板的匹配程度，來计算出该 元组的可信度。同dipre算法类似，snowball系统没有解决关系抽取过程中需耍人工干预的问题。 但该系统对模型的精准定义上有了很大的改进，提高了关系抽取过程的效率与准确率。 同时，该系统对模型及元组的质量的评估做出了很大的探索，形成了一个规模化了评估 体系。通过实验数据，可看出应用该体系斤，抽取元组的止确率和准确率有了大幅提升。3. statsnowball: a statistical approach to extracting entityrelationships基于snowball系

13、统，微软亚洲研究院的研究人员对英进行改进，引入了 mln （马 尔可夫逻辑网络）來评判模型的质量，提出了 statsnowball系统模型。与snowball相比, 此系统对mle （最大似然估计）的应用，使得系统在评估与选择模型上更为精准。在此 系统中，模型中每一项h权重的确定可以通过mln学习自动得到，而不像snowball系 统还需要专门的启发式规则来确定每一项目权璽。同时，statsnowball易于扩展。该系统的总体可以分为以下几个部分，每个部分的功能阐明如下：1. 输入部分。同其它基于种了的关系挖掘系统类似，statsnowball系统需要少量种了元 组作为输入，以启动后续挖掘的迭

14、代过程。2. 模型训练。得到种子元组后，statsnowball会在线对种子元组进行学习，得到一系列 模型。在这个过程中，statsnowball的模型产生算法与snowball大同小异。值得指 出的是，同snowball采用启发式限制不同，statsnowball系统采用了概率模型来训 练关键字与模型。这样一来，statsnowball系统克服了若干snowball的缺点，可以 同等的处理特定模型及一般模型。3. 模型筛选。针対某些种子元组得到了若干关系模型后，还要对模型进行筛选。木文 所涉及的模型筛选问题，可以看作是一个马尔克夫随机场中的特征消减问题。statsnowball系统应用了 l

15、l-norm的mle来定义并解决这个问题。本文针对传统的 snowball所应用的评估筛选方法及文中所采用了方法进行了对比实验，结果表明， 这一改进显著提高模型质量，并最终提高了元组准确率与召冋率。4. 产生元组。利用上一步所得模型，到开放环境中进行元组匹配和关系抽取。将得到 的元组投入到下一轮的迭代过程中去。5. 关系聚类。对产生元组，运用一定的聚类算法，对其进行聚类处理。并获得聚得的 每一类的关键词，以标记这一类元组的关系属性。由此可以看岀，statsnowball系统是对snowball系统的进一步加工与细化。基于这 个系统研制开发而成的人立方系统已投入使用，并在不断的进行着改进和优化。

16、!1!总结山以上介绍可以看岀，这三篇基于种子的关系挖掘论文在其上一篇的基础上思想在 一脉相承，方法上不断的做岀了探索与改进，以得到更高的准确率及召回率。每一篇所 对应系统或算法跟前一篇相比都做出了改进。在对某一领域的研究中，这一现象或作法 是相当普遍的，对于一个初步提出的笼统的算法或思想，其理论或指导思想上比较成熟, 但在实际的实现上还可能有不少的可以改进的空间。我们可以结合其它领域用到的思维 方法，对这一算法或系统的某部分进行优化，从而达到了对这一问题更为深入的探索， 同时也可能得到解决这一问题的更好方式。参考文献1 s. brin. extract! ng patter ns and re

17、lati ons from the world wide web (in inter national workshop on the web and database, 1998).2 s no wball: extracti ng relati ons from large plain -text collect! ons (in in ter national con fere nee on digital libraries, 2000).3 statsnowball: a statistical approach to extracti ng en tity relati on sh

18、ips (in the proceed! ngs of the 18th international world wide web conference, 2009).4 proceedi ngs of the sixth message un d erst a nding con fere nce.( morga n kaufma n, 1995).5 un supervised models for n amed en tity classificati on. (in proceed! ngs of the joint sig- dat conference on empirical methods in natural language processing and very large corpora, 1999).6 lear ning to con struct kno wledge bases from the world wide web, (mark crave n, dan dipasquo, dayne f