一種基于關(guān)鍵詞的網(wǎng)頁搜索結(jié)果多樣化方法*

林古立 彭宏 馬千里 韋佳 覃姜維

(華南理工大學(xué)計算機科學(xué)與工程學(xué)院，廣東廣州510006)

現(xiàn)在的互聯(lián)網(wǎng)已經(jīng)成為全球最大的信息庫，用戶要在浩瀚的信息海洋中檢索需要的信息，搜索引擎扮演著非常關(guān)鍵的角色.但現(xiàn)有大多數(shù)搜索引擎在根據(jù)相關(guān)度對結(jié)果文檔進行排序時，都是獨立考慮每個結(jié)果文檔與用戶查詢的相關(guān)性，并沒有考慮文檔與文檔之間的相似性，這樣的排序結(jié)果容易造成冗余［1］.另一方面，用戶使用的查詢詞通常都比較短，搜索引擎很難分辨用戶所表達的查詢意圖.例如，用戶使用查詢詞“蘋果”時，他有可能想查詢一種水果，也可能是想查詢蘋果電腦.只返回與某一種意圖相關(guān)的結(jié)果，無法滿足想搜索其它信息的用戶.另外，用戶往往期望能在搜索引擎所返回的較靠前的結(jié)果文檔(例如第一頁)中獲得他們所需要的信息.在這種情況下，在結(jié)果列表較靠前的位置為用戶提供多樣化的文檔不失為一種提高搜索效率和用戶滿意的方案.

網(wǎng)頁搜索結(jié)果的多樣化問題在近幾年開始得到學(xué)者們的重視［2-3］.Carbonell等［4］提出的 MMR 方法在保持文檔與用戶查詢相關(guān)性的同時，減少了結(jié)果文檔的冗余.Zhai等［5］提出在語言模型的框架下對結(jié)果文檔的多樣性和相關(guān)性進行平衡.Gollapudi等［6］采用公理化的方法對多樣化問題進行描述和分析，提出了3個優(yōu)化目標(biāo)，并把其中2個目標(biāo)還原為離散問題，用2種優(yōu)化算法MMD和MSD進行求解.Zhu等［7］提出的 Grasshopper算法把集中性、多樣性和優(yōu)先性統(tǒng)一在吸收馬爾可夫隨機游走的框架下進行優(yōu)化.Swaminathan等［8］提出的EP方法通過最大化所選擇的結(jié)果文檔子集的聯(lián)合信息覆蓋值進行搜索結(jié)果的多樣化.Yue等［9］提出了一種監(jiān)督式的結(jié)構(gòu)學(xué)習(xí)方法SVMdiv，通過學(xué)習(xí)得到單個詞的重要性，然后選擇最優(yōu)的結(jié)果文檔子集覆蓋最多的重要的詞，讓排序結(jié)果多樣化.Agrawal等［10］試圖在已知查詢和文檔的類別信息的情況下，通過最大化在列表前k個文檔中找到至少一個相關(guān)文檔的可能性來達到多樣化的效果.Santos等［11-12］提出的多樣化框架xQuad，顯式地對查詢詞所蘊含的子查詢進行建模，然后通過估計結(jié)果文檔與子查詢的相關(guān)度進行結(jié)果多樣化.

文中用信息面［13］來表示蘊含在結(jié)果文檔中與用戶查詢相關(guān)的信息集合，把結(jié)果多樣化問題形式化為信息面覆蓋率的最大化問題，提出了一種新的網(wǎng)頁搜索結(jié)果多樣化方法KDM，使重排序后的結(jié)果列表中較靠前的文檔可以包含盡量多的信息面，以達到多樣化的目的.KDM既不需要直接對結(jié)果文檔蘊含的信息面進行建模，也不是直接對文檔進行相似度比較.KDM從結(jié)果文檔中提取出關(guān)鍵詞，利用關(guān)鍵詞在信息面級別的距離，估計文檔的信息面新穎度(以下簡稱新穎度)，并結(jié)合文檔與查詢的相關(guān)度對文檔進行重排序.最后，在一個公開數(shù)據(jù)集AMBIENT上進行實驗以驗證KDM的性能.

1 多樣化網(wǎng)頁搜索結(jié)果

1.1 信息面覆蓋率的最大化問題

