劉鈺峰 ，李仁發(fā)

(1．湖南大學 信息科學與工程學院，湖南 長沙 410082; 2．湖南大學 嵌入式系統(tǒng)與網(wǎng)絡實驗室，湖南 長沙 410082)

當前，搜索引擎主要基于關鍵詞匹配的方法進行檢索，然而，用戶輸入的查詢難以準確完整的表達用戶的檢索意圖.因此，如何理解用戶真正的信息需求成為信息檢索系統(tǒng)重要的任務之一.當用戶提交查詢關鍵字時，搜索引擎推薦一系列與原始查詢相關的查詢供用戶選擇，這一技術稱為查詢推薦.由于它能幫助用戶修正初始查詢更好的表達查詢需求而被眾多的商業(yè)搜索引擎所采用.

日志信息中包含了用戶的查詢和點擊行為，根據(jù)點擊信息(click-through data)構造查詢(Query)和URL之間的二部圖是查詢推薦中的主要模型之一[1-3].在此基礎上，文獻[1]采用隨機游走模型分析查詢詞之間的平均首達時間(hitting time)進行查詢推薦.文獻[2]在Query-URL二部圖的基礎上整合了用戶在查詢過程中返回的Top N地址信息，從而優(yōu)化稀疏查詢的推薦性能.另一方面，通過分析用戶在查詢過程中的序列行為構造Query-Flow圖也得到了廣泛的研究，通常使用在同一個查詢?nèi)蝿罩蠶uery和Query之間的文本關系、session特征以及時間相關等信息構造Query之間的轉(zhuǎn)移概率，從而得到Query-Flow圖[4].文獻[5]采用了短隨機游走(short random walk)對Query-Flow圖進行分析，得出了在沒有使用點擊記錄的情況下也可以獲得較好的推薦效果.文獻[6]對比分析了基于Query-URL二部圖和基于Query-Flow圖的查詢推薦方法，認為基于Query-Flow圖的查詢推薦方法效果更好.基于日志信息的方法雖然得到了廣泛的應用，但是存在著以下問題：一是用戶提交給搜索引擎的查詢滿足長尾分布(long-tailed distributions)，基于日志的查詢推薦在處理高頻查詢?nèi)〉昧瞬诲e的效果，但是面對大量的稀疏查詢，由于日志記錄缺乏相應的信息進行訓練，因此難以取得較好的效果[7].二是日志分析的本質(zhì)是利用群體智慧進行協(xié)同推薦，但是無法分析查詢中的語義信息.

基于以上原因，研究者考慮通過分析查詢的語義概念進行查詢推薦.例如：文獻[7-8]等通過分析用戶點擊的摘要片段構造概率語言模型進行查詢推薦.文獻[9]使用維基百科來構造查詢之間的語義關系.文獻[10]使用大規(guī)模的鏈接文本作為語義分析的數(shù)據(jù)源.文獻[11]把查詢記錄按照語義概念進行聚類，然后從聚類結(jié)果中選擇用戶瀏覽次數(shù)最多的Query作為類別的代表進行查詢推薦.文獻 [12]根據(jù)多種語義特征構造了基于主題的詞匯轉(zhuǎn)移矩陣進行查詢推薦，取得了較好的效果.文獻[13]提出了一種基于詞項-查詢圖(term-query graph)的概率混合模型，該模型能夠準確地發(fā)掘出用戶的查詢意圖.基于語義的查詢推薦的主要問題包括[14]：一是如何挑選合適的詞匯進行查詢推薦，僅僅按照與原始查詢的相關性選擇詞匯可能會導致冗余性問題.二是如何將挑選的詞匯自動構造成合適的查詢.

