KGU-SP:一种挖掘标准模式的知识图谱更新方法

卢 菁,陈婉璐,刘 丛

(上海理工大学 光电信息与计算机工程学院,上海 200093)

1 引 言

知识图谱最初由谷歌为提高搜索引擎的能力而提出,旨在描述现实世界中存在的实体以及实体之间的关系.随着人工智能技术的发展,知识图谱得到了飞速发展,并已被广泛应用在智能搜索、智能问答、个性化推荐等领域.随着知识爆炸式增长,现存的知识图谱面临着知识更新频繁的挑战[1],大量知识同时更新,若不进行筛选则很容易将错误信息插入知识图谱.

当前大多数知识图谱的更新都是由知识图谱方发起主动更新,分为全局更新和局部更新:1)全局更新.文献[2]根据数据流改良了更新方案,每产生一个更新就生成一条记录主动推送更新,减少更新的量从而一定程度上减少错误,但提供更新流的数据源较少,被动更新往往难以实施;2)局部更新.文献[3]提出关注有限的采样观测频率从而实现主动局部更新,这种方法通过减少更新的量对筛选的准确率略微提升,但知识更新频率时常比估计的频率高,导致更新的准确率较低;文献[4]进一步提出使用时间约束进行查错,但其适用范围仅限于时间敏感的数据;文献[5]提出如果知识图中已经存在该实体,将该实体在知识图中的所有信息全部替换,如果不存在,则将信息抽取后直接嵌入知识图中,虽然能避免冲突但是直接取代过期知识的做法不够准确;文献[6]用三元组分类方法计算三元组知识的置信度,从而判断三元组是否为真,若为真则加入,该方案仅利用基于相似度的评分标准来判断语义是否正确,判断标准单一且不能识别出更精细的语义,更不能判断语义值是否正确,在筛选错的知识上具有一定局限,不能保证准确率;文献[7]进一步基于规则引导,利用关系间的联系对信息的置信度进行估算以筛选错误知识;文献[8]通过改进目标函数并提出双模函数逼近算法来达到目标函数最大化,但会增加原先目标函数求解的复杂度;文献[9]根据挖掘的目标函数的贪婪性使用枚举方法对模式集分类,枚举的方案会产生遗漏而不能保证过滤的准确性.当大量知识同时比对时,实体类型的繁多及实体间关系的复杂性进一步加剧了筛选的难度.

综上所述知识图谱自动更新面临着知识数量大且更新准确率低的问题,而知识图谱中的知识往往是有规律的,不同类型的知识都会遵循各自固有的形式[10],如果将这些特征挖掘出来,利用特征信息构造图模式,对所抽取知识进行正确性和完备性检查,则可以避免将错误的知识插入图谱,提高知识图谱的质量.

图1是一个演员出演电影的实例.从Web中抽取新的知识<“刘青云”,“出演”,“拆弹专家”>并自动插入知识图谱时通常不检查所抽取的知识是否包含演员拍摄的时间,从而造成错误.若能根据此类知识的特征构造包含时间特征信息的标准模式,并将新知识与标准模式进行比对,符合标准模式的知识将被插入知识图谱中,若缺乏相应信息,则抽取缺乏的特征信息后再进行插入,则能提高知识更新的准确率.

图1 图模式实例

本文提出一种基于标准模式挖掘的知识图谱更新方法:先挖掘知识图中的频繁模式,然后基于Giraph模型求解标准模式,最后用标准模式进行图模拟匹配检查,符合模式条件的知识将会被筛选出并插入;当大量知识同时更新时,将标准模式向量化并计算新知识与标准模式之间的向量距离,符合距离阈值条件的知识将被筛出并插入,从而减少知识图谱更新时的错误,提高知识筛选的准确率.

本文的主要贡献包括:

1)针对知识图谱中模式挖掘算法subTopk的缺陷,提出了标准模式的概念和SPM标准模式优化挖掘算法,优化了贪心增益计算,提高了标准模式挖掘的准确度.

2)利用图模拟的方法,用标准模式匹配待插入知识,符合标准模式的知识将被筛选出,提高更新知识的准确率.

3)当大量知识同时更新时,借用TransD中将事实投影到不同领域的思想,将标准模式和待检查知识投影到不同空间,计算知识向量与标准模式向量间距离,符合阈值条件的知识将被筛选并插入,从而加快比对的速度,提高知识更新的效率.