為了滿足用戶的各種信息需求，提高搜索效率和用戶滿意度，結(jié)果列表前端的文檔要盡可能包含多個方面的信息.假設(shè)用戶只瀏覽結(jié)果列表中最靠前的k個文檔，文中將多樣化問題形式化為信息面覆蓋率的最大化問題.

給定一個查詢q和與它相關(guān)的結(jié)果文檔集合D={d1，d2，…，dn}，每個文檔 di(i∈［1，n］)都覆蓋了一個與q相關(guān)的信息面集合Fi.多樣化的目標(biāo)就是選擇一個大小為k(k≤n)的文檔子集，滿足:

如果每個文檔所覆蓋的信息面集合Fi是已知的，那么式(1)是一個NP難問題［14］，一個好的解決方案是直接用子集選擇的貪心算法進行計算，并得到一個接近于(1－1/e)OPT的下界，OPT為最優(yōu)值.但當(dāng)這些信息面集合和結(jié)果文檔集包含的總的信息面集合都是未知時，就會給解決多樣化問題帶來困難.

1.2 KDM

為解決多樣化問題，文中提出了一種新的多樣化方法KDM.該方法沒有直接對結(jié)果文檔所蘊含的信息面進行建模，也不是簡單地根據(jù)文檔間的相似度或距離進行多樣化.具體步驟如下:首先，從結(jié)果文檔集中抽取出一批關(guān)鍵詞，這些關(guān)鍵詞可以進行組合，從而表示蘊含的信息面;然后，根據(jù)關(guān)鍵詞的同現(xiàn)性以及關(guān)鍵詞對文檔的描述能力，計算結(jié)果文檔的新穎度值，并對結(jié)果文檔進行重排序，以最大化前面k個文檔的信息面覆蓋率.

1.2.1 關(guān)鍵詞抽取

關(guān)鍵詞抽取是KDM的重要組成部分，期望抽取出的關(guān)鍵詞能夠通過組合來表示結(jié)果文檔所蘊含的各個信息面.KDM的關(guān)鍵詞抽取采用了已成功應(yīng)用到網(wǎng)頁搜索結(jié)果聚類系統(tǒng)的基于后綴數(shù)組的高頻詞及詞組抽取技術(shù)［15］，它不僅能夠抽取在文檔中頻繁出現(xiàn)的單詞，還可以抽取頻繁出現(xiàn)的詞組，這使得聚類結(jié)果更加準(zhǔn)確，聚類標(biāo)簽更有意義.KDM的關(guān)鍵詞抽取分為兩個步驟:

(1)預(yù)處理.預(yù)處理包括對結(jié)果文檔進行詞根還原、停用詞標(biāo)記和文本分割.在這個階段中，文中方法沒有去除停用詞，因為停用詞可能是詞組的一部分.文本分割則是把結(jié)果文檔分割成單詞和句子，這對于詞組抽取來說非常重要，因為如果一個詞組橫跨了不止一個句子，那么這個詞組對用戶來說沒有什么意義［16］.

(2)關(guān)鍵詞抽取.文中采用一種基于變形的后綴數(shù)組的詞組發(fā)現(xiàn)算法［15］，從結(jié)果文檔中抽取出高頻單詞和高頻詞組，先根據(jù)規(guī)則從中選出關(guān)鍵詞，然后去掉那些屬于停用詞的高頻單詞和以停用詞開頭或結(jié)尾的高頻詞組，最后將出現(xiàn)頻率超過關(guān)鍵詞頻率閾值θ的高頻單詞和詞組作為關(guān)鍵詞.與單詞相比，詞組擁有更強的描述能力，因為它們可以保持單詞間的親近度和相對順序，從語義角度上說比單純的單詞集合具有更強的表達能力.而且，相比高頻單詞和詞組，低頻單詞和詞組與用戶查詢的相關(guān)度可能較低，去掉這些低頻單詞和詞組可以降低噪聲的影響，并提高計算效率.

1.2.2 新穎度值定義