由于基于日志分析和基于語義分析的方法各有優(yōu)缺點，本文通過構造統(tǒng)一的模型同時分析日志信息及語義信息構造Term-Query-URL異構信息網(wǎng)絡，采用基于查詢的重啟動隨機游走進行查詢推薦.相比現(xiàn)有的方法，本文具有以下優(yōu)勢：1)從全局的角度進行查詢推薦，在一個統(tǒng)一的模型中同時使用日志信息和語義信息進行查詢推薦.2)借助于點擊日志進行協(xié)同推薦，在高頻查詢上能取得很好的效果，采用基于文檔的方法訓練詞匯和查詢詞之間的語義關系，可以提高稀疏查詢的推薦效果.3)基于日志的方法無法對沒有在查詢?nèi)罩局谐霈F(xiàn)過的查詢進行推薦，在本文提出的方法中，只需構造合適的查詢向量，無需修改推薦算法即可從歷史查詢中選擇合適的查詢進行查詢推薦，同時避免了挑選詞匯構造合適的查詢的問題.在大規(guī)模商業(yè)搜索引擎查詢?nèi)罩旧系膶嶒灡砻鞅疚姆椒▋?yōu)于現(xiàn)有的查詢推薦方法.

1 基于Term-Query-URL異構信息網(wǎng)絡的查詢推薦標題

本節(jié)首先介紹如何根據(jù)文檔摘要內(nèi)容、查詢序列行為以及點擊信息構造Term-Query-URL異構信息網(wǎng)絡，然后介紹使用重啟動隨機游走模型在該網(wǎng)絡上進行查詢推薦的方法.

1.1 Term-Query二部圖模型

使用在查詢上點擊的文檔摘要片段訓練詞匯和查詢之間的二部圖，該圖示例請參見圖1.基于Term-Query的二部圖可以表示為三元組GTQ=(T,Q,ETQ)，其中T表示為由詞匯組成的非空頂點集，Q表示由查詢構成的非空頂點集，ETQ為連接詞匯和查詢的邊的集合，即E?T×Q，在詞匯和詞匯之間，查詢和查詢之間沒有邊.設w:T×Q→R+表示權重函數(shù)，w(i,j)表示詞匯ti和查詢qj之間關聯(lián)的概率，如果兩者之間沒有關聯(lián)則wTQ(i,j)=0.

可以采用偽反饋文檔來訓練得到wTQ(i,j)，但是這就必須依賴于偽反饋文檔的質(zhì)量.通常認為，用戶點擊的上下文摘要片段和查詢詞之間存在著更為緊密的關系，因此本文采用查詢詞和點擊的文檔摘要片段之間的關系來得到wTQ(i,j).假設用戶發(fā)出查詢q時，點擊的文檔摘要的集合為sq，系統(tǒng)日志中總的摘要集合為S={s1,s2,…,sk}，則令：

(1)

圖1 Term-Query二部圖

1.2 Query-Flow圖模型

Query-Flow圖是一種用來描述查詢序列行為的有向圖[4]，它的基本思想是當查詢qi和查詢qj屬于同一個查詢?nèi)蝿諘r，它們之間應該存在一條有向邊.Query-Flow圖的示例請參見圖2.Query-Flow圖可以定義為GQQ=(Q,EQQ)，其中Q表示由查詢構成的非空頂點集，E為連接查詢和查詢的邊的集合，EQQ?Q×Q.設wQQ:Q×Q→R+表示權重函數(shù)，wQQ(i,j)表示查詢qi和查詢qj之間關聯(lián)的概率，如果兩者之間沒有關聯(lián)則wQQ(i,j)=0.

(2)

psession(qj|qi)描述了從查詢qi到查詢qj的轉(zhuǎn)移概率.在構造Query-Flow圖時，通常使用會話(Session)的概念來判斷兩個查詢是否屬于同一個任務， 可以基于時間閾值或語義概率來判斷同一個用戶發(fā)出的連續(xù)的查詢是否屬于同一個Session[15].f(qi,qj)表示同一個查詢?nèi)蝿罩校樵僸j跟隨查詢qi出現(xiàn)的次數(shù)，其中f(qi)=∑qk∈Qf(qi,qk)用于對w(i,j)進行規(guī)范化.可以觀察到查詢qi和查詢qj之間的轉(zhuǎn)移概率并不對稱，因此Query-Flow圖是一個有向圖.如果按照文獻[5]中的方法估計查詢之間的轉(zhuǎn)移概率，則可以構造無向的Query-Flow圖.

