李亞楠,許 晟,王 斌

(1.中國科學(xué)院計(jì)算技術(shù)研究所,北京100190;2.中國科學(xué)院研究生院,北京100049)

1 引言

目前搜索引擎采用的主要交互方式是用戶自主輸入查詢,檢索系統(tǒng)根據(jù)輸入的查詢提供檢索結(jié)果。但是,很多時(shí)候用戶難以精確表達(dá)其意圖。研究表明,用戶輸入的查詢通常較短[1],只有25%的查詢能清晰表達(dá)用戶的意圖[2]。為了幫助用戶完善查詢,查詢推薦(Query Suggestion)被廣泛用于向用戶推薦若干與用戶輸入查詢相關(guān)的查詢,其既方便了用戶構(gòu)造查詢,也幫助搜索引擎更準(zhǔn)確地定位到用戶的檢索意圖。在搜索引擎中廣泛使用的“相關(guān)搜索”就屬于查詢推薦技術(shù)的一個(gè)實(shí)際應(yīng)用。此外,查詢推薦所用的相關(guān)技術(shù)不僅局限于搜索引擎,也廣泛運(yùn)用在計(jì)算廣告、電子商務(wù)中的商品推薦等應(yīng)用中,具有廣泛的應(yīng)用價(jià)值。

查詢推薦的目的在于向用戶推薦與其輸入查詢相關(guān)的其他查詢。目前,查詢推薦主要通過查詢間的共有屬性直接計(jì)算查詢間的相關(guān)度,例如查詢共同出現(xiàn)在同一搜索過程的次數(shù)[3-4]、查詢共有的點(diǎn)擊URL數(shù)[5-6]、查詢間的文本相似度[7-8]等。盡管這些方法在一些查詢上取得了好的推薦結(jié)果,然而由于用戶查詢具有多樣性(查詢?nèi)罩局型瑤浊f甚至上億不同的查詢)、稀疏性(多數(shù)查詢出現(xiàn)次數(shù)很少,可利用屬性信息很有限)、歧義性(一些屬性特征具有歧義,例如“汽車引擎”和“搜索引擎”都包含特征詞“引擎”,意義卻不相關(guān)),很多時(shí)候,直接根據(jù)屬性特征計(jì)算查詢間相關(guān)度無法給出有效的推薦結(jié)果。

很多查詢之間存在隱含或間接聯(lián)系,兩個(gè)不能直接匹配的相關(guān)查詢往往有著相同或相似的相關(guān)查詢。例如“李彥宏”與“李開復(fù)”均與“搜索引擎公司”有關(guān)因而兩者相似。基于這一簡單思想,本文將查詢映射到一個(gè)查詢關(guān)系圖中,圖中節(jié)點(diǎn)表示查詢,邊表示查詢中某種直接聯(lián)系。而后,根據(jù)結(jié)構(gòu)相似度算法并針對查詢推薦應(yīng)用問題,提出加權(quán)Sim Rank(簡稱WSimRank)計(jì)算圖中查詢(節(jié)點(diǎn))間相似度。對查詢對(qi,qj)間的相似度S(qi,qj),WSim Rank根據(jù)查詢qi和查詢qj各自鄰居查詢之間的相似度計(jì)算S(qi,qj)。WSim Rank綜合利用了多個(gè)查詢的相關(guān)屬性特征信息計(jì)算兩個(gè)查詢間相似度,因此一定程度上克服了查詢的多樣性、稀疏性和歧義性帶來的問題。

在大規(guī)模真實(shí)搜索引擎日志上,我們實(shí)現(xiàn)了幾種近年來提出的查詢推薦方法并將它們與基于Sim Rank和WSimRank的方法對比。實(shí)驗(yàn)結(jié)果表明,WSim Rank在查詢推薦覆蓋率、相關(guān)性等各項(xiàng)評(píng)價(jià)指標(biāo)上均優(yōu)于其他方法,其MAP接近0.9。

本文的主要貢獻(xiàn)在于：

?有別于以往方法直接計(jì)算查詢間相似度,本文基于查詢間直接屬性關(guān)聯(lián)建立起一個(gè)查詢關(guān)系圖,將查詢推薦問題轉(zhuǎn)化成一個(gè)有向帶權(quán)圖上的節(jié)點(diǎn)相似度問題,利用查詢間直接聯(lián)系挖掘出相關(guān)查詢間的間接聯(lián)系。

?本文引入一個(gè)通用的基于圖結(jié)構(gòu)的相似度算法——SimRank——來解決查詢推薦問題,并對它進(jìn)行改造得到WSimRank算法,它在計(jì)算上收斂,并且大幅提高了推薦查詢的相關(guān)性,相對于Sim-Rank,WSim Rank使得MAP提高了42.2%。

