読んだ：Search Engine Click Spam Detection Based on Bipartite Graph Propagation（WSDM2014）

殴り書いていくスタイル。

Search Engine Click Spam Detection Based on Bipartite Graph Propagation

クリックの情報は文書のランキングにおいて重要な要素である。
結果、いくつかのWebサイトは彼らのページへの不正なクリックの増加に
よって高ランクを得る。これはクリックスパムと呼ばれている。
不正なクリックの特徴に関する分析をベースに、
1.ユーザのセッションを行動だけでなく、セッションの目的とセッション間の
間隔もまた考慮に入れた３つの連鎖によってモデリングする
2.より不正を働いているセッションを発見するため、不正を働くユーザに有効になる
ように２部グラフの伝搬アルゴリズムを使用する
3.高precision,recallに達するような不正なセッションパターンを得るために、
パターンセッションの２部グラフ伝搬アルゴリズムを用いる
中国の一日あたり8000万クリックのデータを用いて、97％のprecisionで全体
の2.6%のクリックがスパムとして検出された。

・現実でのクリックスパムの例
a.クエリを要求した後同じURLを繰り返しクリックする
b.異なったクエリを要求した後同じドメインのURLを繰り返しクリックする

・データの収集
中国のコマースサイトから１日8000万の検索ログをランダムに収集。
時間、検索クエリ、クリックタイプ、クリックしたURLを収集
クリックログにはタグと呼ばれるものがついていて、どのタイプの検索をしたのか
わかるようになっている（画像検索とか動画検索）
ここで、検索タグとクリックされたURLに不一致が起きた場合、それはクリック
スパムだと言える。動画タグの検索なのにクリックしたURLが動画タグの結果には
存在しないなど。さらに、クリックされたURLとタグが合致しなかった場合も
スパムとする。
この処理により、収集したデータの0.54%に不正の疑いがあった。

・ユーザのセッションモデリング
セッションの定義・・・ユーザが最初のクエリを検索エンジンに要求してから
３０秒間とする。
ユーザの行動をいくつか定義
$Q_i$ …クエリの要求。iは異なったクエリを区別するのに使う。
$W_i$ …webの結果のクリック
$O_i$ …スポンサーのついた結果をクリック
$N$ …新しいページのロード
$T$ …ページのスクロール
$A_i$ …その他のクリック（タブのクリックなど）

また、前章とは異なり、異なったクエリや異なったリンクをクリックした場合に
別IDを与えることにする。　別クエリや別リンクのクリックは自然だが、同一
クエリの連発やリンクのクリックは不正の疑いがある。

・時間間隔
セッション内の行動が過度に頻繁であればbot的な動きである疑いがある
前のアクションから次のアクションに動くまでの時間を各ユーザの行動
毎にプロットしてやると、大体どの行動も同じくらいの時間間隔になっている。

この知見を利用してtime_intervalを4つのセグメントに分解
0秒
1-10秒
11-30秒
31秒-
すると、ユーザのセッションをモデリングできる
例：(Q0,0),(T,1),(Q0,1),(Q0,0),(W2,1),(Q1,3)...
クエリの送信->1-10秒後、ページスクロール->1-10秒後同じクエリ再送信

>連続で全く同じクエリ送信->1-10秒後、3つ目のページをクリック->

30秒以上経過後、別のクエリを送信->...

・セッションレベルでのクリックスパム認識
1.マルコフ遷移確率を用いた不正セッション検出
※今回の比較対象と成るベースラインの方法。
次のイベントへの遷移はその前のイベントに強く依存しているはず。
なので、ユーザのセッションをマルコフ遷移モデルで表現する。
$Q_{i,j}$ ...状態jから状態iに遷移する確率変数
$Q_i...\sum_{j}Q_{i,j}$
$Pr(i,j)$ ...状態iからjへの遷移確率

ここで、ユーザの各セッションにはセッション内の個々の状態遷移確率の
かけ算によって尤度スコアが与えられる。
高い尤度を持ったセッションは通常の振る舞いであるといえるし、低い尤度
であればレアな振る舞いと言える。
実際には尤度が非常に小さく成るので対数尤度＋セッション数での正規化
を行ってaverage Marcovian Loglikelihood(MLH_avg)を得る。
従った、小さなMLH_avgはセッションが正常でないことを表す尤度と成る。

この手法を１日分の5000万のユーザセッションデータで試したところ、
99.6%のセッションのMLH_avgが(-4,0]に収まっていた。従って、-4より
小さいセッションを不正なセッションと定義する。

2.不正セッション元を発見する
ラベル伝搬アルゴリズムを用いて不正セッションの元を発見、不正ユーザ、
連鎖パターンを検出する。
ここで検出された不正セッションをseedとして後述のグラフ伝搬アルゴリズム
に適用して行く。

5つの不正セッション形式を定義。
・(QAi)*:異なったクエリを投げ、同じドメインのWebページを繰り返し
クリック
・(QiT)*:同一クエリを投げ、繰り返しページスクロールを行う
・(Qi)*:キーワードの頻度を上げるため同じクエリを繰り返し投げる
・Q(Wi)*:クエリを投げた後、Webページを短い間隔で繰り返しクリックする
・Q(Ai)*:クエリを投げた後、同じドメインのページを短い間隔で繰り返しクリックする

