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

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

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

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

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

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

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

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

1　引言

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

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

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

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

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

2　文獻(xiàn)綜述

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

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

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

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

3.1基本假設(shè)

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

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

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

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

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

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

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

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

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

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

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

4.1查詢流圖

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

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

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

4.2模型框架

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5.1實(shí)驗(yàn)數(shù)據(jù)

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

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

5.2評(píng)價(jià)指標(biāo)

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

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

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

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

5.3結(jié)果與討論

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

Fig.5　Experiment results of nDCG@10圖5nDCG@10的實(shí)驗(yàn)結(jié)果

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

6　結(jié)論及展望

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

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

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)域?yàn)椴樵兺扑]，量子信息檢索，個(gè)性化信息檢索等。

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é)計(jì)算機(jī)學(xué)院講師、碩士生導(dǎo)師，CCF會(huì)員，主要研究領(lǐng)域?yàn)樾畔z索，量子認(rèn)知計(jì)算，機(jī)器學(xué)習(xí)等。發(fā)表20余篇期刊及會(huì)議論文，主持1項(xiàng)國家自然科學(xué)基金和1項(xiàng)教育部博士點(diǎn)新教師類基金。

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é)計(jì)算機(jī)學(xué)院教授、博士生導(dǎo)師，CCF會(huì)員，主要研究領(lǐng)域?yàn)樾畔z索理論與模型，多媒體與社會(huì)媒體信息檢索，特定領(lǐng)域信息檢索，信息檢索用戶交互與認(rèn)知，文本挖掘與知識(shí)發(fā)現(xiàn)等。發(fā)表學(xué)術(shù)論文百余篇，主持英國國家工程和物理科學(xué)研究基金委員會(huì)基金項(xiàng)目4項(xiàng)，參與國家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃（973）2項(xiàng)，主持國家自然科學(xué)基金項(xiàng)目1項(xiàng)。

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(國家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃(973計(jì)劃));the Specialized Research Fund for the Doctoral Program of Higher Education of China under Grant No.20130032120044(高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金).

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