NDCG at K

Compute normalised discounted cumulative gain at k.

Precision at k treats every relevant item the same and ignores where in the top k it appears. NDCG does neither. Items can have graded relevance, and an item counts for less the lower it is ranked:

DCG@k  = sum_{i=1..k} rel_i / log2(i + 1)
IDCG@k = DCG@k of the same relevances sorted from high to low
NDCG@k = DCG@k / IDCG@k

rel_i is the relevance of the item at rank i (the first item has rank 1). The ideal ordering gives NDCG = 1, so scores for different users can be averaged.

Function signature

def ndcg_at_k(relevances, k):

Example

Input

ndcg_at_k([2, 0, 3, 1], k=3)

Output

0.73500699

Reasoning

DCG = 2 / log2(2) + 0 / log2(3) + 3 / log2(4) = 2 + 0 + 1.5 = 3.5. The ideal order is 3, 2, 1, so IDCG = 3 + 2 / 1.585 + 1 / 2 = 4.762. NDCG = 3.5 / 4.762 = 0.735. Putting the best item third cost about a quarter of the score.

Constraints and notes

• relevances lists the relevance of each recommended item in rank order.
• Build the ideal ranking from all of relevances, then take its top k.
• If IDCG is 0 (nothing relevant), return 0.0.
• If there are fewer than k items, use all of them.