上記の形式を一日分のユーザセッションデータで検出してみた。
その際、ユーザのセッション全体の50%以上の部分的な連鎖とマッチしたものを検出する。
各５つの形式に対して、100こずつランダムにセッションを抽出し、人為的にアノテーション
とpresicionの評価を行う。
すると、98.6%という極めて高いprecisionで不正なセッションを検出できた。

3.ユーザとセッションからなる２部グラフの伝搬アルゴリズム
何人かのユーザのセッションが不正であることがわかれば、そのユーザの他のセッションも
同様に不正なものであるという考えをベースにする。
先述の方法で検出した不正ユーザをこの方法で一気に検出する。
２部グラフを作ってみると、一日で4000万のユーザと100万のセッションから成るグラフが
構築できた。

- - - - -

アルゴリズム

- - - - -

sscore...セッションスコア
uscore...ユーザスコア
$w_{ij}$ ...ユーザをセッション間の重み。ユーザiがjのセッションを行った頻度。
(1)セッションにスコアをつける。2の方法によって不正判定されたセッションに1、そうで
なければ0をつける
(2)ユーザのスコアを計算。 $usore(u_i) = \sum_{i}w_{ij}*sscore(s_j)$
(3)セッションのスコア計算。不正なセッションは再び1に設定。そうでないものは
$ssore(s_j) = \sum_{j}w_{ij}*uscore(u_i)$
(4)2-3の操作を $|sscore_n-sscore_n-1|$ が指定したしきい値より小さくなるまで繰り返し

4.パターンとセッションからなる２部グラフの伝搬アルゴリズム
3によって不正ユーザのリストと不正なセッションの連鎖を得ることができる。これを
使ってすべての不正な連鎖パターンを検出する。
一定数の不正なセッションパターンとマッチするセッションがあれば、その他のセッション
も不正であるという仮定に基づく。
基本的な考えは、頻繁な連鎖パターンを求め、不正スコアをグラフに拡散させ、不正な
連鎖パターンのリストを得る。
頻繁な連鎖パターンは、連鎖データベースDを用意しておき、任意の連鎖パターン $\alpha$ が
$\alpha > \theta|D|$ を満たすときの $\alpha$ として定義される。（ $\theta$ はユーザ指定）

- - - - -

アルゴリズム

- - - - -

C...不正セッション連鎖集合
P...高頻度連鎖パターン集合
S...セッション連鎖集合
$w_{i,j}$ ...セッションとパターン間の重み
sscore...セッションスコア
pscore...パターンスコア
(1)セッションにスコアをつける。先述のアルゴリズムと同様
(2)pscoreを計算。リンクがあるセッションのsscoreの値と重みのかけ算
(3)sscoreの計算。リンクがあるパターンのpscoreの値と重みのかけ算
(4)2-3の操作を $|sscore_{n}-sscore_{n-1}|$ が指定したしきい値より小さくなるまで繰り返し

・評価
1.ユーザとセッションから成る２部グラフ伝搬アルゴリズム
 アルゴリズムを一日分のデータに試してみる。
不正スコアの高かった(>0.5)セッションをサンプリングして0.1区切りでprecisionを
手動で評価する。当然スコアが高ければ高い程precisionが高くなるはず。結果としても
(0.9,1]のスコアでprecisionが0.966と成った。そして全体のログの約2.1%がこのレンジ内に
入っている、すなわちクリックスパムであった。
一週間単位で一日ずつ評価してみると、月曜、火曜、水曜でクリックスパムが多く検出された
。どうやらこういった業者やユーザは週始めにアクティブになりやすいらしい。

2.セッションとパターンから成る２部グラフ伝搬アルゴリズム
$\theta$ の適切な値
0.005-0.01で動かしてみると、0.01が最も良く、precisionが97%だった。1と比較すると、
クリックスパムとして検出されるセッション数が多くなる。

3.３つのアプローチの比較
上述の２つの方法+ベースライン
ベースラインのprecisionが90%に対し提案アルゴリズムはどちらも97%という高いprecision
をたたき出している。
さらに、セッションとパターンから成る伝搬アルゴリズムを使うことで、より多くの不正な
セッションを検出することが出来るようになる。
さらに、検索結果の妥当性を評価できるNDCGを利用する。
クリック数が1000以上かつクリックスパム率が10%以上のクエリを抽出し、CTRの高い順に
検索結果をソートする。
CTRを計算する際、
・そのまま
・クリックスパムによるクリックを取り除く
の2パターンを用意しておき、NDCGの値を比較する。
その結果、クリックスパムをのぞいたNDCGの方がのぞかないよりも高くなった。すなわち、
クリックスパムにより上位にきたURLがクリックスパムをのぞいたことで妥当な順番に
下がったと言える。

MACにPCをかえてバックスラッシュが打ちづらくなって初めて不便だと思った。