轉(zhuǎn)自：http://www.infoq.com/cn/articles/cyw-evaluate-seachengine-result-quality

前言

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

Cranfield評價體系

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

Cranfield評價體系由三個環(huán)節(jié)組成：

1. 抽取代表性的查詢詞，組成一個規(guī)模適當(dāng)?shù)募?/li>
2. 針對查詢樣例集合，從檢索系統(tǒng)的語料庫中尋找對應(yīng)的結(jié)果，進(jìn)行標(biāo)注（通常人工進(jìn)行）
3. 將查詢詞和帶有標(biāo)注信息的語料庫輸入檢索系統(tǒng)，對系統(tǒng)反饋的檢索結(jié)果，使用預(yù)定義好的評價計算公式，用數(shù)值化的方法來評價檢索系統(tǒng)結(jié)果和標(biāo)注的理想結(jié)果的接近程度

查詢詞集合的選取

Cranfield評價系統(tǒng)在各大搜索引擎公司內(nèi)有廣泛的應(yīng)用。具體應(yīng)用時，首先需要解決的問題是構(gòu)造一個測試用查詢詞集合。

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

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

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

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

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

構(gòu)成查詢集合后，使用這些查詢詞，在不同系統(tǒng)（例如對比百度和Google）或不同技術(shù)間（新舊兩套Ranking算法的環(huán)境）進(jìn)行搜索，并對結(jié)果進(jìn)行評分，以決定優(yōu)劣。

附圖：對同一Query：“社會保險法”，各大搜索引擎的結(jié)果示意圖。下面具體談?wù)勗u分的方法。

Precision-recall（準(zhǔn)確率-召回率方法）

計算方法

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

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

Precision-recall方法假定對一個給定的查詢，對應(yīng)一個被檢索的文檔集合和一個不相關(guān)的文檔集合。這里相關(guān)性被假設(shè)為二元的，用數(shù)學(xué)形式化方法來描述，則是：

A表示相關(guān)文檔集合

A表示不相關(guān)集合

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

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

則單次查詢的準(zhǔn)確率和召回率可以用下述公式來表達(dá)：

（運(yùn)算符∩ 表示兩個集合的交集。|x|符號表示集合x中的元素數(shù)量）

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

Precision-Recall曲線

召回率和準(zhǔn)確率分別反映了檢索系統(tǒng)的兩個最重要的側(cè)面，而這兩個側(cè)面又相互制約。因為大規(guī)模數(shù)據(jù)集合中，如果期望檢索到更多相關(guān)的文檔，必然需要“放寬”檢索標(biāo)準(zhǔn)，因此會導(dǎo)致一些不相關(guān)結(jié)果混進(jìn)來，從而使準(zhǔn)確率受到影響。類似的，期望提高準(zhǔn)確率，將不相關(guān)文檔盡量去除時，務(wù)必要執(zhí)行更“嚴(yán)格”的檢索策略，這樣也會使一些相關(guān)的文檔被排除在外，使召回率下降。

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

P-R的其它形態(tài)

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

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

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

其中參數(shù)λε(0,1)調(diào)節(jié)系統(tǒng)對Precision和Recall的平衡程度。（通常取λ=0.5，此時 ）

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

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

P@N方法

點擊因素

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

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

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

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

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

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

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

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

P@N的計算方法

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

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

N的選取

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

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

MRR

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

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

查詢一結(jié)果：1.AN 2.AR 3.AN 4.AN 5.AR  查詢二結(jié)果：1.AN 2.AR 3.AR 4.AR 5.AN  查詢?nèi)Y(jié)果：1.AR 2.AN 3.AN 4.AN 5.AR  

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

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

MAP

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

MAP 是反映系統(tǒng)在全部相關(guān)文檔上性能的單值指標(biāo)。系統(tǒng)檢索出來的相關(guān)文檔越靠前(rank 越高)，MAP就應(yīng)該越高。如果系統(tǒng)沒有返回相關(guān)文檔，則準(zhǔn)確率默認(rèn)為0。

例如：假設(shè)有兩個主題：

主題1有4個相關(guān)網(wǎng)頁，主題2有5個相關(guān)網(wǎng)頁。

某系統(tǒng)對于主題1檢索出4個相關(guān)網(wǎng)頁，其rank分別為1, 2, 4, 7；

對于主題2檢索出3個相關(guān)網(wǎng)頁，其rank分別為1,3,5。

對于主題1，平均準(zhǔn)確率MAP計算公式為：

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

對于主題2，平均準(zhǔn)確率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. 每條結(jié)果的相關(guān)性分等級來衡量
2. 考慮結(jié)果所在的位置，位置越靠前的則重要程度越高
3. 等級高（即好結(jié)果）的結(jié)果位置越靠前則值應(yīng)該越高，否則給予懲罰

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

評判結(jié)果的標(biāo)準(zhǔn)可以根據(jù)具體的應(yīng)用來確定，Very Good通常是指結(jié)果的主題完全相關(guān)，并且網(wǎng)頁內(nèi)容豐富、質(zhì)量很高。而具體到每條

DCG的計算公式并不唯一，理論上只要求對數(shù)折扣因子的平滑性。我個人認(rèn)為下面的DCG公式更合理，強(qiáng)調(diào)了相關(guān)性，第1、2條結(jié)果的折扣系數(shù)也更合理：

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

取以2為底的log值也來自于經(jīng)驗公式，并不存在理論上的依據(jù)。實際上，Log的基數(shù)可以根據(jù)平滑的需求進(jìn)行修改，當(dāng)加大數(shù)值時（例如使用log₅ 代替log₂），折扣因子降低更為迅速，此時強(qiáng)調(diào)了前面結(jié)果的權(quán)重。

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

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

怎樣實現(xiàn)自動化的評估？

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

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

A/B Testing

A/B Testing系統(tǒng)

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

在指標(biāo)計算時，又可細(xì)分為兩種方法，一種是基于專家評分的方法；一種是基于點擊統(tǒng)計的方法。

專家評分的方法通常由搜索核心技術(shù)研發(fā)和產(chǎn)品人員來進(jìn)行，根據(jù)預(yù)先設(shè)定的標(biāo)準(zhǔn)對A、B兩套環(huán)境的結(jié)果給予評分，獲取每個Query的結(jié)果對比，并根據(jù)nDCG等方法計算整體質(zhì)量。

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

Interleaving Testing

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

如下圖所示，將算法A和B的結(jié)果交叉放置，并分流量進(jìn)行測試，記錄用戶點擊信息。根據(jù)點擊分布來判斷A和B環(huán)境的優(yōu)劣。

Interleaving Testing評估方法

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

總結(jié)

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

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

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