李亞楠，王 斌，李錦濤

(1. 中國(guó)科學(xué)院 計(jì)算技術(shù)研究所，北京 100190；

2. 中國(guó)科學(xué)院 研究生院，北京 100190)

1 引言

隨著互聯(lián)網(wǎng)的普及，搜索引擎已經(jīng)成為人們獲取信息的主要手段之一。目前搜索引擎采用的主要交互方式是：用戶自主輸入查詢，檢索系統(tǒng)根據(jù)輸入的查詢提供檢索結(jié)果。但是，很多時(shí)候用戶輸入的查詢并不能精確表達(dá)其搜索意圖。一方面，用戶輸入的查詢通常較短——平均只有兩三個(gè)詞[1-2]；另一方面，很多搜索引擎含有歧義[3]或意圖模糊[4]；此外，很多時(shí)候，用戶之所以要搜索就是因?yàn)閷?duì)要檢索話題知之甚少甚至毫無(wú)概念，這時(shí)候用戶很難構(gòu)造好查詢。研究文獻(xiàn)[5]表明，只有25%的查詢能清晰表達(dá)用戶的意圖。

為了幫助用戶更好地構(gòu)造查詢，搜索引擎普遍采用查詢推薦技術(shù)，大家熟知的搜索結(jié)果頁(yè)面中的“相關(guān)搜索”就是查詢推薦的一個(gè)具體應(yīng)用。查詢推薦指發(fā)現(xiàn)或構(gòu)造一組與原查詢Q相關(guān)的查詢{Q1,Q2,...}，這些相關(guān)查詢可以通過(guò)修改原查詢Q或整個(gè)替換Q來(lái)實(shí)現(xiàn)。例如，對(duì)查詢“蘋果 mp3”，可以通過(guò)修改查詢?cè)~“mp3”來(lái)推薦查詢“蘋果 播放器”，也可以將整個(gè)查詢替換為“ipod”。在不同文獻(xiàn)中，針對(duì)這查詢推薦的稱呼可能會(huì)有所不同，例如，Query Suggestion[6], Term Suggestion[7], Query Recommendation[8], Query Substitution[9], Query Rewriting[10]。盡管在具體實(shí)現(xiàn)細(xì)節(jié)上，文獻(xiàn)[11]認(rèn)為上述方法間存在一些差異，但是從本文定義看，這些方法是相同的。

早在上世紀(jì)90年代，信息檢索研究者就開展了一些查詢推薦相關(guān)研究[12-15]，一些早期搜索引擎(Altavista; Hotbot; Lycos)上也應(yīng)用了初始的查詢推薦技術(shù)。Rutgers大學(xué)的研究人員曾做了一系列關(guān)于檢索系統(tǒng)的人機(jī)交互實(shí)驗(yàn)[13，16-17]，這些研究顯示[18]，相對(duì)于完全透明、自動(dòng)的查詢擴(kuò)展(Query Expansion)方式，用戶更喜歡他們可以加以選擇、控制的查詢推薦方式。此外，很多研究人員又重新采用了可量化控制各種因素的用戶評(píng)測(cè)實(shí)驗(yàn)[20-22]，這表明：查詢推薦技術(shù)在檢索和瀏覽過(guò)程中的確能幫助用戶進(jìn)行更好的檢索、節(jié)省搜索時(shí)間。如今，查詢推薦技術(shù)已經(jīng)成為了搜索引擎必備技術(shù)之一。

除了幫助搜索用戶改進(jìn)查詢，查詢推薦技術(shù)還可應(yīng)用于廣告檢索系統(tǒng)中。搜索引擎公司通過(guò)廣告檢索系統(tǒng)將用戶查詢與廣告關(guān)聯(lián)起來(lái)。當(dāng)用戶搜索時(shí)，廣告檢索系統(tǒng)找出與其查詢相關(guān)的廣告，然后在搜索結(jié)果頁(yè)面展示這些廣告。然而，廣告商通常只能提供很少一部分與其廣告相關(guān)的查詢。這使得廣告只能展示給部分相關(guān)用戶，因此影響廣告商和搜索引擎的收益。廣告檢索系統(tǒng)通常采用查詢推薦技術(shù)，根據(jù)廣告商提供的廣告相關(guān)查詢找出更多相關(guān)查詢或關(guān)鍵詞，進(jìn)而向用戶推送更多相關(guān)廣告以獲取更多利潤(rùn)。例如，Google AdWords*https://adwords.google.cn/和百度推廣*http://e.baidu.com/pro/中的關(guān)鍵詞推薦工具就屬于此類應(yīng)用。此外，查詢推薦技術(shù)還應(yīng)用于查詢拼寫檢查、問(wèn)答系統(tǒng)[23]、個(gè)性化搜索[24]等領(lǐng)域。

由于有著巨大的應(yīng)用需求，查詢推薦成為近幾年的研究熱點(diǎn)。從技術(shù)上看，查詢推薦可以看作一個(gè)以搜索引擎查詢或查詢關(guān)鍵詞為檢索對(duì)象的信息檢索問(wèn)題。然而，不同于文章或網(wǎng)頁(yè)，查詢的自身特點(diǎn)使查詢推薦面臨諸多挑戰(zhàn)：

? 首先，不同于文章或網(wǎng)頁(yè)，查詢通常只包含兩三個(gè)詞，缺乏充分的文本內(nèi)容，傳統(tǒng)信息檢索模型不適合直接對(duì)其處理；

? 其次，很多查詢信息稀疏。查詢?nèi)罩局卸鄶?shù)查詢出現(xiàn)次數(shù)很少，因此對(duì)這些查詢處理時(shí)，可利用的相關(guān)屬性信息很有限；

? 最后，用戶查詢復(fù)雜多樣。查詢?nèi)罩局型瑤浊f(wàn)甚至上億不同的查詢，即便同一查詢，在不同用戶心中也可能表示不同意圖。此外，查詢受時(shí)間、突發(fā)事件等因素影響。例如，情人節(jié)前后與查詢“禮物”相關(guān)的查詢是“玫瑰”、“巧克力”等，而在萬(wàn)圣節(jié)前后相關(guān)查詢應(yīng)該是“面具”等。

針對(duì)上述問(wèn)題，學(xué)術(shù)界提出了多種方法用于查詢推薦。例如，利用查詢相關(guān)文檔擴(kuò)充查詢以解決查詢短的問(wèn)題[25]，挖掘查詢間的間接隱含聯(lián)系解決信息稀疏問(wèn)題[50]，根據(jù)搜索Session判定用戶查詢意圖[7]等等。查詢推薦作為自然語(yǔ)言處理的一種具體應(yīng)用，很多技術(shù)方法都可以被其所采用。其方法主要有：基于特征匹配的傳統(tǒng)信息檢索模型[8, 25]，關(guān)聯(lián)規(guī)則等傳統(tǒng)數(shù)據(jù)挖掘方法[26]，分類聚類等機(jī)器學(xué)習(xí)方法[9, 27]，基于查詢統(tǒng)計(jì)特征分析的方法[28]，圖模型上的隨機(jī)游走方法[10, 29]，以及一些利用經(jīng)驗(yàn)規(guī)則融合各類方法的研究[7]。

