2.4 基于开放网络知识库的数据挖掘

基于开放网络知识库的数据挖掘包括3方面内容，即线索挖掘、关系推理和关系预测。

2.4.1 线索挖掘

利用开放网络知识库进行线索挖掘，是指利用知识库对两个原本无关联的实体或概念做关联，给出两个实体间的关联路径或关联的模式，或称为storytelling[55，56]。例如，如果要回答奥巴马和比尔·盖茨之间的关系路径是什么，还有哪些实体和他们有关，这些相关性的证据是什么，都要通过实体关联来解决。相关的方法都是将知识库当作图来处理，图中每个点代表一个实体或概念，边代表实体间关系、概念间关系以及实体和概念间的关系。然后，将关联任务转化为基于图的各种操作，例如寻找导出子图、特定的子结构、连通分支等。这里主要介绍两个有代表性的方法。

Hossain等人[56]提出了一种基于团（clique）的实体关联方法，该关联方法在两个节点间构造一条路径，路径上相邻两点以及一些其他点构成事先设定的大小的团结构。如图2-5所示，在关联实体J．Escalante和A．Sufaat时，构造的路径用粗线条标示了出来，这条路径上的相邻两个点连同其他外部节点（如Feb 22，2003、Arze、Cuban Intell、Escalante）构成大小为6的团结构。生成这样的团结构，补充了很多外部信息，可以更好地解释两个实体间的关联，增加更多的线索。基于团的实体关联主要通过3个步骤来实现，首先利用CHARM-L算法[57]生成概念格（concept lattice），然后利用A∗算法产生路径上的候选节点并评估这些候选节点以确定最终的路径。

相比于基于团的实体关联方法得到的只是一条路径的方法，Fang等人[58]提出了基于关系解释（relation explanations）的知识库中实体关联的方法REX，可以返回关联两个实体的比树和路径更为复杂的连通结构，对关联给出更详细的解释。该系统主要包括解释枚举（explanation enumeration）和解释排序（explanation ranking）两部分。在解释枚举部分，系统从知识库中海量的实体中通过定义覆盖路径模式集（covering path pattern set）这一典型的结构来快速识别出能够关联两个实体的候选实体，在解释排序环节，系统定义了基于结构、基于分布和聚集性等多重度量指标用以衡量解释枚举环节得到的候选实体的相关性（interestingness），并按照这些指标对候选实体进行排序。

对大规模知识库中的实体做线索关联，面临很多的挑战。由于知识库中存储的知识规模越来越大，因而对关联的效率、实时性和准确性的要求越来越高。由于知识库的构建并不是完美的，知识库中的数据存在噪声、错误、不一致等情况，如何开发设计出扩展性强、抗噪声能力高的线索挖掘方法，是下一步研究的方向。

2.4.2 关系推理

基于开放网络知识库的关系推理，是指利用知识库现有的实体间关系推断或推理实体间潜在的、隐含的关系。例如，推理人物间的爷孙关系，前提是A是B的父亲，B是C的父亲，则通过关系推理功能，可知A是C的爷爷。利用知识库进行实体间关系推理，目前流行的方法主要有基于规则的方法，即利用机器学习领域中的归纳逻辑编程（inductive logic programming）技术的方法，例如基于一阶Horn子句或一阶归纳逻辑（FOIL）[59，60，61]以及基于概率图的方法，如随机游走[62]、Markov逻辑网络[63，64]等。前者典型的工作有NELL[60]，后者包括Schoenmackers等人[63，64]提出的Sherlock-Holmes方法。

NELL系统采用一阶Horn子句的方法推理实体关系。例如，它会使用如下的Horn子句：

AthletePlaysForTeam（x，y）∧TeamPlayInLeague（y，z） ⇒AthletePlaysInLeague（x，z）

来推断关系AthletePlaysInLeague（HinesWard，NFL）。如果子句里x，y和z分别取值为HinesWard，PittsburghSteelers和NFL，NELL系统学习Horn子句规则的方法是FOIL算法的变形，即N-FOIL算法。N-FOIL将大量正例和反例作为训练数据输入到系统中，例如AthletePlaysInLeague（HinesWard，NFL）是正例，而AthletePlaysInLeague（HinesWard，NBA）是反例，然后利用分而治之（divide-and-conquer）策略学习满足训练数据的Horn子句。每条Horn子句都是通过从对一般规则的特殊化来实现的，使得规则始终覆盖大部分正例和极少的反例。若一个子句通过学习得到，则被该子句覆盖的例子从训练数据中移除，然后迭代地进行下一个子句的学习，直到训练数据中没有正例。之所以采取N-FOIL算法，是因为用FOIL算法学习一阶Horn子句的计算代价很高，不仅搜索空间很大，而且有些Horn子句的得出代价很高。N-FOIL算法通过预处理等技巧来缩小搜索空间，增强FOIL算法的扩展性。尽管如此，NELL系统仍然需要人工编写和指定初始的规则，而且对学习到的规则缺乏有效的评估机制以应对知识库中数据的噪声问题。所以需要一个对规则的评分函数（scoring function）来应对噪声问题，由Schoenmackers等人[63]提出的Sherlock-Holmes方法提出了这样一个评分函数。

