NDCG（Normalized Discounted Cumulative Gain）

中級

4.5.1

NDCG（Normalized Discounted Cumulative Gain）

最終更新 2020-01-29 読了時間 3 分
まとめ
  • NDCG はランキングの順位に応じた利得を正規化して測る指標です。
  • リラバンススコアを用いて DCG/NDCG を算出し、ログ割引の効果を確認します。
  • 多段階評価やカスケードモデルで使う際の注意点を整理します。

1. 定義 #

ランク \(i\) の関連度スコアを \(rel_i\) とすると、DCG（Discounted Cumulative Gain）は

$$ \mathrm{DCG@k} = \sum_{i=1}^{k} \frac{2^{rel_i} - 1}{\log_2(i + 1)} $$

理想的な並び（IDCG）での DCG を求め、正規化することで NDCG を得ます。

$$ \mathrm{NDCG@k} = \frac{\mathrm{DCG@k}}{\mathrm{IDCG@k}} $$

計算例：ステップバイステップ #

ここでは具体的な数値を使い、DCG → IDCG → NDCG の算出過程を一歩ずつ追います。

問題設定 #

検索エンジンが返した 5 件 の結果に対し、人手で以下の関連度（relevance grade）を付けたとします。

順位 $i$アイテム関連度 $rel_i$
1A3
2B2
3C0
4D1
5E0

関連度は0（無関係）〜3（非常に関連）の4段階です。

ステップ 1：DCG@5 を求める #

DCGの定義式を再掲します。

$$ \mathrm{DCG@k} = \sum_{i=1}^{k} \frac{2^{rel_i} - 1}{\log_2(i + 1)} $$

各順位の 利得（gain） $2^{rel_i} - 1$ と 対数割引（discount） $\log_2(i+1)$ を計算し、それぞれの寄与を求めます。

順位 $i$$rel_i$利得 $2^{rel_i}-1$割引 $\log_2(i+1)$寄与 $\dfrac{2^{rel_i}-1}{\log_2(i+1)}$
13$2^3 - 1 = 7$$\log_2 2 = 1.000$$7 / 1.000 = 7.000$
22$2^2 - 1 = 3$$\log_2 3 \approx 1.585$$3 / 1.585 \approx 1.893$
30$2^0 - 1 = 0$$\log_2 4 = 2.000$$0 / 2.000 = 0.000$
41$2^1 - 1 = 1$$\log_2 5 \approx 2.322$$1 / 2.322 \approx 0.431$
50$2^0 - 1 = 0$$\log_2 6 \approx 2.585$$0 / 2.585 = 0.000$

したがって、

$$ \mathrm{DCG@5} = 7.000 + 1.893 + 0.000 + 0.431 + 0.000 = 9.324 $$

ステップ 2：理想順位を作り IDCG@5 を求める #

IDCG（Ideal DCG）は、関連度を降順に並べ替えた理想的なランキングに対してDCGを計算したものです。

関連度を降順に並べると $[3, 2, 1, 0, 0]$ になります。

順位 $i$$rel_i$（理想）利得 $2^{rel_i}-1$割引 $\log_2(i+1)$寄与
1371.000$7.000$
2231.585$1.893$
3112.000$0.500$
4002.322$0.000$
5002.585$0.000$
$$ \mathrm{IDCG@5} = 7.000 + 1.893 + 0.500 + 0.000 + 0.000 = 9.393 $$

ステップ 3：NDCG@5 を算出 #

$$ \mathrm{NDCG@5} = \frac{\mathrm{DCG@5}}{\mathrm{IDCG@5}} = \frac{9.324}{9.393} \approx 0.9927 $$

この結果は「理想の約99.3%の品質」を意味します。実際のランキングでは、関連度1のアイテムDが4位に沈んでいるだけで、上位2件は理想と同じ並びのため、高いNDCGが得られました。

対数割引の直感的な理解 #

なぜ割引に $\log_2(i+1)$ を使うのでしょうか。以下のポイントを押さえてください。

  1. 上位ほど重要 — ユーザーは検索結果の上位から順に見ます。1位の割引は$\log_2 2 = 1$（割引なし）ですが、10位の割引は$\log_2 11 \approx 3.46$で、利得が約3.5分の1に減衰します。
  2. 緩やかな減衰 — 線形割引（$1/i$）に比べると、対数割引はより緩やかです。これは「5位と6位の差」より「1位と2位の差」の方がはるかに大きいという、ユーザー行動の経験則に合致します。
  3. スケール不変 — 対数の底を変えても（例：$\log_2$を$\ln$に変えても）、DCGの値がスケーリングされるだけで、NDCGの値は変わりません。正規化によって底の選択が吸収されるためです。

下の表で、順位が深くなるにつれて割引がどのように変化するかを確認できます。

順位 $i$$\log_2(i+1)$割引率 $1/\log_2(i+1)$
11.000100.0%
21.58563.1%
32.00050.0%
52.58538.7%
103.45928.9%
204.39222.8%
505.67217.6%
1006.65815.0%

1位では利得が100%反映されますが、100位ではわずか15%しか反映されません。このように、NDCGは「上位に高関連のアイテムを置くことがとくに重要」という直感を数値化しています。

2. Python で計算 #

1
2
3
4
5
6
7
8
9

from sklearn.metrics import ndcg_score

# y_true: shape (n_samples, n_labels) に関連度を格納

# y_score: モデルが出力したスコア

score = ndcg_score(y_true, y_score, k=10)

print("NDCG@10:", round(score, 4))

ndcg_score は関連度を 0/1 だけでなく、段階的な整数スコアでも扱えます。Ground Truth の関連度配列を用意するのがポイントです。

3. ハイパーパラメータ #

  • k の設定：ユーザーに提示する件数に合わせて @5, @10 などを選択。
  • 関連度スコア：0/1 の二値でも良いが、段階的なラベル（非常に関連、やや関連など）を使うと精度が高い評価になる。
  • log の底：定義によっては log2 以外を使う場合もあるが、スケーリングの違いに過ぎない。

4. 実務での活用 #

  • 検索結果評価：人手で付けた関連度ラベルを使い、NDCG@10 を主指標にする例が多い。

  • レコメンド：Implicit Feedback（閲覧や購買）を関連度として扱い、ランキング改善の KPI とする。

  • A/B テスト：オンライン評価と合わせ、オフラインで NDCG の向上がオンライン指標にどう影響するかを分析。

5. 注意点 #

  • Ground Truth の関連度を整備するコストが高い。Implicit Feedback を使う場合はノイズの影響に注意。
  • 候補生成とランキングの二段階構成では、それぞれのフェーズに適した指標を設定する。
  • NDCG だけでなく Recall@k や MAP も併用し、ユーザー体験を多面的に評価する。

まとめ #

  • NDCG は関連度スコアを対数減衰で加重し、上位に高関連度が並ぶほど高くなる指標。

  • ndcg_score で容易に計算でき、k の設定や関連度スコアの設計が重要。

  • 他のランキング指標と併用し、ランキング品質を総合的に向上させよう。