一种基于网络分析的语义冗余发现方法

王国栋，高 超，原 野，张自力

(西南大学 a.计算机与信息科学学院；b.智能软件与软件工程重点实验室，重庆 400715)

一种基于网络分析的语义冗余发现方法

王国栋，高 超，原 野，张自力

(西南大学 a.计算机与信息科学学院；b.智能软件与软件工程重点实验室，重庆 400715)

以农业AGROVOC本体为例，结合语义万维网推理机制定性分析冗余信息产生原因，利用复杂网络分析方法量化推理过程中产生的冗余，进而确定本体中的核心概念，解决推理冗余问题。实验表明，复杂网络分析方法可从定量角度找出核心节点及导致推理产生冗余的边，并揭示了语义冗余引起的推理效率降低问题。为优化本体设计、提高推理效率提供了一种新的可行方法。

复杂网络；推理；冗余；AGROVOC

0 引言

随着Tim Berners-Lee在1998年提出语义万维网(The Semantic Web)概念和体系结构，人们对下一代Web——语义万维网的发展和研究产生了浓厚兴趣[1]。本体是一种用来描述概念以及概念之间关系的知识表示[2]，其为Web上的信息赋予一种语义含义[3]，在语义万维网中起着核心作用，是实现基于语义的互操作的关键因素，因此本体的构建也就成为语义万维网实现的重要步骤。

在构建基于物联网的柑橘种植知识本体过程中[4]，通过对联合国粮食组织(FAO)农业AGROVOC本体[5]的研究发现，本体的结构将在推理过程中发生变化，在只有部分本体参与推理时，产生了新的连接，而当全部本体都参与推理时，却没有产生新的连接，这表明推理产生了冗余。为什么会出现这种情况？产生新的连接是什么？这些新的连接在其中起了什么作用？为回答这些问题，本文首先从定性角度分析推理前后农业AGROVOC本体结构变化及冗余产生原因，再从定量角度进行实验验证。

1 相关概念和工作

1.1 语义万维网的推理机制

传统Web资源中的语义信息和领域知识是建立在机器难以处理的自由文本方式之上，它们以一种隐含的语义关系形式存在。而语义万维网中语义推理的一个基本作用就是解读这些隐性知识，把隐含在显示定义和声明中的知识通过推理机制提取出来。以图1中肯尼迪家族本体为例，图1a表示已有的属性hasParent定义为父母与儿女之间的关系，而hasAncestor则没有事先定义，hasParent只是它的子属性(subProperty)，而在图1b中，所有人之间只有hasParent一种关系，那么在肯尼迪家族中谁是Maria Shriver的长辈？在没有推理存在的情况下，得不到任何结果，因为图1b所示的本体中没有任何一个人(图1b中的实例节点)同hasAncestor有直接关联，但是当打开推理引擎时，却出现了4个结果，分别是Jossph Kennedy、Robert Shriver、Rose Fitzgerald和Eunice Kennedy。

图1 属性关系结构图和肯尼迪家族关系结构图Fig.1 The structure of attribute relationship and relationship diagram of Kennedy's family

此外，我们根据柑橘种植专家提供的柑橘病症方面的专家知识，构建了柑橘病症本体[4]，并构建了病症查询系统，该系统已成功应用于柑橘实际生产当中，指导重庆忠县新立镇现代化生态柑橘园的农户[6]。用户只需在系统界面输入观察到的柑橘表象症状，本体会在后台进行自动推理，最终反馈给用户最为可能的柑橘致病原因。由此可见，语义推理在发现隐藏于数据间的知识有着非常好的应用效果。

1.2 本体结构分析

已有的本体结构研究主要从本体的语义角度分析。Burton-Jones等[7]研究了一套从句法、语义、实效性等角度对DAML(DARPA Agent Markup Language)本体进行评估，最后通过函数计算得出本体的评价指标。Yao等[8]利用本体凝聚力来衡量OWL本体的模块化关联，根据树状的OWL本体的语义层次结构计算这些指标，它们分别是根类(NOR)，叶类(NOL)和平均深度继承树的所有叶节点(ADIT-LN)的数目。Kang等[9]采用加权类关系图表示一个给定的类图，提出一种基于熵距离的方法评估UML类图的复杂性结构，并提出将这种复杂度转化成加权类关系图的规则。His等[10]用图论的方法研究了本体概念间的相关性，提出了概念一致性和概念复杂性两个指标衡量概念的平均关系数和概念间的平均距离。

