评估指标及代码实现（NDCG）

针对排序常用的评估指标，给出其计算原理及代码实现

排序评估指标

NDCG

1 原理

NDCG全称为 Normalized Discounted Cumulative Gain（归一化折损累计增益），通常用在搜索排序任务中，在这样的任务里，通常会返回一个list作为搜索排序的结果进行输出，为了验证这个list的合理性，就需要对这个list的排序进行评价。这也是NDCG的由来。

• Gain： G，增益。

  在排序list中，增益指的就是里面的相关性得分，也就是模型的预测结果。rel(i)表示item(i)相关性得分。

• Culumatative Gain：CG，累计增益。

  对k个rel(i)进行叠加，不考虑位置关系。
  $$C{G}_k=\sum _{i=1}^{k}rel(i)$$

• Discounted Cumulative Gain: DCG，折损累计增益。

  考虑排序顺序的因素，使得排名靠前的item增益更高，对排名靠后的item进行折损。DCG认为排在前面的贡献度更大，后面的贡献度较小，也就是对增益值进行加权求和，权重就是位置引起的。
  $$DC{G}_k=\sum _{i=1}^k\frac{rel(i)}{lo{g}_2(i+1)}$$
  或者：
  $$DC{G}_k=\sum _{i=1}^k\frac{2^{rel(i)}+1}{lo{g}_2(i+1)}$$
  也即是说：i越大，排序越往后，对应的$log(i+1)$就越大，折损就越高。

• iDCG，最好排列的的DCG

  根据rel(i)进行降序排列，以此序列计算DCG，也就是最好的DCG，称为iDCG。在计算中，采用labels的相关性得分计算（隐形就是0，1;显性评分则是1-5分数）。
  如果是隐性评分，根据

• NDCG，归一化折损累计增益

  由于不同搜索的结果返回长度不一样，这样的iDCG就是一个绝对值，没法比较，因此通过DCG/iDCG来表示NDCG，代表着一个相对程度。
  $$NDCG=\frac{DCG}{iDCG}$$

2 代码实现

上面的理论乍一看理解起来很简单，但是真到具体应用的时候，发现还是很复杂的，以后很多问题需要思考，比如，里面的相似性得分，排序根据什么得分排序等等。代码的实现也容易绕晕。下面给出两种代码方式，分别是只能计算隐性得分的torch版本和numpy版本

torch

# socres为对应item（i）的预测得分，labels对item（i）的标签，由于是隐形评分数据，只有0，1点击值
scores = torch.tensor([[0,0.1,0.3,0.4,0.5]])
labels = torch.tensor([[0,1,1,0,1]])
k = 5
# 降序排列，获取推荐列表的id
rank = (-scores).argsort(dim=1)
cut = rank[:, :k]
# 获取相关性得分，也就是0，1,如果命中
hits = labels.gather(1, cut)
# 计算位置关系，从2开始计
position = torch.arange(2, 2+k)
# 根据位置关系计算位置权重
weights = 1 / torch.log2(position+1)
# 计算DCG
dcg = (hits* weights).sum(1)
# 计算iDCG，由于相关性得分为0，1，且经过排序，所以计算前面为1对应weights之和即可。
idcg = torch.Tensor([weights[:min(n, k)].sum() for n in labels.sum(1)])

ndcg = dcg / idcg
print(ndcg)

numpy

def getDCG(scores):
    return np.sum(
        np.divide(np.power(2, scores) - 1, np.log2(np.arange(scores.shape[0], dtype=np.float32) + 2)+1),
        # np.divide(scores, np.log2(np.arange(scores.shape[0], dtype=np.float32) + 2)+1),
        dtype=np.float32)

def getNDCG(rank_list, pos_items):
    relevance = np.ones_like(pos_items)
    it2rel = {
    it: r for it, r in zip(pos_items, relevance)}
    rank_scores = np.asarray([it2rel.get(it, 0.0) for it in rank_list], dtype=np.float32)
    print(rank_scores)
    idcg = getDCG(relevance)

    dcg = getDCG(rank_scores)

    if dcg == 0.0:
        return 0.0

    ndcg = dcg / idcg
    return ndcg
## l1是推荐排序列表，l2是真实点击的列表
l1 = [4,3,2,1,0]
l2 = [4,2,1]
a = getNDCG(l1, l2)
print(a)