基于TermQueryURL異構(gòu)信息網(wǎng)絡(luò)的查詢推薦

劉鈺峰+李仁發(fā)

文章編號(hào)：16742974(2014)05010607

收稿日期：20130904

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目（61173036）

作者簡(jiǎn)介：劉鈺峰（1974-），男，湖南邵陽(yáng)人，湖南大學(xué)博士研究生

通訊聯(lián)系人，Email:fx_yfliu@163.com

摘 要：查詢推薦是一種幫助搜索引擎更好的理解用戶檢索需求的方法.基于查詢的上下文片段訓(xùn)練詞匯和查詢之間的語(yǔ)義關(guān)系，同時(shí)結(jié)合查詢和URL的點(diǎn)擊圖以及查詢中的序列行為構(gòu)建TermQueryURL異構(gòu)信息網(wǎng)絡(luò)，采用重啟動(dòng)隨機(jī)游走(Random Walk with Restart，RWR)進(jìn)行查詢推薦.綜合利用語(yǔ)義信息和日志信息，提高了稀疏查詢的推薦效果.基于概率語(yǔ)言模型構(gòu)造查詢的詞匯向量，可以為新的查詢進(jìn)行查詢推薦.在大規(guī)模商業(yè)搜索引擎查詢?nèi)罩旧系膶?shí)驗(yàn)表明本文方法相比傳統(tǒng)的查詢推薦方法性能提升約為3%~10%.

關(guān)鍵詞：信息檢索；查詢推薦；點(diǎn)擊日志；重啟動(dòng)隨機(jī)游走

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A

Query Suggestion by Constructing Heterogeneous 

TermQueryURL Information Network



LIU Yufeng1 ,LI Renfa1,2



(1．School of Information Science and Engineering, Hunan Univ, Changsha,Hunan 410082,China;

2．Embedded System and Networking Laboratory, Hunan Univ, Changsha,Hunan 410082,China)

Abstract:Query suggestion is an interactive approach for search engines to better understand user information need. A TermQuery bipartite graph was trained by extracting semantic relationships from snippet clicked by query. With the combination of QueryURL graph and QueryFlow graph, a heterogeneous TermQueryURL information network was constructed. Random walk with restart (RWR) was performed on the information network for query suggestion. The relevance of long tail query suggestion was greatly improved by taking into account semantic information and log information. Term vector of query was constructed on the basis of probabilistic language model for query suggestion of new query. The experiment results have shown that our approach outperforms baseline methods by about 3% to 10%.

Key words: information retrieval; query suggestion; clickthrough data; random walk with restart



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

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

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

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

1 基于TermQueryURL異構(gòu)信息網(wǎng)絡(luò)的

查詢推薦標(biāo)題

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

1.1 TermQuery二部圖模型

使用在查詢上點(diǎn)擊的文檔摘要片段訓(xùn)練詞匯和查詢之間的二部圖，該圖示例請(qǐng)參見(jiàn)圖1.基于TermQuery的二部圖可以表示為三元組GTQ=(T,Q,ETQ)，其中T表示為由詞匯組成的非空頂點(diǎn)集，Q表示由查詢構(gòu)成的非空頂點(diǎn)集，ETQ為連接詞匯和查詢的邊的集合，即ET×Q，在詞匯和詞匯之間，查詢和查詢之間沒(méi)有邊.設(shè)w:T×Q→R+表示權(quán)重函數(shù)，w(i,j)表示詞匯ti和查詢qj之間關(guān)聯(lián)的概率，如果兩者之間沒(méi)有關(guān)聯(lián)則wTQ(i,j)=0.

可以采用偽反饋文檔來(lái)訓(xùn)練得到wTQ(i,j)，但是這就必須依賴于偽反饋文檔的質(zhì)量.通常認(rèn)為，用戶點(diǎn)擊的上下文摘要片段和查詢?cè)~之間存在著更為緊密的關(guān)系，因此本文采用查詢?cè)~和點(diǎn)擊的文檔摘要片段之間的關(guān)系來(lái)得到wTQ(i,j).假設(shè)用戶發(fā)出查詢q時(shí)，點(diǎn)擊的文檔摘要的集合為sq，系統(tǒng)日志中總的摘要集合為S={s1,s2,…,sk}，則令：

wTQ(t,q)=tfidf(t,sq)∑t′∈sqtfidf(t,sq) (1)

其中，tfidf(t,sq)=tf(t,sq)×idf(t)，其中tf(t,sq)表示 詞匯t在sq中的詞頻.idf(t)為倒轉(zhuǎn)文檔頻率（Inverse Document Frequency），idf(t)=log (ndf(t)).其中n為摘要S的數(shù)目，df(t)為出現(xiàn)詞匯t的摘要數(shù)目.在此引入idf(t)的目的是提高與當(dāng)前查詢相關(guān)的主題詞匯的權(quán)重，降低常用詞的權(quán)重.



圖1 TermQuery二部圖

Fig.1 TermQuery bipartite graph



1.2 QueryFlow圖模型

QueryFlow圖是一種用來(lái)描述查詢序列行為的有向圖[4]，它的基本思想是當(dāng)查詢qi和查詢qj屬于同一個(gè)查詢?nèi)蝿?wù)時(shí)，它們之間應(yīng)該存在一條有向邊.QueryFlow圖的示例請(qǐng)參見(jiàn)圖2.QueryFlow圖可以定義為GQQ=(Q,EQQ)，其中Q表示由查詢構(gòu)成的非空頂點(diǎn)集，E為連接查詢和查詢的邊的集合，EQQQ×Q.設(shè)wQQ:Q×Q→R+表示權(quán)重函數(shù)，wQQ(i,j)表示查詢qi和查詢qj之間關(guān)聯(lián)的概率，如果兩者之間沒(méi)有關(guān)聯(lián)則wQQ(i,j)=0.



圖2 QueryFlow圖

Fig.2QueryFlow graph

wQQ(i,j)=psession(qj|qi)=f(qi,qj)f(qi)（2）

psession(qj|qi)描述了從查詢qi到查詢qj的轉(zhuǎn)移概率.在構(gòu)造QueryFlow圖時(shí)，通常使用會(huì)話（Session）的概念來(lái)判斷兩個(gè)查詢是否屬于同一個(gè)任務(wù)， 可以基于時(shí)間閾值或語(yǔ)義概率來(lái)判斷同一個(gè)用戶發(fā)出的連續(xù)的查詢是否屬于同一個(gè)Session［15］.f(qi,qj)表示同一個(gè)查詢?nèi)蝿?wù)中，查詢qj跟隨查詢qi 出現(xiàn)的次數(shù)，其中f(qi)=∑qk∈Qf(qi,qk)用于對(duì)w(i,j)進(jìn)行規(guī)范化.可以觀察到查詢qi和查詢qj之間的轉(zhuǎn)移概率并不對(duì)稱，因此QueryFlow圖是一個(gè)有向圖.如果按照文獻(xiàn)[5]中的方法估計(jì)查詢之間的轉(zhuǎn)移概率，則可以構(gòu)造無(wú)向的QueryFlow圖.

1.3 TermQueryURL異構(gòu)信息網(wǎng)絡(luò)模型

查詢和URL之間構(gòu)成了另一個(gè)二部圖GQU=(Q,U,EQU)，該圖通常被稱為clickthrough圖[1-2]，示例請(qǐng)參見(jiàn)圖3.其中Q表示由查詢構(gòu)成的非空頂點(diǎn)集，U表示由URL構(gòu)成的非空頂點(diǎn)集，EQU為連接查詢和URL的邊的集合，即EQU={|iQ,jU}.邊的權(quán)重wQU(i,j)的取值為cf(qi,uj)cf(qi) ，cf(qi,uj)表示通過(guò)查詢qi點(diǎn)擊URLuj的次數(shù)，cf(qi)表示通過(guò)查詢qi總的點(diǎn)擊次數(shù).



圖3 QueryURL二部圖

Fig.3 QueryURL bipartite graph

我們把以上討論的三種關(guān)系統(tǒng)一到一個(gè)模型中進(jìn)行分析，考慮包含Term，Query，URL3種不同節(jié)點(diǎn)的異構(gòu)信息網(wǎng)絡(luò)圖GTQU={V,E}，其中V=T∪Q∪U，E=ETQ∪EQQ∪EQU.以A來(lái)表示GTQ的鄰接矩陣，使用B表示GQU的鄰接矩陣，使用C表示GQQ的鄰接矩陣，則GTQU的鄰接矩陣如下所示：

W=TQUTQU0αA0αATγCβB0βBT0(3)

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

Mij=Wij∑kWkj（4）

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

1.4 基于TermQueryURL異構(gòu)信息網(wǎng)絡(luò)的查詢

推薦

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

q=［qt,qq,qu］T（5）

如果q是GTQU中對(duì)應(yīng)的第i個(gè)元素，令qi=1，其他對(duì)應(yīng)的值都為0，很顯然，此時(shí)qt和qu都是零向量.在給定了初始的查詢向量的情況下，在GTQU上的重啟動(dòng)隨機(jī)游走過(guò)程可以描述為：從GTQU上的節(jié)點(diǎn)q出發(fā)，它按照概率λ選擇重新從節(jié)點(diǎn)q出發(fā)，或者按照概率1－λ選擇訪問(wèn)q的鄰居節(jié)點(diǎn)并開(kāi)始新一輪的隨機(jī)游走，不斷地重復(fù)以上行為，直到在某一時(shí)刻停留在任意節(jié)點(diǎn)的概率保持穩(wěn)定.該過(guò)程可以描述為：

