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

創(chuàng)新者：張 磊

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

創(chuàng)新者：張 磊

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

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

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

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

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

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

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

用戶查詢模式分析

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

（1）C模式查詢

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

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

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

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

（2）O模式查詢

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

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

（3）混合模式查詢

混合模式查詢指查詢?cè)~匯中同時(shí)包含C模式詞匯和O模式詞匯。此模式的查詢?cè)~匯既有本體概念，又有位于本體之外的普通單詞。對(duì)于本體概念，采用C模式處理方法進(jìn)行擴(kuò)展；對(duì)于普通詞匯，則按照O模式處理方法進(jìn)行擴(kuò)展。

詞語(yǔ)-概念相關(guān)度計(jì)算

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

查詢擴(kuò)展算法

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

輸入：查詢請(qǐng)求Q（q1，q2，…，ql）

輸出：擴(kuò)展后的查詢請(qǐng)求Q′

算法描述：

1.Q′=Q ；

2.Q查詢模式分析；

3.IFQ 為混合模式

圖2　查詢擴(kuò)展算法流程圖

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

5.For Each qiIn Q1

6.C模式查詢擴(kuò)展；

7.End For；

8.For Each qiIn Q2

9.O模式查詢擴(kuò)展；

10.End For；

11.ELSE

12.IF Q為C模式

13.For EachqiIn Q

14.C模式查詢擴(kuò)展；

15.End For；

16.End IF

17.IF Q為O模式

18.For EachqiIn Q

19.O模式查詢擴(kuò)展；

20.End For；

21.End IF

22.End IF

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

24. 返回?cái)U(kuò)展后的查詢請(qǐng)求Q′。

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

仿真實(shí)驗(yàn)

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

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

搜索性能評(píng)價(jià)指標(biāo)的計(jì)算公式分別為：

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

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

圖3　三種算法的查全率

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

圖5 三種算法的F值

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

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

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

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

結(jié)語(yǔ)

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

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

10.3969/j.issn.1001-8972.2015.09.024