Koresamuel: "本文主要介绍一个Search和Recommend中常用的一个评估指标：NDCG。 NDCG（Normalized Dis"

本文主要介绍一个Search和Recommend中常用的一个评估指标：NDCG。
NDCG（Normalized Discounted Cumulative Gain）可以翻译为归一化折损累计增益，通常用来衡量和评价ranking的准确性。比如在电商系统，用户一个query会返回一个商品列表，假设列表长度为N，可以用NDCG@N评价该列表的排序与真实交互列表的差距。

Cumulative Gain

CG(累计增益) 是搜索结果列表中所有文档的分级相关性得分的总和。CG只考虑了搜索结果列表中结果的相关性，而没有考虑这些文档在结果列表中的位置因素。给定一个结果列表的排序位置$$p$$ ，可定义为：
:::div{style="text-align: center"}
$$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可以定义为：
:::div{style="text-align: center"}
$$DCG_p = \sum_{i=1}^p \frac{rel_i}{log_2(i+1)}$$
:::
还有一个比较常用的公式，它能用来增加相关度影响的比重：
:::div{style="text-align: center"}
$$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 可以如下计算：
:::div{style="text-align: center"}
$$NDCG_p = \frac{DCG_p}{IDCG_p}$$
:::
其中 IDCG 为理想状态下的 DCG，计算方式为：
:::div{style="text-align: center"}
$$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 为：
:::div{style="text-align: center"}
$$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 公式计算如下：
:::div{style="text-align: center"}
$$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 公式计算如下：
:::div{style="text-align: center"}
$$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。那么理想的排序是：
:::div{style="text-align: center"}
$$3, 3, 3, 2, 2, 2, 1, 0$$
:::
m没有第7、8个结果时，理想排序是
:::div{style="text-align: center"}
$$3, 3, 2, 2, 1, 0$$
:::
理想排序的 DCG 或称为 IDCG,计算前 6 个位置
:::div{style="text-align: center"}
$$IDCG_6 = 3/1+3/1.585+2/2+2/2.322+0.387+0/2.807=7.141$$
:::
所以给定这个query的 NDCG 可计算为：
:::div{style="text-align: center"}
$$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)