由于一個信息面可能包含許多關(guān)鍵詞，如果排序時選擇的結(jié)果文檔所包含的關(guān)鍵詞屬于同一個信息面，那么排序結(jié)果并不能體現(xiàn)多樣性.要提高結(jié)果的多樣性，必須選擇那些包含新穎的信息面的文檔，使得結(jié)果文檔集所包含的信息面的冗余盡可能地少.為了衡量文檔的新穎度，文中根據(jù)關(guān)鍵詞的同現(xiàn)性定義了關(guān)鍵詞在信息面級別中的距離，并根據(jù)該距離和關(guān)鍵詞對文檔的描述能力來定義結(jié)果文檔的新穎度值.

首先，假設(shè)抽取出的關(guān)鍵詞集合W有m個關(guān)鍵詞，對于整數(shù) j，l∈［1，m］，i∈［1，n］，f(wj，di)表示關(guān)鍵詞wj在文檔di中出現(xiàn)的頻率:

式中:c(wj，di)表示關(guān)鍵詞wj在文檔di中出現(xiàn)的次數(shù).

假設(shè)兩個關(guān)鍵詞經(jīng)常以接近的頻率出現(xiàn)在同一文檔中，那么它們很有可能表示同一個信息面.基于這樣的假設(shè)，文中定義兩個關(guān)鍵詞wj和wl在信息面級別中的距離為

對于關(guān)鍵詞wj來說，關(guān)鍵詞wl跟它的距離越遠，意味著wl所具有的新穎度越高.

由于文檔由關(guān)鍵詞組成，因此如果一個文檔中最具代表性的關(guān)鍵詞是新穎的，那么這個文檔很可能就是新穎的.在排序過程中，關(guān)鍵詞wj的新穎度Nw(wj)定義為該關(guān)鍵詞與已排序文檔所覆蓋的關(guān)鍵詞集Wc的距離:

而關(guān)鍵詞對文檔的代表性則用關(guān)鍵詞在該文檔中出現(xiàn)的頻率來刻畫.因此，文檔di的新穎度值定義為

1.2.3 結(jié)果重排序

在定義了文檔新穎度的基礎(chǔ)上，文中提出了一種對結(jié)果文檔進行重排序的貪心算法.在選擇文檔時，該算法結(jié)合了文檔與用戶查詢的相關(guān)度和文檔的新穎度λR(di，q)+(1 －λ)Nd(di).其中，R(di，q)表示文檔di與查詢q的相關(guān)度，文中用BM25［17］進行計算;λ(λ∈［0，1］)是一個平衡參數(shù)，用于調(diào)節(jié)相關(guān)度和新穎度的權(quán)重.

算法開始時，重排序子集合Ds和已覆蓋關(guān)鍵詞集合Wc為空.算法首先選擇具有最大新穎度值的文檔作為第一個文檔.由于一開始還沒有任何關(guān)鍵詞被覆蓋，關(guān)鍵詞的新穎度值無法由式(4)計算得到，因此，關(guān)鍵詞的新穎度根據(jù)該關(guān)鍵詞與其它所有關(guān)鍵詞的距離進行計算，即

相應(yīng)地，文檔的新穎度為

選擇了第一個文檔之后，它所包含的關(guān)鍵詞集Wd*加入到Wc中.接著，計算其它文檔的新穎度值Nd(di)，選擇相關(guān)度和新穎度結(jié)合分值最大的文檔作為第二個文檔，并把該文檔的關(guān)鍵詞加入到Wc中，再計算剩下其它文檔的新穎度值.如此重復(fù)，直到選夠k個文檔或者關(guān)鍵詞全部被覆蓋為止.算法的具體描述如下:

2 實驗

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

文中采用一個為子主題檢索設(shè)計的公開數(shù)據(jù)集AMBIENT(AMBIgous ENTries，http:∥credo.fub.it/ambient)來衡量KDM的多樣化效果.

AMBIENT中有44個主題，每個主題包含一個子主題集合和100個排好序的文檔.主題和子主題是從 Wikipedia(http:∥en.wikipedia.org/wiki/Wikipedia:Links_to_%28dis-ambiguation%29_pages)上獲取的;而結(jié)果文檔是以主題名作為查詢詞從Yahoo!搜索引擎獲取的，并且根據(jù)Wikipedia上列出的每個主題對應(yīng)的子主題信息，人工進行子主題相關(guān)性的標(biāo)記.每個文檔由搜索結(jié)果的URL、標(biāo)題和文摘組成.更多的關(guān)于該數(shù)據(jù)集的信息可以參考文獻［18］.由于該數(shù)據(jù)集中結(jié)果的相關(guān)性只建立在Wikipedia列出的子主題的基礎(chǔ)上，因此結(jié)果文檔中所包含的與查詢相關(guān)的信息很有可能沒有包括在Wikipedia所列出的范圍內(nèi)，為了讓實驗更加合理，實驗時去掉了那些不屬于任何一個子主題的文檔.

