基于基元和知網的問題相關度計算

網絡出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20150326.1014.002.html

基于基元和知網的問題相關度計算

曹禮園，李衛華

(廣東工業大學 計算機學院， 廣東 廣州 510006)

摘要：通過對可拓學的基元和復合元與知網的研究，利用Hownet中的詞語相似度的計算方法改進詞語相關度的計算方法，建立基元相關度計算方法，進而建立目標相關度和條件相關度的計算機方法，形成問題相關度的計算。改進了相關度算法，傳統方法只通過上下位關系計算詞語相關度，將知網描述的其他15個關系也考慮進來，并提出了負相關的概念，將相關度的取值范圍定在[-1，1]，對應了關聯函數的值域。通過對基元中特征與特征的對應關系，計算出基元的相關度，進而計算問題的相關度。通過對數據庫里的上千個矛盾問題進行測試，證實了這種方法可有效增加策略生成途徑，使矛盾問題解決的概率大大提高。

關鍵詞：可拓學；知網；相關度；基元；關聯函數

DOI:10.3969/j.issn.1673-4785.

中圖分類號：TP311文獻標志碼：A

收稿日期：2013-10-06. 網絡出版日期：2015-03-26.

基金項目：國家自然科學基金資助項目(61273306).

作者簡介：

中文引用格式：曹禮園，李衛華. 基于基元和知網的問題相關度計算[J]. 智能系統學報， 2015, 10(2): 234-239.

英文引用格式：CAO Liyuan, LI Weihua. Calculation of correlation problem based on basic element and HowNet[J]. CAAI Transactions on Intelligent Systems, 2015, 10(2): 234-239.

Calculation of correlation problem based on basic element and HowNet

CAO Liyuan, LI Weihua

(College of Computer， Guangdong University of Technology, Guangzhou 510006， China)

Abstract：Based on the basic-element and composite elements of extenics and HowNet research, the words similarity computing method in HowNet is used to improve the calculation method for the relationship of words. The basic-element correlation calculation method is built to establish a method for basic-element target correlation and basic-element conditions correlation. This is used to derive the method to calculate correlation of problem. There is improvement with the correlation algorithm, but the traditional method calculates the correlation of words only by hyponymy. In this paper, an additional fifteen relationships described in HowNet is taken into account. The concept of negative correlation is put forward and the range of correlation is in set [-1, 1], which corresponds to the range of the correlation function. Through the corresponding relationship between the features in the basic element, the correlation between basic elements is calculated and the correlation of problems can be calculated. Based on the test of thousands of contradictory problems in the database, the results showed that this method can effectively increase the amount of strategy generating approaches and the probability of contradictory problems to be solved is greatly promoted.

Keywords：extenics; HowNet; correlation; basicelement;dependent function

通信作者：曹禮園.E-mail：369206663@qq.com.

可拓學[1]是一門中國原創的新學科，它以形式化的模型，探討事物拓展的可能性以及開拓創新的規律與方法，并用于解決矛盾問題。知網[2]( HowNet)是一個以漢語和英語的詞語所代表的概念為描述對象，以揭示概念與概念之間以及概念所具有的屬性之間的關系為基本內容的常識知識庫。知網的建網方式、知識獲取和表達方式、事件概念分類方法和其自行設計的知識數據描述拓學中提出解決矛盾問題的策略生成知識需求。本文將可拓學和知網這個中國原創的理論和應用工具相結合，進一步提高了可拓學智能化水平，拓展了知網的應用。 在文獻[3]中，蔡文教授首先提出物元模型的概念，文獻[4]提出了關聯函數的構造方法。知網是我國著名機器翻譯專家董振東先生創立的一個知識系統，它包含豐富的語義知識和世界知識。文獻[5]通過知識描述結構和上下位關系計算義原相似度，文獻[6]和[7]分別提出了一種利用相關度來計算詞語相關度的算法。

1傳統的可拓策略生成系統分析問題的不足

傳統的策略生成系統是先建立可拓模型，即建立問題P的核問題P0的可拓模型為P0=g0×l0，其中，g0為問題的目標，l0為問題的條件。再確定問題的關聯函數K，然后對問題P0進行相容性分析，若不相容(目標與條件有矛盾)，則對問題的目標或條件進行可拓分析，得到問題的發散樹或相關樹，通過對問題發散樹或相關樹的“葉”基元進行可拓變換，生成候選策略集合，最后對策略集合中的策略進行優度評價，推薦優度較高的策略供決策者選擇。這種分析問題的方法存在著一些不足之處。

首先，這個解決問題的方法對每個問題都進行整個過程，當遇到類似的問題時，系統依然重復上次策略生成的過程，增加了策略生成的時間。

