支持用戶偏好查詢的領域概念圖模型

高志君，鄭俊生，安敬民

(1.大連東軟信息學院 計算機學院，遼寧 大連 116023； 2.大連海事大學 信息科學技術學院，遼寧 大連 116026)

0 引 言

傳統的概念聚類主要可分為3類，分別是基于語法相似度的概念聚類、基于語義相似度的概念聚類以及基于語用相似度的概念聚類方法[1]。基于語法相似的概念聚類主要是根據詞匯間的上下文，判斷其語法結構特征，將具有相似語法結構的概念進行聚類，如文獻[2]和文獻[3]分別改進了傳統的語法相似度聚類方法，在文獻[2]中，作者提出了一種可在大規模文本數據中識別少量生成概念文本的模型，而文獻[3]中將互信息與層次聚類相結合，采用自底向上的方式判斷概念間語法特征的相似性，進而實現了概念聚類。基于語義相似度的概念聚類是當前較為通用的一種方法，該方法利用WordNet等語義知識庫計算概念間的語義相似度(包括：語義距離、密度和深度等)，并將其融合到K-Means[4]或層次聚類[5]等不同的方法中，以實現概念的語義聚類。如：文獻[6,7]使用改進的具有優化聚類中心能力的K-Means方法，并基于設定的閾值進行概念聚類。且在文獻[8]中，作者重點考慮了概念在基于語義相似度聚類過程中出現的概念重疊問題，并提出利用圖熵理論進行聚類而摒棄了原有選取聚類質心的方法。文獻基于語用相似度的概念聚類不同于前者，其重點不在于概念本身的特點，而是關注于不同概念與某一對象的接近程度[9]。如：利用關鍵字搜索網頁資源[10]，獲得針對該網頁的關鍵字間的關聯關系。

上述方法均已在實踐中得到了良好的驗證，但都是從某一角度對概念聚類進行研究，仍缺少一種綜合考慮概念間語義關系和用戶偏好的方法，進一步提高聚類的應用效果。由于當前網絡資源等大量的涌現，人們對于本體中概念的查詢需求不再局限于領域專家所給出的同領域概念或基于語義知識庫的語義相似度計算獲得的具有較高關聯性的概念，而同時針對用戶偏好的查詢也有所需求。如用戶集U={u1,u2,…,ui,…,un} 和概念集C={c1,c2,…,ci,cj,…,cn}， 用戶u1,u2,…,ui等高頻次地同時查詢概念ci和cj，說明ci和cj間隱含著用戶的用戶查詢偏好。故，將此用戶偏好關系數值化并合理地用于補充原有的概念語義關系中，可對原有查詢聚類結果進行有益地補充，提高用戶查詢的查準率和查全率。所以，本文基于此問題，提出了支持用戶偏好查詢的領域概念圖模型，具體的創新點及步驟如下：①從多角度(語義距離、深度和密度及內容)計算概念間的語義相似度，并構建領域概念語義關系圖，實現各領域本體(如：醫藥學、農學、海洋科學及計算機科學技術學等領域)中不同概念間關系的重構(改進了原領域本體中概念關系僅從單一角度考慮的情況)；②利用改進的互信息方法挖掘UGD中隱含的不同概念間的用戶偏好關系值；③利用用戶針對概念的偏好關系補全步驟①中的語義關系圖，以獲得支持用戶偏好查詢的領域概念圖模型及本體，使得各領域的研究人員和用戶在查詢和分析不同領域概念時，能夠獲得更為準確和全面的概念數據。

1 概念間的語義相似度計算與語義關系圖的構建

目前，概念間的語義相似度的計算方法可以在概念間的語義距離[10]，WordNet中深度關系和密度關系[11]或重合度及內容相關度等[12]多個方面上實現。本文從多角度考慮概念ci和cj間的語義關系，并將上述方法的結果進行有效地融合，得到ci和cj間的綜合語義相似度，進一步提升結果的準確性。

基于語義距離的相似度計算：

D(ci,cj) 表示WordNet中ci和cj間的語義距離CS(ci,cj) 是ci和cj間的語義相似度，如式(1)計算所得

(1)

這里，a是ci和cj與WordNet中概念集合的平均語義距離。

基于深度的相似度關系計算：

令ci所在的語義樹的最大深度分別為Hmax(ci)， 且H(ci) 表示ci在樹中的深度，故，結合Hmax(ci) 和H(ci) 的概念ci和cj間相似度HS(ci,cj) 的計算公式如式(2)所示

(2)

基于密度的相似度關系計算：

令n(ci) 是ci對應的語義樹中，以ci為根節點的直接子節點數，nmax(T) 則表示ci對應的語義樹T中的所有非葉子節點的直接子節點數量的最大值。則ci和cj在WordNet中密度的語義相似度關系PS(ci,cj) 的計算方法，如式(3)所示

