知识图谱中的关联实体发现

李剑宇 岳昆

引用本文:
Citation:

知识图谱中的关联实体发现

    作者简介: 李剑宇(1993−),男,云南人,硕士生,主要研究数据与知识工程. E-mail:jylee@mail.ynu.edu.cn;
    通讯作者: 岳昆, kyue@ynu.edu.cn
  • 中图分类号: TP

Discovering association entities in Knowledge Graph

    Corresponding author: YUE Kun, kyue@ynu.edu.cn
  • CLC number: TP

  • 摘要: 知识图谱(Knowledge Graph, KG)中的关联实体发现任务旨在为用户输入的查询实体推荐一组最相关的实体集合. 许多实体在KG中没有显式地链接,但隐式地关联在用户生成的数据中. 因此,引入用户数据可得到更加丰富的实体关联信息,利用用户与实体的交互信息(记为用户−实体数据)可提高KG关联实体发现的准确性. 基于用户−实体数据中挖掘到的频繁项,首先,构建实体关联规则(Entity Association Rule, EAR)对实体间的关联信息建模,并利用置信度评估实体间的关联强度;然后,基于分支限界法算法获得最优的实体关联规则,得到与查询实体最相关的关联实体集合. 在两个真实世界数据集上的实验结果表明,相较于传统基于KG结构的方法,EAR发现top 1关联实体的准确率分别提高了10.7%、4.1%.
  • 图 1  用户与实体的交互实例

    Figure 1.  Example of interaction between users and entities

    图 2  top-k关联实体发现的准确率对比

    Figure 2.  Comparison of precision of discovered top-k association entities

    图 3  top-k关联实体发现结果的召回率对比

    Figure 3.  Comparison of recall of discovered top-k association entities

    图 4  top-k关联实体发现结果的F1值对比

    Figure 4.  Comparison of F1-score of discovered top-k association entities

    表 1  节点属性

    Table 1.  Attributes of the node

    属性描述
    nl节点所在层数
    np节点的父亲
    nc标志位:生成左孩子标志为1,生成右孩子标志为0
    csum节点获得的置信度之和
    Ssum节点获得的实体集合
    下载: 导出CSV

    表 2  数据集统计信息

    Table 2.  Statistics of datasets

    数据集MovieLensUserBehavior
    用户数162 541978 994
    商品数62 4234 162 024
    商品类型数1 093 3609 439
    用户行为数25 000 095100 150 807
    下载: 导出CSV
  • [1] Gu Y, Zhou T S, Cheng G, et al. Relevance search over schema-rich knowledge graphs[C]//Proceedings of the 12th ACM International Conference on Web Search and Data Mining, ACM, Melbourne, Australia, 2019: 114-122.
    [2] 黄际洲, 孙雅铭, 王海峰, 等. 面向搜索引擎的实体推荐综述[J]. 计算机学报, 2019, 42(7): 1 467-1 494. Huang Z J, Sun Y M, Wang H F, et al. A survey of entity recommendation in web search[J]. Chinese Journal of Computers, 2019, 42(7): 1 467-1 494.
    [3] Lu X L, Pramanik S, Roy R S, et al. Answering complex questions by joining multi-document evidence with quasi knowledge graphs[C]//Proceedings of the 42nd International ACM SIGIR Conference,Paris, France, ACM, 2019: 105-114.
    [4] Wang H W, Zhao M, Xie X, et al. Knowledge graph convolutional networks for recommender systems [C]//Proceedings of the 28th World Wide Web Conference, ACM, San Francisco, CA, USA, 2019: 3 307-3 313.
    [5] He G L, Li J Y, Zhao W X, et al. Mining implicit entity preference from user-item interaction data for knowledge graph completion via adversarial learning[C]//Proceedings of the 29th World Wide Web Conference, ACM, Taipei, China, 2020: 740-751.
    [6] Zhou T S, Li Z Y, Cheng G, et al. GREASE: A generative model for relevance search over knowledge graphs[C]//Proceedings of the 13th ACM International Conference on Web Search and Data Mining, ACM, Houston, USA, 2020: 780-788.
    [7] Sun S X, Luo Q. Scaling up subgraph query processing with efficient subgraph matching[C]//Proceedings of the 35th IEEE International Conference on Data Engineering, IEEE, Macao, China, 2019: 220-231.
    [8] Jayaram N, Khan A, Li C K, et al. Querying knowledge graphs by example entity tuples[C]//Proceedings of the 32nd IEEE International Conference on Data Engineering, IEEE Computer Society, Helsinki, Finland, 2016: 1 494-1 495.
    [9] Yang S Q, Han F Q, Wu Y H, et al. Fast top-k search in knowledge graphs[C]//Proceedings of the 32nd IEEE International Conference on Data Engineering, IEEE Computer Society, Helsinki, Finland, 2016: 990-1 001.
    [10] Ponza M, Ferragina P, Chakrabarti S. On computing entity relatedness in wikipedia, with applications[J]. Knowledge Based Systems, 2020, 188: 1 957-1 964.
    [11] 郑玉艳, 田莹, 石川. 一种元路径下基于频繁模式的实体集扩展方法[J]. 软件学报, 2018, 29(10): 2 915-2 930. Zheng Y Y, Tian Y, Shi C. Method of entity set expansion based on frequent pattern under meta path[J]. Journal of Software, 2018, 29(10): 2 915-2 930.
    [12] Chen J, Chen Y G, Zhang X L, et al. Entity set expansion with semantic features of knowledge graphs[J]. Web Semantics, 2018, 52: 33-44.
    [13] Han J W, Kamber M, Pei J. Data mining: concepts and techniques[M]. 3rd ed. San Mateo, CA: Morgan Kaufmann Publishers, 2011.
    [14] Harper F M, Konstan J A. The movielens datasets: history and context[J]. ACM Transactions on Interactive Intelligent Systems, 2016, 5(4): 1-9.
    [15] Christopher D M, Prabhakar R, Hinrich S, et al. Introduction to information retrieval[M]. Cambridge: Cambridge University Press, 2008.
  • [1] 周剑云王丽珍何婧 . 基于封闭项目关联规则集压缩方法. 云南大学学报(自然科学版), 2004, 26(4): 301-305.
    [2] 刘云向婵 . 基于虚构理论对不平衡数据集中少数类关联规则挖掘的研究. 云南大学学报(自然科学版), 2017, 39(1): 33-38. doi: 10.7540/j.ynu.20160221
    [3] 赵晓娟贾焰李爱平常春喜 . 多源知识融合技术研究综述. 云南大学学报(自然科学版), 2020, 42(3): 459-473. doi: 10.7540/j.ynu.20190481
    [4] 夏姜虹 . 数据挖掘技术的常用方法分析. 云南大学学报(自然科学版), 2011, 33(S2): 173-175.
    [5] 方刚熊江吴鸿娟钟静 . 基于区间映射的约束拓扑关联规则挖掘. 云南大学学报(自然科学版), 2011, 33(5): 521-526.
    [6] 蔡鹏飞岳昆李雪刘惟一 . 一种基于概率图模型的关联规则更新方法. 云南大学学报(自然科学版), 2013, 35(2): 155-161. doi: 10.7540/j.ynu.20120511
    [7] 陈丽丽何银梅谢崇伟 . 随机Logistic模型的稳态关联函数. 云南大学学报(自然科学版), 2012, 34(4): 420-424.
    [8] 张春霞纪开萍何明霞曹旸刘静王文兵 . 暗褐网柄牛肝菌子实体营养成分分析. 云南大学学报(自然科学版), 2010, 32(6): 702-704 .
    [9] 徐广义严馨余正涛周丽华 . 融合跨语言特征的柬埔寨语命名实体识别方法*. 云南大学学报(自然科学版), 2018, 40(5): 865-871. doi: 10.7540/j.ynu.20170593
    [10] 刘文星邱仕瑜陈毅坚董淼周敏 . 无柄灵芝子实体中的灵芝酸类化合物. 云南大学学报(自然科学版), 2020, 42(3): 553-559. doi: 10.7540/j.ynu.20190525
    [11] 刘云黄亚飞 . 扩展算法在频繁行为模式分析中的优化研究. 云南大学学报(自然科学版), 2018, 40(2): 236-242. doi: 10.7540/j.ynu.20170314
    [12] 胡俊潘志锋张静 . 酵母基因启动子序列结构与转录频率的关联性分析. 云南大学学报(自然科学版), 2010, 32(5): 594-600, .
    [13] 于占东赵自保曾春华谢崇伟 . 色关联噪声驱动双稳系统平均首通时间的研究. 云南大学学报(自然科学版), 2009, 31(5): 493-498 .
    [14] 阎春恒吴小平 . 云南西北部强震前地震活动空间关联维的降维过程. 云南大学学报(自然科学版), 2007, 29(3): 266-271.
    [15] 焦善庆龚自正许弟余 . Planck粒子、磁单极子和亚夸克超对称伴子的相互关联. 云南大学学报(自然科学版), 2005, 27(3): 220-222.
    [16] 金康付照中吴滨金乐 . 基于Soave−Redlich−Kwong气体物态方程的CH4焓、熵图数值计算及关联应用程序开发. 云南大学学报(自然科学版), 2020, 42(3): 485-491. doi: 10.7540/j.ynu.20190376
    [17] 岳昆李维华苏茜刘惟一 . XML查询中的频繁路径选择. 云南大学学报(自然科学版), 2007, 29(3): 241-246.
    [18] 徐丽华李文均崔晓龙李铭刚张利平徐平毛培宏文孟良李一青姜成林 . 新疆青海极端环境发现大量未知放线菌. 云南大学学报(自然科学版), 2003, 25(3): 283-292.
    [19] 汤雪高飞施洪贞张建营胡刚 . 基于社区发现算法的傣族水文化模型研究. 云南大学学报(自然科学版), 2015, 37(S1): 5-. doi: 10.7540/j.ynu.20150194
    [20] 方刚袁刚 . 一种用于移动计算的约束频繁邻近类别集挖掘算法. 云南大学学报(自然科学版), 2012, 34(3): 265-270.
  • 加载中
