広告に関するなにか: RedshiftでAttribution分析の実装

職場の同僚のドッグさん（語尾は上げる）に「パイセン、Redshiftとか使ってイイカンジにAttribution分析するならどんなかんじなんすかね〜」って言われたので考えた。

Attribution分析とは

「あるコンバージョンに対して貢献のあった広告の表示やクリックなどの、要因分析」という感じだと思っている。例えば下記のような導線をたどった場合を考えてみる。

banner impression(1)
banner impression(2)
banner click
paid_search impression
paid_search click

このときにconversionに対して貢献度を下記のように割り振るイメージ。割り振りは適当。適当なんだけど、この数値の精度をいかに上げていくのかというのが恐らく一番大事な話なんだと思う。

banner impression(1): 5%
banner impression(2): 10%
banner click: 20%
paid_search impression: 15%
paid_search click: 50%

こうすると、ひとつのコンバージョンに対して複数の広告やクリック以外のアクションの貢献度を数値化することができ、より精度の高い広告の予算配分が可能になりますよという考え方。

「より」というのはどういうことかというと、よくAttribution分析と比べられる手法として、より昔からあったLast Click分析というのがある。この手法で先ほどの導線を分析すると以下のようになる。

banner impression(1): 0%
banner impression(2): 0%
banner click: 0%
paid_search impression: 0%
paid_search click: 100%

コンバージョン前の最後のクリックに対しての貢献度を100%としておくということになるが、この分析手法だと「search adの効果がよかったので、banner adの出稿を減らしてsearch adに予算を集中させましょう」ということになる。実際にはbanner adもこのコンバージョンに対しての貢献をしているにもかかわらず。

ではなぜAttribution分析が新しいかという話だが、理由はいろいろあると思うのだけれど、システム屋てきな発想としては、impressionまで分析対象にすることのシステムコストが大きな原因のひとつであると思う。

たとえばクリックだけを分析対象にするのと比べて、インプレッションまで分析の対象にすると処理するデータの量（ログの行数）だけで1,000倍くらいにになる。（広告のクリックレートを0.1%で計算した場合）更にラストクリックと違い、ひとつのコンバージョンに対しての貢献があるイベントを時系列に並べて、更に貢献度の時間的減衰を計算して・・・みたいなことをやるととても計算コストが高くなる。ログの行数だけで1,000倍なので、総コストで見ると1,000倍を軽く超えるはず。

実装を考える

前置きが長くなってしまったけれど、これの実装を考えてみる。

スキーマ

ログのスキーマはこんな感じとする。ものすごく単純化してるので注意。もっとたくさんアトリビュートはあるはずだし、一般的にはアクションごとにログを分けちゃうはず。

少しでも計算を楽にするためにログにsession_idという概念を取り入れてみる。広告への初回接触時にsession_idを払い出す感じ。で、conversionしたら破棄、もしくは時間が経ったらexpire、みたいな感じ。

{
  action:    '{impression|click|conversion}' // ユーザーのアクションのタイプ
  campaign_id:     'string',       // 広告のキャンペーンを一意に識別するID
  ad_id:  'string'      // 広告を一意に識別するID
  ad_type:   '{banner|listing}',     // 広告の種類
  uid:   'string',     // ユーザーのID
  session_id: 'string' // ひとつのコンバージョンに至るまでの一連のセッションにふられたID
  timestamp: 'timestamp' // アクションのタイムスタンプ
}

さっきの導線をログにしてみるとこんなかんじ。

{"action":"impression", "campaign_id":"123", "ad_type":"banner","uid":"abc","timestamp":"2015-01-01T12:34:56Z"}
{"action":"impression", "campaign_id":"123", "ad_type":"banner","uid":"abc","timestamp":"2015-01-01T12:45:21Z"}
{"action":"click", "campaign_id":"123", "ad_type":"banner","uid":"abc","timestamp":"2015-01-01T12:45:36Z"}
{"action":"impression", "campaign_id":"123", "ad_type":"listing","uid":"abc","timestamp":"2015-01-01T13:01:01Z"}
{"action":"click", "campaign_id":"123", "ad_type":"listing","uid":"abc","timestamp":"2015-01-01T13:01:21Z"}
{"action":"conversion", "campaign_id":"123","uid":"abc","timestamp":"2015-01-01T13:10:12Z"}

出力

とりあえずこんな感じのテーブルにデータを出力してあげたらあとはいろいろ計算できるはず

