知识融合
目录
知识融合简介
目标: 融合各层面的知识
合并两个知识图谱 (本体),需要确认的是:
1. 等价实例
2. 等价类/子类
3. 等价属性/子属性
合并两个知识图谱（本体）
来源于不同知识库的同一实体
实体对齐是知识融合主要工作
中文百科中等价实例
概念层知识融合
跨语言知识融合
知识在线融合
各种相关名词术语
基本的问题都是研究怎样将来自多个来源的关于同一个实体或概念的描述信息融合起来
知识融合 (Knowledge Fusion)
本体对齐 (Ontology Alignment)
本体匹配 (Ontology Matching)
Record Linkage (传统数据库领域)
Entity Resolution (传统数据库领域)
实体对齐 (Entity Alignment)
实体对齐知识融合的主要挑战
数据质量的挑战
命名模糊,数据输入错误,数据丢失,数据格式不一致,缩写等
数据规模的挑战:
数据量大 (并行计算),数据种类多样性,不再仅仅通过名字匹配,多种关系,更多链接等
知识融合比赛-OAEI
OAEI (Ontology Alignment Evaluation Initiative)本体对齐竞赛,用来评估各种本体对齐算法,以达到评
估,比较,交流以及促进本体对齐工作的目的。OAEI每年举办一次,结果公布在官网上。
SEALS:
SEALS项目致力于评估语义网络技术。 它创建了便于进
行评估的基础架构,组织评估活动,围绕此评估活动构
建工具提供者和工具用户社区。参与者可以通过
OAEI_SealsClient 提交。
tutorial.pdf
Hobbit:
该平台旨在对群集上的关联数据系统进行基准测试。
官网: http://project-hobbit.eu/
Github: https://github.com/hobbit-project
Tutorial : https://github.com/hobbit-project/platform/wiki
知识融合的基本技术流程
知识融合一般分为两步,本体对齐和实体匹配两种的基本流程相似,如下:
数据预处理：语法正则化、数据正则化
数据预处理阶段,原始数据的质量会直接影响到最终链接的结果,不同的数据集对同一实体的描述方式往往是不相同的,对这些数据进行归一化处理是提高后续链接精确度的重要步骤。
语法正规化
语法匹配:联系电话的表示方法
综合属性: 家庭地址的表达方式
数据正规化
移除空格,《》,“”,-,等符号
输入错误类的拓扑错误
用正式名字替换昵称和缩写等
记录链接
假设两个实体的记录x和y,x和y在第i个属性上的值是x i ,y i ,那么通过如下
两步进行记录链接:
1. 属性相似度:
综合单个属性相似度得到属性相似度向量
[sim(x 1 , y 1 ), sim(x 2 , y 2 ), ... , sim(x N , y N )]
2. 实体相似度:
根据属性相似度向量得到一个实体的相似度
计算属性相似度
编辑距离
Levenstein,Wagner and Fisher,Edit Distance with Affine Gaps
集合相似度计算
Jaccard系数,Dice
基于向量的相似度计算
Cosine相似度,TFIDF相似度
编辑距离
Levenshtein distance (最小编辑距离),目的是用最少的编辑操作将一个字符串转成另一个,如下:
插入 ' e '
' Lvensshtain '
' Levensshtain '
' Levensshtain ' ' Levenshtain '
删除 ' s '
替换 ' a ' ' e '
' Levenshtain '
' Levenshtein '
上述将‘Lvensshtain’ 转换成‘Levenshtein’,总共的操作3 次,编辑距离也就是3。
Edit Distance with affine gaps,在上面两种算法的基础上,引入了gap的概念,将上述的插入,删除和替换操作用用gap opening和gap extension代替,编辑操作的代价也就表示为:
Cost g s e * l
其中, s是open gap的代价, e是extend gap的代价, l是gap的长度。
集合相似度
Dice系数用于度量两个集合的相似性,因为可以把字符串理解为一种集合,因此Dice距离也会用于度量字符串的相似性,Dice系数定义如下:
以 ‘Lvensshtain’ 和‘Levenshtein’为例,两者相似度为 2*9/ (11+11)= 0.82
基于向量相似度
TF-IDF主要用来评估某个字或者某个词对一个文档的重要程度。
比如某个语料库中有5万篇文章,含有“健康”的有2万篇,现有一篇文章,共1000个词,‘健康’出现30次,则sim TF-IDF = 30/1000 * log(50000/(20000+1)) = 0.012
计算实体相似度
相似度得分向量:[sim(x 1 , y 1 ), ... , sim(x N , y N )]
1. 聚合
加权平均,手动制定规则,分类器
加权平均:w 1 *sim (x 1 , y 1 )+...+w N *sim (x N , y N )
手动制定规则:sim(x 1 , y 1 )>T 1 and (or) .... sim(x i , y i )> T i
分类器:逻辑回归,决策树,SVM和条件随机场等
问题:
—训练集的生成
—分类不均衡 (更多不匹配的记录对)
—误分类
最关键的问题是需要生成训练集合。
方案
—无监督/半监督 (EM,生成模型等)
—主动学习 (众包等)
2. 聚类
层次聚类
层次聚类 (Hierarchical Clustering) 通过计算不同类别数据点之间的相似度对在不同的层次的数据进行划分,最终形成树状的聚类结构。
底层的原 始数据可以通过相似度函数计算,类之间的相
似度有如下三种算法:
a. SL(Single Linkage)算法
SL算法又称为最邻近算法 (nearest-neighbor),是用两个类数据点
中距离最近的两个数据点间的相似度作为这两个类的距离。
b. CL (Complete Linkage)算法
与SL不同的是取两个类中距离最远的两个点的相似度作为两个类
的相似度。
c. AL (Average Linkage) 算法
用两个类中所有点之间相似度的均值作为类间相似度。
相关性聚类
r xy 表示x,y被分配在同一类中, p xy 代表x,y是同一类的概率 (x,y之间的相似度),w +xy (= p xy )
和w – xy (= 1-p xy )分别是切断x,y之间的边的代价和保留边的代价。相关性聚类的目标就是使用
最小的代价找到一个聚类方案。
minimize ∑ r xy w -xy +(1- r xy ) w +xy
是个NP-Hard问题,可用贪婪算法近似求解。
举例,下图中,实线表示两数据点有关系,将其归为一类,会给最终结果贡献w -xy ;虚线表示两数据点没有关
系,将其归为一类,给最终结果贡献w +xy 。
Canopy + K-means
与K-means不同,Canopy聚类最大的特点是不需要事先指定k值 (即clustering的个数),因此具有很大的实际应用价值,经常将Canopy和K-means配合使用。
3. 表示学习
将知识图谱中的实体和关系都映射低维空间向量,直接用数学表达式来计算各个实体之间相似度。这类方法不依赖任何的文本信息,获取到的都是数据的深度特征。
知识嵌入—TransE模型三元组(h, r, t): 关系向量l r 表示为头向量l h 和尾向量l t 之间的位移TransE希望l t = l h + l r
实体与向量之间的关系
如何将两个知识图谱嵌入到同一个空间
桥梁:预链接实体对 (训练数据)
方法:
联合知识嵌入:将两个KG的三元组糅合在一起共同训练,并将预链接实体对视为具有SameAS
关系的三元组,从而对两个KG的空间进行约束具体实现: Hao Zhu et al. Iterative Entity Alignment via Knowledge Embeddings, IJCAI 2017
双向监督训练:两个KG单独进行训练,使用预链接数据交替进行监督。
如何链接实体
KG向量训练达到稳定状态之后,对于KG1每一个没有找到链接的实体,在KG2中找到与之距离最近的实体向量进行链接,距离计算方法可采用任何向量之间的距离计算,例如欧式距离或Cosine距离。
关注数据规模问题
分块 (Blocking)是从给定的知识库中的所有实体对中,选出潜在匹配的记录对作为候选项,并将候选项的大小尽可能的缩小。
分块 (Blocking)是从给定的知识库中的所有实体对中,选出潜在匹配的记录对作为候选项,并将候选项的大小尽可能的缩小。
1. 基于Hash函数的分块
对于记录x,有hash(x)=h i ,则x映射到与关键字h i 绑定的块C i 上。
常见的hash函数:
—字符串的前n个字
—n-grams
—结合多个简单的hash函数等
2. 邻近分块
Canopy聚类
排序邻居算法
Red‐Blue Set Cover
负载均衡
负载均衡 (Load Balance)来保证所有块中的实体数目相当,从而保证分块对性能的提升程度。最简单的方法是多次Map-Reduce操作。
结果评估
准确率,召回率,F值
整个算法的运行时间
典型知识融合工具介绍
本体对齐—Falcon-AO
简介
Falcon-AO是一个自动的本体匹配系统,已经成为RDF(S)和OWL所表达的Web本体相匹配的一种实用和流行的选择。编程语言为Java。
系统架构
相似度组合策略
语言学可比性
语言学算法找到的映射单元数目对比本体概念数目
结构可比性
本体间使用的原语的数目对比
映射单元集成
语言学可比性和结构可比性分别分为高、中、低档
映射单元选取算法
贪心选取
Model Pool
Parser用Jena将输入的本体导入到模型中,coordinator内置了一套协调规则用来调整模型。
Matcher Library
管理4种匹配方法,包括V-Doc , I-Sub, GMO 和PBM 。其中, V-Doc 和I-Sub是基于语言的匹配器,GMO是基于图结构的匹配器, PBM用分而治之的策略为大规模的本体进行块映射。
Alignment Set
以XML/RDF格式生成匹配文件,并用传统的准确率/召回率进行评测。
Central Controller
手动调节参数,可以选择用Matcher Library 中的哪种方法进行匹配。
Repository
用来存储中间数据。
一种基于分而治之策略的大型本体匹配方法
本体划分：概念间的结构亲近性计算
类:层次关系 (公共父类)
属性:层次关系、定义域等
一个自底向上的划分算法
每个聚类内结点间的内聚度较高
不同聚类内结点间的耦合度较低
本体划分
定义:设O是一个本体,E是O中所包含概念的集合。针对E的一个划分G,把E分成一个聚类集合G = {g 1 , g 2 , ..., g n },满足 (1) g i , g j ,i, j = 1, 2, ..., n且i ≠ j,g i ∩g j = ;同时(2) g 1 ∪...∪g n = E。设b i 是对应于g i 的唯一本体分块 (i = 1, 2, ..., n)。 b i 是一个RDF句子的并集b i = sent 1 ∪... ∪sent m ),其中每个sent k (k = 1, 2, ..., m)满足sent k 的主语属于g i 。 b i , b j ,i, j = 1, 2, ..., ni ≠ j,b i ∩b j = 。
RDF句子:RDF三元组的集合,保证匿名结
GMO (Graph Match for Ontology )
GMO是基于图结构的本体匹配方案,它使用RDF二部图来表示本体,并通过在二部图中递归传播相似来计算实体和三元组之间的结构相似性。一般,用V-Doc和I-Sub的输出作为它的输入。
实体匹配—Dedupe
概要
Dedupe是一个用于模糊匹配, 记录去重 和实体链接的python库
1. 指定谓词集合 & 相似度函数Dedupe的输入需要指定属性的类型,在内部为给每个属性类型指定一个谓词集合以及相似度计算方法。右图是对 ‘比尔盖茨’的’name’属性的简单描述,将每个属性都映射上去,会形成一个大的谓词集合
. 训练Blocking :通过 Red-Blue set cover 找到最优谓词集合来分块最优谓词集合至少能覆盖95% (可以指定)的正样本对,负样本对被误分到同一个block中越少越好。
3. 训练逻辑回归 (LR)模型
用用户标记的正负样本对训练LR模型,来进行分类。LR不能确定的会返回给用户进行标注(Active Learning)。
实体匹配—Limes
概要
Limes是一个基于度量空间的实体匹配发现框架,适合于大规模数据链接,编程语言是Java。
整体框架
整体流程
给定源数据集S,目标数据集T,阈值
1. 样本选取: 从T中选取样本点E来代表T中数据。
2. 过滤: 计算s ∈S与e ∈E之间的距离m(s, e),利用三角不等式进行过滤。
3. 相似度计算: 同上
4. 序列化: 存储为用户指定格式
技术细节
1. 样本点选取
所谓样本点,也就是能代表距离空间的点。应该在距离空间上均匀分布,各个样本之间距离尽可能大。
2. 三角不等式过滤
给定 (A,m),m是度量标准,相当于相似性函数,A中的点x,y和z相当于三条记录,根据三角不
等式有:
上式通过推理可以得到:
上式中y相当于样本点。因为样本点E的数量是远小于目标数据集T的数量,所以过滤这一步会急剧减少后续相似性比较的次数,因而对大规模的web数据,这是非常高效的算法。
实体匹配—Silk
概要
Silk是一个的集成异构数据源的开源框架。编程语言为python。
整体框架
预处理: 会将索引的结果排名前N的记录下来进行作为候选对,进行下一步更精准的匹配 (损失精度)。
相似度计算: 里面包含了很多相似度计算的方法。
过滤: 过滤掉相似度小于给定阈值的记录对。
特点
1. 提供了专门的Silk-LSL语言来进行具体处理
2. 提供图形化用户界面—Silk Workbench ,用户可以很方便的进行记录链接。
典型案例介绍
Zhishi.me
Zhishi.me (http://zhishi.me) 是国内首次发布的大规模中文语义数据集,并致力于将已经发布数据集进行链接形成中文链接开放数据 (CLOD).
等价实体
Openkg.link
LIMES实战
解决方案
通过迭代,自动发现并修改特定数据集的匹配规则
通过找出训练数据对中最具有判别力的数据来推导匹配规则
Workflow – 挖掘等价属性
Workflow – 挖掘匹配规则
匹配规则 (frequent set mining):
baidu:x and hudong:x are matched, iff.
valueOf(baidu:标签) = valueOf(hudong:中文学名)
and
valueOf(baidu:拉丁学名) = valueOf(hudong:二名法)
and
valueOf(baidu:纲) = valueOf(hudong:纲)
Workflow – 生成匹配对
用得到的匹配规则处理未标记的数据,生成候选匹配对。
Combiner用来计算候选匹配对的置信度。
Workflow – the Wrapper 算法
Wrapper 是对EM迭代算法的封装
Workflow – E-step
E-step用观测到的数据 (已匹配的实例对)和目前估计的参数 (匹配规则)来评估缺失数据 (未匹配的实例对)。
Workflow – M-step
正如在E-step估计未匹配实例对一样,在M-step通过最大似然函数来估计参数
M: 匹配的实例对
Θ: 参数
似然函数
假设每个数据集中不存在重复的实例,我们可以推断出,对于一个数据集中某个实例a1,在另一个数据集中能找到最多一个与此等价的实例a2。
M中错误的matches会导致某个实例a1匹配到多个等价实例 (a2,a3...),这与上面的假设相违背。
Evaluation – Precisions
在输出matches中采样。
X轴表示在现有的参考matches中选择作为初始seeds的比例。
Evaluation – 新发现的matches
匹配空间是由参考的matches和新产生的matches构成
Results
准确度: ~97% (手动标记)
典型案例二: OpenKG的链接百科
动机
目前OpenKG中已收录了76个中文数据集,目前已经融合几个百科类数据集Zhishi.me, CN-DBpedia, PKU-PIE和Belief Engine。
链接方法
通过繁简转换后的实体名严格匹配
利用wikidata扩展别名
CN-DBpedia与Zhishi.me的链接,使用了CN-DBpedia中具有别名含义的属性扩充实体别名
由于PKUBase里没有可用的具有别名含义的属性,因此它没有上述链接过程
Belief Engine的链接过程与其他完全不同,使用互动百科的唯一“article title”与Zhishi.me中的互动百科实体进行链接