4)在真实数据集上进行实验,验证了本文提出方法的有效性,与现有的方法比较展现了该方法具有更好的精确率、召回率和F1值.

2 相关定义及方法流程

2.1 相关定义及符号

定义1.知识图:知识图表示为G=〈V,E,L〉,其中V是节点集,∀v∈V表示节点集中的任意点;E⊆V×V是边集,∀e∈E表示边集中的任意边;L是类型集,表示节点或者边的类型,即L(v)是节点的实体类型,L(e)是边的标签,表示两个节点之间的关系类型.

定义2.图模式:图模式表示为P=〈VP,EP,LP〉,其中VP是模式节点集,EP是关系边集,LP是类型集.

定义3.模式覆盖度:给定知识图G和图模式P,满足二元关系R(P,G)的节点v和节点间的边l构成覆盖子图GP,模式覆盖度为该子图中节点和边的总数与知识图G的节点和边的总数的比,记为cov(GP,G),表示如公式(1)所示:

cov(GP,G)=|GP|/|G|

(1)

其中|GP|和|G|均表示图的大小,分别为覆盖子图GP和知识图G中节点和边的总数.

定义4.频繁模式:在给定知识图上,频繁模式集为模式覆盖度超过给定阈值的所有模式的集合,给定的阈值被称为最小模式覆盖度.阈值根据需求设定,如设定为0.5,那么cov(GP,G)=|GP|/|G|>0.5的为频繁模式.

定义6.标准模式挖掘问题(SPM):在候选模式集中给定一个常数m,Top-m标准模式挖掘问题定义如公式(2)所示:

(2)

其中S={P1,P2,…,Pm}有m个标准模式的集合,GPi为标准模式Pi在知识图上的覆盖子图,|GPi|为GPi的节点数和边数的总和.

定义7.图模拟匹配:给定一个模式图P(VP,EP,LP)和一个数据子图Gsub=(Vsub,Esub,Lsub),两者之间存在二元关系S⊆VP×Vsub,其中VP和Vsub分别表示模式图节点和数据图节点的集合,若LP(v)=Lsub(u),则称该子图满足节点约束;若∀(v,v′)∈EP,∃(u,u′)∈Et:(u′,v′)∈S,则称该子图满足边约束;若∀v∈VP,∃u∈Vsub:(u,v)∈S,则称该子图满足图约束,检查数据子图与模式图之间是否同时满足3个约束的过程叫图模拟匹配.

定义8.知识向量化:给定一个知识图G=(V,E,L),对于G中每一条知识三元组(h,r,t),将三元组中不同类型的关系和实体投影至不同的空间域中,即对h和t向不同的关系空间进行投影,并建立h到t的转换关系.

定义9.向量距离:给定两个知识向量x=(x1,x2,x3,…,xn)和y=(y1,y2,y3,…,yn),两者间距离公式定义见公式(3):

(3)

问题描述:给定知识图G=〈V,E,L〉,利用频繁模式挖掘算法挖掘知识图中的频繁模式P,当知识图中节点v和模式节点vP满足(v,vP)∈R且模式覆盖度cov(Pi,G)满足给定最小模式覆盖度阈值,同时使S*=argmax|S|成立时,该模式P是标准模式,利用标准模式设计筛选方案,使用图模拟匹配或计算向量间距离的方法筛选正确知识,并将正确知识插入知识图谱.

2.2 方法流程

本文提出的基于标准模式挖掘的知识图谱更新处理方法流程图如图2所示,具体流程步骤如下:

图2 知识图谱更新处理流程图

1)模式挖掘.利用频繁模式挖掘算法挖掘初始模式集,给出模式限制参数并规范模式;进一步用Giraph算法进行匹配,剔除描述信息少概括能力差的模式;对候选模式集进行增益计算,挖掘出具有代表性的标准模式集.

2)构造新增知识图.利使用词条更新频率预测器获取热词并作为种子实体,抽取种子实体所在三元组以构造知识图.

3)筛选更新知识.用目标模式集中的模式模拟匹配更新知识图,根据近似匹配要求筛选不匹配的知识,当大量知识同时筛选时,向量化标准模式和待匹配知识,利用向量距离进行筛选.

