# 推荐系统评价指标nDCG到底如何实现
[真中合欢](https://www.zhihu.com/people/zhen-zhong-he-huan-68)
真中合欢爱好者
作为一个推荐系统方向的研究者，跑模型避不开nDCG这个指标。但是怎奈何本人愚钝，在网上看了很多对nDCG的讲述，比如：[Ranking算法评测指标之 CG、DCG、NDCG](https://zhuanlan.zhihu.com/p/136199536) 、[搜索排序性能评价指标-NDCG](https://zhuanlan.zhihu.com/p/78657246) 、 [CG, DCG, NDCG](https://link.zhihu.com/?target=https%3A//www.cnblogs.com/ywl925/archive/2012/11/21/2780861.html) 、 [搜索评价指标——NDCG](https://link.zhihu.com/?target=https%3A//www.cnblogs.com/by-dream/p/9403984.html) 后，依旧有一些问题无法理解：
1. 累计增益用到的相似度究竟是什么
2. 折损累计增益到底是对谁排序，计算谁的相似度
在Github上搜了一圈论文开源代码，看了各种人的实现方法后，决定写下自己的理解。
## **引入**
想搞清楚nDCG就首先要知道四个概念：
1.模型分数：顾名思义，模型预测出的用户u对项目i的兴趣分数。
2.真实分数：用户u对项目i的真实兴趣分数，也就是数据集中的分数，显式反馈数据集一般是1-5，隐式一般是1或0。
3.模型排序：根据模型分数对项目依次进行的排序，也就是模型成生的top-k推荐顺序。
4.真实排序：根据真实分数对项目依次进行的排序。
## 累计增益 CG
$$
CG_k = \sum_{i=1}^k rel_i\\
$$
网上的说明大多数喜欢用 $CG_p$ 来表示累计增益，但请允许我将p改成k。因为在推荐系统方向，更常用的是top-**k**推荐。如果按照论文的风格，那就应该写为$CG@k$ 。所以k在这里代表什么不言而喻，就是top-k推荐的这个k，在检索里就是返回给用户的检索结果的条数。
这里 $rel$ 表示相似度分数（以下简称“分数”），这个分数到底是什么？分数是什么什么取决于你用的数据集是什么。如果是用的是推荐的显示反馈，也就是打分数据集（1-5分），那么这个1-5的打分就是计算时要用的分数。如果用的隐式反馈，也就是用户点击数据集，那这个分数就是0-1。1表示用户点击过，0表示未点击过。
但是在实际计算nDCG的时候，到底是用数据集中标注的真实分数，还是我们模型预测的分数？请往下看。
## 折损累计增益 DCG
$$
DCG_k = \sum_{i=1}^k\frac{rel_i}{\log(i+1)} \\
$$
和CG相同，如果按照论文风格来写，可以表示为 $DCG@k$ 。DCG是每个推荐项目的分数，除以它所在的位置，也就是说一个项目（item）推荐的排名越靠后，它折损的越严重。这里的顺序，是预测的顺序，而用到的分数，是数据集中的真实分数。
所以DCG的计算方法是：我们的模型计算出某个用户对所有候选项目的相似度后，根据相似度对项目进行排序，返回前k个最相似的项目作为推荐结果。这k个项目维持我们推荐的顺序，为它们标注上它们在数据集中真实的打分，然后拿来计算DCG。
DCG还有另一种计算方式，是用指数计算的，公式稍有差别，但是计算思想相同，具体可以参照我一开始列出的那几个教程。
## 归一化折损累计增益 nDCG
$$
nDCG_k =\frac{DCG_k}{iDCG_k}\\
$$
nDCG在论文里通常写作 $nDCG@k$ 。$nDCG_k$ 就是折损累计增益 $DCG_k$ 除以最大折损累计增益 $iDCG_k$ 。
最大折损累计增益iDCG的计算方法是：模型返回了k个推荐的项目，我们将这k个项目标注上它们在原始数据集上的分数，然后再根据分数进行重排序，然后再计算DCG，得到的就是iDCG。
那么nDCG整体的计算过程就是：模型根据用户和候选物品的相似度，对候选项目进行排序，返回k个最相似的项目作为推荐结果。保持模型的推荐顺序，给每个项目标注它在原始数据集中的分数，计算DCG。然后再对标注的分数从大到小重排，再计算一次DCG，这一次计算出的DCG就是iDCG，让二者相除得到的就是nDCG。
## 最后附一个在隐式反馈数据集计算ndcg的样例代码
```
import numpy as np
np.random.seed(2021)
class Model:
def __init__(self, k):
self.k = k
self.item_size = 50
def __call__(self, users):
# 模型随机返回 k 个 item,模拟推荐结果
res = np.random.randint(0, self.item_size, users.shape[0] * self.k)
return res.reshape((users.shape[0], -1))
def get_implict_matrix(rec_items, test_set):
rel_matrix = [[0] * rec_items.shape[1] for _ in range(rec_items.shape[0])]
for user in range(len(test_set)):
for index, item in enumerate(rec_items[user]):
if item in test_set[user]:
rel_matrix[user][index] = 1
return np.array(rel_matrix)
def DCG(items):
return np.sum(items / np.log(np.arange(2, len(items) + 2)))
def nDCG(rec_items, test_set):
assert rec_items.shape[0] == len(test_set)
# 获得隐式反馈的rel分数矩阵
rel_matrix = get_implict_matrix(rec_items, test_set)
ndcgs = []
for user in range(len(test_set)):
rels = rel_matrix[user]
dcg = DCG(rels)
idcg = DCG(sorted(rels, reverse=True))
ndcg = dcg / idcg if idcg != 0 else 0
ndcgs.append(ndcg)
return ndcgs
# 假设 top-20 推荐,一共 5 个 user, 50 个 item ,隐式反馈数据集.
users = np.array([0, 1, 2, 3, 4])
# test_set 表示 5 个用户在测试集中分表交互过那些 item
test_set = [
[0, 21, 31, 41, 49],
[2, 3, 4, 5, 33],
[5, 10, 20, 30, 39, 44, 45, 49],
[4, 7, 13, 15],
[2]
]
model = Model(20)
rec_items = model(users)
ndcgs = nDCG(rec_items, test_set)
print(ndcgs)
```
## 续
1. 隐式反馈数据集计算iDCG更简单，因为没被点击过的项目分数都是0，点击过的都是1，不用重排，可以根据真正例数量TP直接算出iDCG。
$$
iDCG_k^{Implicit} = \sum_{i=1}^{TP}\frac{1}{\log(i+1)}\\
$$
![]()