改进的基于本体的语义相似度计算

张沪寅，温春艳，刘道波，叶 刚

（武汉大学 计算机学院，湖北 武汉430072）

0 引 言

词语相似度计算在信息检索、数据挖掘、机器翻译、个性化推荐等领域有广泛的应用，因此提高相似度计算结果的准确性显得尤为重要。随着领域本体的不断普及，以及本体树对概念节点之间关系的准确描述，本体已经成为语义相似度研究的基础。当前基于本体的语义相似度的研究主要有：提高相似度计算结果准确性、解决本体树中节点的多继承问题、解决节点对之间的不对称性问题等。本文算法通过改进相似度计算模型，在提高相似度准确度的同时解决各类多继承问题。

1 研究现状

当前基于本体的相似度计算主要分为基于语义距离、基于信息内容、基于属性、混合式相似度计算［1］。基于语义距离的方法［2］是最早采用的本体相似度计算方法，Shortest Path法［3］是该类的典型算法，通过概念词在本体树中的路径长度来量化概念节点之间的语义距离。Weighted Links法［4］对Shortest Path法进行了改进，对概念节点的边进行了权值分配。基于语义距离的方法随着不断改进，已发展为基于本体结构的相似度算法［5］。基于信息内容的方法［1］是用概念共同父节点的信息量来衡量二者的相似度，节点的信息量用节点包含内容在本体中出现的频率p来衡量。Resnik［6］对基于信息量算法进行改进，采用最小p衡量节点信息量。用父节点包含的信息量来衡量两个节点的相似度，但并未考虑节点本身所包含的信息量。基于属性的相似度计算［7］是用两个节点的公共属性个数来衡量节点相似度。混合式相似度计算［8－10］是目前比较常用的相似度算法，综合考虑语义距离、信息量和概念属性计算相似度。

文献 ［11］同时考虑加权语义距离和概念的属性，文献 ［12］在文献 ［11］的基础上考虑了语义相关度，同时语义距离加入了反向因子。文献 ［13］提出了基于共享路径的方法，同时考虑了LCA 节点深度，一定程度上解决了多继承的问题，算法并未考虑节点本身的信息，使得计算结果的准确性有待提高。

2 改进的相似度计算

本文的PRSSC算法是在基于信息内容的相似度计算方法的基础上，综合考虑概念节点的密度、自身深度，LCA节点深度以及概念的属性。PRSSC 算法描述如下：①采用概念间共享路径重合度的方法计算相似度，并对其进行改进，在考虑节点多继承共同父节点的同时，引入共同子节点因素；②考虑概念节点的密度，用节点宽度与本体树的最大出度的比值计算相似度；③考虑概念节点本身在本体树中的深度，并对其进行改进，加入LCA 节点深度因素；④考虑概念属性的影响，用节点属性的相似度衡量节点间的相似度；⑤通过参考其它已有研究进行权值分配，综合加权上述4个因素的算法公式，得到本文的PRSSC算法。

2.1 基本定义

本体 （ontology）是由概念组成的高级描述，是表述特殊知识领域的形式化语言。一个本体由有限个数的概念以及概念之间的关系组成。本文中本体用有向无环图表示，记为G＝ （V，E），图中节点表示本体的概念，节点间的有向边表示概念间的关系。

词语之间的关系分为语义相关度和语义相似度。语义相似度是指两个词语之间在语义上的相似程度，如红酒和白酒。语义相关度是指词语之间的关联程度，如Microsoft和Internet。由于语义的相关度没有普遍性，我们通常研究概念的语义相似度。概念M1，M2的语义相似度定义为Sim（M1，M2），对Sim（M1，M2）的值做如下定义：

（1）是 ［0，1］之间的一个实数；

（2）当且仅当M1和M2为同一节点时，值为1；

（3）当M1和M2不在同一个本体树时，值为0。