1.3 农业AGROVOC本体

农业AGROVOC本体[11]是由联合国粮农组织和欧洲共同体委员会创建的一个多语言结构化词库，涉及领域包括食品、农业、林业、渔业和其他相关领域，它由近40 000个概念20多种语言组成的，具备各类词间关系(如：广义(broader)关系、狭义(narrower)关系和相关(related)关系等)，旨在全球范围内将信息索引标准化，提高搜索信息来源的准确性[12]。

1.3.1 AGROVOC本体描述

本体可以看作是概念和关系的集合，以农业AGROVOC本体库为例，本体可表示为一个二元组O=(C,R)，C=(c1,c2,c3,…,cn)，其中ci=(i∈[1,n])代表农业相关领域的概念事实，R=(r1,r2,r3,…,rn)，其中ri=(i∈[1,n])代表概念事实间不同关系。在农业领域，概念事实之间的关系包含不同的类别，比如传统词库关系、概念到概念的关系、术语到术语的关系、概念到术语的关系等，但是最重要的是传统关系，即R=(broader,narrower,related)。

传统关系中广义(broader)关系是将一个通用的术语同更具体的术语联系起来，在图2a中，“土壤”这个概念通过broader同“土地覆盖”这个概念相联系。而狭义(narrower)关系则表示相反的broader。“土壤”通过narrower同“顶部土壤”、“根际土壤”和“底土”3个更具体的概念连接。相关术语(related)关系连接任何两个非等级关系的概念，在图2b中，“鱼”这一概念可以通过related和“食品”、“易腐产品”、“海鲜”或者“新鲜产品”等概念连接起来。

1.3.2 AGROVOC本体推理逻辑分析

图2 农业AGROVOC中的广义关系概念图和相关术语关系概念图Fig.2 The concept map of broader relationship and the concept map of related relationship in AGROVOC

图3 语义的从属关系Fig.3 Semantic dependency relationship

图4 传导推理规则Fig.4 Rules of conduction inference

本文用SKOS(Simple Knowledge Organization System)来表示知识组织系统的一个模型，充当知识组织系统设计和应用之间的桥梁[13]。SKOS区分两种语义关系：层次关系和关联关系。层次关系链接两个概念指的是其中一个概念比另一个更通用(或更具体)，而关联关系指的是两个概念是“相关”的，其中任何一个不比另一个通用或具体。在农业AGROVOC本体中，W3C标准在SKOS框架下提出了R=(narrower,broader,narrower Transitive,related,broader Transitive)5种关系[14]，其中narrower、broader和related出现在本体推理前，narrowerTransitive和broaderTransitive出现在本体推理后[15]。related属于关联关系，不具有传递特性[16]。其他4种是层次关系，如图3所示。其中narrower，broader只用于直接的层次关系。narrowerTransitive和broaderTransitive用来推理层级关系的传递性，具体规则如图4所示。

根据以上分析，本体中的概念及其关系构成了一个动态网络，推理前后，网络的结构发生了变化。如何定量衡量语义万维网推理结构变化，发现核心概念对本体构造人员来说是一种挑战。由于任何一种现实网络都兼有确定性和随机性，而确定性的法则或特征通常都隐藏在统计涨落之中[7]，因此，利用复杂网络分析方法研究语义万维网推理前后的网络统计特征为本体构造人员提供一种分析推理中的确定性法则和特征的新手段。

1.3.3 AGROVOC本体推理冗余定性分析

本文通过观察推理前后农业AGROVOC本体关系，验证了related关系只参与了部分本体的推理，而没有参与整个本体的推理。从定性角度来看，由于related与剩余本体的关联被割断，成为一种单连通状态，它们只与部分本体中的事实相连。但在推理过程中，推理机却默认单连通状态全部参与推理，导致了related关系参与了没有必要的推理过程，由此推断related关系是导致推理冗余产生的根源。举例来讲，Mutton(羊肉)与Sheep(羊)相关(羊肉出在羊身上)，Sheep(羊)与Clothes(衣服)相关(羊毛衣服的材料来自于羊身上的毛)，用语义关系结构表达如下：

