全局分析和本體技術(shù)相結(jié)合的查詢擴展算法

創(chuàng)新者：張 磊

全局分析和本體技術(shù)相結(jié)合的查詢擴展算法

創(chuàng)新者：張 磊

查詢擴展可以彌補用戶初始查詢請求語義信息不明晰的缺陷，提高搜索性能。首先，對用戶查詢模式進行分析，根據(jù)查詢模式的不同特點給出相應(yīng)的查詢擴展方法與策略，然后，提出一種全局分析和本體技術(shù)相結(jié)合的查詢擴展算法，有效解決各類查詢模式的查詢擴展問題。仿真實驗的結(jié)果表明，該算法的綜合性能比全局分析的查詢擴展算法的綜合性能提高了12.9％，比基于本體技術(shù)的查詢擴展算法的綜合性能提高了9.8％。

研究發(fā)現(xiàn)，兩個人使用相同詞匯描述同一事物的概率小于20％。必須對用戶查詢請求進行改進處理，以提高檢索性能。查詢擴展QE（Query Expansion）是在初始查詢的基礎(chǔ)上加入與用戶檢索詞相關(guān)聯(lián)的新詞，生成更準(zhǔn)確的查詢請求，彌補用戶查詢信息不足的缺陷，改善信息檢索的性能。查詢擴展對短查詢尤為有效，因為查詢越短，查詢本身表達的信息就越模糊。常用的查詢擴展技術(shù)有全局分析、局部分析、基于關(guān)聯(lián)規(guī)則的方法以及基于本體的方法等。

全局分析對全部文檔中的詞或詞組進行相關(guān)分析，計算每對詞或詞組間的關(guān)聯(lián)程度，將詞或詞組按共同發(fā)生的頻率先行聚類，其后根據(jù)詞或詞組的不同集合對查詢進行擴展。全局分析需要對整個文獻集進行處理，過程復(fù)雜，計算量大。局部分析較好地解決了全局分析的缺陷。局部分析利用初次檢索得到的與查詢最相關(guān)的top-k篇文章作為擴展用詞的來源，而非全部文檔。常用的局部分析技術(shù)有局部聚類、用戶相關(guān)反饋（如用戶日志、歷史查詢信息等）和局部上下文分析等。局部分析依賴初次檢索文檔的質(zhì)量，當(dāng)初檢文檔與原查詢相關(guān)度不高時，會把大量無關(guān)詞加入到查詢中，降低查詢性能。

基于關(guān)聯(lián)規(guī)則的查詢擴展則是通過數(shù)據(jù)挖掘技術(shù)挖掘詞間關(guān)聯(lián)規(guī)則，將關(guān)聯(lián)規(guī)則的結(jié)論作為擴展用詞的來源。該方法雖然在一定程度上克服了全局分析和局部分析的不足，但是查詢擴展的效果受詞間關(guān)聯(lián)規(guī)則質(zhì)量影響較大。

基于本體的查詢擴展利用本體中的同義詞和特定的子類進行擴展，收到了很好的效果。查詢擴展中常用的本體有兩類，一類是通用的詞匯本體，如WordNet、HowNet等。這類本體在各個領(lǐng)域廣泛使用，缺乏專業(yè)領(lǐng)域的詞匯間的語義聯(lián)系，擴展性能不穩(wěn)定；另一類是領(lǐng)域本體，這類本體針對特定領(lǐng)域，本體概念所表達的語義信息明確，對該領(lǐng)域內(nèi)的查詢請求進行語義擴展非常有效。

全局分析、局部分析和基于關(guān)聯(lián)規(guī)則的查詢擴展在關(guān)鍵詞匹配層次上進行的查詢擴展，難以充分表達和擴展用戶查詢的語義信息，不能從根本上消除用戶查詢意圖與檢索結(jié)果之間的語義偏差問題。基于本體的查詢擴展忽略了用戶查詢關(guān)鍵詞存在多樣性，查詢詞匯可能位于本體之外這一事實，假設(shè)查詢詞匯都來源于本體。一旦假設(shè)不成理，如何找到與查詢詞匯語義相關(guān)的本體概念就變得非常關(guān)鍵。

