朱小飛，郭嘉豐，程學(xué)旗，杜 攀

(1. 中國(guó)科學(xué)院 計(jì)算技術(shù)研究所, 北京 100190;2. 中國(guó)科學(xué)院 研究生院, 北京 100049; 3. 重慶理工大學(xué) 數(shù)理學(xué)院，重慶 400054)

1 引文

目前，互聯(lián)網(wǎng)上存儲(chǔ)了大量的信息，搜索引擎已經(jīng)成為用戶(hù)訪(fǎng)問(wèn)這些信息最有效的途徑。用戶(hù)通過(guò)輸入想要查詢(xún)的關(guān)鍵字到搜索引擎，然后搜索引擎返回搜索結(jié)果供用戶(hù)使用。然而，構(gòu)造一個(gè)合適的查詢(xún)并不是一件輕松的事情，一方面因?yàn)椴樵?xún)通常比較短[1](1～2個(gè)詞)并且存在歧義性[2](例如java，apple等)，另一方面，由于用戶(hù)對(duì)所查詢(xún)的內(nèi)容不熟悉，使得自身對(duì)要查詢(xún)什么內(nèi)容不清楚，例如用戶(hù)輸入harry potter，他可能是對(duì)名字叫harry potter的一款游戲感興趣，或者對(duì)同名的電影感興趣，也可能對(duì)同名的小說(shuō)感興趣。如何幫助用戶(hù)更好的找到需要的信息已經(jīng)成為一個(gè)至關(guān)重要的問(wèn)題。

查詢(xún)推薦通過(guò)向用戶(hù)推薦相關(guān)的查詢(xún)，以幫助用戶(hù)構(gòu)造更有效的查詢(xún)，目前已經(jīng)成為一個(gè)十分重要的研究方向。一些著名的搜索引擎公司(如Google和Yahoo)開(kāi)始為用戶(hù)提供查詢(xún)推薦系統(tǒng)，以幫助用戶(hù)更方便地找到所需要的信息。

傳統(tǒng)的查詢(xún)推薦方法主要關(guān)注于向用戶(hù)推薦相關(guān)的查詢(xún)，通過(guò)度量候選查詢(xún)與用戶(hù)所提交查詢(xún)的相關(guān)程度，對(duì)候選查詢(xún)進(jìn)行排序，并推薦最相關(guān)的前k個(gè)查詢(xún)給用戶(hù)。這種方法可以有效地幫助用戶(hù)構(gòu)造更恰當(dāng)?shù)牟樵?xún)，但同時(shí)也存在一些問(wèn)題：(1) 相關(guān)性度量問(wèn)題。傳統(tǒng)查詢(xún)推薦方法通常在歐式空間上計(jì)算查詢(xún)之間的相似性，但由于查詢(xún)?nèi)罩局械牟樵?xún)具有高維稀疏性，傳統(tǒng)的相似度度量方法往往不能很好的反應(yīng)用戶(hù)查詢(xún)之間的相關(guān)性。例如，在基于關(guān)鍵詞來(lái)度量查詢(xún)之間的相似性時(shí)，由于兩個(gè)相關(guān)的查詢(xún)(如“national basketball association”和“nba”)之間沒(méi)有相同的查詢(xún)關(guān)鍵詞，從而被認(rèn)為是不相關(guān)；或者在基于用戶(hù)點(diǎn)擊的URL來(lái)計(jì)算查詢(xún)之間的相似性時(shí)，兩個(gè)相關(guān)的查詢(xún)因?yàn)闆](méi)有點(diǎn)擊相同的URL(因用戶(hù)結(jié)果點(diǎn)擊的稀疏性)，會(huì)導(dǎo)致其被認(rèn)為不相關(guān)。(2)冗余性問(wèn)題。由于僅關(guān)注候選查詢(xún)與源查詢(xún)的相關(guān)性，使得傳統(tǒng)的推薦方法所推薦的查詢(xún)存在較大的冗余性(推薦的查詢(xún)之間的差異性小)，例如當(dāng)用戶(hù)輸入查詢(xún)“abc”時(shí)，系統(tǒng)可能會(huì)同時(shí)向用戶(hù)推薦“abc television”和“abc tv”，而這兩個(gè)查詢(xún)其實(shí)是表達(dá)了相同的意思。

