李競飛，商振國，張　鵬，宋大為

天津大學(xué) 天津市認(rèn)知計算與應(yīng)用重點實驗室，天津 300072

融合用戶實時搜索狀態(tài)的自適應(yīng)查詢推薦模型*

李競飛，商振國，張鵬+，宋大為

天津大學(xué) 天津市認(rèn)知計算與應(yīng)用重點實驗室，天津 300072

傳統(tǒng)的查詢推薦算法通過挖掘查詢?nèi)罩緸橛脩敉扑]查詢詞。通?，F(xiàn)存模型只考慮原始查詢詞與推薦詞之間的關(guān)系（例如語義相似性或相關(guān)性等），沒有考慮用戶在搜索過程中的滿意度情況。針對用戶在搜索過程中表現(xiàn)出的不同滿意度狀態(tài)，提出了一個查詢推薦基本假設(shè)，并通過開展在線用戶問卷調(diào)查，驗證了這一假設(shè)?；谙鄳?yīng)的假設(shè)，提出了一種基于用戶搜索滿意度狀態(tài)的自適應(yīng)查詢推薦模型，該模型可以為用戶智能推薦不同種類的查詢詞。當(dāng)用戶對搜索結(jié)果滿意時，模型將為用戶提供更加新穎的推薦詞；當(dāng)用戶對搜索結(jié)果不滿意時，模型將為用戶提供一些增強信息表示能力的查詢詞。大規(guī)模日志實驗表明，提出的推薦模型顯著優(yōu)于傳統(tǒng)的查詢流圖模型，證明了所提模型的有效性。

查詢推薦；查詢流圖；搜索狀態(tài)；滿意度

1　引言

查詢推薦已經(jīng)成為現(xiàn)代搜索引擎（例如百度、必應(yīng)和谷歌等）必備的功能之一。雖然現(xiàn)有的查詢推薦算法已經(jīng)能夠滿足用戶的基本需求，但是查詢推薦的準(zhǔn)確性和智能性還有待進一步提升。為了提高查詢推薦質(zhì)量，研究人員已經(jīng)提出了大量的查詢推薦模型[1-4]。許多經(jīng)典的查詢推薦模型是基于查詢?nèi)罩咎岢龅?，例如查詢流圖模型（query flow graph，QFG）[3]。然而，現(xiàn)有的推薦模型有一個明顯的缺陷，即在為用戶推薦查詢詞時，并沒有考慮用戶當(dāng)前的搜索狀態(tài)。本文所指的搜索狀態(tài)是用戶搜索信息過程中，表現(xiàn)出來的對搜索結(jié)果是否滿意的一種實時狀態(tài)。為了解決這個問題，本文提出了一種基于查詢流圖模型的新穎查詢推薦模型，可以根據(jù)用戶當(dāng)前的搜索狀態(tài)提供相對原始查詢更新穎的或者增強相關(guān)性的推薦詞。

經(jīng)典的查詢流圖模型是一種以查詢?yōu)楣?jié)點，以查詢之間的轉(zhuǎn)移關(guān)系為邊的有向圖?；诓樵兞鲌D的推薦模型可以建模全局用戶的查詢轉(zhuǎn)移關(guān)系，反應(yīng)查詢推薦過程中的群體智慧。然而基礎(chǔ)的查詢流圖僅考慮了原始查詢與候選推薦詞之間的靜態(tài)轉(zhuǎn)移關(guān)系，并沒有考慮用戶實時的搜索滿意度狀態(tài)。

為了使系統(tǒng)推薦的查詢詞能自然地適應(yīng)用戶在不同狀態(tài)下的信息表示需求，本文根據(jù)用戶的實時搜索狀態(tài)，對每一個候選推薦詞重新賦權(quán)重，從而為用戶推薦期望的查詢詞。