查詢推薦方法根據(jù)所依賴的數(shù)據(jù)不同可分為兩類：基于文檔的方法和基于日志的方法。1)基于文檔的方法主要通過(guò)處理包含查詢或查詢?cè)~的文檔來(lái)分析查詢，從查詢相關(guān)文檔或人工編輯語(yǔ)料(如詞典)中找出與輸入查詢相關(guān)的詞或短語(yǔ)，然后利用這些相關(guān)詞或短語(yǔ)構(gòu)建推薦查詢。2)基于日志的方法依靠分析搜索引擎查詢?nèi)罩緦ふ疫^(guò)去出現(xiàn)過(guò)的相似查詢，然后向用戶給予推薦。這兩種方法各有利弊，基于日志的方法難以處理出現(xiàn)頻率小的稀疏查詢，基于文檔的方法雖能處理稀疏查詢，但是查找相關(guān)文檔本身也是一個(gè)難題。近幾年來(lái)，有研究提出將文檔信息和日志信息結(jié)合起來(lái)進(jìn)行查詢推薦。

本文將系統(tǒng)闡述查詢推薦技術(shù)的相關(guān)概念、理論方法及評(píng)價(jià)體系。后續(xù)內(nèi)容組織如下：第2節(jié)總結(jié)了目前各類查詢推薦技術(shù)方法；第3節(jié)講述了查詢推薦的評(píng)價(jià)體系；最后，第4節(jié)對(duì)本文進(jìn)行了總結(jié)。

2 技術(shù)方法

搜索引擎查詢推薦要解決的是一個(gè)應(yīng)用問(wèn)題，其可以看作是以查詢或查詢?cè)~作為處理對(duì)象的信息檢索。這個(gè)檢索問(wèn)題的輸入是用戶初始查詢，輸出是一系列與初始查詢相關(guān)的其他查詢。然而，如前面所述，搜索引擎查詢不同于傳統(tǒng)文本檢索對(duì)象，其文本內(nèi)容很少、信息稀疏，傳統(tǒng)信息檢索方法并不完全適用。與此同時(shí)，搜索引擎查詢有其他一些特征可以利用。一方面，查詢通常有一兩個(gè)詞或短語(yǔ)構(gòu)成，而這些查詢?cè)~和短語(yǔ)間的語(yǔ)義關(guān)系會(huì)體現(xiàn)在包含它們的文檔或詞典中；另一方面，查詢?nèi)罩局杏涗浟瞬樵兊乃阉髡?、時(shí)間、點(diǎn)擊URL等屬性，相關(guān)查詢的這些屬性也會(huì)表現(xiàn)一定的關(guān)聯(lián)。查詢推薦作為一個(gè)應(yīng)用問(wèn)題，需要考慮如何利用這些特征信息找出各查詢間背后的聯(lián)系，而不同的特征和數(shù)據(jù)又有一些不同的性質(zhì)，需要相對(duì)應(yīng)的合適方法對(duì)其處理。因此，查詢推薦技術(shù)包括各種針對(duì)不同數(shù)據(jù)采用不同模型的方法。

本文根據(jù)查詢推薦所依賴的數(shù)據(jù)和特征不同，對(duì)各種技術(shù)方法分別給予簡(jiǎn)要介紹。總的來(lái)說(shuō)，根據(jù)所依賴的數(shù)據(jù)不同，查詢推薦技術(shù)可分為兩類：基于文檔的方法和基于查詢?nèi)罩镜姆椒?。下面分別介紹這兩類方法：

2.1 基于文檔的方法

基于文檔的方法主要通過(guò)處理包含查詢的相關(guān)文檔來(lái)找出與查詢相關(guān)的詞或短語(yǔ)，然后用這些詞或短語(yǔ)構(gòu)成要推薦的查詢?；谖臋n的方法主要分為三類：全局文檔集分析，局部文檔集分析和分析人工編輯語(yǔ)料(如詞典、維基百科等)。全局文檔集分析利用所有文檔分析文檔中詞與詞的關(guān)系，找出與查詢?cè)~關(guān)系緊密的其他詞，進(jìn)而構(gòu)造推薦查詢。局部文檔集分析只分析部分文檔來(lái)找出查詢相關(guān)詞，通?；谙嚓P(guān)文檔分析處理。隨著信息技術(shù)和互聯(lián)網(wǎng)的發(fā)展，現(xiàn)在有很多編輯良好的描述詞與詞之間關(guān)系的數(shù)據(jù)，例如WordNet，HowNet，ODP資源等。利用這些資源可以發(fā)現(xiàn)詞與詞間的語(yǔ)義聯(lián)系，構(gòu)造相關(guān)查詢。

2.1.1 全局文檔集分析

2.1.2 局部文檔集分析

局部文檔集分析只分析部分文檔來(lái)找出查詢相關(guān)詞，通常基于相關(guān)文檔分析處理。直覺(jué)上，與查詢相關(guān)的詞或短語(yǔ)將有更大可能出現(xiàn)在相關(guān)文檔中，只分析相關(guān)文檔就可以找出查詢相關(guān)詞。然而相關(guān)文檔難以獲得，常用的方法是假設(shè)檢索返回的排名靠前文檔是相關(guān)的。由于這些文檔并非真正的相關(guān)文檔，因此也常被稱為偽相關(guān)文檔。

有很多方法利用偽相關(guān)文檔檢索查詢相關(guān)詞。首先，偽相關(guān)文檔中出現(xiàn)的高頻非停用詞可以作為查詢相關(guān)詞[32]，由于偽相關(guān)文檔中都包含查詢?cè)~，這種方法其實(shí)就是找出在查詢?cè)~出現(xiàn)的條件下出現(xiàn)概率最高的那些詞語(yǔ)作為相關(guān)詞。另一個(gè)知名方法是Xu和Croft[15]提出的LCA(Local Context Analysis)。LCA計(jì)算偽相關(guān)文檔中每個(gè)詞與整個(gè)查詢而非某個(gè)查詢?cè)~的關(guān)系緊密程度，因此擁有更高的準(zhǔn)確度。但是LCA效率較低，查詢推薦需要實(shí)時(shí)處理，LCA計(jì)算復(fù)雜度偏高。

上述方法幾乎可以處理各種查詢，即便對(duì)于罕見(jiàn)查詢，只要能返回搜索結(jié)果，也同樣可以處理。但是這些方法的前提假設(shè)是能找到查詢相關(guān)文檔，能否找出查詢相關(guān)文檔本身就是一個(gè)困難問(wèn)題。偽相關(guān)文檔畢竟不是真正的相關(guān)文檔，它們會(huì)引入不相關(guān)文檔而降低準(zhǔn)確度。