(3)

基于語義重合度的相似度關系計算：

若將從節點ci到根節點所經過的節點數記為S(ci)， 則基于語義重合度的ci和cj相似度SS(ci,cj) 的計算如式(4)所示

(4)

基于概念內容信息的相似度關系計算：

本文改進了文獻[12]中提出的利用概念信息內容計算概念相似度的方法，考慮到WordNet中概念子節點的空間結構對概念信息內容值的影響，給出式(5)，計算IS(ci,cj)， 其中I(c) 計算方式由文獻[12]而得

(5)

為了將上述的概念ci和cj間的語義距離、深度和密度關系以及語義重合度及內容信息方面的相關度進行有效合理的組合，本文使用加權的形式計算ci和cj間的綜合語義相似度。考慮到過多的參數設定對最終結果的影響，本文利用主成分分析方法[13,14]分析CS、HS、PS、SS和IS的貢獻率，進而動態地求解影響因子，克服了概念間語義相似度計算過多依賴WordNet的問題。

構建矩陣α=(xi1,xi2,xi3,xi4,xi5)T， 且i=1,2,3,4,5。 這里xi是由向量 (CS,HS,PS,SS,IS) 構成。基于主成分分析法將α等價轉化為一維矩陣γ=[x′1,x′2,x′3,x′4,x′5]， 即α的主成分表示，并同時計算矩陣的特征值，以獲取主成分貢獻率 (q1,q2,q3,q4,q5)， 最終得概念間相似度綜合計算公式為式(6)

KSIM(ci,cj)=q1x′1+q2x′2+q3x′3+q4x′4+q5x′5

(6)

將KSIM(ci,cj) 用于構建間的語義關系圖，如定義1和圖1所示。

圖1 領域概念語義關系

定義1 令領域概念語義關系圖GS=(V,E,η,θ1)，V表示概念集 {c1,c2,…,ci,cj,…,cn}， 表示E是概念節點間的邊的集合 {e12,e23,…,eij,…,emn}，eij=；η=KSIM(ci,cj) 是eij的權值，θ1是判斷語義關系的閾值，且當η>θ1時，概念ci與概念cj間存在邊eij。

2 基于互信息的用戶概念查詢偏好關系挖掘

互信息[15,16](具體定義及公式參見文獻[15,16])是度量不同實體間相關性的主要手段。

首先，本文使用互信息計算不同概念間可能隱含的針對用戶偏好的直接交互關系，如定義2所示。

定義2 對于概念集C中任意兩個概念ci和cj(i≠j)， 針對用戶的查詢偏好，ci和cj間的關聯關系如式(7)所示

(7)

式中：I(ci,cj) 表示基于用戶偏好的概念ci和cj間相關度，且I(ci,cj)∈[0,1]；P(ci) 表示用戶查詢ci的概率，P(ci,cj) 是ci和cj的聯合概率，使用如式(8)和式(9)求得

(8)

(9)

這里，F表示用戶查詢概念頻次總數，F(ci,cj) 是ci和cj同時被查詢頻次，F(ci) 表示概念ci的查詢頻次。

例2：如表1給出了用戶u在概念集C上的概念查詢的UGD記錄 {ui,cj}。 由表1可知，F=5， (c1,c2) 即ci和cj同時被查詢的次數為2，則F(c1,c2)=2，P(c1,c2)=0.4，I(c1,c2)=0.52， 所以c1和c2同時出現的頻次與二者的關聯性呈正相關。

表1 用戶的查詢概念記錄

進一步地，若用戶多次同時查詢ci和ck及cj和ck，而未同時查詢或很少同時查詢ci和cj，并不一定說明用戶對ci或cj的偏好程度較低(因為ci和cj均與ck有著密切的交互關系)，可能是很少有用戶同時熟知ci和cj，且這種情況較為普遍，所以挖掘隱含在用戶生成數據中的間接概念交互關系能進一步刻畫用戶查詢偏好。本文根據定義2獲得的I(ci,ck) 與I(ck,cj)， 計算ci和cj間可能存在間接交互關系，為此，本文給出如下定義3所示的計算方法。

定義3計算。若概念ci,ck和cj滿足上述概念間接交互關系，則I(ci,cj)=I(ci,ck)I(ck,cj)， 具體地

I(ci,cj)=I(ci,ck)I(ck,cj)=

(10)

當k不唯一，即k=1,2,…,n時，根據式(5)可知，I(ci,cj) 不唯一，此時本文綜合不同的I1(ci,cj)，I2(ci,cj)， …和In(ci,cj)， 利用運算獲得最終的I(ci,cj)， 如式(11)所示

