在搜索和推薦任務中，系統(tǒng)常返回一個item列表。如何衡量這個返回的列表是否優(yōu)秀呢？

例如，當我們檢索【推薦排序】，網頁返回了與推薦排序相關的鏈接列表。列表可能會是[A,B,C,G,D,E,F],也可能是[C,F,A,E,D]，現在問題來了，當系統(tǒng)返回這些列表時，怎么評價哪個列表更好？

這就引出了這篇文章要介紹的兩個評價指標——NDCG和MAP，這兩個指標都是用來評估排序結果的。

1. NDCG

NDCG的全稱是：Normalized Discounted Cumulative Gain(歸一化折損累計增益）學習NDCG最好按照G-CG-DCG-NDCG這個順序來學習。

• Gain：表示一個列表中所有item的相關性分數。rel(i)表示item(i)相關性得分。

  $Gain=rel(i)$

• Cumulative Gain：表示對K個item的Gain進行累加。

  $C{G}_k={\sum }_{i=1}^{k}rel(i)$

  CG只是單純累加相關性，不考慮位置信息。

  如果返回一個list_1= [A,B,C,D,E]，那list_1的CG為0.5+0.9+0.3+0.6+0.1=2.4

  如果返回一個list_2=[D,A,E,C,B]，那list_2的CG為0.6+0.5+0.1+0.3+0.9=2.4

  所以，順序不影響CG得分。如果我們想評估不同順序的影響，就需要使用另一個指標DCG來評估。

• Discounted Cumulative Gain: 考慮排序順序的因素，使得排名靠前的item增益更高，對排名靠后的item進行折損。

  CG與順序無關，而DCG評估了順序的影響。DCG的思想是：list中item的順序很重要，不同位置的貢獻不同，一般來說，排在前面的item影響更大，排在后面的item影響較小。（例如一個返回的網頁，肯定是排在前面的item會有更多人點擊）。所以，相對CG來說，DCG使排在前面的item增加其影響，排在后面的item減弱其影響。

  $DC{G}_k={\sum }_{i=1}^k\frac{rel(i)}{lo{g}_2(i+1)}$

  怎么實現這個思想呢？DCG在CG的基礎上，給每個item的相關性比上log2(i+1)，i越大，log2(i+1)的值越大，相當于給每個item的相關性打個折扣，item越靠后，折扣越大。

  還是上面那個例子：

  list_1=[A,B,C,D,E], 其對應計算如下：

  i	rel(i)	log(i+1)	rel(i)/log(i+1)
  1=A	0.5	1	0.5
  2=B	0.9	1.59	0.57
  3=C	0.3	2	0.15
  4=D	0.6	2.32	0.26
  5=E	0.1	2.59	0.04

  list_1的 DCG_1= 0.5+0.57+0.15+0.26+0.04=1.52

  list_2=[D,A,E,C,B]，其對應計算如下：

  i	rel(i)	log(i+1)	rel(i)/log(i+1)
  1=D	0.6	1	0.6
  2=A	0.5	1.59	0.31
  3=E	0.1	2	0.05
  4=C	0.3	2.32	0.13
  5=B	0.9	2.59	0.35

  list_2的 DCG_2= 0.6+0.31+0.05+0.13+0.35=1.44

  DCG_1 > DCG_2, 所以在這個例子里list_1優(yōu)于list_2。

  到這里，我們可以知道，使用DCG方法就可以對不同的list進行評估，那為什么后面還有一個NDCG呢？

• NDCG(Normalized DCG): 歸一化折損累計增益

  在NDCG之前，先了解一些IDGC(ideal DCG)–理想的DCG，IDCG的依據是：是根據rel(i)降序排列，即排列到最好狀態(tài)。算出最好排列的DCG，就是IDCG。

  IDCG=最好排列的DCG

  對于上述的例子，按照rel(i)進行降序排列的最好狀態(tài)為list_best=[B,D,A,C,E]

  i	rel(i)	log(i+1)	rel(i)/log(i+1)
  1=B	0.9	1	0.9
  2=D	0.6	1.59	0.38
  3=A	0.5	2	0.25
  4=C	0.3	2.32	0.13
  5=E	0.1	2.59	0.04

  IDCG = list_best的DCG_best = 0.9+0.38+0.25+0.13+0.04=1.7 (理所當然，IDCG>DCG_1和DCG_2)

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

  $NDCG=\frac{DCG}{IDCG}$

  所以NDGC使用DCG/IDCG來表示，這樣的話，NDCG就是一個相對值，那么不同query之間就可以通過NDCG值進行比較評估。

2. MAP

要學習MAP指標首先要了解Precision這個指標，即精確度。在推薦系統(tǒng)場景下，我們可以定義正樣本為相關的商品，因此Precision就代表了，推薦的 n 個商品中，有多少個商品是相關的。而Recall就代表了數據庫中一共有 m個相關商品，推薦系統(tǒng)選出了多少個相關商品。

例如下面的理財產品推薦場景，用戶在未來購買了四款產品，而一個推薦系統(tǒng)在當前推薦了三款產品，用戶只購買了一款產品。那么此時，推薦系統(tǒng)的Recall為 1/4 ，Precision為 1/3。

值得注意的是，由于屏幕大小限制，推薦系統(tǒng)只能展示前 N 個商品，因此一般推薦系統(tǒng)中的Precision計算會采用Cutoff形式進行計算。如下圖所示，盡管我們的推薦系統(tǒng)可以推薦 m個商品，但是在Cutoff-Precision的計算過程中，只會考慮前 k 個商品的Precision。

根據上面的概念，我們就可以定義Average Precision。從公式中可以看出，AP@N可以直觀理解為枚舉Precision@k之后取平均值。

第k個item的precision是指前k個推薦的item里被用戶pick的item有幾個

在推薦系統(tǒng)場景下，使用AP最大的好處在于AP不僅僅考慮了商品推薦的準確率，還考慮了推薦順序上的差異。考慮下面這樣一個表格，從整體來考慮的話，三種推薦方案都只推薦了一個相關商品，但是第一種推薦方案明顯是更好的，而AP指標可以體現這種差異。

介紹了AP@N指標，我們就可以定義MAP@N指標了。其實MAP@N指標就是將所有用戶 UUU 的AP@N指標進行平均。

總的來說，MAP指標同時考慮了預測精準度和相對順序，從而避免了傳統(tǒng)Precision指標無法刻畫推薦商品相對位置差異的弊端。因此。在很多推薦系統(tǒng)場景下，MAP指標是一個非常值得嘗試的推薦系統(tǒng)評估指標。

參考1：知乎Satellite
參考2：知乎震靈