基于權(quán)重標(biāo)準(zhǔn)化SimRank方法的查詢擴(kuò)展技術(shù)研究

馬云龍，林 原，林鴻飛

(大連理工大學(xué) 信息檢索研究室，遼寧 大連 116024)

1 引言

當(dāng)前，通用搜索引擎主要是通過(guò)查詢關(guān)鍵詞匹配的方法進(jìn)行檢索。其存在的不足是： 用戶進(jìn)行檢索時(shí)輸入的有限詞語(yǔ)往往不能準(zhǔn)確且完全地表達(dá)其檢索的真正意圖，進(jìn)而導(dǎo)致搜索引擎返回大量的不相關(guān)文檔。為此，需要找到一種有效的方法對(duì)用戶輸入的查詢進(jìn)行糾正及補(bǔ)充，即查詢擴(kuò)展技術(shù)。

查詢擴(kuò)展過(guò)程需要從特定的語(yǔ)料資源中挖掘各詞項(xiàng)與原始查詢之間的某種關(guān)聯(lián)屬性，進(jìn)而選擇較好的詞項(xiàng)作為擴(kuò)展詞。查詢擴(kuò)展技術(shù)的兩個(gè)關(guān)鍵之處在于擴(kuò)展資源的選取以及詞項(xiàng)間關(guān)聯(lián)屬性的挖掘。在擴(kuò)展詞資源方面，大規(guī)模真實(shí)的搜索引擎日志通常包含了用戶的原始查詢、瀏覽頁(yè)面、點(diǎn)擊鏈接以及對(duì)應(yīng)的時(shí)間等非常豐富且有價(jià)值的信息，作為擴(kuò)展資源，其質(zhì)量相比于傳統(tǒng)的偽相關(guān)文檔更具有優(yōu)勢(shì)。同時(shí)，在真實(shí)的搜索引擎日志中，也包含了大量的噪聲數(shù)據(jù)，因此，需要有效地挖掘詞項(xiàng)關(guān)聯(lián)屬性以求更好地篩選出與原始查詢相關(guān)的擴(kuò)展詞項(xiàng)。本文采用基于圖結(jié)構(gòu)的相似度算法SimRank應(yīng)用于適當(dāng)?shù)脑~項(xiàng)關(guān)系圖上，全面有效地挖掘詞項(xiàng)間的相似度及語(yǔ)義關(guān)聯(lián)，從而減少噪音影響，提高篩選質(zhì)量。

本文后續(xù)內(nèi)容將按如下方式組織： 第2節(jié)介紹基于搜索引擎日志及加權(quán)SimRank方法的查詢擴(kuò)展技術(shù)研究的相關(guān)工作；第3節(jié)說(shuō)明查詢點(diǎn)擊圖與詞項(xiàng)關(guān)系圖的構(gòu)造和處理方法；第4節(jié)闡述權(quán)重標(biāo)準(zhǔn)化SimRank算法及其優(yōu)化方法；第5節(jié)展示實(shí)驗(yàn)設(shè)計(jì)、結(jié)果及分析；最后，本文在第6節(jié)進(jìn)行總結(jié)。

2 相關(guān)工作

查詢擴(kuò)展技術(shù)早在 20 世紀(jì) 70 年代就已經(jīng)被提出，作為解決表達(dá)差異的一種有效方法，能在一定程度上彌補(bǔ)用戶表達(dá)與相關(guān)文檔之間的差別，提高檢索效果。 按照用戶交互方式的不同可將其分為顯式反饋和隱式反饋兩種。顯式反饋以相關(guān)反饋(relevance feedback)方法為主[1]，指用戶主動(dòng)向系統(tǒng)提供自己的興趣偏好或?qū)ο到y(tǒng)返回的結(jié)果進(jìn)行相關(guān)性評(píng)價(jià)，系統(tǒng)根據(jù)這些反饋生成新的查詢。隱式反饋的查詢擴(kuò)展方法基本上可以分為全局分析、局部分析[1]和外部數(shù)據(jù)分析[2-3]三大類。全局分析是較早出現(xiàn)的具有實(shí)際應(yīng)用價(jià)值的查詢擴(kuò)展方法，其基本思想是對(duì)全部文檔中的詞項(xiàng)進(jìn)行相關(guān)性分析，計(jì)算每對(duì)詞項(xiàng)間的關(guān)聯(lián)程度。當(dāng)需要查詢擴(kuò)展時(shí)，根據(jù)預(yù)先計(jì)算的相關(guān)關(guān)系，將與原查詢用詞關(guān)聯(lián)程度最高的詞項(xiàng)加入原查詢以生成新的查詢，常見的方法包括 LSI(Latent Semantic Indexing)、LDA(Latent Dirichlet Allocation)和相似性詞典等。目前流行的局部分析方法主要是偽相關(guān)反饋(Pseudo Relevance Feedback)，它是在相關(guān)反饋的基礎(chǔ)上發(fā)展起來(lái)的，其基本思想是利用初次檢索得到的與原查詢最相關(guān)的 N篇文章(偽相關(guān)文檔集)作為擴(kuò)展詞項(xiàng)的來(lái)源。隱式反饋方式的查詢擴(kuò)展方法通過(guò)分析用戶與系統(tǒng)正常的交互行為來(lái)推測(cè)用戶檢索意圖，不需用戶做額外的相關(guān)性評(píng)價(jià)。由于通常情況下用戶不愿花費(fèi)額外的精力進(jìn)行主動(dòng)反饋，所以隱式反饋方式逐漸成為查詢擴(kuò)展技術(shù)研究中的重點(diǎn)。

