[추천시스템 평가지표 5. DCG, NDCG와 Mean NDCG

추천 시스템 평가지표 5. DCG

Intro

“추천으로 맞춘 정답이 얼마나 관련도 높은 정답인가?”

지금까지 살펴본 Precision, Recall, RR, AP는 모두 정답 여부(binary)를 기준으로 추천 품질을 평가하는 지표들이었습니다. 하지만 실제 서비스에서는 아래와 같은 질문이 자연스럽게 등장할 수 있습니다.

맞았다/틀렸다가 아니라, 추천 대상자와 “더 관련도이 높은” 아이템을 추천했는가?
어떤 아이템은 관련도이 크고, 어떤 아이템은 작다면, 추천 품질을 어떻게 평가해야 하는가?
별점과 같은 사용자의 선호도를 반영한 추천 평가 지표가 있을까?

이러한 요구들을 반영해 사용할 수 있는 지표가 바로 DCG 와 NDCG 입니다.

개념

DCG는 관련도 점수(relevance)와 추천 순위(rank)를 고려해 추천 결과의 랭킹 품질을 누적 점수로 평가하는 지표입니다. 즉, 정답이 추천 목록에 얼마나 빨리 등장했는가도 평가하지만, 추천된 아이템이 실제 사용자와 얼마나 관련도가 높은지도 함께 평가하는 지표입니다.

Discounted Cumulative Gain

Discount : 랭킹의 위치가 내려갈수록 기여도를 줄이기 때문에 Discount
Cumulative : 누적. 각 추천 아이템에 대해 계산한 세부항을 누적합으로 더해간다.
Gain : 이익. 추천된 아이템과 추천 대상과의 관련도 점수가 높을 수록 지표상 이득을 보므로 Gain

관련도	예시
사람의 선호도	0:무관, 1:조금관련, 2:관련, 3:매우관련, 4:완벽매칭
이진 값	0:불일치, 1:일치
질의-문서 일치율	0~1 사이의 실수값

CG - Cumulative Gain

누적 이익

DCG를 살펴보기 전에, 먼저 CG부터 살펴보겠습니다. CG는 추천 리스트의 상위 K개에 대해 아이템의 관련도 점수를 단순 합산한 것입니다. 즉, 정답이 어디에 있든 관련도 합이 같다면, 같은 점수로 평가됩니다. 수식으로 표현하면 아래와 같습니다.

\[CG_{k} = \sum_{i=1}^{k}rel_{i}\]

추천 리스트 상위 k개 아이템의 관련도 점수를 단순 합산
추천 순서(랭킹) 정보는 반영하지 않음

DCG - Discounted Cumulative Gain

감소된 누적 이익

앞서 살펴본 CG에 관련도 높은 정답 아이템이 얼마나 앞에 등장하는지를 포함해 평가하는 것이 바로 DCG 입니다. CG가 가지고 있는, 추천 순서에 대한 평가를 하지 못한다는 한계를 보완한 것입니다.

DCG는 순위를 분모로, 관련도 점수를 분자로 하여 순위가 내려갈수록 관련도 점수의 기여도가 적어집니다. 이를 통해 DCG는 같은 관련도라면, 앞에 등장할수록 더 중요하다라는 추천 순위 품질의 기본 가정을 반영합니다.

\[DCG@K = \sum_{i=1}^{k}{\frac{rel_{i}}{log_{2}(i+1)}}\]

순위 $i$가 내려갈수록 분모가 커짐
즉, 뒤에 등장한 아이템일수록 기여도가 감소

Exponential Gain DCG

추가적으로, 관련도 점수를 비선형적으로 증폭시키는 경우도 있습니다. Exponential Gain DCG는 관련도 점수를 2의 지수로 하여, 관련도가 높을수록 평가점수가 비선형적으로 증가하게 합니다. 즉, 상위의 관련도 높은 아이템의 중요도를 강조하는 것입니다.

\[Exponential \, Gain \, DCG@K = \sum_{i=1}^{k}{\frac{2^{rel_{i}}-1}{log_{2}(i+1)}}\]

특징

DCG는 아래와 같은 특징을 가지고 있습니다.

랭킹의 위치를 고려한다.
정답과 추천 아이템의 관련도을 고려한다.
관련도의 평가 기준이 다양하다. (0~5 정수, 0~1실수, 0 or 1 등)

사용하는 경우

DCG는 다음과 같은 경우에 적합합니다.

랭킹의 위치가 중요한 경우
추천 아이템의 관련도과 추천 순서가 중요한 경우
e.g. 검색, 컨텐츠 추천, 상품 추천 등 노출 순위가 곧 성과로 이어지는 서비스

수식

\[DCG@K = \sum_{i=1}^{k}{\frac{rel_{i}}{log_{2}(i+1)}}\\ 또는\\ Exponential \, Gain \, DCG@K = \sum_{i=1}^{k}{\frac{2^{rel_{i}}-1}{log_{2}(i+1)}}\]

$rel_{i}$ : i번째 아이템의 관련도 점수
$i$ : 아이템의 순서
$k$ : 추천 목록의 길이

즉, 추천 아이템의 관련도이 높을수록 지표에 대한 기여도가 높아지며(gain)
추천 아이템의 순위가 낮아질수록 지표에 대한 기여도가 낮아짐(discount)
그리고 gain과 discount를 적용한 세부 계산항을 누적함(cumulative)

코드

predict_list = ["A", "B", "C"]
ground_truth = {"A":0.1, "B":0.5, "C":0.7, "D":0.5, "E":0.1}

import math

def calc_dcg(relevance_scores, k:int=None) -> float:
    if k is None:
        k = len(relevance_scores)
    relevance_scores_k = relevance_scores[:k]
    dcg = sum(score / (math.log2(i+1+1)) for i, score in enumerate(relevance_scores_k))
    return dcg

relevance_scores = [ground_truth.get(item, 0.0) for item in predict_list]
calc_dcg(relevance_scores)

# >> 0.7654648767857287

IDCG

개념

이상적인 DCG 값

IDCG(Ideal Discounted Cumulative Gain)은 이론적으로 가능한 최고의 DCG 값 입니다. 즉, 완벽한 추천이 수행되었을 때 얻을 수 있는 DCG 값입니다. IDCG는 정답 아이템(사용자가 실제로 선호한 아이템)들의 관련도 점수를 내림차순으로 정렬한 뒤, 이들에 대한 DCG를 계산하여 얻을 수 있습니다.

정답 아이템의 관련도 점수를 내림차순으로 정렬
이들의 DCG 값을 계싼

수식

\[IDCG@K = \sum_{i=1}^{k}{\frac{rel_{i}}{log_{2}{(i+1)}}}\]

기본적으로 수식은 DCG와 동일
다만, 계산되는 “데이터”가 이상적인 순서로 정렬된 관련도 점수이다.

예시

관련도 점수 : [3, 2, 2, 1]
이상적 추천 : [3, 2, 2, 1]

\[IDCG@4 = \frac{3}{log_{2}{(2)}} + \frac{2}{log_{2}{(3)}} + \frac{2}{log_{2}{(4)}} + \frac{1}{log_{2}{(5)}} = 5.6925...\]

특징

항상 DCG는 0보다 크거나 같으며, IDCG는 DCG보다 크거나 같다.
단, 관련도 정보가 없거나, 관련도 점수가 모두 0이라면 IDCG = 0이다.

코드

predict_list = ["A", "B", "C"]
ground_truth = {"A":0.1, "B":0.5, "C":0.7, "D":0.5, "E":0.1}

import math

def calc_dcg(relevance_scores, k:int=None) -> float:
    if k is None:
        k = len(relevance_scores)
    relevance_scores_k = relevance_scores[:k]
    dcg = sum(score / (math.log2(i+1+1)) for i, score in enumerate(relevance_scores_k))
    return dcg

def calc_idcg(ground_truth, k:int=None) -> float:
    if len(ground_truth) == 0:
        return 0.0
    ideal_relevance_scores = sorted(ground_truth.values(), reverse=True)
    idcg = calc_dcg(ideal_relevance_scores, k)
    return idcg

calc_idcg(ground_truth)
# >> 1.3472178133165222

DCG 와 IDCG 점수 비교

predict_list = ["A", "B", "C"]
ground_truth = {"A":0.1, "B":0.5, "C":0.7, "D":0.5, "E":0.1}

# DCG  : 0.7654648767857287
# IDCG : 1.3472178133165222

NDCG

개념

최선의 DCG에 대비해 몇% 수준의 DCG 점수를 보이는가

앞서 살펴본 DCG는, 절대값이기 때문에 케이스간 비교가 어렵습니다. 예를 들어 추천시스템 A에서는 0~10 사이의 값을 가지는데, 추천시스템 B에서는 100~200 사이의 값을 가질 수도 있습니다. 또한 동일한 추천시스템에서도 사용자에 따라 각기 다른 DCG 평가값을 가질 수 있습니다.

이러한 간극을 해결하고, 서로 다른 스케일을 가진 추천시스템 간의 비교평가를 하기 위해 DCG 값을 최선의 DCG(IDCG) 값으로 나눈 게 바로 NDCG 입니다.

Normalized Discounted Cumulative Gain

특징

값의 범위 : 0~1
DCG의 값을 IDCG로 정규화하여, 추천 결과가 최선 대비 몇%의 수준인지를 평가할 수 있다.
1에 가까울수록 이상적인 랭킹에 가깝다.
서로 다른 모델, 사용자, 쿼리 간 비교를 할 수 있다.

수식

\[NDCG@K = \frac{DCG@K}{IDCG@K}\]

코드

predict_list = ["A", "B", "C"]
ground_truth = {"A":0.1, "B":0.5, "C":0.7, "D":0.5, "E":0.1}

import math

def calc_dcg(relevance_scores) -> float:
    dcg = sum(score / (math.log2(i+1+1)) for i, score in enumerate(relevance_scores))
    return dcg

def calc_ndcg(predict_list, ground_truth, k:int=None) -> float:
    if len(ground_truth) == 0:
        return 0.0
    if (k is None) or (k > len(predict_list)):
        k = len(predict_list)
    ideal_relevance_scores = sorted(ground_truth.values(), reverse=True)[:k]
    idcg = calc_dcg(ideal_relevance_scores)
    if idcg == 0.0:
      return 0.0
    dcg = calc_dcg([ground_truth.get(item, 0.0) for item in predict_list][:k])
    return dcg/idcg

calc_ndcg(predict_list, ground_truth)
# >> 0.6048882832133625

Mean NDCG

개념

Mean Normalized Discounted Cumulative Gain 의 약자로, 여러 케이스에 대한 NDCG 점수의 평균값입니다.

수식

\[Mean \, NDCG@K = \frac{1}{n}\sum_{i=1}^{n}{NDCG@K(i)}\]

코드

cases = [
    {
    "predict_list" : [ "A", "B", "C"],
    "ground_truth" : {"A":0.1, "B":0.5, "C":0.7, "D":0.5, "E":0.1}
    },
    {
    "predict_list" : [ "D", "A", "C", "B", "E" ],
    "ground_truth" : {"A":0.1, "B":0.5, "C":0.7, "D":0.5, "E":0.1}
    }
]

import math

def calc_dcg(relevance_scores) -> float:
    dcg = sum(score / (math.log2(i+1+1)) for i, score in enumerate(relevance_scores))
    return dcg

def calc_ndcg(predict_list, ground_truth, k:int=None) -> float:
    if len(ground_truth) == 0:
        return 0.0
    if (k is None) or (k > len(predict_list)):
        k = len(predict_list)
    ideal_relevance_scores = sorted(ground_truth.values(), reverse=True)[:k]
    idcg = calc_dcg(ideal_relevance_scores)
    if idcg == 0.0:
      return 0.0
    dcg = calc_dcg([ground_truth.get(item, 0.0) for item in predict_list][:k])
    return dcg/idcg

def calc_mean_ndcg(cases, k:int=None) -> float:
    mean_ndcg = sum(calc_ndcg(case["predict_list"], case["ground_truth"], k) for case in cases) / len(cases)
    return mean_ndcg

calc_mean_ndcg(cases)
# >> 0.7356022113638424

Reference

https://en.wikipedia.org/wiki/Discounted_cumulative_gain
https://scikit-learn.org/stable/modules/generated/sklearn.metrics.ndcg_score.html?utm_source=chatgpt.com

Twitter Facebook LinkedIn

[추천시스템 평가지표 5. DCG, NDCG와 Mean NDCG

Jongya