2.2 評價指標(biāo)

2.2.1 子主題召回率

子主題召回率是Zhai等［5］定義的用于評價子主題檢索的度量指標(biāo).給定一個主題T和一個排好序的文檔列表{d1，d2，…，dn}，其中 T包含了 nt個子主題 T1，T2，…，Tnt，定義 Ts(di)為與文檔 di相關(guān)的子主題集合.那么在位置k上的子主題召回率定義為結(jié)果列表中前k個文檔的子主題覆蓋率:

子主題召回率越大，說明被覆蓋的子主題越多，當(dāng)所有子主題都被覆蓋時，子主題召回率為1.在實驗中，考察各種方法在位置1到10的子主題召回率，以評價這些方法在搜索結(jié)果第一頁中的多樣化效果.

由于不同的主題包含不同數(shù)量的子主題，固定位置的子主題召回率可能還不能非常準(zhǔn)確地衡量多樣化性能.因此，文中還采用了另外一個子主題召回率的評價指標(biāo).對于每一個主題，都可以找到一個最小的位置，使得在該位置上的子主題召回率為1，稱這個位置為最小排序位置，最小排序位置的子主題召回率可以很好地對多樣化效果進行評價.因此，文中用44個主題在最小排序位置的平均子主題召回率(avg_S-rec@minR)對多樣化方法進行評價.

2.2.2 加權(quán)子主題損失

當(dāng)不同子主題有不同的重要性時，僅僅采用2.2.1節(jié)所介紹的評價方法不能體現(xiàn)重要性的差別的.Yue等［9］認(rèn)為在多樣化任務(wù)中，越主流的子主題越重要，被覆蓋的需求更大，提出了一個加權(quán)子主題損失函數(shù)來衡量多樣化性能.給定一個主題及其結(jié)果文檔集，每個子主題的權(quán)重跟包含該子主題的文檔數(shù)成正比.在位置k的加權(quán)子主題損失定義為前k個文檔所沒有覆蓋的子主題的加權(quán)比率.跟子主題召回率一樣，文中用44個主題在最小排序位置的平均加權(quán)子主題損失(avg_WSL@minR)來評價多樣化方法.

2.3 實驗對比方法

為了考察KDM的多樣化性能，將其與其它6種現(xiàn)有的多樣化方法進行了對比，包括MMR［4］、Grasshopper［7］、MMD［6］、MSD［6］、EP［8］和 SVMdiv［9］.由于所采用的數(shù)據(jù)集中的文檔都至少與主題中的一個子主題相關(guān)，因此可把這些文檔與主題的相關(guān)性看作是相等的.此外，由于數(shù)據(jù)集中最大的子主題數(shù)是15，因此在實驗中只獲取各種方法所產(chǎn)生的結(jié)果列表的前15個文檔.6種方法的實驗參數(shù)如下:

(1)對于MMR，抽取數(shù)據(jù)集中檢索結(jié)果的標(biāo)題和文摘組成結(jié)果文檔，并進行了詞根還原、去停用詞的預(yù)處理.接著把文檔表示成文檔所有單詞的TFIDF向量，然后計算文檔間的余弦相似度.根據(jù)文獻［4］進行了算法的實現(xiàn).

(2)對于Grasshopper，有3個輸入?yún)?shù)，包括表示文檔間相似度的加權(quán)矩陣、表示優(yōu)先性的概率分布和一個權(quán)衡參數(shù)λ(λ∈［0，1］).采用與 MMR相同的預(yù)處理和文檔相似度計算，并構(gòu)建相似度加權(quán)矩陣;給所有文檔相等的優(yōu)先概率.直接采用代碼(http:∥www.cs.wisc.edu/～jerryzhu/pub/grasshopper.m)實現(xiàn)算法.

(3)對于離散算法MMD和MSD，在進行預(yù)處理和文檔表示后，計算文檔間的歐氏距離，并根據(jù)文獻［6］實現(xiàn)這兩種算法.