為了實現(xiàn)這一目標(biāo)，本文提出了一個假設(shè)，即搜索引擎應(yīng)該依據(jù)用戶不同的交互狀態(tài)提供不同類型的查詢推薦詞。設(shè)想一個真實的搜索場景（如圖1所示），一個用戶通常輸入一個原始查詢詞作為一次搜索任務(wù)的開始，搜索引擎返回一系列結(jié)果。隨后，用戶基于自己的信息需求查看若干可能相關(guān)的內(nèi)容。如果用戶對當(dāng)前的搜索結(jié)果已經(jīng)滿意，他可能會中斷當(dāng)前的搜索任務(wù)，也可能會提交另一個新的查詢；如果用戶對當(dāng)前的結(jié)果不滿意，他將很有可能修改原始的查詢詞，重新搜索以期獲得更好的搜索結(jié)果；另一種極端情況是用戶因?qū)Ξ?dāng)前結(jié)果極度失望而放棄搜索或轉(zhuǎn)向其他搜索引擎。通過分析日志發(fā)現(xiàn)，這種人機交互行為會頻繁出現(xiàn)，本文3.2節(jié)的用戶實驗也進一步證實了這種現(xiàn)象的存在。本文致力于提出一種基于用戶搜索滿意度的方法建模這種人機交互行為，從而為用戶提供高質(zhì)量的查詢推薦詞，以引導(dǎo)用戶開展高效的探索式查詢。

Fig.1　Interactive process of user with a search engine圖1　用戶與搜索引擎交互過程

2　文獻綜述

在查詢推薦領(lǐng)域，已經(jīng)存在大量的相關(guān)工作。按照查詢推薦候選詞的來源，可以將現(xiàn)有工作大致分為基于查詢?nèi)罩镜耐扑][1,5-6]和基于文本集的推薦[7]。按照模型方法分類，現(xiàn)有工作可以分為基于圖的模型[4]和基于排序?qū)W習(xí)的模型[8]。本文提出的自適應(yīng)推薦模型是以查詢?nèi)罩緸橥扑]詞來源，是基于圖的推薦模型。

圖模型可以方便地用于挖掘日志中查詢之間的關(guān)系，包括轉(zhuǎn)移關(guān)系、語義相似關(guān)系等。進而查詢之間的關(guān)系可以用于未來的查詢推薦。Boldi等人開創(chuàng)性地提出了查詢流圖模型[3]，該模型已經(jīng)廣泛應(yīng)用于基于日志的推薦方法中，并且取得了很好的效果。后續(xù)有一系列基于查詢流圖的工作[9-11]。例如，Adeyanju等人利用查詢流圖的思想對靜態(tài)概念層次模型進行動態(tài)更新，并用于局域網(wǎng)查詢推薦[1]。此外，點擊二分圖（click bipartite graph）也是一種廣泛應(yīng)用的查詢推薦方法[12-14]，它基于不同用戶可能利用不同的查詢詞來搜索同一網(wǎng)頁的事實，挖掘查詢之間的語義相似性。例如，Baeza-Yates等人提出了基于二分圖的迭代聚類方法進行查詢推薦[6]。

基于排序?qū)W習(xí)的推薦模型主要思想是利用從日志中提取大量的特征對查詢候選詞進行排序。Joachims利用排序支持向量機（ranking support vector machine，RankSVM）對聚類得到的候選推薦詞進行排序[15]。Liu等人針對難查詢（difficult query）利用排序?qū)W習(xí)算法（learning to rank）直接對候選查詢詞的搜索結(jié)果進行優(yōu)化，進而達到對候選詞進行排序的目的[8]。

現(xiàn)有推薦模型中存在的一個重要問題是，在為候選詞排序時，沒有考慮用戶當(dāng)前的滿意度狀態(tài)，忽略了用戶可能在一些條件下更喜歡相似的推薦詞，而一些情況下更喜歡新穎的推薦詞的事實。針對這個問題，本文改進了現(xiàn)有的查詢流圖，探索性地提出了基于用戶滿意度狀態(tài)的推薦模型。

3　基本假設(shè)及驗證

3.1基本假設(shè)

本文提出的自適應(yīng)查詢推薦模型，建立在兩個基本假設(shè)基礎(chǔ)上。

假設(shè)1當(dāng)用戶對當(dāng)前搜索結(jié)果滿意時，希望獲得新穎的推薦詞；相反當(dāng)用戶對當(dāng)前搜索結(jié)果不滿意時，希望修改當(dāng)前查詢并且增強當(dāng)前查詢的相關(guān)性表示能力。

假設(shè)2用戶當(dāng)前的搜索滿意度可以通過用戶行為（例如點擊和翻頁等）進行估計。

第一個假設(shè)是為了表明用戶在不同搜索狀態(tài)下希望獲取不同類型的推薦詞。第二個假設(shè)是希望可以探索性地估計用戶搜索滿意度的量化指標(biāo)。為了驗證這兩個基本假設(shè)，本文首先利用第三方問卷調(diào)查平臺（問卷星）開展充分的用戶實驗。下面詳細(xì)介紹用戶實驗的情況。

3.2用戶實驗設(shè)計及結(jié)果分析

為了驗證本文提出的假設(shè)，首先在互聯(lián)網(wǎng)的真實環(huán)境下進行了問卷調(diào)查用戶實驗。問卷調(diào)查的題目為《關(guān)于用戶使用搜索引擎的行為習(xí)慣調(diào)查》，其中包含9道單項選擇題，1道多項選擇題。實驗采用第三方問卷調(diào)查平臺（問卷星是國內(nèi)知名的網(wǎng)絡(luò)調(diào)查問卷平臺），以保證此次用戶實驗的公平、公正和公開性。在實驗過程中，設(shè)定了防重復(fù)填寫機制，通過限制IP設(shè)定同一手機、電腦只能參與一次調(diào)查。每一次調(diào)查完畢后，系統(tǒng)給予用戶一定的激勵。為了保證問卷調(diào)查的質(zhì)量和結(jié)果的可靠性，本文設(shè)定用戶作答問卷的總用時長最少為30 s。本次用戶問卷調(diào)查共收到174份調(diào)查問卷，過濾保留其中154份有效答卷用于結(jié)果分析。

Fig.2　Questionnaires results of user study圖2　部分調(diào)查問卷結(jié)果

通過對有效問卷結(jié)果進行分析發(fā)現(xiàn)（如圖2所示）：（1）問卷用戶中，74.68%的用戶為本科生，17.53%的用戶為碩士生，其他學(xué)歷的用戶占7.79%，基本覆蓋了所有學(xué)歷層次的用戶。（2）93.51%的用戶頻繁使用搜索引擎，說明搜索引擎對用戶十分重要。（3）關(guān)于用戶對查詢推薦服務(wù)的期待，當(dāng)用戶對當(dāng)前搜索結(jié)果感到滿意時，53.9%的用戶會選擇與當(dāng)前查詢相關(guān)且新穎的查詢詞開始下一次的查詢；當(dāng)用戶對搜索結(jié)果不滿意時，只有14.94%的用戶選擇新穎的推薦詞，而85.06%的用戶希望修改當(dāng)前查詢，并且獲得增強當(dāng)前信息表達能力的推薦詞。這直接驗證了本文的假設(shè)1，當(dāng)用戶的當(dāng)前搜索滿意度狀態(tài)不同時，應(yīng)推薦不同類型的查詢推薦詞給用戶。（4）針對用戶對當(dāng)前滿意度的判別，37.66%的用戶認(rèn)為在點擊的網(wǎng)頁上停留超過30 s即為滿意；51.95%的用戶認(rèn)為在當(dāng)前網(wǎng)頁中進行了選中、復(fù)制等操作為滿意的標(biāo)志。

本文的實驗數(shù)據(jù)基于必應(yīng)搜索日志，只記錄了用戶在當(dāng)前網(wǎng)頁停留的時長，直觀上當(dāng)用戶在網(wǎng)頁進行閱讀、選中和復(fù)制等行為用時一般會超過30 s，因此選擇當(dāng)用戶點擊并且在當(dāng)前網(wǎng)頁停留超過30 s作為用戶對一個結(jié)果滿意度的標(biāo)識；把用戶的翻頁行為作為折算因子，直觀認(rèn)識是當(dāng)用戶有翻頁行為時，表明用戶對當(dāng)前查詢結(jié)果不滿意，越往后翻頁表示滿意度越低，這一直觀認(rèn)識是基于用戶通過搜索引擎期望得到查詢結(jié)果是準(zhǔn)確而完整的。若用戶期望獲得更為詳細(xì)或全面的答案往往需要點擊相關(guān)網(wǎng)頁，并在相關(guān)網(wǎng)頁內(nèi)進行詳細(xì)瀏覽。本文提及的用戶翻頁行為指用戶在綜合搜索引擎結(jié)果頁的翻頁行為，而非在一些專業(yè)搜索引擎中的翻頁瀏覽行為。本文探索性地通過分析用戶的點擊行為和翻頁行為提出了估計用戶當(dāng)前滿意度的量化指標(biāo)，也就驗證了假設(shè)2。

4　自適應(yīng)查詢推薦模型

以下首先介紹了查詢流圖的基本概念，隨后提出了基于用戶滿意度狀態(tài)的自適應(yīng)的查詢推薦模型框架。接下來，形式化了構(gòu)建推薦詞候選集的方法，探索性地給出了一種基于用戶滿意度狀態(tài)建模方法，以解決框架中的一個關(guān)鍵問題，即對用戶當(dāng)前搜索滿意度估計。最后提出了自適應(yīng)的推薦詞排序模型。

4.1查詢流圖

查詢流圖是一種常用的日志挖掘模型[3]。它定義為一個有向圖Gqf=(V,E,w)，其中節(jié)點集合V=Q∪{s,t}，表示所有用戶在歷史上提交的所有查詢Q和兩個特殊的節(jié)點s和t，s和t分別代表一個查詢鏈的開始和結(jié)束節(jié)點；有向邊E∈V×V連接同一個查詢會話中兩個前后鄰接的查詢；權(quán)重w∈(0,1]，連接一對查詢(q,q′)的邊的權(quán)重表示為w(q,q′)：

其中，f(q)為查詢q在歷史日志中出現(xiàn)過的頻率；f(q,q′)為查詢?nèi)罩局杏^測到由查詢q轉(zhuǎn)移（改寫）為q′的次數(shù)。在查詢推薦模型中，每一個原始查詢將匹配圖中的一個查詢節(jié)點，匹配節(jié)點的出邊節(jié)點，將作為候選推薦詞集合。然后按照各自邊的權(quán)重排序，選取前K個節(jié)點對應(yīng)的查詢詞推薦給用戶。

本文在構(gòu)建查詢流圖時，對日志中所有查詢詞進行詞干化（stemming）處理，以保證相同單詞的不同形式可以完全匹配。本文構(gòu)建查詢推薦模型以會話為基礎(chǔ)，把在30 min之內(nèi)的所有查詢詞劃分為一次會話。

4.2模型框架

根據(jù)第3章中提出的推薦假設(shè)以及相應(yīng)的用戶調(diào)查結(jié)果，理想的推薦模型應(yīng)該針對用戶當(dāng)前的搜索狀態(tài)，為用戶推薦合理的查詢詞。為了實現(xiàn)自適應(yīng)地推薦查詢詞，本節(jié)提出了一個形式化的模型框架。首先通過查詢流圖模型獲取一組候選查詢推薦詞，同時估計得到用戶當(dāng)前的滿意度狀態(tài)，然后基于用戶滿意度狀態(tài)對推薦詞候選集進行排序，最后選取前K個候選詞推薦給用戶。自適應(yīng)查詢推薦模型框架如圖3所示。

Fig.3　Auto-adaptive query recommendation framework圖3　自適應(yīng)查詢推薦模型框架

為了實現(xiàn)模型的自適應(yīng)推薦目標(biāo)，需要解決以下3個問題：第一，如何獲取足夠多的相關(guān)候選推薦詞；第二，如何估計用戶當(dāng)前的滿意度狀態(tài)；第三，如何根據(jù)用戶滿意度對候選推薦詞進行排序，為用戶推薦高質(zhì)量的查詢詞。下面將分別詳細(xì)介紹3個問題的解決算法。

4.3候選推薦詞集合構(gòu)建

本文采用的候選推薦詞集合由兩類節(jié)點組成。第一類節(jié)點是與原始查詢qo模糊匹配得到的節(jié)點(No)，通過查卡德系數(shù)（Jaccard index）[16]為每一個節(jié)點賦予初始得分Score(No)，具體定義如下：

其中，J(?)是計算兩個集合之間查卡德系數(shù)的函數(shù)，查卡德系數(shù)可以衡量兩個集合之間的相似度；qo表示一個查詢（或節(jié)點）的單詞集合；No表示圖中匹配節(jié)點的單詞集合。第二類節(jié)點是由第一類節(jié)點在圖中的出邊決定的全部節(jié)點(Noe)，每個節(jié)點的初始得分由父節(jié)點的初始得分和相應(yīng)邊的權(quán)重相乘得到。這樣，遠離原始查詢的推薦節(jié)點得分將得到相應(yīng)的懲罰，具體形式為：

其中，weight(No,Noe)為兩個節(jié)點之間邊的權(quán)重。兩類節(jié)點融合之后作為候選推薦詞集合，其中移除重復(fù)的節(jié)點。

4.4用戶搜索狀態(tài)建模

本文通過用戶的點擊行為和翻頁行為來估計用戶對當(dāng)前查詢結(jié)果的滿意度狀態(tài)。為了更準(zhǔn)確地建模用戶的點擊行為，本文采用廣泛接受的停留時間點擊模型來預(yù)測用戶對一個查詢結(jié)果（網(wǎng)頁）的滿意度[17]。點擊模型規(guī)定，當(dāng)用戶點擊一個網(wǎng)頁并在這個網(wǎng)頁上停留時間超過30 s作為滿意點擊。本文第3章中所做的用戶調(diào)查，也可說明30 s的停留時間可以作為用戶滿意度的一個標(biāo)識。

為了衡量用戶對整個查詢列表的滿意度，本文基于平均準(zhǔn)確率（average precision，AP）[18]的計算方法定義了用戶對當(dāng)前結(jié)果的滿意度得分SAT(qo)。在計算時，滿意點擊的網(wǎng)頁被看作是相關(guān)文檔。具體計算如下：

其中，AP(qo)是當(dāng)前查詢的平均準(zhǔn)確率；n是用戶當(dāng)前所在的搜索結(jié)果頁碼（考慮用戶的翻頁行為，并且在用戶每次翻頁時都會觸發(fā)查詢推薦事件）；lb(n+1)是折扣因子。本文假設(shè)用戶翻頁越多對當(dāng)前查詢結(jié)果的滿意度就越低。AP(qo)的具體計算方法如下：

為了估計式（4）中的參數(shù)，在實驗數(shù)據(jù)集的規(guī)模上計算了兩個鄰接查詢詞AP值的浮動分布概率和平均準(zhǔn)確率的變動幅度，如表1所示。

Table 1　Difference ofAP between adjacent queries表1 相鄰查詢的不同AP值

將表1中統(tǒng)計得到的數(shù)據(jù)帶入式（4）可以化簡得到當(dāng)前查詢與鄰接前一個查詢詞的AP值關(guān)系為AP(qo)=1.112 2×AP(qpre)。在實際計算中，當(dāng)前一個查詢詞的AP值也無法估計時，本文用歷史搜索日志的平均AP值(AP=0.324 2)來估計當(dāng)前查詢的AP值。

4.5自適應(yīng)排序算法

本節(jié)介紹自適應(yīng)推薦排序算法。當(dāng)用戶提交一個原始查詢qo時，依據(jù)用戶對當(dāng)前搜索結(jié)果的滿意度狀態(tài)給出推薦詞，即通過自適應(yīng)排序算法給出最后每個候選詞的分?jǐn)?shù)并排序。對于每一個在候選集合中的推薦詞s，定義其自適應(yīng)排序算法的得分Scoreadaptive(s)如下：

其中，novelty(s)和similarity(s)分別表示每一個候選詞的新穎性和相似性；Score(s)表示候選詞s與原始查詢qo的初始匹配得分。

通過式（5），可以很直觀地看到，當(dāng)用戶滿足于原始查詢時，搜索引擎會給出一些新穎性更強的候選詞作為推薦查詢詞。反之，當(dāng)用戶對原始查詢結(jié)果不滿意時，搜索引擎會推薦那些與原始查詢更相關(guān)的候選詞。具體的新穎性函數(shù)和相似性函數(shù)，形式如下：

其中，D是當(dāng)前查詢的前3個網(wǎng)頁結(jié)果的摘要和所有滿意點擊網(wǎng)頁的摘要組成的文本，可以認(rèn)為是對原始查詢的擴展表示。本文認(rèn)為，D中包含了用戶已經(jīng)閱讀信息。如果當(dāng)前候選詞與文本D重合較多，說明這個候選詞不夠新穎。如何更有效地建模新穎性和相似性，將作為未來工作進一步探索。

5　實驗

5.1實驗數(shù)據(jù)

實驗數(shù)據(jù)是從必應(yīng)搜索引擎日志中隨機采樣得到的查詢數(shù)據(jù)（英文），其中包括1 166個用戶從2012 年7月1日到31日提交的522 900個查詢。在構(gòu)建基本的查詢流圖時，本文采用信息檢索領(lǐng)域廣泛接受劃分會話（session）的方法，將相鄰時間間隔在30 min之內(nèi)的查詢詞劃分為一個查詢會話[1-2]，則共劃分得到134 284個查詢會話。圖4描述了在實驗數(shù)據(jù)集的日志中每一天的查詢數(shù)和會話數(shù)。