2.1.3 基于人工編輯語(yǔ)料的方法

隨著信息技術(shù)和互聯(lián)網(wǎng)的發(fā)展，現(xiàn)在有很多編輯良好的描述詞與詞之間關(guān)系的數(shù)據(jù)，利用這些資源可以發(fā)現(xiàn)詞與詞間的語(yǔ)義聯(lián)系，構(gòu)造相關(guān)查詢。這類方法通過(guò)利用詞典(例如WordNet[33])或其他人工編輯好的數(shù)據(jù)(如Wikipedia[34-35]、Open Directory Project[36])查找相關(guān)查詢?cè)~或短語(yǔ)。這類方法的結(jié)果往往比較準(zhǔn)確，但是難以處理那些尚未編輯的新出現(xiàn)查詢?cè)~，而新詞卻在用戶搜索中占很大比例。

盡管基于文檔的方法可以找出與當(dāng)前查詢相關(guān)的一系列詞或短語(yǔ)，但是要完成查詢推薦還需要將這些相關(guān)詞或短語(yǔ)組合成合適的搜索引擎查詢。搜索引擎查詢不同于人類自然語(yǔ)言中的問(wèn)題，它有其自身的特點(diǎn)，如何組合成合適的查詢本身也是一個(gè)難題。另一方面，搜索引擎查詢?nèi)罩局杏涗浟擞脩魳?gòu)造的各種真實(shí)查詢，通過(guò)分析查詢?nèi)罩靖菀渍页霾⑼扑]合適的查詢。

2.2 基于日志的方法

當(dāng)用戶搜索時(shí)，搜索引擎通常會(huì)將用戶的行為記錄下來(lái)，這些記錄數(shù)據(jù)構(gòu)成了搜索引擎查詢?nèi)罩?。查詢?nèi)罩局忻織l記錄對(duì)應(yīng)于用戶的一次行為，例如，開啟一次新的查詢、點(diǎn)擊一個(gè)搜索結(jié)果鏈接、翻看新一頁(yè)的搜索結(jié)果等等。查詢?nèi)罩局杏涗浟擞脩酎c(diǎn)擊文檔和其他用戶搜索行為信息，這些重要信息是基于文檔的方法難以提供的。利用查詢?nèi)罩局杏涗浀母鞣N信息，可以挖掘出不同查詢間的聯(lián)系?，F(xiàn)有方法主要利用查詢間的共有屬性來(lái)挖掘查詢間的聯(lián)系緊密程度，這些屬性特征主要包括：查詢共同出現(xiàn)在同一搜索過(guò)程(Session)的次數(shù)、查詢共有的相同或相似的點(diǎn)擊URL、日志中不同查詢間的文本相似度、兩查詢出現(xiàn)頻率隨時(shí)間分布的相關(guān)性。根據(jù)所依賴的特征不同，這里將基于日志的方法分為四類方法：基于Session的方法、基于點(diǎn)擊URL的方法、基于文本相似度的方法和基于時(shí)間分布的方法。

2.2.1 基于Session的方法

用戶在搜索過(guò)程中為了同一個(gè)檢索目標(biāo)所做的一系列檢索行為構(gòu)成一個(gè)Session。很多時(shí)候，一個(gè)Session中會(huì)包含多個(gè)查詢，這表明用戶對(duì)Session中初始查詢的檢索結(jié)果不滿意，后來(lái)他有重新構(gòu)造一個(gè)或多個(gè)表達(dá)同一搜索意圖的查詢。

用戶搜索Session中的信息可以從多個(gè)方面幫助查詢推薦。首先，可以用之前用戶的搜索經(jīng)驗(yàn)幫助后來(lái)的用戶，直接向當(dāng)前用戶推薦之前用戶最終找到正確答案所用的查詢?；谶@一思想，Cucerzan和White[6]提出一套規(guī)則判別Session中的最終結(jié)果網(wǎng)頁(yè)，進(jìn)而向用戶推薦能直接返回最終結(jié)果網(wǎng)頁(yè)的查詢。其次，經(jīng)常出現(xiàn)在同一Session中的兩個(gè)查詢很有可能是語(yǔ)義相似的，因?yàn)樗鼈兌啻伪磉_(dá)同一查詢意圖。由此，可以根據(jù)Session中查詢的共現(xiàn)信息利用關(guān)聯(lián)規(guī)則[26]、互信息[9]、相似度算法[7, 37, 41]度量查詢間相關(guān)性。最后，Session相對(duì)于單個(gè)查詢，提供了更多有助于明確查詢意圖的信息，根據(jù)整個(gè)Session而非單個(gè)查詢進(jìn)行推薦將會(huì)更加準(zhǔn)確[7, 38]。

基于Session的方法需要首先將查詢?nèi)罩緞澐殖啥鄠€(gè)Session，而Session劃分好壞會(huì)影響查詢推薦的準(zhǔn)確率。傳統(tǒng)方法根據(jù)同一用戶兩個(gè)相鄰查詢間的時(shí)間間隔判斷這兩個(gè)查詢是否處于同一Session中，如果時(shí)間間隔大于一個(gè)設(shè)定的閾值，則在這兩個(gè)查詢間進(jìn)行Session切分。單純依靠時(shí)間間隔進(jìn)行Session劃分并不十分精確，近年來(lái)提出了一些更有效的Session劃分方法，相關(guān)工作可參見(jiàn)文獻(xiàn)[39]。

2.2.2 基于點(diǎn)擊URL的方法

查詢?nèi)罩局杏涗浟嗣看尾樵儠r(shí)用戶點(diǎn)擊的URL，這些URL可用來(lái)挖掘查詢間的關(guān)系緊密程度。如果兩個(gè)查詢所對(duì)應(yīng)的點(diǎn)擊URL很多都是相同或相似的，那么這兩個(gè)查詢就有很大的相關(guān)性。根據(jù)此思想，很多查詢推薦算法被提出。

最開始的工作主要利用相同點(diǎn)擊URL衡量查詢相關(guān)性。其中，王繼民和彭波[40]提出一種基于查詢共有相同點(diǎn)擊URL數(shù)的查詢推薦的方法。進(jìn)一步地，查詢Qi可以表示成由其所對(duì)應(yīng)URL構(gòu)成的向量(Ui1,Ui2,…,Uim)，然后應(yīng)用向量空間檢索模型[42]計(jì)算不同查詢間的相似度。其中Uia表示第a個(gè)URL的權(quán)重，Uia可以用最簡(jiǎn)單的第a個(gè)URL在查詢Qi出現(xiàn)的次數(shù)表示，也可以根據(jù)tf-idf思想做適當(dāng)改進(jìn)。

查詢?nèi)罩窘y(tǒng)計(jì)分析[43]顯示一次查詢平均只有幾次點(diǎn)擊，表示查詢的向量往往非常稀疏。實(shí)際上，對(duì)一個(gè)查詢，用戶往往只點(diǎn)擊前1，2頁(yè)中的某幾個(gè)結(jié)果，很多相似查詢沒(méi)有相同的點(diǎn)擊URL。為了應(yīng)對(duì)這一問(wèn)題，不同研究者提出了不同的方法。首先，可以在計(jì)算查詢相似度時(shí)，把相似URL也考慮進(jìn)來(lái)，擁有內(nèi)容相似點(diǎn)擊URL的查詢也應(yīng)該是相似的。既然可以根據(jù)點(diǎn)擊URL算出查詢間的相似度，反過(guò)來(lái)依據(jù)URL所對(duì)應(yīng)的查詢同樣可以求得URL間相似度，這樣不斷迭代就可以同時(shí)得到查詢間和URL間的更精確的相似度?；谶@種思想，Antonellis等人[10]提出利用一種改進(jìn)的SimRank相似度算法度量查詢相關(guān)性。另一方面，如果能把查詢或URL的空間維度降低，就能避免數(shù)據(jù)稀疏的問(wèn)題。這方面的相關(guān)研究有基于查詢聚類的方法[27, 38]和基于矩陣分解的方法[44-45]。但是，上述方法在提高準(zhǔn)確度的同時(shí)也加大了算法計(jì)算復(fù)雜度。

2.2.3 基于文本相似度的方法

查詢也是由詞和短語(yǔ)構(gòu)成的對(duì)象，傳統(tǒng)的文本信息檢索模型或文本編輯距離同樣可以用來(lái)度量查詢相似度。但是搜索引擎查詢通常很短，平均長(zhǎng)度不到三個(gè)詞[1-2]，直接對(duì)日志中查詢計(jì)算相似度的效果并不好。例如，查詢“電腦”和“計(jì)算機(jī)”相關(guān)但是卻沒(méi)有相同查詢?cè)~，查詢“汽車引擎”和“搜索引擎”不相關(guān)卻有50%的查詢?cè)~重疊。

如果能對(duì)日志中查詢的文本內(nèi)容進(jìn)行擴(kuò)充，就能避免上述問(wèn)題。為此，很多研究用偽相關(guān)文檔構(gòu)造表示查詢的文檔QD，進(jìn)而利用QD間的相似度計(jì)算其所對(duì)應(yīng)查詢的相似度。不同方法中偽相關(guān)文檔的定義不同，Sahami[25]提出用搜索引擎返回的排名靠前的n個(gè)結(jié)果作為偽相關(guān)文檔，Baeza-Yates等人[8]用有用戶點(diǎn)擊的結(jié)果作為偽相關(guān)文檔并將點(diǎn)擊頻率因素考慮進(jìn)來(lái)。直觀來(lái)看，用戶點(diǎn)擊過(guò)的文檔比直接用所有排名靠前文檔似乎更相關(guān)一些，但實(shí)際上搜索引擎排序?qū)τ脩酎c(diǎn)擊同樣會(huì)產(chǎn)生很大影響[46]，用戶點(diǎn)擊頻率排序經(jīng)常跟搜索引擎排序是一致的。采用一些更可靠的分析用戶點(diǎn)擊的模型[47]可能有助于提高該類方法。

2.2.4 基于時(shí)間分布的方法

有研究提出相似查詢的搜索頻率在時(shí)間分布上應(yīng)該是相似的，例如查詢“沃爾瑪”和“山姆會(huì)員店”在不同時(shí)間段的分布都是比較均勻的，而查詢“北京奧運(yùn)會(huì)”和“中國(guó) 金牌榜”這樣的查詢頻率分布在同一特定時(shí)間有明顯的尖峰。此外，查詢推薦也應(yīng)該考慮查詢頻率在時(shí)間上的分布情況，有的查詢有其重要時(shí)間段，在其重要時(shí)間段的推薦將更有效。例如，查詢“巧克力”在2月14日是個(gè)比較好的推薦查詢，因?yàn)榍煽肆ψ鳛槎Y物在情人節(jié)很流行。

查詢頻率在時(shí)間上的分布可以用查詢時(shí)間分布向量fq=(fq1,fq2,…,fqd)表示，其中fqi表示查詢q在第i個(gè)單位時(shí)間段內(nèi)的搜索頻率。為了度量不同查詢?cè)跁r(shí)間分布上的相關(guān)性，Chien和Immorlica[28]提出用查詢時(shí)間分布向量的皮爾森(pearson)相關(guān)度表征查詢相似度。基于Chien和Immorlica的工作，Zhang等人[48]提出一種考慮重要時(shí)間段的方法。此外，如同Web搜索中的PageRank一樣，查詢?cè)谌罩局谐霈F(xiàn)頻率也常作為一種靜態(tài)排序因子用于查詢推薦[49]。查詢頻率的時(shí)間分布特征的確是查詢推薦中的一個(gè)重要特征，但是只依靠此類特征判斷查詢相關(guān)性是不充分的，這類方法可以作為其他方法的一種補(bǔ)充應(yīng)用在查詢推薦系統(tǒng)中。

基于日志的方法根據(jù)用戶搜索歷史推薦查詢，相對(duì)于基于文檔的方法其構(gòu)造的查詢更符合用戶查詢的特點(diǎn)。但是查詢?cè)谌罩局械某霈F(xiàn)頻率呈指數(shù)分布，大多數(shù)查詢?cè)谌罩局谐霈F(xiàn)次數(shù)不多[43]。這使得基于日志的方法時(shí)面臨更嚴(yán)重的數(shù)據(jù)稀疏問(wèn)題，當(dāng)前方法在處理流行查詢時(shí)可以取得不錯(cuò)的效果，但是對(duì)付出現(xiàn)次數(shù)較少的查詢準(zhǔn)確度較差。

2.3 小結(jié)

各種查詢挖掘方法各有優(yōu)缺點(diǎn)，表1對(duì)此進(jìn)行了總結(jié)。采用基于文檔的方法分析查詢，可以利用互聯(lián)網(wǎng)上各類大規(guī)模數(shù)據(jù)和一些人工編輯好的資源。然而普通文檔中的文本內(nèi)容與一般查詢不同，從普通文檔中挖掘查詢信息受到很多制約。搜索引擎查詢有其自身的特點(diǎn)，搜索引擎查詢?nèi)罩局杏涗浟擞脩魳?gòu)造的各種真實(shí)查詢， 相對(duì)于基于文檔的方法更適合分析挖掘查詢性質(zhì)。但是查詢?nèi)罩局写蠖鄶?shù)查詢出現(xiàn)次數(shù)不多，面臨嚴(yán)重的數(shù)據(jù)稀疏問(wèn)題，當(dāng)前方法在處理流行查詢時(shí)可以取得不錯(cuò)的效果，但是對(duì)于出現(xiàn)次數(shù)較少的查詢準(zhǔn)確度較差。

表1 查詢處理相關(guān)工作優(yōu)缺點(diǎn)總結(jié)

從本質(zhì)看，查詢推薦是一種以查詢作為處理對(duì)象的信息檢索應(yīng)用問(wèn)題。然而，不同于傳統(tǒng)文本信息檢索，查詢推薦面臨文本內(nèi)容少、復(fù)雜多樣、信息稀疏等挑戰(zhàn)。直接應(yīng)用傳統(tǒng)信息檢索模型并不能很好解決這些問(wèn)題，為此學(xué)術(shù)界提出多種方法應(yīng)對(duì)這些挑戰(zhàn)。下面分別針就上述問(wèn)題使用不同方法做一個(gè)小結(jié)。

(1) 搜索引擎查詢平均長(zhǎng)度一般只有兩三個(gè)詞，缺乏傳統(tǒng)信息檢索模型所需的特征信息。針對(duì)該問(wèn)題有兩類解決方法。

? 第一類，利用查詢相關(guān)文檔擴(kuò)充查詢文本內(nèi)容，將查詢間的相似度計(jì)算就轉(zhuǎn)化為查詢相關(guān)文檔集間的文本相似度計(jì)算[25]。查詢相關(guān)文檔可以定義為搜索引擎返回的前N篇文檔，或者是查詢?nèi)罩局械挠脩酎c(diǎn)擊結(jié)果。

? 第二類，利用文檔或日志中的相關(guān)信息將查詢或查詢?cè)~映射到另一個(gè)特征空間[8]，這樣不同但相似的查詢或查詢?cè)~間的匹配度也不為零。

(2) 為了應(yīng)對(duì)信息稀疏問(wèn)題，近幾年學(xué)術(shù)界提出了不少解決辦法，這些方法基本上可以歸為三類。

? 第一類，將查詢映射到一個(gè)目錄中，利用目錄的樹狀結(jié)構(gòu)度量查詢間相似度[37]；這個(gè)目錄可以采用WordNet、ODP等已經(jīng)編輯好的目錄，也可以根據(jù)具體問(wèn)題重新構(gòu)建。

? 第二類，通過(guò)聚類或LSI等方法將信息稀疏的高維特征空間映射到低維空間中[38, 45]。

? 第三類，將查詢組織到關(guān)系圖中，其中節(jié)點(diǎn)表示查詢，邊表示查詢間的關(guān)系。在查詢關(guān)系圖中，通過(guò)其他查詢間接關(guān)聯(lián)的查詢之間也有一定相關(guān)性。利用查詢間關(guān)系信息可以計(jì)算間接相關(guān)查詢間的相似度[29, 50-51]。

(3) 搜索引擎查詢復(fù)雜多樣且經(jīng)常意圖不清。為了辨識(shí)用戶搜索意圖，利用整個(gè)Session信息而非單個(gè)查詢信息是經(jīng)常采用的方法[7, 38]，用戶的查詢歷史記錄也可用于幫助明確用戶意圖。另一方面，查詢受時(shí)間、地域等因素影響。對(duì)一些查詢?cè)谕扑]時(shí)考慮更多特征信息將取得更好的效果[28, 48]。

綜上所述，查詢推薦是一項(xiàng)應(yīng)用驅(qū)動(dòng)的技術(shù)，為了在具體應(yīng)用環(huán)境中取得更好的效果，各種數(shù)據(jù)和方法都可以采用。各類數(shù)據(jù)和方法都與各自的優(yōu)缺點(diǎn)，真實(shí)查詢推薦系統(tǒng)中應(yīng)該綜合利用各種數(shù)據(jù)和方法。有研究提出綜合兩種方法進(jìn)行查詢推薦，現(xiàn)有方法[49, 52]主要將基于文檔的查詢相似度和基于日志的查詢相似度做一個(gè)線性加權(quán)，基于文檔的相似度權(quán)重和基于日志的相似度權(quán)重根據(jù)經(jīng)驗(yàn)值設(shè)定。總的來(lái)說(shuō)，現(xiàn)有的綜合文檔和日志的方法還比較簡(jiǎn)單，也缺乏相應(yīng)的理論基礎(chǔ)。另一方面，由于真實(shí)搜索引擎的搜索量巨大，查詢推薦的可擴(kuò)展性和實(shí)時(shí)性也是非常重要的。能更好解決查詢稀疏性、多樣性等問(wèn)題的方法也常常更加復(fù)雜，因此這類算法經(jīng)常分為在線運(yùn)算和離線運(yùn)算兩部分。一個(gè)實(shí)際運(yùn)行的查詢推薦系統(tǒng)需要在推薦效果和效率方面做好平衡。

3 評(píng)價(jià)方式

查詢推薦的質(zhì)量與其應(yīng)用目標(biāo)相關(guān)，在不同的應(yīng)用環(huán)境中，推薦查詢的目的會(huì)有所不同。在搜索引擎中，查詢推薦的目的在于幫助用戶構(gòu)造更合適查詢，從而更快地找到所需信息。一個(gè)好的推薦查詢不僅要與初始查詢相關(guān)還應(yīng)該貼合用戶查詢意圖并有很好的檢索效果[21]，這樣才能幫助用戶。在廣告檢索系統(tǒng)中，查詢推薦的目的在于提高搜索引擎的廣告收益，這也不僅要求語(yǔ)義相關(guān)還應(yīng)該考慮查詢價(jià)格、廣告商預(yù)算等多種因素[53]。針對(duì)一個(gè)具體的應(yīng)用，查詢推薦的質(zhì)量評(píng)價(jià)需要考慮多方面因素，而且很多時(shí)候要做到完全準(zhǔn)確客觀的評(píng)價(jià)是很困難的。

如第三部分“相關(guān)概念”所述，本文的查詢推薦指根據(jù)初始查詢找出或構(gòu)造一組相關(guān)查詢的技術(shù)。因此，這里所述的評(píng)價(jià)體系只考慮推薦出的查詢是否與原查詢相關(guān)，不考慮其他因素。實(shí)際上，絕大多數(shù)查詢推薦研究工作都采用這種方法進(jìn)行評(píng)價(jià)。下面分別從測(cè)試集構(gòu)建和評(píng)價(jià)指標(biāo)設(shè)計(jì)兩個(gè)方面介紹查詢推薦評(píng)價(jià)體系。

3.1 測(cè)試集

要評(píng)價(jià)一種查詢推薦技術(shù)的好壞，首先需要構(gòu)建一個(gè)用于評(píng)測(cè)推薦結(jié)果相關(guān)與否的測(cè)試集，測(cè)試集包括查詢推薦方法依賴的數(shù)據(jù)和標(biāo)示相關(guān)性的答案。這里，查詢推薦方法依賴的數(shù)據(jù)可以是基于文檔的方法所依賴的文檔集，或者是基于日志的方法所用的查詢?nèi)罩?；?biāo)示答案的相關(guān)性只考慮推薦與原查詢是否語(yǔ)義相關(guān)，不考慮推薦查詢能否使搜索引擎返回與用戶意圖更相關(guān)結(jié)果等其他因素。下面分別介紹已有的可用數(shù)據(jù)和相關(guān)性答案的構(gòu)建方法。

