MicroAd Developers Blog

マイクロアドのエンジニアブログです。インフラ、開発、分析について発信していきます。

RIDITスコアによる不正検知

マイクロアドでデータを分析している高橋と申します。
大学院までは物理学を専攻していましたが、縁あってデータ分析の分野に飛び込むこととなりました。
入札額の最適化アルゴリズムに取り組んでいた時期もありましたが、現在は広告表示の異常検知・不正検知周りが主テーマです。
今回は、不正検知等で役に立ちそうなRIDITスコアについての話をさせていただきます。

広告表示の不正検知

私が取り組んでいるテーマについて、もう少しだけ深くご説明いたします。
マイクロアドではDSP(Demand Side Platform)・SSP(Supply Side Platform)市場に参入していますが、そこで問題となるのがアドフラウド(広告不正)*1です。 一口にアドフラウドと言っても手段・目的は千差万別。例えば

  • 隠し広告(広告システム上は表示されていることになって課金されるが、実際にはユーザーの目に触れていない広告)
  • 自動リロード(広告表示を何度も自動的にリロードすることで、広告の表示回数を水増しする)
  • 不正クリックによるCTR(Click Through Rate)水増し・広告効果カサ増し

など、挙げ始めたらキリがありません。
不正に対抗するため、マイクロアドではアドフラウド対策研究機関として「アドベリラボ」を昨年設立いたしました。
現在その研究開発の一環として、広告表示の異常検知・不正検知および不正除去のアルゴリズム開発に取り組んでおります。これが私の任務になります。
研究成果は、現在開発中の「UNIVERSE Ads」に順次フィードバックされていく予定です。

不正検知で困ること

銀行や保険などの金融業界やアクセス解析などのセキュリティ界隈でポピュラーな不正検知。 検知手法は様々ですが、どのレコードが不正なのかが未知のデータセットを利用する教師なし学習の場合、素朴に以下のような方法が考えられると思います。

f:id:microad-developer:20190611184220j:plain
  1. 不正に関連していると思われる指標をいくつかピックアップする
  2. 閾値を設定し、異常な値を示した場合には0/1の不正フラグをつける(ただし、指標の値が連続量ではなく純粋なYES/NOの二値しかないような場合もある)
  3. フラグが多すぎるレコードを不正だと判断する

この手法を採用する場合に、単に0/1の値を振るだけでいいのか、フラグ数を数えるだけではなく重み付けする必要があるのではないか、といった疑問が生じます。かく言う私もその一人でした。

RIDITスコア

単に0/1の値を振るだけでいいのか、という問いに対する一つの解決策がRIDITスコア(Bross, 1958*2、Brockett and Levine, 1977*3、Brockett, 1981*4、Golden and Brockett, 1987*5 )です。

計算方法

不正指標 t の各値に応じて不正らしさの順番を事前に与えておきます。例えば、不正指標の値をビンに区切るなどして何段階かに分けることで順番が決まります。これをランクと呼ぶことにします。 k_t を不正指標 t に対するランク数(順番の最大値)とし、各ランクに属する値を持つレコードの割合が  \hat p_t=( \hat p_{t1}, \cdots, \hat p_{tk_t} ) で与えられる場合を考えます。ただしここではランクの値が大きいほど不正度合いが高いものとします。 つまり不正指標  t について  t1 が一番問題なさそう、  tk_t が一番問題ありそうという並びです。 このとき、不正指標 t の各ランク  ti に対してRIDITスコアは以下のように定義されます。

$$ R_{ti}=\sum_{j<i}\hat p_{tj} - \sum_{j>i}\hat p_{tj} \qquad i=1, 2, \cdots, k_t$$

ランクを保ちつつも、割合が少ないものを大きく評価するスコアです。少数派の不正レコードを検出する際に使えそうです。

具体例

具体例を挙げた方が分かりやすいと思います。

f:id:microad-developer:20190613134900p:plain

ある不正指標 t のランクと各ランクに属する値を持つレコードの割合が与えられた場合のRIDITスコアを計算しました。具体的な計算式は以下のようになります。

R_{t4} = (0.6 + 0.2 + 0.1) - 0 = 0.9
R_{t3} = (0.6 + 0.2) - 0.1 = 0.7
R_{t2} = 0.6 - (0.1 + 0.1) = 0.4
R_{t1} = 0 - (0.2 + 0.1 + 0.1) = -0.4

この場合、出現確率の低いランク3, 4あたりに属するレコードが不正判定に大きく近づきそうです。

念の為、0/1フラグの場合も考えてみます。こちらの方がより簡単な計算です。

f:id:microad-developer:20190613135019p:plain

このように、RIDITスコアによって各不正指標のランクを-1~1の範囲で表現できます。

PRIDITメソッド

これで問題解決!...ではありません。不正指標の重み付けという難題が残っています。
この難題に立ち向かうのがPRIDITメソッド(Brockett et al., 2002*6 )です。

計算方法

f:id:microad-developer:20190611164717j:plain:w400