4)更新知识的嵌入.原本没有的实体其知识直接嵌入,存在的实体找出其冲突元素所在三元组,进一步判断是否符合三元组所在模式的约束并更新.

3 标准模式挖掘算法

3.1 候选模式挖掘

先利用GRAMI框架在大图中挖掘频繁子图,通过调整频繁度找到符合的所有子图,且能避免复杂的枚举[11].由于知识图谱中实体信息丰富、实体间关系复杂,图模式会根据实体和关系的不同情况而产生不同的大小,为了避免过于复杂和庞大,在频繁模式挖掘后需要对模式进行限制:给定整数参数k和n,k为节点间的路径长度,n为模式中的节点数.有图模式P,其中kP为模式P中节点间的最长路径长度,|P|为模式P的节点数和路径长度,则kP≤k,|P|≤k+n时,模式P满足限制模式定义.例如图2中P1的kP1=2,|P1|=5,如果kP1和|P1|满足给定的参数,那么P1就是符合参数限制的模式.

实际应用中的知识图谱含有大量节点和边,判定图模式P和求解覆盖子图GP是耗时的,本文选用Giraph模型图模拟[12]的思想进一步得到候选模式集:先进行模式P与知识图G之间任意节点vP∈V的匹配.如果u的标签l∈VP,且l是P中的叶子节点,则u是匹配的;如果v的标签为l,且P在中l有子节点l′1,l′2,…,l′c,则v在G中具有l′1,l′2,…,l′c标签的子节点,且v与其l′i(i=1,2,…,c)标签子节点之间的边与边(l,l′i)的标签一致,则v匹配.将模式v中节点进行拓扑排序,并生成一个由v决定的标签拓扑序列,记为l1,l2,…,lt.对知识图G中的节点,按照P中的标签拓扑序列的逆序判定相应标签的节点是否匹配,如知识图G中存在l1,l2,…,lt标签的匹配节点,那图模式P就是一个候选模式,匹配的节点及与这些节点相邻的具有相应标签的边即构成覆盖子图GP.

从边缘的叶子节点开始匹配,匹配过程如图3所示:从“麦兆辉”、“罗志良”、“刘青云”3个节点开始匹配,3个节点根据连接的边的关系标签同步向上游节点进行消息的传递,将会传递本节点的标签属性等包含的所有信息,例如“麦兆辉”节点会向“窃听风云”节点发送自身节点的ID和属性标签“导演”,“窃听风云”节点接受到信息后继续向它的上游节点发送信息,信息包含自身信息和从下游节点收到的信息,以此迭代传递.传递的过程中尤其注意标签信息的匹配,所以“金像奖”节点与“麦兆辉”节点此时不会进行消息的传递,因为其边标签“获得奖项”与图模式P3中的“指导”边标签不能匹配.迭代传递信息的过程中,消息是合并后迭代传递的,边标签一直保持匹配,逻辑上是“∨”的关系,节点均活跃表示匹配,才能保证迭代匹配,最终完成关于模式P3完整的消息匹配,且P3是一个匹配的标准模式,图中虚线为消息传递过程与节点共同组成模式覆盖子图.

图3 基于Giraph的图模拟标准模式判定及覆盖子图求解

在图模拟匹配后以模式覆盖度为度量标准,模式的覆盖度越高,表示该模式对知识图的表示越完备,留下表示更完备的模式.如给定参数k=2和b=7的限制,图模式P1、P2、P3均满足,但在知识图中“消失的凶手”节点标签为“电影”,与图模式P1的节点类型“电影”相匹配;其上游节点和下游节点为“罗志良”和“上海”,节点类型为“导演”和“拍摄地点”,各自的边标签为“指导”和“拍摄于…”,与P1中的节点类型和边标签不匹配,那么P1就是一个不满足匹配关系的模式.故P1、P2、P3仅P2、P3满足标准模式.对于候选模式P2、P3的二元关系R(P2,G)和R(P3,G)的覆盖子图,分别计算图的大小:|GP2|=10,|G|=40,|GP3|=18,可以得到:cov(GP2,G)=|GP2|/|G|=10/40

图4 P2和P3的覆盖子图实例

3.2 标准模式挖掘

