NDCG (Normalized Discounted Cumulative Gain) を理解する

まとめ

1. NDCGは、scoreの大小は関係なく、スコアの順番に並べたときの順序を評価するもの
2. CG (Cumulative Gain): Relevancyを足してく (Relevancyの計算は色々ある. 例のような単純なtarget 0/1の場合は単純に relevance score の足し算)
3. Discount: Rankが下がるにつれて足してくDiscountしていく (高いランクよりも低いランクの正解をたかく評価する)
4. Normalized: Ideal DCGでの割って 0~1に収める

以下の記事がわかりやすい！

計算

Pythonのライブラリ準備

sklearn.metrics.ndcg_scoreをimport

>>> from sklearn.metrics import ndcg_score
>>> import numpy as np

Relevance scoreを定める

Relevance Scoreは、ランキングの評価をクリックされたかどうかでは、判定する場合には、Clickを1、それ以外を0などに設定する。ことができる。

が、以下のように、重み付けをしたスコアにすることも可能。今回は、 itemを4つでそれぞれのスコアは、1,0.1,0,0としておく。

>>> relevancy = np.asarray([[1, 0.1, 0, 0]])

Relevancyを決めると任意の順序に対して一つのスコアを算出できるようになる。

例1. 完璧なケース

完璧なケースはつまりrelevance score 順に並んでいるもの。

例えば、item0~3に3,2,1,0という点数をつけるランキングシステムがあったとすると、Relevance score通りに並んでいるのでndcgは1となる。

>>> score = np.asarray([[3, 2, 1, 0]]) # perfect rank (Relevancyが高いスコア順に並んでいる)
>>> ndcg_score(relevancy, score)
np.float64(1.0)

scoreのところに、直接relevancyを入れても同様に1となる。

ndcg_score(relevancy, relevancy)
np.float64(1.0)

scoreの大小は関係なく、スコアの順番に並べたときの順序を評価するものである。

例2. 2位と3位が逆になっているランキングの場合

item1よりもitem2の方がscoreを高く評価するランキングがあったとする。

>>> score = np.asarray([[3, 1, 2, 0]]) # 2nd and 3rd places are wrongly ranked
>>> ndcg_score(relevancy, score)
np.float64(0.987684073114351)

この場合は、NDCGは0.9876と1より少し落ちるがそこまで大きく落ちてはいない。

愚直に計算すると以下のように logで割引率をかけて足し算をするので、今回減った分は 0.1 * np.log(2+1) の値分だけで、relevance scoreがそもそも低い部分に対して外しただけなので、最終的なNDCGは高いままだった。

>>> (1 / np.log(1+1) + 0 / np.log(2+1) + 0.1 / np.log(3+1) + 0) / (1 / np.log(1+1) + 0.1 / np.log(2+1) + 0 + 0)
np.float64(0.987684073114351)

例3. 1位と2位を逆にしてしまったランキングの場合

item0のスコアの方がitem1より低くしてしまうランキングがあったとする。

>>> score = np.asarray([[2, 3, 1, 0]]) # 1st and 2nd places are wrongly ranked
>>> ndcg_score(relevancy, score)
np.float64(0.6875501677789769)

するとNDCGは、0.68とかなり下がってしまう。

愚直に計算すると、以下のようになる。

>>> (0.1 / np.log(1+1) + 1 / np.log(2+1) + 0 + 0) / (1 / np.log(1+1) + 0.1 / np.log(2+1) + 0 + 0)
np.float64(0.687550167778977)

繰り返しにはなるが、ランキングに使うスコア自体の大きさは最終的なNDCGスコアには影響しない。

>>> score = np.asarray([[200, 300, 1, 0]]) # prediction score, which is used for ranking, is irrelevant to the final score
>>> ndcg_score(relevancy, score)
np.float64(0.6875501677789769)