根據(jù)已知知識(shí)，現(xiàn)在尚未有公認(rèn)的查詢推薦公共評(píng)價(jià)語(yǔ)料。因此，盡管現(xiàn)在已經(jīng)有大量查詢推薦相關(guān)工作發(fā)表，但仍然缺乏不同方法間的客觀比較。對(duì)于基于文檔的方法，所需的文檔集可以用傳統(tǒng)的方法收集或直接使用TREC語(yǔ)料、維基百科等現(xiàn)成數(shù)據(jù)。但是對(duì)于現(xiàn)在主要研究的基于日志的方法，由于查詢?nèi)罩旧婕坝脩綦[私等原因，除了搜索引擎公司(如微軟、雅虎、谷歌)的實(shí)驗(yàn)室，多數(shù)大學(xué)和研究機(jī)構(gòu)的實(shí)驗(yàn)室難以獲取真實(shí)查詢?nèi)罩?。已知的公開或曾公開過(guò)的查詢?nèi)罩居校核压饭竟_的2008年部分中文查詢?nèi)罩?http://www.sogou.com/labs/dl/q.html，AOL曾公開過(guò)的2006年部分英文查詢?nèi)罩?http://gregsadetsky.com/aol-data/。這些日志包括用戶ID、查詢?cè)~、點(diǎn)擊URL、點(diǎn)擊URL在返回結(jié)果中的排名等基本信息。

在查詢推薦實(shí)驗(yàn)中，有兩類構(gòu)建相關(guān)性答案的方法：人工評(píng)價(jià)和自動(dòng)評(píng)價(jià)。人工評(píng)價(jià)指：由人工標(biāo)注每個(gè)推薦查詢與原查詢是否語(yǔ)義相關(guān)。自動(dòng)評(píng)價(jià)則不需要人工標(biāo)注。下面分別簡(jiǎn)要介紹這兩類方法：

? 采用人工評(píng)價(jià)方法時(shí)，為了減少標(biāo)注工作量，通常采用類似于pooling[54]的評(píng)測(cè)集構(gòu)建方法。即對(duì)每個(gè)評(píng)測(cè)查詢，取各種對(duì)比方法的前n個(gè)推薦結(jié)果構(gòu)成一個(gè)集合，然后請(qǐng)人評(píng)價(jià)集合中每個(gè)結(jié)果的相關(guān)度。相關(guān)度的標(biāo)注可以只是“相關(guān)”、“不相關(guān)”兩類，也可以根據(jù)某些標(biāo)準(zhǔn)[9, 45]分成多個(gè)等級(jí)。

? 自動(dòng)評(píng)價(jià)利用其他資源判定查詢間的相關(guān)度，一般利用查詢?nèi)罩?、人工編輯目錄、WordNet、維基百科等數(shù)據(jù)構(gòu)建相關(guān)性答案。文獻(xiàn)[10]用查詢?nèi)罩咀鲎詣?dòng)評(píng)價(jià)，將查詢?nèi)罩痉譃閮刹糠郑阂徊糠肿鲇?xùn)練集，一部分做測(cè)試集。對(duì)測(cè)試集中出現(xiàn)的查詢Q，找出用戶在同一Session中使用查詢Q后又構(gòu)造的其他查詢{Q1,Q2,…,Q3}。對(duì)一種待評(píng)價(jià)方法R,如果R的推薦結(jié)果中包括 {Q1,Q2,…,Q3}中的查詢，則認(rèn)為推薦成功。有些研究利用人工編輯目錄(ODP[45, 55], Google Directory[56])評(píng)價(jià)推薦結(jié)果的相關(guān)程度：對(duì)于兩個(gè)要度量其相關(guān)度的查詢Q1和Q2，它們的相似度通過(guò)它們的共享目錄類別個(gè)數(shù)度量，Q1和Q2共同屬于的類別越多，它們就越相關(guān)。

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

查詢推薦是以查詢作為處理對(duì)象的信息檢索問(wèn)題，因此一般查詢推薦系統(tǒng)的評(píng)價(jià)都采用了文本檢索系統(tǒng)里面的指標(biāo)。常用的評(píng)價(jià)指標(biāo)有：

? 召回率(Recall)和正確率(Precision)。對(duì)一個(gè)查詢推薦系統(tǒng)的推薦結(jié)果：

其中P@N(Precision at N)是一個(gè)經(jīng)常被采用的指標(biāo)，即前N個(gè)推薦結(jié)果中相關(guān)查詢所占的比例。

?AP和MAP。AP(Average Precision)是對(duì)單個(gè)查詢?cè)诓煌倩芈庶c(diǎn)上的正確率進(jìn)行平均得到的平均正確率。對(duì)所有測(cè)試查詢的取平均值，則得到MAP(Mean AP)。令R(k)表示第k個(gè)相關(guān)結(jié)果所在位置，N表示測(cè)試查詢的個(gè)數(shù)，則：

，

?DCG和NDCG。有時(shí)候推薦查詢的相關(guān)度有多個(gè)等級(jí)，并非只有“相關(guān)”和“不相關(guān)”兩類，另外用戶往往更關(guān)注于排名靠前的結(jié)果。這時(shí)需要更準(zhǔn)確的評(píng)價(jià)指標(biāo)，相關(guān)等級(jí)越高的結(jié)果越多越好，相關(guān)等級(jí)越高的結(jié)果排名越靠前越好。DCG(Discounted Cumulative Gain)和NDCG(Normalized DCG)就是這樣一類評(píng)價(jià)指標(biāo)。假設(shè)是查詢q的返回結(jié)果，令R(k)表示Vk的得分，則在第k個(gè)位置上的DCG表示為：

NDCG是歸一化后的DCG。對(duì)每個(gè)查詢，計(jì)算一個(gè)標(biāo)準(zhǔn)答案的IDCG(Ideal DCG)，用返回結(jié)果的DCG除以標(biāo)準(zhǔn)DCG，就是NDCG。

? 覆蓋率(Coverage)

4 結(jié)論

查詢推薦及其相關(guān)技術(shù)是搜索引擎的必備技術(shù)之一。一方面，查詢推薦可以幫助用戶構(gòu)造更準(zhǔn)確查詢，節(jié)省搜索時(shí)間。另一方面，查詢推薦技術(shù)也幫助搜索引擎廣告系統(tǒng)匹配更多更準(zhǔn)確的廣告，增加搜索引擎利潤(rùn)已經(jīng)廣告商的潛在收益。此外，查詢推薦相關(guān)技術(shù)還被廣泛應(yīng)用于查詢優(yōu)化、拼寫錯(cuò)誤檢查、查詢擴(kuò)展、個(gè)性化搜索等領(lǐng)域。