图(4)表(2)
计量
  • 文章访问数:  417
  • HTML全文浏览量:  350
  • PDF下载量:  27
  • 被引次数: 0
出版历程
  • 收稿日期:  2021-02-01
  • 录用日期:  2021-06-06
  • 网络出版日期:  2021-07-23
  • 刊出日期:  2021-11-15

知识图谱中的关联实体发现

    作者简介:李剑宇(1993−),男,云南人,硕士生,主要研究数据与知识工程. E-mail:jylee@mail.ynu.edu.cn
    通讯作者: 岳昆, kyue@ynu.edu.cn
  • 云南大学 信息学院,云南 昆明 650500

摘要: 知识图谱(Knowledge Graph, KG)中的关联实体发现任务旨在为用户输入的查询实体推荐一组最相关的实体集合. 许多实体在KG中没有显式地链接,但隐式地关联在用户生成的数据中. 因此,引入用户数据可得到更加丰富的实体关联信息,利用用户与实体的交互信息(记为用户−实体数据)可提高KG关联实体发现的准确性. 基于用户−实体数据中挖掘到的频繁项,首先,构建实体关联规则(Entity Association Rule, EAR)对实体间的关联信息建模,并利用置信度评估实体间的关联强度;然后,基于分支限界法算法获得最优的实体关联规则,得到与查询实体最相关的关联实体集合. 在两个真实世界数据集上的实验结果表明,相较于传统基于KG结构的方法,EAR发现top 1关联实体的准确率分别提高了10.7%、4.1%.