:Mutton skos:related:Sheep.

(1)

:sheep skos:related:Clothes.

(2)

根据related边的定义，无法得出

:Mutton skos:related Clothes.

(3)

但若related边参与了推理，则(3)成立。因此，本体推理冗余可表达为

图5 本体与复杂网络的对应关系Fig.5 The corresponding relationship between ontology network and complex network

其中，R表示推理产生的冗余，Y表示本体推理中产生了冗余，N表示本体推理中未产生冗余。

本文将进一步从定量的角度分析推理产生的冗余，为优化本体设计、提高推理效率提供一种新的可行方法。

2 研究方法

如图5所示，若将本体中的概念建模成复杂网络中的节点，将本体中的关系建模成复杂网络中的边，则本体可以建模成一个复杂网络。本文采用复杂网络分析方法对农业AGROVOC本体推理前后的结构进行分析，从定量角度衡量农业AGROVOC本体推理前后是否产生冗余。复杂网络分析方法是一种研究各类网络共性的通用方法，提供了一系列指标对节点和网络特性进行定量评估。例如，可通过节点度数和网络度分布特性来判断某个节点是否为核心节点；利用网络平均最短路径判断网络在演化时是否产生新的边。因此，本节将利用复杂网络分析方法所提供的度分布、簇系数和平均最短路径等指标对本体结构进行定量衡量，找出推理产生冗余的原因，为解决推理冗余问题提供一种可行方案[17]。

2.1 度与无尺度分布

网络中节点的度是其互相连接统计特性的直接描述，也反映重要的网络演化特征[18]，大部分节点只与少数重要节点连接，这些重要节点为集散节点。在语义网络中，本体也存在一些核心概念，其它的概念或多或少都会与其有联系。而一个本体与其他本体联系的强度可以用复杂网络中度的大小来表示，本体中某个节点的度数可判断该节点是否为核心概念，一个本体中的节点度数较大，说明该节点是该本体中的集散节点，从而可确定该节点为本体中较为核心的概念。本文将采用度分布和累积度分布来观察本体网络的分布特征，验证其是否具有无标度网络的特性[18]。

2.2 聚类特性

簇系数用来衡量网络节点聚集情况[19]。网络中某个节点的簇系数定义为所有相邻节点之间连接的数目占最大连接数目的比例，而网络的簇系数是所有节点的簇系数的平均值。网络的簇系数越大，类聚特性越高，网络越紧密。根据簇系数计算公式，网络中一个节点i的相邻节点之间的边数li是影响网络簇系数大小的根本原因，网络簇系数会随着li的增大而增大。在本体推理过程中，li增大意味着推理产生新的连接(即冗余)。因此，根据本体簇系数在推理前后的变化即可判断推理是否产生了冗余。

2.3 平均最短路径与小世界性质

本文将采用介数中心性方法[20]计算语义网中本体间推理路径的变化。在本体推理过程中，若推理产生了新连接，大部分概念可用3～4条短路径连接起来，则本体的最短路径减小，使其具有小世界网络的特征[21]；若推理未产生新连接，则本体的最短路径没有变化。因此本体的最短路径的变化亦可说明推理是否产生了冗余。

2.4 重要度评价矩阵与网络贡献度

重要度评价矩阵方法是综合考虑节点自身在网络信息流通中所起作用和相邻节点对其重要贡献度而产生的一种评价方法[22-23]。在构建本体时，关键节点的设计是重中之重。这不仅体现在推理前的分析中，在推理后，一些之前不重要的节点有可能变得很重要，成为关键节点。因此，本体构建中采用节点重要度评价方法可很容易地鉴别关键本体。相对于节点重要性，网络中不同性质的边也是网络的重要组成。因此，本文用网络贡献度表示不同的边在网络中的占比，发现构建本体时的关键边，这也对构建本体有很大帮助。

