[轉貼]NDCG評量指標，滿清楚的解說文章

衡量指標編輯

衡量搜索引擎質量指標(DCG -- Discounted Cumulative Gain)

DCG的英文全稱是Discounted cumulative gain，它是一個衡量搜索引擎算法的指標。

搜索引擎一般採用PI（per item）的方式進行評測，簡單地說就是逐條對搜索結果進行分等級的打分。假設我們現在在Google上搜索一個詞，然後得到5個結果。我們對這些結果進行3個等級的區分：Good（好）、Fair（一般）、Bad（差），然後賦予他們分值分別為3、2、1，假定通過逐條打分後，得到這5個結果的分值分別為3、2 、1 、3、 2。

接下來我們來看看是怎麼計算DCG的

使用DCG這個統計方法有兩個前提：

1.在搜索結果頁面，越相關的結果排在越前面越好

2.在PI標註時，等級高的結果比等級低的結果好，即Good要比Fair好、Fair要比Bad好。

DCG這個概念是從Cumulative Gain這個概念發展起來的

什麼叫Cumulative Gain（CG）

CG並不考慮在搜索結果頁面中結果的位置信息，它是在這個搜索結果list裡面所有的結果的等級對應的得分的總和。如一個搜索結果list頁面有P個結果，CG被定義為：

reli是第i位結果的得分。CG的統計並不能影響到搜索結果的排序，CG得分高只能說明這個結果頁面總體的質量比較高並不能說明這個算法做的排序好或差。什麼是好的排序？也就是說要把Good的結果排到Fair結果上面、Fair結果排到Bad結果上面，如果有Bad的結果排在了Good上面，那當然排序就不好了。到底排序好不好，需要一個指標來衡量，DCG就是這樣的一個指標。

上面的例子CG=3+2+1+3+2=11，如果調換第二個結果和第三個結果的位置CG=3+1+2+3+2=11，並沒有改變總體的得分。

Discounted Cumulative Gain

在一個搜索結果list裡面，比如有兩個結果的打分都是Good，但是有一個是排在第1位，還有一個是排在第40位，雖然這兩個結果一樣都是Good，但是排在第40位的那個結果因為被用戶看到的概率是比較小的，他對這整個搜索結果頁面的貢獻值是相對排在第一位那個結果來得小的。

DCG的思想是等級比較高的結果卻排到了比較後面，那麼在統計分數時，就應該對這個結果的得分有所打折。一個有p（P≧2）個結果的搜索結果頁面的DCG定義為：

為什麼要用以2為底的對數函數？這個並沒有明確的科學依據，大概是根據大量的用戶點擊與其所點寶貝的位置信息，模擬出一條衰減的曲線。

那麼上例中的數字如下：

DCG=3+（1+1.26+1.5+0.86）=7.62

DCG的公式另外一種表達式是：

這個表達式在一些搜索文檔中經常會被提到，他的作用和之前的那個公式一樣，但是這個公式只適合打分分兩檔的評測。

nDCG（normalize DCG）

因為不同query的搜索結果有多有少，所以不同query的DCG值就沒有辦法來做對比。

定義：

IDCG（ideal DCG），就是理想的DCG。IDCG如何計算？首先要拿到搜索的結果，人工對這些結果進行排序，排到最好的狀態後，算出這個排列下本query的DCG，就是IDCG。

因為nDCG是一個相對比值，那麼不同的query之間就可以通過比較nDCCG來決定哪個query的排序比較好。

例子中，理想的排序應該是3 、3 、2 、2 、1，那麼IDCG=3+3+1.26+1+0.43=8.69

nDCG=DCG/IDCG=7.62/8.69=0.88，從nDCG這個值可以看出目前算法存在的優化空間。