?針對WSimRank在實(shí)際使用中面臨的運(yùn)行效率問題提出優(yōu)化措施,將其計(jì)算過程轉(zhuǎn)化成一個(gè)狀態(tài)層次圖的搜索遍歷求和問題,并采用動(dòng)態(tài)規(guī)劃思想和剪枝策略優(yōu)化了運(yùn)行空間和時(shí)間,同時(shí)提高了結(jié)果精度和運(yùn)行效率。

本文內(nèi)容將按如下方式組織：第2節(jié)介紹查詢推薦的相關(guān)工作;第3節(jié)說明查詢關(guān)系圖的構(gòu)造;第4節(jié)給出Sim Rank算法;第5節(jié)闡述WSim Rank及其優(yōu)化方法;第6節(jié)展示實(shí)驗(yàn)結(jié)果和分析;最后,本文在第7節(jié)進(jìn)行總結(jié)。

2 相關(guān)工作

根據(jù)文獻(xiàn)[4],查詢推薦技術(shù)根據(jù)推薦內(nèi)容的來源分為兩類：基于文檔的方法和基于日志的方法?；谖臋n的方法從文檔中抽取查詢相關(guān)詞并構(gòu)造推薦查詢?；谌罩镜姆椒◤乃阉饕娌樵?nèi)罩局胁檎遗c當(dāng)前用戶查詢相關(guān)的其他查詢作為推薦。

基于文檔的方法包括偽相關(guān)反饋[10]、隱性語義索引(Latent Semantic Index)[11]等從文檔中尋找查詢相關(guān)詞的方法。傳統(tǒng)的基于文檔的查詢擴(kuò)展和查詢重構(gòu)方法也可以用于查詢推薦。這些方法幾乎可以處理各種查詢,即便對于罕見查詢,只要能找到其相關(guān)的文檔,也同樣可以處理,但是找出查詢相關(guān)文檔本身又是一個(gè)問題,會(huì)引入不相關(guān)文檔從而降低準(zhǔn)確度。此外,有研究工作[12]采用詞典(例如WordNet)、人工編輯語料(如 Wikipedia、Open Directory Pro ject)或其他資源產(chǎn)生查詢相關(guān)詞進(jìn)行查詢推薦。這類方法推薦結(jié)果往往比較準(zhǔn)確,但是難以處理那些尚未編輯的新出現(xiàn)詞語,而新詞卻在用戶搜索中占很大比例。

即便基于文檔的方法發(fā)現(xiàn)了查詢相關(guān)詞,如何用這些相關(guān)詞構(gòu)造出符合用戶習(xí)慣的查詢依然是個(gè)問題。而搜索引擎日志本身就包含了大量構(gòu)造完整的查詢,并且從中可以挖掘出查詢間的各種聯(lián)系,因此近幾年的查詢推薦主要采用基于日志的方法。根據(jù)所用的查詢屬性,基于日志的方法主要分為三類：基于查詢內(nèi)容的方法[7-8]、基于點(diǎn)擊 URL的方法[5-6]、基于Session的方法[3-4,13]?；诓樵儍?nèi)容的方法利用查詢間的文本相似度計(jì)算查詢相關(guān)度,查詢文本可以包括查詢所對應(yīng)用戶點(diǎn)擊結(jié)果的錨文本、摘要等信息?；邳c(diǎn)擊URL的方法利用兩查詢上相同或相似的點(diǎn)擊URL作為特征計(jì)算兩查詢間的相關(guān)度?；赟ession的方法根據(jù)兩查詢在同一搜索過程(Session)中共現(xiàn)的次數(shù)計(jì)算相關(guān)度。基于這些特征,多類算法被用于進(jìn)行查詢推薦,包括傳統(tǒng)的IR模型[5,8]、數(shù)據(jù)挖掘方法[3]、機(jī)器學(xué)習(xí)[13]、基于查詢—點(diǎn)擊URL二分圖的圖算法[6]、以及基于規(guī)則的方法[4]。

結(jié)構(gòu)相似度利用對象所處的圖或樹的結(jié)構(gòu)計(jì)算對象間相似度。近年來,結(jié)構(gòu)相似度已經(jīng)成為數(shù)據(jù)庫模式匹配、協(xié)同過濾、鏈接分析等領(lǐng)域的熱門研究方向。Antonellis等人[14]提出一種基于改進(jìn)Sim-Rank的廣告搜索方法。不同于上述算法實(shí)驗(yàn)中用到的網(wǎng)頁、論文引用等數(shù)據(jù),查詢間沒有顯式的鏈接關(guān)系。因此,本文首先引入查詢關(guān)系圖表示不同查詢間的聯(lián)系,進(jìn)而構(gòu)造適合查詢關(guān)系圖的結(jié)構(gòu)相似度算法WSim RAnk衡量查詢間的相關(guān)度。

