轉自：http://www.infoq.com/cn/articles/cyw-evaluate-seachengine-result-quality

前言

搜索質量評估是搜索技術研究的基礎性工作，也是核心工作之一。評價（Metrics）在搜索技術研發中扮演著重要角色，以至于任何一種新方法與他們的評價方式是融為一體的。

Cranfield評價體系

A Cranfield-like approach這個名稱來源于英國Cranfield University，因為在二十世紀五十年代該大學首先提出了這樣一套評價系統：由查詢樣例集、正確答案集、評測指標構成的完整評測方案，并從此確立了“評價”在信息檢索研究中的核心地位。

Cranfield評價體系由三個環節組成：

1. 抽取代表性的查詢詞，組成一個規模適當的集合
2. 針對查詢樣例集合，從檢索系統的語料庫中尋找對應的結果，進行標注（通常人工進行）
3. 將查詢詞和帶有標注信息的語料庫輸入檢索系統，對系統反饋的檢索結果，使用預定義好的評價計算公式，用數值化的方法來評價檢索系統結果和標注的理想結果的接近程度

查詢詞集合的選取

Cranfield評價系統在各大搜索引擎公司內有廣泛的應用。具體應用時，首先需要解決的問題是構造一個測試用查詢詞集合。

按照Andrei Broder（曾在AltaVista/IBM/Yahoo任職）的研究，查詢詞可分為3類：尋址類查詢（Navigational）、信息類查詢(Informational)、事務類查詢(Transactional)。對應的比例分別為

Navigational ： 12.3%  Informational ： 62.0%  Transactional ： 25.7% 

為了使得評估符合線上實際情況，通常查詢詞集合也會按比例進行選取。通常從線上用戶的Query Log文件中自動抽取。

另外查詢集合的構造時，除了上述查詢類型外，還可以考慮Query的頻次，對熱門query（高頻查詢）、長尾query（中低頻）分別占特定的比例。

另外，在抽取Query時，往往Query的長短也是一個待考慮的因素。因為短query（單term的查詢）和長Query（多Term的查詢）排序算法往往會有一些不同。

構成查詢集合后，使用這些查詢詞，在不同系統（例如對比百度和Google）或不同技術間（新舊兩套Ranking算法的環境）進行搜索，并對結果進行評分，以決定優劣。

附圖：對同一Query：“社會保險法”，各大搜索引擎的結果示意圖。下面具體談談評分的方法。

Precision-recall（準確率-召回率方法）

計算方法

信息檢索領域最廣為人知的評價指標為Precision-Recall（準確率-召回率）方法。該方法從提出至今已經歷半個世紀，至今在很多搜索引擎公司的效果評估中使用。

顧名思義，這個方法由準確率和召回率這兩個相互關聯的統計量構成：召回率（Recall）衡量一個查詢搜索到所有相關文檔的能力，而準確率（Precision）衡量搜索系統排除不相關文檔的能力。（通俗的解釋一下：準確率就是算一算你查詢得到的結果中有多少是靠譜的；而召回率表示所有靠譜的結果中，有多少被你給找回來了）。這兩項是評價搜索效果的最基礎指標，其具體的計算方法如下。

Precision-recall方法假定對一個給定的查詢，對應一個被檢索的文檔集合和一個不相關的文檔集合。這里相關性被假設為二元的，用數學形式化方法來描述，則是：

A表示相關文檔集合

A表示不相關集合

B表示被檢索到的文檔集合

B表示未被檢索到的文檔集合

則單次查詢的準確率和召回率可以用下述公式來表達：

（運算符∩ 表示兩個集合的交集。|x|符號表示集合x中的元素數量）

從上面的定義不難看出，召回率和準確率的取值范圍均在[0,1]之間。那么不難想象，如果這個系統找回的相關越多，那么召回率越高，如果相關結果全部都給召回了，那么recall此時就等于1.0。

Precision-Recall曲線

召回率和準確率分別反映了檢索系統的兩個最重要的側面，而這兩個側面又相互制約。因為大規模數據集合中，如果期望檢索到更多相關的文檔，必然需要“放寬”檢索標準，因此會導致一些不相關結果混進來，從而使準確率受到影響。類似的，期望提高準確率，將不相關文檔盡量去除時，務必要執行更“嚴格”的檢索策略，這樣也會使一些相關的文檔被排除在外，使召回率下降。

