NDCG (Normalized Discounted Cumulative Gain)
NDCG (Normalized Discounted Cumulative Gain)
When ranking search results or recommendations, not all positions are equally valuable. A relevant item at position 1 is far more useful than one buried at position 10. NDCG captures this by discounting relevance based on position and normalizing against the ideal ranking.
Given a list of relevance scores (in the order your system ranked them) and a cutoff k, compute NDCG@k.
Formula
DCG@k=i=1∑klog2(i+1)2reli−1The ideal DCG (IDCG@k) is the DCG of the best possible ranking, obtained by sorting relevance scores in descending order.
NDCG@k=IDCG@kDCG@kIf IDCG@k is zero (all relevance scores are zero), return 0.0.
If k is larger than the number of items, use all available items.
Return the NDCG score as a float.
Examples
Input:
relevance_scores = [3, 2, 1, 0] k = 4
Output:
1.0
The items are already in ideal order (highest relevance first), so DCG equals IDCG.
Input:
relevance_scores = [0, 1, 2, 3] k = 4
Output:
0.5479...
The ranking is reversed. The most relevant item is at the last position, so DCG is much lower than IDCG.
Hint 1
The ideal ranking is just the relevance scores sorted in descending order.
Hint 2
Be careful with the position indexing in the discount factor. The first position should have a discount of 1.
Requirements
- Use the exponential gain formula: gain = 2^rel - 1
- Discount using log base 2 of (position + 1), where positions are 1-indexed
- Normalize by the ideal DCG computed from the optimal ranking
- Handle the edge case where all relevance scores are zero
Constraints
- 1 <= len(relevance_scores) <= 10000
- 0 <= relevance_scores[i] <= 10
- 1 <= k <= 10000
- Relevance scores are non-negative integers
- Time limit: 300 ms
Log in to take notes on this problem
Accepts: array
Accepts: number
NDCG (Normalized Discounted Cumulative Gain)
NDCG (Normalized Discounted Cumulative Gain)
When ranking search results or recommendations, not all positions are equally valuable. A relevant item at position 1 is far more useful than one buried at position 10. NDCG captures this by discounting relevance based on position and normalizing against the ideal ranking.
Given a list of relevance scores (in the order your system ranked them) and a cutoff k, compute NDCG@k.
Formula
DCG@k=i=1∑klog2(i+1)2reli−1The ideal DCG (IDCG@k) is the DCG of the best possible ranking, obtained by sorting relevance scores in descending order.
NDCG@k=IDCG@kDCG@kIf IDCG@k is zero (all relevance scores are zero), return 0.0.
If k is larger than the number of items, use all available items.
Return the NDCG score as a float.
Examples
Input:
relevance_scores = [3, 2, 1, 0] k = 4
Output:
1.0
The items are already in ideal order (highest relevance first), so DCG equals IDCG.
Input:
relevance_scores = [0, 1, 2, 3] k = 4
Output:
0.5479...
The ranking is reversed. The most relevant item is at the last position, so DCG is much lower than IDCG.
Hint 1
The ideal ranking is just the relevance scores sorted in descending order.
Hint 2
Be careful with the position indexing in the discount factor. The first position should have a discount of 1.
Requirements
- Use the exponential gain formula: gain = 2^rel - 1
- Discount using log base 2 of (position + 1), where positions are 1-indexed
- Normalize by the ideal DCG computed from the optimal ranking
- Handle the edge case where all relevance scores are zero
Constraints
- 1 <= len(relevance_scores) <= 10000
- 0 <= relevance_scores[i] <= 10
- 1 <= k <= 10000
- Relevance scores are non-negative integers
- Time limit: 300 ms
Log in to take notes on this problem
Accepts: array
Accepts: number