如图1wordnet所示是本体的一个典型实例。图中节点间都只有一个LCA 节点，不存在多继承问题，如若在图1中添加虚线部分，则motor vehicle和wheeled vehicle有两个LCA 节点，从而二者相似度增大，产生多继承问题。

2.2 基于信息内容计算相似度

基于信息内容的计算相似度方法主要是通过衡量概念所包含的信息量来计算相似度。概念是对其祖先节点的继承，是祖先节点的又一次细化，所以可以通过祖先节点包含的信息量来衡量两个概念的共享信息［14］。当然，祖先节点包含的信息量仅仅只能表示概念包含的相同信息，概念间的不同信息要通过计算概念本身所包含的信息量来衡量。本文采用基于共享信息重合度来计算相似度。

图1 wordnet片段

2.2.1 共享路径重合度

甘明鑫等［13］提出了基于共享路径重合度的方法计算相似度。两个概念之间共享的信息越多，则二者之间的相似度越高。反之，则二者的相似的越低。这是共享信息内容的相似度计算方法的基本原理。概念的子图是指概念节点与其祖先节点构成的本体部分图。定义概念M1，M2之间的基于共享路径重合度的相似度计算公式为

式中：re——概念节点和有向边权重的比值，即相对权重。VM1∩M2——概念M1，M2的子图交集所包含节点个数加权，EM1∩M2——概念M1，M2的子图交集包含有向边个数的加权和，VM1∪M2——概念M1，M2的子图并集所包含节点个数加权，EM1∪M2——概念M1，M2的子图并集包含有向边个数的加权和。

基于共享路径重合度计算相似度能在有效地计算相似度的前提下，解决概念多继承的问题。当两个概念具有相同的子节点时，二者之间的相似度应该更大，上述算法不能很好地解决这一点，针对这一问题，本文对式 （1）进行改进，将共享子节点信息也加入到共享信息中

式中：｜Vcom｜——概念M1，M2共同直接子节点的个数。

2.2.2 概念节点的密度

概念节点的密度的定义请参见文献 ［4］。概念节点的密度越大，则其直接子节点的数目越大，节点细化的越具体，各直接子节点之间的相似性就越大，所以可以通过概念节点的LCA 节点的密度来衡量概念节点之间的相似度。基于概念节点密度的相似度计算算法［4］

式中：CountLca（M1，M2）——概念节点LCA 节点的直接子节点个数；Degree（Tree）——概念M1，M2的所在本体树中各节点出度的最大值。

2.2.3 概念节点的深度

概念节点的深度是指概念在所处的本体树中的层次深度［15］。在本体树中，每个概念节点 （除了根节点）都是对其上一层节点的一次细化。因此概念节点处于本体树的层次越深，则其表示的内容就越具体，概念间的相似度越大。反之概念间的相似度越小。此处定义根节点的深度为1，概念节点M 的深度为Dep（M），Dep（M）＝Dep（parent（M））＋1，其中parent（M）为节点M 的父节点。Dep（Tree）表示本体树的深度。胡哲等［12］的基于概念节点深度的相似度计算公式为

LCA 节点的深度越深，代表概念的分类越具体，则概念节点之间的相似度越大。反之，概念节点之间的相似度越小。对式 （4）进行改进，得到新的基于概念节点深度的相似度计算式 （5）

2.2.4 概念属性

2.3 PRSSC算法

本文在基于共享信息相似度计算算法的基础上进行改进，加入节点密度、深度、属性，由式 （2）、式 （3）、式（5）、式 （6），得到PRSSC算法公式

式中：α1＋β1 ＋χ1 ＋λ1＝1。

依据文献 ［1，12］中的权值分配情况，以及分析各影响因素对相似度的影响程度来分配权值，式 （7）中α1、β1、χ1 、λ1的取值分别为0.75、0.01、0.20、0.04。

3 实验与分析

选用图2所示的打印机本体实例［11］中的概念节点作为相似度计算实例。

