一种基于社会选择理论的本体聚集方法

朱泽宇， 钟 智， 陆建波*

(1.扬州大学 广陵学院，扬州 225000)(2.广西师范学院 计算机与信息工程学院， 南宁 530023)

语义Web作为人工智能的一个研究热点已经得到广泛关注．本体对Web信息提供了完全形式化的语义描述,可以实现知识共享和重用,在一定程度上提高了计算机对信息进行访问和搜索的能力．由于不同的用户可以构造不同的本体,导致了同一个领域中会产生许多不同的本体．由于异构本体之间很难实现互操作,严重限制了语义Web的发展,而本体的集成、映射、合并可以有效解决这类问题[1-2]．本体合并是最为常见的分布式语义融合方式之一,以期望形成一个更大的语义共享空间[3]．在本体合并形成的语义空间里,不同的网页信息可以用多个本体描述;在本体合并中通过聚集函数产生一个新的上层本体,以协调不同本体之间的差异．

本体是概念化的形式化规格说明,反应了人类对客观世界的认知,具有明显的社会属性[4]．因此,从社会选择理论的视角来看,本体合并可以转化为研究个体偏好和集体选择之间的关系,形成能达成共识的最优的群体认知．投票理论和判定聚集等都是社会选择中比较经典的应用,通过社会选择函数生成一个代表整体偏好的最终决策,也为本体聚集提供了理论基础[5]．

本体映射通过制定一系列规则来建立本体之间的关联,它不会破坏源本体的结构．在本体映射的研究中,有学者分析了整个映射过程的方法，例如文献[6]中提出了一种基于手动编码规则的识别本体之间映射的方法，并证明了该方法的优越性;文献[7]中介绍了本体映射的基本框架，并且设计了一种通用的本体映射过程用以研究和比较不同的映射方法；文献[8]中重点讨论了如何利用实体类的相似度来进行本体映射，在语义Web的背景下,利用机器学习，通过计算概念实体之间的相似度，建立本体间的映射关系．

本体合并是通过输入两个或多个源本体生成一个新的本体的过程,新本体可以提供反馈从而指导分布式本体的自我修正,它相对源本体来说结构发生了改变．文献[9]中提出了一种基于概念代数的本体合并方法,该方法可以用可视化的概念网形式表示本体并通过运算实现概念之间的合并,建立了概念代数与OWL(web ontology language)的对应关系,为本体合并提供了一个新视角．

本体映射和合并都是实现异构本体互操作的有效方法,其关键技术都依赖于本体相似度的计算．文献[10]中提出了基于Jaccard相似度的计算关键字之间的相似性度量方法．实验结果表明,该方法在测量单词中每个字母相似度时具有很好的性能．文献[11]中提出了一种基于Jaccard相似度和位置行为的协同过滤推荐算法,改善了传统的推荐算法．文献[12]中将社会选择中的投票理论运用在本体合并领域中,将本体提供者看作是投票者,通过社会选择函数选举出群体本体作为最终决策．

社会选择理论主要研究如何将个人偏好聚集为一个群体偏好,其中包含的大量的社会选择函数用来聚集个体偏好．在语义Web、多智能体系统、本体合并等领域中将社会选择理论和计算机科学相结合,既拓展了社会选择的理论研究范围,又为解决人工智能等领域的问题提供了新思路．文中采用社会选择理论，实现了本体聚集.

1 本体聚集问题描述

1.1 基本概念和性质

社会选择主要研究如何将个人偏好聚集为一个群体偏好．给定选项集合A,群体中n个个体可以根据个人意愿对A中的元素排序,并汇报自己的个人偏好Ri，最后通过一个社会选择函数(R1,R2,…,Rn)=Rc选取A中的元素作为最终的群体决策．将本体合并视为社会选择中的问题,用一个有限集合N={1,2,…,N}来表示Agent集合,集合A表示候选者Alternative集合,任意Agenti∈N都可以提供一个本体Oi⊆A,那么O={O1,O2,…,On}⊆ON构成了一个完整的本体组合．

定义1本体聚集:收集所有的本体并通过本体聚集函数F：ON→2A从本体集合中选出唯一的本体作为最终决策．

基于社会选择的本体聚集模型如图1，本体聚集器读取分布式本体的概念及关系要素,通过聚集规则给出本体要素之间的对应关系,最终形成新的顶层本体,作为更高层次的语义共享空间．

图1 基于社会选择的本体聚集模型Fig.1 Model of ontology aggregation basedon social choice