近些年，隨著一些商業(yè)通用搜索引擎的部分查詢?nèi)罩颈还_，對(duì)查詢?nèi)罩镜难芯抗ぷ鞅淮笠?guī)模地展開。一種普遍的觀點(diǎn)認(rèn)為，在現(xiàn)實(shí)中用戶與搜索引擎的交互，并不僅僅是搜索引擎向用戶提供合適信息的過(guò)程，與此同時(shí)用戶在點(diǎn)擊相應(yīng)頁(yè)面鏈接的過(guò)程中也對(duì)搜索結(jié)果進(jìn)行了高質(zhì)量的相關(guān)性反饋，這些內(nèi)容都以搜索引擎日志(Query Logs)的形式被記錄和保存，其中包含了用戶的原始查詢、瀏覽頁(yè)面、點(diǎn)擊鏈接以及對(duì)應(yīng)的時(shí)間等非常豐富且有價(jià)值的信息[4]。有一部分學(xué)者在偽相關(guān)反饋的基礎(chǔ)上對(duì)查詢擴(kuò)展方法進(jìn)行了改進(jìn)，使其能夠利用查詢?nèi)罩局械男畔⑼诰蚝线m的擴(kuò)展詞項(xiàng)[2，4]。而更多的研究則關(guān)注于通過(guò)對(duì)查詢?nèi)罩镜姆治鰜?lái)優(yōu)化查詢推薦[5-7]，其中文獻(xiàn)[6]的方法利用了查詢點(diǎn)擊圖(Query-Click Graph)，文獻(xiàn)[5]和[7]的方法利用了查詢遷移圖(Query-Flow Graph)。

3 查詢點(diǎn)擊圖與詞項(xiàng)關(guān)系圖

3.1 查詢點(diǎn)擊圖

查詢點(diǎn)擊圖又被稱為查詢文檔圖[4]，記為GQC={VQC,EQC}。它是一個(gè)加權(quán)有向二部圖，對(duì)于給定的查詢集合Q以及地址集合U，其節(jié)點(diǎn)集合VQC={vq,vu}=Q∩U，即一部分節(jié)點(diǎn)表示不同的查詢，另一部分節(jié)點(diǎn)表示用戶所點(diǎn)擊的不同地址(URL)。邊集合為EQC={equ}?Q×U，即每一條邊equ均由某一查詢節(jié)點(diǎn)出發(fā)到某一地址節(jié)點(diǎn)結(jié)束，表示用戶鍵入該查詢進(jìn)行檢索并在搜索引擎返回的結(jié)果列表中點(diǎn)擊了相應(yīng)的地址。邊權(quán)重ω(equ)記錄了相應(yīng)查詢和地址對(duì)在查詢?nèi)罩局械墓铂F(xiàn)次數(shù)，一定程度反映了特定節(jié)點(diǎn)對(duì)的關(guān)聯(lián)程度。

具體地，查詢點(diǎn)擊圖通過(guò)以下步驟進(jìn)行構(gòu)造：

(1) 對(duì)搜索引擎查詢?nèi)罩具M(jìn)行去噪處理和詞項(xiàng)過(guò)濾，采用本文第5.1節(jié)中的方法。

(2) 對(duì)于查詢?nèi)罩局行鲁霈F(xiàn)的每一個(gè)查詢，在查詢點(diǎn)擊圖中增加一個(gè)查詢節(jié)點(diǎn)。

(3) 對(duì)于查詢?nèi)罩局行鲁霈F(xiàn)的每一個(gè)地址，在查詢點(diǎn)擊圖中增加一個(gè)地址節(jié)點(diǎn)。

(4) 對(duì)于每個(gè)查詢節(jié)點(diǎn)，建立從它到所有相關(guān)點(diǎn)擊地址節(jié)點(diǎn)的有向邊，邊的初始權(quán)重設(shè)置為1，若邊已存在，權(quán)重加1。

3.2 詞項(xiàng)關(guān)系圖