本文首先對用戶查詢模式進行分析，針對不同查詢模式的特點給出不同的查詢擴展方法與策略，然后提出一種全局分析和本體技術(shù)相結(jié)合的查詢擴展方法，該方法在兼顧二者優(yōu)點的同時避開各自的缺點。

用戶查詢模式分析

分析發(fā)現(xiàn)，用戶查詢請求往往遵循一些典型模式。針對查詢模式的不同特點，可以采用不同的方法進行擴展處理。

（1）C模式查詢

C模式即概念詞匯模式（Concept Word Model）。此模式的查詢詞匯由本體概念組成，能夠根據(jù)本體概念判斷查詢語義，獲知用戶查詢意圖。在此模式下，可以利用本體概念中的父子和同義等關(guān)系進行擴展，準(zhǔn)確表達用戶的查詢目的，提高搜索性能。本文對C模式查詢采用三種擴展方式，即同義替換、概念泛化和概念細(xì)化。

1）同義替換。本體概念的同義關(guān)系表示概念表達的語義信息相同，可以替換使用。這種利用概念間的同義關(guān)系進行擴展的方式叫同義替換。比如，用戶輸入了“計算機”這一本體概念，可以將具有同義關(guān)系的“電腦”概念作為語義擴展的目標(biāo)。

2）概念泛化。本體中的某些概念可能同時出現(xiàn)在多個概念分支下面。比如，ACM本體（http：∥www.acm. org/about/class/1998）中，“Fault Tolerance”位于“B.1 Microprogramming”、“B.4 Data Communication”和“D.4 Operating System”等多個概念分支下面。概念泛化的基本思想是確定概念所屬分支，將分支上的父概念和概念本身組合起來表達查詢的具體語義。比如，將“Fault Tolerance”與其父概念“B.1 Microprogramming”組合起來后，表達的語義比單個“Fault Tolerance”更為精確。概念泛化可以通過自然語言理解及上下文分析等技術(shù)實現(xiàn)，也可以通過用戶交互實現(xiàn)。

3）概念細(xì)化。概念細(xì)化的基本思想是將子概念與概念本身組合起來表達查詢的具體語義。比如，概念“C.2.3 Network Operations”分支下面有子概念“NetworkManagement”和“Network Monitoring”。將“C.2.3 Network Operations”與其子概念“Network Management”或“Network Monitoring”組合起來后，表達的語義比單個“C.2.3 Network Operations”更為精確。在概念細(xì)化過程中，可以將分支上的全部子概念作為細(xì)化對象，也可以通過用戶交互選擇其中某一個或幾個子概念作為細(xì)化對象。

（2）O模式查詢

O模式即普通詞匯模式（Ordinary Word Model）。此模式的查詢詞匯非本體概念，而是位于本體之外的普通單詞。該模式無法借助本體技術(shù)進行擴展，只能使用全局分析或局部分析等擴展技術(shù)。為了避免局部分析中的二次搜索，本文選擇全局分析進行O模式查詢擴展。

統(tǒng)計發(fā)現(xiàn)，普通詞匯和特定的本體概念間往往有很強的相關(guān)性。比如，“QoS”詞頻比較高的文檔資源一般和本體概念“Network Measure”有關(guān)。如果借助全局分析技術(shù)計算普通詞語和本體概念間的相關(guān)性，就可以根據(jù)計算結(jié)果選擇合適的本體概念作為擴展的目標(biāo)。在O模式查詢擴展中，詞語-概念相關(guān)度計算是進行語義擴展的關(guān)鍵環(huán)節(jié)。

（3）混合模式查詢

