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で発表されたもののようです。

Mitigating User Experience from 'Breaking Bad': The Twitter Approach: Velocity New York 2014 - O'Reilly Conferences, September 15 - 17, 2014, New York, NY

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

対数尤度関数を使う最尤推定、的な? 最尤法、ぜんぜん理解できてないのでよくわかりません。。

最尤法 - Wikipedia

まとめ

とりあえずキーワードは出そろった感じ。 スライド16の数式を理解するために、論文読んで最尤法のこと勉強しなおして出直します。。