Problems

1 / 1

NDCG (Normalized Discounted Cumulative Gain)

Recommender SystemsMetrics & Evaluation

Medium

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

\text{DCG}@k = \sum_{i=1}^{k} \frac{2^{rel_i} - 1}{\log_2(i + 1)}

The ideal DCG (IDCG@k) is the DCG of the best possible ranking, obtained by sorting relevance scores in descending order.

\text{NDCG}@k = \frac{\text{DCG}@k}{\text{IDCG}@k}

If 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.

Loading visualization...

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

Try Similar Problems

Hit Rate At K Precision Recall At K Mean Average Precision Top K Recommendations Catalog Coverage

Prev Next

NDCG (Normalized Discounted Cumulative Gain)

Recommender SystemsMetrics & Evaluation

Medium

Given a list of relevance scores (in the order your system ranked them) and a cutoff k, compute NDCG@k.

Formula

\text{DCG}@k = \sum_{i=1}^{k} \frac{2^{rel_i} - 1}{\log_2(i + 1)}

The ideal DCG (IDCG@k) is the DCG of the best possible ranking, obtained by sorting relevance scores in descending order.

\text{NDCG}@k = \frac{\text{DCG}@k}{\text{IDCG}@k}

If 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.

Loading visualization...

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

Try Similar Problems

Hit Rate At K Precision Recall At K Mean Average Precision Top K Recommendations Catalog Coverage

Case 1

Case 2

relevance_scores =

Accepts: array

k =

Accepts: number

Given a list of relevance scores (in the order your system ranked them) and a cutoff k, compute NDCG@k.

Formula

\text{DCG}@k = \sum_{i=1}^{k} \frac{2^{rel_i} - 1}{\log_2(i + 1)}

The ideal DCG (IDCG@k) is the DCG of the best possible ranking, obtained by sorting relevance scores in descending order.

\text{NDCG}@k = \frac{\text{DCG}@k}{\text{IDCG}@k}

If 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.