# nDCG(Normalized Discounted Cumulative Gain)

Normalized Discounted Cumulative Gain：一种对搜索引擎或相关程序有效性的度量。

2个假设：

​ 1.强相关的文档应该出现在结果列表前面，且越靠前（rank越高）越有用。

​ 2.强相关文档比弱相关文档有用，比不相关文档有用。

$DCG$来源于一个更早的、更基础的方法—$CG$。

## CG

$CG$不考虑结果集中的序信息，单纯把分级相关度相加。前个$P$个位置的$CG$值是：

$$CG_p = \sum\limits_{i=1}^{p}{rel_i}$$

$rel_i$是搜索结果列表的位置$i$处结果的分级相关度。

## DCG

$DCG$取代$CG$作为一个更准确的测量方法。

$$DCG_p = rel_1 + \sum_{i=2}^{p}\frac {rel_i}{log_2 i}$$

$$DCG_p = \sum_{i=1}^{p} \frac{2^{rel_i}-1}{log_2(1+i)}$$

## nDCG

$$nDCG_p =\frac{DCG_p}{IDCG_p}$$

$IDCGp$（Ideal DCG）是在一个完美的排序下，$p$所具有的最大$DCG$值

$$CG_6=\sum_{i=1}^6 rel_i = 3+2+3+0+1+2=11$$

$i$ $rel_i$ $\log _{2}(i+1)$ $\frac {rel_{i}}{\log _{2}(i+1)}$
1 3 1 3
2 2 1.585 1.262
3 3 2 1.5
4 0 2.322 0
5 1 2.585 0.387
6 2 2.807 0.712

$${DCG_{6}} =\sum _{i=1}^{6}{\frac {rel_{i}}{\log _{2}(i+1)}}=3+1.262+1.5+0+0.387+0.712=6.861$$

\begin {aligned} &IDCG_{6} =8.740 \\ \\ & nDCG_{6} ={\frac {DCG_{6}}{IDCG_{6}}}={\frac {6.861}{8.740}}=0.785 \\ \end {aligned}

$nDCG$的缺点是：当排序的数很少（比如：只有1-3个），那么任何排序的$nDCG$值都比较接近，所以可以考虑使用AUC（area under the ROC curve）。

note: 当 ideal_dcg = 0 时, 我见过两种处理方法:

1. nDCG sum += 0, query count += 1;
2. nDCG sum += 0, query count += 0, 即抛弃该query, tf_ranking 采用的是该方案.

# RR（reciprocal rank）

RR（reciprocal rank）倒数排名，指检索结果中第一个相关文档的排名的倒数。
$$RR = \frac 1 {rank_i}$$

## MRR(Mean Reciprocal Rank)

MRR的核心思想很简单：返回的结果集的优劣，跟第一个正确答案的位置有关，第一个正确答案越靠前，结果越好。MRR为所有query的RR的平均值。

$$MRR = \frac1 {\left| Q \right|}\sum_{i = 1}^{\left| Q \right|} \frac 1 {rank_i}$$

## 例子

$$MRR = \frac14(\frac13+\frac11+\frac15+0 )=0.383$$

## ERR（Expected reciprocal rank）

$$P(C_i) = r_i \prod_{j=1}^{i-1} (1 - r_j)$$

ERR (倒数排名的期望)，表示用户的需求被满足时停止的位置的倒数的期望，与 MRR 计算第一个相关文档的位置倒数不同。

$$P_r = R_r \prod_{i=1}^{r-1}(1 - R_i)$$

$$R_i = \frac {2^{l_i} - 1}{2^{l_m}}$$
$l_m$表示相关性评分最高的一档。$l_i$ 表示样本中第$i$ 个结果的相关度标记。

ERR 的计算公式如下：

$$ERR = \sum_{r} \frac1r P_r = \sum_{r} \frac1r R_r \prod_{i=1}^{r-1}(1 - R_i)$$

# MAP(mean average precision)

## Precision

Precision is the fraction of the documents retrieved that are relevant to the user’s information need.

$$precision = \frac {\left| {\{ relevant\;documents\} \cap \{ retrieved\;documents\} } \right|} {\left| {\left\{ {retieved\;documents} \right\}} \right|}$$

Precision takes all retrieved documents into account. It can also be evaluated at a given cut-off rank, considering only the topmost results returned by the system. This measure is called precision at n or P@n.

## Average precision

Precision and recall are single-value metrics based on the whole list of documents returned by the system. For systems that return a ranked sequence of documents, it is desirable to also consider the order in which the returned documents are presented. By computing a precision and recall at every position in the ranked sequence of documents, one can plot a precision-recall curve, plotting precision $p(r)$ as a function of recall $r$. Average precision computes the average value of $p(r)$ over the interval from $r=0$ to $r=1$

$$AveP=\int_0^1p\left(r\right)dr$$

That is the area under the precision-recall curve. This integral is in practice replaced with a finite sum over every position in the ranked sequence of documents:

$$AveP = \sum _{k=1}^n{P\left(k\right)}\Delta{r\left(k\right)}$$

where $k$ is the order in the sequence of retrieved documents, $n$ is the number of retrieved documents, $P(k)$ is the precision at cut-off $k$ in the list, and $\Delta r(k)$is the change in recall from items $k-1$ to $k$.

This finite sum is equivalent to:

$${AveP} = \frac{\sum_{k=1}^n (P(k) \times {rel}(k))}{number\; of\; relevant \;documents}$$

where ${rel} (k)$ is an indicator function equaling 1 if the item at k is a relevant document, zero otherwise. Note that the average is over all relevant documents and the relevant documents not retrieved get a precision score of zero.

## Mean average precision

Mean average precision for a set of queries is the mean of the average precision scores for each query.

$$MAP=\frac{\sum_{q=1}^Q{AveP(q)}}{Q}$$

where Q is the number of queries.

# 参考

http://en.wikipedia.org/wiki/Discounted_cumulative_gain