p=(1－λ)Mp+λq（6）

不斷地迭代計(jì)算式（6），p將會(huì)達(dá)到一個(gè)穩(wěn)定的狀態(tài)，p中pq的值可以作為衡量與初始查詢相關(guān)度的標(biāo)準(zhǔn)，排名靠前的查詢節(jié)點(diǎn)用來(lái)作為q的查詢推薦.

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

pt=(1－λ)αApq+λqt

pq=(1－λ)(αATpt+βBpu+γCpq)+λqq

pu=(1－λ)βBTpq+γqu（7）

基于日志方法進(jìn)行查詢推薦的前提是查詢q必須是Q中的節(jié)點(diǎn)，本文方法可以克服這一問(wèn)題.設(shè)查詢?yōu)楠={t1,t2,…,tm}，且qQ，因此初始的查詢向量q中對(duì)應(yīng)的qq為零向量，但是我們可以根據(jù)查詢向量的語(yǔ)言模型構(gòu)造qt. 最簡(jiǎn)單的辦法就是令p(ti)=tf(ti,q)tf(q)，tf(ti,q)表示ti在q中出現(xiàn)的次數(shù)，tf(q)表示q中詞匯的總數(shù).但這種簡(jiǎn)單的方案存在一個(gè)問(wèn)題，即給予了查詢中一些區(qū)分能力不強(qiáng)的通用詞過(guò)高的概率.例如當(dāng)用戶發(fā)出查詢“小夜曲下載”，由于“下載”是一個(gè)高頻詞，如果給予“下載”和“小夜曲”相同的地位，就會(huì)導(dǎo)致用戶查詢的意圖出現(xiàn)漂移，傾向于高頻的通用詞.因此在構(gòu)造查詢向量時(shí)，我們應(yīng)該給予查詢主題詞更高的估值，同時(shí)降低通用背景詞的估值.為此，可以認(rèn)為當(dāng)前的查詢模型是由查詢主題模型和背景模型構(gòu)成的混合模型，即：

p(t|q)=(1－λ)p(t|θq)+λp(t|θc) （8）

其中λ為平滑參數(shù)，λ∈［0,1］，p(t|θc)為詞匯t在所有查詢集合上的極大似然估計(jì)，它相當(dāng)于查詢的背景模型.在固定λ的情況下需要估計(jì)的就只有p(t|q)了，EM算法的求解過(guò)程可參看相關(guān)文獻(xiàn)[16]，迭代計(jì)算的過(guò)程為：

E步：

p(zj=1)=λp(t|θC)λp(t|θc)+(1－λ)p(t|θ(n)q) （9）

M步：

p(t|θ(n+1)q)=(1－p(zj=1))p(t|θq)∑t′∈q(1－p(zw=1))p(t′|θq)（10）

其中的zj為引入隱含變量：

zj=1tj由背景模型θc產(chǎn)生

0其他（11）

迭代達(dá)到穩(wěn)定值的時(shí)候，得到的p(t|θ(n+1)q)就是在查詢主題模型中觀測(cè)到的概率，該方法能有效的提升主題詞在主題模型中的概率，降低通用的背景詞的概率.以“小夜曲下載”為例，沒(méi)有使用混合模型時(shí)p(小夜曲|q)=p(下載|q)=0.5，使用混合模型之后，在搜狗搜索引擎2008年6月的日志記錄上得到的結(jié)果為p(小夜曲|q)=0.893，p(下載|q)=0.107.

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

算法1：基于TermQueryURL異構(gòu)信息網(wǎng)絡(luò)的查詢推薦算法．

輸入：TermQueryURL異構(gòu)信息網(wǎng)絡(luò)GTQU上的矩陣M及原始查詢q．

輸出：與原始查詢q相關(guān)的查詢推薦序列．

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

2)令qt和qu為零向量，q是GTQU中查詢對(duì)應(yīng)的第i個(gè)元素，令qqi=1，其他對(duì)應(yīng)的值都為0，由式（5）得到初始向量q，跳轉(zhuǎn)至4）.

3)根據(jù)式（8）計(jì)算q中詞匯在qt中的權(quán)重，令qu和qq為零向量，由（5）式得到初始向量q，跳轉(zhuǎn)至4）.

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

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

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

2 實(shí)驗(yàn)與分析

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

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

2.2 實(shí)驗(yàn)設(shè)計(jì)及結(jié)果分析

使用的top N的精度P@N和MAP(Mean Average Precision)作為評(píng)價(jià)指標(biāo)，給定了一個(gè)查詢q，系統(tǒng)給出j個(gè)推薦的查詢.

