介紹並實現 NDCG

本文主要介紹一個 Search 和 Recommend 中常用的一個評估指標：NDCG。
NDCG（Normalized Discounted Cumulative Gain）可以翻譯為歸一化折損累計增益，通常用來衡量和評價 ranking 的準確性。比如在電商系統，使用者一個 query 會返回一個商品列表，假設列表長度為 N，可以用 NDCG@N 評價該列表的排序與真實互動列表的差距。

Cumulative Gain#

CG (累計增益) 是搜索結果列表中所有文檔的分級相關性得分的總和。CG 只考慮了搜索結果列表中結果的相關性，而沒有考慮這些文檔在結果列表中的位置因素。給定一個結果列表的排序位置 $p$ ，可定義為：

$CG_p = \sum_{i=1}^p rel_i$

其中 $rel_i$ 表示第 $i$ 位置上的相關性。
比如使用者在某個電商平台搜索「手機」。結果的前 6 個結果分別是：iPhone，xiaomi，Huawei，OPPO, VIVO，三星。而使用者更傾向於選擇的是 Huawei，這時候無論華為手機排在前 6 的任何一位，對於累計增益都是等價的。但是對於 search，recommend 系統來說，最好的結果是 Huawei 手機放在第一個，因此引出下一個指標，折損累計增益。

Discounted Cumulative Gain#

DCG (折損累計增益) 提出，在搜索結果列表較後面位置出現相關性較高的結果時，應該對評測得分施加懲罰。懲罰比例與文檔的所在位置的對數值相關。給定一個列表結果的排序位置為 $p$ ，DCG 可以定義為：

$DCG_p = \sum_{i=1}^p \frac{rel_i}{log_2(i+1)}$

還有一個比較常用的公式，它能用來增加相關度影響的比重：

$DCG_p = \sum_{i=1}^p \frac{2^{rel_i}-1}{log_2(i+1)}$

後面這個公式更常用，在多數的搜索公司和電商平台。
當相關性得分 $rel_i\in(0,1)$ ，即取值只有 0 和 1 時，上面兩個公式是等價的。

Normalized Discounted Cumulative Gain#

NDCG (歸一化折損累計增益) , 回到文章開始提到的 NDCG。NDCG 認為搜索結果的長度因 query 而異，僅使用 DCG 對不同 query 的 performance 的比較不具有一致性。因此，對於所選擇的 $p$ 值，每個位置的 CG 應該在 query 上做規範化，首先對庫裡所有相關的結果按相關性排序，在通過位置 $p$ 生成最大可能的 DCG , 通常稱為 IDCG (理想 DCG) 。對於一個 query，NDCG 可以如下計算：

$NDCG_p = \frac{DCG_p}{IDCG_p}$

其中 IDCG 為理想狀態下的 DCG，計算方式為：

$IDCG_p = \sum_{i=1}^{|REL_p|} \frac{2^{rel_i}-1}{log_2(i+1)}$

$REL_p$ 表示庫裡相關性最高的 $p$ 個結果列表（按相關性排序後）。
對所有 query 的 NDCG 值取平均，來評判搜索引擎 Ranking 算法的平均 performance。NDCG 值越大，Ranking 算法 performance 越好。在一個完美的 Ranking 算法裡， $DCG_p$ 和 $IDCG_p$ 應該是相等的，此時 NDCG 的值為 1。而 NDCG 值最小為 0，所以 NDCG 的值分布在 0 到 1 之間。它是一個相對值，因此可以跨 query 進行比較。

計算舉例#

按前文提到的使用者搜索 query 為「手機」並返回 6 個結果為例，按結果為：iPhone，xiaomi，Huawei，OPPO, VIVO，三星，分別對應相關性得分為 3，2，3，0，1，2
那麼，對應的 CG 為：

$CG_6 = \sum_{i=1}^6 rel_i = 3 + 2 + 3 + 0 + 1 + 2 = 11$

改變任意兩個結果的順序並不會影響 CG 計算的最終結果。DCG 用於強調出現在結果列表前面的高度相關的結果。使用對數進行歸約，每個結果的 DCG 依次為：

${i}$	${rel_i}$	$2^{rel_i} - 1$	${log_2(i + 1)}$	$\frac{rel_i}{log_2(i+1)}$	$\frac{2^{rel_i}-1}{log_2(i+1)}$
1	3	7	1	3	7
2	2	3	1.585	1.262	1.893
3	3	7	2	1.5	3.5
4	0	0	2.322	0	0
5	1	1	2.585	0.387	2.585
6	2	3	2.807	0.712	1.069

用第一個 DCG 公式計算如下：

$DCG_6 = \sum_{i=1}^6 \frac{rel_i}{log_2(i+1)} = 3+1.262+1.5+0+0.387+0.712 = 6.861$

再用第二個 DCG 公式計算如下：

$DCG_6 = \sum_{i=1}^6 \frac{2^{rel_i}-1}{log_2(i+1)} = 7+1.893+3.5+0+2.585+1.069=16.047$

現在將第 3 個結果和第 4 個結果位置交換，會導致 DCG 降低。因為相關性較低的結果在排序中排名靠前，也就是說，一個更相關的結果被放在一個較低的位置上被更多地折損。
這個 query 的 performance 在這種情況下是沒法比較的，因為另一個 query 可能有更多的結果，導致更大的 DCG，但不一定代表這個 query 的 performance 更好。為了進行比較，必須對 DCG 值進行歸一化。
為了歸一化 DCG 的值，需要對給定 query 進行理想的排序。在本示例中，該排序將是所有已知相關性判斷的單調遞減排序。除了這個示例中的 6 個結果之外，假設我們還知道有一個結果 7 的相關性分數為 3，而一個結果 8 的相關性分數為 2。那麼理想的排序是：

$3, 3, 3, 2, 2, 2, 1, 0$

沒有第 7、8 個結果時，理想排序是

$3, 3, 2, 2, 1, 0$

理想排序的 DCG 或稱為 IDCG, 計算前 6 個位置

$IDCG_6 = 3/1+3/1.585+2/2+2/2.322+0.387+0/2.807=7.141$

所以給定這個 query 的 NDCG 可計算為：

$NDCG_6 = \frac{DCG_6}{IDCG_6} =\frac{6.861}{7.141} = 0.961$

Python 程式碼計算 NDCG#

import numpy as np  

def get_dcg(rec_list):  
    log_2 = np.log2(np.arange(2, len(rec_list) + 2))  
    mi = np.power(2, rec_list) - 1  
    dcg = np.array(mi / log_2).sum()  
    return dcg  

if __name__ == "__main__":  
    rec_list = [3, 2, 3, 0, 1, 2]  
    sort_rec_list = [3, 3, 2, 2, 1, 0]  
    dcg = get_dcg(rec_list)  
    idcg = get_dcg(sort_rec_list)  
    print("ndcg = dcg / idcg = ", dcg/idcg)

Reference#

https://en.wikipedia.org/wiki/Discounted_cumulative_gain