NDCG (Normalized Discounted Cumulative Gain)

NDCG는 랭킹 추천 시스템에서 많이 사용되는 평가 지표로, 기존 정보 검색에서 널리 사용되던 지표이다. 이 지표는 랭킹 리스트의 정확성을 평가하며, 특히 더 관심 있거나 관련성이 높은 아이템을 얼마나 잘 포함하고 있는지 평가한다. 예를 들어, 검색창에 10개의 아이템이 나타났을 때, 그 중 1, 3, 5, 7번 아이템이 관심 있는 아이템이라면 이를 바탕으로 랭킹이 제대로 매겨졌는지 평가하는 것이다.

NDCG는 단순한 랭킹이 아닌 데이터의 성향을 반영하기 위한 평가 지표로, 추천 시스템이 사용자에게 얼마나 정확한 순서로 아이템을 추천하는지를 평가한다. 이 지표는 기존의 MAP(Mean Average Precision), Top-K Precision/Recall 등의 평가 방법을 보완한다. 또한, NDCG는 기존 정보 검색에서 많이 사용되었으며, 특히 상위 랭킹 리스트가 하위 랭킹 리스트보다 확연하게 중요한 도메인에서 유용한 평가 기준이 된다. 예를 들어, TV나 영화 프로그램을 랭킹 순으로 추천해주는 도메인에서 매우 유용하다.

NDCG를 통해 추천 시스템의 성능을 효과적으로 평가하고, 사용자에게 더 나은 추천을 제공할 수 있다.

NDCG 구성 요소

CG (Cumulative Gain)

상위 p개의 아이템의 관련성을 합한 값이다. 각 아이템의 관련성(rel_i)은 binary(관련 여부) 또는 complex value(문제에 따라 세분화된 값)로 표현된다.

DCG (Discounted Cumulative Gain)

각 아이템의 관련성에 log normalization을 적용한 값이다. 상위 아이템에 더 높은 가중치를 부여하며, 하위 아이템일수록 가중치가 줄어드는 방식으로 관련성을 계산한다.

NDCG (Normalized DCG)

이상적인 DCG(Ideal DCG)를 계산하여 최종 NDCG를 도출한다. IDCG는 전체 p개의 결과 중 가질 수 있는 가장 큰 DCG 값이다.

NDCG 예시

예제에서는 4개의 문서(d1, d2, d3, d4)에 대한 관련성 점수(r_i)와 두 개의 랭킹 함수(Ranking Function1, Ranking Function2)를 사용하여 NDCG를 계산하는 과정을 설명한다.

각 컬럼의 의미

1. Ground Truth:
   Document Order: 문서의 순서(d4, d3, d2, d1).
   r_i: 각 문서의 관련성 점수(2, 2, 1, 0).

2. Ranking Function1:
   Document Order: 문서의 순서(d3, d4, d2, d1).
   r_i: 각 문서의 관련성 점수(2, 2, 1, 0).

3. Ranking Function2:
   Document Order: 문서의 순서(d3, d2, d4, d1).
   r_i: 각 문서의 관련성 점수(2, 1, 2, 0).

해석

Ground Truth와 Ranking Function1은 동일한 순서로 문서를 정렬했기 때문에 NDCG 값이 1.00이다.
Ranking Function2는 Ground Truth와 다르게 문서를 정렬했기 때문에 NDCG 값이 0.9203으로, Ground Truth보다 낮은 값을 가진다.
NDCG 값은 0에서 1 사이의 값을 가지며, 1에 가까울수록 이상적인 랭킹과 가까움을 나타낸다.

장점

1. 랭킹의 순서 반영
NDCG는 문서나 아이템의 랭킹 순서를 고려하여 평가한다. 상위에 위치한 항목이 더 높은 가중치를 받기 때문에, 사용자가 더 관심을 가질 만한 아이템이 상위에 있을수록 높은 점수를 받는다.
2. 상위 랭킹의 중요도 반영
NDCG는 상위 랭킹의 중요도를 반영한다. 상위에 위치한 아이템이 더 중요하다고 가정하고, 순위가 낮아질수록 가중치가 감소한다. 이를 통해 중요한 항목이 상위에 위치하도록 평가할 수 있다.
3. 다양한 관련성 값 지원
NDCG는 아이템의 관련성을 binary 값(관련 있음/없음)뿐만 아니라 연속적인 값으로도 표현할 수 있다. 이를 통해 관련성의 정도를 세분화하여 평가할 수 있다.
4. 정규화된 점수
NDCG는 0과 1 사이의 값을 가지며, 1에 가까울수록 이상적인 랭킹과 가까움을 나타낸다. 이는 결과를 직관적으로 이해하고 비교하는 데 도움이 된다.
5. 다양한 도메인에 적용 가능
NDCG는 검색 엔진뿐만 아니라 추천 시스템, 광고, 영화 추천 등 다양한 도메인에 적용할 수 있다.

단점

1. 계산의 복잡성
NDCG는 DCG와 IDCG를 계산하는 과정이 포함되어 있어 계산이 다소 복잡할 수 있다. 특히 대규모 데이터셋에서는 계산 비용이 증가할 수 있다.
2. 이상적인 DCG(IDCG) 계산 필요
NDCG를 계산하기 위해서는 이상적인 DCG(IDCG)를 계산해야 한다. 이는 모든 쿼리나 추천에 대해 최상의 순위를 가정하고 계산해야 하기 때문에 추가적인 계산이 필요하다.
3. 부분적인 평가
NDCG는 특정 쿼리나 추천 세트에서의 순위에 중점을 둔다. 전체 시스템의 전반적인 성능을 평가하기 위해서는 다른 지표와 함께 사용해야 한다.
4. 해석의 복잡성
NDCG 값이 0에서 1 사이의 값을 가지지만, 그 차이가 정확히 어떤 의미를 갖는지 해석하기 어려울 수 있다. 예를 들어, 0.85와 0.90의 차이가 실제로 얼마나 중요한 차이인지를 해석하기 어려울 수 있다.

결론

NDCG는 랭킹 시스템의 성능을 평가하는 데 매우 유용한 지표로, 특히 상위 랭킹의 중요성을 반영하고 다양한 관련성 값을 지원하는 장점이 있다. 그러나 계산의 복잡성, 이상적인 DCG 계산의 필요성, 부분적인 평가 및 해석의 복잡성 등의 단점도 있다. 이러한 장단점을 고려하여 NDCG를 다른 지표와 함께 사용하면, 시스템의 성능을 더 정확하게 평가할 수 있다.

정리

1. NDCG는 0~1 사이의 값을 가지며, 1에 가까울수록 우수한 추천 시스템이다.
2. 랭킹에 민감한 추천 서비스의 경우 유용한 평가지표이다.
3. 연속형 변수뿐만 아니라, Binary 변수 데이터에도 계산 가능하다.
4. 상위 랭킹의 중요성을 반영하고 다양한 관련성 값을 지원하는 장점이 있다.
5. 계산의 복잡성, 이상적인 DCG 계산의 필요성, 부분적인 평가 및 해석의 복잡성 등의 단점이 있다.