詞項(xiàng)關(guān)系圖，記為GT={VT,ET}，是一個(gè)加權(quán)有向圖。節(jié)點(diǎn)集合為VT={vt}，其中每個(gè)節(jié)點(diǎn)vt表示一個(gè)詞項(xiàng)。邊集合為ET={et}，其中每條邊et均由某一詞項(xiàng)節(jié)點(diǎn)出發(fā)到另一詞項(xiàng)節(jié)點(diǎn)結(jié)束，表示兩詞項(xiàng)在搜索日志中有直接關(guān)聯(lián)。邊權(quán)重ω(et)的大小反映了兩詞項(xiàng)直接關(guān)聯(lián)的強(qiáng)弱，若邊et不存在，則另ω(et)=0。

詞項(xiàng)關(guān)系圖可以通過(guò)對(duì)查詢點(diǎn)擊圖進(jìn)行兩次圖結(jié)構(gòu)轉(zhuǎn)換而得到。

3.2.1 查詢節(jié)點(diǎn)替換

由查詢?nèi)罩局苯訕?gòu)建的查詢點(diǎn)擊圖雖然能夠完整地記錄查詢?nèi)罩局胁樵兣c地址及其之間關(guān)系，然而對(duì)于查詢擴(kuò)展這一以詞項(xiàng)為處理單元的任務(wù)來(lái)說(shuō)，其查詢節(jié)點(diǎn)包含的信息粒度過(guò)大，不利于挖掘詞項(xiàng)間的關(guān)聯(lián)。因此需要將其細(xì)化，具體步驟如下：

(1) 對(duì)于查詢點(diǎn)擊圖中的每一個(gè)查詢節(jié)點(diǎn)，將該查詢節(jié)點(diǎn)使用其對(duì)應(yīng)查詢所包含的各詞項(xiàng)節(jié)點(diǎn)代替。

(2) 若對(duì)應(yīng)詞項(xiàng)節(jié)點(diǎn)不存在則增加該節(jié)點(diǎn)。

(3) 將所有與查詢節(jié)點(diǎn)關(guān)聯(lián)的邊逐一復(fù)制給相應(yīng)的各詞項(xiàng)節(jié)點(diǎn)。

(4) 刪除該查詢節(jié)點(diǎn)及與其關(guān)聯(lián)的所有邊。

至此形成由詞項(xiàng)節(jié)點(diǎn)、地址節(jié)點(diǎn)及它們之間加權(quán)邊所構(gòu)成的詞項(xiàng)—地址關(guān)系圖。

3.2.2 地址節(jié)點(diǎn)消除

由于查詢擴(kuò)展技術(shù)的特定性質(zhì)，詞項(xiàng)—地址關(guān)系圖中的地址節(jié)點(diǎn)是不必要的，并且其存在勢(shì)必會(huì)給處理過(guò)程增加額外的消耗。因此本文通過(guò)如下步驟將地址節(jié)點(diǎn)消除：

(1) 對(duì)于每一個(gè)詞項(xiàng)節(jié)點(diǎn)對(duì)(vt1,vt2)和每一個(gè)地址節(jié)點(diǎn)vu，若vt1與vt2均指向vu， 則建立由vt1到vt2以及由vt2到vt1的邊，邊上權(quán)重均初始化為c(vt1,vt2,vu)，若邊已存在，則將其上權(quán)重加c(vt1,vt2,vu)。

(2) 刪除所有地址節(jié)點(diǎn)及與其關(guān)聯(lián)的所有邊。

其中對(duì)于任意詞項(xiàng)節(jié)點(diǎn)vt1和vt2(vt1≠vt2)和任意地址節(jié)點(diǎn)vu，c(vt1,vt2,vu)表示vt1與vt2經(jīng)由vu所產(chǎn)生的點(diǎn)擊通量[8]，由如下公式計(jì)算得到：

c(vt1,vt2,vu)=min(ω(vt1→vu),ω(vt2→vu))

(1)

綜上所述，經(jīng)過(guò)這些步驟可以快速的將查詢點(diǎn)擊關(guān)系圖轉(zhuǎn)換為詞項(xiàng)關(guān)系圖，并且該轉(zhuǎn)換有諸多現(xiàn)實(shí)意義： (1)詞項(xiàng)關(guān)系圖更利于以查詢擴(kuò)展為目的較全面和直接地發(fā)掘查詢?nèi)罩局懈髟~項(xiàng)間的關(guān)聯(lián)；(2)可以避免由查詢?nèi)罩緮?shù)據(jù)直接構(gòu)造詞項(xiàng)關(guān)系圖所需要的復(fù)雜邏輯；(3)相比查詢和地址數(shù)量，詞項(xiàng)數(shù)量更小，進(jìn)而詞項(xiàng)關(guān)系圖所需存儲(chǔ)數(shù)據(jù)量更小，結(jié)構(gòu)也更簡(jiǎn)單；(4)對(duì)于SimRank算法而言，對(duì)于節(jié)點(diǎn)同質(zhì)的圖結(jié)構(gòu)處理更加高效，也更利于進(jìn)行優(yōu)化。

