基于聚類和用戶點擊的在線多樣化排序算法*

馬千里 林古立

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

互聯網信息檢索系統(tǒng)的一個核心問題是如何對檢索得到的文檔根據用戶提交的查詢進行排序以滿足用戶的需求［1］.因此，排序算法的研究一直是信息檢索領域的一個重要研究方向.現有的大多數互聯網信息檢索系統(tǒng)，無論是采用基于文檔內容的相關度計算［2］，還是基于鏈接分析［3］的排序方法，抑或是近幾年興起的排序學習方法［4］，它們在對結果文檔進行排序時通常都是根據概率排序原則［5］按照估計出來的文檔與查詢的相關度從大到小進行排序，以期望獲得最好的檢索性能.然而，隨著信息檢索研究的不斷深入，越來越多的研究結果［6-8］表明，現有的基于概率排序原則的排序方法無法滿足用戶的多樣化需求.

信息檢索排序中的多樣化需求主要源于兩方面［9］:一是用戶查詢的不確定性，例如查詢詞有多義性，存在多種解釋，搜索引擎無法確定用戶的需求;二是用戶查詢所涉及的信息面可能較廣，包含多個方面的內容，單個文檔無法滿足用戶的需求.例如，查詢詞“Java”，既可以表示一種編程語言、也可以表示印尼的爪哇島，這就是查詢意圖的不確定性;而即使查詢詞是“Java編程”，那也包含了很多方面的內容，例如與Java編程相關的書、源代碼或者軟件等.在這些情況下，信息檢索系統(tǒng)在對檢索結果進行排序時，必須挖掘用戶查詢所蘊含的各種潛在意圖，在結果列表靠前的位置盡可能地提供滿足用戶各種需求的檢索結果.

現有的多樣化排序方法［10-12］大多采用啟發(fā)式的方法，把多樣化排序問題看作是文檔的查詢相關度與文檔間的相似性的線性組合優(yōu)化問題進行求解.這類相對靜態(tài)的方法是從系統(tǒng)的角度對用戶意圖進行挖掘，無法真正把握用戶的查詢意圖.Radlinski等［13］提出了一種基于在線學習的多樣化排序算法RBA，通過與用戶進行交互，從用戶的點擊中捕捉用戶的查詢意圖，從而調整結果文檔的排序，提高用戶的滿意度.但RBA算法需要將待排序的所有文檔逐個進行選擇，當結果文檔數量較大時，RBA算法的收斂速度很慢，早期難以滿意用戶的多樣化需求.針對這個問題，文中在RBA算法的基礎上，利用文檔之間的相似性，提出了一個基于聚類和用戶點擊的在線多樣化排序算法CRBA(Cluster-Based Ranked Bandit Algorithm).該算法首先對候選網頁文檔進行主題聚類，接著選擇類別中的文檔形成排序列表，然后根據用戶的反饋進行在線學習，動態(tài)調整類別的排列順序以及類別內文檔的選擇，以更好地滿足用戶的多樣化需求.

1 CRBA算法描述

CRBA算法的目標是解決這樣的問題:給定一個查詢及其候選文檔集合D={d1，d2，…，dn}，算法通過不斷的學習得到一個包含k個文檔的多樣化排序列表，以滿足各種不同的用戶需求.假設存在一個用戶群體，其中每一個用戶ui都覺得D中的一個文檔子集Ai是與其查詢意圖相關的，而剩下的其它文檔則是不相關的.直觀來看，抱有不同意圖的用戶所對應的相關文檔子集是不同的，而抱有類似意圖的用戶所對應的相關文檔子集則應該是類似的.在時刻t，CRBA算法將提供給用戶ut一個排好序的k個文檔列表Bt={b1(t)，b2(t)，…，bk(t)}.假設用戶將會從頭至尾按順序瀏覽這k個文檔，在瀏覽過程中，用戶如果發(fā)現相關的文檔，就會進行點擊，然后停止瀏覽行為.這里假設用戶點擊相關文檔的概率為1，即只要是相關文檔就會進行點擊.CRBA算法的目標是最大化從時刻1開始的整個過程的用戶點擊率，較高的點擊率表示較多的用戶點擊了CRBA算法提供的文檔列表，從文檔列表中找到了相關的文檔，也就是說，CRBA算法滿足了較多用戶的需求.