3 查詢關(guān)系圖

查詢關(guān)系圖 Gq=是一個(gè)有向圖,Vq={v}是節(jié)點(diǎn)集合,每個(gè)節(jié)點(diǎn)v表示一個(gè)查詢,Eq={e}是邊集合,邊e=(v→w)表示查詢v到查詢w的某種關(guān)聯(lián)。邊權(quán)重 ω(v→w)的大小反映了查詢v到查詢w之間聯(lián)系的強(qiáng)弱;若邊e不存在,ω(v→w)=0。查詢關(guān)系圖中的邊可以根據(jù)查詢內(nèi)容、點(diǎn)擊 URL、Session等查詢屬性構(gòu)造。實(shí)驗(yàn)表明：基于查詢內(nèi)容建立起的查詢圖連通分支很多,而分支內(nèi)的子圖又往往完全連通,幾乎沒有可挖掘的間接聯(lián)系;點(diǎn)擊URL在檢索結(jié)果不理想時(shí)很稀疏,因而對需要推薦的困難查詢反而難以處理。本文采用基于Session的方法,從Session中挖掘查詢之間的關(guān)系。

Session具有兩個(gè)基本性質(zhì)：(1)同一Session中的查詢具有很高的相似性。Session是同一用戶為了某一特定搜索意圖進(jìn)行的一系列活動(dòng),因而同一個(gè)Session中的查詢都是語義相關(guān)的。(2)Session中的前后查詢具有“跳轉(zhuǎn)性”。不同用戶重構(gòu)的查詢是不同的,所以這種前后查詢跳轉(zhuǎn)不是確定的,而是帶有某種概率。跳轉(zhuǎn)到某個(gè)查詢的概率越大,說明這個(gè)查詢相對于前一個(gè)查詢越相關(guān)、越完善。具體地,查詢關(guān)系圖基于以下步驟構(gòu)造：

(1)對搜索引擎查詢?nèi)罩具M(jìn)行Session劃分,本文采用文獻(xiàn)[15]中的方法。

(2)對于Session中出現(xiàn)的每一個(gè)查詢,在查詢關(guān)系圖中增加一個(gè)節(jié)點(diǎn)。

(3)對于Session中的每個(gè)查詢,建立從它到隨后兩個(gè)重構(gòu)查詢的有向邊,邊的初始權(quán)重設(shè)置為1,若邊已建立,權(quán)重加1。

(4)對每個(gè)節(jié)點(diǎn)的入邊權(quán)重歸一化,即對節(jié)點(diǎn)v,使得 ∑iω(i→v)=1。邊權(quán)重 ω(v →w)可以看作查詢v到查詢w的跳轉(zhuǎn)概率。

4 基于SimRank的查詢相似度

建立查詢關(guān)系圖后,原先孤立地計(jì)算兩個(gè)查詢之間的相似度的問題被轉(zhuǎn)化成在查詢關(guān)系圖上計(jì)算節(jié)點(diǎn)之間的相似度問題。Sim Rank[9]利用圖的結(jié)構(gòu)信息計(jì)算對象間的相似度：一個(gè)節(jié)點(diǎn)與自身的相似度最高,相同或相似節(jié)點(diǎn)的鄰居節(jié)點(diǎn)也相似。也就是說,節(jié)點(diǎn)間的相似性可以沿著邊傳遞到他們的鄰居間。從另一方面看,節(jié)點(diǎn)的相似性依賴于鄰居節(jié)點(diǎn)的相似性,節(jié)點(diǎn)間的相似度可以由鄰居節(jié)點(diǎn)間相似度遞歸計(jì)算。

對查詢關(guān)系圖Gq=中任一節(jié)點(diǎn)(查詢)v,I(v)表示v的入邊鄰居節(jié)點(diǎn)集合,Ii(v)表示第i個(gè)入邊相鄰節(jié)點(diǎn)。令Sim(a,b)表示節(jié)點(diǎn)a和節(jié)點(diǎn)b的Sim Rank相似度。根據(jù)前面所述的Sim-Rank 思想,則 ：如果 a=b,Sim(a,b)=1;否則