4 權(quán)重標(biāo)準(zhǔn)化SimRank與查詢擴(kuò)展

4.1 SimRank

構(gòu)造詞項(xiàng)關(guān)系圖后，原先孤立地計(jì)算兩個(gè)查詢?cè)~項(xiàng)之間共現(xiàn)度或翻譯概率的問題就被轉(zhuǎn)化成為在詞項(xiàng)關(guān)系圖上計(jì)算兩詞項(xiàng)節(jié)點(diǎn)之間相似度的問題。Glen和Jennifer提出的SimRank方法[1]能利用有向圖的結(jié)構(gòu)信息計(jì)算圖中任意兩節(jié)點(diǎn)對(duì)象的相似度，其基本思想是： 如果兩對(duì)象a和b同時(shí)分別與另外兩對(duì)象c和d關(guān)聯(lián)，且c與d是相似的，則a與b也是相似的；并且任意節(jié)點(diǎn)與其自身?yè)碛凶畲笙嗨贫?。也就是說(shuō)，節(jié)點(diǎn)間的相似性依賴于鄰節(jié)點(diǎn)的相似性，節(jié)點(diǎn)間的相似度可以由鄰居節(jié)點(diǎn)間的相似度遞歸計(jì)算。

針對(duì)本文而言，對(duì)詞項(xiàng)關(guān)系圖GT={VT,ET}中任意詞項(xiàng)節(jié)點(diǎn)vt，定義I(vt)表示vt的入邊源節(jié)點(diǎn)集合，Ii(vt)表示該集合中第i個(gè)入邊源節(jié)點(diǎn)，|I(vt)|為vt的入度總和。令Sim(va,vb)表示節(jié)點(diǎn)va和節(jié)點(diǎn)vb的SimRank相似度。根據(jù)SimRank的基本思想，該相似度的標(biāo)準(zhǔn)計(jì)算公式如下：

其中，常數(shù)C為取值范圍由0到1的實(shí)數(shù)，表示相似度在沿有向邊傳遞過(guò)程中的衰減系數(shù)。

4.2 權(quán)重標(biāo)準(zhǔn)化SimRank

通過(guò)在詞項(xiàng)關(guān)系圖上應(yīng)用SimRank算法，能夠綜合考慮任意查詢?cè)~項(xiàng)對(duì)之間的所有路徑，進(jìn)而可以挖掘出各詞項(xiàng)間的深層關(guān)聯(lián)。同時(shí)，由于SimRank具有對(duì)稀疏數(shù)據(jù)公平對(duì)待的特性，更加適用于搜索引擎查詢?nèi)罩具@種信息非常稀疏的數(shù)據(jù)類型。

然而，對(duì)于本文研究的問題而言，基礎(chǔ)的SimRank算法仍然存在一個(gè)主要問題： SimRank算法在計(jì)算節(jié)點(diǎn)間相似度的過(guò)程中僅利用了有向圖的結(jié)構(gòu)信息，而沒有考慮到有向邊上的權(quán)重信息。在詞項(xiàng)關(guān)系圖中，邊上權(quán)重體現(xiàn)了兩詞項(xiàng)在查詢?nèi)罩局锌偟狞c(diǎn)擊通量情況，點(diǎn)擊通量越大的查詢?cè)~項(xiàng)間關(guān)聯(lián)程度越高，所表達(dá)的語(yǔ)義也更接近，在查詢擴(kuò)展的候選詞項(xiàng)中理應(yīng)給予更多的考慮，而這些在基礎(chǔ)SimRank方法的計(jì)算過(guò)程中均未考慮。

為此本文對(duì)SimRank算法進(jìn)行了改進(jìn)，以適合在詞項(xiàng)關(guān)系圖上的查詢?cè)~項(xiàng)相似度計(jì)算。首先，對(duì)詞項(xiàng)關(guān)系圖中每個(gè)節(jié)點(diǎn)的入邊權(quán)重進(jìn)行標(biāo)準(zhǔn)化，使之對(duì)于任意節(jié)點(diǎn)vt均滿足以下關(guān)系：

(3)

進(jìn)而將標(biāo)準(zhǔn)化后的邊權(quán)重融入基礎(chǔ)SimRank算法，記為權(quán)重標(biāo)準(zhǔn)化SimRank算法(Weight Normalized SimRank，簡(jiǎn)稱WNS)，其計(jì)算公式如下：

其中，ω(va→vb)表示由va節(jié)點(diǎn)到vb節(jié)點(diǎn)的有向邊上的權(quán)重，其他符號(hào)與基礎(chǔ)SimRank公式中同義。