1.3 Term-Query-URL異構信息網(wǎng)絡模型

圖3 Query-URL二部圖

我們把以上討論的三種關系統(tǒng)一到一個模型中進行分析，考慮包含Term，Query，URL3種不同節(jié)點的異構信息網(wǎng)絡圖GTQU={V,E}，其中V=T∪Q∪U，E=ETQ∪EQQ∪EQU.以A來表示GTQ的鄰接矩陣，使用B表示GQU的鄰接矩陣，使用C表示GQQ的鄰接矩陣，則GTQU的鄰接矩陣如下所示：

(3)

為了在該圖上使用隨機游走模型，對W的列向量進行規(guī)范化：

(4)

式(3)中的α，β和γ為系數(shù)，α∈[0,1]，β∈[0,1]，γ∈[0,1]且α+β+γ=1.如果當前處在Q中的節(jié)點，α表示跳轉(zhuǎn)到T中節(jié)點的概率，β表示跳轉(zhuǎn)到U中節(jié)點的概率，γ表示使用Query-Flow圖跳轉(zhuǎn)到查詢節(jié)點的概率.當α=γ=0，則本文模型退化為只使用Query-URL的點擊模型，如果β=γ=0，則退化為只使用Term-Query模型的二部圖，如果α=β=0則退化為只使用Query-Flow模型.

1.4 基于Term-Query-URL異構信息網(wǎng)絡的查詢推薦

當用戶發(fā)出查詢q，查詢推薦的目標是在Q中尋找最為相似的查詢進行推薦.我們使用重啟動隨機游走模型進行查詢推薦，首先討論當q∈Q的情況下的查詢推薦.我們可以構造向量q：

q=[qt,qq,qu]T

(5)

如果q是GTQU中對應的第i個元素，令qi=1，其他對應的值都為0，很顯然，此時qt和qu都是零向量.在給定了初始的查詢向量的情況下，在GTQU上的重啟動隨機游走過程可以描述為：從GTQU上的節(jié)點q出發(fā)，它按照概率λ選擇重新從節(jié)點q出發(fā)，或者按照概率1-λ選擇訪問q的鄰居節(jié)點并開始新一輪的隨機游走，不斷地重復以上行為，直到在某一時刻停留在任意節(jié)點的概率保持穩(wěn)定.該過程可以描述為：

p=(1-λ)Mp+λq

(6)

不斷地迭代計算式(6)，p將會達到一個穩(wěn)定的狀態(tài)，p中pq的值可以作為衡量與初始查詢相關度的標準，排名靠前的查詢節(jié)點用來作為q的查詢推薦.

進一步分析本文中的模型，可以發(fā)現(xiàn)，q的鄰居節(jié)點有3種：Term節(jié)點、URL節(jié)點以及Query節(jié)點.因此，在隨機游走的過程中，它按照(1-λ)α的概率選擇Term節(jié)點，按照(1-λ)β的概率選擇URL節(jié)點，按照(1-λ)γ的概率選擇Query節(jié)點，式(6)可以進一步轉(zhuǎn)化為(7)，從而減少計算過程中的計算量.

pt=(1-λ)αApq+λqt

pq=(1-λ)(αATpt+βBpu+γCpq)+λqq

pu=(1-λ)βBTpq+γqu

(7)

(8)

E步：

(9)

M步：

(10)

其中的zj為引入隱含變量：

(11)

綜合以上描述，給出Term-Query-URL異構信息網(wǎng)絡上的查詢推薦算法如下.

算法1：基于Term-Query-URL異構信息網(wǎng)絡的查詢推薦算法．

輸入：Term-Query-URL異構信息網(wǎng)絡GTQU上的矩陣M及原始查詢q．

輸出：與原始查詢q相關的查詢推薦序列．

1)檢查q是否在查詢集合Q中出現(xiàn)，q∈Q則跳轉(zhuǎn)至2，否則跳轉(zhuǎn)至3.