本文闡述了查詢推薦技術(shù)的相關(guān)概念及研究和發(fā)展過(guò)程，對(duì)查詢推薦的主要方法和關(guān)鍵技術(shù)進(jìn)行綜述，介紹了目前學(xué)術(shù)研究中采用的方法和評(píng)價(jià)體系。本文將查詢推薦技術(shù)按照所依賴的數(shù)據(jù)不同分為基于文檔的方法和基于日志的方法，并說(shuō)明了查詢推薦中面臨的挑戰(zhàn)和現(xiàn)有的各種解決思路。

相對(duì)于傳統(tǒng)文本檢索，查詢推薦還是一個(gè)相對(duì)較新的研究領(lǐng)域，還有很多地方有待進(jìn)一步探討和研究。首先，查詢推薦尚缺乏統(tǒng)一的評(píng)價(jià)標(biāo)準(zhǔn)和評(píng)測(cè)語(yǔ)料，各類技術(shù)方法難以做客觀的比較。其次，各類基于不同數(shù)據(jù)和算法的查詢推薦方法各有優(yōu)缺點(diǎn)，需要一種有效的理論方法將它們?nèi)谌胍粋€(gè)統(tǒng)一的系統(tǒng)中。最后，中文搜索引擎查詢推薦也有待完善[57]。不同于其他語(yǔ)言，中文搜索引擎查詢有其自身特點(diǎn)，例如，多數(shù)中文查詢是一個(gè)不包含空格的完整詞或短語(yǔ)而不是多個(gè)查詢?cè)~的集合[43]。盡管有一些利用中文查詢?nèi)罩舅鞯牟樵兺扑]研究[41, 58]，但是這些方法基本與語(yǔ)言無(wú)關(guān)，結(jié)合中文特點(diǎn)的查詢推薦仍然亟待研究。

[1] A. Spink, B. J. Jansen. A Study of Web Search Trends [J]. Webology. 2004, 1(2), Article 4. Available at：http://www.webology.ir/2004/v1n2/a4.html

[2] 余慧佳,劉奕群,張敏,茹立云,馬少平. 于大規(guī)模日志分析的網(wǎng)絡(luò)搜索引擎用戶行為研究[C]//第三屆學(xué)生計(jì)算語(yǔ)言學(xué)研討會(huì)(SWCL2006). 2006.

[3] R. Song, Z. Luo, J.-R. Wen, Y. Yu, and H.-W. Hon. Identifying ambiguous queries in web search[C]//WWW’07. New York：ACM, 2007:1169-1170.

[4] Andre Broder. A taxonomy of web search [J]. SIGIR Forum 36(2), 2002.

[5] M. Strohmaier, M. Kr?ll, C. K?rner. Intentional Query Suggestion：Making User Goals More Explicit During Search [C]//Proceedings of the 2009 workshop on Web Search Click Data. 2009:68-74.

[6] Silviu Cucerzan, Ryen W. White, Query suggestion based on user landing pages [C]//Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval. New York：ACM, July 23-27, 2007: 875-876.

[7] C.K. Huang, L.F. Chien,, & Y.J. Oyang. Relevant term suggestion in interactive Web search based on contextual information in query session logs [J]. Journal of the American Society for Information Science and Technology. 2003, 54(7): 638-649.

[8] R. Baeza-Yates, C. Hurtado, and M. Mendoza. Query Recommendation Using Query Logs in Search Engines[C]//EDBT 2004 Wordshops. LNCS 2368, 2004:588-596.

[9] R. Jones, B. Rey, O. Madani, W. Greiner. Generating Query Substitutions [C]//WWW2006 New York：ACM, 2006: 387-396.

[10] I. Antonellis, H. Garcia-Molina and C. C. Chang, SimRank++：query rewriting through link analysis of the click graph[C]//Proceedings of VLDB. 4 Dec 2008: 408-421.

[11] D. Kelly, K. Gyllstrom, E. W. Bailey. A comparison of query and term suggestion features for interactive searching [C]//SIGIR ’09. New York：ACM, 2009:371-378.

[12] E. Eftheimiadis. Query expansion [J]. Annual Review of Information Science Technology. 1996, 31:121-187.

[13] J. Koenemann. Relevance feedback：usage, usability, utility [D]. Ph.D. Dissertation, Rutgers University, Dept. of Psychology. 1996.

[14] A. Spink, R.M. Losee. Feedback in information retrieval [J]. Annual Review of Information Sciences Technology. 1996, 31: 33-78.

[15] J. Xu, W.B. Croft. Query expansion using local and global document analysis[C]//Proceedings of 19th ACM-SIGIR Conference on Research and Development in Information Retrieval. New York：ACM, 1996: 4-11.

[16] N. J. Belkin. Intelligent information retrieval：Whose intelligence? Herausforderungen an die Informationswissenschaft[C]//Proceedings des 5. Internationalen Sypmosiums für Informationswissenschaft (ISI ’96). J. Krause, M. Herfurth, and J. Marx, Eds. Universitatsverlag Konstanz, 1996: 25-31.

[17] N. J. Belkin, C. Cool, J. Head, J. Jeng, D. Kelly, S.J. Lin, Lobash, L. Park, P. Savage-Knepshield, and C. Sikora. Relevance feedback versus Local Context Analysis as term suggestion devices[C]//Proceedings of the Eighth Text Retrieval Conference TREC8. Washington, D.C., 2000.

[18] N.J. Belkin. Helping people find what they don’t know [J]. Communications of the ACM. 2000, 43(8): 58-61.

[19] Peter Anick. Using Terminological Feedback for Web Search Refinement - A log-based Study. In SIGIR2003 [C]//New York：ACM, 2003:88-95.

[20] A. Feuer, S. Savev, J. A. Asiam. Evaluation of phrasal query suggestions [C]//CIKM’07. New York：ACM, 2007: 841-847.

[21] R. W. White, M. Bilenko, S. Cucerzan. Studying the use of popular destinations to enhance web search interaction [C]//Proceedings of SIGIR ’07. New York：ACM, 2007: 159-166.

[22] P. Vakkari. Changes in search tactics and relevance judgments when preparing a research proposal：A summary of the findings of a longitudinal study [J]. Information Retrieval. 2004, 4(3-4), 295-310.

[23] J. Jeon, W. B. Croft, and J.H. Lee. Finding similar questions in large question and answer archives [C]//CIKM ’05. New York：ACM. 2005: 84-90.

[24] P. A. Chirita, C. S. Firan, and W. Nejdl. Personalized query expansion for the web[C]//SIGIR ’07. New York：ACM, 2007:7-14.

[25] M. Sahami and T. D. Heilman, A web-based kernel function for measuring the similarity of short text snippets [C]//Proceedings of the 15th international conference on World Wide Web. New York：ACM, 2006: 377-386.