所以為了更清晰的描述兩者間的關系，通常我們將Precison-Recall用曲線的方式繪制出來，可以簡稱為P-R diagram。常見的形式如下圖所示。（通常曲線是一個逐步向下的走勢，即隨著Recall的提高，Precision逐步降低）

P-R的其它形態

一些特定搜索應用，會更關注搜索結果中錯誤的結果。例如，搜索引擎的反作弊系統（Anti-Spam System）會更關注檢索結果中混入了多少條作弊結果。學術界把這些錯誤結果稱作假陽性（False Positive）結果，對這些應用，通常選擇用虛報率（Fallout）來統計：

Fallout和Presion本質是完全相同的。只是分別從正反兩方面來計算。實際上是P-R的一個變種。

再回到上圖，Presion-Recall是一個曲線，用來比較兩個方法的效果往往不夠直觀，能不能對兩者進行綜合，直接反映到一個數值上呢？為此IR學術界提出了F值度量（F -Measure）的方法。F-Measure通過Presion和Recall的調和平均數來計算，公式為：

其中參數λε(0,1)調節系統對Precision和Recall的平衡程度。（通常取λ=0.5，此時 ）

這里使用調和平均數而不是通常的幾何平均或算術平均，原因是調和平均數強調較小數值的重要性，能敏感的反映小數字的變化，因此更適合用來反映檢索效果。

使用F Measure的好處是只需要一個單一的數字就可以總結系統的檢索效果，便于比較不同搜索系統的整體效果。

P@N方法

點擊因素

傳統的Precision-Recall并不完全適用對搜索引擎的評估，原因是搜索引擎用戶的點擊方式有其特殊性，包括：

A 60-65%的查詢點擊了名列搜索結果前10條的網頁；  B 20-25%的人會考慮點擊名列11到20的網頁；  C 僅有3-4%的會點擊名列搜索結果中列第21到第30名的網頁 

也就是說，絕大部分用戶是不愿意翻頁去看搜索引擎給出的后面的結果。

而即使在搜索結果的首頁（通常列出的是前10條結果），用戶的點擊行為也很有意思，我們通過下面的Google點擊熱圖（Heat Map）來觀察（這個熱圖在二維搜索結果頁上通過光譜來形象的表達不同位置用戶的點擊熱度。顏色約靠近紅色表示點擊強度越高）：

從圖中可以看出，搜索結果的前3條吸引了大量的點擊，屬于熱度最高的部分。也就是說，對搜蘇引擎來說，最前的幾條結果是最關鍵的，決定了用戶的滿意程度。

康乃爾大學的研究人員通過eye tracking實驗獲得了更為精確的Google搜索結果的用戶行為分析圖。從這張圖中可以看出，第一條結果獲得了56.38%的搜索流量，第二條和第三條結果的排名依次降低，但遠低于排名第一的結果。前三條結果的點擊比例大約為11:3:2 。而前三條結果的總點擊幾乎分流了搜索流量的80%。

另外的一些有趣的結論是，點擊量并不是按照順序依次遞減的。排名第七位獲得的點擊是最少的，原因可能在于用戶在瀏覽過程中下拉頁面到底部，這時候就只顯示最后三位排名網站，第七名便容易被忽略。而首屏最后一個結果獲得的注意力（2.55）是大于倒數第二位的(1.45)，原因是用戶在翻頁前，對最后一條結果印象相對較深。搜索結果頁面第二頁排名第一的網頁（即總排名11位的結果）所獲得的點擊只有首頁排名第十網站的40%，與首頁的第一條結果相比，更是只有其1/60至1/100的點擊量。

因此在量化評估搜索引擎的效果時，往往需要根據以上搜索用戶的行為特點，進行針對性的設計。

P@N的計算方法

P@N本身是Precision@N的簡稱，指的是對特定的查詢，考慮位置因素，檢測前N條結果的準確率。例如對單次搜索的結果中前5篇，如果有4篇為相關文檔，則P@5 = 4/5 = 0.8 。

測試通常會使用一個查詢集合（按照前文所述方法構造），包含若干條不同的查詢詞，在實際使用P@N進行評估時，通常使用所有查詢的P@N數據，計算算術平均值，用來評判該系統的整體搜索結果質量。

N的選取

對用戶來說，通常只關注搜索結果最前若干條結果，因此通常搜索引擎的效果評估只關注前5、或者前3結果，所以我們常用的N取值為P@3或P@5等。

