NDCG

可能大家接触比较多的是MAP，MAP考虑的是0和1的排序。而NDCG则是考虑到评分的排序。

说到NDCG就需要从CG开始说起。

CG（cumulative gain，累计增益）可以用于评价基于打分/评分的个性推荐系统。假设我们推荐$k$个物品，这个推荐列表的$C{G}_k$计算公式如下：

$$C{G}_k=\sum _{i=1}^k{\text{rel}}_i.$$

${\text{rel}}_i$表示第$k$个物品的相关性或者评分。假设我们共推荐$k$个电影，$re{l}_i$可以是用户对第$i$部电影的评分。

比如豆瓣给用户推荐了五部电影，

$M_1$,$M_2$,$M_3$,$M_4$,$M_5$，

该用户对这五部电影的评分分别是

5, 3, 2, 1, 2

那么这个推荐列表的CG等于

$$C{G}_5=5+3+2+1+2=13.$$

CG没有考虑推荐的次序，在此基础之后我们引入对物品顺序的考虑，就有了DCG(discounted CG)，折扣累积增益。公式如下：

$$DC{G}_k=\sum _{i=1}^k\frac{2^{{\text{rel}}_i}-1}{{\log }_2(i+1)}.$$

比如豆瓣给用户推荐了五部电影，

$M_1$,$M_2$,$M_3$,$M_4$,$M_5$，

该用户对这五部电影的评分分别是

5, 3, 2, 1, 2

那么这个推荐列表的DCG等于

$$DC{G}_5=\frac{2^5-1}{{\log }_{2}2}+\frac{2^3-1}{{\log }_{2}3}+\frac{2^2-1}{{\log }_{2}4}+\frac{2^1-1}{{\log }_{2}5}+\frac{2^2-1}{{\log }_{2}6}=31+4.4+1.5+0.4+1.2=38.5$$

DCG没有考虑到推荐列表和每个检索中真正有效结果个数，所以最后我们引入NDCG(normalized discounted CG)，顾名思义就是标准化之后的DCG。

$$NDC{G}_k=\frac{DC{G}_k}{IDC{G}_k}$$

其中$IDCG$是指ideal DCG，也就是完美结果下的DCG。

继续上面的例子，如果相关电影一共有7部

$M_1$,$M_2$,$M_3$,$M_4$,$M_5$,$M_6$,$M_7$

该用户对这七部电影的评分分别是

5, 3, 2, 1, 2 , 4, 0

把这7部电影按评分排序

5, 4, 3, 2, 2, 1, 0

这个情况下的完美DCG是$$IDC{G}_5=\frac{2^5-1}{{\log }_{2}2}+\frac{2^4-1}{{\log }_{2}3}+\frac{2^3-1}{{\log }_{2}4}+\frac{2^2-1}{{\log }_{2}5}+\frac{2^2-1}{{\log }_{2}6}=31+9.5+3.5+1.3+1.2=46.5$$

所以

$$NDC{G}_5=\frac{DC{G}_5}{IDC{G}_5}=\frac{38.5}{46.5}=0.827$$

NDCG是0到1的数，越接近1说明推荐越准确。

参考文献