キーワード検索システムにnDCGを導入~現状分析の話

はじめに

キーワード検索をリプレイス&独立した検索サービスを立ち上げた - nakamura244 blog

上記のエントリーで 今後の予定で 検索に評価指数の導入がありました。

これが完了したのでまとめてみたというのが話の主旨です

そもそもnDCGに関して

正しくはこちら

Discounted cumulative gain - Wikipedia

SEOが存在するように検索結果の順位によってクリックされる確率が大きく異なります。

簡単に言うと、その検索順位を考慮した評価指標がnDCGと言えるかと思います。

もうちょっと具体的に

下記の画面は時計というキーワードで検索した時の結果画面にクリックやCVの数をプロットしたものになります

• 検索順位が4位のものは1位と比べてクリックは少ないものの、CVRの値は良いです。
• 検索順位が1位になれば、クリックされる数は増えるのは普通の出来事だと思います。
• もし、検索順位4位のものが、1位に表示されて入れば、クリックの値は必然的に増えて、CVRは一番良いので購入の数は一番増えていた可能性があります。

ユーザにとって4位のものが一番求めてたものになるので1位に表示してあげるべきだと考えられます。

こういった検索結果の順位のアドバンテージを考慮して定量的に計測できるのがnDCGの特徴かと思います

適合度に応じた価値を利得 (gain) として考え、ランクが下位になるほどその価値を下げる減損利得 (discounted gain)というような仕組みです

設計や構成

キーワード検索結果からのリンク設定

キーワード検索の結果画面からリンクをクリックした時、下記のようなURLになっています

https://www.makuake.com/project/perfect_beer04/?from=keywordsearch&keyword=%E3%83%93%E3%83%BC%E3%83%AB&disp_order=1

GETパラメータでfrom=keywordsearch&keyword=ビール&disp_order=1となっている。

これはキーワード検索ページからビールというワードで検索して1番目に表示された結果をクリックして遷移してきたという意味になります

アクセスログからどんなキーワードで検索した時に、何番目のリンクをクリックしたかを集計する為、このような設定にしています

集計システム

• 検索されたキーワードはAPI Gatewayのlog = CloudWatchに出力されて、lambda経由でElasticsearchの専用のindexに格納されます
  • 水色のラインの部分です
• アクセスログはGoogle Analyticsを利用します
  • Load BalancerのアクセスログをETL(AWS Glue)で取ってきて利用する方法もありますが、ここではより簡単な方をチョイス
• Google AnalyticsからBigQueryへ定期的にデータをエクポートします
• スキャンするバイト数を考慮して新しいテーブルに必要なデータを定期エクスポートします
• CloudWatch eventから定期的にlambdaを起動し、BigQueryから検索システムを経由したアクセス数を抽出します(Getパラメータでアクセスログを絞り込む)
  • オレンジのラインの部分です
  • 適切な粒度のlambdaにしてstep functionsで連結します
    • jobを動かす度にBigQueryにアクセスが走り、都度課金される事を防ぐ為にjobを分けています
• 購入（CV）トラッキングもGoogle Analyticsで行っているのでBigQuery経由で取得します
• オレンジのラインのjobで検索されたワードを取得して、PV、CVをBigQueryから取得してDCG計算してElasticsearchの専用のindexに格納します

全て、Elasticsearchのindexに保存している理由はKibanaのCanvasでまとめて可視化しているからです

nDCGの計算式に関して

式で表すとこんな感じ

• p は検索順位の何番目までのDCGを対象とするかという意味
• reliはGETした利得スコア
• iは検索順位

これで導いた数値と本来の理想系のDCGで導いた値で割り算して x 100 で100%に近いほど精度が良いとする

式にするとこんな感じ

具体がないとわからないと思うのであげてみる

ビールというワードで検索した時の結果が下記だった場合

検索順位1位　A   click:240, cv:10
検索順位2位　B   click:244, cv:7
検索順位3位　C   click:249, cv:9
検索順位4位　D   click:100, cv:4
検索順位5位　E   click:100, cv:4

利得スコア = (click + cv ) * 100

実際に利得スコアしてみると

検索順位1位 Aの利得スコア : (240 + 10) * 100 = 25000
検索順位2位 Bの利得スコア : (244 + 7) * 100 = 25100
検索順位3位 Cの利得スコア : (249 + 9) * 100 = 25800
検索順位4位 Dの利得スコア : (100 + 4) * 100 = 10400
検索順位5位 Eの利得スコア : (100 + 4) * 100 = 10400

DCG5の計算式に当てて見ると

DCG5 =  25000 + (25100 / log_2(2)) + (25800 / log_2(3)) + (10400 / log_2(4)) + (10400 / log_2(5)) = 76057.0238461069

ここいうlog_2(x)は2を底とした対数の意

しかし、利得スコアから理想を導くと

本来は下記のように検索順位が望ましい

検索順位3位 Cの利得スコア : (249 + 9) * 100 = 25800
検索順位2位 Bの利得スコア : (244 + 7) * 100 = 25100
検索順位1位 Aの利得スコア : (240 + 10) * 100 = 25000
検索順位4位 Dの利得スコア : (100 + 4) * 100 = 10400
検索順位5位 Eの利得スコア : (100 + 4) * 100 = 10400

