Robust Random Cut Forest Based
Anomaly Detection On Stream — ICML2016
【一言まとめ】robust random cut tree(RRCF)に基づくストリームデータの異常検知手法を提案した。
【著者】
【所属機関】
【URL】http://jmlr.org/proceedings/papers/v48/guha16.pdf
【Abstract】
In this paper we focus on the anomaly detection problem for dynamic data streams through the lens of random cut forests. We investigate a robust random cut data structure that can be used as a sketch or synopsis of the input stream. We provide a plausible definition of non-parametric anomalies based on the influence of an unseen point on the remainder of the data, i.e., the externality imposed by that point. We show how the sketch can be efficiently updated in a dynamic data stream. We demonstrate the viability of the algorithm on publicly available real data.
【Abstract翻訳】
本論文では、ランダムカットフォレストのレンズを通した動的データストリームの異常検出問題に焦点を当てる。 私たちは、入力ストリームのスケッチまたはシノプシスとして使用できる強固なランダムカットデータ構造を調べます。 我々は、残りのデータ上の見えない点の影響、すなわちその点によって課される外部性の影響に基づいて、ノンパラメトリックな異常の妥当な定義を提供する。 スケッチを動的データストリームで効率的に更新する方法を示します。 公開されている実データに対するアルゴリズムの実行可能性を実証する。
【どんなもの？】
robust random cut tree(RRCF)に基づくストリームデータの異常検知手法
【先行研究と比べてどこがすごい？】
類似手法であるIsolation Forest より学習が早い
【技術や手法のキモはどこ？】
各ステップでの次元選択時に各次元のデータ分散に基づいた重み付け分布を用いる
【どうやって有効だと検証した？】
様々な距離構造においての精度
【議論はある？】
次元選択を適切に行う必要がある
【次に読むべき論文は？】
・Isolation-based Anomaly Detection — ACM
【手法詳細】
RRCFはIsolation Forestと類似しているが、各ステップにおける次元選択時に各次元のデータ分散幅に基づいた重み付け分布を用いる。
またその分割の軌跡を木構造で構築し、それを大量に作りアンサンブルする事でforestを作る。
このRRCF構造は、データ分散幅に基づく距離の定義の利用で、その距離が大きければ少なくともある2点がマンハッタン距離以上は離れている事が言える。
この事実を利用してさらに任意のLp(p>1）距離に関してもそれが大きい場合はRRCFにおけるisolationが早くなる事も言える。
またオンライン監視を意識した、保持するサンプルの取捨、またそれに伴う木構造変化に関して、生成確率的に一貫したサンプル取捨後の木構造を効率よく計算する手法を提案する。
この手法では、確率分布を替えないようにするだけでなく、サンプル取捨前後で構造が近い事を要求する。この要求を満たすためにはデータ分散に応じた次元選択がキーとなる
【関連リンク】
