추천 Ranking 알고리즘 관련 metric :: NDCG

NDCG (Normalized Discounted Cumulative Gain)

- 정보 검색 시스템과 추천 시스템의 성과를 평가하는 데 있어, 단순히 클릭 수나 정확도만으로는 충분하지 않음

- 사용자에게 제공되는 결과의 랭킹도 중요

- NDCG (Normalized Discounted Cumulative Gain)는 이러한 랭킹의 품질을 평가하는 데 유용한 메트릭

- NDCG는 검색 결과나 추천 목록에서 항목이 어떻게 랭킹되는지를 측정

- 이 메트릭은 정확성과 랭킹 품질을 동시에 고려하며, 높은 순위에 더 많은 가중치를 부여

Cumulative Gain (CG): 각 위치의 점수를 합산하여 얻은 총 점수.

Discounted Cumulative Gain (DCG): 위치가 높을수록 중요도가 낮아지므로, 점수를 할인하여 계산

Normalized Discounted Cumulative Gain (NDCG): DCG 값을 이상적인 최대 DCG 값으로 정규화하여 0과 1 사이의 값으로 표현

 

 

CG (Cumulative Gain)

- Cumulative Gain은 랭킹의 각 위치에서 얻은 점수의 합산

- 예를 들어, 검색 결과에서 각 문서가 얼마나 유용한지를 평가

- CG는 단순히 랭킹된 목록의 점수를 모두 합산하여 계산

$$CG_p = \sum_{i=1}^{p} rel_i$$

여기서 relirel_ireli​는 i번째 위치의 관련성 점수

 

DCG (Discounted Cumulative Gain)

- Discounted Cumulative Gain은 각 위치의 점수를 할인하여 계산

- 위치가 낮을수록 중요도가 줄어드는 것을 반영

DCG는 다음과 같이 계산

$$DCG_p = \sum_{i=1}^{p} \frac{rel_i}{\log_2(i+1)}$$

​​

여기서$log⁡2(i+1)\log_2(i+1)log2​(i+1)$ 는 i번째 위치의 할인 계수

- 할인 계수는 위치가 높을수록 점수가 감소

 

NDCG (Normalized Discounted Cumulative Gain)

- NDCG는 DCG 값을 이상적인 DCG (IDCG)로 정규화하여 계산

- 이상적인 DCG는 주어진 쿼리에 대해 가능한 최고의 랭킹을 가정하여 계산된 DCG

- 이를 통해 평가 결과를 0과 1 사이로 정규화

Ideal Discounted Cumulative Gain (IDCG)
$$IDCG_p = \sum_{i=1}^{p} \frac{rel_{(i)}}{\log_2(i+1)}$$

 

Normalized Discounted Cumulative Gain (NDCG)
$$NDCG_p = \frac{DCG_p}{IDCG_p}$$

​​

NDCG의 중요성

NDCG는 검색 시스템과 추천 알고리즘의 성과를 평가하는 데 매우 유용합니다. 높은 NDCG 값은 검색 결과나 추천 목록이 사용자에게 매우 유용하다는 것을 의미합니다. 또한, NDCG는 랭킹된 결과의 품질을 직접적으로 평가할 수 있기 때문에 실용적인 기준을 제공합니다.

 

NDCG 계산 예제

간단한 예를 통해 NDCG 계산 과정을 살펴보겠습니다.

순위 1: 관련성 점수 3

순위 2: 관련성 점수 2

순위 3: 관련성 점수 1

 

DCG 계산
$$DCG_3 = \frac{3}{\log_2(1+1)} + \frac{2}{\log_2(2+1)} + \frac{1}{\log_2(3+1)} = \frac{3}{\log_2(2)} + \frac{2}{\log_2(3)} + \frac{1}{\log_2(4)} = 3 + 1.0 + 0.5 = 4.5$$

IDCG 계산 (최적 순서가 3, 2, 1일 경우)
$$IDCG_3 = \frac{3}{\log_2(1+1)} + \frac{2}{\log_2(2+1)} + \frac{1}{\log_2(3+1)} = \frac{3}{\log_2(2)} + \frac{2}{\log_2(3)} + \frac{1}{\log_2(4)} = 3 + 1.0 + 0.5 = 4.5$$

NDCG 계산
$$NDCG_3 = \frac{DCG_3}{IDCG_3} = \frac{4.5}{4.5} = 1.0$$

결과 설명
NDCG가 1.0으로, 결과가 완벽하게 정렬된 상태