由于数据属性相对复杂，为了本体图看起来简单直观，给出LaserJetPrinter、PresonalPrinter、HPPrinter的数据类型属性，如下表示：

根据图1和上述数据属性类型属性值，按照式 （7）计算概念间相似度，将计算结果与文献 ［13］、文献 ［11］和Resnik算法［6］的计算结果进行对比，见表1。

分析图2可得， （LaserJetPrinter，HPPrinter）相较于（PresonalPrinter，HPPrinter）有相同的子节点，且有更多相似的数据类型属性，所以二者的相似度要大于 （Presonal－Printer，HPPrinter）的相似度。PRSSC 算法得到的结果是0.4940＞0.4425，显然PRSSC 的结果更为准确。文献［13］算法和Resnik算法算得的二者的相似度相等，是由于二者均未考虑属性和共同子节点的问题。

（LaserJetPrinter，PresonalPrinter）与 （PresonalPrinter，HPPrinter）共享父节点路径相同，说明两对节点的共有信息量相同，而HPPrinter是多继承节点，且其HPProducts父节点到根节点这条路径不在 （PresonalPrinter，HPPrinter）的共享父节点路径中，因此 （LaserJetPrinter，HPPrinter）的共有信息量不变，但是私有信息量增加，显然 （Laser－JetPrinter，PresonalPrinter）的相似度应该大于 （Presonal－Printer，HPPrinter）的相似度。文献 ［13］算法和Resnik算法计算结果显然不太准确。

给图1添加LaserJetPrinter到HPProducts的虚线，使（LaserJetPrinter，HPPrinter）有两个LCA 节点：Printer和HPProducts。PRSSC算法计算 （LaserJetPrinter，HPPrinter）的相似度结果为0.5764＞0.4940。这是由于LaserJetPrinter和HPPrinter节点多继承，二者有两个LCA 节点，从而导致二者共享路径重合度增大，二者相似度增大。

根据上述三组数据对比，可以看出PRSSC 算法相较于其它几种算法，考虑更加全面，在解决各类的多继承问题的同时，计算结果更为准确。

图2 打印机本体片段

表1 打印机本体实验结果

4 结束语

本文在基于共享信息的基础上进行改进，提出了一种新的算法模型——PRSSC算法。算法对基于共享路径重合度进行了改进，加入了共同子节点因素影响，并引入概念节点的密度、深度和概念属性作综合加权计算。其中概念节点的深度不仅考虑节点自身的深度，还考虑了概念的LCA 节点的深度。实验结果表明，PRSSC 算法计算结果相较于其它算法更加准确，而且能够解决各类多继承问题。本文的算法未解决概念对相似度的不对称性，这一问题还需进一步研究。

［1］SUN Haixia，QIAN Qing，CHENG Ying.Review of ontolo－gy－based semantic similarity measuring ［J］.New Technology of Library and Information Service，2010，26 （1）：51－56 （in Chinese）.［孙海霞，钱庆，成颖.基于本体的语义相似度计算方法研究综述 ［J］.现代图书情报技术，2010，26 （1）：51－56.］

［2］YANG Fangying，JIANG Zhengxiang，ZHANG Shanshan.Semantic similarity measurement based on ontology ［J］.Computer Technology and Development，2013，23 （7）：52－56 （in Chinese）.［杨方颖，蒋正翔，张姗姗.基于本体结构的语义相似度计算［J］.计算机技术与发展，2013，23 （7）：52－56.］

［3］ZHAO Yongjin，ZHENG Hongyuan，DING Qiulin.Study on semantic similarity algorithm based on ontology ［J］.Journal of Computer Applications，2009，29 （11）：3074－3076 （in Chinese）.［赵永金，郑洪源，丁秋林.一种基于本体的语义相似度算法研究 ［J］.计算机应用，2009，29 （11）：3074－3076.］