4.3 性能優(yōu)化

SimRank和WNS算法均是以圖結(jié)構(gòu)為基礎(chǔ)的算法，因此對(duì)圖中節(jié)點(diǎn)對(duì)進(jìn)行一次遍歷計(jì)算需要耗費(fèi)大量的計(jì)算時(shí)間，加之其計(jì)算過(guò)程需要進(jìn)行多次迭代以得到收斂后的穩(wěn)定相似度，因此該算法的時(shí)間復(fù)雜度為Ο(kn2d2)(k表示迭代次數(shù)，d表示節(jié)點(diǎn)的平均入度)。當(dāng)n的規(guī)模很大時(shí)，算法的性能很差，這也是本文方法在實(shí)現(xiàn)過(guò)程中所遇到的主要問題，為此本文分別使用了靜態(tài)剪枝和限制傳播半徑兩種方法對(duì)WNS算法進(jìn)行了性能優(yōu)化。

4.3.1 靜態(tài)剪枝

從算法的時(shí)間復(fù)雜度中不難看出，有向圖中節(jié)點(diǎn)的平均入度對(duì)實(shí)際時(shí)間消耗有較大影響，因此如果能減少計(jì)算圖中節(jié)點(diǎn)的平均入度，則會(huì)相應(yīng)地提高算法效率。為此，本文對(duì)詞項(xiàng)關(guān)系圖進(jìn)行了靜態(tài)剪枝操作。

首先，對(duì)于圖中每一個(gè)節(jié)點(diǎn)，只保留其入邊集合中點(diǎn)擊量最大的dm條邊，刪除其余入邊；如果節(jié)點(diǎn)入邊數(shù)不足dm條，則全部保留；然后，再對(duì)所有保留的入邊上的權(quán)重進(jìn)行標(biāo)準(zhǔn)化。

靜態(tài)剪枝會(huì)損失原詞項(xiàng)關(guān)系圖中的一部分信息，但是由公式(2)和公式(5)不難看出，入邊權(quán)重很小的鄰節(jié)點(diǎn)相似度對(duì)當(dāng)前計(jì)算的節(jié)點(diǎn)對(duì)的相似度貢獻(xiàn)很小，又因?yàn)镾imRank是一種收斂速度較快的迭代算法[9]，所以，在一般情況下，能夠較快的找到一個(gè)數(shù)值較小的dm使得所需的最終相似度數(shù)值幾乎沒有損失，對(duì)此本文實(shí)驗(yàn)部分將會(huì)給出進(jìn)一步說(shuō)明。

4.3.2 限制傳播半徑

G. Jeh和J. Widom[9]提出了一種通過(guò)限制SimRank計(jì)算過(guò)程中的相似度傳播半徑r，以提高算法效率的優(yōu)化方法。在最壞情況下，每次迭代中需要計(jì)算n2個(gè)節(jié)點(diǎn)對(duì)的相似度，當(dāng)n的規(guī)模很大時(shí)效率很差?！凹僭O(shè)兩節(jié)點(diǎn)相距很遠(yuǎn)，則它們的鄰節(jié)點(diǎn)集合只會(huì)有很少量的重疊，因此根據(jù)SimRank的算法思想，像這樣相距很遠(yuǎn)的節(jié)點(diǎn)間相似度必然會(huì)遠(yuǎn)低于相距較近節(jié)點(diǎn)”[9]。所以在本文的方法中我們也限制了WNS計(jì)算過(guò)程中的相似度傳播半徑，即若兩節(jié)點(diǎn)va與vb間距離超過(guò)r，則記WNS(va,vb)=0。

通過(guò)這種方式，SimRank計(jì)算的時(shí)間復(fù)雜度可以降至接近Ο(knd2)，同時(shí)由此產(chǎn)生的誤差可忽略不計(jì)[9]。

4.4 查詢擴(kuò)展

查詢擴(kuò)展技術(shù)的基本思想是選擇與原始查詢同義或有強(qiáng)語(yǔ)義關(guān)聯(lián)的詞項(xiàng)作為擴(kuò)展詞項(xiàng)加入查詢中。本文中采用的查詢擴(kuò)展策略具體步驟如下：

(1) 對(duì)于原始查詢中每一個(gè)詞項(xiàng)t，若其在詞項(xiàng)關(guān)系圖中有對(duì)應(yīng)節(jié)點(diǎn)vt，則將與vt間WNS相似度非0的所有節(jié)點(diǎn)所對(duì)應(yīng)的詞項(xiàng)加入候選集。

(2) 在候選集中選擇相似度最高的K個(gè)節(jié)點(diǎn)作為擴(kuò)展詞加入原始查詢中。

(3) 利用擴(kuò)展后的查詢進(jìn)行檢索。

