[ReMemo] Unexpected Co-occurrences of Patterns


前提条件

  • トランザクションデータベース \(D\) (トランザクション数 \( |D| \) )
  • 全アイテム集合 \(\Omega\)
  • 各トランザクション \( t\subseteq \Omega \) (アイテム数/大きさ \(|t|\))

基本的な考え方

A transaction is anomalous when it deviates from what we expect considering the whole dataset.

いくつかの取り組み方

Class 0: Unexpected Transaction Length

  • 長さが特殊なもの
  • 定量化方法

\( \mathit{score}_0 (t) = -\log P(|t|) = \log \frac{|t’\in D\mid |t’|=|t||}{|D|} \)

Class 1: Unexpected Transaction

  • データベースの中で特殊なもの
  • 定量化方法については別記(執筆中)

Class 2: Unexpected Co-occurrences

  • 表題
  • 考え方: 個別に出現するよりも低くしか共起しない組

A transaction contains a class 2 anomaly when it contains two patterns that occur much less often together in the data than what could be expected from their individual supports

  • 定量化方法: 共起しない(第1項)、両方の個別出現が多い(第2項)ものが良いスコアを持つ

\( \mathit{score}_2 (t) = -\max _{{X, Y\in\mathcal{S} | X, Y\subseteq t}} -\log P(XY) + \log(P(X)\times P(Y))\)

トイプログラム: Toy example

  • 準備中

論文など

  • L. Akoglu, H. Tong, J. Vreeken, and C. Faloutsos. Fast and reliable anomaly detection in categorical data. In CIKM, pages 415–424, 2012.
  • K. Smets and J. Vreeken. The odd one out: Identifying and characterising anomalies. In SDM, pages 804–815, 2011.