J3Medium★ Core Essential · Industrial BedrockPart J · RecSys & Search Metrics

NDCG@K (Normalized Discounted Cumulative Gain)

⚡Flashcard Drill➔

Evaluate Top-K ranking quality using exponential relevance gains discounted logarithmically by slot position.

⏱️ Time: O(K log K) 理想排序开销
💾 Space: O(K)
🎯 Interactive Self-Practice Loop (Attempt Before Peeking)
Practice in 4 steps: recall mechanism, complete core lines, check edge cases, and log mastery locally.
Step 1 · Mechanism Recall & Stability Self-Check
Step 2 · Complete Key Implementation Lines
import numpy as np
def compute_ndcg_at_k(relevance_scores: list, k: int = 10) -> float:
"""
参数:
relevance_scores: 按推荐/搜索排序给出的真实相关度得分列表 (如 [3, 2, 0, 1])
k: 截断位置
"""
rel = np.asarray(relevance_scores)[:k]
if len(rel) == 0:
return 0.0
# 1. 计算实际预测顺序的 DCG@K
discounts = np.log2(np.arange(len(rel)) + 2) # i=0 时 log2(2)=1.0
gains =
dcg = np.sum(gains / discounts)
# 2. 计算理想完美顺序下的 IDCG@K
ideal_rel = np.sort(np.asarray(relevance_scores))[::-1][:k]
ideal_gains = 2.0 ** ideal_rel - 1.0
ideal_discounts = np.log2(np.arange(len(ideal_rel)) + 2)
idcg = np.sum(ideal_gains / ideal_discounts)
if idcg == 0.0:
return 0.0
return
Step 3 · Verify Boundary Cases & Assertions
Step 4 · Follow-Up Drill & Review Outcome
Q1: How do MRR (Mean Reciprocal Rank) and NDCG@K differ in real search/recommendation use cases?
Next: Confusion Matrix, Precision, Recall & Macro/Micro F1 →
💡

Core Mental Anchor / Mnemonic

Sum (2^rel - 1) / log2(i + 2) for DCG, then divide by sorted ideal IDCG.

📐 Mathematical Derivation & Core Formula

DCG@K=∑i=1K2reli−1log⁡2(i+1),NDCG@K=DCG@KIDCG@K\mathrm{DCG}@K = \sum_{i=1}^K \frac{2^{rel_i} - 1}{\log_2(i + 1)}, \quad \mathrm{NDCG}@K = \frac{\mathrm{DCG}@K}{\mathrm{IDCG}@K}
### Graded Relevance Gain & Logarithmic Position Discount
Ranking metrics weight top positions logarithmically:
- Gain: 2reli−12^{rel_i} - 1 emphasizes highly relevant items;
- Discount: 1/log⁡2(i+1)1 / \log_2(i + 1) reduces weight down the list (i≥1i \ge 1);
- Normalization: Dividing DCG@K\mathrm{DCG}@K by the ideal sorted ceiling IDCG@K\mathrm{IDCG}@K yields NDCG@K∈[0,1]\mathrm{NDCG}@K \in [0, 1] comparable across queries.

🔄 Tensor Dimensions & Shape Flow

relevances -> slice top K -> sum((2^rel - 1)/log2(i+2)) -> DCG / ideal IDCG -> NDCG@K

🛡️ Numerical Stability & Pitfalls Checklist

  • Use log2(rank + 1) with 1-based rank (i + 2 for 0-based indices) so position 0 has denominator log2(2) = 1.
  • Return 0.0 explicitly when IDCG == 0 (no relevant items exist).

💻 Reference Code Implementation

import numpy as np

def compute_ndcg_at_k(relevance_scores: list, k: int = 10) -> float:
    """
    参数:
        relevance_scores: 按推荐/搜索排序给出的真实相关度得分列表 (如 [3, 2, 0, 1])
        k: 截断位置
    """
    rel = np.asarray(relevance_scores)[:k]
    if len(rel) == 0:
        return 0.0
        
    # 1. 计算实际预测顺序的 DCG@K
    discounts = np.log2(np.arange(len(rel)) + 2) # i=0 时 log2(2)=1.0
    gains = 2.0 ** rel - 1.0
    dcg = np.sum(gains / discounts)
    
    # 2. 计算理想完美顺序下的 IDCG@K
    ideal_rel = np.sort(np.asarray(relevance_scores))[::-1][:k]
    ideal_gains = 2.0 ** ideal_rel - 1.0
    ideal_discounts = np.log2(np.arange(len(ideal_rel)) + 2)
    idcg = np.sum(ideal_gains / ideal_discounts)
    
    if idcg == 0.0:
        return 0.0
    return float(dcg / idcg)

🧪 Runnable Assertions & Validation

Copy and run directly in Python / Jupyter:

import numpy as np
# 完美排序
assert compute_ndcg_at_k([3, 2, 1, 0], k=3) == 1.0
# 最差逆序
ndcg_bad = compute_ndcg_at_k([0, 1, 2, 3], k=4)
assert 0.0 < ndcg_bad < 1.0
print("✓ NDCG@K 排名增益评估自测通过")

🎯 Core Follow-up Inquiries & Reference Answers

Q1:How do MRR (Mean Reciprocal Rank) and NDCG@K differ in real search/recommendation use cases?
MRR scores only 1/rank1 / \mathrm{rank} of the first relevant hit, fitting single-answer lookups (e.g., QA or navigational queries), while NDCG evaluates graded relevance across all top-KK slots for exploratory search and feeds.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔
← Prev: AUC-ROC Calculation with Rank Ties HandlingBack to Part J & All 105Next: Confusion Matrix, Precision, Recall & Macro/Micro F1 →