CREATE TABLE attributions (
  `campaign_id` CHAR(20),
  `ad_id`       CHAR(20),
  `ad_type`     CHAR(20),
  `action`      CHAR(20),
  `score`       REAL,
  `timestamp`   TIMESTAMP
);

計算の大まかな流れを確認する

では、上記のような出力をつくるためにはどんな計算をしたらいいんだろうということでRubyっぽい擬似コードを書いてみる。なんかMapReduceっぽくなった。これそのまま実装すりゃいいじゃんw

actions = [...] #すべてのログへの参照を持つとする
actions
  .group_by{|action| action[:session_id]} #session_idでgrouping。Map処理。
  .each_value{|grouped_actions| #Shuffle & Sort
    grouped_actions.each{|action| #Reduce
      puts    1/actions.size
              * action_factor(action[:action])
              * type_factor(action[:ad_type])
              * recency_factor(actions[-1][:timestamp] - action[:timestamp])
    }
  }

def action_factor
  #クリックやインプレッションなど、ユーザーのアクションによる係数を計算する
end

def type_factor
  #bannerやListingなど、広告の種類による係数を計算する
end

def recency_factor
  #コンバージョンを起点として、アクションのRecencyによる係数を計算する
end

あくまでここで書いているのは計算の流れであってアルゴリズムではない。上記のサンプル内の*_factorの精度をどうやってあげていくのか、というのが非常に重要なポイントであり、アルゴリズムの話。

SQLで実装しなおす

で、計算の流れに戻ると・・・actions.size....?

!!!

これはアレだ。ひとつの計算をするために複数行のデータを参照しなきゃいけないアレだ。Window関数が必要になってくる感じ。あんまり効率のいいSQLにならなそう。

ひとまず書いてみるとこんな感じだろうか。現状、RedshiftにはUDFを取り扱う機能はないが、めんどくさいのでとりあえず擬似コード的にUDFを使って書く。

SELECT
  campaign_id,
  ad_id,
  ad_type,
  action,
  (1/ COUNT(*) OVER (PARTITION BY sessiond_id)) * action_factor(action) * type_factor(ad_type) * recency_factory(LAST_VALUE(timestamp) OVER (PARTITION BY sessiond_id) - timestamp) AS score,
  timestamp
FROM actions;

UDFほしい

・・・はい。UDFほしいですね。いまのところだと、それぞれの*_factor関数をSQLにベタ書きで展開してcase文とか使ったら書けると思う。

しかしそれではメンテナンス性が低い。アルゴリズムの調整をするたびにSQLを修正しなきゃいけないというのはちょっとアレな感じ。去年のre:InventでUDF対応するよって言ってたので、期待して待つのがよさげ。

アルゴリズム

もう長くなってきたので、というのと集中力が切れてきたのでアルゴリズムについてはまた今度考えてみることにする。いちおう、今回の記事を書くのにあたって、いろいろ記事やらなにやらを掘ってみたんだけど、Quoraのこのスレッドがわかりやすくまとまっていてよかった。

What is a conversion attribution model in online advertising?

主に議論の対象になっているのは - バナーなのかリスティングなのか - クリックなのかインプレッションなのか - 3rd Partyのデータもいかすべき

みたいな話なんだけど、とりわけいい話だなと思ったのは下記のコメント。

It's important to distinguish between data-driven and user-driven models. By this I mean that some attribution solutions simply consist of user-assigned weights for each type of touch point. If you think that Search is 2X as good as Display, you can set that weight, and the results you get will be tilted towards search. This type of "model" is easy to implement, but not very objective since it relies on the marketer's existing intuition. Data-driven models, on the other hand, rely on statistical algorithms and extract the value of each channel from the data.

たとえばクリックだったらインプレッションの2倍みたいなアナログな手法よりも、もっとデータドリブンでやるべきということを主張している。

具体的には先程の*_factorな関数たちの係数を決めるためのパラメータを実際のデータから計算しようという話になるんだと思う。ではそれを実現するためにはどうしたらいいのか。例えば以下のようなデータを集めることが想像できる。 - 係数を分散させた複数の広告を出稿して、実際に効果のよさそうな係数設定を探っていく - 流れている広告主の出稿データと結果から係数の精度を上げていく

このあたりはまた今度ふかく考えてみることにする。

まとめ

ありません。次回（いつになるかは・・・）に続く！

工場長のブログ

日々思ったことを書いてます。