Fig.4　Distribution of session number and query number on 31 days圖4　查詢會話數(shù)和查詢數(shù)在31天的分布

5.2評價指標(biāo)

本文實驗采用信息檢索中常用的NDCG（normalized discounted cumulative gain）[19]作為實驗效果的評價指標(biāo)。

DCG（discounted cumulative gain）是用來衡量排序結(jié)果質(zhì)量的重要指標(biāo)，表示如下：

其中，n表示返回的推薦詞在結(jié)果列表中的排序值；rel(j)表示第j個推薦詞的相關(guān)度；lb(1+j)是折扣因子。歸一化的DCG值為nDCG@n=DCG@n/idealDCG@n，其中idealDCG@n是最優(yōu)排序情況下的DCG評價值。

相關(guān)性評價指標(biāo)需要反映用戶在實時搜索狀態(tài)下的推薦質(zhì)量。本文將用戶在搜索過程中的實際查詢修改行為引入到性能評價中，并改進了NDCG中的相關(guān)性函數(shù)rel(j)：其中，qr是原始查詢qo在查詢?nèi)罩局械膶嶋H查詢修改詞，作為查詢推薦的“標(biāo)準(zhǔn)答案”是n個查詢推薦詞；qsj表示第 j個推薦詞。這樣本文的NDCG評價能夠真實地反映用戶在搜索過程中的實際行為，從而如實地反映模型推薦詞的質(zhì)量。

5.3結(jié)果與討論

在本文實驗中，利用第一天到第i天的數(shù)據(jù)進行訓(xùn)練，第i+1天的數(shù)據(jù)用于測試。與傳統(tǒng)查詢流圖模型比較的實驗結(jié)果如圖5所示。

Fig.5　Experiment results of nDCG@10圖5nDCG@10的實驗結(jié)果

圖5中橫坐標(biāo)表示天數(shù)，縱坐標(biāo)表示nDCG@10值，結(jié)果表明基于實時用戶搜索狀態(tài)改進后的推薦模型顯著優(yōu)于傳統(tǒng)的查詢流圖模型。分析模型表現(xiàn)優(yōu)異的原因是：（1）通過模糊匹配，得到了更多的查詢候選詞；（2）本文提出的基于用戶當(dāng)前搜索滿意度的模型能夠有效調(diào)整候選詞集合中推薦詞順序，在真實的環(huán)境中，更能匹配用戶的搜索習(xí)慣。

6　結(jié)論及展望

本文提出了一種基于用戶搜索狀態(tài)的查詢推薦模型。通過用戶實驗驗證了本文提出的假設(shè)，即在用戶不同搜索狀態(tài)下，用戶喜歡不同類型的推薦詞。本文利用跳轉(zhuǎn)頁面和點擊相關(guān)文檔的行為來估算用戶對當(dāng)前搜索結(jié)果的滿意度，并且基于當(dāng)前滿意度，自適應(yīng)地調(diào)整推薦詞順序。

在下一步的工作中，首先將著力優(yōu)化改進相關(guān)算法，重點是對用戶當(dāng)前滿意度的估計方法，如Albakour等人提出的自適應(yīng)的MRR[20]評價指標(biāo)，并且嘗試用多種相關(guān)性指標(biāo)進行衡量，尤其是當(dāng)用戶期望獲得全面信息時的用戶翻頁行為的建模還需要進一步改進。其次對候選詞的新穎性和相關(guān)性評價工作進行完善，更好地建模推薦詞的新穎性和相關(guān)性。最后考慮將更多的擴展文檔資源融合進本文的模型，擴充原始查詢候選詞集合。

References:

[1]Adeyanju I A,Song Dawei,Albakour M,et al.Adaptation of the concept hierarchy model with search logs for query recommendation on intranets[C]//Proceedings of the 35th International ACM SIGIR Conference on Research and Development in Information Retrieval,Oregon,USA,Aug 12-16,2012.New York:ACM,2012:5-14.

[2]Adeyanju I A,Song Dawei,Albakour M,et al.Learning from users ? querying experience on intranets[C]//Proceedings of the 21st International Conference on World Wide Web,Lyon,France,Apr 16-20,2012.New York:ACM,2012: 755-764.

[3]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, Napa Valley,USA,Oct 26-30,2008.New York:ACM,2008: 609-618.