其中，K為正整數(shù)，表示擴(kuò)展詞數(shù)。下文中將該方法簡(jiǎn)記為WNSE。

5 實(shí)驗(yàn)

5.1 實(shí)驗(yàn)數(shù)據(jù)與評(píng)測(cè)指標(biāo)

5.1.1 搜索引擎查詢?nèi)罩?/p>

為了驗(yàn)證本文方法的有效性，實(shí)驗(yàn)在真實(shí)的搜索引擎查詢?nèi)罩旧祥_展，所使用的查詢?nèi)罩緮?shù)據(jù)為AOL(American Online)公司面向?qū)W術(shù)研究公開的旗下搜索引擎由2006年3月1日00:00:00至2006年5月31日23:59:59期間的全部搜索日志，包含了657 426個(gè)獨(dú)立用戶的總共36 389 567條記錄，格式為“用戶 查詢 時(shí)間 [點(diǎn)擊序號(hào) 地址]”[10]。其中共有10 154 742個(gè)不同查詢以及19 442 629次用戶點(diǎn)擊。

5.1.2 檢索文檔集與原始查詢

本文實(shí)驗(yàn)使用TREC評(píng)測(cè)所提供的公開文檔集GOV2作為檢索文檔集，共包含文檔25 205 179個(gè)，其中大部分為政府部門曾公開發(fā)表的英文新聞文章；同時(shí)實(shí)驗(yàn)中我們使用了TREC公開的701至850號(hào)Topic作為原始查詢集合。

5.1.3 評(píng)價(jià)方法

本文實(shí)驗(yàn)評(píng)測(cè)部分使用TREC提供的公開相關(guān)文檔標(biāo)注結(jié)果以及標(biāo)準(zhǔn)評(píng)測(cè)程序。為了同時(shí)從不同角度考察本文方法的有效性，本文采用了P@10、P@20和MAP三項(xiàng)指標(biāo)對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行評(píng)價(jià)。

5.2 實(shí)驗(yàn)設(shè)計(jì)

首先，我們對(duì)AOL搜索引擎查詢?nèi)罩具M(jìn)行去噪處理，將諸如“fidelity.com”的網(wǎng)址導(dǎo)航查詢和類似“wu 20v 20-----”的無(wú)語(yǔ)義信息查詢以及包含成人詞匯的查詢過(guò)濾后，按前文所述方法構(gòu)造了查詢點(diǎn)擊圖。圖中共有查詢節(jié)點(diǎn)4 605 412個(gè)，地址節(jié)點(diǎn)2 316 342個(gè)。在此基礎(chǔ)上構(gòu)造詞項(xiàng)關(guān)系圖，圖中共有詞項(xiàng)節(jié)點(diǎn)413 013個(gè)。

接著，對(duì)詞項(xiàng)關(guān)系圖進(jìn)行靜態(tài)剪枝，我們對(duì)不同的最大節(jié)點(diǎn)入度dm取值進(jìn)行了簡(jiǎn)單的對(duì)比試驗(yàn)，在用WNS進(jìn)行5次迭代后的結(jié)果中抽取3個(gè)詞項(xiàng)節(jié)點(diǎn)對(duì)的相似度進(jìn)行觀察，發(fā)現(xiàn)當(dāng)dm取值范圍在100至900時(shí)，其相似度變化如表1所示。

可以看出，當(dāng)dm取值500以上時(shí)，dm數(shù)值的增加對(duì)最終相似度的影響甚微，所以在實(shí)際實(shí)驗(yàn)中，我們?cè)O(shè)置dm為500。

之后，我們?cè)诘玫降脑~項(xiàng)關(guān)系圖上使用WNS方法進(jìn)行詞項(xiàng)間相似度的計(jì)算，由于一般情況下當(dāng)C在0.5到0.9之間變化時(shí)，相似度關(guān)系的變化很小[7]，所以實(shí)際實(shí)驗(yàn)中我們將C設(shè)置為經(jīng)驗(yàn)值0.8[9]。類似的，將相似度傳播半徑r和迭代次數(shù)k均按經(jīng)驗(yàn)值設(shè)置為 2和5[9]。

表1 不同dm取值時(shí)的WNS相似度

最后，使用本文在4.4節(jié)所述的查詢擴(kuò)展方法，在Indri檢索工具中利用結(jié)構(gòu)化查詢語(yǔ)句“#weight”和“#combine”進(jìn)行檢索，并按照是否將WNS相似度作為擴(kuò)展詞項(xiàng)的權(quán)重加入最終查詢而分為WNSE-Weighted以及WNSE-Unweighted兩種方法，分別進(jìn)行有效性驗(yàn)證，最終查詢形式如公式(6)。

#weight(λQori(1.0-λ)Qexp)

(6)