以下、行列の上付き文字  t は転置記号を表します。
F=(f_{it}) を縦がレコード i 、横が不正指標 t としてその成分にRIDITスコアを入れたRIDITスコア行列とします。 レコードが i=1, 2, \cdots, N 、不正指標が t=1, 2, \cdots, m だった場合、行列は  N\times m の次元数になります。
ここに初期重みベクトル  \boldsymbol{w}^{(0)}=(1, 1, \cdots, 1)^{t} (ただし次元数は  m )をかけると、 各レコードの初期不正スコアベクトルが  \boldsymbol{s}^{(0)}= F\boldsymbol{w}^{(0)} として計算できます。この  \boldsymbol{s}^{(0)} の成分は各レコードの不正スコアを表しており、次元数は  N です。
この  \boldsymbol{s}^{(0)} を再び用いて、  \boldsymbol{w}^{(1)}= F^{t}\boldsymbol{s}^{(0)}/||F^{t}\boldsymbol{s}^{(0)}|| といった形で重みベクトルを更新してやります。
こうしてまた不正スコアベクトルを  \boldsymbol{s}^{(1)}= F\boldsymbol{w}^{(1)} という形で算出して、 重みベクトルを更新して...と続いていきます。
更新は一定値で収束し、最終的に算出された重みベクトル \boldsymbol{w}^{(\infty)} の各成分は、対応する不正指標の重要度そのものとみなせます。

これ以上の詳細はBrockett et al., 2002をご参照ください。

実際にやってみた

PRIDITメソッドを使って不正検知を行ってみます。

import numpy as np
from numpy.random import randn, seed

# 元となる行列の次元を設定
row = 100
col = 10
half_col = int(col / 2)

# 標準正規分布による100×10の行列作成
seed(seed=0)
mat = randn(row, col)

# 0/1のフラグをつける際、indexが0~4の列とindexが5~9の列で条件を変える
a = np.where(abs(mat)[:, 0:half_col] > 1., 1., 0.)
b = np.where(abs(mat)[:, half_col:col] > 2., 1., 0.)
cat_mat = np.concatenate([a, b], 1)

これでデータの準備が完了しました。ただし、ここのフラグをつける閾値はざっくり決めてあります(本来の不正検知であればランク分けの閾値設定に注意を払いますが、あくまで今回はお試しです。以下も同様)。 あとで比較できるように、単純な不正フラグの個数だけで怪しいと判定したレコードをいくつか抽出しておきます。

# 不正フラグの個数だけで怪しいと判定したレコードを抽出する
high_indices = np.where(np.sum(cat_mat, axis=1) >= 3.)[0]

この段階だと0/1の成分しかないため、RIDITスコアに変換します。

# 各指標(各列)の1となる成分の個数を計算
counts = np.count_nonzero(cat_mat, axis=0)

# RIDITスコアに変換(floatで処理しているため、0.001という数値と比較する)
for i in range(col):
    np.transpose(cat_mat)[i] = np.where(np.transpose(cat_mat)[i] >= 0.001, (1 - counts[i] / row), -(counts[i] / row))

下準備ができたので、ここからPRIDITメソッドで重みを更新していこうと思います。

# 重みベクトル初期化
weights = np.ones(col)

# iteration
iter = 100
for i in range(iter):
    scores = cat_mat @ weights
    weights = (np.transpose(cat_mat) @ scores) / np.linalg.norm(np.transpose(cat_mat) @ scores)

無事に重みベクトルを得ることができました! 中身を確認してみましょう。

print(weights)
[ 0.62758036 -0.57742762 -0.2226612   0.11012925  0.44542115 -0.03847074
 -0.03294317  0.03540356 -0.07543845 -0.05571489]

どうやらindexが0と4の指標が重視されているようです。
続けて重みを考慮して怪しいと判定したレコードを抽出し、不正フラグの個数だけで怪しいと判定した先のレコードと比較してみましょう。

new_indices = np.where(cat_mat @ weights > 0.5)[0]
print(high_indices)
print(new_indices)
[ 0  4  8 10 19 23 27 33 38 45 49 51 53 54 58 64 68 70 73 74 85 91 92]
[ 0  2  8 11 14 19 23 26 34 41 45 47 49 53 56 60 78 80 85 86 87 88 90 93]

引き続き不正が疑われるものもありますが、新たに現れたり消えたりしたレコードも多数あります。 試しに、PRIDITによって新しく不正を疑われたindexが2のレコードを見てみます。

print(mat[2])
[-2.55298982  0.6536186   0.8644362  -0.74216502  2.26975462 -1.45436567
  0.04575852 -0.18718385  1.53277921  1.46935877]

重みベクトルが大きな値をとる成分と、このレコードで(絶対値の)大きな値をとる成分が一致しているように見えます。 具体的な精度を評価していませんが、どうやら単純に行列を作成しただけでは見えなかった重要度が考慮されているようです。 実データで分析した場合にはもっと顕著に分かるはずです。

ちなみにこのPRIDITスコアで求まる重みベクトルは、更新を続けていくと  F^{t}F という行列を主成分分析した際の第一主成分の固有ベクトルに収束するようです。この説明を受けると、重要度がうまく抽出できているというのも頷けますね。

まとめ

簡単にではありますが、不正検知を行う際に役立ちそうなRIDITスコア・PRIDITメソッドについてご紹介いたしました。
マイクロアドでは機械学習に限らず幅広い知見を持ったデータ分析者を随時募集しております。 興味を持たれた方は、ぜひwebページをチェックしてください!