[4]Bai Lu,Guo Jiafeng,Cheng Xueqi.Query recommendation by modelling the query-flow graph[C]//LNCS 7097:Proceedings of the 7th Asia Information Retrieval Societies Conference,Dubai,United Arab Emirates,Dec 18-20,2011. Berlin,Heidelberg:Springer,2011:137-146.

[5]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,Beijing,China,Jul 24-28, 2011.New York:ACM,2011:795-804.

[6]Baeza-Yates R,Hurtado C,Mendoza M.Query recommendation using query logs in search engines[C]//LNCS 3268: Proceedings of the 2004 International Conference on Current Trends in Database Technology,Heraklion,Greece,Mar 14-18,2004.Berlin,Heidelberg:Springer,2005:588-596.

[7]Xu Jinxi,Croft W B.Query expansion using local and global document analysis[C]//Proceedings of the 19th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval,Zurich,Switerland, Aug 18-22,1996.New York:ACM,1996:4-11.

[8]Liu Yang,Song Ruihua,Chen Yu,et al.Adaptive query suggestion for difficult queries[C]//Proceedings of the 35th International ACM SIGIR Conference on Research and Development in Information Retrieval,Oregon,USA,Aug 12-16, 2012.New York:ACM,2012:15-24.

[9]Bordino I,De Francisci Morales G,Weber I,et al.From Machu_Picchu to rafting the urubambariver:anticipating information needs via the entity-query graph[C]//Proceedings of the 6th ACM International Conference on Web Search and Data Mining,Rome,Italy,Feb 4-8,2013.New York: ACM,2013:275-284.

[10]Bai Lu,Guo Jiafeng,Cheng Xueqi,et al.Exploring the queryflow graph with a mixture model for query recommendation [C]//Proceedings of the 2011 SIGIR Workshop on Query Representation and Understanding,Beijing,China,Jul 24-28,2011.New York:ACM,2011.

[11]Song Yang,Zhou Dengyong,He Liwei.Query suggestion by constructing term-transition graphs[C]//Proceedings of the 5th ACM International Conference on Web Search and Data Mining,Seattle,USA,Feb 8-12,2013.New York: ACM,2012:353-362.

[12]Wu Wei,Li Hang,Xu Jun.Learning query and document similarities from click-through bipartite graph with metadata [C]//Proceedings of the 6th ACM International Conference on Web Search and Data Mining,Rome,Italy,Feb 4-8, 2013.New York:ACM,2013:687-696.

[13]Chen Jimeng,Wang Yuan,Liu Jie,et al.Modeling semantic and behavioral relations for query suggestion[C]//LNCS 7923:Proceedings of the 14th International Conference on Web-Age Information Management,Beidaihe,China,Jun 14-16,2013.Berlin,Heidelberg:Springer,2013:666-678.

[14]Wei Chao,Liu Yiqun,Zhang Min,et al.Fighting against Web spam:a novel propagation method based on clickthrough data[C]//Proceedings of the 35th International ACM SIGIR Conference on Research and Development in Information Retrieval,Oregon,USA,Aug 12-16,2012.New York:ACM,2012:395-404.

[15]Joachims T.Optimizing search engines using clickthrough data[C]//Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Edmonton,Canada,Jul 23-26,2002.New York:ACM,2002: 133-142.

[16]Jaccard P.The distribution of the flora in the alpine zone 1 [J].New Phytologist,1912,11(2):37-50.

[17]Teevan J,Dumais S T,Horvitz E.Potential for personalization[J].ACM Transactions on Computer-Human Interaction, 2010,17(1):4.

[18]Turpin A,Scholer F.User performance versus precision measures for simple search tasks[C]//Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval,Seattle, USA,Aug 6-11,2006.New York:ACM,2006:11-18.

[19]J?rvelinK,Kek?l?inen J.Cumulated gain-based evaluation of IR techniques[J].ACM Transactions on Information Systems,2002,20(4):422-446.

[20]Albakour M D,Kruschwitz U,Nanas N,et al.AutoEval:an evaluation methodology for evaluating query suggestions using query logs[C]//LNCS 6611:Proceedings of the 33rd European Conference on Advances in Information Retrieval, Dublin,Ireland,Apr 18-21,2011.Berlin,Heidelberg:Springer, 2011:605-610.

LI Jingfei was born in 1987.He is a Ph.D.candidate at Tianjin University,and the student member of CCF.His research interests include query recommendation,quantum information retrieval and search personalization,etc.He has published 5 papers on international conferences.