其次，這個過程無法對問題進行歸類。也找不到問題之間關聯性，因而無法對問題進行歸并，進而找到通用解。同時導致策略的針對性不強。

可見，在可拓策略生成系統中，在原問題和核問題建模后，增加另一個過程――進入矛盾問題庫，用問題相關度判斷是否與已有矛盾問題相關(或相同)是非常重要的。如果問題與已在問題庫的問題類似，則可直接進入可拓策略庫搜索選取相應的策略，縮短問題解決的時間，提高問題解決的概率。

2詞語相關度計算模型

2.1詞語相關概念

定義1詞語相關度。給定2個詞語B1和B2，它們之間的相關度通過函數rele(B1，B2):S×S→[-1，1]，表示集合S中2個詞語B1和B2的相關程度。

相關度函數的性質具有自反性和對稱性，即對于B1∈S，B2∈S，形式上有:

1)rele(B1,B2)∈[-1，1]。相關度的計算值為[-1,1]中的一個實數。

2) 相關關系具有自反性，rele(B1，B2) = rele(B2，B1) 。

3)rele(B1,B2)=1,當且僅當B1=B2，即如果2個詞匯是詞語等價，則相關度為1。

4)rele(B1,B2)=-1,當且僅當即存在對義或反義關系，相關度為-1。

5)rele(B1,B2)=0。如果2個基元沒有任何共同特征，那么其相關度為0。

定義2正相關。給定2個基元B1和B2，如rele(B1，B2) >0,則稱B1、B2正相關。

定義3負相關。給定2個基元B1和B2，如rele(B1，B2) <0,則稱B1、B2負相關。

在知網中，美麗與漂亮的相關度為1，美麗與丑陋的相關度0.814815，在情感分析中，美麗與丑陋是反義的。美麗和丑陋在句子中是可以替換的，但這并不符合句子的原意。

負相關是指2個詞語是對義或者反義，或者兩者在路徑中存在對義或反義關系。如：假設O1與O3是反義(對義)關系(根據《同義、反義以及對義組的形成》獲得)，則O5、O9的相關度就是在路徑中存在對義或反義關系，rele(O5，O9)為負數。

2.2詞語相關度計算

相似的詞語相關的可能性也大些，把詞語的相似度和基于直接關系和語義關系挖掘規則獲得的關系作為判斷是否相關的依據而得出來的基本相關度部分按比例相加，就得到了詞語的相關度。

2.2.1相似度部分 Sim(W1,W2)

2個詞語相似度計算，直接采用文獻[5]中方法計算。

2.2.2 基本相關度部分Rele_prim(W1,W2)

對于2個漢語詞語W1和W2，如果W1有n個義項(概念)： S11,S12,…，S1n，W2有m個義項(概念)：S11,S12,…，S1n規定，W1和W2的相關度是各個概念的相關度絕對值最大的那個值，也就是說：

Rele_prim(W1,W2)=

這樣，就把2個詞語之間的相關度問題歸結到了2個概念之間的相關度問題。

下面來計算2個義項S1和S2之間的相關度。

S1與S2的知網形式化表示為

定義相對相關度Re le_primi(S1,S2)，Rele_primi(S1,S2)代表概念相對于概念S1在關系i上的相對相關度,定義

它包括直接關系和間接關系。

直接關系包括上下位關系之外、同義關系、反義關系、對義關系、部件-整體關系、屬性-宿主、材料-成品、施事/經驗者/關系主體-事件關系、受事/內容/領屬物等-事件關系、工具-事件關系、場所-事件、時間-事件關系、值-屬性關系、實體-值關系、事件-角色關系、相關關系等16種關系。間接關系指根據語義關系挖掘規則獲得的關系[9]。

Rele_prim(S1,S2)=

[∑wiRele_primi(S1,S2)+

∑wjRele_primj(S2,S1)]/2

表1　 知網間接關系挖掘規則

wi是S1對S2對應的關系的權值，wj是S2對S1對應的關系的權值，都是可調節的參數。

例如：

國慶：time|時間，day|日，@congratudate|祝賀，#country|國家

煙花炮竹：tool|用具，*whileAway|消閑,*congratulate|祝賀

“國慶”和“煙花炮竹”通過事件“祝賀”相關，計算如下：

在關系@上S1與S2相關，在關系*上S2與S1相關，所以Rele_prim(S1,S2)=(w@*1+w**1)/2

2.2.3詞語相關度Rele(W1,W2)計算

Rele(W1,W2)=

β1Sim(S1,S2)+β2Rele_primi(S1,S2)

式中：β1+β2=1。

β1和β2是相似度Sim(S1,S2)和基本相關度Rele_prim(S1,S2)在總體相關度所占的比例。

3基元及問題相關度計算