這里C(0

讓我們來看一個(gè)例子,有兩個(gè)Session,從查詢“in formation retrieval”開始 ,分別結(jié)束于“CCIR”和“SIGIR”：

Session1：information retrieval→信息檢索→CCIR Session2 ：inform ation retrieval→IR→SIGIR

“信息檢索”和“IR”都有共同的入邊相鄰節(jié)點(diǎn)“information retrieval” ,因此 ,根據(jù) SimRank,“信息檢索”和“IR”相關(guān)。同樣,因?yàn)椤癈CIR”和“SIGIR”的入邊相鄰節(jié)點(diǎn)“信息檢索”和“IR”相似,因此“CCIR”和“SIGIR”也相似。盡管“信息檢索”和“IR”、“CCIR”和“SIGIR”沒有出現(xiàn)在同一Session中,SimRank仍然可以挖掘出它們間的相似性。實(shí)質(zhì)上,“CCIR”和“SIGIR”相似是因?yàn)樗鼈兛梢怨餐厮莸酵徊樵儭癷nformation retrieval”。這種相遇的路線越多,兩個(gè)查詢就越相關(guān),其SimRank相似度也就越高。

5 加權(quán)SimRank查詢推薦

SimRank可以挖掘出查詢間的深層聯(lián)系,并綜合考慮了一對查詢間可以相遇的所有對稱路徑,這種計(jì)算相似度的策略適用于查詢這種屬性信息稀缺的對象。但是,Sim Rank算法在計(jì)算查詢相似度上仍然存在兩個(gè)問題：

?Sim Rank算法僅僅利用了圖的結(jié)構(gòu)信息,沒有考慮邊權(quán)重信息。邊權(quán)重體現(xiàn)了查詢間的跳轉(zhuǎn)概率,權(quán)重高的查詢間關(guān)系更緊密,應(yīng)該在推薦中給予更多考慮,而原始的SimRank算法卻一視同仁,這影響了計(jì)算結(jié)果的準(zhǔn)確性。

?Sim Rank中兩節(jié)點(diǎn)是否相鄰對它們間相似度沒有影響。在上個(gè)例子中“information retrieval”和“信息檢索”的相似度計(jì)算為0。這是不合理的,查詢關(guān)系圖中具有直接關(guān)聯(lián)的查詢才會(huì)直接相連,這些查詢往往非常相關(guān)。

因此需要改進(jìn)SimRank算法以適合查詢關(guān)系圖上的查詢相似度計(jì)算。首先,將權(quán)重信息融入公式;其次,修改公式保證相鄰查詢肯定相似。這個(gè)改造后的算法被稱做加權(quán)SimRank(Weighted Sim-Rank,簡稱WSim Rank),公式如下：

與原始Sim Rank公式不同,WSim Rank保證查詢關(guān)系圖上有連邊的節(jié)點(diǎn)對的相似度大于等于邊權(quán)重。這樣所有具有直接連邊的查詢的相似度都不為0了?？梢缘蠼?WSimRank值,首先初始化如下：

利用數(shù)學(xué)歸納法,可以證明WSim Rank算法具有與Sim Rank算法相同的性質(zhì)：唯一性、對稱性和有界性。同樣,WSim Rank的迭代算法具有收斂性。容易看出,在迭代過程中WSim k(a,b)單調(diào)非減,由于邊權(quán)重事先做了歸一化,則

所以WSim′k(a,b)≤1,因而 WSim k(a,b)≤1。根據(jù)單調(diào)有界收斂準(zhǔn)則,迭代過程一定收斂。

5.1 性能優(yōu)化

在Sim Rank和WSim Rank算法的每次迭代過程中,要暫存每次迭代的中間結(jié)果,因此空間復(fù)雜度為O(n2),其中n為圖中節(jié)點(diǎn)個(gè)數(shù)。Sim Rank和WSim Rank算法的時(shí)間復(fù)雜度是O(kn4),其中k表示迭代次數(shù)。即便采用稀疏矩陣存儲(chǔ)查詢關(guān)系圖,時(shí)間復(fù)雜度仍為O(kn2d2)(d表示節(jié)點(diǎn)的平均入度)。當(dāng)n的規(guī)模很大時(shí),會(huì)遭遇到性能瓶頸。真實(shí)搜索引擎中的查詢總數(shù)往往至少數(shù)以百萬計(jì),我們必須對WSim Rank算法進(jìn)行優(yōu)化。