• 実際には検索順位が3だったCが1位で結果表示されるべきだった
• 実際には検索順位が1だったAが3位で結果表示されるべきだった

DCG5の計算式に当てて見ると

iDCG5 =  25800 + (25100 / log_2(2)) + (25000 / log_2(3)) + (10400 / log_2(4)) +  (10400 / log_2(4)) = 77073.24383928644

nDCGにしてみると

nDCG5 = 76057.0238461069 / 77073.24383928644 * 100 = 98% (小数点切り捨て)

理想の状態に98%近い状態であるという意味。

とってもいい結果ですね。

なぜnDCG10にしているか

正しい情報元がどこだったか、忘れてしまいましたが、検索を行うユーザのほとんどが検索結果ページの1ページ目しか見ないという事実があります。

1ページ目に表示する検索結果はだいたい10件程度になるという事でnDCG10にしています

計測対象

• 全ての検索キーワードでnDCG10を計算するのはちょっと非効率なので、検索キーワードの多いTOP30件に対してnDCG10計算を行うようにしています
• desktop,mobile,tabletというデバイスごとに集計して見ております
  • 検索アルゴリズムだけでユーザの求めるものに改善するというアプローチだけでは不十分です
  • アルゴリズムを変えずにUIだけを変えるだけで改善する事例は多々あります
  • デバイス間で検索アルゴリズムを変える事は当分行わないので（今後もやらないとは言っていない）、デバイス間比較をする事はUI / UX 比較に間接的になる為です

実際の可視化

可視化はKibanaのcanvasを使ってます

全体サマリー

• まずは全体のサマリー
• 一番上にあるのが全体のaverage
• 下に各デバイスごとのaverage
• アイコンを用いて可視化もついでにしてる
  • コーヒーアイコンは単に私がコーヒー好きであるというだけです
• x 100 をしていないので0.xxxみたいな数値になっています
  • 細かい数字は出せないけど...

詳細サマリー

• もうちょっと細かくバージョン
• 上のグラフは日毎のnDCGをピポットしてる
  • だいたいmobileデバイスのがnDCGの値が良いのでちょっと大きめの○になってたりする
• 下のグラフはnDCGのワースト
• ここで言うとペットというワードでdesktopで検索した時の結果が一番よくない
  • このデータからペットというワードで検索した時にどのような検索結果になっているのか
  • UX的にはどうなのか等々を掘り下げて調査をし、改善をはかります
  • そーすると、もともと検索回数の多いワードでnDCGを計測しているので、他に比べて大きいボトルネックの改善に繋がります。なので改善したときの効果も相対的に高くなります
  • あとはこのサイクルを繰り返すだけ

リプレイス前後比較

検索システムのリプレイスの前後1ヶ月で比較しました。

詳しい数値は書けませんが、結論から言うとnDCG10の指標からすると悪化してしまいました...😰😱

どういう事か詳しくみてみると...

リリース前の検索はmysqlのLIKE検索。リリース後はElasticsearch。Elasticsearchでの検索はngram検索ではなく、形態素解析したフレーズで検索するようにしています。

なので当然、検索ロジックは異なります。

その中でもリリース後は同じキワードでも検索ヒット数が多くなるようにパラメータをチューニングしました。

そのことにより、1ページ目の検索結果にノイズが混じり過ぎた結果だと思います

今後の改善ポイントです。

しかしもっとよくみてみると..

検索システムからのクリックに関しては倍以上に増えました。

これは、Elasticsearchに切り替えてから検索スピードが格段に良くなり、その結果たくさん検索を使ってもらった様子。

検索結果の2ページ目も良く使ってもらったようで2ページ目からのクリック（送客）がたくさんあったようです。

アクセスログを見ると検索結果の2ページ目からの送客の数値がリリース前に比べて桁が一つ違うほど増加していました。

トータルで考えると

• nDCGの値は悪化してしまい残念であった
• ただし、サジェストも含めると検索システムからの送客は2倍ほど増加した
  • 今後nDCGを改善を測るとさらに送客の価値が上がると思われる！！

あえてやっていない事

適合率、再現率、F値という部分はあまり気にしていません。これらのKPIを高める事が、より良い方向に行くとはあまり思えていない為です。

（今の所ね。今後も気にしないとは言っていない）

今後

• とりあえずnDCGの値をもうちょっと良い数値に改善をしたい
• 検索アルゴリズムだけでなくてUI / UXだけで改善できる部分もあるので進めたい
  • もちろん、合わせ技で改善していくべきところもあるので見極めて進めたい
  • 同じ検索アルゴリズムでデバイス間でnDCGが異なるのはUI / UXの影響であると言えそう
• 曜日や時間帯によっての検索キーワードの分析、傾向を把握して、傾向があればその時間にあったアルゴリズムで検索できるようにして行くと良いかなと思ったりしたす

最後

定量評価できることの価値を改めて感じてる。検索と言っても色々な使われ方も存在するし、それぞれの視点での良し悪しがあります。

定量評価指標がない中で改善施策を考えるのはかなり偏った方向に進む可能性が高いです。

一つの物差しを用いて改善の議論をできる事は良いですね！！

nDCGはレコメンド等の評価指標にも使えるので今後も活かしていきたいと思います