3)根據(jù)式(8)計算q中詞匯在qt中的權重，令qu和qq為零向量，由(5)式得到初始向量q，跳轉(zhuǎn)至4).

4)根據(jù)式(7)迭代計算p至穩(wěn)定狀態(tài).

5)取p中的pq排名靠前的查詢作為推薦的查詢序列輸出.

步驟4中使用兩個向量之間夾角的余弦小于給定的閾值作為判斷迭代是否達到穩(wěn)定狀態(tài)的條件.在算法1中第4步是最為耗時的操作，其時間復雜度為O(n2).在實際應用中，GTQU圖中的節(jié)點非常多，算法1難以直接用于數(shù)據(jù)規(guī)模較大的應用，但在GTQU圖中大部分的節(jié)點與原始查詢沒有關系，因此，我們可以從原始查詢節(jié)點出發(fā)，采用深度遍歷的辦法抽取GTQU的子網(wǎng)按照算法1進行迭代計算.

2 實驗與分析

2.1 數(shù)據(jù)集

我們采用的原始數(shù)據(jù)集是來自搜狗搜索引擎2008年6月份網(wǎng)頁查詢?nèi)罩緮?shù)據(jù)集合，該數(shù)據(jù)中共包含51,537,393條日志記錄，5,736,696個不同的查詢，15,951,082個不同的URL.我們把日志記錄中出現(xiàn)次數(shù)大于20次的查詢稱為頻繁查詢，共238,761個，平均每個頻繁查詢查詢141.4次點擊，小于20次的查詢稱為稀疏查詢，共5,497,935個，平均每個稀疏查詢點擊3.2次.對于Session的定義，我們采用了簡單的方法，使用時間閾值30 min作為判斷兩個查詢是否屬于同一個任務的判斷標準[16]，經(jīng)處理后得到374,468個Session.

2.2 實驗設計及結(jié)果分析

使用的topN的精度P@N和MAP(Mean Average Precision)作為評價指標，給定了一個查詢q，系統(tǒng)給出j個推薦的查詢.

(12)

(13)

其中K是查詢測試集的總數(shù)，在我們的實驗中K=200，N=5.在文獻[2]中MAP被定義為所有查詢的AvgP的平均值，其中：

(14)

RQ為推薦查詢中與原始查詢相關查詢的總數(shù).φ(j)是一個指示函數(shù)，如果推薦的第j個查詢與原始查詢相關，則取1，否則為0.

從頻繁查詢和稀疏查詢中分別抽取了200個查詢作為測試集，然后由人工進行判斷產(chǎn)生的查詢推薦是否相關.我們使用Query-URL二部圖作為對比測試的基準模型(Baseline)，此時對應的參數(shù)設置為α=0,β=1,γ=0，文獻[1]在此基礎上使用隨機游走模型進行查詢推薦.文獻[2]在Query-URL圖的基礎上整合了系統(tǒng)返回的TopN地址信息，本文稱為RW-Pseudo.當α=0,β=0,γ=1時，本文模型退化為Query-Flow圖，正是文獻[3-4]中使用的模型.文獻[17]中給出了在沒有日志信息的情況下從文檔中抽取與原始查詢相關的短語作為查詢詞進行推薦，本文稱為Probabilistic方法，在本文中僅抽取包含查詢詞的句子進行訓練.文獻[13]使用概率混合模型來挖掘詞項查詢圖中的查詢意圖，并使用個性化隨機游走來預測單詞在查詢中的重要程序?qū)Σ樵冞M行推薦，該方法在實驗中我們稱為基于意圖的方法.本章方法采用的參數(shù)設置為α=0.2,β=0.4,γ=0.4，由于GTQU圖中大部分節(jié)點和原始查詢無關，對推薦的性能影響不大，因此我們設置預定義的節(jié)點數(shù)為500，然后從原始查詢節(jié)點出發(fā)采用深度遍歷的辦法抽取GTQU的子網(wǎng)，子網(wǎng)節(jié)點數(shù)大于500時深度遍歷終止，然后使用在抽取的子網(wǎng)上按照算法1進行迭代計算.