關(guān)于Sim Rank優(yōu)化,前人提出一些方法,文獻(xiàn)[9]提出限制傳播半徑來減少計(jì)算量;文獻(xiàn)[16]采用蒙特卡洛方法得到近似解;文獻(xiàn)[14]通過變化公式來優(yōu)化計(jì)算。但是這些方法都沒有結(jié)合計(jì)算機(jī)實(shí)現(xiàn)給出具體的實(shí)用性優(yōu)化算法,本文把Sim Rank和WSim Rank的迭代計(jì)算過程轉(zhuǎn)化成一個(gè)層次狀態(tài)圖中路徑和的計(jì)算問題并給出優(yōu)化方法。結(jié)合Sim Rank和WSim Rank,可以發(fā)現(xiàn)查詢關(guān)系圖中的每個(gè)節(jié)點(diǎn)在不同時(shí)刻具有四種不同的狀態(tài)：

?起始節(jié)點(diǎn)：計(jì)算中作為某個(gè)相似度節(jié)點(diǎn)對(a,b)的左節(jié)點(diǎn)a,

?起始鄰居：計(jì)算中作為某個(gè)相似度節(jié)點(diǎn)對(a,b)左節(jié)點(diǎn)a的入邊節(jié)點(diǎn)I(a),

?終止鄰居：計(jì)算中作為某個(gè)相似度節(jié)點(diǎn)對(a,b)右節(jié)點(diǎn)b的入邊節(jié)點(diǎn)I(b),

?終止節(jié)點(diǎn)：計(jì)算中作為某個(gè)相似度節(jié)點(diǎn)對(a,b)的右節(jié)點(diǎn)b。

把查詢圖的每個(gè)節(jié)點(diǎn)分裂成四個(gè)狀態(tài),建立起所有狀態(tài)間的聯(lián)系,就構(gòu)成了一個(gè)圖,稱之WSim-Rank計(jì)算圖(簡稱計(jì)算圖,圖1)。計(jì)算圖實(shí)際上反應(yīng)了WSim Rank的計(jì)算過程。

圖1 計(jì)算圖

對于計(jì)算圖中某一起始節(jié)點(diǎn)a,定義其可達(dá)節(jié)點(diǎn)b為：節(jié)點(diǎn)b屬于終止?fàn)顟B(tài)集合且a到b之間存在至少一條路徑。只有起始節(jié)點(diǎn)才具有可達(dá)節(jié)點(diǎn),只有終止節(jié)點(diǎn)才能作為可達(dá)節(jié)點(diǎn)。起始節(jié)點(diǎn)與其任一可達(dá)節(jié)點(diǎn)構(gòu)成一可達(dá)節(jié)點(diǎn)對。非可達(dá)節(jié)點(diǎn)對間的相似度肯定為0,因此不需要計(jì)算。定義可達(dá)路徑為可達(dá)節(jié)點(diǎn)對間的一條路徑,其權(quán)值為路徑中各邊權(quán)重的乘積。由此,WSim(a,b)的計(jì)算過程轉(zhuǎn)化為：遍歷計(jì)算圖中節(jié)點(diǎn)a到節(jié)點(diǎn)b間的解有可達(dá)路徑,并將這些可達(dá)路徑權(quán)值累加的過程。

5.1.1 計(jì)算優(yōu)化

從計(jì)算圖中可以發(fā)現(xiàn)許多可達(dá)路徑之間共享子路徑。采用動(dòng)態(tài)規(guī)劃思想,將子路徑的權(quán)值作為中間計(jì)算結(jié)果保存起來,下次計(jì)算直接利用,能大大減少重復(fù)計(jì)算。下面舉例說明,在圖1中黑色邊表示從a到e和a到 f的四條路徑：a→b→d→e,a→c→d→e,a→b→d→f,a→c→d→f,這四條路徑的權(quán)值在計(jì)算路徑和S(a,e)和S(a,f)時(shí)都必須計(jì)算出來,由于每條路徑做2次乘法計(jì)算,那么一共需要8次乘法計(jì)算和4次累加計(jì)算。而S(a,e)=S(a,d)×ω(e,d),S(a,f)=S(a,d)×ω(f,d),它們都需要使用子路徑權(quán)值S(a,d),計(jì)算S(a,d)需要2次乘法和1次加法計(jì)算,保存S(a,d)之后,一共僅需4次乘法和1次加法。

5.1.2 剪枝優(yōu)化

如果能減少計(jì)算圖中邊的數(shù)量,那么將降低復(fù)雜度。剪枝的策略有兩種,一種是靜態(tài)剪枝,在計(jì)算前修剪,主要是修剪原始查詢關(guān)系圖,例如我們可以去除查詢關(guān)系圖中權(quán)重很低的邊,或者去除像“百度”、“Google”這樣連邊多卻不能體現(xiàn)搜索意圖的查詢;另一種是動(dòng)態(tài)剪枝,在運(yùn)行時(shí)修剪,主要是刪去計(jì)算過程中相似度較低的節(jié)點(diǎn)對。在每次計(jì)算中預(yù)先刪掉一些值較小且不會(huì)對最終結(jié)果有較大影響的中間結(jié)果,就能在接下來的計(jì)算中減少相當(dāng)多的計(jì)算量。本文使用簡單的啟發(fā)函數(shù)f：