CRBA算法建立在多臂賭博機(MAB)［14］算法的基礎上.MAB是一類決策優(yōu)化問題:一個擁有K個臂的投幣機器，賭博者在某一時刻從這K個臂中選擇一個臂進行拉動來獲得回報，這個回報可能是正值、零或者負值，一次拉動獲得一個回報.在某一時刻，賭博者只能操作一個臂，目的是使賭博者的回報總和最大.將該問題對應到多樣化排序中，可以把候選文檔看成臂，用戶的點擊作為回報.RBA算法正是基于這一點，通過構建多個MAB實例實現多樣化排序.與RBA算法不同的是，筆者提出的CRBA算法采用了兩層MAB實例結構，一層用于選擇文檔類別，另一層用于選擇類別內的文檔.這樣做的好處是可以先利用文檔聚類將待排序文檔進行一個簡單的劃分，在此基礎上利用用戶點擊捕捉不同類別文檔滿足用戶的需求程度，相比RBA算法，CRBA算法可以大大減少不必要的用戶交互，從而提高早期的用戶滿意度.

CRBA算法包含4個輸入參數:查詢詞q、候選文檔集合D、用戶瀏覽范圍k(即前k個文檔)和時刻s.CRBA算法的輸出為到時刻s為止的用戶點擊率r，即有多大比例的用戶對排序結果進行了點擊.CRBA算法中的h是指MAB實例的一個臂，p是指該MAB實例獲得的回報，MAB實例會根據回報調整各個臂的權重，以更新下一次選擇各個臂的概率.CRBA算法的具體描述如下.

輸入參數:q，D，k，s

輸出參數:r

對D進行主題聚類得到m類，記為C1，C2，…，Cm

初始化 MAB1(m)，MAB2(m)，…，MABk(m);對于每一個類別Cj(j∈［1，m］)，初始化對應的

fort=1 tosdo

fori=1 tokdo∥選擇前k個文檔供用戶瀏覽c'i(t)=select-arm(MABi)∥選擇類別

ifc'i(t)∈{c1(t)，c2(t)，…，ci－1(t)}ci(t)=任意類別?{c1(t)，c2(t)，…，ci－1(t)}

else

ci(t)=c'i(t)

end if

ifb'i(t)∈{b1(t)，b2(t)，…，bi－1(t)}

bi(t)=任意文檔?{b1(t)，b2(t)，…，bi－1(t)}

else

bi(t)=b'i(t)

end if

end for

展示{b1(t)，b2(t)，…，bk(t)}給用戶，記錄用戶點擊

應該說，“首都餐飲業(yè)品質提升工作”是北京市餐飲業(yè)以習近平總書記關于食品安全系列講話精神為指導，全面實施國家市場監(jiān)管總局提出的《餐飲服務食品安全操作規(guī)范》的自律表現，是繼北京餐飲業(yè)實現“明廚亮灶”、“陽光餐飲”后的一次全面提升，是為迎接2022年冬奧會打造餐飲業(yè)的首都標準、北京品牌，使北京餐飲業(yè)成為彰顯首都文化魅力、良好生態(tài)環(huán)境、和諧文明社會、安定富裕生活的載體，成為體現首都城市內在品質的亮麗名片，在全國餐飲行業(yè)中做出了表率。下一步，中國烹飪協會將在北京市市場監(jiān)督管理局的指導下，繼續(xù)深入落實“首都餐飲業(yè)品質提升工作”，力爭取得更大的成效，惠及更多的企業(yè)和消費者。

fori=1 tokdo

if用戶點擊了bi(t)＆＆ci(t) ==c'i(t)＆＆bi(t)==b'i(t)