表1 6種算法在P@5和MAP上的性能比較

為了考察不同算法在不同P@N上的變化，我們分別使用Baseline、基于查詢意圖以及本文方法在P@1，P@3，P@5，P@5上對頻繁查詢和稀疏查詢進行測試.圖4為頻繁查詢上的測試結(jié)果，可以看到本文算法優(yōu)于Baseline、基于查詢意圖的方法．圖5為稀疏查詢上的測試結(jié)果，可以看到只有基于查詢意圖的方法和本文方法性能大致一致，這是由于基于查詢意圖的方法通過概率模型來挖掘詞項查詢圖，可以在不考慮其他查詢的情況下提升查詢推薦的性能，這與本文在稀疏查詢上的方法有異曲同工之處．

本文采用的是重啟動隨機游走算法，式(6)中的參數(shù)λ表示重啟動的概率.對于未在查詢?nèi)罩局谐霈F(xiàn)過的查詢，由于無法在Query中找到對應的節(jié)點，使用日志信息的方法無法進行處理[14].我們通過分析原始的查詢記錄，構造了在數(shù)據(jù)集中沒有出現(xiàn)過的查詢，其中部分推薦結(jié)果示例如表2所示.

圖4 不同算法在頻繁查詢上的P@N比較

圖5 不同算法在稀疏查詢上的P@N比較

從表2中可見，本文算法在相關性上取得了較好的效果.由于本文的數(shù)據(jù)集采用的是2008年6月的數(shù)據(jù)，在推薦的查詢中反映了當時的一些熱點信息，例如汶川地震以及范尼離開曼聯(lián)等.另一方面，由于算法關注的是推薦查詢與原查詢之間的相關性，但并沒有考慮推薦查詢之間的冗余性，導致推薦了一些重復的查詢，例如：“為什么曼聯(lián)不留范尼”和“曼聯(lián)不留范尼”，該問題也是當前查詢推薦算法共同面臨的問題之一.Term-Query-URL異構信息網(wǎng)絡上不同的重啟動概率λ對MAP的影響.當λ趨近于0時，系統(tǒng)是從全局的范圍選擇最為重要的查詢節(jié)點進行推薦，從而忽略了推薦查詢和當前查詢的相關性.而當λ趨近于1時，與原始查詢路徑最短的節(jié)點在推薦中就起到了關鍵性的重要，在局部查詢節(jié)點與原始查詢相關性不高的情況下，推薦性能就會急劇的下降.因此，λ的取值需要在全局和局部之間取得平衡，它的取值通常和圖的結(jié)構及數(shù)據(jù)特點有一定的關系，由圖6中可知在本文中λ=0.7時性能最優(yōu).

表2 查詢推薦示例

λ

3 結(jié)束語

本文針對當前基于日志分析和基于語義分析進行查詢推薦方法的不足展開研究，提出一種綜合利用日志信息和語義信息的Term-Query-URL異構信息網(wǎng)絡模型，使用該模型可以有效的提升檢索系統(tǒng)在稀疏查詢上的推薦性能.同時，針對沒有在查詢?nèi)罩局谐霈F(xiàn)過的查詢，采用概率語言模型衡量詞匯在原始查詢中的重要程度，把原始查詢轉(zhuǎn)化為合適的詞匯向量，從而提出了一種能直接使用本模型的進行查詢推薦的方法.

當前的查詢推薦系統(tǒng)通常只考慮推薦的查詢與原始查詢的相關性，往往忽略了查詢推薦結(jié)果的冗余性[18].要進一步提升查詢推薦系統(tǒng)的性能，需要回答以下關鍵問題：原始查詢是否含義明確？如果原始查詢含義模糊，那么與之相關的語義概念有幾個？如何為每個不同的語義概念進行查詢推薦？文獻[19]在這些方面進行了初步的嘗試，這也是我們下一步工作的重點.

[1]MEI Q,ZHOU D,CHURCH K.Query suggestion using hitting time[C]//Proceedings of the 17th ACM Conference on Information and Knowledge Management.ACM,2008: 469-478.