小图为概率分布图，大图为累积度分布图。图6 农业AGROVOC本体出入度分布双对数坐标图Fig.6 The cumulative degree distribution of AGROVOC ontology network

3 实验结果分析

3.1 度与集散节点

通过对比发现推理前后网络平均度由4.12增加到23.71，这表明农业AGROVOC本体推理后的新关系narrowerTransitive和broaderTransitive具有传导性，它们使得概念间有了更多联系，推理产生了冗余。

表1 网络簇系数对比表Tab.1 The comparision of network cluseter coefficient

图6a、6b展现了农业AGROVOC本体推理前的幂律分布特性，这说明该本体具有无标度分布特性，只有极少数集散节点与网络中多数节点相连。这些集散节点代表本体中某一农业领域的核心概念或者这一领域概念的总称，如灌溉方法下面包含渠灌、哇灌、滴灌等。根据此特点，在搜索农业AGROVOC本体的时候，为了提高效率，通常可以优先匹配比较核心的概念，确定搜索方向，再进行更细致的搜索。图6c、6d展现了推理后农业AGROVOC本体度分布也满足幂律分布，且推理后的幂指数α=0.9小于推理前的幂指数α=1.9，这说明推理后网络比推理前更紧密、本体之间的关系更复杂，推理产生了冗余。

3.2 簇系数和类聚特性

表1对比了推理前农业AGROVOC本体和一些已知的具有高聚类特性的网络的簇系数，农业AGROVOC本体的簇系数远小于因特网和食物链的簇系数，由此可见推理前农业AGROVOC本体不具备高聚类特性。

图7分析了推理前后节点度和簇系数的关系。图7a显示大部分节点的度数偏小，集中在4到100中间，随着度数的增加，簇系数从1逐渐减小到0.001，说明在AGROVOC本体中，各个词汇与核心词汇联系不紧密，整个结构接近树状图。图7b显示推理后农业AGROVOC本体的簇系数增加到0.948 3，远大于因特网和食物链的簇系数，推理后网络具有高类聚特性，因此推理产生了冗余，概念间联系更紧密，网络也状图接近于完全图。可见，narrowerTransitive和broaderTransitive两个关系的传导性可使得聚集度低的网络变得更紧密。

3.3 平均最短路径和介数中心性

图8展示了在农业AGROVOC本体中，推理前两概念间最短路径长度的最大值为14，有87%的路径值不大于16，有98.7%的路径不大于20，整个网络的平均最短路径为12.6，说明农业AGROVOC本体不具有小世界网络特征。

图7 推理前后节点的度与簇系数双对数图Fig.7 The relationship between the degree and cluster coefficient of a node in the logarithmic coordinates

图8 路径长度分布图Fig.8 The distribution of path length

图9 推理前后最短路径比较Fig.9 Comparsion of the shortest path before and after reasoning

图9对比了推理前后最短路径的变化，结果表明推理前后平均最短路径差距明显，说明经过推理后网络中节点之间有了更多的联系，可连通节点间的路径一般都很短，本体符合了小世界网络类似的特征，这说明农业AGROVOC本体在推理过程中产生了冗余。

3.4 推理冗余的定量分析

在农业AGROVOC本体中，SKOS中的5种关系只有narrower、broader和related出现在推理前[14]。而灌溉本体是农业AGROVOC本体的一部分，它由23个节点和36条边组成，包括7条related边、14条narrower边和15条broader边，其结构如图10所示。因此，选取灌溉本体作为样本进行定量分析能够全面分析哪一类型的边才是导致推理产生冗余的根本原因。通过计算发现，灌溉本体推理后的平均最短路径为2.009。

图10 灌溉本体结构图Fig.10 The network structure of irrigation ontology network

表2 不同推理关系的比较Tab.2 The comparison of different reasoning relations

为分析related、narrowerTransitive和broaderTransitive边在推理前后的作用，分别去除3组边后构成3个新网络。表2对比了最短路径变化情况以及它们对最终网络的贡献度。结果表明related边对网络的贡献度最低，分别是其他边的一半或更少。由此可以证明related边就是冗余边，同时通过对运行时间的对比也可知related边对推理没有产生影响反而影响了效率，去边前推理时间为349ms，去边后则提升到287ms。实验结果证明，去除冗余边可以明显提高推理的效率。