為了避免傳統(tǒng)查詢(xún)推薦方法中存在的問(wèn)題，已有研究人員提出一些解決方法，例如Mei等人[3]基于隨機(jī)游走(random walk)提出了通過(guò)計(jì)算各候選查詢(xún)到源查詢(xún)的游走時(shí)間(hitting time)來(lái)進(jìn)行查詢(xún)推薦(文中使用Hitting-time Ranking來(lái)表示)，該方法可以有效地推薦長(zhǎng)尾(long tail)的查詢(xún)給用戶(hù)，以降低查詢(xún)推薦的冗余性。然而通過(guò)這種方法獲得的長(zhǎng)尾查詢(xún)往往不常見(jiàn)，相關(guān)性也無(wú)法得到保證，因此會(huì)影響到推薦的有效性和實(shí)用性。

針對(duì)已有查詢(xún)推薦方法的不足，我們提出了一種基于流形排序的查詢(xún)推薦方法(文中使用Manifold Ranking來(lái)表示)。通過(guò)把用戶(hù)查詢(xún)建模在流形結(jié)構(gòu)上，我們可以利用查詢(xún)數(shù)據(jù)內(nèi)在流形結(jié)構(gòu)來(lái)獲得查詢(xún)之間的相關(guān)性，從而有效避免傳統(tǒng)方法的相關(guān)性度量問(wèn)題。此外，基于查詢(xún)的流形結(jié)構(gòu)，我們使用流形排序算法來(lái)對(duì)候選查詢(xún)進(jìn)行排序和推薦，由于各查詢(xún)的排序得分不再僅來(lái)自于源查詢(xún)，同時(shí)也來(lái)自于其鄰居查詢(xún)，從而使得那些結(jié)構(gòu)上與源查詢(xún)相近并且具有代表性的查詢(xún)(那些具有較多鄰居結(jié)點(diǎn)的查詢(xún))獲得更大的排序得分。由此可見(jiàn)，和Hitting-time Ranking不同，Manifold Ranking是通過(guò)提升那些結(jié)構(gòu)上具有代表性的查詢(xún)來(lái)減小查詢(xún)推薦的冗余性。

我們使用了一個(gè)大規(guī)模商業(yè)搜索引擎用戶(hù)查詢(xún)?nèi)罩緛?lái)進(jìn)行實(shí)驗(yàn)，該查詢(xún)?nèi)罩景s1 500萬(wàn)條用戶(hù)查詢(xún)記錄。我們將Manifold Ranking與兩種基準(zhǔn)方法：基于傳統(tǒng)的相似性排序算法(Na?ve Ranking)和Hitting-time Ranking進(jìn)行比較，并通過(guò)一個(gè)自動(dòng)評(píng)價(jià)機(jī)制來(lái)對(duì)各方法所推薦查詢(xún)的相關(guān)性和差異性進(jìn)行評(píng)價(jià)。實(shí)驗(yàn)結(jié)果表明，Manifold Ranking方法在保持較高相關(guān)性的條件下，明顯地提高了查詢(xún)推薦的差異性，在整體上要優(yōu)于Na?ve Ranking和Hitting-time Ranking方法。

本文的組織結(jié)構(gòu)如下：第2節(jié)介紹相關(guān)的研究工作，基于Manifold Ranking的查詢(xún)推薦方法將在第3節(jié)進(jìn)行討論，第4節(jié)給出了實(shí)驗(yàn)結(jié)果及其評(píng)價(jià)，結(jié)論將在最后一節(jié)給出。

2 相關(guān)工作