P(j)=#ofrelevantqueriesj（12）

P@N=∑Ki=1p(N)K（13）

其中K是查詢測(cè)試集的總數(shù)，在我們的實(shí)驗(yàn)中K=200，N=5.在文獻(xiàn)[2]中MAP被定義為所有查詢的AvgP的平均值，其中：

AvgP=∑Mj=1(P(j)×φ(j))RQ（14）

RQ為推薦查詢中與原始查詢相關(guān)查詢的總數(shù).φ(j)是一個(gè)指示函數(shù)，如果推薦的第j個(gè)查詢與原始查詢相關(guān)，則取1，否則為0. 

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

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

Tab．1 Performance of the six algorithms 

on MAP and P@5

頻繁查詢稀疏查詢

P@5

MAP

P@5

MAP

Baseline

0.521 429

0.576 874

0.423 205

0.498 037

RWPseudo

0.567 183

0.631 288

0.517 005

0.572 239

QueryFlow

0.573 372

0.629 265

0.520 173

0.580 076

Probabilistic

0.529 917

0.584 403

0.525 582

0.587 138

基于查詢意圖的方法

0.541 266

0.613 271

0.560 793

0.621 772

α=0.2,β=0.4,

γ=0.4

0.592 312

0.658 765

0.578 776

0.645 531

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

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



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

Fig.4 P@N of different algorithms on frequent queries



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

Fig.5 P@N of different algorithms on long tail queries

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

表2 查詢推薦示例

Tab．2 Examples of query suggestions

查詢

推薦查詢

oracle 視頻

oracle視頻教程， oracle視頻下載，北大青鳥(niǎo)oracle視頻教程，尚學(xué)堂+oracle，oracle +課件

地震 預(yù)報(bào)

美國(guó)預(yù)報(bào)汶川地震，四川汶川地震預(yù)報(bào)，四川地震預(yù)報(bào)網(wǎng)，地震預(yù)報(bào)網(wǎng)，政府地震預(yù)報(bào)

李小龍 功夫片

電影++李小龍專輯，李小龍傳奇電影，李小龍系列電影，李小龍+電影下載，李小龍歷年電影

朱棣 朱允文

明朝皇帝朱允文與朱棣，朱棣，燕王朱棣，朱棣篡位的證據(jù)，朱棣的故事

曼聯(lián) 范尼

為什么曼聯(lián)不留范尼，范尼在曼聯(lián)怎么了，曼聯(lián)不留范尼，曼聯(lián)中文網(wǎng)，曼聯(lián)的核心球員是誰(shuí)

λ

圖6重啟動(dòng)概率λ對(duì)MAP的影響?yīng)?/p>

Fig.6 The effect of varying parameters

restart probability λ

3 結(jié)束語(yǔ)

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

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

參考文獻(xiàn)

［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, et al. 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, et al. 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, et al. 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, et al. 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, et al. 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, et al. 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］白露, 郭嘉豐, 曹雷, 等. 基于查詢意圖的長(zhǎng)尾查詢推薦[J]. 計(jì)算機(jī)學(xué)報(bào), 2013, 36(3): 636-642.

BAI Lu, GUO Jiafeng, CAO Lei, et al. 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, et al. 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, et al. 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)建立索引: 基于詞關(guān)系網(wǎng)絡(luò)的智能查詢推薦[J]. 軟件學(xué)報(bào), 2011, 22(8): 1771-1784.

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

［5］ BOLDI P, BONCHI F, CASTILLO C, et al. 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, et al. 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, et al. 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, et al. 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］白露, 郭嘉豐, 曹雷, 等. 基于查詢意圖的長(zhǎng)尾查詢推薦[J]. 計(jì)算機(jī)學(xué)報(bào), 2013, 36(3): 636-642.

BAI Lu, GUO Jiafeng, CAO Lei, et al. 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, et al. 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, et al. 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)建立索引: 基于詞關(guān)系網(wǎng)絡(luò)的智能查詢推薦[J]. 軟件學(xué)報(bào), 2011, 22(8): 1771-1784.

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

［5］ BOLDI P, BONCHI F, CASTILLO C, et al. 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, et al. 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, et al. 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, et al. 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］白露, 郭嘉豐, 曹雷, 等. 基于查詢意圖的長(zhǎng)尾查詢推薦[J]. 計(jì)算機(jī)學(xué)報(bào), 2013, 36(3): 636-642.

BAI Lu, GUO Jiafeng, CAO Lei, et al. 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, et al. 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, et al. 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)建立索引: 基于詞關(guān)系網(wǎng)絡(luò)的智能查詢推薦[J]. 軟件學(xué)報(bào), 2011, 22(8): 1771-1784.

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