基于有向邊和屬性的相似度模型設計

崔 巖，張淑麗

（西北工業大學明德學院計算機信息技術系，西安710124）

基于有向邊和屬性的相似度模型設計

崔 巖，張淑麗

（西北工業大學明德學院計算機信息技術系，西安710124）

通過分析單一條件下相似度算法的計算原理及設計思想，以有向圖的形式描述概念，分析和推導了有向邊、語義重合度及屬性相似度的計算模型，給出了一個含有語義及屬性權值的概念相似度計算模型。最后通過對比傳統模型的性能測試，驗證了新模型對相似度計算的精度。

概念相似度；有向邊；屬性權值；本體

1 設計背景

概念相似度的研究，是在以本體為設計核心的檢索系統中研究的重點問題。它不僅對于語義提取中詞頻分析及閾值的設定有一定的參考意義，從應用角度分析，它也直接影響查詢效率的高低與查找代價的大小。因此對于概念相似度的研究十分重要。

通過不同角度對概念之間相似度特點的分析和描述［1］，可以總結出某一個方面對概念相似度描述的計算模型。不同角度的側重各有差異，都有明顯的優勢和缺陷，基于這些不同描述角度給出的計算模型，找出一個或者幾個最適合或最接近現實情況的模型，作為相似度計算的主要依據。

1.1 單一條件下的計算模型

（1）基于內容的語義相似度計算模型

如果兩個概念共享的信息越多，則它們之間語義相似度也就越大。基于這樣的原理，在概念網絡層次中，每個概念結點都可以看做是對其父結點的細化，它們繼承了父結點的信息。那么兩個概念的語義相似度就可以用它們最近共同的祖先結點的信息內容來衡量。

這樣可以得到概念層次網絡中任意兩個概念之間的語義相似度。給定兩個概念c1和c2，其計算模型為公式（1）所示：

其中Anc（c1，c2）表示概念結點c1和c2在網絡中的最近共同祖先結點；IC（c）表示概念c所擁有的信息量。

（2）基于屬性的語義相似度計算模型

一般情況下，兩個客觀事物如果有多個屬性相同，則說明它們是相似的事物，概念，也具有類似的性質。基于屬性的語義相似度計算模型就是根據這個原理來進行相似度計算的。

由Tversky提出的一種語義相似度計算方法就是基于屬性的。如公式（2）所示。

其中：（c1∩c2）表示兩個概念相同的屬性集；c1-c2表示c1相對于c2所獨有的屬性集；c2-c1表示c2相對于c1所獨有的屬性集。

（3）基于距離的語義相似度計算模型

通過文獻［1］指出，語義相似度的計算是以概念層次結構為基礎的，計算概念間與它們的最近公共父節點的距離來計算它們的語義距離，進而計算出概念間的相似度。

在只存在上下位關系的概念層次機構中，任意的兩個概念間，連通它們的最短路徑就是通過它們的最近公共父節點或者是通過它們的最近公共子節點，因此可以計算它們通過最近公共父節點或子節點的路徑距離為：

其中：d（c，min f）＝｜s（min f）-s（c）｜。min f是c1和c2最近公共父節點或子節點。由此，就可以計算出兩個概念之間的語義相似度了。

1.2 相似度分析與設計思路

上述三種計算模型是通過不同的三個角度來量化概念之間的相似度。基于內容的語義相似度計算模型更具有理論說服性，它是由信息理論和概率統計理論當中的有關知識作為理論根據的。基于屬性的語義相似度計算模型更符合人類對于客觀世界中事物相似性識別的認知過程。但如果要做到準確識別，就必須要對客觀事物的所有屬性進行詳細描述才可以保證結果的正確性。基于距離的語義相似度計算模型，相對比較直觀，便于理解和認識，但是它首先應該是在一個完整的概念層次網絡的基礎上才可以發揮作用。概念層次的組織結構可以直接影響到語義的計算結果。

除了單一模型的提出，目前國內研究中還提供了一些在綜合因素的考慮下建立的計算模型，如文獻［2-7］中，一方面是在語義重合度、語義密度、概念屬性的角度綜合考慮；另一方面，另辟蹊徑如從過濾無關概念的角度或語義矩陣的方式出發給出了新型的計算模型。這些都是從不同角度進行的優化。但基于本體的思想，構建相似度計算模型的本身是為了構造一個完整的領域本體之上的分析系統，緊扣語義和概念應該是最為重要和本質的要求。加入過多的因素或脫離語義本身進行的排除性算法都會脫離基于本體的這個基礎概念。

