Normalized Discounted Cumulative Gain is a metric used in recommendation systems to assess the ranking quality of the top listed products. More relevant products should be ranked higher than less relevant products.
To understand NDCG, we must understand all it’s smaller parts.
- Cumulative Gain (CG): CG is the sum of all the item’s relevance scores, the latter being a score that indicate how relevant a product is for the user (it can be obtained either by supervised or semi-supervised ways). The major drawback of CG is the fact that it doesn’t consider the ranking of the recommendations, but only the relevance score.
- Discounted Cumulative Gain (DCG) : to address the problems in CG, DCG introduces a discounting factor, which is a factor multiplying the relevance score that decreases logarithmically as the item is lower in the ranking. Example: where is the relevance of the item, and the other number is the discounting factor. The drawback of DCG is the fact that the score is dependent on the ranking list’s length. In particular, as the length of the recommendation increases, there is a high probability that DCG increases.
- Normalized Discounted Cumulative Gain (NDCG): to solve the DCG problem, in NDCG we normalize the DCG by dividing it by the Ideal Discounted Cumulative Gain (IdCG), which is the DCG of a perfect ranking.
As all the other ranking metrics, usually we compute the NDCG@K, meaning we get the top-K elements from the ranking and compute the metric on those, instead of using the whole recommendation list.
resources: