基于MapReduce的大规模本体匹配方法研究 张航 指导老师：瞿裕忠教授、胡伟老师

语义Web本体 <owl:Class rdf:ID=“Person”> <rdfs:subClassOf> <owl:Restriction> <owl:maxCardinality>1</owl:maxCardinality> <owl:onProperty rdf:resource=“#hasSSN” /> </owl:Restriction> </rdfs:subClassOf> </owl:Class> <owl:Class rdf:ID=“SSN” /> <owl:ObjectProperty rdf:ID=“hasSSN” />

大规模本体匹配 大型本体匹配 大量本体匹配 Hang_Zhang hang.z

摘 要 一种基于MapReduce的大型本体匹配方法 基于MapReduce的大量本体匹配框架

摘 要 一种基于MapReduce的大型本体匹配方法 基于MapReduce的大量本体匹配框架

主要思路 利用本体匹配中虚拟文档相似度技术 (V-Doc) 利用MapReduce将实体与其相关的RDF语句做连接 利用一种高相关度单词的实体集合划分算法缩小计算空间

一种基于MapReduce的大型本体匹配方法 本体预处理 构建描述信息 获取邻接结点 信息 匹配虚拟文档 V-Doc+ 算法流程图

构建描述信息（实体） … “Teacher” Local Name rdfs:label 𝐶 1 “People” rdfs:comment “Teach students” “Teacher” rdfs:label Desc 𝐶 1 = 𝛼 1 Teacher+ 𝛼 2 People+ 𝛼 3 (Teach+student)+ 𝛼 4 (…)

构建描述信息（实体） Example: Map: C1 Map: (C1, P2, L4,) Reduce: (C1: L4+ L5) 实体与RDF语句等值连接 Example: Map: C1 Map: (C1, P2, L4,) Reduce: (C1: L4+ L5) Map: (C1, P1, L5,)

构建描述信息（空白结点） 𝐷𝑒𝑠𝑐 𝑘+1 𝑏 =𝛽∗( 𝐷𝑒𝑠𝑐 1 𝑏 + 𝑠𝑢𝑏𝑗 𝑠 =𝑏 𝑜𝑏𝑗(𝑠)∈𝐵 𝐷𝑒𝑠𝑐 𝑘 (𝑜𝑏𝑗(𝑠)) ) 𝐷𝑒𝑠𝑐 1 𝑏 = 𝑠𝑢𝑏𝑗 𝑠 =𝑏 𝐷𝑒𝑠𝑐 (𝑝𝑟𝑒𝑑(𝑠)) + 𝑠𝑢𝑏𝑗 𝑠 =𝑏 𝑜𝑏𝑗(𝑠)∉𝐵 𝐷𝑒𝑠𝑐(𝑜𝑏𝑗(𝑠))

构建描述信息（空白结点） b29 c26 b10 “literal” “literal”

构建描述信息（空白结点） Step1: 重写空白结点结构，在MapReduce的传输中可携带已到达的结点信息。 实体、空白结点与RDF语句等值连接 Step1: 重写空白结点结构，在MapReduce的传输中可携带已到达的结点信息。 Step2: Map阶段：(Desc(b1), (b1,c5)) --> (b1, Desc(b1)) (c5, Desc(b1)) Step3: Reduce阶段：(b1, Desc(b1))与所有以b1为主语的三元组聚合，添加下一步结点 (c5, Desc(b1))与c5的描述信息Desc(c5)聚合，更新b1描述信息Desc(b1) Step4: 合并所有与b1相关的结果

考虑邻接结点 Virtual Document 𝑉𝐷 𝑒 =𝐷𝑒𝑠𝑐 𝑒 +𝛾∗𝑁𝑒𝑖𝑔ℎ(𝑒) 𝑁𝑒𝑖𝑔ℎ 𝑒 = 𝑒′∈𝑆𝑁(𝑒) 𝐷𝑒𝑠𝑐(𝑒′) + 𝑒′∈𝑃𝑁(𝑒) 𝐷𝑒𝑠𝑐(𝑒′) + 𝑒′∈𝑂𝑁(𝑒) 𝐷𝑒𝑠𝑐(𝑒′) 𝑆𝑁(𝑒): 主语为e的三元组的谓词和宾语 P𝑁(𝑒):谓词为e的三元组的主语和宾语 O𝑁(𝑒):宾语为e的三元组的主语和谓词