由于模式间可能存在重叠冗余或者相似,如何得到表达能力强且准确率高的标准模式进一步定义为标准模式挖掘问题.根据定义6可知挖掘问题的目标函数argmax|S|是一个单调非负的且有大小约束的次模函数且满足次模性,且该函数能用贪心算法得到近似解结果为(1-1/e)倍的最优解[13].待挖掘的图模式集具有边际效益递减的特点[14],即挖掘出的图模式集会随着新挖掘的标准模式的加入而减小.故标准模式挖掘的目标是在候选的图模式集中得到满足最大边际效益的模式.

文献[15]不断给初始图模式集加入覆盖子集大且边际效益高的模式,直到子集数满足需要的模式数.但这样的标准模式挖掘目标函数唯一,且利用函数的次模性来找到满足最大边际效益的图模式,其挖掘过程的算法是贪婪的,每次都在标准图模式集中选择使当前具有最大边际效益的图模式加入,即计算P′←argmaxP∈SPσ(S|P),该算式保证了ΔGP最大化,但不能使ΔGS最大化,即不能保证最终得到的图模式集覆盖率最大.

本文不改变目标函数P′←argmaxP∈SPσ(S|P),提出以下改进方案:先计算所有可行的小于m的图模式集中所有具有最大|GP|的集,然后在计算的模式集合中选择只有一个P使得|GP|最大的模式集,依次选择包含先前模式的新模式集,新模式集的模式个数比先前模式集的模式多一个,迭代得到目标标准模式集,在这样的情况下,求解的结果会更加逼近最优解.

算法1为SPM标准模式优化挖掘算法,先利用GRAMI频繁模式挖掘工具挖掘频繁模式(第1行),然后对模式的大小进行限制并进行图模拟匹配(第2～3行),匹配完成后得到候选模式集(第4行).初始化标准模式集为空(第6行),进行模式边际效益和新增模式前后的模式集覆盖度计算(第7～9行),计算后选择具有最大边际效益的模式加入模式集(第10～12行),直到模式集中模式个数满足所需结果集模式个数.具体算法如下:

算法1. SPM标准模式优化挖掘算法

输入:知识图G(V,E,L),限制边数k,限制节点数n,初始结果集S← Ø,标准模式结果集模式个数m

输出:标准模式集S

4 知识筛选

从热门语句文本中抽取出相应的三元组实例,构造待更新的知识图,根据抽取的知识量选择合适的筛选方案:知识三元组较少时,构造更新知识图Gnew,用标准模式P匹配更新知识图Gnew,剔除不满足两者中S⊆VP×Vnew这样关系的节点,剩余节点构成正确知识;当待更新知识量较大时,选择将标准模式P和更新知识三元组向量化,用向量间距离衡量向量相似度,大于一定阈值的向量为正确知识,并向量化三元组嵌入更新.

4.1 图模拟筛选方法

利用挖掘的标准模式集在待更新知识图中进行图模拟匹配,具体匹配过程如下:匹配过程与找标准模式的匹配类似.标准模式集与待更新知识图存在二元关系R(P,G)⊆VP×V,先根据待更新知识图中节点的标签在模式集中产生匹配候选集,保证该知识图存在后继节点与模式图中对应节点的后继关系,即该知识图节点存在后继节点与模式图节点的后继节点的属性值相同,按照这样的近似匹配要求筛选不匹配的节点,剩下的覆盖子图为可以嵌入的正确知识.

算法2为基于标准模式图匹配的更新知识筛选算法,将算法1中得到的标准模式都与更新知识图进行匹配(第1行),先从叶子节点开始匹配(第3～5行),依次判断知识图中节点和边与标准模式中的节点和边(第6～8行),都匹配时筛选出符合的知识图,得到待更新匹配的知识(第9行).

算法2. 基于标准模式图匹配的更新知识筛选算法

输入:更新知识图Gnew,标准模式集S=(P1,P2,…,Pm)

输出:待更新知识G*

4.2 向量化筛选方法

上述方法在图模拟匹配时,会因过大的知识量加大和复杂的实体间关系而急剧增加图模拟匹配的时间复杂度.由于TransD能较好的解决复杂关系下的实体表示区分性,不同的关系有不同的投影空间,不同类型的实体有不同的投影方式[16],本文利用翻译模型TransD捕获实体和关系之间的语义相关性的思想,通过映射矩阵Mrh和Mrt来表示不同关系下的实体向量.Mrh和Mrt分别是h和t的映射矩阵,其映射矩阵定义如公式(4)和公式(5)所示:

(4)

(5)

其中rp、hp和tp是投影向量,Im×n为单位矩阵,用来初始化映射矩阵.对应的每个三元组(h,r,t)中的两个实体向量h和t投影后分别定义如公式(6)和公式(7)所示:

h⊥=Mrhh

(6)

t⊥=Mrtt

(7)

且两实体的投影向量满足的关系如公式(8)所示:

h⊥+r≈t⊥

(8)

因此对于标准模式集S=(P1,P2,P3,…,Pm),任意标准模式三元组(hsp,rsp,tsp)∈Pm,其实体hsp和tsp的投影如公式(9)和公式(10)所示:

hsp⊥=Mrh_sphsp

(9)

tsp⊥=Mrh_sptsp

(10)

标准模式投影后的向量满足的关系如公式(11)所示:

hm⊥+rm≈tm⊥

(11)

对于更新知识图Gnew,其知识三元组为(hk,rk,tk)∈Gnew,其实体hk和tk的投影如公式(12)和公式(13)所示:

hk⊥=Mrh_khk

(12)

tk⊥=Mrt_ktk

(13)

知识三元组向量满足的关系为公式(14):

hk⊥+rk≈tk⊥

(14)

对标准模式和知识三元组向量化后,计算标准模式向量与知识向量的距离,并给定一个距离差的阈值ε,筛选大于阈值的知识向量,得到待嵌入的知识.

算法3为基于向量距离计算的更新知识筛选算法,在模式向量集中选择一个模式的向量,再在知识向量集中寻找与该模式的向量在同一空间域的知识三元组向量,并将三元组向量依次与模式向量进行距离计算,直到模式向量集中被选完(第1～6行),判断两者的距离差与阈值的关系,只要与其中一个模式向量的距离差小于阈值,就作为待更新知识并放入待更新知识集中(第7～9行).

算法3. 基于向量距离计算的更新知识筛选算法

输入:更新知识图Gnew,标准模式集S=(P1,P2,…,Pm),投影域集D=(D1,D2,…,Dn),向量距离阈值ε

输出:待更新知识G*

完成筛选后,得到待更新的知识图,利用图嵌入或三元组嵌入的方法将待更新知识插入原先的知识图谱中.

5 实 验

5.1 数据集与实验设计

中文学术信息集成系统Scholar Space包含不同数据源的学术数据,并能进一步构建一个学术关系知识图谱Scholar Graph[17],本文实验中选择其计算机类的数据作为实验数据集,其中节点数为774263,边数为395833,节点标签有4类,边标签有2类.本文先通过简单抽样方法将数据集分割,分为比例为80%和20%两部分,其中80%数据集(D1)作为模式挖掘的数据,20%数据集(D2)作为实行筛选实验的数据并进行注错处理.

5.2 评价指标

本文采用精确率Precision、召回率Recall和F1值作为评价指标.

表1 筛选结果混淆矩阵

5.3 实验结果与分析

根据5.1中的实验设计进行实验,实验结果如下文所示:

5.3.1 频繁模式挖掘

对数据集D1利用GRAMI挖掘工具挖掘得到频繁模式集,使得挖掘出的模式对知识图达到最大覆盖面积,并使用覆盖度作为衡量图模式的覆盖性的度量标准,覆盖度越大,解集的覆盖性就越好,且最大为1.挖掘结果如表2所示.

表2 频繁模式挖掘参数

5.3.2 m值取值分析

调节m的取值,得到不同的模式覆盖度cov值,覆盖度越大表明标准模式集效果越好.

图5为m值取不同值时的影响图,标准模式集在更新知识图上的覆盖度变化如图5(a)所示:随着选取的模式个数m值的增加,标准模式集的覆盖度增大,但不会随着m值的增加而一直增大,分析这是由于标准模式的大小不同而产生局部重叠的原因.

图5 调节m值的影响图

不同的m值使得标准模式集的个数不同,从而在利用标准模式集筛选更新知识图时,会对精准率、召回率和F1产生影响.产生的影响如图5(b)所示:随着m值的取值的增大,精确率、召回率会先增大后略降低并趋于平稳,F1受精确率和召回率影响,随着m值的取值的增大先上升后趋于不变,最终当m值取7时,使得F1值最大,此时pre=92.3%,recall=85.6%,覆盖度为0.876,在保证召回率尽可能大的情况下,提高精确度,使两者综合结果较好,标准模式集最优,并用该值进行接下来实验.