對一些特定類型的查詢應用，如尋址類的查詢（Navigational Search），由于目標結果極為明確，因此在評估時，會選擇N=1（即使用P@1）。舉個例子來說，搜索“新浪網”、或“新浪首頁”，如果首條結果不是 新浪網（url：www.sina.com.cn），則直接判該次查詢精度不滿足需求，即P@1=0

MRR

上述的P@N方法，易于計算和理解。但細心的讀者一定會發現問題，就是在前N結果中，排序第1位和第N位的結果，對準確率的影響是一樣的。但實際情況是，搜索引擎的評價是和排序位置極為相關的。即排第一的結果錯誤，和第10位的結果錯誤，其嚴重程度有天壤之別。因此在評價系統中，需要引入位置這個因素。

MRR是平均排序倒數（Mean Reciprocal Rank）的簡稱，MRR方法主要用于尋址類檢索（Navigational Search）或問答類檢索（Question Answering），這些檢索方法只需要一個相關文檔，對召回率不敏感，而是更關注搜索引擎檢索到的相關文檔是否排在結果列表的前面。MRR方法首先計算每一個查詢的第一個相關文檔位置的倒數，然后將所有倒數值求平均。例如一個包含三個查詢詞的測試集，前5結果分別為：

查詢一結果：1.AN 2.AR 3.AN 4.AN 5.AR  查詢二結果：1.AN 2.AR 3.AR 4.AR 5.AN  查詢三結果：1.AR 2.AN 3.AN 4.AN 5.AR  

其中AN表示不相關結果，AR表示相關結果。那么第一個查詢的排序倒數（Reciprocal Rank）RR₁ = 1/2=0.5 ；第二個結果RR₂ = 1/2 = 0.5 ； 注意倒數的值不變，即使查詢二獲得的相關結果更多。同理，RR₃= 1/1 = 1。 對于這個測試集合，最終MRR=（RR₁+RR₂+RR₃）/ 3 = 0.67

然而對大部分檢索應用來說，只有一條結果無法滿足需求，對這種情況，需要更合適的方法來計算效果，其中最常用的是下述MAP方法。

MAP

MAP方法是Mean Average Precison，即平均準確率法的簡稱。其定義是求每個相關文檔檢索出后的準確率的平均值（即Average Precision）的算術平均值（Mean）。這里對準確率求了兩次平均，因此稱為Mean Average Precision。（注：沒叫Average Average Precision一是因為難聽，二是因為無法區分兩次平均的意義）

MAP 是反映系統在全部相關文檔上性能的單值指標。系統檢索出來的相關文檔越靠前(rank 越高)，MAP就應該越高。如果系統沒有返回相關文檔，則準確率默認為0。

例如：假設有兩個主題：

主題1有4個相關網頁，主題2有5個相關網頁。

某系統對于主題1檢索出4個相關網頁，其rank分別為1, 2, 4, 7；

對于主題2檢索出3個相關網頁，其rank分別為1,3,5。

對于主題1，平均準確率MAP計算公式為：

(1/1+2/2+3/4+4/7)/4=0.83。 

對于主題2，平均準確率MAP計算公式為：

(1/1+2/3+3/5+0+0)/5=0.45。 

則MAP= (0.83+0.45)/2=0.64。”

DCG方法

DCG是英文Discounted cumulative gain的簡稱，中文可翻譯為“折扣增益值”。DCG方法的基本思想是：

1. 每條結果的相關性分等級來衡量
2. 考慮結果所在的位置，位置越靠前的則重要程度越高
3. 等級高（即好結果）的結果位置越靠前則值應該越高，否則給予懲罰

我們首先來看第一條：相關性分級。這里比計算Precision時簡單統計“準確”或“不準確”要更為精細。我們可以將結果細分為多個等級。比如常用的3級：Good（好）、Fair（一般）、Bad（差）。對應的分值rel為：Good:3 / Fair:2 / Bad:1 。一些更為細致的評估使用5級分類法：Very Good（明顯好）、Good（好）、Fair（一般）、Bad（差）、Very Bad（明顯差），可以將對應分值rel設置為：Very Good:2 / Good:1 / Fair:0 / Bad:-1 / Very Bad: -2

評判結果的標準可以根據具體的應用來確定，Very Good通常是指結果的主題完全相關，并且網頁內容豐富、質量很高。而具體到每條

DCG的計算公式并不唯一，理論上只要求對數折扣因子的平滑性。我個人認為下面的DCG公式更合理，強調了相關性，第1、2條結果的折扣系數也更合理：

此時DCG前4個位置上結果的折扣因子（Discount factor）數值為：

