一種基于關鍵詞的網頁搜索結果多樣化方法*

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

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

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

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

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

1 多樣化網頁搜索結果

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

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

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

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

1.2 KDM

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

1.2.1 關鍵詞抽取

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

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

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

1.2.2 新穎度值定義

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

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

式中:c(wj，di)表示關鍵詞wj在文檔di中出現的次數.

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

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

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

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

1.2.3 結果重排序

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

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

相應地，文檔的新穎度為

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

2 實驗

2.1 數據集

文中采用一個為子主題檢索設計的公開數據集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)上獲取的;而結果文檔是以主題名作為查詢詞從Yahoo!搜索引擎獲取的，并且根據Wikipedia上列出的每個主題對應的子主題信息，人工進行子主題相關性的標記.每個文檔由搜索結果的URL、標題和文摘組成.更多的關于該數據集的信息可以參考文獻［18］.由于該數據集中結果的相關性只建立在Wikipedia列出的子主題的基礎上，因此結果文檔中所包含的與查詢相關的信息很有可能沒有包括在Wikipedia所列出的范圍內，為了讓實驗更加合理，實驗時去掉了那些不屬于任何一個子主題的文檔.

2.2 評價指標

2.2.1 子主題召回率

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

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

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

2.2.2 加權子主題損失

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

2.3 實驗對比方法

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

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

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

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

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

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

2.4 結果與分析

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

表1 7種方法前10個排序結果的平均子主題召回率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依然取得了最優的效果，即把所有44個主題的性能平均起來，KDM在最小排序位置上的子主題覆蓋率(avg_S-rec@minR)最高，達到了0.693;而在最小排序位置上的子主題加權損失(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中關鍵詞抽取的作用進行分析.

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

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

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

3 結語

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

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

［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.