First Story Detection, New Event Detection
ツイートの無限列が流れてきて: \[d_1,d_2,..,d_{n-1},d_n,..\] \(d_n\) と同じイベント (話題) について言及してるツイートがそれ以前にあったかどうかを判定したい
そのようなツイートが無いなら、\(d_n\) は新しいイベントの話をしていることになる
2つのツイートが同じイベントについて話してるかどうかは適当な閾値を以って \(O(1)\) で出来るとする.
FSDの素朴な方法:
本論文で提案するのは、1つのツイートの処理が定数時間で済むもの
ツイートを、bag-of-words と大体同様のもので管理する.
高々 \(k\) 個の語の集合を k-term と呼ぶ. 以下 \(k=3\) とする (一般に自然数).
文章をbag-of-words \(d\) とする. \(d\) の content とは、 \[\{ t : t \subseteq d, |t| \leq k \}.\] \(d\) の部分としての k-term 全体からなる集合のこと.
\(d\) のハッシュとして content を用いる.
\(d_1,..,d_{n-1}\) までcontent 全体を履歴 \(H\) として持っておく.
ツイート \(d_n\) について、 content を \(c_n\) とするとき:
\[N(d_n) = \sum_{t \in c_n} \alpha_{|t|} \binom{|d_n|}{|t|}^{-1} \chi(t, H)\] where \(\chi(t,H) = 1\) if \(t \not\in H\) else \(0\)
本質は \(\chi\) の和であるところで、その前の部分は適当な重み.
\(N(d_n)\) が閾値を超えたら、\(d_n\) を新しいイベントについて言及したツイートとして報告する.
新規性の計算の後、 \[H \leftarrow H \cup c_n\]
\(|c_n|\) は \(O(|d_n|^k)\). Twitterの条件と\(k\)が定数であることから、これは定数.
\(H\) のmembership の判定、更新はツイート数が増えるにつれて遅くなるはず.
i32 に変換アノテートされた116,000のツイートを用いて実験
TDT と呼ばれる定番の指標を用いる
[Figure 1]
[Table 1]
tweets/sec は処理速度