[26] B.M. Fonseca, Golghe, P.B., Moura, E.S.d., and Ziviani, N. Discovering Search Engine Related Queries Using Association Rules [J]. J. Web Eng., 2004, 2(4):215-227.

[27] D. Beeferman and A. Berger. Agglomerative clustering of a search engine query log [C]//SIGKDD ’00. New York：ACM, 2000: 407-416.

[28] S. Chien and N. Immorlica. Semantic similarity between search engine queries using temporal correlation[C]//Proceedings of WWW-05, International Conference on the World Wide Web. New York：ACM, 2005: 798-799.

[29] Paolo Boldi, Francesco Bonchi, Carlos Castillo, Debora Donato, Sebastiano Vigna, Query suggestions using query-flow graphs[C]//Proceedings of the 2009 workshop on Web Search Click Data. Barcelona, Spain, February 09-09, 2009: 56-63.

[30] Y. Qiu and H. P. Frei. Concept based query expansion [C]//SIGIR 1993. New York：ACM, 1993:160-169.

[31] S. Deerwester, S. T. Dumais, G. W. Furnas, T. K. Landauer, and R. Harshman. Indexing by latent semantic analysis [J]. JASIS, 41(6)：391-407. January 1999.

[32] R. W. White and G. Marchionini. Examing the effectiveness of real-time query expansion [J]. Inf. Process. Manage. 2007, 43(3)：685-704.

[33] E. Stoica, M. Hearst, and M. Richardson. Automating creation of hierarchical faceted metadata structures [C]//NAACL/HLT 2007. 2007.

[34] J.-R. Shieh, Y.-H. Hsieh, T.-Ch. Su, Ch.-Y. Lin, J.-L. Wu. Building term suggestion relational graphs from collective intelligence[C]//WWW 2009. New York：ACM, 2009:1091-1092.

[35] Yang Xu, Gareth J.F. Jones, Bin Wang. Query dependent pseudo-relevance feedback based on wikipedia [C]//SIGIR 2009. New York：ACM, 2009:59-66.

[36] Y. Chen, G.-R. Xue, and Y. Yu. Advertising keyword suggestion based on concept hierarchy[C]//Proceedings of the international conference on Web search and web data mining. New York：ACM, 2008: 251-260.

[37] Eric C. Jensen, Steven M. Beitzel, Abdur Chowdhury, Ophir Frieder, Query Phrase Suggestion from Topically Tagged Session Logs[C]//Proceedings of the 7th International Conference on Flexible Query Answering Systems (FQAS 2006), Milan, Italy, June 2006: 185-196.

[38] H. Cao, D. Jiang, J. Pei, Q. He, Z. Liao, E. Chen and H. Li, Context-aware query suggestion by mining click-through and session data[C]//Proceeding of the 14th ACM SIGKDD. New York：ACM, 2008: 875-883.

[39] D. Gayo-Avello. A survey on session detection methods in query logs and a proposal for future evaluation [J]. Information Science：an International Journal. Elsevier Science Inc. May, 2009, 179(12): 1822-1843.

[40] 王繼民,彭波. 搜索引擎用戶點(diǎn)擊行為分析 [J]. 情報(bào)學(xué)報(bào). 2006,25(2).

[41] 李亞楠，許晟，王斌.基于加權(quán)SimRank的中文查詢推薦研究[J].中文信息學(xué)報(bào). 2010, 24(3)：4-10.

[42] R. Baeza-Yates, B. Ribeiro-Neto, Modern Information Retrieval [M]. New York：ACM, and England：Addison-Wesley, 1999.

[43] Yanan Li, Sen Zhang, Bin Wang, Jintao Li, Characteristics of Chinese Web Searching：A Large-Scale Analysis of Chinese Query Logs [J]. Journal of Computational Information Systems, 2008, 4(3)：1127-1136.

[44] D. Gleich, L. Zhukov. SVD based term suggestion and ranking system [C]//ICDM’04. IEEE, 2004.

[45] H Ma, H Yang, I King, M R Lyu. Learning latent semantic relations from clickthrough data for query suggestion [C]//CIKM’08. New York：ACM, 2008:709-718.

[46] Thorsten Joachims, Laura Granka, Bing Pan, Accurately Interpreting Clickthrough Data as Implicit Feedback [C]//SIGIR’05. New York：ACM, 2005.

[47] Shihao Ji, Ke Zhou, Ciya Liao, Zhaohui Zheng, Gui Rong Xue, O. Chapelle, Gordon Sun, Hongyuan Zha. Global ranking by exploiting user clicks[C]//SIGIR’09. New York：ACM, 2009: 35-42.

[48] W.Zhang, J.Yan, Sh.-Ch.Yan, N.Liu, Zh.Chen. Temporal query substitution for ad search[C]//SIGIR’09. New York：ACM, 2009: 798-799.

[49] J.-M.Yang, R.Cai, F.Jing, Sh.Wang, L.Zhang, W.-Y.Ma. Search-based query suggestion[C]//CIKM’08. New York：ACM, 2008.

[50] Yanan Li, Bin Wang, Sheng Xu, Peng Li, Jintao Li. QueryTrans：Finding Similar Queries Based on Query Trace Graph[C]//Proceedings of the 2009 IEEE / WIC / ACM Joint Conference on Web Intelligence. September 15th-18th, 2009:260-263.

[51] Q. Mei, D. Zhou, and K. Church. Query suggestion using hitting time [C]//CIKM ’08. New York：ACM, 2008:469-478.

[52] Zh.-Y.Zhang, O.Nasraoui. Mining Search Engine Query Logs for Query Recommendation [C]//WWW’06//New York：ACM, 2006: 1039-1040.

[53] Azarakhsh Malekian, Chi-Chao Chang, Ravi Kumar, Grant Wang. Optimizing query rewrites for keyword-based advertising [C]//EC ’08：Proceedings of the 9th ACM conference on Electronic commerce. 2008:10-19.

[54] E. M. Voorhees. The philosophy of information retrieval evaluation[C]//In Proceedings of the Second Workshop of the Cross-Language Evaluation Forum, (CLEF 2001), 2001: 355-370.

[55] R. Baeza-Yates and A. Tiberi. Extracting semantic relations from query logs[C]//KDD’07. New York：ACM, 2007:76-85.

[56] Hongbo Deng, Irwin King, Micheal R.lyu. Entropy-biased Models for Query Representation on Click Graph [C]//SIGIR’09. New York：ACM, 2009: 339-346.

[57] 姜文彬. 搜索引擎相關(guān)關(guān)鍵詞推薦的對(duì)比研究 [J]. 現(xiàn)代圖書情報(bào)技術(shù). 2009, 180:35-40.

[58] Xiaoyan Shen, Bo Cheng, Junliang Chen, Xiangwu Meng. An Effective Method for Chinese Related Queries Recommendation[C]//Proceedings of the 2008 Ninth ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing table of contents. 2008: 381-386.