混合模式查詢指查詢詞匯中同時包含C模式詞匯和O模式詞匯。此模式的查詢詞匯既有本體概念，又有位于本體之外的普通單詞。對于本體概念，采用C模式處理方法進行擴展；對于普通詞匯，則按照O模式處理方法進行擴展。

詞語-概念相關(guān)度計算

隨著語義Web和本體技術(shù)的發(fā)展，人們借助本體為越來越多的文檔資源添加語義信息，把資源標(biāo)注到1個或者多個本體概念下作為概念實例是最常見的操作。此時，文檔資源到概念間存在所屬關(guān)系，文檔資源中的詞語到概念也存在所屬關(guān)系，這種所屬關(guān)系蘊涵著詞語-概念的相關(guān)關(guān)系。

如圖1所示，一個詞語可能存在于多個文檔中，而每個文檔又屬于1個或多個概念類。詞語與概念通過文檔建立聯(lián)系，可以利用詞匯與概念間的共現(xiàn)性計算詞匯-概念相關(guān)度。通過統(tǒng)計包含詞語的文檔資源所屬的概念，就可以統(tǒng)計出這個詞語對不同概念的所屬程度，即是詞語-概念相關(guān)度。

詞語-概念相關(guān)度計算應(yīng)滿足下面3個基本準(zhǔn)則。

（1）一個詞語通過文檔資源映射到的本體概念的個數(shù)越多，它對單個概念的相關(guān)度越低。

（2）一個詞語在某一概念對應(yīng)文檔資源中的詞頻越高，它對這個概念的相關(guān)度越高。

（3）一個詞語在某一個概念對應(yīng)的越多文檔資源中存在，它對這個概念的相關(guān)度越高。

準(zhǔn)則1是從詞語在概念空間中的分布情況來分析。一個詞語與越多的概念關(guān)聯(lián)，它對概念的區(qū)分性就越不明顯，它與概念的相關(guān)度也就越低。

準(zhǔn)則2是從詞語在一個概念對應(yīng)的文檔資源中出現(xiàn)的頻率來分析。選擇詞頻作為統(tǒng)計量而不選擇文檔資源數(shù)量作為統(tǒng)計量，原因在于前者屬于細(xì)粒度，區(qū)分性強，可以更準(zhǔn)確地刻畫詞語對概念的相關(guān)度。

圖1　詞語-文檔-概念關(guān)系

準(zhǔn)則3是從詞語在一個概念對應(yīng)的文檔資源中的分布情況來分析。詞語在一個概念對應(yīng)的越多文檔資源中出現(xiàn)，說明它在這個概念中分布的越均勻，它與概念的所屬關(guān)系被越多的文檔承認(rèn)，因而它與這個概念的相關(guān)度也就越高。

本文基于上述3個基本準(zhǔn)則，并借鑒文獻中的部分思想，給出詞語-概念相關(guān)度計算公式。

定義1. 假設(shè)文檔資源集為D ，共有m 個文檔資源，dj（j=1，...，m）表示第j 個文檔資源；本體概念集為C ，共有n 個概念，ci（i=1，...，n）表示第i 個概念，詞語集為T ，共有p 個詞匯，tk（i =1，...，p）表示第k 個詞匯。詞語tk和概念ci的相關(guān)度為

式（1）中，nk表示tk根據(jù)文檔-概念關(guān)系映射到概念上的概念數(shù)目，numi表示概念ci對應(yīng)的文檔數(shù)目，numk，i表示概念ci對應(yīng)的文檔資源中出現(xiàn)詞語tk的文檔數(shù)目，表示詞語tk通過文檔映射到概念ci的詞頻統(tǒng)計量。

式（2）中，Di表示概念ci對應(yīng)的文檔集合，即Di=｛dj|dj∈D∧dj是ci的 實例｝，count （tk，dj）表示詞語tk在文檔資源dj中出現(xiàn)的次數(shù)，len（dj）表示dj的長度。

利用公式（1）可以計算詞語和本體概念間的語義相關(guān)度，從而構(gòu)建詞語-概念相關(guān)度詞典（Association Thesaurus），用于語義查詢擴展。

