Что такое NDCG и как его рассчитать?

NDCG (Normalized Discounted Cumulative Gain)

NDCG - это метрика качества ранжирования, которая оценивает, насколько хорошо система расположила релевантные элементы в верхних позициях списка. Широко используется в поисковых системах, рекомендательных системах и information retrieval.

Интуиция

Пользователь просматривает результаты поиска сверху вниз. Релевантный документ на 1-й позиции ценнее, чем такой же на 10-й. NDCG учитывает и степень релевантности, и позицию в выдаче.

Пошаговый расчет

Шаг 1: Cumulative Gain (CG)

Простая сумма релевантностей без учета позиции:

# relevance scores: [3, 2, 3, 0, 1, 2]
CG = sum([3, 2, 3, 0, 1, 2])  # = 11

Шаг 2: Discounted Cumulative Gain (DCG)

Добавляем штраф за позицию (дисконтирование):

import numpy as np

def dcg(relevances, k=None):
    if k:
        relevances = relevances[:k]
    discounts = np.log2(np.arange(len(relevances)) + 2)  # log2(2), log2(3), ...
    return np.sum(relevances / discounts)

# Формула: DCG = sum(rel_i / log2(i + 1)) для i от 1 до k
relevances = [3, 2, 3, 0, 1, 2]
print(f"DCG = {dcg(relevances):.4f}")
# DCG = 3/1 + 2/1.585 + 3/2 + 0/2.322 + 1/2.585 + 2/2.807 = 7.14

Шаг 3: Ideal DCG (IDCG)

DCG для идеальной сортировки (по убыванию релевантности):

ideal_relevances = sorted(relevances, reverse=True)  # [3, 3, 2, 2, 1, 0]
IDCG = dcg(ideal_relevances)
print(f"IDCG = {IDCG:.4f}")

Шаг 4: NDCG

Нормализация: отношение реального DCG к идеальному:

def ndcg(relevances, k=None):
    actual_dcg = dcg(relevances, k)
    ideal = sorted(relevances, reverse=True)
    ideal_dcg = dcg(ideal, k)
    if ideal_dcg == 0:
        return 0.0
    return actual_dcg / ideal_dcg

score = ndcg(relevances)
print(f"NDCG = {score:.4f}")  # от 0 до 1, где 1 = идеальное ранжирование

NDCG@k

На практике оценивают только top-k позиций:

from sklearn.metrics import ndcg_score

# sklearn ожидает 2D массивы
y_true = np.array([[3, 2, 3, 0, 1, 2]])
y_score = np.array([[0.9, 0.8, 0.7, 0.6, 0.5, 0.4]])

print(f"NDCG@3 = {ndcg_score(y_true, y_score, k=3):.4f}")
print(f"NDCG@5 = {ndcg_score(y_true, y_score, k=5):.4f}")
print(f"NDCG@10 = {ndcg_score(y_true, y_score, k=10):.4f}")

Свойства NDCG

• Диапазон: от 0 до 1 (1 = идеальное ранжирование)
• Учитывает градации релевантности (не бинарная)
• Позиционно-чувствительная: штрафует за релевантные элементы на низких позициях
• Нормализованная: можно сравнивать запросы с разным количеством релевантных документов

Сравнение с другими метриками

Практическое применение

# В рекомендательной системе
def evaluate_recommendations(user_id, model, k=10):
    recommended_items = model.recommend(user_id, n=k)
    true_relevances = [get_true_relevance(user_id, item) for item in recommended_items]
    return ndcg(true_relevances, k=k)

# Средний NDCG по всем пользователям
avg_ndcg = np.mean([evaluate_recommendations(uid, model) for uid in test_users])

Ограничения

• Требует градаций релевантности (не всегда доступны)
• Не учитывает порядок нерелевантных элементов
• Чувствителен к выбору k (NDCG@5 и NDCG@20 могут сильно различаться)
• Предполагает каскадную модель просмотра (сверху вниз)