3.1基元概念以及基元與基元的對應關系

3.1.1基元的概念

定義4 以物Om為對象，Cm為特征，Om關于Cm的量值Vm構成的有序三元組：

作為描述物的基本元，稱為一維物元，Om、Cm、Vm三者稱為物元M的三要素，其中Cm和Vm構成的二元組(Cm,Vm)稱為物Om的特征元。

為方便起見，把物元的全體記為￡(M)，物的全體記為￡(Om)，特征的全體記為￡(Cm)。關于特征Cm的取值范圍記為V(Cm)，稱為Cm的量域。

一物具有多個特征，與一維物元相仿，可以定義多維物元：

定義5物Om, n個特征名cm1，cm2，…，cmn及Om關于cmi(i=1,2，…,n)對應的量值vmi(i=1,2，…,n)所構成的陣列：

稱為n維物元，其中

3.1.2基元與基元之間的對應關系

在基元中，最重要是的特征與特征的對應關系。依靠下列方法建立基元的特征與另一基元的特征的對應關系：

1)首先計算2個基元的所有特征兩兩之間的相關度；

2)從所有的相關度值中選擇最大的一個，將這個相關度值對應的2個特征對應起來；

3)從所有的相關度值中刪去那些已經建立對應關系的特征的相關度值；

4)重復上述2)和3)，直到所有的相關度值都被刪除；

5)沒有建立起對應關系的特征與空特征對應。

3.2基元相關度計算

每一個特征就是一個詞語，特征對應特征，相當于詞語對應詞語，即用詞語相關度計算方法計算對應特征相關度。將對應起來的特征分別計算關聯度，最后按比例相加，就是基元相關，計算公式為

Ri是一個比例系數，等于1/k

3.3問題相關度計算

問題建模是按以下步驟進行：

界定問題1的目標g1與條件l1和問題2的目標g2與條件l2，并用基元表示分別建立問題的可拓模型P1=g1×l1、P2=g2×l2利用基元相關公式分別計算出目標基元和條件基元的相關度以后，再計算問題相關度Rele_P(P1,P2)，計算公式為

Rele_P(P1,P2)=

4案例分析

利用以下6個問題測試問題相關度問題：

P1曹沖稱象；

P2用直尺測量一張紙的厚度；

P3把一根長為2m、寬為1.2m、高為0.5m的桌子抬進高為2m、寬為1m的門；

P4把一根長為3m、半徑為0.2m的竹桿抬進高為2.5m、寬為2m的城門；

根據文獻[1]中的方法，建立問題的可拓模型P=G×L，進而提取核問題：

P0=g0×l0

問題相關度計算

Rele_P(P1,P2)=-0.394

Rele_P(P1,P3)=+0.204

Rele_P(P1,P4)=+0.075

Rele_P(P2,P3)=-0.076

Rele_P(P2,P4)=+0.204

Rele_P(P3,P4)=+0.654

在參數的選擇上，由于一般認為%、#、?、*、@、$、&所代表的關系權重程度逐漸下降，即表1中的關系的重要程度逐步下降。經多次測試，最終設置參數如下:w1=0.25,w2=0.2,w3=0.2,w4=0.15,w5=0.10,w6=0.05,w7=0.05，其中，1～7分別指關系%、#、?、*、@、$、&。

對于相關度的太低的相關度值，可以認為它不相關，把相關度大于0.3作為相關的閾值。

Rele_P(P1,P2)=-0.394

Rele_P(P3,P4)=+0.654

解決策略：Rele_P(P1,P2)=-0.394說明這個矛盾問題是負相關的。對于P1，采取復制變換，用測量N張紙的厚度N×y∈[1,20]cm。

通過解決問題P1，采用可拓變換中的逆變換找出解決問題P2的方法，即利用分解變換(在利用分解變換的之前，先利用置換變換)。

Rele_P(P3,P4)=+0.654

說明這2個矛盾問題是高度正相關的，P3、P4可采取類似的方法解決。對P3，將桌子旋轉，高變為寬，寬變為高，則可抬入門內。對P4也可采取這種方法。

5實驗及結果

根據上述方法，利用C++，采用VS編程環境實現計算問題相關度程序，并對問題庫里的2413個矛盾問題的問題相關度計算。實驗參數設置如下:w1=0.25,w2=0.2,w3=0.2,w4=0.15,w5=0.10,w6=0.05,w7=0.05。

其中，1～7分別指關系%、#、?、*、@、$、&。閾值為0.3。

通過計算，其中1782個與其他問題相關。將相關問題放在一起研究，并運用可拓學策略生成方法再次研究解決矛盾問題，實驗結果如下。

表2　 實驗結果