取以2為底的log值也來自于經驗公式，并不存在理論上的依據。實際上，Log的基數可以根據平滑的需求進行修改，當加大數值時（例如使用log₅ 代替log₂），折扣因子降低更為迅速，此時強調了前面結果的權重。

為了便于不同類型的query結果之間橫向比較，以DCG為基礎，一些評價系統還對DCG進行了歸一，這些方法統稱為nDCG（即 normalize DCG）。最常用的計算方法是通過除以每一個查詢的理想值iDCG（ideal DCG）來進行歸一，公式為：

求nDCG需要標定出理想情況的iDCG，實際操作的時候是異常困難的，因為每個人對“最好的結果”理解往往各不相同，從海量數據里選出最優結果是很困難的任務，但是比較兩組結果哪個更好通常更容易，所以實踐應用中，通常選擇結果對比的方法進行評估。

怎樣實現自動化的評估？

以上所介紹的搜索引擎量化評估指標，在Cranfield評估框架（Cranfield Evaluation Framework）中被廣泛使用。業界知名的TREC（文本信息檢索會議）就一直基于此類方法組織信息檢索評測和技術交流。除了TREC外，一些針對不同應用設計的Cranfield評測論壇也在進行進行（如 NTCIR、IREX等）。

但Cranfield評估框架存在的問題是查詢樣例集合的標注上。利用手工標注答案的方式進行網絡信息檢索的評價是一個既耗費人力、又耗費時間的過程，只有少數大公司能夠使用。并且由于搜索引擎算法改進、運營維護的需要，檢索效果評價反饋的時間需要盡量縮短，因此自動化的評測方法對提高評估效率十分重要。最常用的自動評估方法是A/B testing系統。

A/B Testing

A/B Testing系統

A/B testing系統在用戶搜索時，由系統來自動決定用戶的分組號（Bucket id），通過自動抽取流量導入不同分支，使得相應分組的用戶看到的是不同產品版本（或不同搜索引擎）提供的結果。用戶在不同版本產品下的行為將被記錄下來，這些行為數據通過數據分析形成一系列指標，而通過這些指標的比較，最后就形成了各版本之間孰優孰劣的結論。

在指標計算時，又可細分為兩種方法，一種是基于專家評分的方法；一種是基于點擊統計的方法。

專家評分的方法通常由搜索核心技術研發和產品人員來進行，根據預先設定的標準對A、B兩套環境的結果給予評分，獲取每個Query的結果對比，并根據nDCG等方法計算整體質量。

點擊評分有更高的自動化程度，這里使用了一個假設：同樣的排序位置，點擊數量多的結果質量優于點擊數量少的結果。（即A2表示A測試環境第2條結果，如果A2 > B2，則表示A2質量更好）。通俗的說，相信群眾（因為群眾的眼睛是雪亮的）。在這個假設前提下，我們可以將A/B環境前N條結果的點擊率自動映射為評分，通過統計大量的Query點擊結果，可以獲得可靠的評分對比。

Interleaving Testing

另外2003年由Thorsten Joachims 等人提出的Interleaving testing方法也被廣泛使用。該方法設計了一個元搜索引擎，用戶輸入查詢詞后，將查詢詞在幾個著名搜索引擎中的查詢結果隨機混合反饋給用戶，并收集隨后用戶的結果點擊行為信息．根據用戶不同的點擊傾向性，就可以判斷搜索引擎返回結果的優劣，

如下圖所示，將算法A和B的結果交叉放置，并分流量進行測試，記錄用戶點擊信息。根據點擊分布來判斷A和B環境的優劣。

Interleaving Testing評估方法

Joachims同時證明了Interleaving Testing評價方法與傳統Cranfield評價方法的結果具有較高的相關性。由于記錄用戶選擇檢索結果的行為是一個不耗費人力的過程，因此可以便捷的實現自動化的搜索效果評估。

總結

沒有評估就沒有進步——對搜索效果的量化評測，目的是準確的找出現有搜索系統的不足（沒有哪個搜索系統是完美的），進而一步一個腳印對算法、系統進行改進。本文為大家總結了常用的評價框架和評價指標。這些技術像一把把尺子，度量著搜索技術每一次前進的距離。

感謝張凱峰對 本文的審校。

給InfoQ中文站投稿或者參與內容翻譯工作，請郵件至editors@cn.infoq.com。也歡迎大家加入到InfoQ中文站用戶討論組中與我們的編輯和其他讀者 朋友交流。