查詢(xún)?nèi)罩咀鳛橐环N用戶(hù)產(chǎn)生的數(shù)據(jù)，是眾多用戶(hù)在使用搜索引擎進(jìn)行查詢(xún)操作時(shí)的日志記錄，其包含大量有價(jià)值的信息，被稱(chēng)為“大眾智慧”(wisdom of crowds)[4]。近年來(lái)，許多研究工作開(kāi)始使用查詢(xún)?nèi)罩局械腸lick-through data來(lái)挖掘查詢(xún)之間的語(yǔ)義相關(guān)關(guān)系，這種相關(guān)關(guān)系可以被用來(lái)進(jìn)行查詢(xún)推薦。例如，Beeferman等人[5]通過(guò)對(duì)query-URL二部圖上使用凝聚聚類(lèi)算法來(lái)發(fā)現(xiàn)相關(guān)查詢(xún)；Wen等人[6]同時(shí)考慮使用click-through data和查詢(xún)及文檔的內(nèi)容信息來(lái)確定相似查詢(xún)。Li等人[7]提出了一個(gè)兩階段的查詢(xún)推薦方法：發(fā)現(xiàn)階段和排序階段。在發(fā)現(xiàn)階段，使用基于query-URL向量來(lái)計(jì)算查詢(xún)之間的相似度；在排序階段，使用層次凝聚聚類(lèi)算法來(lái)對(duì)相似查詢(xún)進(jìn)行排序。Baeza-Yates等人[8]基于query-URL二部圖定義了3種連邊類(lèi)型：identical cover，strict complete cover和partial cover，并以此計(jì)算查詢(xún)間的語(yǔ)義關(guān)系。以上研究工作共同的特點(diǎn)是僅關(guān)注于推薦相關(guān)的查詢(xún)。Mei等人[3]在query-URL二部圖上使用隨機(jī)游走方法，依據(jù)各候選查詢(xún)到源查詢(xún)的游走時(shí)間來(lái)對(duì)查詢(xún)進(jìn)行排序，可以有效的推薦長(zhǎng)尾的查詢(xún)，但是其缺點(diǎn)在于：由于推薦長(zhǎng)尾的查詢(xún)可能與源查詢(xún)相關(guān)程度不高，降低了查詢(xún)推薦的相關(guān)性。

Manifold Ranking是由Zhou等人[9-10]首先提出，與傳統(tǒng)的歐式空間上直接計(jì)算查詢(xún)之間的相似性不同，該方法通過(guò)利用大規(guī)模數(shù)據(jù)內(nèi)在的全局流形結(jié)構(gòu)來(lái)計(jì)算排序得分。直觀的解釋為：首先構(gòu)造一個(gè)帶權(quán)網(wǎng)絡(luò)，并且分配給源節(jié)點(diǎn)一個(gè)正的得分，其他待排序節(jié)點(diǎn)的得分設(shè)為0，然后每一個(gè)節(jié)點(diǎn)將其自身得分傳播到鄰居節(jié)點(diǎn)直到整個(gè)網(wǎng)絡(luò)達(dá)到平衡狀態(tài)。除源節(jié)點(diǎn)外的所有節(jié)點(diǎn)按照最終得分大小進(jìn)行排序(得分越大，排序越靠前)。目前Manifold Ranking已經(jīng)被用來(lái)對(duì)圖像或文檔摘要進(jìn)行排序，并取得很好的效果。例如，He等人[11]基于Manifold Ranking進(jìn)行圖像排序，其利用所有數(shù)據(jù)之間的關(guān)系，來(lái)測(cè)量輸入查詢(xún)與所有圖片的相關(guān)性。Wan[12]等人使用Manifold Ranking來(lái)進(jìn)行主題相關(guān)的多文檔摘要，通過(guò)利用文檔中所有句子相關(guān)性以及句子與主題的相關(guān)性，并基于貪心算法來(lái)實(shí)現(xiàn)有差異的文檔摘要。

3 我們的工作

在這一部分的內(nèi)容中，我們?cè)敿?xì)描述了如何使用click-through data來(lái)構(gòu)造查詢(xún)的流形結(jié)構(gòu)，然后在此基礎(chǔ)上使用Manifold Ranking方法來(lái)進(jìn)行查詢(xún)推薦的過(guò)程。

3.1 基本概念

給定一組查詢(xún)?chǔ)?{x0,x1,…,xn}?m，第一個(gè)查詢(xún)x0表示源查詢(xún)，其他查詢(xún)xi(1≤i≤n)為候選查詢(xún)。令d:χ×χ→表示χ上的一個(gè)度量，其中d(xi,xj)表示查詢(xún)xi和xj的距離(如歐式距離)。f:χ→為排序函數(shù)，其為每一個(gè)查詢(xún)xi(0≤i≤n)計(jì)算一個(gè)排序得分fi，這里我們可以將f看成是一個(gè)向量f=[f0,f1,…,fn]T。同時(shí)，定義向量y=[y0,y1,…,yn]T，其中y0=1(x0是源查詢(xún))，yi=0(1≤i≤n)。

3.2 構(gòu)造查詢(xún)的流形結(jié)構(gòu)

圖1 query-URL二部圖

(1)

wij=e-d(xi,xj)2/2σ2

(2)

