# nDCG (normalized Discounted Cumulative Gain)

## 1. 개요
**nDCG(normalized Discounted Cumulative Gain)**는 정보 검색(Information Retrieval) 및 추천 시스템에서 검색 결과나 추천 리스트의 품질을 측정하기 위해 사용되는 순위 평가 지표이다. 

단순히 정답 포함 여부만을 따지는 정확도(Accuracy)나 정밀도(Precision)와 달리, nDCG는 **관련성(Relevance)**과 **순위(Rank)**를 동시에 고려한다. 즉, 사용자가 필요로 하는 관련성 높은 아이템이 상위권에 배치될수록 더 높은 점수를 부여하는 방식이다.

---

## 2. 관련성 점수 척도 (Relevance Scale)
nDCG를 계산하기 전, 각 아이템이 쿼리와 얼마나 관련이 있는지를 나타내는 관련성 점수($rel_i$)를 정의해야 한다. 이는 크게 두 가지 방식으로 나뉜다.

*   **이진 관련성 (Binary Relevance):** 아이템이 관련이 있으면 1, 없으면 0으로 표시하는 방식이다. (예: 클릭 여부, 구매 여부)
*   **등급 관련성 (Graded Relevance):** 관련성의 정도를 다단계 척도로 표시하는 방식이다. (예: 0: 관련 없음, 1: 약간 관련, 2: 매우 관련)
    *   nDCG는 특히 이러한 **등급 관련성**을 처리할 수 있다는 점에서 다른 지표(MAP, MRR 등)보다 유연하고 강력하다.

---

## 3. 핵심 원리와 계산 과정
nDCG는 CG $\rightarrow$ DCG $\rightarrow$ IDCG $\rightarrow$ nDCG의 4단계 과정을 거쳐 산출된다.

### 3.1. CG (Cumulative Gain)
CG는 특정 순위까지 나타난 아이템들의 관련성 점수를 단순히 합산한 값이다. 순위를 고려하지 않으므로, 관련성 높은 아이템이 하단에 있어도 점수가 동일하다는 한계가 있다.
$$\text{CG}_p = \sum_{i=1}^{p} rel_i$$

### 3.2. DCG (Discounted Cumulative Gain)
DCG는 순위가 낮아질수록(인덱스 $i$가 커질수록) 관련성 점수에 감쇠 값(Discount)을 곱하여, 상위권에 배치된 아이템에 더 큰 가중치를 부여한다. 일반적으로 로그 함수($\log_2$)를 사용하여 감쇠시킨다.

**DCG의 수식 변형:**
목적에 따라 두 가지 수식이 주로 사용된다.

| 구분 | 수식 | 특징 |
| :--- | :--- | :--- |
| **표준 공식** | $\text{DCG}_p = \sum_{i=1}^{p} \frac{rel_i}{\log_2(i+1)}$ | 관련성 점수 자체를 선형적으로 반영할 때 사용 |
| **강조 공식** | $\text{DCG}_p = \sum_{i=1}^{p} \frac{2^{rel_i} - 1}{\log_2(i+1)}$ | 관련성이 매우 높은 아이템의 가치를 기하급수적으로 높게 평가할 때 사용 (현업에서 더 선호됨) |

**[수식 상세]**
*   **표준 공식:** $\text{DCG}_p = \sum_{i=1}^{p} \frac{rel_i}{\log_2(i+1)}$
*   **강조 공식:** $\text{DCG}_p = \sum_{i=1}^{p} \frac{2^{rel_i} - 1}{\log_2(i+1)}$

### 3.3. IDCG (Ideal DCG)
사용자 쿼리에 대해 가능한 최선의 결과(관련성 점수가 높은 순서대로 정렬된 상태)가 나왔을 때의 DCG 값이다. 이는 각 쿼리마다 다른 최대 가능 점수를 제공하여 정규화의 기준점이 된다.

**※ 예외 처리:** 만약 모든 아이템의 관련성 점수가 0이라면 $\text{IDCG} = 0$이 되며, 이 경우 분모가 0이 되어 계산이 불가능하므로 $\text{nDCG}$는 관례적으로 0으로 정의한다.

### 3.4. nDCG (normalized DCG)
실제 계산된 DCG를 IDCG로 나누어 0과 1 사이의 값으로 정규화한 최종 지표이다.
$$\text{nDCG}_p = \frac{\text{DCG}_p}{\text{IDCG}_p}$$

일반적으로 전체 리스트가 아닌 상위 $k$개의 결과만을 평가하는 **$\text{nDCG}@k$** 형태로 가장 많이 사용된다.

---

## 4. nDCG의 특징 및 장점
nDCG는 다른 순위 평가 지표와 비교했을 때 다음과 같은 차별점을 가진다.