1.2 本体聚集函数

社会选择理论中常见的投票聚集规则及其性质包括一致性、独立性等，是在设计聚集函数时需要考虑的因素．通过证明,存在一种聚集函数同时满足万有域、匿名性、独立性和单调性的性质．

定义4联盟聚合规则:基于联盟的聚合函数F(O)=O1∪O2∪…∪On是一种简单的聚合方式,任意一个ontology都可能会成为群体决策，只要其中一个Agent接受它即可．

定义5基于距离规则:用d(O,Oi)表示两个本体O和Oi之间的距离,一般采用海明距离将一个本体变换成本体所需要替换的元素个数进行计算．基于距离的聚集算法，定义本体聚集函数为F(O)=argminO∈ON∑i∈Nd(O,Oi)．

性质4匿名性：也称平等原则F(O1,…,On)=F(On(1)，…,On(n))，匿名性是指聚集函数对agent都是同等对待的，π:N→N表示任意置换．

2 基于相似度的本体聚集算法

2.1 基于树状图的本体相似度计算

用算法1计算两个本体之间的相似度：① 本体规范化,将本体用同一种语言描述,若本体的表达形式不一致,则不利于相似度计算;② 相似度计算,从本体中分析出概念、结构(关系)等特征,并计算相似度;③ 本体相似度修正,得出多个相似度值之后,根据这些相似度的重要程度进行加权计算,得到最终的本体相似度．

算法1:本体相似度算法输入:O1,O2输出:sim(O1,O2)步骤:(1) for i:1→n ∥本体树状图有n层(2) if (Oi1∩Oi2=∅)(3) end(4) else(5) for j:1→|Oi1∩Oi2|(6) simij(O1,O2);∥分别计算第i层中j个结点的相似度(7) end for(8) simi(O1,O2)=∑simij(O1,O2)|Oi1,Oi2|;∥计算第i层中本体结点相似度(9) end if(10) end for(11) sim(O1,O2)=∑i=ni=1n-kn simi(O1,O2);∥最终的本体相似度

2.2 基于相似度的本体聚集算法

算法2: 基于相似度的本体聚集算法输入:Ontology1,Ontology2,…Ontologyn输出:Ontology*步骤:(1) for i: 1→n(2) sim(O,Oi)=1n·∑O'∈Osim(O',Oi)(3) end for(4) if sim(O,Oi)

3 实验结果分析

3.1 实验环境及数据

实验的开发环境:① 开发语言Java;② 本体构建工具Protégé，用于对本体进行语言、语法的统一描述;③ 集成开发环境Eclipse;④ 语义web应用API Jena，用于对本体进行解析和识别．实验运行在处理器为2.9 GHz Intel Core i5，内存为8 GB的PC机上.实验数据来源于OAEI2008[14]提供的Conference本体,本实验采用其中的4个本体,具体数据信息如表1．

表1 实验数据信息

本实验中用到的本体简记为O={O1,O2,O3,O4},这些实验数据信息主要来源于3类资源,分别是真实的会议以及它的网页信息、与会者的经验和用于会议组织的软件工具．

3.2 实验结果分析

首先根据算法1,计算本体之间的相似度,计算结果见表2．实验中,令t为所有本体与本体组合相似度的平均值，用于进行模拟实验．令q为1,再根据算法2求出最终合并后的本体,合并结果如图2,合并后的决策本体的概念和属性体系更简洁．

表2 本体之间的相似度

因为sim(O,O3)，sim(O,O4)

图2 本体聚集生成的顶层本体Fig.2 Upper ontology generated by ontology aggregation

4 结论

(1) 在同一领域本体的基础上,本体合并通过一系列规则合并，生成一个全新的本体,形成更高层次的共享语义空间．而社会选择理论研究将个人偏好聚集为群体偏好,其中提供了大量的社会选择函数．因此,可以将本体合并视为社会选择中的本体聚集问题．

(2) 文中给出了基于社会选择的本体聚集框架,并形式化定义了一组常见的聚集函数,进而设计了基于相似度的本体聚集算法．通过证明,可得该算法满足万有域、匿名性、独立性和单调性．以OAEI2008提供的会议本体作为实验数据,文中通过实验证明了新算法的有效性．

(3) 文中提出的新算法在进行相似度计算时,执行速度会随着源本体数量的增加而降低,如何减少执行时间有待进一步研究;此外,由于本体概念中有很多复合词,但这些词无法从WordNet中找到,因此对本体间相似度计算造成的误差也需要进一步研究．