NDCG (Normalized Discounted Cumulative Gain)

• 추천 시스템에서 많이 사용되는 평가지표 중 하나
• 추천의 순서에 가중치를 두어 평가
• 1에 가까울수록 높은 성능
• 수치나 이진값(binary value)에 사용 가능

CG (Cumulative Gain)

• 상위 K개 아이템에 대해 관련도(rel, relevance)를 합한 것

$$ CG_{K} = \sum_{i=1}^{K} rel_{i} $$

DCG (Discounted Cumulative Gain)

• 아이템의 관련도를 순서에 따라 Discount
• 하위 순서로 갈수록 작은 DCG 값을 가지게 됨

$$ DCG_{K} = \sum_{i=1}^{K} \frac {rel_{i}}{log_{2}(i+1)} $$

IDCG (Ideal DCG)

• 이상적인 추천이 일어났을 때의 DCG값
• 가능한 DCG 값 중 가장 큼

$$ IDCG_{K} = \sum_{i=1}^{K} \frac{rel_{i}^{opt}}{log_{2}(i+1)} $$

Normalized DCG

• 추천 결과에 따라 구해진 DCG 를 IDCG 로 나눈 값

$$ NDCG = \frac{DCG}{IDCG} $$

NDCG@5 예시

Item [A, B, C, D, E] 에 대힌 이상적인 결과는

Ideal Order : [B(5), E(4), A(3), C(2), D(1)]

이고 추천 결과가 다음과 같을 때

Recommend Order : [B, C, D, E, A]

DCG 와 IDCG 를 구하면

$$ DCG@5 = \frac{5}{log_{2}(1+1)} + \frac{2}{log_{2}(2+1)} + \frac{1}{log_{2}(3+1)} + \frac{4}{log_{2}(4+1)} + \frac{3}{log_{2}(5+1)} = 9.65$$

$$ IDCG@5 = \frac{5}{log_{2}(1+1)} + \frac{4}{log_{2}(2+1)} + \frac{3}{log_{2}(3+1)} + \frac{2}{log_{2}(4+1)} + \frac{1}{log_{2}(5+1)} = 10.27$$

$$ NDCG@5 = \frac{DCG@5}{IDCG@5} = \frac{9.65}{10.27}=0.94$$