Press "Enter" to skip to content

NDCG介绍与实现和推荐系统中的应用

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

 

本文主要介绍一个搜索和推荐中常用的一个评估指标:。

 

(Normalized Discounted Cumulative Gain)直接翻译为归一化折损累计增益,这个指标通常是用来衡量和评价排序的准确性,比如:推荐系统通常为某用户返回一个item列表,假设列表长度为,这时可以用评价该排序列表与用户真实交互列表的差距。的两个思想:

 

1、高关联度的结果比一般关联度的结果更影响最终的指标得分(高相关性的物比低相关性的物品更有用,低相关性的物品比不相关的物品更有用)

 

2、有高关联度的结果出现在更靠前的位置的时候,指标会越高(理想情况下,推荐的列表是按照高相关性进行倒排的,即相关性越高的物品排的越靠前越好)

 

想要搞明白,需要从Cumulative Gain开始说起。

 

Cumulative Gain,CG

 

(累计增益
)是搜索结果列表中所有文档的分级相关性得分的总和。只考虑了搜索结果列表中文档的相关性,而没有考虑这些文档在结果列表中的位置因素。给定一个结果列表的排序位置,可定义为:

 

其中表示第位置上的相关性。

 

比如用户在某电商平台搜索「手机」,搜索列表的前5条中分别为:苹果手机、小米手机、华为手机、荣耀手机、OPPO手机,而用户倾向于选择的是荣耀,这时候无论荣耀手机排在前5位中的任何一位,对于累计增益
来讲都是等价的。但是对于搜索、推荐系统而言,最好的结果是将荣耀手机排在前面。因此也就引出了折损累计增益。

 

Discounted Cumulative Gain

 

(折损累计增益
)提出在搜索结果列表的较低位置上出现相关性较高的文档时,应该对评测得分施加惩罚。惩罚比例与文档的所在位置的对数值相关。给定一个结果列表的排序位置,可定义为:

 

早前,对数衰减因子的使用,除了衰减比较平滑外,在理论上并没有其他合理的解释。后来,Wang等人在其对使用对数衰减因子提供了理论解释。作者表明,对于每一对本质上不同的排序函数,在决定哪一个更好上具有一致性。

 

当然还有一种比较常用的公式,它能用来增加相关度影响的比重:

 

后一个公式在工业中被广泛使用,如多数的搜索公司和 Kaggle 等数据科学竞赛平台等。

 

当相关性得分只有 0 或 1 两个值时,即,上述两个公式是等价的。

 

Normalized Discounted Cumulative Gain

 

(归一化折损累计增益
)认为搜索结果列表的长度因 Query 而异,仅使用对不同 Query 性能的比较不具有一致性。因此,对于所选择的值,每个位置的 CG 应该在 Query 上做规范化。首先对语料库
中所有相关文档的相关性排序,再通过位置生成最大可能的,也称为理想。对于一个 Query ,的计算如下:

 

其中为理想状态下的,其计算如下:

 

其中,表示语料库中相关性最高的个文档列表(已按相关性排序)。

 

可对所有 Query 的值取平均,以此来获得搜索引擎 Ranking 算法的平均性能。请注意,在一个完美的 Ranking 算法中,与是相等的,此时的值为 1.0。此外,值域为,它是一个相对值,因此是可 cross-query 比较的。

 

使用的主要难点是,当只有部分相关性反馈可用时,无法获取理想的

 

NDCG计算示例

 

依旧以上文中提到的用户搜索「手机」返回的五个商品为例。假设其对应的相关性为:

 

苹果手机:3、小米手机:2、华为手机:4、荣耀手机:5、OPPO手机:1

 

则对应的的:

 

而对应的为:

 

 

2^{rel_i}-1log_2(i+1)(2^{rel_i}-1) / (log_2(i+1))
13717
2231.581.89
341527.5
45312.3213.35
5112.580.39

 

接下来看,计算首先要计算一下,假设召回的有6个商品,第6个商品的相关性为 3,那幺在理想情况下,按照相关性排序为:5、4、3、3、2、1。

 

计算:

 

 

2^{rel_i}-1log_2(i+1)(2^{rel_i}-1) / (log_2(i+1))
1531131
24151.589.46
33723.5
4372.323.01
5232.581.16

 

 

Python实现NDCG

 

import numpy as np
def get_dcg(rec_list):
    log_2 = np.log2(np.arange(2, len(rec_list) + 2))
    print(log_2)
    mi = np.power(2, rec_list) - 1
    print(mi)
    dcg = np.array(mi / log_2).sum()
    print(np.array(mi / log_2))
    print(dcg)
return dcg
if __name__ == "__main__":
    rec_list = [3, 2, 4, 5, 1]
    sort_rec_list = [5, 4, 3, 3, 2]
    print(rec_list)
    print(sort_rec_list)
    dcg = get_dcg(rec_list)
    idcg = get_dcg(sort_rec_list)
    print("ndcg = dcg / idcg = ", dcg/idcg)

 

参考:

 

https://zhuanlan.zhihu.com/p/136199536

 

关注我们不错过每一篇精彩

 

「搜索与推荐Wiki」猜你喜欢

 

1


基尼系数介绍与在推荐系统中的应用

 

2、
闲聊推荐系统中的曝光过滤机制

 

3、
特征工程|四种主流的embedding特征技术

 

4



上班如上坟的年轻人,我有这些话想对你说

 

5、
电商平台中的9种共性推荐策略

 

 

Be First to Comment

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注