1、引言
1.1研究背景
搜索引擎已經成為了人們獲取信息的必不可少的工具。根據CNNIC發布的2011年年度報告,截至2011年底,中國網民規模已經達到了5.13億人,其中搜索引擎的使用率達到了79.4%,在互聯網應用中排名第二。與此同時,網絡資源也在迅速膨脹,如何準確理解用戶的檢索需求并快速而有效的幫助用戶找到信息目標仍然是搜索引擎面臨的挑戰,而搜索性能的評價也就受到越來越多的重視。
目前,作為一種主流發展方向,基于用戶行為分析的方法已經開始被應用到搜索引擎查詢性能的評價上。然而,目前已有的搜索引擎性能評價的研究還只是主要集中于查詢頻度比較高的查詢詞上,對于長尾查詢來說,缺少大量的用戶檢索行為的數據,因此簡單照搬用戶行為分析的方法并不可靠,這也是長尾查詢性能評價的難度所在。
實際上,由于高頻查詢詞隨著時間的變化不大,很多商業搜索引擎通過人工標注的方法對高頻查詢詞進行了優化,或者通過用戶反饋不斷調整高頻查詢的結果排序,在高頻查詢上各個搜索引擎已經做得非常好了。因此,真正影響用戶的體驗很大程度上取決于低頻查詢的搜索性能。我們知道,搜索引擎的查詢的分布遵循冪律分布,而同時其也遵循齊普夫定律。據前人的統計發現,幾乎所有搜索引擎用戶都有長尾查詢的需求。因此,長尾查詢的搜索性能的評價也逐漸被搜索引擎重視起來。
本文工作就是在長尾查詢的評價這一挑戰性問題方面的一個探索和嘗試。我們通過大規模的數據分析,結合內容和用戶行為兩個方面的信息,提出包括來自搜索引擎排序、結果呈現、以及用戶點擊行為等多種類型的、適用于搜索引擎長尾查詢評價的特征,并將它們用于搜索引擎結果的自動評價,取得了令人鼓舞的效果。
1.2相關研究
在19世紀五六十年代,英國的Cranfield工程建立了Cranfield的評價體系,應用于信息檢索等相關的領域。該評價體系的一項重要工作是標注人員需要在語料庫中標注出查詢樣例對應的答案集合。標注人員可以根據需要進行不同等級的標注\\(比如5級標注\\)。
針對搜索引擎的性能評價,人們又提出了用戶滿意度的概念。然而,到目前為止,仍然沒有一個明確的用戶滿意度的定義和標準。一方面,用戶滿意度仍然是基于結果的相關性,使用NDCG等指標進行評價;另一方面,也有研究提出用戶滿意度是一個主觀變量,要綜合考慮檢索系統的各種指標以及用戶個性化的因素來進行衡量,但是在實際的實驗中,仍然是通過對用戶檢索出的結果分別評價來進行最終評判。
然而,由于搜索引擎具有海量數據,同時數據資源還在不斷爆炸式增長,人工標注有著明顯的缺點:耗費時間、人力、財力。鑒于人工標注有著巨大的困難,人們開始研究自動標注以替代人工標注。其中用戶行為分析起到了重要的作用,主要包括用戶查詢需求分析和用戶點擊行為分析。當前一些基于用戶行為分析的方法已經能夠實現搜索引擎的自動 性能評價,例如,Liu等在2007年的 工 作等。但是在這些工作中,均首先排除了長尾查詢,而只關注查詢頻度較高的熱門或常見查詢。
在長尾查詢方面,由于被人們關注的時間不長,在這方面的研究并不多。目前主要相關研究工作體現在三個方面,廣告搜索,查詢推薦,以及長尾查詢的用戶行為分析。在長尾查詢的用戶行為分析方面,Yao等人對長尾查詢及熱門查詢的用戶行為進行了較全面的對比分析,得到了一些有意義的結論,這對本文工作也有一定的啟發。
分析以上的相關工作可以發現,在搜索引擎的高頻查詢性能評價方面,前人已經做了很多工作,相應的評價技術已經較為成熟。而對長尾查詢的研究也只是體現在查詢推薦和廣告搜索的擴展上,在長尾查詢性能評價方面的工作還非常缺乏。長尾查詢與高頻查詢相比,在特征方面存在著很大的差異。例如,長尾查詢的查詢詞長度會更長,長尾查詢返回的結果數目會相對較少,長尾查詢返回的結果列表上的用戶首次點擊位置會更偏下等等。由于存在著這些差異,評價高頻查詢的特征也很難直接用來評價長尾查詢,因此,我們的工作首先要通過對長尾查詢的數據進行分析和調研,找到影響長尾查詢搜索性能的因素,提取出相應的特征,從而建立起對長尾查詢搜索性能的評價體系。
2、數據集
我們在某公司的協助下獲得了2011年3月至2012年3月的部分查詢結果的標注數據,以及相應時間段內的用戶點擊日志。其中每個月有約1 000個查詢詞,每個查詢詞對約15個文檔進行5級相關度人工標注,標注分值為0,2,3,4,5,其中分值越高相關度越高,標注為0的表示不相關。這些查詢既包括了長尾查詢,也包括了中頻查詢和高頻查詢\\(依照慣例,將半年內查詢頻度大于100的分為高頻查詢,查詢頻度在20~100之間的分為中頻查詢,查詢頻度小于20的分為長尾查詢。如果沒有特殊說明,在后續實驗中我們對于不同頻度查詢的定義均按照此標準\\)。同時,我們也抓取了這些查詢詞的搜索引擎結果展示頁面以及搜索引擎排序值結果頁面,作為特征分析的候選集合。
3、搜索引擎長尾查詢評價方法
對于查詢結果的評價主要可以從兩個方面進行,一個是查詢粒度結果滿意度評價,另一個是查詢-文檔對粒度的文檔相關度評價。在目前的搜索引擎性能評價方法,主要是基于查詢-文檔對粒度的相關度評價。長尾查詢在查詢粒度上并沒有特別突出的特征,因此,我們的工作也是從查詢-文檔對的相關度評價展開的,這也是查詢粒度滿意度評價的基礎。
3.1特征提取
3.1.1點擊特征
用戶點擊行為在高頻查詢的評價中是非常有效的。對于長尾查詢,雖然其點擊數據非常稀疏,但是我們還是希望能夠從其中獲取一些有效信息。我們提出使用如表1所示的兩個點擊特征,并統計了兩個點擊特征在不同相關度文檔上的分布情況,給出了點擊特征1\\(Click_Attr1\\)的箱形圖。
從圖1中可以看出,相關度為5的特征值明顯要高于其他相關度的特征值,這應該和相關度為5的文檔的質量明顯非常好有關。從整體趨勢來看,隨著相關度的升高,特征值的均值和中位數都有升高的趨勢。不過相關度為0的文檔的特征值雖然是最低的,但是其與相關度為2和3的文檔差異并不是十分明顯,這說明,我們的特征雖然能體現相關度,但是特征的區分度并不是很大。
3.1.2標紅特征
在以前的工作中發現,搜索引擎結果列表的展示對用戶體驗是有影響的,而標紅部分覆蓋查詢詞的比例有比較明顯的影響。為此,我們從標紅部分這一指標中進行了特征提取。
搜索引擎給出結果的同時,標題和摘要中與查詢詞重疊的部分會標紅。為此,我們提取了體現標紅部分覆蓋比例的三個特征,在提取過程中,這些標紅信息都進行了去重處理。同時,也發現標紅部分的順序也會影響其與原查詢的相關度,因此,我們采用標紅部分與查詢詞的編輯距離相關的特征來體現標紅部分與查詢的匹配度及順序的影響。表2給出了標紅特征的描述,分別統計了每個特征下相關的結果文檔與不相關的結果文檔的相應特征值分布,圖2給出了部分標紅特征的分布圖。
結合考察特征過程中統計得到的分布圖,我們發現,相關的結果文檔和不相關的結果文檔在這6個特征上的分布的差異是比較明顯的。在體現標紅部分覆蓋查詢詞的比例的三個特征中,標題中標紅部分覆蓋查詢詞的比例與標題中最大連續標紅部分覆蓋查詢詞的比例相對來說更加明顯,而后者尤為顯著。同樣,在體現標紅部分與查詢詞的順序關系的三個特征中,也具有類似的結果。因此,我們可以看出,標題中最大連續標紅部分對結果文相關性影響是最大的,其次是標題中的標紅部分,而摘要中的標紅部分影響最弱。
3.1.3排序特征
搜索引擎在返回用戶結果文檔列表時,會根據每個文檔與查詢的相關度對文檔進行排序。這種排序\\(Rank\\)是搜索引擎系統中最核心的一個模塊。
我們獲取了每個結果文檔的一系列重要排序值,包括PageRank值、正文匹配度值、點擊排序值、綜合排序值等。這些排序值體現了該文檔與相應查詢的相關度,從而用于結果的排序。我們將每一個排序值作為一個特征,用這些特征對我們的結果文檔進行相關度分類,也是作為我們相關度評價的一個基線。我們做出了各個排序值在不同相關度上的分布箱線圖,多數排序值的分布隨著相關度的增加有升高的趨勢,但很不明顯。這也從反映出搜索引擎對于長尾查詢結果的排序值計算并不準確,體現了長尾查詢相關度評價的難度。
3.2數據不平衡處理
在我們的數據集中,每一個查詢-文檔對都是帶有五級相關性標注的,而一般在性能評價中通常更關注不相關或非常相關的結果,因此,我們將這一數據集劃分為了三個類別:4和5劃分為非常相關,稱為類別2;2和3劃分為一般相關,稱為類別1;0劃分為不相關,稱為類別0\\(后文實驗中如無特殊說明,均采用這樣的類別劃分\\)。
我們知道,一般的分類方法都會在假設類分布平衡,樣本數據大致相當時,具有較好的精度。而我們的數據中,不同相關度的文檔數目有著非常大的差異,一般相關的數據數目是不相關數據數目的近10倍,如果直接使用這些數據去訓練分類器,必然會存在很大的偏置。為此,我們必須要進行數據平衡的處理。
在處理數據平衡方面,有兩種較為常用的方法。
一種是通過增加正類樣本數目\\(樣本數目少的稱為正類,數目多的稱為負類\\),來彌補與負類的差距以達到數據平衡。增加正類樣本數目的方法是通過隨機抽取正類中的樣本增加到正類中;另一種方法是進行多次抽樣,得到多個訓練集,每一個訓練集包括全部的正類樣本和從負類樣本中隨機抽取的相同數量的樣本加入到訓練集。然后對每一個訓練集分別學習一個分類器,通過投票的方式對測試集進行分類。其中抽樣的訓練集數目與數據不平衡的程度有關。通過在數據集上分別測試兩種數據平衡方法,在樣例數目較少的不相關文檔上的精度有比較明顯的提升,在后續工作中,我們采取了第二種平衡方法。工作中,我們僅對訓練集進行了數據平衡處理,測試集仍保留原來的正負類比例,因此,并不影響我們的方法應用于真實標注的數據。
3.3評價算法的優化
基于上述分析,不難看出對于長尾查詢評價這一挑戰性問題來說,雖然不同的特征都具有一定的區分度,但是每個特征的效果并不足夠理想,而每個特征所能夠識別和區分的查詢也有所差異。因此我們采用集成學習的思路,將每個特征\\(或每組特征組合\\)看作是一個弱分類器,總體上在數據平衡的基礎上進行多分類器的融合。同時,我們也對算法進行了優化,每個分類器的權重并不是一樣的,而是取其在訓練集上的精度作為其權重。表3介紹了優化后評價算法的流程。
4、實驗結果與分析
4.1特征疊加的結果
排序特征的評價效果是我們實驗的基線。在這一部分,我們分別測試了三類特征各自的效果,兩兩組合的效果以及三類特征疊加起來的效果。測試時,對數據進行了歸一化處理,采用了數據平衡方法,多次采樣訓練了50個分類器,以投票結果作為分類結果,使用了決策樹和SVM兩種分類算法,記錄了訓練集和測試集的精度,以及測試集上每一個類別的精度。
這里我們給出了搜索引擎排序特征的結果如表4所示以及三類特征疊加的結果如表5所示,可以看出測試集上的精度有大概2%的提升。雖然我們的精度只有不到60%,但是相對于基線\\(基于搜索引擎排序特征的效果\\)是有提升的,這也是長尾查詢的特征稀疏性明顯,評價難度大的結果。
4.2評價算法的投票方式優化結果
如表6所示,優化后的算法相比之前使用SVM在整體精度上有了2.25%的提升,使用決策樹在整體精度上有了8.22%的提升,類別0的精度也有了明顯的提高,使用決策樹在類別0上的精度有了近50%的提升。其中,提升幅度=\\(優化后精度-優化前精度\\)/優化前精度,在優化之后,決策樹的結果有了明顯的改善,甚至比SVM更好。
4.3二分類效果分析的結果
考慮到在搜索引擎的實際應用中,找出相關度最差的結果文檔是更有意義的。為此,我們也考察了長尾查詢性能評價工作中對挑出最不滿意的查詢的效果。因此對數據集重新分為了兩個類別,即原標注為0的定義為不相關,記為類別0;其他的為相關,記為類別1。對于找出的不相關的文檔,我們更關注其準確率,即找到的不相關文檔確實就是不相關的,盡可能少的把相關的文檔誤分為不相關。
實驗結果表明在不相關文檔這一類別上,我們使用二分類的精度達到了75%,相比之前的18.54%有了很大的提升,也說明我們的算法能夠更加準確的找出不相關的結果文檔。
5、結論
本文旨在研究長尾查詢的評價方法,對長尾查詢結果文檔進行更加有效的相關度評價。由于長尾查詢方面沒有工作基礎,從長尾查詢數據分析入手,提取了三種類別的特征,并進行分析,分析過程中,對不同特征組合進行了測試。針對數據集存在的嚴重不平衡問題,提出了數據平衡方法和基于集成學習的評價算法,并對算法進行了改進,使評價精度有了一定的提升。進行二分類評價,對不相關文檔的評價精度能達到一個較高的水平。
就目前的工作來看,我們的評價方法比搜索引擎自身的評價有了一定的提高,雖然準確率提高的幅度并不大,但是在長尾查詢的特征如此稀疏的情況之下,能達到這樣的效果已屬不易。在接下來的工作中,我們一方面需要繼續通過特征提取或算法優化來提高整體的評價精度,另一方面,對于找出相關度最差的文檔有著更重要的意義。如果能夠在保證準確率的前提下,提高相關度最差的文檔的召回率,那么對于評價長尾查詢的查詢性能和改善搜索引擎的用戶體驗是有很重要意義的。
