(12)发明专利申请
(10)申请公布号 CN 106250412 A(43)申请公布日 2016.12.21
(21)申请号 201610583823.0(22)申请日 2016.07.22
(71)申请人 浙江大学
地址 310027 浙江省杭州市西湖区浙大路
38号(72)发明人 鲁伟明 戴豪 庄越挺 (74)专利代理机构 杭州求是专利事务所有限公
司 33200
代理人 刘静 邱启旺(51)Int.Cl.
G06F 17/30(2006.01)G06F 17/27(2006.01)
权利要求书3页 说明书8页 附图2页
CN 106250412 A(54)发明名称
基于多源实体融合的知识图谱构建方法(57)摘要
本发明公开了一种基于多源实体融合的知识图谱构建方法。本发明首先爬取中文三大百科：百度百科、互动百科，维基百科，并对数据做预处理，包括标题同义词提取、消岐页面提取、候选集提取和文本分词等。然后，针对在同一个候选集里的页面，计算两两页面之间的特征，并训练分类器计算页面之间的相似度，并根据相似度构建权重图。最后，通过混合线性规划模型，约束权重图中顶点与顶点之间的关系，通过计算目标函数的最大值，得到顶点与顶点之间的连通性，将每一个连通分量当作一个实体，从而获得描述同一个实体的所有页面。本发明通过引入候选集，大大减小了问题的规模；同时又通过混合线性规划模型，提高了实体融合的准确率。
CN 106250412 A
权 利 要 求 书
1/3页
1.一种基于多源实体融合的知识图谱构建方法，其特征在于，包括以下步骤：1)预处理百科页面：提取百科标题的同义词，提取消岐页面，利用同义词的传递关系构建同义词组，所有同义词组形成同义词组集合，根据同义词组集合中每一个同义词组对应的页面构建候选集，用分词工具对百科页面的文本进行分词。
2)通过步骤1)的分词结果，计算同一个候选集里的两两页面之间的特征，通过训练分类器为每一维特征赋上不同的权重，并利用这个分类器计算页面之间的相似度。
3)根据步骤2)中计算的页面之间的相似度构建该候选集的权重图，利用混合线性规划模型，定义该模型目标函数，并计算目标函数的最大值，得到顶点与顶点之间的连通性。将权重图上的每一个连通分量当作一个实体，从而获得描述同一个实体的所有页面。
2.根据权利要求1中所述的一种基于多源实体融合的知识图谱构建方法，其特征在于，所述的步骤1)包括：
1.1)提取百科标题的同义词，提取方式包括以下两种：a)模板匹配：利用特定的模板去匹配每个页面的开头和摘要的第一句话，如果匹配成功，则得到同义词对。模板人为定义，涵盖大部分同义词对出现模式。
b)链接重定向：通过页面中超链接跳转到另一个页面，如果另一个页面的标题和该超链接的文本不同，则认为这两个词是同义词。
1.2)提取消岐页面：第k个百科表示为
k最大值为3，其中ai表示页面，n表
示页面总数量。由消岐页面中出现的所有页面，可提取消岐页面集合M，集合M里面的任意两两页面都不能表示同一个实体。
M＝{ai∈εk|ai∈M≠aj∈M}1.3)提取候选集：根据同义词的传递性，如果A和B互为同义词，A和C互为同义词，那么B和C也互为同义词。通过这种方式，得到同义词组St，所有同义词组St形成同义词组集合,该集合的每一个同义词组中的两两元素互为同义词。
给定St,从所有百科源中找出标题属于St的页面，所有的这些页面构成候选集Pt。Pt＝{a∈ε1,…,K|a.Title∈St}K为百科的总数；a.Title为页面a的标题。1.4)对百科页面的文本进行分词：对页面的5个域分词，包括摘要，信息框(键和值)，链接，目录，用户标签，并去除停用词和长度小于2的词。
3.根据权利要求1中所述的一种基于多源实体融合的知识图谱构建方法，其特征在于，所述的步骤2)包括：
2.1)定义一个页面所包含的6个域，包括标题T，摘要A，信息框I，目录C，用户标签G和链接L，用一个6元组来表示一个页面：
a＝{T,A,I,C,G,L}
其中信息框表示为键值对，因此I＝{P,V},其中P表示属性，V表示属性值；对于属于同一个候选集的2个页面，如果他们描述的是一个实体，那么他们的文本重叠率会比较大，因此定义以下7个特征，分别如下：
1)摘要特征
2
CN 106250412 A
权 利 要 求 书
2/3页
2)信息框属性特征
3)信息框属性值特征
4)目录特征
5)用户标签特征
6)链接特征
7)全局特征,S表示6元组{T,A,I,C,G,L}的字符串拼接
Sw(X)表示对字符串X分词后的结果集合。
2.2)将在步骤2.1)得到的7个特征作为分类器的输入，利用Weka算法包中的RandomForest算法训练二类分类器，然后用这个二类分类器来预测两个页面之间的相似度。
4.权利要求1中所述的一种基于多源实体融合的知识图谱构建方法，其特征在于，所述的步骤3)具体包括以下步骤：
3.1)根据步骤2)计算得到的页面之间的相似度构建该候选集的权重图，两个结点之间的权重边用相似度表示。由此，将原问题转换成边的取舍问题。用yij表示两个结点之间是否有边：
同时加入其他惩罚项和约束条件来构建混合线性规划模型：惩罚项1：
如果ai与aj有边，且ai与ak有边,那么aj与ak之间也应该有边，否则加入惩罚项φ，同时
3
CN 106250412 A
权 利 要 求 书
3/3页
乘上系数u作为调整参数。因此对于φ，有下面的约束：
φjk≥0
惩罚项2：
如果ai与aj之间的相似度越高，那么他们之间有边的概率越大。对于两个相似度很小的ai与aj，如果他们之间有边，则惩罚项较大，如果ai与aj的相似度较大，那么惩罚项较小。因此，用ψ用λ表示调整参数，该惩罚项用下式约束：ij表示惩罚项，
ψij≥0
sim(ai,aj)为ai和aj之间的权重；惩罚项3：
对于在一个消岐页面集合M里面出现的ai与aj，如果yij等于1，则表明匹配错误，因此需要用惩罚项ζ用下面的式子表示这个约束条件：ij来约束ai与aj之间没有边。
ζij≥0
N为消岐页面集合的个数；此外，对相似度设置阈值τ，只有相似度大于阈值τ的ai与aj的页面之间才能有边。综合以上各个惩罚项和阈值，得到目标函数如下所示：
s.t. yij∈{0,1},φij,ψζij,ij≥0
求得该目标函数的最大值，从而得到该最大值对应的边的参数yij。3.2)将该权重图中的每一个连通分量当作一个实体，得到描述一个实体的所有页面。
4
CN 106250412 A
说 明 书
基于多源实体融合的知识图谱构建方法
1/8页
技术领域
[0001]本发明涉及文本相似度计算方法，尤其涉及一种基于多源实体融合的知识图谱构建方法。
背景技术
[0002]随着互联网的迅速发展，人们获取信息和知识的途径越来越多样化，但是海量的数据分布于互联网的每一个角落，这给用户获取知识带来了很大的障碍。因此，构建一个统一完备的知识库迫在眉睫。
[0003]目前已经存在许多知识库，比如DBpedia是一个特殊的语义网应用范例，它从维基百科的词条里撷取出结构化的资料，以强化维基百科的搜寻功能，并将其他资料集连结至维基百科；Freebase是一个大型的合作知识库，它整合了网络上的许多资源。Freebase中的条目也与DBpedia类似，都采用结构化数据的形式。通过访问其数据可以发现其中所有的内容都是格式化的，按照三元组的格式存储并展示。这个模式是固定的，同一类型的条目都包含相同的属性。鉴于以上原因，同类数据之间就可以很容易地联系在一起，为信息查询提供了便利。Freebase包含数以千万计的主题，成千上万的类型和属性。但是这些知识库的语言都是英语，目前中文领域还没有一个大型的完备的知识库。[0004]传统的关于知识库的实体匹配算法中，主要是基于成对实体的匹配，并把这个问题形式化成一个分类问题。然而，大多数这类算法都严重地依赖于数据模板的质量。对于Web数据来说，数据不是以一个统一的三元组形式呈现的，而且不同源的数据在表达形式上也有较大的差异，因此这种方法在我们的这个问题上适用性较低。[0005]在另外一些匹配算法中，将页面的结构信息也考虑到特征中，比如在中英文维基的实体匹配中，因为已经有相当一部分页面存在跨语言链接，所以这部分信息可以作为先验知识。然而，我们的多源数据之间是没有任何链接的，所以页面的结构特征无法纳入特征之中。
[0006]在两个集合的特征计算中，可以使用Jaccard系数。Jaccard系数主要用于计算符号度量或布尔值度量的个体间的相似度，因为个体的特征属性都是由符号度量或者布尔值标识，因此无法衡量差异具体值的大小，只能获得“是否相同”这个结果，所以Jaccard系数只关心个体间共同具有的特征是否一致这个问题。如果比较X与Y的Jaccard相似系数，只比较Xn和Yn中相同的个数。
[0007]在特征相似度计算中，有许多算法可以应用。简单的可以直接计算欧式距离或者余弦距离。也可以根据特征训练分类器，使用分类器来计算相似度。随机森林是一种性能良好的分类器，可以用在特征相似度计算中。它指的是利用多棵决策树对样本进行训练并预测的一种分类器，并且其输出的类别是由个别树输出的类别的众数而定。随机森林具有许多优点，比如特征丢失时，仍可以保持较高的准确度，且不会产生过拟合问题。发明内容
5
CN 106250412 A[0008]
说 明 书
2/8页
本发明为整合多源百科知识，构建统一的知识库，提供了一种基于多源实体融合
的知识图谱构建方法。不同源的百科通常会包含描述同一个实体的多个页面，多源实体融合技术可以在海量的数据中找到这些页面，并将其映射到同一个实体上。[0009]本发明解决其技术问题采用的技术方案如下：一种基于多源实体融合的知识图谱构建方法，包括以下步骤：[0010]1)预处理百科页面：提取百科标题的同义词，提取消岐页面，利用同义词的传递关系构建同义词组，所有同义词组形成同义词组集合，根据同义词组集合中每一个同义词组对应的页面构建候选集，用分词工具对百科页面的文本进行分词。[0011]2)通过步骤1)的分词结果，计算同一个候选集里的两两页面之间的特征，通过训练分类器为每一维特征赋上不同的权重，并利用这个分类器计算页面之间的相似度。[0012]3)根据步骤2)中计算的页面之间的相似度构建该候选集的权重图，利用混合线性规划模型，定义该模型目标函数，并计算目标函数的最大值，得到顶点与顶点之间的连通性。将权重图上的每一个连通分量当作一个实体，从而获得描述同一个实体的所有页面。[0013]进一步地，所述的步骤1)包括：[0014]1.1)提取百科标题的同义词，提取方式包括以下两种：[0015]a)模板匹配：利用特定的模板去匹配每个页面的开头和摘要的第一句话，如果匹配成功，则得到同义词对。模板人为定义，涵盖大部分同义词对出现模式。[0016]b)链接重定向：通过页面中超链接跳转到另一个页面，如果另一个页面的标题和该超链接的文本不同，则认为这两个词是同义词。
[0017]
1.2)提取消岐页面：第k个百科表示为k最大值为3，其中ai表示页
面，n表示页面总数量。由消岐页面中出现的所有页面，可提取消岐页面集合M，集合M里面的任意两两页面都不能表示同一个实体。[0018]M＝{ai∈εk|ai∈M≠aj∈M}[0019]1.3)提取候选集：根据同义词的传递性，如果A和B互为同义词，A和C互为同义词，那么B和C也互为同义词。通过这种方式，得到同义词组St，所有同义词组St形成同义词组集合,该集合的每一个同义词组中的两两元素互为同义词。[0020]给定St,从所有百科源中找出标题属于St的页面，所有的这些页面构成候选集Pt。[0021]Pt＝{a∈ε1,…,K|a.Title∈St}[0022]K为百科的总数；a.Title为页面a的标题。[0023]1.4)对百科页面的文本进行分词：对页面的5个域分词，包括摘要，信息框(键和值)，链接，目录，用户标签，并去除停用词和长度小于2的词。[0024]进一步地，所述的步骤2)包括：
[0025]2.1)定义一个页面所包含的6个域，包括标题T，摘要A，信息框I，目录C，用户标签G和链接L，用一个6元组来表示一个页面：[0026]a＝{T,A,I,C,G,L}
[0027]其中信息框表示为键值对，因此I＝{P,V},其中P表示属性，V表示属性值；[0028]对于属于同一个候选集的2个页面，如果他们描述的是一个实体，那么他们的文本重叠率会比较大，因此定义以下7个特征，分别如下：[0029]1)摘要特征
6
CN 106250412 A
说 明 书
3/8页
[0030][0031][0032][0033][0034][0035][0036][0037][0038][0039][0040][0041][0042]
2)信息框属性特征
3)信息框属性值特征
4)目录特征
5)用户标签特征
6)链接特征
7)全局特征,S表示6元组{T,A,I,C,G,L}的字符串拼接
Sw(X)表示对字符串X分词后的结果集合。
[0044]2.2)将在步骤2.1)得到的7个特征作为分类器的输入，利用Weka算法包中的RandomForest算法训练二类分类器，然后用这个二类分类器来预测两个页面之间的相似度。
[0045]进一步地，所述的步骤3)具体包括以下步骤：
[0046]3.1)根据步骤2)计算得到的页面之间的相似度构建该候选集的权重图，两个结点之间的权重边用相似度表示。由此，将原问题转换成边的取舍问题。用yij表示两个结点之间是否有边：
[0047][0048]
[0043]
同时加入其他惩罚项和约束条件来构建混合线性规划模型：
[0049]惩罚项1：
[0050]如果ai与aj有边，且ai与ak有边,那么aj与ak之间也应该有边，否则加入惩罚项φ，同时乘上系数u作为调整参数。因此对于φ，有下面的约束：
7
CN 106250412 A[0051][0052]
说 明 书
4/8页
φjk≥0
[0053]惩罚项2：
[0054]如果ai与aj之间的相似度越高，那么他们之间有边的概率越大。对于两个相似度很小的ai与aj，如果他们之间有边，则惩罚项较大，如果ai与aj的相似度较大，那么惩罚项较小。因此，用ψ用λ表示调整参数，该惩罚项用下式约束：ij表示惩罚项，
[0055]
ψij≥0
[0057]sim(ai,aj)为ai和aj之间的权重；[0058]惩罚项3：
[0059]对于在一个消岐页面集合M里面出现的ai与aj，如果yij等于1，则表明匹配错误，因此需要用惩罚项ζ用下面的式子表示这个约束条件：ij来约束ai与aj之间没有边。
[0060][0061][0062][0063][00]
[0056]
ζij≥0
N为消岐页面集合的个数；此外，对相似度设置阈值τ，只有相似度大于阈值τ的ai与aj的页面之间才能有边。综合以上各个惩罚项和阈值，得到目标函数如下所示：
[0065]
[0066][0067][0068][0069][0070][0071][0072]
s.t.yij∈{0,1},φij,ψζij,ij≥0
求得该目标函数的最大值，从而得到该最大值对应的边的参数yij。3.2)将该权重图中的每一个连通分量当作一个实体，得到描述一个实体的所有页
面。
[0073]
本发明方法与现有技术相比具有的有益效果：
[0074]1.该方法利用标题同义词，得到标题候选集，再从标题候选集中得到页面候选集，在一个页面候选集中计算页面相似度，从而很大程度地减小了问题的规模，使得接下来的算法实施更加简单。
[0075]2.该方法根据页面结构，提取了7个文本特征的Jaccard系数，并采用随机森林算法计算页面与页面之间的相似度，这个相似度可以较准确地反应页面的相似度。
8
CN 106250412 A[0076]
说 明 书
5/8页
3.该方法在图上对页面之间的相似度建模，利用混合线性规划模型求得图上顶点
与顶点之间的关系，即页面与页面之间的关系。通过这些关系，可以构建一个无向图。在这个无向图中，可以较准确地得到描述一个实体的所有页面。
附图说明
[0077]图1是本发明的总体流程图；[0078]图2是步骤2)的流程图；[0079]图3是步骤3)的流程图；[0080]图4是步骤4)的流程图。
具体实施方式
[0081]下面结合附图和具体实施例对本发明作进一下详细说明。[0082]如图1-图4所示，基于多源实体融合的知识图谱构建方法的步骤如下：[0083]1)预处理百科页面：提取百科标题的同义词，提取消岐页面，利用同义词的传递关系构建同义词组，所有同义词组形成同义词组集合，根据同义词组集合中每一个同义词组对应的页面构建候选集，用分词工具对百科页面的文本进行分词。[0084]2)通过步骤1)的分词结果，计算同一个候选集里的两两页面之间的特征，通过训练分类器为每一维特征赋上不同的权重，并利用这个分类器计算页面之间的相似度。[0085]3)根据步骤2)中计算的页面之间的相似度构建该候选集的权重图，利用混合线性规划模型，定义该模型目标函数，并计算目标函数的最大值，得到顶点与顶点之间的连通性。将权重图上的每一个连通分量当作一个实体，从而获得描述同一个实体的所有页面。[0086]所述的步骤1)为：
[0087]1.1)提取百科标题的同义词，提取方式包括以下两种：[0088]a)模板匹配：利用特定的模板去匹配每个页面的开头和摘要的第一句话，如果匹配成功，则得到同义词对。模板人为定义，涵盖大部分同义词对出现模式。例如：对于带有同义词的页面，在页面的开头或摘要的第一句话通常会出现“A又名B”“,A别称B”，“A是B的同义词”等字符串，通过正则匹配，可以得到一部分同义词对。[00]b)链接重定向：通过页面中超链接跳转到另一个页面，如果另一个页面的标题和该超链接的文本不同，则认为这两个词是同义词。
[0090]
1.2)提取消岐页面：第k个百科表示为k最大值为3，其中ai表示页
面，n表示页面总数量。由消岐页面中出现的所有页面，可提取消岐页面集合M，集合M里面的任意两两页面都不能表示同一个实体。[0091]M＝{ai∈εk|ai∈M≠aj∈M}[0092]1.3)提取候选集：根据同义词的传递性，如果A和B互为同义词，A和C互为同义词，那么B和C也互为同义词。通过这种方式，得到同义词组St，所有同义词组St形成同义词组集合,该集合的每一个同义词组中的两两元素互为同义词。[0093]给定St,从所有百科源中找出标题属于St的页面，所有的这些页面构成候选集Pt。[0094]Pt＝{a∈ε1,…,K|a.Title∈St}[0095]K为百科的总数；a.Title为页面a的标题。
9
CN 106250412 A[0096]
说 明 书
6/8页
1.4)对百科页面的文本进行分词：对页面的5个域分词，包括摘要，信息框(键和
值)，链接，目录，用户标签，并去除停用词和长度小于2的词。[0097]所述的步骤2)包括：
[0098]2.1)定义一个页面所包含的6个域，包括标题T，摘要A，信息框I，目录C，用户标签G和链接L，用一个6元组来表示一个页面：[0099]a＝{T,A,I,C,G,L}
[0100]其中信息框表示为键值对，因此I＝{P,V},其中P表示属性，V表示属性值；[0101]对于属于同一个候选集的2个页面，如果他们描述的是一个实体，那么他们的文本重叠率会比较大，因此定义以下7个特征，分别如下：1)摘要特征
[0102][0103][0104][0105][0106][0107][0108][0109][0110][0111][0112][0113][0114]
2)信息框属性特征
3)信息框属性值特征
4)目录特征
5)用户标签特征
6)链接特征
7)全局特征,S表示6元组{T,A,I,C,G,L}的字符串拼接
Sw(X)表示对字符串X分词后的结果集合。
[0116]2.2)将在步骤2.1)得到的7个特征作为分类器的输入，利用Weka算法包中的RandomForest算法训练二类分类器，然后用这个二类分类器来预测两个页面之间的相似度。
[0117]所述的步骤3)具体包括以下步骤：
[0115]
10
CN 106250412 A[0118]
说 明 书
7/8页
3.1)根据步骤2)计算得到的页面之间的相似度构建该候选集的权重图，两个结点
之间的权重边用相似度表示。由此，将原问题转换成边的取舍问题。用yij表示两个结点之间是否有边：
[0119][0120]
同时加入其他惩罚项和约束条件来构建混合线性规划模型：
[0121]惩罚项1：
[0122]如果ai与aj有边，且ai与ak有边,那么aj与ak之间也应该有边，否则加入惩罚项φ，同时乘上系数u作为调整参数。因此对于φ，有下面的约束：
[0123][0124]
φjk≥0[0125]惩罚项2：
[0126]如果ai与aj之间的相似度越高，那么他们之间有边的概率越大。对于两个相似度很小的ai与aj，如果他们之间有边，则惩罚项较大，如果ai与aj的相似度较大，那么惩罚项较小。因此，用ψ用λ表示调整参数，该惩罚项用下式约束：ij表示惩罚项，
[0127]
ψij≥0
[0129]sim(ai,aj)为ai和aj之间的权重；[0130]惩罚项3：
[0131]对于在一个消岐页面集合M里面出现的ai与aj，如果yij等于1，则表明匹配错误，因此需要用惩罚项ζ用下面的式子表示这个约束条件：ij来约束ai与aj之间没有边。
[0132][0133][0134][0135][0136]
[0128]
ζij≥0
N为消岐页面集合的个数；此外，对相似度设置阈值τ，只有相似度大于阈值τ的ai与aj的页面之间才能有边。综合以上各个惩罚项和阈值，得到目标函数如下所示：
[0137]
[0138][0139][0140][0141]
s.t.yij∈{0,1},φij,ψζij,ij≥0
11
CN 106250412 A[0142][0143][0144]
说 明 书
8/8页
求得该目标函数的最大值，从而得到该最大值对应的边的参数yij。3.2)将该权重图中的每一个连通分量当作一个实体，得到描述一个实体的所有页
面。
实施例
[0146]下面提供一实例详细说明本发明的实现步骤：
[0147](1)实例采用的数据集来自百度百科和互动百科，其中百度百科的页面数量为10143321，互动百科的页面数量为6618544。[0148](2)根据(1)中的所有页面，分析页面版块结构，提取标题，摘要，目录，分类，链接，信息框等信息，并将这些信息存入lucene索引中。除了标题之外，其他的域均可以为空。[0149](3)根据(1)中的所有页面，提取标题同义词。同义词的提取方法主要包括模板匹配和链接重定向。通过提取到的同义词对，进一步得到标题同义词集合。用这些标题同义词集合去和(1)中的页面标题匹配，得到候选集页面。[0150](4)在(3)得到的候选集页面中，提取两两页面之间的特征，并以这些特征为输入，训练随机森林分类器。在这个步骤中，需要人工标注训练集。[0151](5)基于步骤(4)得到的相似度矩阵，构建混合线性规划模型，用该模型可得到顶点与顶点之间的关系，1表示两个顶点之间有边，0表示两个顶点之间没有边。以这些顶点和边为输入，可以构建一个无向图。提取无向图中的每一个连通分量，这些连通分量代表的页面表示一个实体。
[0152]本实例的运行结果：[0153]对于相似度计算，采用了5种方法进行对比，最后得出随机森林分类器的效果是最好的。相似度的计算通过Precision,Recall,F1和Accuracy四种评价指标将本发明所使用的方法(SCM)和其他方法，包括贪心匹配(GA),层次聚类(AC)，最小生成树聚类(MSTC)和协同聚类(CC)进行比较，得到的结果如下表：
[0154][0145]
PrecisionRecallF1Accuracy
78.3％76.1％77.2％91.6％73.0％79.0％75.9％91.5％63.4％80.5％71％88.8％62.4％65.5％63.9％87.4％75.8％82.5％79.0％92.5
[0155]由上表对比可以看出，本方法在F1和Accuracy的表现上都要比其他方法要好。因此，本方法在实体匹配方面具有良好的使用价值和应用前景。
方法GAACMSTCCCSCM
12
CN 106250412 A
说 明 书 附 图
1/2页
图1
图2
13
CN 106250412 A
图3
说 明 书 附 图
2/2页
图4
14
因篇幅问题不能全部显示，请点此查看更多更全内容