| 비교 항목 | MRR (Mean Reciprocal Rank) | MAP (Mean Average Precision) | nDCG |
| :--- | :--- | :--- | :--- |
| **관련성 척도** | 이진 (Binary) | 이진 (Binary) | **등급 (Graded)** |
| **평가 대상** | 첫 번째 정답의 위치 | 모든 정답의 위치 | **모든 아이템의 관련성** |
| **가중치 적용** | 역수 ($\frac{1}{rank}$) | 순위 기반 평균 | **로그 감쇠 (Log Discount)** |
| **정규화 여부** | 기본적으로 정규화됨 | 기본적으로 정규화됨 | **IDCG를 통한 정규화** |

---

## 5. 실제 적용 예시
**시나리오:** 사용자 쿼리에 대해 3개의 아이템이 추천되었으며, 실제 관련성 점수(0~3점)가 다음과 같다고 가정한다.

*   **추천 결과 순서:** 아이템 A $\rightarrow$ 아이템 B $\rightarrow$ 아이템 C
*   **실제 관련성 점수:** A(1점), B(3점), C(2점)

**단계별 계산 (강조 공식 기준):**

1.  **DCG 계산:**
    *   $i=1: \frac{2^1-1}{\log_2(2)} = \frac{1}{1} = 1.0$
    *   $i=2: \frac{2^3-1}{\log_2(3)} \approx \frac{7}{1.58} \approx 4.43$
    *   $i=3: \frac{2^2-1}{\log_2(4)} = \frac{3}{2} = 1.5$
    *   $\text{DCG} = 1.0 + 4.43 + 1.5 = \mathbf{6.93}$

2.  **IDCG 계산 (최적 순서: B(3) $\rightarrow$ C(2) $\rightarrow$ A(1)):**
    *   $i=1: \frac{2^3-1}{\log_2(2)} = \frac{7}{1} = 7.0$
    *   $i=2: \frac{2^2-1}{\log_2(3)} \approx \frac{3}{1.58} \approx 1.90$
    *   $i=3: \frac{2^1-1}{\log_2(4)} = \frac{1}{2} = 0.5$
    *   $\text{IDCG} = 7.0 + 1.90 + 0.5 = \mathbf{9.40}$

3.  **nDCG 계산:**
    *   $\text{nDCG} = \frac{6.93}{9.40} \approx \mathbf{0.737}$

---

## 6. 실제 서비스 적용 사례 (Case Study)
*   **전자상거래 검색 엔진:** 사용자가 '노트북'을 검색했을 때, 단순 키워드 매칭 상품(관련성 1)보다 실제 노트북 카테고리의 베스트셀러(관련성 3)가 상단에 노출되도록 모델을 튜닝하고 이를 nDCG로 검증한다.
*   **OTT 콘텐츠 추천:** 사용자의 시청 기록을 바탕으로 영화를 추천할 때, '끝까지 시청한 영화'는 3점, '중간에 끈 영화'는 1점, '클릭만 한 영화'는 0점으로 정의하여 추천 리스트의 품질을 평가한다.
*   **법률/의학 전문 검색:** 정답이 하나가 아니라 여러 개의 관련 문서가 존재하며, 문서마다 중요도가 다른 전문 분야에서 검색 결과의 정밀도를 측정하는 핵심 지표로 활용된다.

---

## 7. 한계점 및 고려사항
1.  **관련성 점수의 주관성:** Graded Relevance를 사용할 경우, 점수를 매기는 평가자(Annotator)마다 기준이 달라 데이터의 일관성이 떨어질 수 있다.
2.  **데이터셋 크기 민감도:** 추천 리스트의 길이($p$)를 어떻게 설정하느냐에 따라 값이 크게 변한다. (예: nDCG@5 vs nDCG@10)
3.  **계산 복잡도:** 모든 쿼리에 대해 IDCG를 계산해야 하므로, 단순 정확도 지표보다 계산 비용이 높다.

---

## 8. 구현 가이드
Python의 `scikit-learn` 라이브러리를 사용하면 `ndcg_score` 함수를 통해 간편하게 구현할 수 있다.

```python
from sklearn.metrics import ndcg_score
import numpy as np

# 1. 실제 관련성 점수 (True Relevance)
# - 정답지 역할: 각 아이템이 실제로 얼마나 관련 있는지 정의한 값
# - 2차원 배열 형태여야 함: [[user1_item1, user1_item2, ...]]
true_relevance = np.asarray([[1, 3, 2]])

# 2. 모델이 예측한 점수 (Predicted Scores / Confidence Score)
# - 정렬 기준: 모델이 예측한 '우선순위 점수' (높을수록 상단에 배치됨)
# - 주의: true_relevance와 혼동하여 실제 관련성 점수를 넣지 않도록 주의
scores = np.asarray([[0.5, 0.8, 0.2]])

# nDCG 계산
# k 값을 지정하여 nDCG@k를 계산할 수 있음
n_dcg = ndcg_score(true_relevance, scores, k=3)

print(f"nDCG@3: {n_dcg:.4f}")
# 출력 결과는 위 예시 계산 값(0.737)과 유사하게 산출됨
```