［4］LI Wenjie，ZHAO Yan.Semantic similarity between concepts algorithm based on ontology structure ［J］.Computer Engineering，2010，36 （23）：4－6 （in Chinese）.［李文杰，赵岩.基于本体结构的概念间语义相似度算法 ［J］.计算机工程，2010，36 （23）：4－6.］

［5］HE Yuanxiang，SHI Baoming，ZHANG Yong.Research on ontology－based semantic similarity algorithm ［J］.Computer Applications and Software，2013，30 （11）：312－315 （in Chinese）.［贺元香，史宝明，张永.基于本体的语义相似度算法研究 ［J］计算机应用与软件，2013，30 （11）：312－315.］

［6］Resnik P.Using information content to evaluate semantic similarity in a taxonomy ［C］／／Proceedings of the 14th International Joint Conference on Artificial Intelligence，1995.

［7］LIU Hongzhe，XU De.Ontology based semilarity and relatedness measures review ［J］.Computer Science，2012，39 （2）：8－13（in Chinese）.［刘宏哲，须德.基于本体的语义相似度和相关度计算研究综述［J］.计算机科学，2012，39 （2）：8－13.］

［8］CUI Qiwen，XIE Fu.An improved computational method for conceptual semantic similarity in domain ontology ［J］.Computer Applications and Software，2012，29 （2）：173－174 （in Chinese）.［崔其文，解福.改进的领域本体概念语义相似度计算方法［J］. 计算机应用与软件，2012，29 （2）：173－174.］

［9］LI Wenqing，SUN Xin，ZHANG Changyou，et al.A semantic similarity measure between ontological concepts［J］.ACTA Automatica Sinica，2012，38 （2）：229－235 （in Chinese）.［李文清，孙新，张常有，等.一种本体概念的语义相似度计算方法 ［J］.自动化学报，2012，38 （2）：229－235.］

［10］DING Zhengjian，ZHANG Lu.Improved approach for ontology similarity computation ［J］.Computer Engineering，2010，36 （24）：39－41 （in Chinese）.［丁政建，张路.一种改进的本体相似度计算方法 ［J］.计算机工程，2010，36（24）：39－41.］

［11］XU Guichen，YE Feng.An improved algorithm for semantic similarity based on weighted semantic distance［J］.Journal of Intelligence，2012，31 （2）：119－123 （in Chinese）. ［徐桂臣，叶枫.基于语义加权距离的语义相似度改进算法 ［J］.情报杂志，2012，31 （2）：119－123.］

［12］HU Zhe，ZHENG Cheng.Improved concept similarity computation ［J］.Computer Engineering and Design，2010，31（5）：1121－1124 （in Chinese）.［胡哲，郑诚.改进的概念语义相似度计算 ［J］.计算机工程与设计，2010，31 （5）：1121－1124.］

［13］GAN Mingxin，DOU Xue，WANG Daoping，et al.Comprehensive weighting method for calculation of ontologybased semantic similarity ［J］.Computer Engineering and Applications，2012，48 （17）：148－153 （in Chinese）.［甘明鑫，窦雪，王道平，等.一种综合加权的本体概念语义相似度计算方法 ［J］.Computer Engineering and Applications，2012，48（17）：148－153.］

［14］JIANG Hua.Research on concept semantic sim ilarity computation based on ontology ［J］.Computer Applications and Software，2009，26 （7）：143－145 （in Chinese）.［姜华.一种基于本体的概念语义相似度计算研究 ［J］.计算机应用与软件，2009，26 （7）：143－145.］

［15］ZHANG Zhongping，ZHAO Hailiang，ZHANG Zhihui.Concept similarity computation based on ontology ［J］.Computer Engineering，2009，35 （7）：17－19 （in Chinese）. ［张忠平，赵海亮，张志惠.基于本体的概念相似度计算 ［J］.计算机工程，2009，35 （7）：17－19.］