針對上述分析結合不同計算模型的特點，本次項目把概念相似度放在一個層次結構進行描述，并在建模過程中，考慮結合屬性及語義重合度方面的因素作為影響因子，緊扣語義本身的特性推導影響因子，建立一個全新的計算模型。

2 新型相似度計算模型

2.1 計算模型的分析與構想

系統中所有的概念都存在于本體層次網絡結構當中，這是一個有著比較嚴謹的語義結構的體系［3］。因此，在這個結構中所處的位置可以體現出概念之間的一些關系。這個結構可以看成是一個由點和有向邊構成的一個有向圖。其中的有向邊表示了概念間的相關性關系。

如果假設這個有向圖中所有的邊權值都是1，所有概念結點沒有屬性，那么計算任意兩個概念結點之間的相似度就是計算它們之間的距離。當然現實情況并沒有這么簡單，概念的屬性在其中也起著重要的作用，它一方面可以直觀反映出概念本身的特征，另一方面兩個概念的屬性之間相似性越大，概念的相似度也越高。所以它也可以很好的反映概念間的相似性關系。

概念之間有向邊的距離和概念屬性的相似性都可以從各自的角度反映出概念相似度的情況，但是都不夠完整［2］。這類問題已在文獻［3-6］中有很多論證。如果在計算概念間有向邊距離的同時，可以考慮到屬性對最后結果的影響，那么將無疑大大增加相似度計算的精度。所以，為了得到盡量接近現實描述的相似度計算模型，就必須考慮到概念的屬性對概念之間相似度的影響。另一方面文獻［6］針對相似度計算也提出要考慮屬性、內容重合度等方面的因素。但是對于計算模型的建立只是通過簡單的調節因子之間的疊加進行。并且語義重合度與語義密度的計算有重復部分。在一個基于詞匯相似度計算的模式中，加入語義密度的因子似乎沒有太大的意義。

因此本項目的重點放在考慮屬性相似度計算及語義重合度和有向邊的相似度計算上。可以通過合理的公式推導，把屬性相似度及語義內容的重合因素加入基于有向邊相似度的計算模型，建立一個統一的相似度模型。通過分析發現，在計算有向邊距離的時候，每條有向邊都假設權值為1，其實由于關系類型不一樣它們應該具有不同的權值。可以把語義內容重合度計算加入到有向邊計算模型中，而概念屬性之間的相似性從層次網絡的角度來分析，也可以看作是對每條邊權數的反映。所以，如果從層次網絡結構中描述概念之間的相似度模型，可以考慮兩個方面的因素，一是加權之后有向邊的距離；二是概念屬性的相似性轉換成為邊的權數。

基于上述分析，建立計算模型的基本思想是：基于加權的有向邊和屬性的計算模型。確定影響有向邊權值的因素即屬性相似性的計算，給出計算這些因素的公式。而后推導出單位有向邊的距離與權值關系的計算公式。再根據任意兩個結點之間有向邊距離的計算公式，得出概念之間的權值從而給出概念間的相似度計算模型。

2.2 有向邊計算

一般在領域本體中，概念之間的關系有：上下位關系、同義關系、反義關系、對義關系、整體與部分關系等等［8］。在實現中，本體構成的層次網絡中只需要考慮三種關系即可，繼承關系、整體與部分關系、同義關系。這三種關系幾乎占到了概念間關系的絕大多數情況。每種關系都是概念間不同的相關程度，一般地，同義關系的有向邊表示其兩端的概念為同一個意思，相關度最高。部分與整體關系的相關度小于繼承關系的有向邊。在本體層次網絡中，兩個直接相連的概念結點一定是處于不同層次，因此也就是父子結點。

設任意兩個相連父子結點為x和y，則有向邊相關程度的計算公式，如公式（4）所示：

其中：3／4和1／4為領域專家給出的權值。該計算模型反映了有向邊的相關度和其類型之間的關系，將不同的類型轉換為對應的數值。

2.3 屬性相似性計算

在本體的層次網絡中，概念的描述是非常詳細和準確的，其中也包括了屬性描述。通過概念間擁有相同屬性的多少，在一定程度上就可以表示結點，也就是概念之間的相似程度。相同屬性越多，說明相似度越大，有向邊的權值也就越大。

由此得到有向邊與概念間屬性關系的公式，如公式（5）所示。