5.1.3 復(fù)雜度分析

設(shè)計(jì)算圖中起始鄰居狀態(tài)節(jié)點(diǎn)的平均出邊數(shù)為l,查詢關(guān)系圖中每個(gè)節(jié)點(diǎn)的平均出邊數(shù)為d。使用壓縮矩陣存儲(chǔ)查詢關(guān)系圖需O(n+nd)空間,存儲(chǔ)結(jié)果圖需要O(n+nl)空間,另外需要O(n)存儲(chǔ)中間結(jié)果,空間復(fù)雜度為O(n+n(d+l))。計(jì)算所有節(jié)點(diǎn)的子路徑中間結(jié)果需要O(n)×O(d)×O(l)=O(nd l)時(shí)間,利用中間結(jié)果計(jì)算相似度需要O(d)+O(n)=O(nd),于是迭代一次的時(shí)間復(fù)雜度是O(nd l)+O(nd)=O(nd l),迭代k遍的時(shí)間復(fù)雜度是O(k)×O(nd l)=O(knd l)。由于查詢關(guān)系圖非常稀疏,d<

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

6.1 實(shí)驗(yàn)數(shù)據(jù)和評(píng)價(jià)方法

為了驗(yàn)證加權(quán)Sim Rank,我們在真實(shí)搜索引擎查詢?nèi)罩旧祥_展了一系列實(shí)驗(yàn)。實(shí)驗(yàn)數(shù)據(jù)基于新浪愛問搜索2006年9月到11月初的部分查詢?nèi)罩?這部分日志包含近兩億條記錄。我們從中抽取了93 862個(gè)不同的高頻查詢構(gòu)建查詢關(guān)系圖,本文選取了五種不同的方法進(jìn)行對比：1)關(guān)聯(lián)規(guī)則挖掘[3],用ARMSim表示;2)把所有查詢用其對應(yīng)點(diǎn)擊URL的向量表示,以向量余弦夾角計(jì)算查詢間相似度,以URLSim表示;3)Huang和Jian發(fā)表的查詢推薦方法[4],也是基于Session的方法,記做Jian-Sim;4)原始 Sim Rank[9],以 Na?ve Sim Rank 表示;5)加權(quán)Sim Rank,記做 Weighted Sim Rank。

在93 862個(gè)查詢中,我們隨機(jī)抽取了200個(gè)查詢作為測試查詢。并采用Poo ling的方法構(gòu)建了評(píng)價(jià)集。具體而言,對每種方法返回的排名最前的10個(gè)推薦結(jié)果,使用文獻(xiàn)[13]中的標(biāo)準(zhǔn)進(jìn)行手工標(biāo)注,這樣共標(biāo)注了約8 000個(gè)查詢對作為評(píng)價(jià)集;每一對查詢相關(guān)與否,均有3名學(xué)生進(jìn)行標(biāo)注,標(biāo)注過程中,可以參考查詢在搜索引擎中的返回結(jié)果;對于少量不一致的標(biāo)注結(jié)果,標(biāo)注者根據(jù)評(píng)價(jià)標(biāo)準(zhǔn)協(xié)商后最終給出一致結(jié)果?；谠u(píng)價(jià)集,定義召回率(Reca ll)和準(zhǔn)確率(Precision)：

此外,還有平均結(jié)果數(shù)(所有測試查詢的平均返回結(jié)果數(shù))、覆蓋率(能給出推薦結(jié)果的查詢在所有測試查詢中的比例)。

6.2 實(shí)驗(yàn)結(jié)果和分析

圖2和表1給出了各種方法的各項(xiàng)評(píng)價(jià)指標(biāo)得分,其中,ARMSim[3]中關(guān)聯(lián)規(guī)則參數(shù) support和con fidence分別為2和 10%,Sim Rank和Weighted Sim Rank的衰減系數(shù)C均設(shè)為0.8,各自迭代計(jì)算5次,其他方法參數(shù)按照它們論文中的值進(jìn)行設(shè)置,實(shí)驗(yàn)表明以上參數(shù)設(shè)置為在此語料集上的最佳參數(shù)設(shè)置方式。

圖2 各種方法查詢推薦結(jié)果的precision-recall曲線和NDCG曲線對比結(jié)果