其中λ為取值0到1間的實(shí)數(shù)，表示原始查詢權(quán)重；Qori表示原始查詢；Qexp表示擴(kuò)展詞。

作為有效性驗(yàn)證的對(duì)比實(shí)驗(yàn)，我們分別選擇了兩種較成熟且被廣泛用于對(duì)比的方法： (1)查詢似然模型，并使用以經(jīng)驗(yàn)值1 500為參數(shù)的Dirichlet平滑方法，記為L(zhǎng)M-Dir，該方法同時(shí)也為其他查詢擴(kuò)展方法的基礎(chǔ)檢索方法；(2)基于偽相關(guān)文檔的Lavrenko查詢擴(kuò)展方法[11]，記為RM方法。

5.3 實(shí)驗(yàn)結(jié)果

通過(guò)觀察實(shí)驗(yàn)所得到的3種查詢擴(kuò)展方法在GOV2數(shù)據(jù)集上的性能變化情況(圖1)， 可以發(fā)現(xiàn)

圖1 K=30時(shí)各擴(kuò)展方法的性能變化曲線

當(dāng)擴(kuò)展詞數(shù)K=30時(shí)，RM方法在λ取值約0.6時(shí)MAP指標(biāo)分值最高；本文提出的WNSE-Weighted和WNSE-Unweighted方法分別在λ取值0.9和 0.8 時(shí)效果最好。表2、表3和表4分別給出了上文所述4種方法在λ參數(shù)取最優(yōu)情況時(shí)的P@10、P@20 和MAP評(píng)價(jià)指標(biāo)分值。

表2 4種方法檢索結(jié)果MAP分值

表3 4種方法檢索結(jié)果P@10分值

表4 4種方法檢索結(jié)果P@20分值

從各表中不難看出，本文提出的WNSE-Weighted和WNSE-Unweighted方法，在MAP評(píng)價(jià)指標(biāo)上與傳統(tǒng)RM方法性能相當(dāng)，并且大多數(shù)情況下分值略高于后者；而在P@10和P@20評(píng)價(jià)指標(biāo)上相對(duì)RM方法均有較大幅度提高；實(shí)驗(yàn)中涉及的各查詢擴(kuò)展方法在三項(xiàng)評(píng)價(jià)指標(biāo)上均相對(duì)于基礎(chǔ)檢索方法LM-Dir有很大幅度的提高；WNSE-Weighted方法效果略優(yōu)于WNSE-Unweighted方法，且相比更加穩(wěn)定。為了更直觀的反映實(shí)驗(yàn)結(jié)果，圖2給出了各評(píng)價(jià)指標(biāo)的分值變化曲線。

從圖中可以得出與上文相同的結(jié)論，與此同時(shí)我們還發(fā)現(xiàn)WNSE方法在擴(kuò)展規(guī)模較小(K取值20至40)時(shí)效果較好，而RM方法在擴(kuò)展規(guī)模較大時(shí)效果更優(yōu)。其意義將在5.4節(jié)中進(jìn)行討論。

圖2 4種方法檢索結(jié)果的MAP、P@10和P@20分值變化曲線

5.4 實(shí)驗(yàn)結(jié)果分析

由實(shí)驗(yàn)結(jié)果可以得出在最優(yōu)情況下，本文設(shè)計(jì)的WNSE方法與傳統(tǒng)RM以及基礎(chǔ)檢索LM-Dir方法相比： 在MAP指標(biāo)上分別提高了1.81%和5.22%；在P@10指標(biāo)上分別提高了5.44%和8.61%；在P@20指標(biāo)上分別提高了3.73%和7.73%。說(shuō)明WNSE查詢擴(kuò)展方法在AOL搜索引擎查詢?nèi)罩竞虶OV2文檔集上有不錯(cuò)的實(shí)際檢索效果。

關(guān)于WNSE方法在擴(kuò)展規(guī)模較小時(shí)效果較好這一特點(diǎn)，也有其現(xiàn)實(shí)意義。眾所周知在各檢索框架下，查詢?cè)~項(xiàng)的增加都會(huì)不同程度地增加檢索所需時(shí)間，因此WNSE方法有助于使用較少的檢索時(shí)間得到較好的檢索效果。

從圖2中還可以看出，WNSE方法隨平均擴(kuò)展度的增加各指標(biāo)分值均有一定程度的波動(dòng)，經(jīng)過(guò)觀察實(shí)驗(yàn)中間結(jié)果，我們發(fā)現(xiàn)造成波動(dòng)的原因主要是所使用的查詢?nèi)罩局邪胍?，雖然已經(jīng)經(jīng)過(guò)了一些去噪處理，但仍然殘存一定數(shù)量的噪音詞項(xiàng)。在原始查詢較短情況下，噪音詞項(xiàng)的加入會(huì)一定程度上影響檢索效果。然而即便如此，在處于波動(dòng)低值時(shí)的檢索性能也是可以容忍的。