令wii=0。此外，若帶權(quán)網(wǎng)絡(luò)中邊所對(duì)應(yīng)的兩個(gè)查詢(xún)不是互為k近鄰 (k=50)，則刪除此邊，以保持帶權(quán)網(wǎng)絡(luò)的稀疏性。至此，我們得到了一個(gè)查詢(xún)帶權(quán)網(wǎng)絡(luò)(即查詢(xún)流形結(jié)構(gòu))，其可以用一個(gè)仿射矩陣W=[wij]來(lái)描述。Manifold Ranking 算法如下：

1. Compute the pair-wise similarity valueswijbetween queriesiandj, and then construct a weighted network. The affinity matrixWis defined byW=[wij].

2. Symmetrically normalizeWbyS=D-1/2WD-1/2, in whichDis the diagonal matrix with (i,i)-element equal to the sum of thei-th row ofW.

3. Iteratef(t+1)=αSf(t)+(1-α)yuntil convergence, whereαis a parameter in [0,1), started withf(0)=0.

3.3 Manifold Ranking 方法

基于以上定義的查詢(xún)流形結(jié)構(gòu)，我們使用流形排序算法來(lái)進(jìn)行查詢(xún)排序和推薦。首先，我們對(duì)W進(jìn)行對(duì)稱(chēng)規(guī)范化：S=D-1/2WD-1/2，其中D為對(duì)角矩陣，其對(duì)角元素分別為W各行元素之和。然后，按照下面的迭代公式：

f(t+1)=αSf(t)+(1-α)y

(3)

迭代至f收斂。其中，α用來(lái)控制來(lái)自于先驗(yàn)的得分和來(lái)自于結(jié)構(gòu)上相鄰的結(jié)點(diǎn)得分對(duì)最終排序得分的貢獻(xiàn)，α值越大表示來(lái)自于相鄰的節(jié)點(diǎn)得分貢獻(xiàn)所占比例越大(α∈[0,1))。

Manifold Ranking的過(guò)程可以形象地描述為：首先構(gòu)造一個(gè)帶權(quán)網(wǎng)絡(luò)，網(wǎng)絡(luò)中每一個(gè)節(jié)點(diǎn)對(duì)應(yīng)于一個(gè)查詢(xún)；初始化時(shí)，給源查詢(xún)賦以一個(gè)正的排序得分，其余候選查詢(xún)的排序得分為0；網(wǎng)絡(luò)中所有的節(jié)點(diǎn)將其得分傳播給與其相鄰的節(jié)點(diǎn)，當(dāng)網(wǎng)絡(luò)達(dá)到全局平衡狀態(tài)時(shí)，傳播過(guò)程停止；所有候選查詢(xún)的得分將被用來(lái)對(duì)候選查詢(xún)進(jìn)行排序，并將排序最前的k個(gè)候選查詢(xún)推薦給用戶(hù)。Manifold Ranking算法的詳細(xì)過(guò)程，文獻(xiàn)[9]中證明了f最終會(huì)收斂到:

f*=β(I-αS)-1y

(4)

其中β=1-α，雖然可以直接使用(4)式來(lái)計(jì)算f*，但是由于涉及到計(jì)算逆矩陣(I-αS)-1，當(dāng)數(shù)據(jù)規(guī)模較大時(shí)，需要的計(jì)算開(kāi)銷(xiāo)很大，因此與大多數(shù)研究工作[10-11]一樣，我們這里選擇使用迭代方式來(lái)計(jì)算f*。

此外，為了減小計(jì)算開(kāi)銷(xiāo)同時(shí)又不影響算法的有效性，我們從源查詢(xún)出發(fā)使用廣度優(yōu)先搜索構(gòu)造一個(gè)子圖，直到子圖中的查詢(xún)節(jié)點(diǎn)達(dá)到預(yù)先指定的數(shù)目。子圖的每一個(gè)節(jié)點(diǎn)(除源查詢(xún)節(jié)點(diǎn)外)可以看成是源查詢(xún)的一個(gè)候選查詢(xún)，那些不在子圖中的節(jié)點(diǎn)，由于離源查詢(xún)節(jié)點(diǎn)足夠遠(yuǎn)，以至于不可能被推薦給用戶(hù)，將這部分節(jié)點(diǎn)去除，不會(huì)影響實(shí)際查詢(xún)推薦的效果，但可以有效的減小算法計(jì)算開(kāi)銷(xiāo)。

