目录

• 0. 前言
• 1. 原理
• 2. 步骤
• • 2.1 计算CG
  • 2.2 计算DCG
  • 2.3 计算nDCG
• 3. 本地代码实现
• • 3.1 自己编写代码
  • 3.2 使用sklearn.metrics.ndcg_score
  • 3.3 两种代码的速度比较
  • 3.4 两种代码之间的误差
• 4. spark代码实现
• • target为回归
  • target为0-1分类

0. 前言

之前在排序项目中用到了nDCG，其离线指标对模型训练及上线具有一定的参考意义，在此做一个总结。因为计算是在集群的hive表进行的，所以加上了spark上的计算代码。

1. 原理

• 高度相关的文档在搜索引擎结果列表的前面显示时更有用。
• 高度相关的文档比不相关的文档更有用，勉强相关的文件比不相关的文件更有用

2. 步骤

有以下例子：

2.1 计算CG

CG（Cumulative Gain）是结果列表中所有 items 的相关性得分的总和。CGk\text{CG}_kCGk​是前 kkk 个 items 的相关性得分的总和。

CGk=∑i=1kreli\text{CG}_k=\sum_{i=1}^{k}rel_i CGk​=i=1∑k​reli​

比如上面表格中的 CG1=3\text{CG}_1=3CG1​=3, CG2=5\text{CG}_2=5CG2​=5, CG3=8\text{CG}_3=8CG3​=8…

缺点：CG 忽略了位次的重要性，比如CG3=8\text{CG}_3=8CG3​=8的序列有{(3,3,2), (3,2,3), (2,3,3)}，但最优的序列是将最大值都排在前面的序列，如(3,3,2)。

2.2 计算DCG

DCG（Discounted CG）,折损累计收益。因为CG的缺点是不能区分位次，所以将位次作为折损，位次越靠后，折损越大，所以DCG的计算为：

DCGk=∑i=1krelilog2(i+1)\text{DCG}_k=\sum_{i=1}^{k}{\frac {rel_i} {log_2(i+1)}} DCGk​=i=1∑k​log2​(i+1)reli​​

2.3 计算nDCG

通常在排序中，nDCG（normalized DCG）是使用最多的。即对DCG进行归一化，归一化就是理想的排序结果，即相关性最大的排在前面，其DCG成为IDCG（Ideal DCG）。

nDCGk=DCGIDCG\text{nDCG}_k={\frac {DCG} {IDCG}} nDCGk​=IDCGDCG​

3. 本地代码实现

3.1 自己编写代码

def get_dcg(y_true, y_scores, k):'''@pred_arr: 预测顺序的相关度,ndarray,shape=(n,1)@gt_arr: 实际顺序相关度,ndarray,shape=(n,1)@k: 要计算的最大位置,int'''arr = [x[1] for x in sorted(zip(y_scores, y_true), reverse=True)[:k]]weights = np.power(np.log2(range(2,len(arr)+2)), -1)dcg = np.sum(arr*weights)return dcgdef get_ndcg(y_true, y_scores, k):dcg = get_dcg(y_true, y_scores, k)idcg = get_dcg(sorted(y_true), np.arange(len(y_true)), k)return dcg/idcg

3.2 使用sklearn.metrics.ndcg_score

使用方式可参考我的博文sklearn.metrics模块重要API的原理与应用总结 的“DGC和nDCG”一节。

3.3 两种代码的速度比较

随机生成不同数量的样本，查看两个函数的运行时长。

m = 100  # 样本量
y_true = np.random.randint(0,1000000,m).reshape(1,-1)
y_scores = np.random.randint(0,1000000,m).reshape(1,-1)k = 10  # 前k个最高排名的ndcg
ndcg1 = get_ndcg(y_true[0], y_scores[0], k=k)
ndcg2 = ndcg_score(y_true, y_scores, k=k)# 在jupyter中执行
"""
%%timeit
get_ndcg(y_true[0], y_scores[0], k=k)%%timeit
ndcg_score(y_true, y_scores, k=k)
"""

可以看到，当样本数量较大时，使用sklearn提供的函数速度较。值得注意的是，自己写的代码还没有优化，与复杂度与数据量大致成线性增长，可以使用前k大个数算法进行优化，进一步缩短时长。

3.4 两种代码之间的误差

两种代码之间的误差主要来自于对相同y_scores的值不同的排序位次导致的，比如：

y_scores = [0.9, 0.5, 0.6, 0.9, 0.9]
y_true = [7, 4, 1, 0, 0]

根据y_scores，y_true的排序方式及相应的ndcg为：

如果y_score保留小数点后6位的话，两个方法的误差将在10−610^{-6}10−6数量级。

4. spark代码实现

target为回归

target为0-1分类