1. 简介
推荐问题是现在互联网最核心的问题之一，从搜索体统到淘宝的用户推荐，一个好的推荐/搜索系统能够有效地提升用户的使用体验，从而更好地提升用户粘性，产生更高的经济效益。
要把推荐问题做好，一个好的metrics定义就是必不可少的，从算法训练时候的算法指标到上线模型时AB测试使用的业务指标，都需要进行很好的定义。
这里，我们不对具体的推荐业务指标进行展开（这部分比较依赖于业务，因而会非常的繁杂，需要根据实际业务进行调整），仅仅针对线下训练时的算法指标进行讨论。
通常，在实际的算法训练中，我们拿到的都是用户的历史搜索与点击记录，从而根据点击记录分析出推荐结果与用户搜索目标之间相关度，而我们的算法目标就是，通过训练一个回归模型，将相关度越高的结果排序排到最前方。
换言之，我们可以抽象问题得到如下：
- 假设候选集中一共有 N N N条数据，针对用户的某一次搜索行为 X X X，我们对这 N N N条数据计算相关度分数 f ( X ) f(X) f(X)，然后根据这个相关度分数进行排序，考察其与用户实际的搜索结果之间的相似度。
我们metrics定义的核心思想也就是：
- 当metrics越高时，我们希望实际的返回结果能够越靠近用户真实的需求。
2. 具体metrics指标考察
推荐问题常用的metrics指标包含有：
- 准确率 & 召回率
- 击中率
- map
- ndcg
1. 准确率 & 召回率
推荐问题事实上也是可以使用准确率和召回率指标来标识性能的，不过用的很少就是了。
其定义和分类问题中的准确率召回率定义大差不差，就是让用户考察总的N条数据中有效数据有哪些（假设有K条数据），然后我们推荐K条数据，考察其推荐结果的准确率与召回率。
不过，显而易见的，这种情况下需要用户考察全部的数据，需要耗费大量的时间，且大部分数据对用户而言是完全无用的，因此，这俩显然不会是一个很好的评价指标。
2. 击中率
在上述基础上，击中率算是一个改良指标，事实上也是在用的，拿浏览器搜索引擎为例，显而易见的，用户很少会进行翻页操作，或者即使翻页也不会翻页超过3次，那么我们的目标不一定是将最为关联的数据全部推荐到头部（当然能做到是最好的），更为重要的是，我们希望头部的K条数据全部都是和用户搜索关联的。
击中率就是考察关联数据在前K条数据中的占比。
但是，击中率无法区别数据间的关系，当一条数据明显优于另一条数据时，我们明显希望他被推荐在前方，但是击中率指标无法做到这一点。
为了引入顺序关系的影响，我们引入了MAP和NDCG指标。
3. MAP
MAP指标全称Mean Average Precision，他的定义其实就是针对所有的用户搜索计算AP的平均值。
因此，我们重点来考察一下Average Precision的定义。给出其定义公式如下：
A P = ∑ k n P ( k ) × r e l ( k ) ∑ k n r e l ( k ) AP = frac{sum_{k}^{n} P(k) times rel(k)}{sum_{k}^{n}rel(k)} AP=∑knrel(k)∑knP(k)×rel(k)
其中， r e l ( k ) rel(k) rel(k)为一个符号函数，表示第k个搜索结果是否与搜索目标相关，如果相关则返回1，反之返回0； P ( k ) P(k) P(k)表示前k个搜索结果中相关搜索的占比，即 P ( k ) = ∑ i k r e l ( i ) k P(k) = frac{sum_{i}^{k} rel(i)}{k} P(k)=k∑ikrel(i)。
举例说明如下，假设搜索引擎一次搜索返回了10个结果，其中4个返回结果与目标相符，排序分别为1，4，5，8，则该次搜索的AP即为：
A P = 1 1 2 4 3 5 4 8 4 = 0.65 AP = frac{frac{1}{1} frac{2}{4} frac{3}{5} frac{4}{8}}{4} = 0.65 AP=411 42 53 84=0.65
假设多次搜索的AP分别为0.6,0.65,0.7,0.75,0.8，则可以计算 M A P = 0.7 MAP=0.7 MAP=0.7。
由上即可看到，MAP指标同样是基于搜索结果的准确率，但是，与之前的两个指标不同，MAP指标考虑了搜索结果的顺序信息，当相关搜索的排序越靠前，则MAP指标越高。
但是，MAP指标还是存在一定的缺陷，最典型的缺陷在于其无法表征两个相关搜索间的程度关系，比如搜索结果A比搜索结果B明显更与搜索目标相接近，如果使用MAP指标，那么我们无法准确地令A排序在B的前方。
为此，我们又发展出了NDCG指标。
4. NDCG
下面，我们来考察一下NDCG指标的定义。
NDCG全称为Normalized Discounted Cumulative Gain，中文就不翻了，好像也没什么人用中文来说这个指标，直接称呼NDCG就行了。
他的核心思想包括两点：
- 相关度指标 r e l rel rel将不再是一个0、1函数，而是一个含有相关程度信息的值；
- 对于搜索靠后的结果，我们需要对其进行一个权重上的惩罚，因为越是靠后的结果越不会有人去考察。
基于此，我们可以给出NDCG指标的定义公式如下：
N D C G @ K = D C G @ K I D C G @ K NDCG@K = frac{DCG@K}{IDCG@K} NDCG@K=IDCG@KDCG@K
其中， @ K @K @K表示的是考察前K个搜索结果。 D C G DCG DCG指标为带有衰减的关联性增益指标，而 I D C G IDCG IDCG为归一化指标，其定义为完全符合正确排序时的 D C G DCG DCG指标的计算值。
因此，我们下面重点来考察一下 D C G DCG DCG指标的定义。
同样的，我们先给出定义公式，而后结合定义公式进行说明：
D C G @ K = ∑ i K r e l ( i ) l o g 2 ( i 1 ) DCG@K = sum_{i}^{K}frac{rel(i)}{log_{2}(i 1)} DCG@K=i∑Klog2(i 1)rel(i)
和之前MAP指标中的定义相似， r e l ( i ) rel(i) rel(i)表示第i条返回结果与搜索内容的相关度。与MAP中不同，MAP指标中的相关度定义非零即一，而DCG指标中的相关度指标却是一个量化指标。
我们同样给出一个例子来进行说明。假设某一次搜索返回了10个结果，我们来考察 N D C G @ 5 NDCG@5 NDCG@5的结果，那么，我们只需要考察其中前5条返回结果的相关度。假设相关度指标分别如下：
idx | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
relevance | 7 | 2 | 5 | 10 | 1 |
那么，我们可以计算 D C G DCG DCG指标如下：
D C G = 7 l o g 2 ( 2 ) 2 l o g 2 ( 3 ) 5 l o g 2 ( 4 ) 10 l o g 2 ( 5 ) 1 l o g ( 6 ) = 15.46 DCG = frac{7}{log_2(2)} frac{2}{log_2(3)} frac{5}{log_2(4)} frac{10}{log_2(5)} frac{1}{log(6)} = 15.46 DCG=log2(2)7 log2(3)2 log2(4)5 log2(5)10 log(6)1=15.46
I D C G = 10 l o g 2 ( 2 ) 7 l o g 2 ( 3 ) 5 l o g 2 ( 4 ) 2 l o g 2 ( 5 ) 1 l o g ( 6 ) = 18.16 IDCG = frac{10}{log_2(2)} frac{7}{log_2(3)} frac{5}{log_2(4)} frac{2}{log_2(5)} frac{1}{log(6)} = 18.16 IDCG=log2(2)10 log2(3)7 log2(4)5 log2(5)2 log(6)1=18.16
则有：
N D C G = D C G I D C G = 0.85 NDCG = frac{DCG}{IDCG} = 0.85 NDCG=IDCGDCG=0.85
此外，DCG还有一种常用的用于突出高相关度搜索结果权重的公式定义如下：
D C G @ K = ∑ i K 2 r e l ( i ) − 1 l o g 2 ( i 1 ) DCG@K = sum_{i}^{K}frac{2^{rel(i)}-1}{log_{2}(i 1)} DCG@K=i∑Klog2(i 1)2rel(i)−1
在这种定义下，我们还是针对上述例子可以计算：
D C G = 2 7 − 1 l o g 2 ( 2 ) 2 2 − 1 l o g 2 ( 3 ) 2 5 − 1 l o g 2 ( 4 ) 2 10 − 1 l o g 2 ( 5 ) 2 1 − 1 l o g ( 6 ) = 585.36 DCG = frac{2^7-1}{log_2(2)} frac{2^2-1}{log_2(3)} frac{2^5-1}{log_2(4)} frac{2^{10}-1}{log_2(5)} frac{2^1-1}{log(6)} = 585.36 DCG=log2(2)27−1 log2(3)22−1 log2(4)25−1 log2(5)210−1 log(6)21−1=585.36
I D C G = 2 10 − 1 l o g 2 ( 2 ) 2 7 − 1 l o g 2 ( 3 ) 2 5 − 1 l o g 2 ( 4 ) 2 2 − 1 l o g 2 ( 5 ) 2 1 − 1 l o g ( 6 ) = 1120.31 IDCG = frac{2^{10}-1}{log_2(2)} frac{2^7-1}{log_2(3)} frac{2^5-1}{log_2(4)} frac{2^2-1}{log_2(5)} frac{2^1-1}{log(6)} = 1120.31 IDCG=log2(2)210−1 log2(3)27−1 log2(4)25−1 log2(5)22−1 log(6)21−1=1120.31
N D C G = D C G I D C G = 0.53 NDCG = frac{DCG}{IDCG} = 0.53 NDCG=IDCGDCG=0.53
3. 总结
综上，我们整理了一下我所知的搜索问题中常用的算法指标，其中，准确率、召回率以及击中率指标都无法表征排序信息，MAP指标考虑了排序信息，但是没有区分返回结果间的相关性程度关系，而NDCG指标在考虑了顺序关系的同时还区分了返回结果与搜索目标间的相关程度关系。
因此，在实际的使用中，事实上感觉用的一直都是NDCG指标，而没怎么见过剩下几个指标被使用过。
4. 参考链接
- 推荐系统遇上深度学习(十六)–详解推荐系统中的常用评测指标
- 推荐系统常见评测标准之MAP与NDCG
- 【推荐系统】评估指标总结