考虑邻接结点 MapReduce对图的宽度搜索 Step1: 将每个结点的邻居结点ID通知给该结点

考虑邻接结点 Step2: 每个结点把自己的描述信息发送给邻居结点

考虑邻接结点：Step 1 对于每个三元组(s, p, o), 生成三组键值对(s, {p, o}), (p, {s, o}) and (o, {s, p}) 将每个结点的邻居结点ID通知给该结点. For example: (c1, Desc(c1)) + (c1, {b2, p4}) = (c1, (Desc(c1), {b2, p4}))

考虑邻接结点：Step 2 用邻居结点ID作为key，将每个结点自身描述信息发送给邻居结点 每个结点用收到的描述信息更新自身的描述信息

实体相似度计算 利用TF/IDF模型 余弦相似度 利用基于单词权重的划分方法 通过对本体内单词词频统计平均划分单词，以此平 衡负载 𝑠𝑖𝑚 𝑒 1 , 𝑒 2 = 𝑉𝐷( 𝑒 1 )×𝑉𝐷( 𝑒 1 ) 𝑉𝐷 𝑒 1 ∗|𝑉𝐷( 𝑒 2 )| >θ 利用基于单词权重的划分方法 对单词 𝑤𝑜𝑟𝑑 i , 𝑠𝑐𝑜𝑟𝑒 i 排序，使得 𝑠𝑐𝑜𝑟𝑒 1 ≥ 𝑠𝑐𝑜𝑟𝑒 2 ≥…≥ 𝑠𝑐𝑜𝑟𝑒 n 取得高相关度单词集合 {𝑤𝑜𝑟𝑑 1 , 𝑤𝑜𝑟𝑑 2 ,…, 𝑤𝑜𝑟𝑑 i }, 其中i是满 足以下式子的最小正整数： 𝑠𝑐𝑜𝑟𝑒 1 + 𝑠𝑐𝑜𝑟𝑒 2 +…+ 𝑠𝑐𝑜𝑟𝑒 i ≥ 𝛿𝜖(0,1] 通过对本体内单词词频统计平均划分单词，以此平 衡负载

实体相似度计算 实体集合的分割过程。

大型本体匹配实验 数据集 OAEI 2007 食物本体 FMA vs. GALEN

大型本体匹配实验 精确度、召回率和F1-measure

大型本体匹配实验 食物本体匹配耗时比较 在不同节点数目下的运行时间 V-Doc+ Falcon-AO DSSim RiMOM Prior+ 10分钟 6小时 1周 4小时 1.5小时 在不同节点数目下的运行时间

大型本体匹配实验 V-Doc+的各模块运行时间

大型本体匹配实验 V-Doc+在不同𝛿取值下情况（基于单词划分方法的参数）

基准数据集测试 数据集：OAEI Benchmark testbed #101-104：匹配实体的名称具有相似字符串特征。 #201-210：匹配实体有相似结构特征，但没有相似字符串特征。 #221-247：匹配实体没有相似结构特征，但有相似语言特征。 #248-266：匹配实体既没有相似结构特征，也没有相似语言特征。 #301-304：采用真实世界数据，具有混合特征。

基准数据集测试 #101–104 #201–210 #221–247 #248–266 #301–304 Average   #101–104 #201–210 #221–247 #248–266 #301–304 Average V-Doc+ (δ=0.80) 1.00 0.80 0.99 0.27 0.69 0.71 V-Doc+ (δ=0.99) 0.83 0.42 0.68 0.76 V-Doc 0.84 0.41 0.74 0.77 Falcon-AO 0.92 0.56 0.81 AUTOMS 0.97 0.32 COMA 0.95 0.96 0.60 0.73 DSSim 0.44 0.00 0.82 0.57 HMatch 0.01 0.54 0.53 JHU/APL 0.64 0.09 0.21 0.59 Prior+ 0.67 0.05 0.63 RiMOM 0.65 0.87 排到前5，名列前茅