表1 各種方法查詢推薦結(jié)果評(píng)價(jià)值

從P-R曲線圖上看到,Weighted SimRank的曲線大大超過其余所有方法的,取得最好效果。關(guān)聯(lián)規(guī)則挖掘和原始Sim Rank性能相似,但是關(guān)聯(lián)規(guī)則曲線在Recall<0.3時(shí)更陡,隨著召回率增加下降明顯,說明簡單地統(tǒng)計(jì)頻率信息會(huì)帶來很多雜質(zhì)。URLSim和JianSim效果最差,這主要是由于召回率偏低,結(jié)果稀疏導(dǎo)致的。Weighted Sim Rank算法之所以在召回率和正確率均有不同程度的提高,是引入圖結(jié)構(gòu)表示查詢關(guān)系,并通過迭代計(jì)算挖掘出了更多的隱含關(guān)系,這在一定程度上保證了高召回率。

MAP和P@N的結(jié)果與P-R曲線稍有不同,關(guān)聯(lián)規(guī)則挖掘在各項(xiàng)指標(biāo)上都優(yōu)于原始SimRank,這揭示了原始 SimRank算法的一個(gè)很重要的缺陷——沒有結(jié)合權(quán)重信息。而Weighted Sim Rank在各類指標(biāo)上都遠(yuǎn)遠(yuǎn)優(yōu)于其他方法。這里平均結(jié)果個(gè)數(shù)統(tǒng)計(jì)的是整個(gè)測試查詢集上所有查詢的平均返回結(jié)果數(shù)目(對Sim Rank和Wsim Rank,相似度小于0.1的結(jié)果不予推薦),可以看到非迭代的方法都遭遇到稀疏性問題,前10個(gè)僅能返回不到6個(gè)結(jié)果,而SimRank類的方法均接近10個(gè)。在測試集上的覆蓋率指標(biāo)顯示W(wǎng)eighted Sim Rank所有查詢均有正確返回結(jié)果,關(guān)聯(lián)規(guī)則挖掘次之。而基于URL的方法覆蓋率和召回率都很低,這可能與實(shí)驗(yàn)語料有關(guān)。

6.2 加權(quán)SimRank的參數(shù)和性能

衰減系數(shù)C是Weighted Sim Rank中唯一的參數(shù),實(shí)驗(yàn)結(jié)果表明C的選取對實(shí)驗(yàn)結(jié)果影響不大。當(dāng)C在0.5到0.9間變化時(shí),M AP的變化區(qū)間為(0.88,0.89),其他各項(xiàng)指標(biāo)的變化幅度也小于5%。性能優(yōu)化對于Weighted Sim Rank是必須的,在擁有一塊2.4GH z CPU及8G DDR內(nèi)存的機(jī)器環(huán)境下,包含93 862個(gè)節(jié)點(diǎn)的查詢關(guān)系圖可在1小時(shí)內(nèi)完成5次迭代,實(shí)驗(yàn)表明迭代5次的結(jié)果已經(jīng)非常接近最優(yōu)值,而不加優(yōu)化的運(yùn)行時(shí)間估計(jì)需要數(shù)月。

6.3 例子

為了更好地理解加權(quán)SimRank給出的查詢推薦結(jié)果。這里給出一個(gè)具體的例子①各搜索引擎相關(guān)搜索的返回結(jié)果均為2009年5月間取得的結(jié)果。,在日志中有一個(gè)查詢詞是“訊騰 qq”,因?yàn)椤坝嶒v”沒有與“QQ”相關(guān)的含義,很明顯用戶的本意是想搜索“騰訊qq”,但是輸入錯(cuò)誤變成“訊騰qq”。我們發(fā)現(xiàn)目前主流的搜索引擎的推薦結(jié)果竟然都包含“訊騰”二字,而我們的結(jié)果給出了用戶真正想要的推薦“騰訊qq”。這也說明我們的方法能挖掘出查詢間的語義聯(lián)系。

7 總結(jié)

查詢推薦是現(xiàn)代檢索系統(tǒng)的重要組成部分,是搜索引擎與用戶交互的途徑之一。本文給出一種將查詢關(guān)系用圖模型表示的方法,并引入結(jié)構(gòu)相似度算法——Sim Rank——來計(jì)算圖中查詢之間的相似度,這樣能綜合利用傳統(tǒng)信息檢索算法和查詢間全局信息進(jìn)行推薦。同時(shí),改進(jìn)Sim Rank變成加權(quán)Sim Rank?；谡鎸?shí)搜索引擎日志的實(shí)驗(yàn)驗(yàn)證了該算法的有效性：加權(quán)Sim Rank在查詢推薦各項(xiàng)指標(biāo)上比其他方法都有很大提高。