I(ci,cj)=I1(ci,cj)I2(ci,cj)…In(ci,cj)

(11)

式中：兩個不同概念間的交互關系I(ci,cj) 與I(cj,ci) 是相等的，且I(ci,ck)I(ck,cj)=I(ck,cj)I(ci,ck)，I(ci,cj)∈[0,1]。

3 基于偏好查詢的語義關系圖補全

GS中缺失的邊表明對應節點ci和cj間的語義相似度較低(小于θ1)，所以在用戶查詢其中某個概念ci時，另一個概念cj應該不能作為相關聯概念出現，但這是從語義角度考慮的，如果進一步從語用和用戶查詢偏好角度考慮，如果用戶經常性地同時直接或間接地查詢ci和cj，即使二者語義相關度很低，但cj仍應該作為ci的相關概念，同時作為查詢結果。這一過程綜合了ci和cj的語用和語義關系，進一步滿足用戶查詢需求。本文將上述第1節和第2節中提出領域概念相似度計算方法與用戶偏好挖掘方法相結合，首先針對不同領域分別構建領域概念語義關系圖GS，其次從獲取得到的UGD中挖掘(訓練)出用戶在不同概念間的查詢偏好，并最終利用后者得到的概念間隱含的用戶偏好關系補全GS以獲得支持用戶偏好查詢的概念語義關系圖GK，用于不同領域中本體的構建以及概念查詢。具體地，如算法1所示。

算法1： 基于UGD的領域概念語義關系圖補全算法

Input：D： 用戶生成數據集UGD片段；GS； 交互關系閾值θ2

Output： 支持偏好查詢的領域概念圖GK

(1)For eachciinGSdo

For eachcjinGSdo

利用由式(7)計算I(ci,cj); 構建鄰接概念；

Ifeij?E∩I(ci,cj)>θ2

補全eij;

Else

Continue;

End For

End For

(2)For eachciinGSdo

構建ci的鄰居節點集Si；

For eachcjinGSdo

IfSi∩Sj≠?

構建ci和cj的共同鄰居節點集，←Si∩Sj;

構建三元組(ci,cj,ck)←{ci}∩{cj}∩{ck∈}

Else

Continue;

End For

End For

(3)For each (ci,cj,ck) do

利用式(10)和式(11)計算I(ci,cj);

IfI(ci,cj)>θ2

補全eij;

Else

Continue;

End For

(4)GK←GS;

(5)ReturnGK;

算法1旨在利用用戶查詢的生成數據補全概念本身的語義相似度構建的關系圖GS。其中，主要時間消耗是在步驟(1)和步驟(2)，對于GS中含有n個概念節點，進行GS中缺失邊的直接補全(對應上文的概念間直接交互關系的處理)的時間復雜度為O(n2)(步驟(1))，遍歷GS中各個節點并構建其鄰居節點的時間消耗可以認為也是O(n2)(步驟(2))，而步驟(3)進行GS中缺失邊的間接補全(對應上文的概念間間接交互關系的處理)的時間復雜度為O(m2)(m?n)，所以算法1的最終時間復雜度是O(n2)。最后對圖1進行了更新的結構如圖2所示。

圖2 支持用戶查偏好的領域概念語義關系

4 實驗與分析

本文的實驗過程是在Windows 10，內存8 GB，2.5 GHz的PC機上進行的，主要使用Microsoft.NET framework和SQL Server 2012 database搭建平臺。本文的實驗數據選取由全國科學技術名詞審定委員會審定公布的領域概念集合作為實驗數據集(http：//www.cnctst.cn/)，我們挑選其中24個領域中概念各500，并分配給100個用戶，收集他們在一個月內查詢記錄(UGD)共96 743條。

實驗1：本文提出模型中的參數有閾值θ1和θ2，而閾值的設置直接影響本文模型的性能，所以文中首先利用數據集進行參數的設置。將數據集中的60%作為訓練集，剩余40%用于測試，結果見表2。由表中結果可知，隨著閾值的增大，模型在支持用戶查詢的正確率在降低，同時消耗的時間代價也在減少，這是因為閾值較小時，構建圖模型時對于概念間的關聯關系過濾性較弱，圖的連通性較強，進而用戶的查詢結構更多地包含了滿足其要求的概念；但同時模型中的概念節點間的邊結構復雜，查詢時所花費的遍歷時間代價相對較高。具體地，當閾值θ1,θ2≤0.6時，模型的正確率變化并不明顯，而時間消耗卻有明顯變化，當θ1,θ2>0.6時，模型正確率開始明顯地下降。說明θ1,θ2在0.6附近可使本文模型獲得最優的性能表現，最終，本文設置θ1=0.55，θ2=0.6，此時正確率為0.794，消耗時間897 ms。

表2 不同閾值情況下的GK模型的性能表現

實驗2：本文根據設定的閾值，以及訓練出的GK模型，與現有的相關算法[3,8,10]進行對比，目的是能夠在其基礎上進一步提升查準率(precision)和查全率(recall)以及F-值，并使用文獻[8]中的公式進行計算，如式(12)～式(14)所示。為了在實驗過程中驗證本文方法與其它方在支持多用戶查詢時的數據處理能力，本文將數據集分為不等的4組，分別是測試數據總數據量的10%、20%、30%和40%，并依次進行實驗。對比方法中涉及到的參數均盡可能與其原文保持一致。查詢過程中，本文依據三度影響力理論[17]，只查詢路徑長度小于等于3的路徑上的相關概念(因為路徑長度大于3的概念間盡管連通，但是關聯性很弱)，具體對比結果如表3、表4及圖3所示

(12)

(13)

(14)

這里，N是用戶滿足用戶需求的概念個數，M為用戶查詢獲得的概念個數；A表示概念集C當中所有滿足用戶查詢需求的概念。

通過上述的實驗結果不難發現，本文的方法整體上要優于其它3種方法。整體看來，隨著實驗數據的增加，4種方法的性能均受到了影響，但具體地，本文模型在precision方面，本文方法較文獻[8]中的方法依次提高了1.53%、

表3 precision結果對比

表4 recall結果對比

圖3 F-值對比

2.76%、6.03%及9.52%；在recall方面，較文獻[8]在4組實驗中分別提高了1.10%、3.31%、8.19%及10.89%。分析發現，由于數據的增加，其中包含了多個用戶查詢大量領域概念，文獻[3,8,10]中的方法分別是基于語法、語義和語用角度來考量與用戶查詢概念相關的領域概念，而本文方法則在此基礎上考慮了用戶查詢偏好，能夠進一步補充用戶的查詢需求，所以用戶偏好的挖掘在查詢過程中起到了積極的作用。

實驗3：考慮到支持用戶查詢的響應時間是反映模型性能的重要評價指標，本文利用實驗2中的數據，對4種方法處理數據的響應時間進行對比，結果如圖4所示。由圖4發現，隨著數據量增加，該4種方法的響應時間均是趨于上升，其中文獻[8,10]中的方法響應時間增長比例較大，而文獻[3]和本文方法的增長比例相對較小，且隨著數據量加大，本文方法優勢更加明顯。原因在于本文提出的方法主要的時間消耗是在構建GK部分，且構建構成是在線下完成的，所以對于線上的查詢過程消耗的時間主要花費在利用已有模型進行基于規則的遍歷，而另外3種方法的時間消耗主要集中在線上的概念查詢(聚類)過程中。

圖4 響應時間對比

實驗4：為驗證本文的可拓展性，本文分別使用數據集的20%、40%、60%以及80%作為訓練集，以驗證在不同訓練集下的GK模型的性能，結果如圖5～圖7所示。GK模型在使用較低數量的訓練集構建時，其性能較低，而隨著訓練數據集達到40%甚至60%時，GK模型的性能明顯提高，且在訓練集在50%～60%間，GK模型性能達到最優，當訓練集超過60%時，其性能開始下降。分析發現，由于較低的訓練集致使構建的GK模型連通性較弱，使得遍歷查詢達不到預期效果，隨著訓練集增加，GK模型中概念節點間的關聯關系不斷建立，其連通性較強；但不斷增加訓練集，會導致GK中的概念間的關系(邊)出現冗余的情況，使得性能降低。

圖5 不同訓練集下的precision值

圖6 不同訓練集下的recall值

圖7 不同訓練集下的F-值

5 結束語

本文主要針對現有概念查詢聚類方法中未考慮用戶查詢偏好的問題，提出了一種支持用戶偏好查詢的領域概念圖模型，全面考慮了概念的語義關系和語用關系在用戶查詢領域概念過程中的作用，將概念的語義和語用相結合，改進現有的概念語義相似度計算方法，利用綜合語義相似度計算方法計算不同概念間的語義關系，并構建對應的關系圖；針對用戶生成數據，分別考慮概念間的直接交互關系和間接交互關系，使用改進的互信息計算方法挖掘UGD中隱含的用戶偏好，并提出了一個基于UGD的領域概念語義關系圖補全算法，實現GS的補全，獲得GK。最后，本文從多個角度對GK模型進行實驗，包括參數影響、precision、recall以及F-值，響應時間以及可拓展性，驗證了本文方法整體上優于目前流行的概念聚類方法。因為訓練集過大而造成的概念語義關系圖中冗余的無用邊過多，影響了模型的整體性能，所以下一步工作將專注于消除關系圖中冗余邊的研究。