nDCGを2つのランキングが変わらないことの確認に使ってみた

はじめに

みなさんElasticsearch触っていますか？

検索ランキングに変更を加えた際に、ランキングの変わり具合が大きいものを探したいことありますよね？
定性的に探すと時間がかかるし精度が低い。差異を定量的に表現して大きく変わっているものを探したい時にどんな指標を使えば良いのか考えてみたいと思います。

ランキングの差異を知るにはどんな評価指標がよいか？

今回のケースでは、3点を選定基準としました。

1. ランキング全体ではなく、上位の方で評価したい
   • 検索結果が数万件のクエリに対して全件計算すると計算コストがかかるため
2. 変更前後のランキングで共通じゃない要素が入ることを許容したい
   • 1で上位の方だけ使用して計算する都合上一方にある要素がもう一方にない可能性がありえる
3. より上位を重視した数値にしたい
   • プロダクトへの影響を考えると上位の差がより影響度が大きいのでこれを数値にも反映したい

ランキングの差異を測るために、以下の指標を候補として検討しました。サクッと調べた感じだとSpearman相関係数、Spearman Footrule、nDCG(Normalized DCG)あたりが候補になりそうでした。
3つの候補の良し悪しを3つの選定基準の観点で表にまとめてみました。

指標	1.上位k件で評価できるか？	2.不一致要素の許容	3.上位を重視	備考
Spearman相関係数	× 全体の順位が必要	× 要素不一致の計算不可	× 全体を均等に評価	全件に共通する要素が前提
Spearman Footrule	× 全体の順位が必要	× 要素不一致の計算不可	× 全体を均等に評価	距離感は直感的だが正規化されてない
nDCG（Normalized DCG）	◎ 任意のk件で評価可能	◎ 片方にない要素も考慮可能	◎ 上位に重みあり	情報検索・レコメンドで広く使用される指標

Spearman相関係数とSpearman Footruleに関しては、2つのランキングで要素がどのくらい移動したかを数値化したもので、上位k件での評価をすると不一致要素が発生しうる。もう一方のランキングに含まれない要素は距離計算不能となるのでその点でこの2つは今回の要件的には不適切です。上位を重視するという点については、nDCGは下位ほど減点することで相対的に上位に加点することになりますし、不一致要素も関連度0として扱えばよいので今回の要件をクリアしています。

nDCGとは？

nDCG(Normalized Discounted Cumulative Gain)は、検索結果やレコメンデーションの品質の評価などに使われる指標です。

nDCGはDCGを正規化した指標で、理想のDCG(IDCG)で割ることで正規化しており、これにより検索クエリ同士比較しやすくなります。

$$\mathrm{nDCG}_k = \frac{\mathrm{DCG}_k}{\mathrm{IDCG}_k}$$

$k$件ランキングについてのDCGは下記の数式で表され、$rel_i$は$i$番目の要素の関連度を示しています。

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

実際に計算してみると、、、
例えば理想の関連度が[5,3,3,1,1]となっていたとします。実際の関連度が[3,1,5,1,3]だったとすると
その場合の計算は