4 實(shí)驗(yàn)結(jié)果及評(píng)價(jià)

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

我們使用一個(gè)商業(yè)搜索引擎的查詢(xún)?nèi)罩咀鳛閿?shù)據(jù)集，該查詢(xún)?nèi)罩居涗浟?006年5月1日至2006年5月31日期間的1 500萬(wàn)條查詢(xún)。對(duì)于每一個(gè)查詢(xún)，日志中記錄其相應(yīng)的信息，包括查詢(xún)ID，查詢(xún)?cè)~本身，所點(diǎn)擊的URL，URL的位置信息，時(shí)間戳，用戶(hù)Session ID，URL在結(jié)果頁(yè)面中的排序，以及返回的結(jié)果數(shù)目。我們對(duì)查詢(xún)?nèi)罩具M(jìn)行預(yù)處理：只保留英文查詢(xún)，并用空格替代查詢(xún)中的標(biāo)點(diǎn)符號(hào)，不執(zhí)行詞干還原和去除停用詞的操作。為了減小噪音數(shù)據(jù)帶來(lái)的影響，對(duì)于每個(gè)查詢(xún)要求用戶(hù)的點(diǎn)擊次數(shù)不能小于3次。表1是所獲得的query-URL二部圖的統(tǒng)計(jì)信息。

表1 query-URL二部圖的統(tǒng)計(jì)信息

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

評(píng)價(jià)查詢(xún)推薦是一件十分困難的事情，因?yàn)閷?duì)于一個(gè)查詢(xún)來(lái)說(shuō)并不存在某種標(biāo)準(zhǔn)的推薦結(jié)果。為了使評(píng)價(jià)結(jié)果更為客觀合理，這里我們采用了一種自動(dòng)評(píng)價(jià)的策略。該策略使用開(kāi)放式分類(lèi)目錄搜索系統(tǒng)ODP (the Open Directory Project)和Google的檢索結(jié)果作為評(píng)價(jià)數(shù)據(jù)資源，對(duì)查詢(xún)推薦結(jié)果的相關(guān)性和差異性進(jìn)行評(píng)價(jià)。ODP是目前最大的人工編制的分類(lèi)檢索系統(tǒng)，已經(jīng)被一些研究人員用來(lái)作為評(píng)價(jià)數(shù)據(jù)，例如Baykan等人[13]使用ODP作為URL主題類(lèi)別信息來(lái)評(píng)價(jià)分類(lèi)結(jié)果，Baeza-Yates等人[8]使用其評(píng)價(jià)查詢(xún)的語(yǔ)義相關(guān)性。

4.2.1 相關(guān)性指標(biāo)

對(duì)于ODP中的兩個(gè)類(lèi)別ci和cj，我們定義其相關(guān)度為類(lèi)別的相同前綴長(zhǎng)度與類(lèi)別最大長(zhǎng)度的商，形式化的表示為s(ci,cj)=|l(ci,cj)|/max{|ci|,|cj|}，其中|l(ci,cj)|為類(lèi)別ci和cj相同前綴長(zhǎng)度，|c|為類(lèi)別c的長(zhǎng)度。舉例來(lái)講，兩個(gè)目錄“Arts/Television/News” 和“Arts/Television/Stations/North_America/United_States”的相關(guān)度為2/5。因?yàn)槠湎嗤熬Y為“Arts/Television/”，長(zhǎng)度為2，而最大類(lèi)別為“Arts/Television/Stations/North_America/United_States”，長(zhǎng)度為5。

對(duì)于每個(gè)查詢(xún)，在抓取Google Directory中前k個(gè)ODP目錄作為該查詢(xún)對(duì)應(yīng)的類(lèi)別集合，設(shè)C和C′分別為查詢(xún)q和q′所對(duì)應(yīng)的ODP類(lèi)別集合，類(lèi)似于文獻(xiàn)[8]，我們用類(lèi)別集合C與C′之間最相似的兩個(gè)類(lèi)別的相關(guān)度來(lái)衡量查詢(xún)q和q′相關(guān)性。形式化表示為:

(5)

因此，對(duì)于給定的源查詢(xún)q，其推薦查詢(xún)結(jié)果的相關(guān)性指標(biāo)定義為：所有推薦查詢(xún)與q的平均相關(guān)性，形式化表示為:

(6)