English Abstract

  • 知识图谱(Knowledge Graph,KG)中的关联实体发现任务,旨在为用户输入的查询实体推荐最相关的实体集合[1]. 准确地为用户输入的查询返回关联实体,不仅能够加强用户的查询体验,还能有效地提高用户的参与度. 近年来,随着KG在搜索引擎[2]、智能问答[3]和个性化推荐[4]等领域应用的日益广泛,用户对关联实体发现的需求与日俱增. 与此同时,用户在KG下游应用中与实体的交互也产生了大量的行为数据[5],称为用户−实体数据. 值得注意的是,KG中的实体间的关联往往体现在用户−实体数据中,并且具有不确定性. 例如,在图1所示的KG中,某一用户对电影“终结者:黑暗命运”给出“喜欢”的评价,则该用户也有90%的概率会对电影“阿凡达”给出“喜欢”评价. 这种不确定性是对真实世界中实体依赖的定量描述,本文将其作为关联度. 针对KG中给定的实体,找到与之相关联的实体集合,是关联实体发现的基本任务[6],通过计算实体间的关联度,以更细的粒度回答关联实体查询,能够得到更加符合KG实际应用的结果. 因此,如何有效地计算实体之间的关联度,是关联实体发现的关键.

    图  1  用户与实体的交互实例

    Figure 1.  Example of interaction between users and entities

    近年来,国内外学者基于KG的结构特征对关联实体发现做了大量研究,主要包括子图匹配和实体相似度计算两类方法.

    基于子图匹配的方法是将用户输入的查询表示为一个小型查询图,从KG中找出与查询图匹配的前k个子图[7]. 例如,Jayaram等[8]提出了基于实体元组查询的方法,在KG中查找与给定元组近似的top-k元组集合; Yang等[9]提出STAR模型来提高大规模KG中查询关联实体的效率. 然而,这类基于子图匹配的方法开销十分昂贵,并且不能描述实体之间的隐含关联.

    一些学者通过实体间的相似度计算来发现关联实体. 例如,Ponza等[10]在KG中创建一个围绕两个查询实体动态增长的加权子图,然后使用已知的相关性度量方法计算子图中的边权重,从而得到实体间的关联度;文献[11]将KG建模为一个异质网络,基于元路径捕捉种子实体之间的潜在共同特征,从而发现关联实体;Chen等[12]基于路径的语义特征来发现关联实体,通过处理知识图的不完全性,提出概率模型来对实体进行排序.

    上述方法在利用KG结构发现关联实体方面取得了很好的效果,但在考虑到用户行为时,这些方法不足以获得足够的实体间隐含的关联信息,从而难以满足用户的查询需要. 例如,在图1所示的KG中查询与“终结者:黑暗命运”相关联的实体,对于喜欢“詹姆斯·卡梅隆”电影作品的用户而言,可能有90%的概率在喜欢电影“终结者:黑暗命运”的同时也喜欢“阿凡达”,而只有40%的概率同时喜欢电影“死侍”. 然而,KG可能会优先给出“死侍”作为关联实体反馈给用户,因为“死侍”和“终结者:黑暗命运”在KG中具有相同的导演“蒂姆·米勒”.

    从KG的应用和数据分析来看,KG中实体间的关联信息蕴含在用户−实体数据中. 例如,与“泰坦尼克号”相比,“终结者:黑暗命运”和“阿凡达”的关联更强,因为喜欢“终结者:黑暗命运”的用户有更高的概率也喜欢“阿凡达”,而不是“泰坦尼克号”. 因此,本文将用户−实体数据中所蕴含的知识作为对KG所描述领域知识的补充,通过计算用户−实体数据中实体之间的关联度,获得更为准确、完整的关联实体集合. 具体而言,首先根据给定的查询实体,基于KG的结构描述的领域知识抽取一部分候选实体,通过用户−实体数据蕴含的知识计算候选实体与查询实体间的关联度,返回与查询实体最相关的一组实体集合. 为此,我们考虑以下两方面的问题:① 如何从KG中抽取候选实体集?② 如何计算实体间的关联强度?

    为了从KG中获取候选实体集,以查询实体为“中心”,利用广度优先搜索(Breadth First Search, BFS)抽取KG的子图. 通过观察实体在用户−实体数据中的特点设计一种加权函数来计算KG子图中实体的权值,从而获得权值最高的一组实体,将其作为候选实体集. 然而,基于KG领域知识获得的候选实体并不能反映用户−实体数据中实体之间真实的关联关系,并且无法计算实体间的关联度.

    以Apriori算法为代表的频繁模式挖掘,是从数据中挖掘频繁项的经典方法[13]. 通过从用户−实体数据中挖掘频繁实体,能够生成表示实体之间依赖关系的关联规则,即形如AB的蕴含式;置信度表示数据中包含A的事务也会包含B的事务的概率[13]. 为了描述查询实体与候选实体之间的关联关系,我们基于关联规则构建实体关联规则(Entity Association Rule,EAR). 通过EAR的置信度来定量描述实体之间的依赖关系,作为查询实体与候选实体之间的关联度. 进一步,基于分支限界法得到具有最大置信度的EAR集合,从而获得一组具有最高关联度的关联实体. 在真实世界数据集上的实验结果验证了本文提出方法的有效性.

    • 下面给出KG和用户−实体数据的定义.

      定义 1 KG是一个表示为G =(E, $ \mathcal{R} $, A)的有向图,其中E表示KG中实体对应节点的集合,$ \mathcal{R} $ 表示实体关系对应边的集合,A(e)是将实体e与其属性相关联的函数.

      例 1 针对图1所示的KG,实体“阿凡达”的属性为A(阿凡达)={动作,科幻}.

      定义 2 用户−实体数据表示为Ω={<u, d>|uU, dD}的二元组集合,其中U表示用户集合,D表示实体集合,二元组<u, d>表示用户u与实体集d之间产生了交互行为.

      给定一个KG,G =(E, $ \mathcal{R} $, A)和查询实体eq,首先从G中抽取一部分可能与eqΩ中关联的候选实体集Ec. 为此,以eq为“中心”,利用BFS算法从G中抽取出子图Gs. 设计加权函数来计算Gs中除了eq以外实体的权值,以获得具有最高权值的实体并将其加入Ec. 直观地,权值应满足以下性质:

      (1)KG中任意一个实体与eq之间的最短路径越短,则它与eq越有可能关联,因此,权值与实体间的最短路径成反比;

      (2)Gs中具有某一属性的实体出现的频率越高,则具有该属性的实体与eq越有可能关联. 例如,若eq类型是“导演”,则它常常与类型为“电影”、“演员”的实体一同出现在真实世界的数据中.

      下面给出满足以上性质(1)和(2)的权值计算公式:

      $ W\left(e\right)=\frac{F\left(e\right)/F\left({G}_{{\rm{s}}}\right)}{\sqrt{\mathcal{l}\left(e\right)}}, $

      其中,$ \mathcal{l} $(e)表示eeq间的最短路径长度,F(e)表示A(e)在Gs中的频率,F(Gs)表示GsA的数量.

      为了获取m个候选实体,首先从eq出发,基于BFS算法对G进行搜索,遍历第1层实体得到子图Gs. 然后,根据公式(1)计算Gseq以外所有实体的权值,并根据权值大小依次把实体添加至候选实体集合,再继续遍历下一层实体. 重复上述操作直到获得m个候选实体. 上述思想见算法1.

      算法1 获取候选实体集

      输入 G =(E, $ \mathcal{R} $, A):输入的KG;eq:查询实体;m:获取的候选实体数.

      变量 Gs=(Es, $ \mathcal{R} $s, As):KG子图;l:广度优先搜索步长.

      输出 Ec:候选实体集合.

      步骤1 初始化:Ec$\emptyset $Gs$\emptyset $l←1;i←1;

      步骤2 eq为中心,利用BFS得到Gi层子图Gs

      步骤3 若|Es|≥m,执行下一步;否则,i++,执行步骤2;

      步骤4 利用式(1)计算Es中所有实体的权值,根据权值大小将Es中的实体加入Ec,直到|Ec|=m

      步骤5 输出Ec.

      若BFS抽取Gs的总实体数为En,则BFS时间复杂度为O(|En|2),将m个候选实体加入Ec时间复杂度为O(|m|). 因此,算法1的时间复杂度为O(|En|2+ O(|m|)).

      例 2 针对图1所示的KG,从查询实体“终结者:黑暗命运”来获取4个候选实体. 首先基于BFS搜索步长1范围内的实体,得到子图中的实体集合Es={终结者:黑暗命运(科幻),詹姆斯·卡梅隆(导演,制片),蒂姆·米勒(导演)}. 由式(1)计算实体“詹姆斯·卡梅隆”与“蒂姆·米勒”的权值分别为0.75与0.5,将其加入候选实体集Ec. 继续遍历下一层的实体并重复上述步骤. 最终得到候选实体集为Ec={詹姆斯·卡梅隆,蒂姆·米勒,阿凡达,死侍}.

    • 通过算法1抽取m个权值最高的候选实体,记为Ec={e1, e2,…, em}. 为了构建表示实体之间依赖关系的关联规则,采用Apriori算法从Ω中挖掘出满足最小支持度的候选实体集L,并通过以下公式计算置信度:

      $ c\left({e}_{u}\to {e}_{v}\right)=\frac{s\left({e}_{u}\cup {e}_{v}\right)}{s\left({e}_{u}\right)},(u,v \subseteq L,u\ne v), $

      其中,$ s\left({e}_{u}\cup {e}_{v}\right) $D中包含 $ {e}_{u}\mathrm{和}{e}_{v} $d的数目,$ s\left({e}_{u}\right) $D中包含 $ {e}_{u} $d的数目.

      使用以下步骤[13]生成关联规则:

      步骤1 对于L中的每个频繁项集l,产生所有的非空子集;

      步骤2 对于l中的每个非空子集ls,如果 $ \dfrac{\mathrm{s}\left({e}_{u}\cup {e}_{v}\right)}{s\left({e}_{u}\right)} $Cmin,则输出规则“ls→(lls)”,其中,Cmin是最小置信度的阈值.

    • 为了描述 $ {e}_{{\rm{q}}} $L中实体的依赖关系,引入如下关联规则:

      $ {e}_{{\rm{q}}}\to {e}_{1}\wedge {e}_{2}\wedge \dots \wedge {e}_{j},(j\leqslant m,{e}_{j}\in L) ,$

      其中,$ {e}_{{\rm{q}}} $$ {e}_{1}\wedge {e}_{2}\wedge \dots \wedge {e}_{j} $ 分别称为规则头和规则体.

      把具有如(3)式的关联规则称作EAR,所有EAR的集合记为H.

      EAR的置信度描述了 $ {e}_{{\rm{q}}} $ 与候选实体集之间的关联度. 因此,基于置信度选取一部分EAR、以获取具有最高关联度的前k个关联实体. 不难发现,规则体中具有相同候选实体的不同EAR之间存在冲突. 例如,若H中存在 $ {e}_{{\rm{q}}}\to {e}_{1}\wedge {e}_{2} $$ {e}_{{\rm{q}}}\to $$ {e}_{1}\wedge {e}_{3} $ 两个EAR,其置信度分别为0.7和0.9. 已选择前者时,后者中的实体可能不会添加到关联实体集合中. 因此,在各EAR规则体互不相交的条件下,如何得到具有最高置信度的一组EAR是获取关联实体的关键. 形式化描述如下:

      $ \begin{array}{l}\max \left\{\displaystyle\sum\limits_{i=1}^{\left|H\right|}{c}_{i}{x}_{i}\right\}, \\ \displaystyle\sum\limits_{i=1}^{\left|H\right|}{B}_{i}{x}_{i}=k,({x}_{i}\in \left\{\mathrm{0,1}\right\},1\leqslant i\leqslant \left|H\right|),\end{array} $

      其中,i表示H中EAR的序号,ci表示Hi的置信度,Bi表示Hi规则体中的实体集合,xi表示是否选取第i条EAR.

      对于上述优化问题,采用分支限界法来获得最优EAR. 形式化描述如下:

      (1)解空间树 解空间树为子集树. 子集树中的节点作为一个EAR对象,其属性如表1所示.

      属性描述
      nl节点所在层数
      np节点的父亲
      nc标志位:生成左孩子标志为1,生成右孩子标志为0
      csum节点获得的置信度之和
      Ssum节点获得的实体集合

      表 1  节点属性

      Table 1.  Attributes of the node

      (2)限界函数 对H中所有EAR按照单位实体的置信度(即 $ {c}_{i}/{|B}_{i}| $)排序. 假设遍历到子集树的第i层(i=1,2,…,|H|),则此节点的上界限界函数为:

      $ {c}_{{\rm{up}}}={c}_{{\rm{sum}}}+|{E}_{{\rm{c}}}-{S}_{{\rm{sum}}}|\times ({c}_{i+1}/{|B}_{i+1}|). $

      (3)最大堆 在子集树的生成过程中,采用最大堆存储和选择扩展节点,以生成解空间,即用二叉树构造最大堆,节点按cup排序,根节点具有最高优先级.

      上述思想见算法2.

      算法2 获取最优关联实体集合

      输入 H:所有EAR集合;c:EAR置信度集合; Ec:候选实体集合.

      变量 B:EAR规则体中的实体集合;cmax:获得置信度的最大值.

      输出 ∑:最优EAR集合.

      步骤1 初始化:初始一个空的最大堆 h ;初始一个子集树;根据每条EAR的单位实体置信度对 H 排序; ∑ ←$\emptyset $i ←1;

      步骤2 Hi 置为子集树根节点,根据式(4)计算 Hi 的上界函数值,并加入 h

      步骤3 获取 h 根节点 X ,将 Xh 中删除并更新 hX 所在子集树层数 iX.nl

      步骤4  i ++; BiHi 规则体中的实体集合;若 BiX.Ssum =$\emptyset $,执行下一步;否则,执行步骤6;

      步骤5 Hi 生成左孩子 XlXl.nc ←1; Xl.SsumX.SsumBiXl . csumX.csum + ciXl.npXcmaxX.csum + ci ;将 Xl 加入 h

      步骤6 Hi 生成右孩子 XrXr.nc ←0;Xr.SsumX.SsumXr.csumX.csumXr.np ← X;根据式(4)计算 Xr 上界函数值,若 Xr.cupcmax ,将 Xr 加入 h ;否则,丢弃该节点;

      步骤7 重复步骤3~7,直到 i > |H|;

      步骤8 X ←子集树中具有最大 csum 值的叶子节点; i ←|H|;

      步骤9 X.nc =1; ∑ ← ∑ ∪{Hi}; XX.np

      步骤10  i−−;重复步骤9直到 i =1;

      步骤11 输出 ∑

      步骤3~7的时间复杂度为O(2|H|). 步骤10~11的时间复杂度为O(|H|). 将节点插入h的时间复杂度为O(log2(|H|)). 因此,算法2的时间复杂度为O(log2(|H|)×2|H|+|H|).

      通过获取∑中所有EAR规则体中的实体,得到与eq具有最高关联度的关联实体集合.

    • 实验在两个真实世界的数据集上进行:①来自MovieLens[14]的用户电影评分数据,评分以5星为标准,以半星为增量(0.5星至5.0星). 如果用户对电影的评分大于4.0,则为该用户与电影创建“喜欢”关系, 此外,每一部电影与其类型之间存在“类型为”的关系;②来自淘宝名为UserBehavior(https://tianchi.aliyun.com/dataset/dataDetail?dataId=649&userId=1)的用户行为数据集,用户行为的类型(点击,购买,购物车,偏好)作为用户与项目之间的关系(例如,〈用户,购买,项目〉).

      对于每个数据集,采用70%作为训练数据,30%作为测试数据. 在训练数据集中,提取一部分数据来构建KG,其余的作为外部数据来挖掘实体的关联. 表2给出上述两个数据集的统计信息.

      数据集MovieLensUserBehavior
      用户数162 541978 994
      商品数62 4234 162 024
      商品类型数1 093 3609 439
      用户行为数25 000 095100 150 807

      表 2  数据集统计信息

      Table 2.  Statistics of datasets

    • 使用准确率(P)、召回率(R)、F1分数(F1)来测试EAR推断的前k个关联实体的有效性,定义如下:

      $ P=\frac{{T}_{{\rm{p}}}}{{T}_{{\rm{p}}}+{F}_{{\rm{p}}}}, $

      $ R=\frac{{T}_{{\rm{p}}}}{{T}_{{\rm{p}}}+{F}_{{\rm{N}}}} ,$

      $ {{\rm{F}}}{1}=\frac{2 P R}{P+R}, $

      其中,TPFPFN分别是正确发现的实体数、错误发现的实体数和未发现的实体数.

    • GQBE[8]和TSF[10]作为仅以KG为知识来源发现关联实体的对比方法. Jaccard相似系数[15]作为分别以KG(Jaccard-KG)或用户实体数据(Jaccard-D)为知识来源发现关联实体的对比方法.

    • 在一台2.5 GHz Intel Core i5-10300H CPU和16GB RAM的机器上用Java实现本文提出的算法.

    • 为了测试基于本文方法发现关联实体的有效性,将前k个关联实体发现的准确率(P@k)与基于其他模型的计算结果进行比较,如图2所示,可得到以下结论:

      图  2  top-k关联实体发现的准确率对比

      Figure 2.  Comparison of precision of discovered top-k association entities

      (1)EAR在两个数据集中都取得了最高的准确率. 与准确率此高的模型相比,EAR在MovieLens数据集的top 1、top 5和top 10的关联实体发现中,准确率分别提高了10.7%、9.9%和6%. 在UserBehavior数据集的top 1、top 5和top 10的关联实体发现中,准确率分别提高了4.1%、2.2%和1%.

      (2)仅依靠KG作为知识来源的模型(GQBE,TSF和Jaccard-KG)在UserBehavior数据上的准确率比在MovieLens数据集上的得分低,这是因为UserBehavior数据集中用户与实体之间的交互具有较强的随机性,导致构建的KG中的实体关联相对较弱. 与这些方法不同,EAR通过结合KG外部的用户实体数据计算实体之间的关联度,从而能在实体关联较弱的KG中更准确地得到关联实体.

      为了进一步测试基于EAR发现关联实体的有效性,将前k个关联实体发现的召回率(R@k)和F1值(F1@k)与其他模型进行了比较,结果如图3图4所示. 我们观察到:

      图  3  top-k关联实体发现结果的召回率对比

      Figure 3.  Comparison of recall of discovered top-k association entities

      图  4  top-k关联实体发现结果的F1值对比

      Figure 4.  Comparison of F1-score of discovered top-k association entities

      (1)EAR的召回率随着k值增大而稳定上升,且与其他4种模型在不同k值下的召回率差距不大.

      (2)EAR在UserBehavior数据集中获得了最高的F1分数. 当k值大于5时,EAR在MovieLens数据集中与其他模型相比能得到最高的F1分数. 具体而言,相比于F1分数次高的模型,EAR在UserBehavior数据集的top 1、top 5和top 10关联实体发现中,F1分数分别提高了4.4%、3.4%和1.6%. 在MovieLens数据集的top 6和top 10关联实体发现中,F1值分别提高了5.1%和4.5%.

    • 本文基于关联规则表示KG查询实体和关联实体间的不确定性依赖关系. 相较于基于KG结构的传统模型,通过将用户−实体数据相结合,关联实体发现的准确率有较大提升. 对于实体之间关联较弱的KG,EAR能通过结合数据中的知识对KG领域知识进行补充,从而更有效地发现实体之间的关联.

      实验还应该考虑以Wikipedia和Freebase为代表的大规模KG数据集,进一步测试本文提出方法的普遍性和实用性. 基于本文的方法获取候选实体集时,未能充分利用KG实体之间路径的语义关系,如何有效利用KG中的路径信息发现候选实体集,是我们未来要开展的工作.

参考文献 (15)

目录

    /

    返回文章
    返回