其中：Attr（x）、Arrt（y）表示概念x、y的屬性集合；Attr（x）∩Attr（y）表示概念x與概念y相同的屬性集合；Attr（x）∪Attr（y）表示概念x與概念y所有的屬性集合；cou（）表示屬性個數。

2.4 語義重合度計算

語義的重合度可以通過分析任意兩個概念結點之間所擁有的祖先結點的個數來判斷它們之間的重合度高低。顯然，如果兩個結點的祖先結點的個數越多，重合度就越高，如果一個都沒有，說明是完全沒有語義重合的兩個概念。

由此得到任意兩結點間的語義重合度的計算公式，如公式（6）所示。

其中：Up（x）、Up（y）表示概念結點x、y的祖先結點集合；Up（x）∩Up（y）表示概念x與概念y相同的祖先結點的集合；Up（x）∪Up（y）表示概念x與概念y所有的祖先結點的集合；cou（）表示對象個數。

2.5 權值因子計算公式

通過上面的推導，已經把影響權值的因素量化并給出了公式，接下來計算有向邊的權值。這部分是相似度計算模型中最核心的部分，其表達式應該為：

可以發現，當WAttr（x，y）與WNode（x，y）的值為1時，權值最大。表示兩個結點是相同的概念。其他取值都小于1且無限趨近于0，當然理論上存在屬性或語義完全不相交的情況，這時取值等于零。因此權值的取值范圍是［0，1］。

由此給出有向邊長度與權值的公式，如公式（7）所示。

其中，β為調節因子。顯然當權值為1時，長度為0，表示父子結點x，y表示同一個概念。

基于2.2中的分析已經得出了有向邊單位長度的計算公式。在本體層次網絡中對于任意兩個結點的計算公式也可以得出。這里借鑒Leacock模型中的結點距離公式來得出任意兩個結點距離的計算公式。

Leacock模型中距離公式如公式（8）所示。

其中Anc（p，q）表示任意結點p、q的最近共同祖先結點。這里可以代入單位距離的公式從而建立任意結點距離與單位結點距離的關系。如公式（9）所示。

其中path（p，q）表示兩個結點p，q在網絡中最短的路徑上所有結點的集合。

由此，可以得出本體層次網絡中任意兩個概念的相似度計算公式，如公式（10）所示。

其中的α為調節因子。雖然從公式上看，這里概念的相似程度的量化似乎只和結點距離有關系，但實際上，這里距離的得出是包含了有向邊相關程度，和概念間屬性的相似度來作為計算依據的。因此可以較為準確的反映出任意兩個概念之間的語義相關程度。

3 實際應用效果

以基于有向邊和屬性的計算模型作為算法核心構建的搜索引擎，已在一個實際項目上進行應用。對其基于本體的搜索引擎做了相關的性能測試。為了突出實驗的對比效果，除了實現本模型外，加入Montserrat模型與傳統的Leacock模型進行相同實驗對象的結果比對。為方便區別，提出的相似度計算模型用ZKM模型表示。

利用Protégé本體建立工具，使用Jena API，Lucene開源工具包，Java語言作為編程語言。選取5組，共41個概念作為分析對象，實現了本項目的模型和其它兩個比對模型。

實驗結果得到了比較理想的數據結果，選取其中一部分進行介紹，如表1所示。

通過表1中計算的結果可以發現，本項目的相似度計算結果比其他兩個計算模型計算結果的有效性有了明顯提高。前四個例子分別選取的是belong-to、part of關系的概念，在計算結構中都體現了比較好的相似性。最后一組是一個特例，概念“軟體”并不是本領域的專業詞匯，但是在臺灣的詞匯體系中，軟體就是軟件。這里算作是一種特殊關系進行測試。由于在構建領域本體中，作為陌生詞匯的“軟件”本身和軟件沒有直接聯系，但是通過追溯祖先結點和屬性重合度的權值調節，在最后的計算結果中也顯示了較高的相似度。從語義上，基本符合現實情況。

表1 不同相似度模型的計算結果（部分）

4 總結與展望