在语义网中，一个概念的“邻居”越多，越能体现这个概念的重要性[24]。鉴于概念本体在语义网中是以单属性形式存在(即概念的推理属性，是由每个概念与其它概念构成的推理边组成)，因此本文将本体中的概念建模成复杂网络中的节点，将关系建模成边，目的是利用复杂网络中基于拓扑属性的节点重要度排名方法分析本体中概念的重要性。节点n2代表灌溉本体中的灌溉方法(Irrigation methods)，是灌溉本体中最重要的概念，所以在推理前后其重要度排名都是第一；节点n20代表方法(Methods)，是比灌溉方法更为通用的概念(但在灌溉本体中不一定重要)，而它从推理前的第13名攀升到推理后的第2名，成了灌溉本体中的关键节点，所以在本体构建时要特殊关注诸如n20这样的节点，以降低因推理产生冗余对节点重要度产生的影响。

表3 节点重要度排名Tab.3 The ranking result of node importance

4 结论

语义推理的一个基本作用就是把隐含的知识通过处理机制提取出来。在实际应用中，推理会产生无意义的信息，即推理冗余，它不仅影响了准确性，也影响速度和效率。在构建本体时及早地去除这些导致冗余的推理关系是解决这一问题的关键。本文以农业AGROVOC本体为例，从定性的角度解释了推理冗余的产生原因，并利用复杂网络分析方法提供的衡量指标(如度分布、簇系数、最短路径等)从定量的角度鉴别本体中的核心概念，以便在推理中优先匹配核心概念，提高推理效率。同时，通过划分区域的方式发现推理冗余问题，为减少推理冗余、提高推理效率提供一种新手段。

本文对推理冗余的研究是语义推理领域的一次拓展，为语义研究人员在本体优化、提高推理效率方面提供衡量标准，同时也为语义技术的发展提供更多的参考和使用价值。

[1]Meenachi N,Sai Baba M.Web ontology language editors for semantic web:a survey [J].International Journal of Computer Applications,2012,53(12):12-16.

[2]Antoniou G,Van Harmelen F.A semantic web primer[M].Cambridge,Massachusetts,United States:MIT Press,2004:9-12.

[3]Berners-Lee T,Hendler J,Lassila O.The semantic web[J].Scientific American,2001,284(5):28-37.

[4]Yuan Y,Zeng W,Zhang Z L.A semantic technology supported precision agriculture system:a case study for citrus fertilizing[C]// 6th International Conference on Knowledge Science,Engineering and Management.Dalian,China:Springer Berlin Heidelberg,2013:104-111.

[5]The AGROVOC team.AGROVOC [OL].(2015-03-01) [2015-06-01].http://aims.fao.org/zh-hans/agrovoc.

[6]王艺,王英,原野,等.基于语义本体的柑橘肥水管理决策支持系统[J].农业工程学报,2014,30(9):93-101.Wang Yi,Wang Ying,Yuan Ye,et al.A decision support system for fertilization and irrigation management of citrus based on semantic ontology[J].Transactions of the Chinese Society of Agricultural Engineering,2014,30(9):93-101.

[7]Xu Y,Zou S,Gu A,et al.Research on the complex network of the UNSPSC ontology[J].Physics Procedia,2012,24:1863-1867.

[9] Zhang H,Li Y F,Tan H B K.Measuring design complexity of semantic web ontologies[J].Journal of Systems and Software,2010,83(5):803-814.

[10] Hsi I.Analyzing the conceptual coherence of computing applications through ontological excavation[D].Atlanta:Georgia Institute of Technology,2004.

[11] Caracciolo C,Stellato A,Morshed A,et al.The agrovoc linked dataset[J].Semantic Web,2013,4(3):341-348.

[12] Rajbhandari S,Keizer J.The AGROVOC concept scheme-a walkthrough[J].Journal of Integrative Agriculture,2012,11(5):694-699.

[13] Manaf N A A,Bechhofer S,Stevens R.The current state of SKOS vocabularies on the web[C]// 9th Extended Semantic Web Conference.Greece:Springer Berlin Heidelberg,2012:270-284.

