在搜索系统排序任务中，评估排序质量是至关重要的。NDCG（Normalized Discounted Cumulative Gain）指标作为一种常用的排序评价指标，能够量化排序结果与理想排序之间的差距。本文将介绍NDCG指标的定义、计算方法以及其在实际应用中的重要性。
1.为什么要评估排序？
排序问题对于任何一个计算机领域的从业者来说是老熟人了，解决简单排序问题的基础算法也有很多， 诸如冒泡排序，快速排序，归并排序等等。这些算法应用的场景都是在已知一个显式的数组的情况下，返回最佳排序。 例如给定一个数组\([1,3,5,2,4]\)， 我们熟知的各种排序算法都会给我们一个最理想的排序\([5,4,3,2,1]\)。 在这种场景下，当然没有评估排序的必要，因为最理想的排序是显而易见的。
但在实际应用场景下，例如搜索场景的Ranking任务中，每个元素的价值是隐式的，我们无法预先知道最理想的排序。 举个例子，想象这样一个场景，我们经营了一家美妆商店，仓库中有5支不同品牌的口红，一位用户在app上搜索口红，在用户的搜索结果页中这五支口红该以什么顺序出现呢？ （实际场景中，需要考虑口红的价格，用户的品牌偏好等等因素以达成商店的收益最大化)。这里为了简化问题方便讨论，我们假设每支口红都有一个隐式的成交概率评分。 最理想的情况是将口红按照这个隐式的成交概率评分倒排。评分越高的商品占据越靠前的宝贵的曝光位。但由于评分是隐式的，工程师研发的排序算法只能综合各方面因素推测成交可能性，给出排序结果。 这时为了事后评估排序算法，就需要一个标准来对排序的效果进行排序，从而确定离最理想的情况还有多少差距。
比如最理想的口红排序是\([5,4,3,2,1]\),但是算法A给出了\([5,1,3,2,4]\)， 算法B给出了\([5,3,4,2,1]\)，哪个排序更优呢？只有知道了哪个排序更优，更接近最理想的排序，机器学习算法才能够开始根据现有样本和一个可量化的标准进行拟合。
所以确定一个标准来衡量排序的质量是有必要的。
2. 如何评估排序？
仍然关注之前提到的例子，假设第\(i\)个口红拥有一个隐藏的成交概率评分\(ItemScore_i\)，这里称这个评分为\(Gain\)，这个评分当然是越高越好，我们期望用户在更靠前的位置看到的商品具有更高的成交可能。
2.1 Cumulative Gain
于是根据评分越高越好这个初衷，我们似乎有了一个粗糙的标准：
\[\small Cumulative~Gain = \sum_{i=1}^{n} ItemScore_i\]这里的\(Cumulative~Gain\)称之为累加增益，即所有商品的成交概率评分总和。但当我们使用这个指标对算法A和算法B的排序进行计算。 发现算法A的累加增益与算法B相同：
\[\small Cumulative~Gain_A = 5 + 1 + 3 + 2 + 4 = 15\] \[\small Cumulative~Gain_B = 5 + 3 + 4 + 2 + 1 = 15\]看上去这个指标只是单纯计算了商品序列的总评分，并不能评估排序好坏，我们需要进一步改进。
2.2 Discounted Cumulative Gain
\(Cumulative~Gain\)仅仅考虑了商品的价值评分，并没有考虑每个商品的实际位置带来的影响。位置越靠后的商品曝光机会处于劣势，如果排序算法将高成交概率评分的商品放到了靠后的位置，需要得到惩罚， 相反如果将高成交概率评分的商品放到了靠前的位置，需要得到奖励。
基于以上想法，尝试改进\(Cumulative~Gain\)，引入\(Discounted~Cumulative~Gain\)，即折损累加增益，以下简写为\(DCG\)：
\[DCG = \sum_{i=1}^{n} \frac{ItemScore_i}{log_2(i+1)}\]实际应用场景中，为了增加\(ItemScore\)的影响，一般采用：
\[DCG = \sum_{i=1}^{n} \frac{2^{ItemScore_i} - 1}{log_2(i+1)}\]在这个标准下，重新计算算法A与B的排序得分：
\[\small \begin{align} DCG_A & = \frac{2^5 - 1}{log_2(1 + 1)} + \frac{2^1 - 1}{log_2(2+ 1)} \\&+ \frac{2^3 - 1}{log_2(3 + 1)} + \frac{2^2 - 1}{log_2(4 + 1)} + \frac{2^4 - 1}{log_2(5 + 1)} \\ & \approx 42.225751536309765 \end{align}\] \[\small \begin{align} DCG_B & = \frac{2^5 - 1}{log_2(1 + 1)} + \frac{2^3 - 1}{log_2(2+ 1)} \\&+ \frac{2^4 - 1}{log_2(3 + 1)} + \frac{2^2 - 1}{log_2(4 + 1)} + \frac{2^1 - 1}{log_2(5 + 1)} \\ & \approx 44.595390756454925 \end{align}\]2.3 Ideal Discounted Cumulative Gain
根据以上标准，计算最理想的排序\([5,4,3,2,1]\)的折损累加增益。
这里我们称之为\(Discounted~Cumulative~Gain_{ideal}\)，即理想折损累加增益：
\[\small \begin{align} DCG_{ideal} & = \frac{2^5 - 1}{log_2(1 + 1)} + \frac{2^4 - 1}{log_2(2+ 1)} \\&+ \frac{2^3 - 1}{log_2(3 + 1)} + \frac{2^2 - 1}{log_2(4 + 1)} + \frac{2^1 - 1}{log_2(5 + 1)} \\ & \approx 45.64282878502658 \end{align}\]2.4 Normalized Discounted Cumulative Gain
最后，为了衡量算法A与算法B产生的结果与理想结果相差多少，引入\(Normalized~Discounted~Cumulative~Gain\)，即\(NDCG\)。
\[NDCG = \frac{DCG}{IDCG}\]现在，分别计算算法A与算法B产生的结果的\(NDCG\)。
\[\begin{align} NDCG@5_A &= \frac{DCG_A}{IDCG} = \frac{42.2258}{45.6428} \\&\approx 0.9251 \end{align}\] \[\begin{align} NDCG@5_B &= \frac{DCG_B}{IDCG} = \frac{44.5954}{45.6428} \\&\approx 0.9771 \end{align}\]至此我们使用\(NDCG\)指标衡量了算法A与算法B产生的排序结果的优劣，\(NDCG@5_B > NDCG@5_A\), 故针对口红排序这一次搜索结果，算法B的排序更优，这也与我们对两个排序的肉眼直觉相符合。
实际应用场景中，需要频繁地评判更长更复杂的序列，肉眼无法做出准确的直觉判断，这时候\(NDCG\)能够公平准确的对排序打分。
（由于用户的注意力有限，实际Ranking问题中，我们可能仅仅只关注头部元素的排序，而忽略掉尾部的排序效果，此时使用\(NDCG@i\)表示头部\(i\)个元素的\(NDCG\)值）
3. 总结
\(NDCG\)指标在信息检索、推荐系统的排序任务，相关性任务中有广泛的应用。