相关论文 Zhang, H., Hu, W. Qu, Y.Z.: VDoc+: A Virtual Document Based Approach for Matching Large Ontologies Using MapReduce. Journal of Zhejiang University - SCIENCE C (SCI-Indexed), 2012. 257-267. Zhang, H., Hu, W., Qu, Y.Z.: Constructing Virtual Documents for Ontology Matching Using MapReduce. Proc. Joint International Conference of Semantic Web Technology (JIST), 2011. 48-63. Won Best Paper Award.

大量本体匹配 V-Doc+是一种大型本体的一对一匹配方法 假设有n个本体需要做匹配计算，那么一对一匹 配算法需要重复 n∗(n−1) 2 次。

摘 要 一种基于MapReduce的大型本体匹配方法 基于MapReduce的大量本体匹配框架 基于匹配任务划分的方案 基于本体内容划分的方案

基于匹配任务划分的方案

基于本体内容划分的方案 1. 匹配器内并行化方案并行度更大 2. 利用Feature划分数据集可减小计算空间

基于匹配任务划分 v.s.基于本体内容划分 直观对比 基于匹配任务划分 基于本体内容划分 便于实施 是 否 并行粒度 小（取决于本体数量） 大（取决于实体特征数量） 利用实体特征划分实体集

实验对比 数据集： OAEI Benchmark (66个本体) 匹配算法：余弦相似度 F1-measure对比 𝑆𝑖𝑚 𝐼 𝑎 , 𝐼 𝑏 = 𝑘 𝑓 𝑎𝑘 𝑓 𝑏𝑘 ( 𝑘 𝑓 𝑎𝑘 2 ) ( 𝑘 𝑓 𝑏𝑘 2 ) F1-measure对比   非并行匹配方案 基于匹配任务划分的并行化方案 基于本体内容划分的并行化方案 F1-measure 0.72 0.70

实验对比 实体数目对运行时间影响

实验对比 MapReduce节点数目对运行时间影响

实验对比 66个本体 4个本体

基于匹配任务划分 v.s.基于本体内容划分 实验结论 在运行耗时上，两种并行方案都比非并行方法有较大的提升 对于余弦相似度算法，尽管基于本体内容划分的并行度更大，但优 势并不明显，耗时不会始终随MapReduce节点数目增加而大幅度减 小。事实上，很多研究表明，匹配等算法的速度提升会在特定节点 环境下会收敛 对于余弦相似度算法，当本体数较多时，基于本体内容划分方案并 不一定会比基于匹配任务划分方案耗时更少。只有当本体数较少、 单个本体较大时才有优势。

总结 基于MapReduce设计了一种针对大型本体的匹配方法 基于MapReduce设计两种针对大量本体匹配的并行方案 引入虚拟文档相似度技术 利用MapReduce将实体与其相关的RDF语句做连接 利用MapReduce的图模型处理技术获取实体邻接结点信息 利用一种高相关度单词的实体集合划分算法缩小计算空间 基于MapReduce设计两种针对大量本体匹配的并行方案 在计算耗时上，两种并行方案都比非并行方法有较大的提升 在余弦相似度算法上对比两种方案

硕士期间发表论文 Zhang, H., Hu, W. Qu, Y.Z.: VDoc+: A Virtual Document Based Approach for Matching Large Ontologies Using MapReduce. Journal of Zhejiang University - SCIENCE C (SCI-Indexed), 2012. 257-267. Zhang, H., Hu, W., Qu, Y.Z.: Constructing Virtual Documents for Ontology Matching Using MapReduce. Proc. Joint International Conference of Semantic Web Technology (JIST), 2011. 48-63. Won Best Paper Award. Hu, W., Chen, J.F., Zhang, H., Qu, Y.Z.: How Matchable Are Four Thousand Ontologies on The Semantic Web. Proc. Extended Semantic Web Conference (ESWC), 2011. 290-304. Hu, W., Chen, J.F., Zhang H., Qu, Y.Z.: Learning Complex Mappings between Ontologies. Proc. Joint International Conference of Semantic Web Technology (JIST), 2011. 350-357.

谢 谢！