추천 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_i는 i번째 위치의 관련성 점수
DCG (Discounted Cumulative Gain)
- Discounted Cumulative Gain은 각 위치의 점수를 할인하여 계산
- 위치가 낮을수록 중요도가 줄어드는 것을 반영
DCG는 다음과 같이 계산
\[
DCG_p = \sum_{i=1}^{p} \frac{rel_i}{\log_2(i+1)}
\]
여기서$log2(i+1)\log_2(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으로, 결과가 완벽하게 정렬된 상태