其中S為源查詢(xún)q的推薦查詢(xún)集合，|S|為推薦查詢(xún)集合中查詢(xún)數(shù)目。

4.2.2 差異性指標(biāo)

對(duì)于每個(gè)查詢(xún)q，我們抓取Google前k個(gè)搜索結(jié)果的URL，作為查詢(xún)q對(duì)應(yīng)的URL集合。查詢(xún)q和q′的差異度可以定義為：查詢(xún)q和q′的URL集合中相異的URL的數(shù)目所占的比例，形式化表示為：d(q,q′)=1-|o(q,q′)|/k，其中|o(q,q′)|是查詢(xún)q和q′的URL集合中相同URL的數(shù)目。因此，對(duì)于給定的源查詢(xún)q，其推薦查詢(xún)結(jié)果的差異性指標(biāo)定義為：所有推薦查詢(xún)兩兩之間的平均差異度，形式化表示為:

(7)

其中S為源查詢(xún)q的推薦查詢(xún)集合，|S|為推薦查詢(xún)集合中查詢(xún)數(shù)目。

4.3 實(shí)驗(yàn)結(jié)果及分析

我們隨機(jī)抽取了150個(gè)查詢(xún)作為測(cè)試樣本，類(lèi)似于文獻(xiàn)[14]，我們要求這些查詢(xún)的各自總的URL點(diǎn)擊次數(shù)介于700至15 000次之間，這樣做的目的是為了避免選擇那些過(guò)于頻繁出現(xiàn)的查詢(xún)(例如www, car, book等查詢(xún)，因?yàn)閷?duì)其進(jìn)行推薦沒(méi)有實(shí)質(zhì)意義)和過(guò)于不頻繁出現(xiàn)的查詢(xún)(查詢(xún)?nèi)罩局胁淮嬖诳梢酝扑]的查詢(xún))。其他參數(shù)設(shè)置為：算法迭代的次數(shù)設(shè)置為30, α=0.99, σ=1.25。

我們將基于Manifold Ranking的查詢(xún)推薦方法，與另外兩種查詢(xún)推薦方法(Na?ve Ranking，Hitting-time Ranking)進(jìn)行了實(shí)驗(yàn)比較，實(shí)驗(yàn)結(jié)果分別顯示在表2和表3*注：我們沒(méi)有列出推薦數(shù)目為1的差異性指標(biāo)，因?yàn)椴町愋灾笜?biāo)是計(jì)算推薦查詢(xún)兩兩之間的平均差異度，當(dāng)推薦數(shù)目為1時(shí)，計(jì)算出來(lái)的差異性指標(biāo)沒(méi)有評(píng)價(jià)意義。中。表2是對(duì)三種不同方法的相關(guān)性指標(biāo)進(jìn)行比較，從表2中我們可以看到Manifold Ranking與Na?ve Ranking的查詢(xún)推薦結(jié)果在相關(guān)性指標(biāo)方面接近相同(Na?ve Ranking的平均相關(guān)性指標(biāo)為0.891，Manifold Ranking平均相關(guān)性指標(biāo)為0.898)；而Hitting-time Ranking的查詢(xún)推薦結(jié)果在相關(guān)性指標(biāo)方面要明顯低于前兩種方法(Hitting-time的平均相關(guān)性指標(biāo)只有0.859)，這主要是因?yàn)镠itting-time Ranking方法過(guò)于強(qiáng)調(diào)推薦長(zhǎng)尾的查詢(xún)，其計(jì)算候選查詢(xún)到源查詢(xún)的游走時(shí)間來(lái)作為推薦依據(jù)，而忽略了這樣一個(gè)事實(shí)：候選查詢(xún)到源查詢(xún)的游走時(shí)間的值小，并不意味著源查詢(xún)到候選查詢(xún)的游走時(shí)間的值也小，這就造成推薦的查詢(xún)與源查詢(xún)相關(guān)性不高。表3是對(duì)三種不同方法的差異性指標(biāo)(所推薦查詢(xún)的冗余性越大，其差異性指標(biāo)越低)進(jìn)行比較，從表3中我們可以看到Manifold Ranking與Hitting-time Ranking的查詢(xún)推薦結(jié)果在差異性指標(biāo)方面要顯著高于Na?ve Ranking方法(Hitting-time Ranking與Manifold Ranking的平均差異性指標(biāo)比Na?ve Ranking方法分別提高了 4.9 和2.1個(gè)百分點(diǎn))。從差異性指標(biāo)比較的結(jié)果來(lái)講，Hitting-time Ranking要優(yōu)于Manifold Ranking的推薦結(jié)果。但是如前面分析的結(jié)果所示，Hitting-time Ranking的平均相關(guān)性指標(biāo)比Na?ve Ranking低了3.9個(gè)百分點(diǎn)，而Manifold Ranking平均相關(guān)性指標(biāo)和Na?ve Ranking基本相同。從查詢(xún)推薦的角度來(lái)講，我們希望所推薦的查詢(xún)與源查詢(xún)盡可能相關(guān)，同時(shí)所推薦的查詢(xún)之間又盡可能保持差異性?？紤]查詢(xún)推薦的相關(guān)性與差異性，我們可以得到以下結(jié)論：Manifold Ranking其在不損失相關(guān)性的條件下，明顯的提高了查詢(xún)推薦的差異性，整體上要優(yōu)于Na?ve Ranking和Hitting-time Ranking。

