推荐系统中的NDCG

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

CG（cumulative gain，累计增益）可以用于评价基于打分/评分的个性推荐系统。假设我们推荐k个物品，这个推荐列表的CGk计算公式如下：
$CG_k=\sum _i^k rel_i$ .
$rel_i$ 表示第 $k$ 个物品的相关性或者评分。假设我们共推荐 $k$ 个文档， $rel_i$ 可以是用户对第 $i$ 部电影的评分。

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

$M1,M2,M3,M4,M5,$

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

5, 3, 2, 1, 2

那么这个推荐列表的 $CG$ 等于
$CG_5=5+3+2+1+2=13.$
$CG$ 没有考虑推荐的次序，在此基础之后我们引入对物品顺序的考虑，就有了 $DCG$ (discounted CG)，折扣累积增益。公式如下：

$DCG_k=\sum_{i=1}^k \frac{2^{\text{rel}_i}-1}{\log_2(i+1)}.$
比如豆瓣给用户推荐了五部电影，

$M1,M2,M3,M4,M5，$

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

5, 3, 2, 1, 2

那么这个推荐列表的 $DCG$ 等于
$DCG_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$ 。

$NDCG_k=\frac {DCG_k} {IDCG_k}$
其中 $IDCG$ 是指ideal $DCG$ ，也就是完美结果下的 $DCG$ 。

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

$M1,M2,M3,M4,M5,M6,M7$
该用户对这七部电影的评分分别是

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

把这7部电影按评分排序

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

这个情况下的完美DCG是
$IDCG_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$
所以

$NDCG_5 = \frac{DCG_5}{IDCG_5}=\frac{38.5}{46.5}=0.827$
NDCG是0到1的数，越接近1说明推荐越准确。
下图为两个变量的概念解析：
推荐系统中的NDCG

相关推荐