(4)對于EP方法，先對文檔進行預(yù)處理，然后根據(jù)文獻［8］中的描述實現(xiàn)該方法，取k=15.

(5)對于SVMdiv方法，使用文獻［9］中的數(shù)據(jù)集進行模型的訓(xùn)練.訓(xùn)練時，選定參數(shù)k=15，C=0.1.測試時，把AMBIENT的數(shù)據(jù)轉(zhuǎn)換成該方法所要求的格式，并取k=15.直接采用代碼(http:∥projects.yisongyue.com/svmdiv/)實現(xiàn)算法.

2.4 結(jié)果與分析

表1給出了7種方法的多樣化排序結(jié)果中，前10個排序位置(搜索結(jié)果第一頁)的文檔的平均子主題召回率.總體而言，KDM的多樣化效果要優(yōu)于其它方法.具體來看，在排序位置1和2，7種方法的性能比較接近，SVMdiv在位置1取得了最高的子主題召回率;從位置4開始，KDM和MMR的性能都明顯優(yōu)于其它方法;在位置10時，KDM的平均子主題召回率達到了0.800，比表現(xiàn)最差的Grasshopper方法高將近30%.

表1 7種方法前10個排序結(jié)果的平均子主題召回率Table 1 Average S-recall at rank from 1 to 10 of seven mthods

7種方法的avg_S-rec@minR和avg_WSL@minR如表2所示.從表2中可以看出，KDM依然取得了最優(yōu)的效果，即把所有44個主題的性能平均起來，KDM在最小排序位置上的子主題覆蓋率(avg_S-rec@minR)最高，達到了0.693;而在最小排序位置上的子主題加權(quán)損失(avg_WSL@minR)最小(為0.099).7種方法的avg_S-rec@minR與表1中的avg_S-rec@10一致，從大到小依次為:KDM＞MMR＞MMD＞EP＞MSD＞SVMdiv＞Grasshopper.

表2 7種方法的avg_S-rec@minR和avg_WSL@minRTable 2 avg_S-rec@minR and avg_WSL@minR of seven methods

為進一步分析KDM的有效性，筆者還進行了如下實驗，對KDM中關(guān)鍵詞抽取的作用進行分析.

首先，不進行1.2.1節(jié)中描述的關(guān)鍵詞抽取，而是采用2.3節(jié)中的預(yù)處理方法對文檔進行預(yù)處理，然后把所有單詞作為關(guān)鍵詞，再用KDM的重排序算法進行多樣化，實驗結(jié)果見表3中KDM_ST方法所對應(yīng)的性能.從實驗結(jié)果可以看出，以所有單詞作為關(guān)鍵詞，KDM的多樣化效果比進行關(guān)鍵詞抽取的效果差.這說明1.2.1節(jié)中描述的關(guān)鍵詞抽取有利于提高KDM的多樣化效果.對比KDM_ST和表2中的實驗結(jié)果可以看出，即使以所有單詞作為關(guān)鍵詞，KDM的多樣化性能還是要優(yōu)于除MMR外的其它方法.

另外，由于KDM所抽取的關(guān)鍵詞包括高頻單詞和高頻詞組，為考察它們對KDM多樣化效果的影響，文中分別只使用高頻單詞或高頻詞組作為關(guān)鍵詞進行實驗，結(jié)果見表3中KDM_FT(高頻單詞)和KDM_FP(高頻詞組)方法所對應(yīng)的性能.從結(jié)果可以看出，單獨使用高頻單詞或高頻詞組的效果均不如把它們結(jié)合起來利用的效果好，而只用高頻單詞的效果要明顯優(yōu)于只用高頻詞組的效果.這與在1.2.1節(jié)中的設(shè)想一致，高頻單詞所包含的信息要大于高頻詞組，但僅僅使用高頻單詞是不夠的，高頻詞組所蘊含的更為豐富的語義信息是高頻單詞的重要補充.

表3 采用不同形式的關(guān)鍵詞的KDM性能Table 3 Performance of KDM with different types of keywords

3 結(jié)語

