CG-DCG-NDCG 排序系统评价指标
2022-01-24 本文已影响0人
臻甄
NDCG：Normalized Discounted cumulative gain，归一化折损累计增益
- 高关联度的结果比一般关联度的结果更影响最终的指标得分：高相关性的文档>边缘相关的文档>不相关的文档。
- 有高关联度的结果出现在更靠前的位置的时候，指标会越高：高相关性的文档在搜索引擎结果列表越早出现越好。
CG 累计增益
CG只考虑到相关性的关联程度，没有考虑到位置的因素。它是一个搜索相关性分数的综合。指定位置p上CG为
代表i这个位置上的相关度
假设搜索"篮球"结果，最理想的结果是：B1、B2、B3；而出现的结果是B3、B1、B2的话，CG的值是没有变化的，因此需要下面的DCG
DCG 折损
DCG就是在每一个CG的结果上除以一个折损值，目的就是让排名越靠前的结果能影响到最后的结果。
- 假设排序越往后，价值越低：到第i个位置的时候，它的价值就是
；那么第i个结果产生的效益就是
，因此
- 还有一种比较常用的公式，用来增加相关度比重的DCG计算方式：这种多用于工业，比如多数的搜索公司和Kaggle等数据科学竞赛平台等。当相关性的得分只有0或者1的时候，上述两个公式是等价的。
# 第二种公式的实现
import numpy as np
def dcg_at_n(rel, n):
rel = np.asfarray(rel)[:n]
dcg = np.sum(np.divide(np.power(2, rel) - 1, log2_table[:rel.shape[0]]))
return dcg
早前，对数衰减因子的使用，除了衰减比较平滑外，在理论上并没有其他合理的解释。后来，Wang等人在NDCG对使用对数衰减因子提供了理论解释。作者表明，对于每一对本质上不同的排序函数，NDCG在决定拿一个更好上具有一致性
NDCG 归一化折损累计增益（NDCG）
- 由于搜索结果随着检索词的不同，返回的数量是不一致的；而DCG是一个累加的值，没法针对两个不同的所有结果进行比较，因此需要进行归一化处理。
- 什么意思呢？搜索结果列表的长度因query而异，仅使用DCG对不同query性能的比较不具有一致性。因此，对于所选择的p值，每个位置的CG应该在Query上做规范化。首先对语料库中所有相关文档的相关性排序，在通过位置p生成最大可能的DCG，也称为理想DCG（IDCG）。对于一个Query，nDCG的计算如下：
-
表示理想情况下最大的
值
- 其中
表示，结果按照相关性从大到小的顺序排序，取前p个结果组成的集合，即语料库中相关性最高的p个文档列表（已按相关性排序）。
- 请注意：在一个完美的ranking算法中，
与
是相等的，此时的
值为1.0
可对所有 Query 的 nDCG 值取平均，以此来获得搜索引擎 Ranking 算法的平均性能。
import numpy as np
def ndcg(golden, current, n = -1):
log2_table = np.log2(np.arange(2, 102))
def dcg_at_n(rel, n):
rel = np.asfarray(rel)[:n]
dcg = np.sum(np.divide(np.power(2, rel) - 1, log2_table[:rel.shape[0]]))
return dcg
ndcgs = []
for i in range(len(current)):
k = len(current[i]) if n == -1 else n
idcg = dcg_at_n(sorted(golden[i], reverse=True), n=k)
dcg = dcg_at_n(current[i], n=k)
tmp_ndcg = 0 if idcg == 0 else dcg / idcg
ndcgs.append(tmp_ndcg)
return 0. if len(ndcgs) == 0 else sum(ndcgs) / (len(ndcgs))
举例子
假设搜索到5个结果：相关性分数分别是：
可以看到只是对相关的分数进行了一个关联的打分，并没有召回所在位置对排序结果评分的影响。
：
1：3
2：1.26
3：1.5
4：0
5：0.38
6：0.71
接下来做归一化，需要先计算IDCG。
假设我们一共召回了8个文档，除了上面6个，还有两个结果的相关性为
理想情况下的相关性分数排序应该是：。
：
1：3
2：1.89
3：1.5
4：0.86
5：0.77
6：0.35
