推荐系统常见评测标准之MAP与NDCG

清疚 2022-07-17 00:39 192阅读 0赞

## MAP ##

### AP ###

关于 AP 与 MAP 这里有个非常好的文章: [intuition-behind-average-precision-and-map][]

在了解MAP(Mean Average Precision)之前，先来看一下AP(Average Precision), 即为平均准确率。

对于AP可以用这种方式理解: 假使当我们使用google搜索某个关键词，返回了10个结果。当然最好的情况是这10个结果都是我们想要的相关信息。但是假如只有部分是相关的，比如5个，那么这5个结果如果被显示的比较靠前也是一个相对不错的结果。但是如果这个5个相关信息从第6个返回结果才开始出现，那么这种情况便是比较差的。这便是AP所反映的指标，与recall的概念有些类似，不过是“顺序敏感的recall”。

比如对于用户 u, 我们给他推荐一些物品，那么 u 的平均准确率定义为：

APu=1|teu|∑i∈teu∑j∈teuδ(puj≺pui)\+1pui

在这里 pui 表示推荐列表中物品 i 的排序位置。puj≺pui 表示在对用户 u 的排序列表中物品 j 的排序位置在物品i 的前面。

上面的式子是不是挺唬人的，下面来分析一下

def AP(ranked_list, ground_truth):
        """Compute the average precision (AP) of a list of ranked items """
        hits = 0
        sum_precs = 0
        for n in range(len(ranked_list)):
            if ranked_list[n] in ground_truth:
                hits += 1
                sum_precs += hits / (n + 1.0)
        if hits > 0:
            return sum_precs / len(ground_truth)
        else:
            return 0

### MAP ###

那么对于MAP(Mean Average Precision)，就很容易知道即为所有用户 u 的AP再取均值(mean)而已。那么则有：

MAP=∑u∈teAPu|te|

## NDCG ##

### CG ###

先从后两个字母CG(Cummulative Gain)说起, 直接翻译的话叫做“累计增益”。 在推荐系统中，CG即将每个推荐结果相关性(relevance)的分值累加后作为整个推荐列表(list)的得分。

CGk=∑i=1kreli

这里， reli 表示处于位置 i 的推荐结果的相关性，k 表示所要考察的推荐列表的大小。

### DCG ###

CG的一个缺点是没有考虑每个推荐结果处于**不同位置**对整个推荐效果的影响，例如我们总是希望相关性高的结果应排在前面。显然，如果相关性低的结果排在靠前的位置会严重影响用户体验， 所以在CG的基础上引入位置影响因素，即DCG(Discounted Cummulative Gain), “Discounted”有打折，折扣的意思，这里指的是对于排名靠后推荐结果的推荐效果进行“打折处理”:

DCGk=∑i=1k2reli−1log2(i\+1)

*  分子部分 2reli−1  
    reli越大，即推荐结果 i 的相关性越大，推荐效果越好， DCG越大。
 *  分母部分 log2(i\+1)  
    i 表示推荐结果的位置，i 越大，则推荐结果在推荐列表中排名越靠后，推荐效果越差，DCG越小。

### NDCG ###

DCG仍然有其局限之处，即**不同的推荐列表之间，很难进行横向的评估**。而我们评估一个推荐系统，不可能仅使用一个用户的推荐列表及相应结果进行评估， 而是对整个测试集中的用户及其推荐列表结果进行评估。 那么不同用户的推荐列表的评估分数就需要进行归一化，也即NDCG(Normalized Discounted Cummulative Gain)。

在介绍NDCG之前，还需要了解一个概念：IDCG. IDCG, 即Ideal DCG， 指推荐系统为某一用户返回的最好推荐结果列表， 即假设返回结果按照相关性排序， 最相关的结果放在最前面， 此序列的DCG为IDCG。因此DCG的值介于 (0,IDCG\] ，故NDCG的值介于(0,1\].

对于用户 u 的NDCG@k定义为：

NDCGu@k=DCGu@kIDCGu

这里的  k 表示推荐列表的大小。

那么，则有：

NDCG@k=∑u∈teNDCGu@k|te|

在具体操作中， 可以事先确定推荐目标和推荐结果的相关性分级。

*  例如可以使用 0，1分别表示相关或不相关，比如此处我们用refi=δ(i∈teu) , 在这里如果 x 为true, 则δ(x)=1，否则δ(x)=0.
 *  或是使用 0~5 分别表示严重不相关到非常相关, 也即相当于确定了rel 值的范围。之后对于每一个推荐目标的返回结果给定 rel 值，然后使用DCG的计算公式计计算出返回结果的DCG值。使用根据排序后的 rel 值序列计算IDCG值， 即可计算NDCG.

参见：  
[szuthesis][]

原始参考：  
[使用NDCG评估关键词推荐系统的相关性][NDCG]

[intuition-behind-average-precision-and-map]: https://makarandtapaswi.wordpress.com/2012/07/02/intuition-behind-average-precision-and-map/
[szuthesis]: https://liuchengxu.github.io/szuthesis/pdf/thesis.pdf
[NDCG]: http://semocean.com/%E4%BD%BF%E7%94%A8ndcg%E8%AF%84%E4%BC%B0%E5%85%B3%E9%94%AE%E8%AF%8D%E6%8E%A8%E8%8D%90%E7%B3%BB%E7%BB%9F%E7%9A%84%E7%9B%B8%E5%85%B3%E6%80%A7/