在運用基于問題相關度計算方法后，有73.85%的問題是相關的，其中有140個未解決的問題被解決了，而在已經解決的問題中，有325個問題找到了更好的方法改進策略。所以在總體情況下，基于問題相關度方法對策略生成的改進量為19.27%：其中是將未解決的問題變成已解決5.80%， 13.46%是將已解決的問題找到更好的策略。

6結束語

通過計算基元的相關度進而計算問題的相關度，可以使相關度很高的問題歸類。正相關度高的問題之間，可通過解決問題A而找出類似的方法解決問題B，而負相關的問題之間，通過解決問題A，而逆向找出解決問題B的方法。而將相關問題歸類后，可通過歸納總結得出此類問題的一般特征，找出解決此類問題的一般規律，進而改進策略生成方法，使未解決的矛盾問題得到解決，或者使已解決的矛盾問題找到更優的策略。

實踐證明，這種方法可有效增加策略生成途徑，使矛盾問題解決的概率大大提高。

參考文獻:

[1]楊春燕,蔡文. 可拓工程[M]. 北京：科學出版社， 2007: 1-344.

[2]董振東.HowNet[EB/OL] .[2013-05-12]. http://www．keenage．com.

[3]蔡文. 可拓集合和不相容問題[J]. 科學探索報，1983(1)： 83-97

CAI Wen. Extension set and non compatible problems [J]. Science Journal, 1983 (1): 83-97

[4]李橋興，劉思峰. 基于區間距和區間側距的初等關聯函數構造[J]. 哈爾濱工業大學學報, 2006, 38(7) :1097-1100.

LI Qiaoxing, LIU Sifeng. Elementary dependent function is constructed based on the interval distance and lateral distance[J]. Journal of Harbin Institute of Technology, 2006, 38 (7): 1097-1100.

[5]劉群,李素建.基于《知網》的詞匯語義相似度計算[J]. 計算語言學及中文信息處理, 2002(7): 59-76.

LIU Qun, LI Sujian. based on HowNet semantic similarity calculation[J]. Computational Linguistics and Chinese Information Processing, 2002(7): 59-76.

[6]趙應秋, 羅軍, 張君艷. 基于知網的詞語語義相關度計算[J]. 信息技術, 2010 (3): 90-93.

ZHAO Yingqiu, LUO Jun, ZHANG Junyan. The word semantic relevancy computation based on HowNet[J]. Information Technology, 2010 (3): 90-93.

[7]許云, 樊效忠, 張鋒. 基于知網的語義相關度計算[J]. 北京理工大學學報, 2005, 25(5): 411-414.

XU Yun, FAN Xiaozhong, ZHANG Feng. Semantic relevancy computing based on HowNet[J]. Journal of Beijing Institute of Technology, 2005, 25 (5): 411-414.

[8]江敏,肖詩斌,王弘蔚,等. 一種改進的基于《知網》的詞語語義形似度計算[J]. 中文信息學報, 2008, 22( 5) : 84-89.

JIANG Min, XIAO Shibin, WANG Hongwei, et al. An improved word similarity computing method based on HowNet[J]. Journal of Chinese Information Processing, 2008, 22 (5): 84-89.

[9]王紅玲，呂強，徐瑞. 中文語義相關度計算模型研究[J]. 計算機工程與應用， 2009， 45(7): 22-26

WANG Hongling, LV Qiang, XU Rui. Chinese semantic relativity calculation of model [J] Computer Engineering and Applications, 2009, 45 (7): 22-26.

[10]劉宗妹. 本體可拓模型的復合元實現及應用研究[D]. 廣州： 廣東工業大學， 2010： 1-48.

LIU Zongmei. Meta ontology extension model research and application of the[D]. Guangzhou: Guangdong University of Technology, 2010: 1-48.

[11]李立希,楊春燕,李鏵汶.可拓策略生成系統[M]. 北京： 科學出版社， 2006: 1-231.

[12]方卓君,李衛華,李承曉.自助游可拓策略生成系統的研究與實現[J]. 廣東工業大學學報, 2009， 26(2)： 83-89.

FANG Zhuojun, LI Weihua, LI Chengxiao. The self-help travel extension and implementation[J]. Journal of Guangdong University of Technology, 2009, 26 (2): 83-89.

[13]李承曉,李衛華. 租房可拓策略生成系統[J]. 智能系統學報, 2011, 6(3)： 272-278.

LI Chengxiao, LI Weihua. The extension strategy generating system for rental of intelligent[J]. CAAI Transactions on Intelligent Systems, 2011, 6 (3): 272-278.

曹禮園，女，1987年生，碩士研究生，主要研究方向為智能軟件。

李衛華，女，1957年生，教授，主要研究方向為面向Agent計算、網絡信息系統、智能軟件。發表學術論文40余篇。