6 總結(jié)

查詢擴(kuò)展技術(shù)是現(xiàn)代檢索技術(shù)中一個(gè)重要的組成部分，能夠較為有效地幫助用戶與搜索引擎進(jìn)行交互，從而提高檢索效果。本文提出了一種將搜索引擎查詢?nèi)罩臼褂貌樵凕c(diǎn)擊圖表示，進(jìn)而轉(zhuǎn)化為詞項(xiàng)關(guān)系圖的圖模型表示方法，同時(shí)引入了對(duì)相似度算法SimRank進(jìn)行改進(jìn)后的權(quán)重標(biāo)準(zhǔn)化SimRank算法，來(lái)計(jì)算圖中個(gè)詞項(xiàng)間的相似度，從而綜合利用查詢?nèi)罩局性~項(xiàng)間直接和潛在的信息進(jìn)行查詢擴(kuò)展。

原始權(quán)重標(biāo)準(zhǔn)化SimRank方法在較大規(guī)模數(shù)據(jù)的應(yīng)用中存在很大的時(shí)間消耗，因此本文從該角度出發(fā)，使用靜態(tài)剪枝以及限制傳播半徑的方法對(duì)算法進(jìn)行了優(yōu)化，提高了算法的效率和實(shí)用性。

基于較大規(guī)模真實(shí)搜索引擎查詢?nèi)罩镜膶?shí)驗(yàn)驗(yàn)證了本文方法的有效性。利用基于詞項(xiàng)關(guān)系圖的權(quán)重標(biāo)準(zhǔn)化SimRank方法在標(biāo)準(zhǔn)TREC數(shù)據(jù)集上進(jìn)行查詢擴(kuò)展，其效果比傳統(tǒng)偽相關(guān)文檔查詢擴(kuò)展在P@10評(píng)價(jià)指標(biāo)上有較大幅度提高，同時(shí)在MAP指標(biāo)上也有小幅提升。

同時(shí)我們也注意到，本文方法也存在一些不足之處： (1)由于查詢?nèi)罩緮?shù)據(jù)的稀疏性和大量噪音，導(dǎo)致最終實(shí)驗(yàn)結(jié)果未達(dá)到最優(yōu)；(2)由于作者精力有限，對(duì)比實(shí)驗(yàn)中并未涉及更多的相關(guān)方法，這也還我們?cè)诮窈笠欢螘r(shí)期內(nèi)進(jìn)行更多的相關(guān)研究工作。

[1] J. Xu and W. Croft. Query expansion using local and global document analysis [C]//Proceedings of SIGIR. Zurich, Switzerland，1996：4-11.

[2] X. Wang, C. Zhai. Mining term association patterns from search logs for effective query reformulation [C]//Proceedings of CIKM. Napa Valley, California, USA，2008:479-488.

[3] 宋巍，張宇，劉挺，等. 基于檢索歷史上下文的個(gè)性化查詢重構(gòu)技術(shù)研究[C]//第五屆全國(guó)信息檢索學(xué)術(shù)會(huì)議. 上海，中國(guó)，2009:144-152.

[4] V. Dang, W. B. Croft. Query reformulation using anchor text [C]//Proceedings of WSDM. New York City, New York, USA，2010:41-50.

[5] P. Boldi, F. Bonchi and C. Castillo. Query suggestions using query-flow graphs [C]//Proceedings of WSCD. Barcelona, Spain，2009:51-58.

[6] I. Antonellis, H. G. Molina and C. C. Chang. Simrank++: Query rewriting through link analysis of the click graph [C]//proceedings of VLDB. Auckland, New Zealand，2008:408-421.

[7] 許晟，李亞楠，王斌，等. 基于加權(quán)SimRank的中文查詢推薦研究[C]//第五屆全國(guó)信息檢索學(xué)術(shù)會(huì)議. 上海，中國(guó)，2009:242-251.

[8] D. Beeferman, A. Berger. Agglomerative clustering of a search engine query log [C]//Proceedings of SIGKDD. Boston, Massachusetts, USA，2000:407- 416.

[9] G. Jeh, J. Widom. SimRank: A measure of structural-context similarity [C]//Proceedings of SIGKDD. Edmonton, Alberta, Canada，2002:538-543.

[10] F. Diaz, D. Metzler. Improving the estimation of relevance models using large external corpora [C]//Proceedings of SIGIR. Seattle, Washington, USA，2006:154-161.

[11] V. Lavrenko, W. B. Croft. Relevance based language models [C]//Proceedings of SIGIR. New Orleans, Louisiana, United States，2001:120-127.

[12] C. Silverstein, H. Marais and M. Henzinger. Analysis of a very large web search engine query log [J]. ACM SIGIR Forum, 1999, 33(1)： 6-12.