$$\newcommand{\logtwo}[1]{\log_{2}\!\left(#1\right)} \begin{aligned} \text{IDCG} &= \frac{5}{\logtwo{2}} + \frac{3}{\logtwo{3}} + \frac{3}{\logtwo{4}} + \frac{1}{\logtwo{5}} + \frac{1}{\logtwo{6}} \\[4pt] &= 5.0000 + 1.8928 + 1.5000 + 0.4307 + 0.3869 \\[4pt] &= 9.2103 \end{aligned}$$

$$\newcommand{\logtwo}[1]{\log_{2}\!\left(#1\right)} \begin{aligned} \text{DCG} &= \frac{3}{\logtwo{2}} + \frac{1}{\logtwo{3}} + \frac{5}{\logtwo{4}} + \frac{1}{\logtwo{5}} + \frac{3}{\logtwo{6}} \\[4pt] &= 3.0000 + 0.6309 + 2.5000 + 0.4307 + 1.1606 \\[4pt] &= 7.7222 \end{aligned}$$

$$\text{nDCG} \;=\; \frac{\text{DCG}}{\text{IDCG}} \;=\; \frac{7.7222}{9.2103} \;\approx\; 0.839$$

というようになります。
このように理想の関連度に対して、どのくらい近いかを定量化することができます。

ランキングの差異を測るために使ってみる

本来の使い方と違いますが、擬似的に関連度を定義することで2つのランキングの差を数値化してみたいと思います。

例えば、["apple", "banana", "grape", "orange", "peach"]というランキングがあったとして、変更前のランキングが理想のランキングとして関連度を[5,4,3,2,1]とします。

変更後のランキングについては、変更前ランキングと一致する要素があれば定義した関連度を付与します。変更後["peach", "apple", "banana", "grape", "orange"]となった場合、関連度を[4,3,2,1,5]とします。

このように関連度を擬似的に定義した場合、変更前後のランキングが

• 同じ順の場合
• すべての要素が不一致の場合
• 上位の要素が入れ替わっている場合
• 下位の要素が入れ替わっている場合

でnDCGがどうなるかみてみましょう。要件として上位k件で絞りたいということもあったので4件に絞って計算してみます。

ケース	ランキングアイテム	関連度	nDCG
同じ順	変更前: ["apple", "banana", "grape", "orange", "peach"] 変更後: ["apple", "banana", "grape", "orange", "peach"]	理想: [4, 3, 2, 1] 実際: [4, 3, 2, 1]	1.0000
すべての要素が 不一致	変更前: ["apple", "banana", "grape", "orange", "peach"] 変更後: ["kiwi", "mango", "pineapple", "strawberry", "watermelon"]	理想: [4, 3, 2, 1] 実際: [0, 0, 0, 0]	0.0000
上位の要素が 入れ替わっている	変更前: ["apple", "banana", "grape", "orange", "peach"] 変更後: ["banana", "apple", "grape", "orange", "peach"]	理想: [4, 3, 2, 1] 実際: [3, 4, 2, 1]	0.9496
下位の要素が 入れ替わっている	変更前: ["apple", "banana", "grape", "orange", "peach"] 変更後: ["apple", "banana", "orange", "grape", "peach"]	理想: [4, 3, 2, 1] 実際: [4, 3, 1, 2]	0.9905

nDCGは1~0の値をとりますが、同じ順の場合は1、すべての要素が不一致の場合0。また、上位の要素が入れ替わっている場合が0.9496、下位の要素が入れ替わっている場合が0.9905となっています。
1に近いほど似ている、0に近いほど違うランキングだということが分かり、かつ上位と下位での重み付けも反映されています。

もし同じようなケースがあればぜひ参考にしてみてください！

実際に計算に使ったコードはこんな感じになっています。

def main():
  before_items = ["apple", "banana", "grape", "orange", "peach"]
  after_items = ["kiwi", "mango", "pineapple", "strawberry", "watermelon"]

  k = 4  # 評価するランキングの長さ
  y_true, y_score = create_relevance(before_items, after_items, k)
  result = ndcg(y_true, y_score, k)

  print(f"k = {k}")
  print(f"y_true  = {y_true}")
  print(f"y_score = {y_score}")
  print(f"ndcg = {result}")

def create_relevance(before_ids: List[str], after_ids: List[str], k: int) -> tuple[np.ndarray, np.ndarray]:
  """
  変更前のランキングと変更後のランキングから擬似的に関連度を生成する
  """
  # 各要素にランキング降順でスコアを付与する
  scores = {id: (k - i) for i, id in enumerate(before_ids[:k])}
  # 変更前のランキングの関連度を擬似的に生成 = [k, k-1, ..., 1]
  y_true = np.array([list(scores.values())])
  # 変更後のランキングの関連度を擬似的に生成
  y_score = np.array([[scores.get(id, 0) for id in after_ids[:k]]])

  return y_true, y_score


def ndcg(
  y_true: np.ndarray, y_score: np.ndarray, k: int) -> float:
  """
  Normalized DCG (nDCG)
  """
  y_true = np.asfarray(y_true)
  y_score = np.asfarray(y_score)
  # DCG
  dcg_val = _dcg(y_score, k=k)
  # IDCG
  idcg_val = _dcg(y_true, k=k)

  return dcg_val / idcg_val if idcg_val > 0 else 0.0


def _dcg(
  rels: np.ndarray, k: int) -> float:
  """
  Discounted Cumulative Gain (DCG)
  """
  # 関連度
  rels = np.asfarray(rels[:k])
  # 各要素の割引値を計算
  discounts = np.log2(np.arange(2, rels.size + 2))
  return np.sum(rels / discounts)

最後に

スペースマーケットでは一緒に働く仲間を募集しています！
とりあえず話を聞いてみたいという方でも大歓迎です！ちょっとでも興味があれば以下からご応募お待ちしております！