Mining of Massive Datasetsの1.2節の概要を書きます。
1.2 Statistical Limits on Data Mining
- 大量データの中に隠れているunusual eventsを見つけること
- "Bonferroni's Prnciple"を含むデータマイニングに対する過信について議論する
1.2.1 Total Information Awareness
- Total Information Awareness(wikipedia,ALC)
- 2002年、ブッシュ政権がテロリストの攻撃を追跡するためにクレジットの引き落としなど様々な情報からマイニングすることを推奨していた
- その時作られたDARPAのプロジェクト。プライバシーの問題を指摘され終了している
- 技術的な懸念
- 「テロリスト」かどうかは、どれだけ念入りに「探す対象」を定義するかに依存している
- テロリストに見える振る舞いを見つけようとすることも、無実に見える行動を見つけないことも、テロリズムではないが違法な行動も見つけることができる
- それにより、警察が訪れることも起こりうる
1.2.2 Bonferroni's Principle
- 大規模データのマイニングでは、意味のないパターンを「発見」してしまうリスクがある
- 一定量のデータからある種のイベントを探そうとする時、ランダムなデータからでもイベントとして判断される(偽陽性)データが存在し、その数はデータサイズに応じて増える
- Bonferroniの補正(★)をおこなうと、統計的に偽陽性が得られる確率を目標とする値に調整できる
- 有意水準を検定の回数で割ることで、試行回数を増やして出やすくなる有意差を厳し目にチェックできる
- Bonferroniの補正を雑にしたものがBonferroni's Principle
1.2.3 An Example of Bonferroni's Principle
- 感覚的には誕生日のパラドックスに似ているかも
設定
犯罪組織のペアがホテルで、悪事の密談をしているかを検出したいとする
前提
- 犯罪組織の可能性を疑われている追跡対象者は10億人いる
- 全員100日に1日はホテルに行く
- 1つのホテルは100人入ることができ、100,000ホテル存在する(つまり、10億人の1%はある日どこかのホテルを訪れることができる)
- 1000日のホテルの記録を調べることができる
計算
AさんとBさんが、ある日同じホテルに居る確率は
$ Aさんがあるホテルに居る確率 \times Bさんがあるホテルに入る確率 \times 2つのホテルが同じ確率 = $
$ 1/100 \times 1/100 \times 10^{-5} = 10^{-9} $
AさんとBさんが、2日同じホテルにいる確率は
$ 10^{-9} \times 10^{-9} = 10^{-18} $
日付の組み合わせは
$ _{1000}C_2 = 5 \times 10^{5} $
AさんとBさんが特定の2日に、同じホテルにいる確率は
$ 5 \times 10^{5} \times 10^{-18} = 5 \times 10^{-13} $
人の組み合わせは
$ _{10^{9}}C_2 = 5 \times 10^{17} $
疑わしい人のペアの数は
$ 5 \times 10^{17} \times 5 \times 10^{-13} = 250,000 $
もし、本当に犯罪活動をしていたのが10ペアだとした時、警察は10ペアのために25万人を捜査しないといけない。