查詢擴展算法

算法1. 全局分析和本體技術(shù)相結(jié)合的查詢擴展算法

輸入：查詢請求Q（q1，q2，…，ql）

輸出：擴展后的查詢請求Q′

算法描述：

1.Q′=Q ；

2.Q查詢模式分析；

3.IFQ 為混合模式

圖2　查詢擴展算法流程圖

4.查詢請求Q 分組為Q1和Q2；//Q1為C模式詞匯，Q2為O模式詞匯

5.For Each qiIn Q1

6.C模式查詢擴展；

7.End For；

8.For Each qiIn Q2

9.O模式查詢擴展；

10.End For；

11.ELSE

12.IF Q為C模式

13.For EachqiIn Q

14.C模式查詢擴展；

15.End For；

16.End IF

17.IF Q為O模式

18.For EachqiIn Q

19.O模式查詢擴展；

20.End For；

21.End IF

22.End IF

23.擴展結(jié)果合并；

24. 返回擴展后的查詢請求Q′。

全局分析和本體技術(shù)相結(jié)合的查詢擴展算法流程如圖2所示。

仿真實驗

本節(jié)通過仿真實驗分析查詢擴展算法的性能。本體采用計算機科學(xué)領(lǐng)域的領(lǐng)域本體ACM。文檔資源從ACM數(shù)據(jù)庫下載（http：//porta.acm.org/portal.cfm），資源規(guī)模為19030。本文對比三種不同查詢擴展算法的性能：基于全局分析的查詢擴展算法、基于本體技術(shù)的查詢擴展算法、全局分析和本體技術(shù)相結(jié)合的查詢擴展算法。三種查詢擴展算法分別簡稱為：全局分析、本體技術(shù)、全局分析+本體技術(shù)。

在信息檢索領(lǐng)域，查準(zhǔn)率（precision ）、查全率（recall ）和F值是評價系統(tǒng)性能的主要指標(biāo)。查全率為搜索結(jié)果中符合查詢條件的資源數(shù)量占總符合查詢條件資源數(shù)量的比例。查準(zhǔn)率為搜索結(jié)果中符合查詢條件的資源數(shù)量占返回資源數(shù)量的比例。F 值為查全率和查準(zhǔn)率的加權(quán)幾何平均。F值將查全率和查準(zhǔn)率結(jié)合在一起進行評價，防止出現(xiàn)查準(zhǔn)率很高而查全率很低或者查全率很高而查準(zhǔn)率很低的現(xiàn)象。F值反映系統(tǒng)的綜合性能，該值越接近1越好。

搜索性能評價指標(biāo)的計算公式分別為：

式（3）和（4）中，resourcerelevant為符合查詢條件的總資源數(shù)量，resourceretrieval為返回資源數(shù)量，resourcerelevant∩resourceretrieval為返回結(jié)果中符合查詢條件的資源數(shù)量。

仿真實驗共發(fā)起了20次查詢請求，其中C模式查詢請求4次，O模式查詢請求4次，混合模式查詢請求12次，概念泛化和概念細(xì)化的層數(shù)均設(shè)定為1層。圖3顯示了上述三種算法20次查詢請求的查全率，查詢編號1至4為C模式查詢請求，5至8為O模式查詢請求，9至20為混合模式查詢請求。從圖3可以看出：前4個請求為C模式詞匯，可借助本體進行查詢擴展，本體技術(shù)的查全率明顯優(yōu)于全局分析的查全率。由于請求不包含O模式詞匯，此時全局分析+本體技術(shù)的性能無法充分體現(xiàn)，查全率和本體技術(shù)的查全率持平；5至8為O模式查詢詞匯，無法借助本體進行查詢擴展，全局分析的查全率明顯優(yōu)于本體技術(shù)的查全率。由于請求不包含C模式詞匯，此時全局分析+本體技術(shù)的性能無法充分體現(xiàn)，查全率和全局分析的查全率持平；9至20為混合模式查詢詞匯，全局分析與本體技術(shù)各有優(yōu)勢，查全率基本持平，本體技術(shù)的查全率略高于全局分析的查全率。混合模式查詢請求能充分發(fā)揮全局分析+本體技術(shù)的性能，因此查全率明顯提高。在實際應(yīng)用中，大多數(shù)搜索請求都為混合模式查詢。