在網(wǎng)頁搜索中，搜索結(jié)果的多樣化逐漸變得重要.文中提出了一種新的網(wǎng)頁搜索結(jié)果多樣化方法，該方法通過從結(jié)果文檔中抽取關(guān)鍵詞，以關(guān)鍵詞為基礎(chǔ)計算文檔的新穎度，并根據(jù)文檔的新穎度和相關(guān)度進行重排序.實驗結(jié)果說明，該方法與現(xiàn)有多樣化方法相比，無論是子主題的召回率還是加權(quán)子主題損失的性能，都要優(yōu)于其它方法.

目前KDM只采用了簡單的詞袋模型對關(guān)鍵詞和文檔以及關(guān)鍵詞和關(guān)鍵詞之間的關(guān)系進行刻畫，還可以用其它模型，如語言模型等.另外，在關(guān)鍵詞的抽取方面，也可以采用其它方法進行抽取.

［1］ Goffman W.On relevance as a measure［J］.Information Storage and Retrieval，1964，2(3):201-203.

［2］ Bennett P N，Carterette B，Chapelle O，et al.Beyond binary relevance:preferences，diversity，and set-level judgments［J］.ACM SIGIR Forum，2008，42(2):53-58.

［3］ Radlinski F，Carterette B，Bennett P N，et al.Redundancy，diversity and interdependent document relevance［J］.ACM SIGIR Forum，2009，43(2):46-52.

［4］ Carbonell J，Goldstein J.The use of mmr，diversity-based reranking for reordering documents and producing summaries［C］∥Proceedings of the 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.New York:ACM，1998:335-336.

［5］ Zhai Chenxiang，Cohen W W，Lafferty J.Beyond independent relevance:methods and evaluation metrics for subtopic retrieval［C］∥Proceedings of the 26th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.New York:ACM，2003:10-17.

［6］ Gollapudi S，Sharma A.An axiomatic approach for result diversification［C］∥Proceedings of the 18th International Conference on World Wide Web.New York:ACM，2009:381-390.

［7］ Zhu Xiaojin，Goldberg A B，Van Gael J，et al.Improving diversity in ranking using absorbing random walks［C］∥Proceedings of Human Language Technologies:the Annual Conference of the North American Chapter of the Association for Computational Linguistics.Rochester:NAACL，2007:97-104.

［8］ Swaminathan A，Mathew C，Kirovski D.Essential pages［R］.Redmond:Microsoft Research，2008.

［9］ Yue Y，Joachims T.Predicting diverse subsets using structural svms［C］∥Proceedings of the 25th International Conference on Machine Learning.New York:ACM，2008:1224-1231.

［10］ Agrawal R，Gollapudi S，Halverson A，et al.Diversifying search results［C］∥Proceedings of the Second ACM International Conference on Web Search and Data Mining.New York:ACM，2009:5-14.

［11］ Santos R L T，Peng J，Macdonald C，et al.Explicit search result diversification through sub-queries［C］∥Proceedings of the 32nd European Conference on Information Retrieval.Berlin/Heidelberg:Springer-Verlag，2010:87-99.

［12］ Santos R L T，Macdonald C，Ounis I.Exploiting query reformulations for Web search result diversification［C］∥Proceedings of the 19th International Conference on World Wide Web.New York:ACM，2010:881-890.

［13］ Carterette B，Chandar P.Probabilistic models of ranking novel documents for faceted topic retrieval［C］∥Proceedings of the 18th ACM Conference on Information and Knowledge Management.New York:ACM，2009:1287-1296.

［14］ Khuller S，Moss A，Naor J.The budgeted maximum coverage problem ［J］.Information Processing Letters，1997，70(1):39-45.

［15］ Osinski S，Weiss D.A concept-driven algorithm for clustering search results ［J］.IEEE Intelligent Systems，2005，20(3):48-54.

［16］ Zhang D，Dong Y.Semantic，hierarchical，online clustering of web search results［C］∥Proceedings of 6th Asia Pacific Web Conference.Berlin/Heidelberg:Springer-Verlag，2004:69-78.

［17］ Robertson S，Jones K S.Simple proven approaches to text retrieval［R］.Cambridge:Computer Laboratory of University of Cambridge，1997.

［18］ Carpineto C，Mizzaro S，Romano G，et al.Mobile information retrieval with search results clustering:prototypes and evaluations［J］.Journal of American Society for Information Science and Technology，2009，60(5):877-895.