update(MABi，h=c'i(t)，p=1)

update(MABc'i(t)，h=b'i(t)對應的臂，p=1)

break

end if

end for

end for

CRBA算法主要分為兩個部分:

(1)初始化.對于給定查詢詞q，算法先對其候選文檔集合D進行聚類，獲得聚類結果C1，C2，…，Cm，每個類別包含的文檔集合分別為Dc1，Dc2，…，Dcm.接著，算法初始化多個MAB實例，包括k個用來選擇類別的含有m個臂的MAB實例(用MABi表示)，和m個用來選擇類別中的文檔的MAB實例(用MABcj表示，這m個MAB實例的臂的數量等于對應類別的文檔數).每個MABi都維護著每個類別的一個值，用于選擇類別;而每個MABcj也維護著該類別下面每個文檔的一個值，用于選擇文檔.

(2)交互排序.算法從時刻t=1開始，在每個時刻，都有一位用戶提交查詢詞q，算法則會選擇一個包含k個文檔的排序列表給用戶.然后用戶瀏覽排序列表，根據文檔相關性決定是否進行點擊，算法會根據用戶的點擊對MAB實例進行更新操作，這樣算法就完成了與用戶的一次交互過程.此過程不斷重復直至時刻s.

在整個交互排序的過程中，CRBA算法對文檔的排序分兩個階段進行，每個階段對應一層的MAB實例.首先是選擇文檔的類別，每個排序位置i對應一個選擇出的實例MABi.選擇類別時，從MABi中根據臂的概率隨機選擇一個臂c'i(t)，如果該臂對應的文檔類別尚未在位置i之前被選中過，則選擇該類別作為排序位置i對應的類別ci(t)，否則隨機選擇一個未被選過的類別對應排序位置i.然后是類別內文檔的選擇，從排序位置i對應的類別ci(t)所對應的MAB實例MABci(t)中隨機選擇一個臂b'i(t)，如果該臂對應的文檔尚未在位置i之前被選中過，則選擇該文檔作為排序位置i上的文檔bi(t)，否則隨機選擇一個未被選過的文檔放在排序位置i上.這個過程持續(xù)到選好k個文檔為止.

而當CRBA算法把k個文檔呈現給用戶之后，用戶按順序瀏覽k個文檔直到他看到相關的文檔并進行點擊，至此整個查詢過程完成;如果沒有看到任何相關文檔，用戶將不進行點擊，查詢過程結束.接著，CRBA算法會根據用戶點擊對MAB實例的參數進行更新.假設用戶點擊了排序位置為i的文檔bi(t)，如果該排序位置的類別是由MABi選擇的，即ci(t)==c'i(t)，且該文檔是由用MABci(t)選定的文檔，即bi(t)==b'i(t)，那么該文檔對應的MABci(t)中的臂獲得回報1，MABi中的臂ci(t)獲得回報1，其它臂獲得回報0.根據所獲得的回報，函數update更新各個MAB實例中臂的權重，以便進行下一次排序.

在CRBA算法中，MAB算法是關鍵所在，它必須在保持用戶點擊率的同時，嘗試選擇其它類別或者文檔供用戶選擇，以了解用戶對更多類別或文檔的喜好，據此調整類別和文檔的排序，以得到更高的點擊率.此外，由于采用了多個MAB實例，排序位置i上的文檔的回報會受到該位置之前的文檔的影響，故其回報不服從一定的概率分布，因此，采用文獻［15］提出的Exp3算法作為MAB算法實例.

2 實驗與分析

2.1 模擬數據分析

模擬數據集由用戶模型和文檔構建，用戶模型采用CRP［16］進行生成，把用戶和子主題(用戶潛在意圖)對應起來，即哪些用戶與給定主題的哪些子主題相關.與文獻［13］一樣，實驗時選擇生成20個用戶，設置CRP的參數θ為3，這樣生成的數據集的平均子主題數為6.5，每個子主題上的用戶數呈冪級遞減.對于每一個主題，當用戶和子主題的對應關系生成后，再生成一定數量的文檔，并隨機把文檔按比例分配到各個子主題中.文檔的分配與子主題所包含的用戶數相關，用戶數越多，文檔就越多.最后，設置每個用戶與他所相關的子主題下的所有文檔都相關，而與其它文檔則不相關.模擬數據集總共包含100個主題.

排序算法的結果通過用戶點擊率進行評價，即從時刻1開始到時刻t，有多大比例的用戶點擊了排序列表.在模擬數據的實驗中，用戶查詢次數設置為300000次.一般來說，現實中查詢次數在50000以上的就算常用查詢詞了，設置300000次是為了考察算法的性能變化趨勢.實驗時，在每一個時刻(每一次查詢)，隨機抽取用戶對排序結果進行查看和點擊，并記錄用戶點擊率，最后記錄算法排序結果在100個主題上的平均用戶點擊率.

在第1個實驗中，與文獻［13］一樣，設置生成的給定主題對應的候選文檔數為50.在這個實驗中，CRBA算法所采用的聚類是最優(yōu)聚類，即所有聚類結果完全與子主題分配一致，其目的是想通過實驗驗證CRBA算法在聚類效果最優(yōu)情況下的表現.實驗結果如圖1所示.從圖1中可以看到，CRBA和RBA算法的平均用戶點擊率都遠遠高于下界OPT(OPT表示最優(yōu)排序結果所取得的點擊率)，而且兩個算法的性能都隨著用戶查詢次數的增加而逐漸提高.但CRBA算法的結果很快就逐漸地逼近最優(yōu)排序的結果了，而RBA算法的收斂速度明顯比基于最優(yōu)聚類的CRBA算法要慢得多，在時刻300 000的平均用戶點擊率還遠沒有達到CRBA算法在時刻50000的平均用戶點擊率.由此可知，在獲得最優(yōu)聚類結果的條件下，CRBA算法可以迅速地逼近最優(yōu)排序的結果，相比RBA算法具有明顯的優(yōu)勢.

圖1 算法RBA和CRBA在文檔數量為50的虛擬數據集上的平均用戶點擊率Fig.1 Average user click rates of algorithms RBA and CRBA on a simulated dataset with 50 documents

第2個實驗考察數據集文檔數對兩種算法的影響.為此，實驗中構建了4個文檔數不同的數據集.4個數據集采用相同的主題和用戶模型，但文檔數分別是20、30、50和100.也就是說，4個數據集中的主題及其子主題，還有子主題與用戶的相關關系都是一樣的，不同的只是候選文檔的數量和分配到各個子主題的數量.實驗中CRBA算法依舊采用最優(yōu)的聚類結果.實驗結果如圖2所示，CRBA算法在4個數據集上的表現幾乎完全一致，說明在類別沒有變化的情況下，類別內部文檔數量的大小對CRBA算法沒有影響.而RBA算法則明顯受到文檔數量的影響，當文檔數逐漸增大時，RBA算法的收斂速度也逐漸變慢.從這一點看，CRBA算法比RBA算法更具有實用價值.因為在互聯網搜索的現實情況中，候選文檔集的數量往往很大，類別個數往往比文檔數小得多，此時，基于主題聚類的CRBA算法就能夠減少不必要的用戶交互次數，快速地獲得讓用戶滿意的排序結果.

圖2 算法RBA和CRBA在文檔數量分別為20、30、50和100的虛擬數據集上的平均用戶點擊率Fig.2 Average user click rates of algorithms RBA and CRBA on simulated datasets with 20，30，50 and 100 documents

2.2 公開數據集實驗分析

為進一步考察CRBA算法在實際應用中的有效性，在一個公開的數據集AMBIENT(AMBIgous ENTries)上進行實驗，并采用現有的聚類算法對文檔進行聚類.

AMBIENT 數據集(http://credo.fub.it/ambient)是一個用于子主題檢索評價的公開數據集.它總共包含44個主題，每個主題包含一個子主題集合和100個排好序的文檔.主題和子主題是從Wikipedia(http://en.wikipedia.org/wiki/Wikipedia:Links_to_%28disambiguation%29_pages)上獲取的，而結果文檔是以主題名作為查詢詞從Yahoo!搜索引擎獲取的，并且根據Wikipedia上列出的每個主題對應的子主題信息，人工進行子主題相關性的標記.每個文檔由搜索結果的URL、標題和頁面文摘組成.更多的關于該數據集的信息可以參考文獻［17］.

在用戶模型方面，仍然采用20個用戶，且采用基于文檔占比的用戶模型，即與子主題相關的用戶數跟該子主題所包含的文檔數相關，文檔數多的用戶就多.

實驗中采用k-means聚類算法作為CRBA算法中的聚類算法，聚類目標個數設置為10.為了驗證CRBA算法的有效性，除了與RBA算法進行比較之外，還加上了經典的多樣化排序算法MMR［10］，文檔的查詢相關度用BM25進行計算.

算法的性能依然采用平均用戶點擊率進行評估，是在數據集所有44個主題上的用戶點擊率的平均值.實驗結果如圖3所示.由圖3可見:MMR算法的平均用戶點擊率隨著用戶查詢次數的增多，基本呈現穩(wěn)定的狀態(tài)，主要是由于其排序結果是不變的;而兩種在線排序算法RBA和CRBA的性能都隨著用戶查詢次數的增多而提高.這說明，隨著跟用戶的不斷交互，在線算法可以逐漸獲得對用戶意圖更為準確的估計，從而提高了用戶的滿意度.而CRBA算法的收斂速度明顯比RBA算法要快，因此可以大大縮短與用戶的交互次數，從而在早期也能較好地滿足用戶的需求.

圖3 3種算法在AMBIENT數據集上的平均用戶點擊率Fig.3 Average user click rates of three algorithms on AMBIENT dataset

3 結語

文中提出了一種基于聚類和用戶點擊的在線多樣化排序算法CRBA，它既可以利用主題聚類的優(yōu)點，根據主題對候選文檔集合進行簡單的劃分，從而大大加快收斂算法的收斂速度，又能發(fā)揮在線排序算法的優(yōu)點，利用用戶點擊反饋，獲得對用戶意圖更為準確和完整的估計，為用戶提供多樣化的排序結果.實驗結果表明，CRBA算法比其它在線排序算法收斂更快，且更能適應現實搜索環(huán)境中文檔數量大的特點.

［1］Baeza-Yates R，Ribeiro-Neto B.現代信息檢索［M］.王知津，賈福新，鄭紅軍，等，譯.北京:機械工業(yè)出版社，2005.

［2］馬暉男，吳江寧，潘東華.一種修正的向量空間模型在信息檢索中的應用［J］.哈爾濱工業(yè)大學學報，2008，40(4):666-669.Ma Hui-nan，Wu Jiang-ning，Pan Dong-hua.Application of a modified vector space model in textual information retrieval systems［J］.Journal of Harbin Institute of Technology，2008，40(4):666-669.

［3］Page L，Brin S，Motwani R，et al.The pagerank citation ranking:bring order to the Web［R］.Stanford:Stanford InfoLab，1998.

［4］孫鶴立，馮博琴，黃健斌，等.序關系優(yōu)化的多超平面排序學習模型［J］.模式識別與人工智能，2010，23(3):327-334.Sun He-li，Feng Bo-qin，Huang Jian-bin，et al.Ranking model of optimized multiple hyperplanes using order relations［J］.Pattern Recognition and Artificial Intelligence，2010，23(3):327-334.

［5］Robertson S E.The probability ranking principle in IR［J］.Journal of Documentation，1977，33(4):294-304.

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

［7］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 IR Research.New York:ACM，2010:87-99.

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

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

［10］Carbonell J，Goldstein J.The use of MMR，diversitybased 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.

［11］Zhai C X，Cohen 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.

［12］林古立，彭宏，馬千里，等.一種基于關鍵詞的網頁搜索結果多樣化方法［J］.華南理工大學學報:自然科學版，2010，39(5):102-107.Lin Gu-li，Peng Hong，Ma Qian-li，et al.A keywordbased method for diversification of Web search results［J］.Journal of South China University of Technology:Natural Science Edition，2010，39(5):102-107.

［13］Radlinski F，Kleinberg R，Joachims T.Learning diverse rankings with multi-armed bandits［C］∥Proceedings of the 25th International Conference on Machine Learning.New York:ACM，2008:784-791.

［14］Cesa-Bianchi N，LugosiG.Prediction，learning，and games［M］.New York:Cambridge University Press，2006.

［15］Auer P，Cesa-Bianchi N，Freund Y，et al.The nonstochastic multiarmed bandit problem［J］.SIAM Journal on Computing，2002，32(1):48-77.

［16］Durrett R.Probability models for DNA sequence evolution［M］.2nd ed.New York:Springer，2008.

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