[14] Myers T,Atkinson I.Eco-informatics modelling via semantic inference[J].Information Systems,2013,38(1):16-32.

[15] 唐晋韬,王挺,王戟.利用复杂网络分析方法研究基因本体隐藏结构信息[J].东南大学学报:英文版,2010,1:31-35.Tang JinTao,Wang Ting,Wang Ji.Discovering hidden information of gene ontology based on complex networks analysis[J].Journal of Southeast University,2010,26(1):31-35.

[16] 张自力，李莉.语义万维网——工程实践指南 [M].第2版.北京：高等教育出版社，2015:184-185.

[17] 张大陆,王志晓,刘雯,等.基于复杂网络的本体结构分析[J].同济大学学报:自然科学版,2009,2:258-261.Zhang Da,Wang Zhixiao,Liu Wen,et al.Complex network-based ontology structure analysis[J].Journal of Tongji University (Natural Science),2009,2:258-261.

[18] Costa L F,Oliveira Jr O N,Travieso G,et al.Analyzing and modeling real-world phenomena with complex networks:a survey of applications[J].Advances in Physics,2011,60(3):329-412.

[19] Maoz Z.Preferential attachment,homophily,and the structure of international networks,1816-2003[J].Conflict Management and Peace Science,2012,29(3):341-369.

[20] Zhou L,Lu F,Zhang H.Evaluating road selectivity of urban-trip based on dynamic betweenness centrality[C]// The 20th International Conference on Geoinformatics (GEOINFORMATICS).Hong Kong:IEEE,2012:1-5.

[21] Gulati R,Sytch M,Tatarynowicz A.The rise and fall of small worlds:Exploring the dynamics of social structure[J].Organization Science,2012,23(2):449-471.

[22] 周漩,张凤鸣,李克武,等.利用重要度评价矩阵确定复杂网络关键节点[J].物理学报,2012,61(5):050201.Zhou Xuan,Zhang Fengming,Li Kewu,et al.Use importance evaluation matrix to determine the complex network nodes [J].Journal of Physics,2012,61(5):050201.

[23] 任晓龙,吕琳媛.网络重要节点排序方法综述[J].科学通报,2014,13:1175-1197.Ren Xiaolong,Lv Linyuan.Review of ranking nodes in complex networks[J].Chinese Science Bulletin,2014,13:1175-1197.

[24] Zhang X,Cheng G,Ge W Y,et al.Summarizing vocabularies in the global semantic web[J].Journal of Computer Science and Technology,2009,24(1):165-174.

(责任编辑 耿金花)

Network-Based Analysis for Discovering Semantic Redundancy

WANG Guodong,GAO Chao,YUAN Ye,ZHANG Zili

(a.School of Computer and Information Science; b.Key Laboratory of Intelligent Software and Software Engineering,Southwest University,Chongqing 400715,China)

The efficiency of semantic reasoning can be improved through constructing the semantic ontology reasonably and reducing the redundant information in the process of reasoning.It is a feasible method to reveal the reason of the redundant information in the process of reasoning through analyzing the dynamic changes of an ontology structure and the important role of nodes in an ontology.Taking AGROVOC ontology network as an example,this paper provides qualitative analyses based on the reasoning mechanism of semantic web for understanding the redundant information.Meanwhile,some quantitative measurements from the perspective of complex network are provided in order to identify the core concepts in a semantic web,and further to solve the problem of redundant information.Experimental results show that the reasoning of semantic web and the rationality of ontology construction can be quantitatively analyzed from the perspective of complex network,which provides a new measurement to optimize the design of ontology and improve the efficiency of reasoning in the semantic web.

complex networks； reasoning； redundancy； AGROVOC

1672-3813(2017)01-0058-08；

10.13306/j.1672-3813.2017.01.009

2015-06-04；

2015-12-07

国家高技术研究发展计划项目(2013AA013801)；国家自然科学基金(61402379,61403315)；重庆市研究生科研创新项目(CYS14063)

王国栋(1990-)，男，山东鱼台人，硕士研究生，主要研究方向为语义万维网。

TP392

A