Sherlock-Holmes是基于开放领域文本的关系推理方法，该方法分为线上部分Sherlock和线下部分Holmes。Sherlock学习推理规则，将规则输入到Holmes推理引擎中，利用这些规则对推理查询做出回答。详见图2-6所示。具体地，Sherlock输入已有的实体关系或事实，利用Hearst pattern（如such as模式）识别出具有代表性的实体的类别和这些类别的实例，然后发现类别间关系，通过穷举搜索，如MCMC（Markov chain Monte Carlo）抽样方法推出推理规则，并通过统计相关性检验的方法计算每条推理规则的置信度，输出通过评分函数计算的带权重的Horn子句逻辑规则。Holmes将Horn子句逻辑规则、知识库中的实体间关系以及使用规则表示的查询作为输入，对满足对查询条件的实体间关系构建证据树，把证据树转化为Markov逻辑网络，使用Markov逻辑网络推理相应节点的概率，输出满足条件的隐含关系及其置信度。这里的Markov逻辑网络推理是指在Markov网络中加入边从而产生一系列的团结构（cliques）。根据Markov网络的理论，每个这样生成的团k都具有一个势函数φk，返回基于团中变量状态的非负值。记状态x的概率为P(x)，则P(x)满足

其中，Z是正规化因子，x{k}是团k中所有变量的状态。对于原先证据树中的叶子节点，其概率可以通过知识库计算出来，对于需要推断的节点概率事先赋予一个指数先验。最后利用loopy belief propagation方法，进行近似推理。

Holmes推理新关系采用的Markov逻辑网络方法需要事先由人来编写少量推理规则。而Lao等人[65，66]提出了基于路径排序算法（path ranking algorithm，简称PRA）的知识库关系推理方法[61]，可以从训练数据中自动发现推理规则，而且采用了有效的近似推理方法，从而比Markov逻辑网络的方法具有更高的效率。PRA方法相对于每个查询点x，给关系图中的其他节点y做排序。PRA方法首先枚举生成所有的关系路径，将每条这样的路径当做训练的专家（ranking experts），产生一条随机游走。当达到稳定状态时，给每个点y赋予一个概率值，根据这些概率值，对节点y进行排序。最后，PRA通过logistic回归对这些专家进行加权统计。具体而言，对于知识库中的每个关系R，给定概念x，该方法试图寻找其他所有的概念y，使得x和y满足关系R（x，y）。定义关系路径P为关系R1，R2，…，Ri的序列。为了强调每一步关系的类型，P还可以写成，其中，Ti=range (Ri)=dom ain(Ri+1)。记dom ain(P)=T0，range(P)=Ti。对每条关系路径P=R1，…，Ri和种子点x，路径型（path constrained）随机游走给每个点y都定义了一个分布hx，P（y）。当P是一条空路径时，如果x=y，则hx，P(y)=1，否则hx，P(y)=0。当P不为空时，假定P′=R1，…，Ri－1，则hx，P（y）迭代定义如下：

其中，是从节点y′到节点y的所有长度为1的随机路径的类型是Ri的边的概率。标示了是否存在一条类型为R的从y′到y的边。更一般地，给定关系路径集合P1，…，Pn，可将每个hx，P（y）进行如下线性加权：

θ1hx，P1（y）+θ2hx，P2（y）+…+θnhx，Pn（y）

得到节点y的相对于节点x的打分score（y，x），其中，θi为路径Pi的权重，score（y，x）的定义如下：

其中，Pi是长度为l的关系路径集合。Lao等人[61]提出的基于知识库的关系推理方法对PRA方法做了两方面的改进，以应对知识库中大量的关系和提高推理的准确性。

对知识库中的实体关系进行推断，是近几年研究的热点也是难点问题，如何应对在超大规模知识库中对关系进行精确的推理，以及对推理结果的可信度进行有效判定，是下一步工作需要解决的问题之一。

2.4.3 关系预测

对大规模知识库的实体关系做预测，试图对实体间关系的时序变化做出定量和定性的预测，包括预测是否会产生关系、关系的类型变化、关系的置信度变化、关系发生的频次等。与关系推断不同，对关系的预测是对未来实体间可能发生的关系进行判定。这方面有代表性的工作都是基于机器学习等方法实现的，包括有监督的学习方法和无监督的学习方法。例如，依托社交网站构建的实体关系网络，存在预测两个用户在未来是否会有链接关系存在即Link Prediction问题。针对该应用场景下的关系预测问题，有监督的学习算法是将预测问题视为分类问题。比较有代表性的工作包括文献[67，68]。尽管有监督的学习算法是目前比较流行的算法，但它在分类特征选择方面经常会面临不平衡性（imbalance），必须依赖于实验数据集的先验分布知识，因而预测结果准确率不高。为了解决这一问题，有学者提出了基于非监督的学习算法的关系预测方法。这类方法试图在两个用户之间定义一个合理的相似度指标，越相似的用户越有可能产生关系。非监督的方法不用考虑关系预测的数据集的先验分布知识，因而准确度较高。经典的相似度指标包括Adamic-Ada指标[69]、优先连接或择优连接（preferential attachment）指标[70]、Katz指标[71]、结构相似度的指标[72]以及行为相似度的指标[73]等。基于上述几个指标的非监督关系预测方法在真实数据集上的效果比较已有大量的研究工作，例如Jia等人[73]使用在线微博数据发现基于行为相似度和结构相似度的关系预测方法在F1值等指标上相比上述其他几种非监督关系预测方法取得了更好的效果。其他相关比较工作可参照文献[72，74]等。

对知识库中实体间关系进行预测，可以在一定程度上推动对知识库的更新工作。反过来，知识库的更新又可以验证关系预测的准确性。所以，将知识库的更新和关系预测进行更好的结合，是重要的研究方向。