李競飛（1987—），男，河北石家莊人，天津大學(xué)博士研究生，CCF，主要研究領(lǐng)域為查詢推薦，量子信息檢索，個性化信息檢索等。

SHANG Zhenguo was born in 1990.He is an M.S.candidate at Tianjin University.His research interests include query recommendation and search personalization,etc.

ZHANG Peng was born in 1983.He received the Ph.D.degree from Robert Gordon University in 2013.Now he is a lecturer and M.S.supervisor at Tianjin University,and the member of CCF.His research interests include information retrieval,quantum cognitive computing and machine learning,etc.He has published more than 20 papers in journals and conferences.

張鵬（1983—），男，山西高平人，2013年于英國羅伯特戈登大學(xué)獲得博士學(xué)位，現(xiàn)為天津大學(xué)計算機學(xué)院講師、碩士生導(dǎo)師，CCF會員，主要研究領(lǐng)域為信息檢索，量子認(rèn)知計算，機器學(xué)習(xí)等。發(fā)表20余篇期刊及會議論文，主持1項國家自然科學(xué)基金和1項教育部博士點新教師類基金。

SONG Dawei was born in 1972.He received the Ph.D.degree from Chinese University of Hong Kong in 2000. Now he is a professor and Ph.D.supervisor at Tianjin University,and the member of CCF.His research interests include theory and formal models for context-sensitive information retrieval,multimedia and social media information retrieval,domain-specific information retrieval,user behavior,interaction and cognition in information seeking, text mining and knowledge discovery,etc.He has published more than 100 papers in many top tier international journal and conference.

宋大為（1972—），男，河北滄州人，2000年于香港中文大學(xué)獲得博士學(xué)位，現(xiàn)為天津大學(xué)計算機學(xué)院教授、博士生導(dǎo)師，CCF會員，主要研究領(lǐng)域為信息檢索理論與模型，多媒體與社會媒體信息檢索，特定領(lǐng)域信息檢索，信息檢索用戶交互與認(rèn)知，文本挖掘與知識發(fā)現(xiàn)等。發(fā)表學(xué)術(shù)論文百余篇，主持英國國家工程和物理科學(xué)研究基金委員會基金項目4項，參與國家重點基礎(chǔ)研究發(fā)展計劃（973）2項，主持國家自然科學(xué)基金項目1項。

Auto-adaptive Query Recommendation Model Considering Users? Real-Time Search State?

LI Jingfei,SHANG Zhenguo,ZHANG Peng+,SONG Dawei
Tianjin Key Laboratory of Cognitive Computing andApplication,Tianjin University,Tianjin 300072,China
+Corresponding author:E-mail:pzhang@tju.edu.cn

LI Jingfei,SHANG Zhenguo,ZHANG Peng,et al.Auto-adaptive query recommendation model considering users? real-time search state.Journal of Frontiers of Computer Science and Technology,2016,10(9)：1290-1298.

The traditional query recommendation algorithms generate query suggestions by mining query logs of search engines.However,existing models focus more on the relationships(e.g.,semantic similarity or relevance etc.)between original query and candidate suggestions without considering users’search state during the search process.To address this challenge,this paper proposes a basic assumption for query suggestion inspired by the fact that users have different satisfaction states when searching for information,then verifies the assumption by conducting a large scale online user questionnaire.According to the verified assumption,this paper presents an auto-adaptive query recommendation model which is able to provide different categories of queries to users intelligently.In the proposed model,the system will provide new query suggestions to users when they are satisfied with current search results; on the contrary,the system will tend to recommend those query suggestions which are relevant and have more powerful representing ability.Large scale experiments on query logs show that the proposed model outperforms the traditional query flow graph model significantly and demonstrate the effectiveness of the proposed model.

2015-08,Accepted 2015-10.

query recommendation;query flow graph;search state;satisfaction

*The National Natural Science Foundation of China under Grant Nos.61402324,61272265(國家自然科學(xué)基金);the National Basic Research Program of China under Grant Nos.2013CB329304,2014CB744604(國家重點基礎(chǔ)研究發(fā)展計劃(973計劃));the Specialized Research Fund for the Doctoral Program of Higher Education of China under Grant No.20130032120044(高等學(xué)校博士學(xué)科點專項科研基金).

CNKI網(wǎng)絡(luò)優(yōu)先出版:2015-10-20,http://www.cnki.net/kcms/detail/11.5602.TP.20151020.1041.006.html

A

TP391.3