Twitterが公開したRパッケージBreakoutDetectionについて調べたことメモ(その1)
先月、Twitterが「BreakoutDetection」というRパッケージをオープンソースとして公開してちょっと話題になっていました。Twitterは多くのオープンソースをリリースしてきましたが、Rって珍しいですよね。
Breakout detection in the wild | Twitter Blogs
が、しかし。
BreakoutDetection、中身で何をしているのかさっぱりわかりません。上記のブログでは、
The underlying algorithm – referred to as E-Divisive with Medians (EDM) – employs energy statistics to detect divergence in mean. Note that EDM can also be used detect change in distribution in a given time series. EDM uses robust statistical metrics, viz., median, and estimates the statistical significance of a breakout through a permutation test.
とか書いてあるものの、EDMでググっても出てくるのはElectric Dance Musicだけで、それっぽいのが一向にヒットしません。気になったので調べたので、そのメモです。
※統計あんまり分からないので、間違っているところあればツッコミください
helpを読んでみる
help(breakout)
とすると、相変わらず手法については書いていませんが、Referencesという項目があります。なんかそれっぽい感じ。
References
Nicholas A. James, Arun Kejariwal, David S. Matteson, "Leveraging Cloud Data to Mitigate User Experience from 'Breaking Bad': The Twitter Approach, 2014
このテーマでぐぐると、どうやらこれは今年の9月、Velocityで発表されたもののようです。
Velocityでの発表資料
上のVelocityのページには資料は上がっていませんが、コメント欄で資料のURLが貼ってありました。そのスライドがこれです。
Mitigating User Experience from 'Breaking Bad': The Twitter Approach …
これを読むと、BreakoutDetectionがどういうパッケージなのか分かってきました。
キャパシティプランニングのためのパッケージ
てっきり、バズっている話題を予測するにはどうするかみたいな話だと思っていましたが、アクセス急増にどう対応するか、とかそういうキャパシティプランニング的な話らしいです。
Rolling median
スライド13に書いてあるには、
- Rolling medianはよさげ
- Raw time seriesはノイズや外れ値の影響をかなり受ける
- Moving averageは外れ値の影響を受けやすい
ということで、Rolling medianが採用されています。Rolling medianというのは、ある点の直近n個のデータの中央値です。たぶんMoving medianというのと同じ意味です。日本語だと移動中央値とか移動メディアンとかいうみたいです。
Moving averageは移動平均です。中央値だと外れ値の影響を受けにくい、というのはまあそうですよね。
Change point detection
スライド16には
[Change point Detection - David Hinkley, 1970]
と書いてあるけど、これはたぶんこの論文だと思われる。JSTORのは無料で読めそう。
Hinkley, David V. "Inference about the change-point in a sequence of random variables." Biometrika 57.1 (1970): 1-17. http://scholar.google.co.jp/scholar?cluster=14388703845576024560
Maximum Log Likelihood Estimation
対数尤度関数を使う最尤推定、的な? 最尤法、ぜんぜん理解できてないのでよくわかりません。。
まとめ
とりあえずキーワードは出そろった感じ。 スライド16の数式を理解するために、論文読んで最尤法のこと勉強しなおして出直します。。