一、ndcg简介
ndcg（Normalized Discounted Cumulative Gain）是一种用来评估排序质量的指标，在信息检索领域被广泛应用。ndcg的计算考虑用户对搜索结果的实际点击情况，是一种较为客观的评价排序结果的方法。
ndcg的计算方法是：首先对搜索结果进行排序，针对每一个搜索结果计算其提供的信息价值，并考虑到搜索结果的排序位置，最后将每个搜索结果的价值进行加权后求和，并除以最理想排序结果所能达到的加权值的和。最终得到的值就是ndcg值。
二、ndcg的计算
ndcg的计算主要包括两个步骤：信息价值计算和加权值计算。
1. 信息价值计算
根据用户的点击情况，可以将每个搜索结果的信息价值分为两类：被用户点击的结果的价值为1，未被点击的结果价值为0。如果搜索结果提供的额外信息对用户的满意度有影响，则将其价值定义为介于0和1之间的小数。
假设搜索结果的信息价值向量为$v=(v_1,v_2,...,v_n)$，则查询$q$的信息价值为：
$$Dcg(q)=\sum_{i=1}^{n} \frac{2^{v_i}-1}{\log_2 (i+1)}$$
其中$log_2(i+1)$是对排序位置的折扣因子，用于表示搜索结果排序越前，提供的信息对用户的贡献越大。
2. 加权值计算
最大可能的信息价值(MPD，Maximum Possible Dcg)是指当搜索结果按照真实的理想排序时，查询结果的$Dcg$值。加权$Dcg$在$MPD$上进行归一化，以此计算$ndcg$。
$$MPD(q)=Dcg(q_{perfect})$$$$Ndcg(q)=\frac{Dcg(q)}{MPD(q)}$$
三、ndcg在排序算法中的应用
在排序算法中，常用的指标是Precision、Recall等。但是这些指标只考虑了搜索结果的排名，无法反映搜索结果的实际价值。ndcg则是一种可以考虑搜索结果实际质量的指标。
下面以SVM Rank算法为例，来介绍ndcg在排序算法中的应用。
1. SVM Rank算法
SVM Rank是一种机器学习算法，用于排序问题。它的基本原理是将排序视为一种学习问题，通过训练来学习权重向量。SVM Rank使用的是支持向量机算法，可以有效控制模型复杂度。
2. ndcg在SVM Rank中的应用
在SVM Rank算法中，通过使用训练数据集和目标函数，可以得到权重向量。使用训练数据集训练出的模型，可以对测试数据集进行排序，同时计算测试数据集的ndcg值。通过对不同权重向量进行计算，可以得到最优的权重向量，从而得到最好的排序结果。
// SVM Rank中的ndcg计算示例代码
int compute_ndcg(InputData &input, Vector &weights) {
int n = input.size();
double score[n+1];
for (int i = 0; i < n; i++) {
score[i] = dot_product(input[i].features, weights);
}
sort(input.begin(), input.end(), ScoreCmp(score));
vector v;
for (int i = 0; i < n; i++) {
if (input[i].click) {
v.push_back(input[i].relevance);
}
}
double dcg = 0;
for (int i = 0; i < (int)v.size(); i++) {
dcg += (pow(2.0, v[i])-1)/log2(i+2);
}
double max_dcg = 0;
sort(v.begin(), v.end(), greater
());
for (int i = 0; i < (int)v.size(); i++) {
max_dcg += (pow(2.0, v[i])-1)/log2(i+2);
}
return (int)(dcg/max_dcg*100);
}
四、ndcg的局限性
ndcg虽然是一种较为客观的排序质量评价方法，但是在某些情况下也存在一些局限性。例如，当搜索结果数目较少时，ndcg无法精确地反映搜索结果的排序效果。此外，ndcg也比较容易被一些优化手段所欺骗。因此，在实际应用中，需要根据具体情况进行选择。
五、总结
ndcg是一种用来评估排序质量的指标，可以反映搜索结果的实际价值。在排序算法中，ndcg常被用来衡量算法的排序效果。但是在实际应用中，ndcg也存在一些局限性，需要根据具体情况进行选择。
