Early detection of Twitter trends explained | computational amusement
Twitterのストリームからトレンドを検出する取り組みはいくつかあると思うのですが、ノンパラメトリックなアプローチという点が、 よくあるアルゴリズムとは異なっていて興味深かったので読んでみました。
パラメトリックモデルの問題
トレンド検出でよく用いられるアプローチは、トレンドになるようなストリームの変化をモデル化する方法です。
例えば、普段はほとんど変化がない状態で、突然大きな変化が起こるようなモデルが考えられます。
このときのActivityは、あるワードのツイート数などを表します。
この大きなジャンプがトレンドを示しているので、これを検出する一つの方法としては、ジャンプパラメータpというものを使って
検出区間でpがある閾値を超えればトレンドと判定すれば良いと思われます。
このようにデータからパラメータを推定するやり方がパラメトリックな手法です。
しかし、このようなパラメトリックモデルというのは、うまくいかないことが容易に想像できます。
なぜならば、あらゆるトピックのストリームがこのモデルに当てはまるわけではないからです。
例えば、
- 小さいジャンプがあった後に、大きいジャンプがあるかもしれない
- 徐々に上がって大きいジャンプはないかもしれない
その他にも色々なパターンが考えられます。
確かに、それぞれのパターンのパラメトリックモデルを作ることは可能です。もしくは、共通なモデルを作ることも出来るかもしれない。
しかし、すぐに破綻してしまうだろうし、全てのモデルを作ったとしてどのモデルを当てはめればいいかを事前に知ることは出来ません。
別のアプローチが必要になりそうです。
A data-driven approach
そこで提案されている方式が、ノンパラメトリックなアプローチです。
トレンドになるストリームとならないストリームを十分に集めることが出来れば、それらがトレンドを
検出するためのモデルを表していると考えることが出来るというのが基本的なアイデアになります。
そうすると、無限のパターンが考えられるし、全パターンを十分にモデル化するためには膨大なデータが
必要になるのでは？という点については、ソーシャルネットワークではユーザの行動は予測可能で、
結果としていくつかのパターンがあって無限のパターンにはならないということのようです。
- 小さなジャンプがあって、大きなジャンプのパターン
- ジャンプがあって、その後徐々に上がっていくパターン
- 鋸歯状のような特殊なパターンはなかった
そうすると、パラメトリックにモデル化も出来るのでは？という気もしてきますが。
アルゴリズムの詳細
トピックがトレンドになるかどうかを、最近のストリームの観測sから推定するとします。
このとき、過去のトピックのストリームrとの類似度d(r, s)を計算し、
Positiveもしくはトレンドになったストリームとの比較は”Trending”への投票、
Negativeもしくはトレンドにならなかったストリームとの比較は”Non-trending”への投票とします。
投票スコアをVとすると、
として計算します。ガンマはスケーリングパラメータで、ストリームのどこまでの領域を使うかを決めるパラメータです。 また、類似度dはユークリッド距離です。 最後に、TrendingもしくはNon-trendingの全ての投票値を加えて、Non-trendingに対するTrendingの比が1より大きいかどうかで判定します。
このアプローチの良い所として、以下の点を挙げています。
- 計算がシンプル、距離計算をするだけ
- 距離計算は並列化可能でスケーラブル
- ノンパラメトリック＝どのモデルを使うかを決める必要がない
Result
500のTrendingトピックと500のNon-trendingトピックを集めて評価を行っていて、79%のケースで、 Twitterのトレンド検出よりも1.43時間早くトレンドを検出出来たということのようです。 推定精度としては95%程度となっています（4%のFPにおいて95%のTP）。
まとめ
内容を知ると、非常にシンプルで、その他の色々なケースでも上手く検出できるのか？と少し疑問に思いますが、 ノンパラメトリックなアプローチというのは面白い視点でした。 コメントのところを見ると、ソースもGithubで公開しているみたいだし、理論的にはデータを十分に集めることが出来れば機能するので、自分で試してね！ということかもしれません。:-)
