一個基于語義元的相似度計算方法研究
2008-12-31 00:00:00王剛邱玉輝蒲國林
計算機應用研究 2008年11期
(1.西南大學 語義網格實驗室， 重慶 400715; 2.安康學院 物理與計算機科學系， 陜西 安康 725000; 3.四川文理學院 計算機科學系， 四川 達州 635000)
摘要：針對已有相似性度量方法的局限與不足，對屬性進行語義擴展，提出了基于語義元支持度的相似度計算方法，該方法用語義元表示概念內涵，在語義元中引入支持度來表現不同語義元對概念表示的貢獻，綜合考慮相關性、相似性、非對稱性以及語義元的支持度，通過比較語義元的相似性，實現了概念相似性的度量。把關系作為一種特殊的概念進行關系的比較，得到了基于語義元的本體相似性度量。最后，將該方法與其他方法進行比較，驗證了該方法的計算結果更具有合理性，同時也驗證了該方法的有效性與正確性。
關鍵詞：語義; 本體; 相似性度量; 概念; 關系
中圖分類號：TP301.6文獻標志碼：A
文章編號：1001-3695(2008)11-3253-03
Research on similarity based on semantic unit
WANG Gang1，2， QIU Yu-hui1， PU Guo-lin1，3
(1.Laboratory of Semantic Grid，Southwest University， Chongqing 400715， China; 2.Dept. ofPhysics Computer， Ankang College， Ankang Shaanxi 725000， China; 3.Dept. of Computer Science， Sichuan University of Arts Science， Dazhou Sichuan 635000， China)
Abstract:Because of the flaw of previous models， this paper extended the concept attributes by semantic and proposed a method to measure the similarity based on the semantic unit. Used the semantic unit to express the concept implication， and used the support degree to show the contributions of the semantic unit. It did successfully the concept similarity measure by considering the relevance， resemblance， non-symmetry， and the support degree. Looked on the relation as concept， and measured the ontology similarity based on semantic unit. Finally， the experiment proves that this method is better than other me-thods.
Key words：semantic; ontology; similarity measure; concept; relations
0引言
概念相似性度量在服務選擇[1，2]、自然語言理解、文獻檢索等領域具有重要的作用。當前主要模型有：a)基于距離的語義相似度計算模型。該模型簡單、直觀，但它依賴預先建立好的概念層次網絡，網絡的結構直接影響到語義相似度的計算。b)基于內容的語義相似度計算模型。該模型充分利用了信息理論和概率統計理論的相關知識；但是，這種方法不能更細致地區分層次網絡中各個概念之間語義相似度的值。c)基于屬性的語義相似度計算模型。該模型可以很好地模擬人們平時對現實世界中事物之間的認識和辨別，但要求對客觀事物的每一個屬性進行詳細和全面的描述。本體相似性度量[3，4]包括概念相似性度量、關系相似性度量。詞匯相似性度量通過計算詞語之間的距離來實現，主要是利用本體的層次以及語料庫，通過判斷詞語的相似性來計算。d）認知心理學對相似性研究主要有幾何相似性模型、Tversky模型以及Rodriguez_Egenhofer模型，這些模型都提出了計算相似度的方法與公式。不過，這些模型注重對象相似屬性的個數，忽略了屬性重要性的差異以及屬性的語義擴展。
上述方法的困難與局限在于:a）基于本體的層次結構來比較概念的相似性，需要專家來精心安排概念所處的層次[8~10]，以及安排層次中概念所處的位置，才能計算概念的距離。然而，在實際應用中，面對大量概念與關系，這是很困難的事情。b）概念所處的位置與層次對距離會產生影響。理論上兩個相同的概念，無論位于什么層、什么位置，計算出的距離應該相同，而同一概念理論上也可以位于任何層的任何位置。由于基于距離的方法嚴格限制了概念的位置，使得相似度計算面臨很多困難。c）不能對屬性進行擴展。文獻[10]提出了基于概念上下位置關系的本體比較，但是上下位置關系不能有效表述概念的語義，如概念“雪”與“冷”，如果它們在本體中不具有上下位置關系，就不能確定它們之間的關系，而實際情況是，它們之間可以是蘊涵關系。d）忽略了概念屬性之間的差異性，不同屬性在表示概念時具有不同的重要性。e）忽略了人們對相似性認知的特點。對象的相似性與它們的共同點有關，共同點越多，相似性越大；對象的相似性與它們的差異性有關，差異越大，相似性越小；對象只有共同點，沒有差異點時，稱對象相同，其相似性最大；對象只存在差異點而沒有共同點時，稱對象互斥，其相似性最小；相似性的非對稱性，即對象A與B的相似度不應該等于對象B與A的相似度。例如玩具火車與火車相似，而不能說火車與玩具火車相似。
針對上述困難與局限，本文把心理學中對相似性研究的成果引入到概念相似性度量，提出了基于語義元支持度的概念相似性度量方法。該方法首先對特征進行語義擴展，用語義元表示概念內涵，引入支持度來表現不同語義元對概念內涵表示的貢獻，綜合考慮相似性、相關性、差異性、不同義元的支持度以及不對稱性，通過比較語義元的相似性，實現了概念相似性的度量。把關系作為一種特殊的概念進行關系的比較，最后得到了基于語義元的本體相似度計算方法。
1語義元及其支持度
認知心理學認為概念由定義特征與特異特征構成，如知更鳥具有動物、有羽毛、有翅膀等這類絕對必需的特征；特異特征具有描述的功能，如在樹上棲息、不馴服、無害等特征。可見，不同的特征在表達概念內涵方面具有不同的作用，概念是這些特征的集合。然而，特征不能完全表示概念的語義內涵，因為概念的內涵應該包括根據特征推理的結果。本文把特征和推理的結果稱為語義元。語義元是表示語義的不能再劃分的基本單位，概念C表示為C={∪ki=1ei}，它表示概念由k個語義元組成，如雪:{冷，冬天，毛衣，棉衣，0℃，風，水，…}等。語義元中，有概念的定義特征，也有概念的特異特征稱為基本語義元，還有語義擴展的結果，稱為擴展語義元。概念語義擴展通常是按照推理規則進行推理，推理的結果是擴展語義元。對語義元可以按照如下公式來判斷語義元是否匹配。對概念C1:{e1，e2，e3，…，em}，C2{e1′，e2′，e3′，…，en′}。
sim(ei，e′j)=0:ei｜≠e′j1:ei｜=e′jj
不同的語義元在表現概念內涵方面具有差異，本文用支持度來刻畫它們的差異。
設C1：{e1：α1，e2：α2，e3：α3，…，em：αm}（0＜αi≤1），ei:αi表示ei的支持度為αi。可按如下規則進行語義擴展：
a）R(A)→ek表示對象A按規則R推理， 得到的語義元ek，其支持度為1；
b)R(ei)→ek表示表示語義元ei按規則R推理， 得到的語義元ek，其支持度為ei:αi;
c）R(ei∩em∩…∩en)→ek表示對語義元交集按規則R推理得到的語義元ek，其支持度為minni=1(ei:αi)，即取最小支持度。
d）R(ei∪em∪…∪en)→ek表示對語義元并集按規則R推理得到的語義元ek，其支持度為maxni=1(ei:αi)，即取最大支持度。
例如文獻[10]中定義概念“男人”{生物，人，男性，語言，有子女，雄壯，家庭，挑水，耕田，工作，責任}，定義對應的支持度為[1，1，1，0.8，0.6，0.5，0.6，0.6，0.5，0.5]。確定基本語義元e的支持度d可以按如下的算法進行。
算法1確定基本語義元ei的支持度。Ai為對象集合，ei為語義元，k為包含語義元ei的對象數量。
Begin
For (i =1 to n)
{if (e∈Ai)
k=k+1;}
d=k/∑ni｜Ai｜;
End
2相似度計算
21概念的相似度計算
定義1n=｜S｜表示集合S包含的元素個數為n。
定義2f(A∩B)=｜A∩B｜，即集合交集元素的個數。
定義3f(A-B)=｜A-B｜、即A-B元素的個數。
按如下的算法來計算對象A、B的相似度
算法2計算概念的相似度
Begin
假設有對象A、B，支持度集合分別為sd1、sd2;
求A∩B，I=A∩B，ex∈A∩B，sd′1∈sd1，sd′2∈sd2，I(A)={ek}，ek∈A，ek∈I，m=｜A∩B｜;
r1=a/（a+b）；其中a=∑mi=1(ei:i+e′i:β′i)，b=∑mi=1(e″i:′i+ei:β″i)，i，β′i≥δ，ei∈I，′i，β″i＜δ，ei∈I(A)，e′i∈I(B)，e″i∈I(A)，ei∈I(A)，ei=e′i，e″i=ei；
r2=x/（x+y）；其中x=∑mi=1ei:i，ei∈I(A)，i≥δ，y=∑mi=1e′i:′i，e′i∈I(A)，′i＜ δ；
r3=｜A′｜/m，ei∈A′，ei:i≥δ，ei∈I；
r4=(∑｜Wi｜+∑｜W′i｜)/(2m)，wi:i≥δ，w′i:′i≥δ，wi∈I(A)，w′i∈I(B)；
p(ei，ej)=1/e｜r1-r2｜×1/e｜r3-r4｜表示交集中主要特征支持度差別越小，相似度越大， 交集中主要特征個數差越小，相似度越大；
計算q(ei，ej)=f(A∩B）/[f(A∪B)+α×f(A-B)+β×f(B-A)]，α和β為系數;
sim-concept(A，B)=p(ei，ej)×q(ei，ej)
sim-concept(A，B)就是概念ci，cj的相似度
End
22本體相似度計算
本體由概念和關系組成，本體的相似性度量包括概念和關系的相似性度量[6，7]。本文采用加權平均的方法，先度量本體概念的相似度，然后度量關系的相似度，最后求得本體的相似度。利用前面算法得到sim-concept(O1，O2)=1/(n1×n2)×∑i=n1;j=n2i=1，j=1sim(ci，cj)，n1、n2為O1、O2中概念的個數。
關系由概念和關系核組成。例如最基本的關系R1={c1，c2，r1}，R2={c3，c4，r2}，表示關系R1包含概念c1、c2和關系核r1， 關系R2包含概念c3、c4和關系核r2。按如下公式計算關系Ri、Rj的相似度。
定義sim-relation(Ri，Rj)=sim-concept(c1i，c1j)×sim-concept(c2i，c2j)×sim-concept(ri，rj)， 對于上述關系R1、R2，它們的相似度計算包括概念的相似度與關系核的相似度計算， sim(R1，R3)=sim(c1，c3)×sim(c2，c4)×sim(r1，r3)。
本體中關系相似度sim-relation(O1，O2)=1/(m×n) ∑i=m， j=ni=1，j=1sim-relation(Ri，Rj)。其中：m、n為O1、O2中關系的數目；Ri∈O1，Rj∈O2 。
由此可以得出本體的相似度：sim-ontology(Ox，Oy)= sim-concept(Ox，Oy)×sim-relation(Ox，Oy)。
3實驗及比較
31實驗1：結果比較
目前，國內外缺少統一的數據來度量概念的相似度。本文利用參考文獻提供的研究數據，引用了方法1、2、3的結果[10]，方法4是采用本文算法計算的結果δ=0.6。支持度由算法1得出。方法4（C1→C2）表示以概念C1為參照對象；方法4（C2→C1）表示以概念C2為參照對象；參考文獻中，方法1使用“知網”語義表達式中第一獨立義原來計算詞語相似度；方法2使用文獻[10]的詞語語義相似度計算方法；方法3使用基于“知網”的詞匯語義相似度計算。對參考文獻中的數據，本文設計如表1所示的語義元與支持度。
表1語義元及支持度
概念語義元及支持度
男人
生物人男性語言雄壯家庭挑水耕田工作責任
1110.80.60.50.60.60.50.5
女人
生物人女性語言溫柔家庭織布耕田工作責任
1110.80.60.50.60.10.50.5
父親
生物人男性有孩子語言雄壯家庭挑水耕田工作責任
11110.80.610.60.60.50.5
母親
生物人生孩子有孩子語言女性溫柔家庭織布耕田工作責任
11110.810.610.40.10.50.6
和尚
生物人念經語言挑水耕田
1110.80.20.1
經理
生物人語言家庭有子女工作責任
110.80.40.411
鯉魚
生物魚水游動鯉魚
11111
工作
人工作11
責任
人責任11
從表2可見，本文算法的計算結果更符合常理。在方法3中，男人與女人、男人與母親、男人與和尚，他們的相似度是一樣的，這不符合人們的認識常理；方法4中，男人與父親相似度最大，但不完全相似，而方法3中，男人與父親相似度為1，這也不符合常理；方法3中，男人與女人、母親的相似度相同，而方法4中，男人與母親的相似度小于男人與女人的相似度，這也符合常理，因為女人母親。另外，在方法4中，相似性是非對成的，符合相似性的性質；而方法1，2，3中相似性是不對稱的。從上述分析可見，方法4更有效。
表2相似度比較表
C1C2方法1方法2方法3方法4（C1→C2）方法4（C2→C1）
男人女人1.0000.6680.8330．543 10．591 6
男人父親1.0001.0001.0000．974 20．754 7
男人母親1.0000.6680.8330．518 20．437 4
男人和尚1.0000.6680.8330．615 70．744 2
男人經理1.0000.3510.6570．522 60．630 6
男人鯉魚0.3470.0090.2080．083 80．166 7
男人工作0.1860.0350.1640．194 30．341 9
男人責任0.0160.0050.0100．194 30．341 9
32實驗2：結果比較
該實驗數據也選自參考文獻[8]，α=0.8，β=0.2，δ=0.6，支持度由算法1得出。數據和如表3所示。
從表4可見，方法3中，工人與教師、農民、運動員的相似度是相同的，這顯然不合常理；方法4中，工人與科學家的相似度小于與教師、農民、運動員的相似度，是符合常理的。方法3中，教師與農民、運動員的相似度一樣；而方法4中，與農民的相似度大于與運動員的相似度，因為他們都具有工作這個語義元，而運動員沒有這個語義元。方法3中，教師與科學家的相似度小于教師與農民的相似度，這不合常理；而方法4中，他們是最相似的一組，這是符合常理的。方法4體現了差異性。另外，在方法4中，相似性是非對稱的，符合相似性的性質；而方法3中，相似性是不對稱的。從上述分析可見，方法4更合理。
表3語義元及支持度表
概念語義元及支持度
工人
人工作工廠男女體力文化研究
1110.50.50.80.40.2
教師
人工作學校男女腦力文化研究
1110.50.50.910.7
農民
人工作田土男女體力文化研究
1110.50.510.10.1
科學家
人工作實驗室男女腦力文化研究
110.80.50.5111
運動員
人訓練比賽男女體力文化研究技能
1110.50.510.20.11
表4相似度比較表
C1C2方法3方法4（C1→C2）方法4（C2→C1）
工人教師0.7220．6280．499 5
工人科學家0.5760．626 10．497 3
工人農民0.7220．821 70．810 9
工人運動員0.7220．638 70．632 2
教師科學家0.5760．846 80．846 0
教師農民0.7220．502 10．623 2
教師運動員0.7220．363 20．452 4
科學家農民0.5760．499 60．621 1
科學家運動員0.60．361 60．451 1
33實驗3：屬性數量的變化對相似度的影響
從圖1、2可見，語義元支持度增加且是共同特征，相似度會增加；非共同特征的增加，相似度會減少。支持度雖然很小，但如果是共同特征，相似度也會增加。這也符合認識事物的規律，即差異性越大，相似性越小。
4結束語
計算相似度的方法有很多，本文提出的基于語義元支持度的相似度計算方法對概念特征進行擴展，用語義元表示概念內涵，引入支持度來表現不同語義元對概念內涵表示的貢獻，結合心理學理論，實現了概念相似性的度量。本文將關系作為一種特殊的概念進行關系的比較，最后得到了基于語義元的本體相似度計算方法。實驗表明，本文方法更具科學性與合理性，然而本文的關鍵是確定語義元的支持度，采用的是基于統計的結果，如何更科學地確定支持度，需要進一步研究。
參考文獻：
［1］TANGMUNARUNKIT H.Ontology based resource matching in the grid:the grid meets the semantic Web[C]//Proc of the 2nd International Semantic Web Conference. Sanibel-Captiva Islands:[s.n.]， 2003.
[2]LIU Chuang， FOSTER I. A constraint language approach to grid resource selection[C]//Proc of the 12th IEEE International Symposium on High Performance Distributed Computing . Chicago:IEEE Press，2003
[3]WACHE H，VOGELE T，VISSER U，et al. Ontology-based integration of information:a survey of existing approaches[C]//Proc of the IJCAI’01 Workshop: Ontologies and Information Sharing. Seattle， WA:Springer， 2001.
[4]LI Lei， HORROCKS I. A software framework for matchmaking based on semantic Web technology[C]//Proc of the 12th International World Wide Web Conference (WWW2003).Germany:Folbah Verlag Press，2003.
[5]PAOLUCCI M. Semantic matching of Web service capabilities[C]//Proc of the 1st International Semantic Web Conference (ISWC). Italy:IOS Press， 2002.
[6]SOLOMON M. Matchmaking distributed resource management for high throughput computing[C]//Proc of the 7th IEEE International Symposium on High Performance Distributed Computing. Chicago: IEEE CS Press， 1998.
[7]SOLOMON M， RAMAN R. Resource management through multilateral matchmaking[C]//Proc of the 9th IEEE Symposium on High Perfor-mance Distributed Computing (HPDC9). Pittsburgh:AAAI Press，2000.
[8]BIANCHINI D. Hybrid ontology based matchmaking for service disco-very[C]//Proc of Symposium on Applied Computing the 2006 ACM Symposium on Applied Computing . New York:ACM Press， 2006.
[9]吳健，吳朝暉，李瑩，等.基于本體論和詞匯語義相似度的Web 服務發現［J］.計算機學報， 2005，28(4):595-602.
[10]劉群，李素建. 基于“知網”的詞匯語義相似度計算[C]//第三屆漢語詞匯語義學研討會. 2002.