[2]SONG Y,HE L.Optimal rare query suggestion with implicit user feedback[C]//Proceedings of the 19th International Conference on World Wide Web.ACM,2010: 901-910.

[3]MA H,YANG H,KING I,etal.Learning latent semantic relations from clickthrough data for query suggestion[C]//Proceedings of the 17th ACM Conference on Information and Knowledge Management.ACM,2008: 709-718.

[4]BOLDI P,BONCHI F,CASTILLO C,etal.The query-flow graph: model and applications[C]//Proceedings of the 17th ACM Conference on Information and Knowledge Management.ACM,2008: 609-618．

[5]BOLDI P,BONCHI F,CASTILLO C,etal.From dango to japanese cakes: query reformulation models and patterns[C]//Proceedings of the 2009 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology-Volume 01.IEEE Computer Society,2009: 183-190.

[6]KATO M P,SAKAI T,TANAKA K.Query session data vs clickthrough data as query suggestion resources[J]//Advances in Information Retrieval:33rd European Conference on IR Resarch． ECIR 2011，2011:116-122.

[7]LAUCKNER C,HSIEH G.The presentation of health-related search results and its impact on negative emotional outcomes[C]//Proceedings of the SIGCHI Conference on Human Factors in Computing Systems.ACM,2013:333-342.

[8]LIU Y,MIAO J,ZHANG M,etal.How do users describe their information need: query recommendation based on snippet click model[J].Expert Systems with Applications,2011,38(11): 13847-13856.

[9]XUE X,CROFT W B,SMITH D A.Modeling reformulation using passage analysis[C]//Proceedings of the 19th ACM International Conference on Information and Knowledge Management.ACM,2010: 1497-1500．

[10]CRASWELL N,BILLERBECK B,FETTERLY D,etal.Robust query rewriting using anchor data[C]//Proceedings of the Sixth ACM International Conference on Web Search and Data Mining.ACM,2013: 335-344.

[11]LIAO Z,JIANG D,CHEN E,etal.Mining concept sequences from large-scale search logs for context-aware query suggestion[J].ACM Transactions on Intelligent Systems and Technology (TIST),2011,3(1): 1-17.

[12]SONG Y,ZHOU D,HE L.Query suggestion by constructing term-transition graphs[C]//Proceedings of the Fifth ACM International Conference on Web Search and Data Mining.ACM,2012: 353-362.

[13]白露,郭嘉豐,曹雷,等.基于查詢意圖的長尾查詢推薦[J].計算機學報,2013,36(3): 636-642.

BAI Lu,GUO Jia-feng,CAO Lei,etal.Long tail query recommendation based on query intent[J].Chinese Journal of Computers,2013,36(3): 636-642.(In Chinese)

[14]OZERTEM U,CHAPELLE O,DONMEZ P,etal.Learning to suggest: a machine learning framework for ranking query suggestions[C]//Proceedings of the 35th International ACM SIGIR Conference on Research and Development in Information Retrieval.ACM,2012: 25-34.

[15]LUCCHESE C,ORLANDO S,PEREGO R,etal.Identifying task-based sessions in search engine query logs[C]//Proceedings of the Fourth ACM International Conference on Web Search and Data Mining.ACM,2011: 277-286.

[16]ZHAI C X.A note on the expectation-maximization (em) algorithm[C]//10th Int.2004: 403-410.

[17]BHATIA S,MAJUMDAR D,MITRA P.Query suggestions in the absence of query logs[C]//Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval.ACM,2011: 795-804.

[18]SONG Y,ZHOU D,HE L.Post-ranking query suggestion by diversifying search results[C]//Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval.ACM,2011: 815-824.

[19]李亞楠,王斌,李錦濤,等.給互聯(lián)網(wǎng)建立索引: 基于詞關系網(wǎng)絡的智能查詢推薦[J].軟件學報,2011,22(8): 1771-1784.

LI Ya-nan,WANG Bin,LI Jin-tao,etal.Indexing the world wide web: intelligence query suggestion based on term relation network[J].Journal of Software,2011,22(8): 1771-1784.(In Chinese)