原始加權(quán)Sim Rank的時(shí)間復(fù)雜度和空間復(fù)雜度很高,在實(shí)際系統(tǒng)中難以實(shí)用,本文把計(jì)算過程轉(zhuǎn)化成一個(gè)層次圖——計(jì)算圖,然后從不同角度對算法進(jìn)行優(yōu)化：1)采用圖搜索方法而不是窮舉減少計(jì)算量;2)采用動(dòng)態(tài)規(guī)劃思想保存中間結(jié)果減少重復(fù)計(jì)算;3)采用剪枝策略刪去相似度低的節(jié)點(diǎn)對。將空間和時(shí)間復(fù)雜度從O(n2)和O(kn4)降低到了O(n log(n))和O(n log2(n)),大大提高了算法的效率和實(shí)用性。

表2 關(guān)于查詢“訊騰 qq”的推薦示例

[1] Y.Li,S.Zhang,B.Wang,J.Li.Characteristics o f Chinese W eb Searching：A Large-Scale Analysis o f Chinese Query Logs[J].Journalof Computational Information Systems.Bethel：Binary Information Press,2008,4(3)：1127-1136.

[2] M.Strohmaier,M.K r?ll,C.K?rner.Intentional Query Suggestion：Making User Goals More Explicit During Search[C]//WSCD'09：Proceedings o f the 2009 w orkshop on Web Search Click Data.New York,NY,USA：ACM,2009：68-74.

[3] B.M.Fonseca,Golghe,P.B.,Moura,E.S.d.,and Ziviani,N.Discovering Search Engine Related Queries Using Association Rules[J].Journal of W eb Engineering,2004,2(4)：215-227.

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

[5] R.Baeza-Yates,Hurtado,C.,and Mendoza,M.Query Recommendation Using Query Logs in Search Engines[C]//In：Book Query Recommendation Using Query Logs in Search Engines,Springer Berlin/H eidelberg,2004：588-596.

[6] H.Cao,D.Jiang,J.Pei,Q.He,Z.Liao,E.Chen and H.Li,Context-aware query suggestion bym ining click-through and session data[C]//Proceeding of the 14th ACM SIGKDD international conference on Know ledge discovery and data m ining.Las Vegas,Nevada,New York,NY,USA：ACM,2008：875-883.

[7] M.Saham i and T.D.Heilman,A web-based kernel function formeasuring the similarity o f short text snippets[C]//Proceedings of the 15th international conference on World WideW eb.New York,NY,USA：ACM,2006：377-386.

[8] J.-R.Wen,J.-Y.Nie and H.-J.ZH ang,Query clustering using user logs[J].ACM Trans.Inf.Syst.,2002,20：59-81.

[9] G.Jeh and J.Widom,Sim Rank：ameasure of structural-context sim ilarity[C]//Proceedings o f the eighth ACM SIGKDD international conference on Know ledge discovery and data m ining.New York,NY,USA：ACM,2002：538-543.

[10] J.Xu,and W.B.Croft,Query expansion using local and global document analysis[C]//Proceedings of the 19th annual international ACM SIGIR conference on Research and development in in formation retrieval.New York,NY,USA：ACM,1996：4-11.

[11] S.Deerw ester,et al.Indexing by latent semantic analysis[J].JASIS,January 1999,41(6)：391-407.

[12] Y.Chen,G.-R.Xue,and Y.Yu,Advertising keyw ord suggestion based on concep t hierarchy[C]//Proceedings of the international conference on W eb search and w eb datam ining.New York,NY,USA：ACM,2008：251-260.

[13] R.Jones et al.,Generating query substitutions[C]//Proceedings of the 15th international con ference on W orld WideWeb.New York,NY,USA：ACM,2006：387-396.

[14] I.Antonellis,H.G.Mo lina and C.C.Chang,Simrank++：query rew riting through link ana lysis of the click graph[C]//Proc.VLDB Endow.2008：408-421.

[15] 張磊,李亞楠,王斌,等.網(wǎng)頁搜索引擎查詢?nèi)罩镜膕ession劃分研究[J].中文信息學(xué)報(bào),2009,23(2)：54-61.

[16] D.Fogaras and B.Racz,Scaling link-based sim ilarity search[C]//Proceedings of the 14th international conference on World Wide Web.New York,NY,USA：ACM,2005：641-650.

[17] D.Lizorkin,P.Velikhov,M.Grinev and D.Turdakov,A ccuracy estimate and optim ization techniques for Sim Rank computation[C]//Proc.V LDB Endow.,2008：422-433.