在本體概念架構下的搜索引擎構建中，概念相似度的分析始終是一個研究重點。相似度計算的精度會直接影響搜索的結果。目前對于相似度計算模型的優化改良算法也非常之多。通過有向圖、語義、屬性及過濾云服務［2-10］等方面的計算模型也層出不窮，其目的無外乎就是可以容納更多影響語義的因素。但是在研究過程中，很容易陷入巨大的海量信息中難以自拔，一味的加入能考慮到的各種因素并不是好的解決問題的方法，最后由于邊際效益遞減的規律，往往會讓新的計算模型反而得不到理想的計算結果。項目的研究立足于從現實相關語義的角度出發，并沒有盲目追求加入很多其他的影響因素。從文獻［11］中可以發現，通過統計學分析發現，并不是所有和語義相關的因素都對概念相似度有明顯的影響，有些甚至會成為語義分析的干擾項。因此去掉可能成為干擾項的影響因素，加強那些真正對語義影響重大的因素是本次項目探索的主題。

當然在研究過程中也發現還有一些問題需要解決。比如領域本體的構建方式本身就可能會對將來的相似度計算模型產生結構上的影響，因此在考慮相似度計算模型的同時，還要研究領域本體構建的方式，如何可以找到最適合的相似度計算模型。不同的模型考慮的重點是存在差異性的，這也會影響到最后分析的結果。因此，下一步的分析研究，可能要在關注優化相似度計算模型的同時，考慮與領域本體構建方式上的匹配問題。

［1］張功杰.面向本體的語義相似度計算及在檢索中的應用［J］.計算機工程與應用，2010（5）：131-133.

［2］向津.基于無關概念過濾的云服務相似推理技術研究［J］.計算機應用與軟件，2013（1）：183-185，199.

［3］李景.本體理論在文獻檢索系統中的應用研究［M］.北京：北京圖書館出版社，2005.

［4］劉宏哲.基于本體的語義相似度和相關度計算研究綜述［J］.計算機科學，2012（2）：8-13.

［5］甘明鑫.一種綜合加權的本體概念語義相似度計算方法［J］.計算機工程與應用，2012，48（17）：148-153.

［6］崔其文.改進的領域本體概念語義相似度計算方法［J］.計算機應用與軟件，2012（2）：173-174，182.

［7］王春紅.基于本體和多代理的考試系統模型研究［J］.河北工業科技，2010（3）：174-176.

［8］Fleischman M，Hovy E.Multi-document person name resolution［C］.／／Harabagiu S，Farwell D，eds.Proceedings of the Workshop on Reference Resolution and its Applications.Barcelona，Spain july 2004：1-8.

［9］Kivela A，Hyvonen E.Ontological theories for the semantic Web［M］.Helsinki：HIIT Publications，2002：111-136.

［10］Rodriguez M，Egenbofer M.Derermining Semantic Similarity Among Entity Classes From Different Ontologies［J］.IEEE Transactions on Knowledge and Data Engineening，2008，15（2）：442-456.

［11］Alexander Maeche.Ontology learning for the semantic web［M］.Norwell：Kluwer Academic Publishers，2008：15-17.

［12］武成崗，焦文品，田啟家.基于本體論和多主體的信息檢索服務器［J］.計算機研究與發展，2001，38（6）：641-647.

［13］Bray T，Paoli J，Sperberg-McQueen C M，et al，Extensible Markup Language（XML）1.0（Second Edition）［EB／OL］.W3C Recommendation，http：／／www.w3c.org／TR／2000／TEC-xml.2007-10-06.

［14］Jianmin Yao，Ming Zhou，et al.An Automatic Evaluation Method for Localization Oriented Lexicalised EBMT System［A］.In Proceeding of the 19th International Confernce on Computational Linguistics［C］.（COLING2002）.Taipei，200.

［15］史英杰.云數據管理系統中查詢技術研究綜述［J］.計算機學報，2013（2）：219-225.

［16］常萬軍.OWL本體存儲技術研究［J］.計算機工程與設計，2011（8）：2893-2896.

Sim ilarity Model Design Based on Edge and Attribute

CUIYan，ZHANG Shu-li
（Department of Computer Information Technology，Ming De College，Northwestern Polytechnical University，Xi＇an 710124，China）

Through the analysis of the calculation principle and design concept of similarity algorithm under the single condition，the concept of directed graph is described.The calculation models of the directed edge，the semantic overlap and the attribute similarity are analyzed and concluded to establish the concept similarity calculation modelwith semantic and attribute weight.Finally，the accuracy of the similarity calculation of the new model is verified by comparing with the traditional one.

Concept similarity；Directed edge；Weights of attributes；Ontology

10.3969／j.issn.1002-2279.2014.05.014

TP391

：A

：1002-2279（2014）05-0047-04

崔巖（1976-），男，河北邯鄲人，碩士研究生，講師，研究方向：數據庫技術與應用。

2014-01-17