圖3　三種算法的查全率

圖4　三種算法的查準(zhǔn)率

圖5 三種算法的F值

圖4顯示了上述三種算法20次查詢請求的查準(zhǔn)率。從圖4可以看出，三種算法的查準(zhǔn)率性能表現(xiàn)與圖3的查全率性能表現(xiàn)基本一致。全局分析+本體技術(shù)的查準(zhǔn)率最高，另外兩種算法次之。單獨比較全局分析和本體技術(shù)兩種算法發(fā)現(xiàn)：由于本體在精確語義表達方面的優(yōu)勢，使得無論是C模式查詢，還是混合模式查詢，本體技術(shù)的查準(zhǔn)率都優(yōu)于全局分析的查準(zhǔn)率，而且差距比較明顯。

圖5顯示了上述三種算法20次查詢請求的F值。全局分析和本體技術(shù)相結(jié)合的查詢擴展算法在兼顧二者優(yōu)點的同時避開各自的缺點，因此全局分析+查詢擴展的綜合性能最好，比只采用全局分析的綜合性能提高了12.9％，比只采用本體技術(shù)的綜合性能提高了9.8％。

然后，再通過仿真實驗分析概念泛化和概念細(xì)化的層數(shù)對本文提出的查詢擴展性能的影響。將概念泛化和概念細(xì)化的層數(shù)分別設(shè)定為0、1、2、3、4，考察基于全局分析和本體技術(shù)的查詢擴展算法的F值，結(jié)果如圖6所示。0層表示不進行概念泛化或概念細(xì)化。從圖6可以看出，進行1層、2層的概念細(xì)化和概念泛化可以明顯提高查詢擴展的性能，但是當(dāng)概念泛化或概念細(xì)化的層數(shù)過多（大于2層），查詢擴展的性能不但不會提高，反而下降，并且概念泛化的性能受層數(shù)影響較概念細(xì)化明顯。主要原因是當(dāng)概念泛化或概念細(xì)化的層數(shù)過多后，擴展出的概念與原始查詢詞匯的語義差距明顯增大，概念泛化尤為明顯。因此，在進行概念泛化，以1層為最佳，在進行概念細(xì)化時，最佳層數(shù)為1～2層。

圖6　概念泛化和概念細(xì)化層數(shù)對查詢擴展性能影響

結(jié)語

查詢擴展可以生成更準(zhǔn)確的查詢請求，彌補用戶查詢信息不足的缺陷，提高搜索性能。用戶查詢請求往往遵循一些典型模式。本文首先對用戶查詢模式進行分析，根據(jù)查詢模式的不同特點給出相應(yīng)的查詢擴展方法與策略，在此基礎(chǔ)上，提出一種全局分析和本體技術(shù)相結(jié)合的查詢擴展算法，該算法在兼顧二者優(yōu)點的同時避開各自的缺點。仿真實驗的結(jié)果表明，該算法的綜合性能比全局分析的查詢擴展算法的綜合性能提高了12.9％，比基于本體技術(shù)的查詢擴展算法的綜合性能提高了9.8％。

全局分析和本體技術(shù)相結(jié)合的查詢擴展算法的性能受多種因素影響。這些因素包括：（1）本體自身的合理性與完備性；（2）詞匯-概念詞典的準(zhǔn)確度；（3）和用戶交互過程中所獲得信息的有效性。下一步將從這些影響因素入手，進一步提高全局分析和本體技術(shù)相結(jié)合的查詢擴展算法的性能。

10.3969/j.issn.1001-8972.2015.09.024