表2 三種查詢(xún)推薦方法(Na?ve Ranking, Hitting-timeRanking,Manifold Ranking)在不同推薦數(shù)目下相關(guān)性指標(biāo)的比較

表3 三種查詢(xún)推薦方法(Na?ve Ranking, Hitting-timeRanking,Manifold Ranking)在不同推薦數(shù)目下差異性指標(biāo)的比較

5 結(jié)論

本文中，我們提出了一種基于流形排序的查詢(xún)推薦方法，該方法通過(guò)利用查詢(xún)數(shù)據(jù)內(nèi)在全局的流形結(jié)構(gòu)來(lái)進(jìn)行查詢(xún)推薦，避免了傳統(tǒng)查詢(xún)推薦方法在相關(guān)性度量方面和冗余性方面的不足。與現(xiàn)有Hitting-time Ranking相比，Manifold Ranking通過(guò)提升結(jié)構(gòu)上具有代表性的查詢(xún)，從而使得所推薦的查詢(xún)與源查詢(xún)差異性得到的提高，同時(shí)保持較高的相關(guān)性。在一個(gè)大規(guī)模商業(yè)搜索引擎查詢(xún)?nèi)罩旧系膶?shí)驗(yàn)結(jié)果表明，Manifold Ranking要明顯優(yōu)于兩種基準(zhǔn)方法(Na?ve Ranking和Hitting-time Ranking)。

[1] H. Cui, J.-R. Wen, J.-Y. Nie, and et al. Probabilistic query expansion using query logs[C]//WWW ’02, 2002: 325-332.

[2] J.-R. Wen, J.-Y. Nie, and H.-J. Zhang. Clustering user queries of a search engine[C]//WWW ’01, 2001: 162-168.

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

[4] J. Surowiecki. The wisdom of crowds: why the many are smarter than the few and how collective wisdom shapes business[C]//Doubleday, Reading, MA, 2004.

[5] D. Beeferman and A. Berger. Agglomerative clustering of a search engine query log [C]//KDD ’00, 2000: 407-416.

[6] J.-R.Wen, J.-Y. Nie, and H.-J. Zhang. Clustering user queries of a search engine[C]//WWW ’01, 2001: 162-168.

[7] L. Li, Z. Yang, and et al. Query-url bipartite based approach to personalized query recommendation[C]//AAAI’08, 2008: 1189-1194.

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

[9] D. Zhou, O. Bousquet, T. N. Lal, and et al. Learning with local and global consistency[C]//NIPS’03, 2003.

[10] D. Zhou, J. Weston, A. Gretton, and et al. Ranking on data manifolds[C]//NIPS’03, 2003.

[11] J. He, M. Li, H.-J. Zhang, and et al. Manifold-ranking based image retrieval[C]//MULTIMEDIA’04, 2004: 9-16.

[12] X. Wan, J. Yang, and J. Xiao. Manifold-ranking based topic-focused multi-document summarization[C]//IJCAI’07, 2007: 2903-2908.

[13] E. Baykan, M. Henzinger, L. Marian, and I. Weber. Purely url-based topic classification[C]//WWW ’09, 2009: 1109-1110.

[14] P. Boldi, F. Bonchi, C. Castillo, and et al. Query suggestions using query-flow graphs[C]//WSCD ’09, 2009: 56-63.