5.3.3 向量间距离阈值ε调节结果分析

使用得到的标准模式集中的模式依次对数据集D2进行图模拟匹配,匹配后符合的数据记为正确数据;并同时对数据集D2和标准模式集进行向量化,计算数据集D2的向量和标准模式集的向量间距离差,调节距离差的阈值,通过向量间距离判断两条知识间的相似度,验证知识的正确性,小于阈值时记为正确的知识.

不同的向量间距离的阈值使得三元组准确率要求不同,调节向量间距离的阈值会在筛选更新知识图时对精准率、召回率和F1产生影响.如图6所示:向量间距离差的阈值变化时,即向量间相似度范围发生变化.距离差阈值越大,则对两条向量的相似度要求越低.当距离差阈值增大时,召回率呈增加趋势,精确率呈下降趋势.数据量大时不一定准确率高,要在保证召回率的情况下尽量提高精确率和两者的综合结果F1,因此距离差阈值取0.2时,筛选情况能达到最佳效果.

图6 距离差阈值对精确率、召回率和F1的影响图

5.3.4 知识量影响分析

本文做了两种方案在不同知识量下的影响实验,选取数据集的不同数据量进行实验,运行时间对比如图7(a)所示:在较小的数据集上两者的运行时间相近且SP方法要更快一些,但随着数据量的增加SP+VD的运行时间会更快一些,是由于前者的时间复杂度高于后者,在数据量较小时运行时间相近,但随着数据的增加,前者运行的复杂程度比后者高,运行时间也就高于后者.

图7 SP和SP+VD筛选方案对比图

在20%数据集上进行筛选对比,结果如图7(b)所示:SP精准率和F1较好,而SP+VD召回率较好,是因为SP的筛选过程中使用的参数更多更精细,而SP+VD只有向量间距离这一个参数,前者会使筛选的结果更精确,后者则会筛选出更多预测为符合的数据,且本文提出的两种方法均能提升对更新知识的筛选准确率.

5.3.5 不同筛选方案结果分析

本文将提出的方法与[7,8]这两篇文章中提出的方法进行对比试验.

1)TI:文献[7]提出考虑三元组重要性的特征,分别对实体和关系的重要性进行估计和排名,并根据排名筛选正确知识.

2)RG:文献[8]提出计算基于规则引导的置信度和关联度来衡量知识的正确程度以进行筛选.

3)SP:本文提出的基于标准模式挖掘的方法,利用挖掘出的标准模式在更新知识图中模拟匹配来筛选.

4)SP+VD:本文提出的基于向量间距离的方法,向量化三元组知识和标准模式,通过计算向量间距离来筛选.

图8为采用4种不同方案(TI方法、RG方法、SP方法、SP+VD方法)筛选数据集D2的比较分析图,由图8可知在同一数据集上,本文提出的SP方法和SP+VD方法在精准率、召回率和F1这3个指标上均比TI方法对三元组知识进行正确和错误的分类的效果好,精准率分别高12.1%和9.3%,召回率分别高15.1%和6.8%,F1分别高13.79%和13.35%.RG方法相对于TI方法精准率有提升但仍不够高,本文的SP方法和SP+VD方法分别比RG方法高1.34%和0.9%.

图8 不同筛选方案比较分析图

6 总 结

提取知识图谱的模式信息,利用标准模式筛选更新的知识,对知识图谱的更新准确率具有重要的研究意义.本文提出一种基于标准模式的知识图谱筛选更新方法,该方法先挖掘出数据集上的标准模式,然后根据知识图谱更新的数据量多少,设计了两种筛选的方案,数据量较少时利用标准模式图模拟匹配更新知识图筛选错误的知识或是数据量较多时转化为向量后进行向量距离比较筛选,从而提高了知识更新筛选的准确率和召回率.本文提出的向量距离比较筛选方法的比较操作在不同的域中,可以分布式进行,未来在其规模化的基础上,进一步讨论如何筛选具有多对多关系的知识,且针对带有层次信息和动态知识更新继续开展研究工作.