怎么理解推荐系统中的NDCG?

  统计/机器学习 推荐系统 模型验证    浏览次数: 888
2

怎么理解推荐系统中的NDCG?看起来非常复杂,有清楚的同学可以介绍下吗?

如果能有浅显的例子就更好啦,非常感谢!

 

桐桐酱   2018-07-03 11:41



   1个回答 
10

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

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

CG(cumulative gain,累计增益)可以用于评价基于打分/评分的个性推荐系统。假设我们推荐$k$个物品,这个推荐列表的$CG_k$计算公式如下:

$$CG_k=\sum_{i=1}^k \text{rel}_i.$$

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

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

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

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

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)}.$$

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

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

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

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部

$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是$$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说明推荐越准确。

SofaSofa数据科学社区 DS面经 问答 实战

abuu   2018-07-09 01:16

非常清晰,十分感谢! - hnh100   2018-08-27 12:07


  相关主题

推荐系统有哪些常用的评价标准   3回答

推荐系统中的召回(recall)是什么意思?   1回答

推荐系统算法里的cold start是什么意思?   2回答

余弦相似和内积的意义?   1回答

推荐系统中常用的表示相似或者距离的方法有哪些?   1回答

推荐系统里的ALS是什么意思?   2回答

两个向量的余弦距离大于1?   1回答

Jaccard相似或者Jaccard距离是怎么计算的?   1回答

协同过滤的数据预处理问题   4回答

关于pairwise ranking数据预处理的问题   0回答

余弦相似的定义是什么?怎么计算?   1回答

python里怎么计算jaccard相似   2回答



回答问题时需要注意什么?

我们谢绝在回答前讲“生动”的故事。

我们谢绝“这么简单,你自己想”、“书上有的,你认真看”这类的回答;如果你认为对方的提问方式或者内容不妥,你可以直接忽略该问题,不用进行任何作答,甚至可以对该问题投反对票。

我们谢绝答非所问。

我们谢绝自己不会、硬要回答。

我们感激每一个用户在编写答案时的努力与付出!