Kleinberg のバースト検知 (列挙型) について

はじめに

時系列ストリームデータにおいて出現頻度が急激に増加している時間帯を検出する方法の一つである、 Kleinbergの「列挙型 (enumerating)」バースト検知アルゴリズムを紹介します。

Kleinbergのバースト検知とは

Jon Kleinberg による論文 に、文書ストリームデータが「バースト状態」であるとは、 (文書データのある特定トピックなどの) 出現頻度が、急激に上昇する状態 をいう、と述べられています。 1

そこでは、 「ドキュメントの到着時間間隔」と、 「全ドキュメントと関連するドキュメントとの比」 の二つに着目してバースト状態が論ぜられ、 前者に対する考察が「連続型」に、後者に対する考察が「列挙型」に、それぞれ繋がっていきます。

列挙型バースト検知とは

以下、或るマイクロブログサービスから取り出したデータを用いて、 キーワードとして「松井」を含むドキュメントのバースト検知を考えてみます。

列挙型の説明の前に、 連続型 を復習しておきましょう。

行頭に + を付けてあるのが「松井」を含むドキュメントです。 投稿が短い時間に集中する 2012 年 11 月 20 日 15 時 59 分〜16 時 02 分 あたりを バーストと検知できれば、連続型として「良い」バースト検知であると考えられます。

  2012-11-20T15:09:00 - 東通原発の断層を12月に調査 原子力規制委 - 日本経済新聞: 原子力規制委員会は20日、東北電力東通原子力発電所(青森県)の敷地内の断層を12月13〜14日に現地調査することを決めた。規制委は6… http://t.co/XHr36cXQ
+ 2012-11-20T15:18:01 - 維新とみんな、相互に推薦 競合しない小選挙区で - 日本経済新聞: 日本維新の会幹事長の松井一郎大阪府知事は20日、みんなの党と候補者が競合しない小選挙区で互いの公認候補を推薦し合う方向で調整して… http://t.co/p0jzyD0B
+ 2012-11-20T15:59:14 - 連投4。 RT @******: 4、松井氏「私は府知事に就任してすぐ、府議会に『職員基本条例』を提案し、可決成立した。職員を評価し、5段階の最低ランクが2年連続続けば指導研修に 入る。それでも態度が改まらなければ辞めていただく」
+ 2012-11-20T16:00:38 - 連投6 RT @******: 6、松井氏「党首討論で安倍総裁と野田総理が、議員定数削減についてやり取りしていたが、選挙が終わってからではなく、なぜ今やらないのかと疑問に思う。 本気でやろうと思えば今できるはず。選挙終了後もやらないだろう」
+ 2012-11-20T16:01:12 - 連投 7 RT @******: 7、松井氏「民主党政権では0増5減も出来ていない。その状況で、霞ヶ関の職員たちに『やれ』と指示したところでやるわけがない。まずは政治主導。政治家 が自ら身を切る覚悟をしっかり示すことで職員の意識は変わる」
+ 2012-11-20T16:02:37 - 連投8 RT @******: 8、松井氏「昨年『大阪府市統合本部』という『バーチャル大阪都』なる組織を作り、大阪府と市の二重行政を見直していっている。税金の無駄遣いを改めてい く。例えば、大阪市の病院の建て替えという問題がある。(続く)」
  2012-11-20T16:36:03 - 「全1区擁立」断念=維新幹事長【12衆院選】 - 時事通信 http://t.co/a56f3Qci 2012-11-21 01:21:56
  2012-11-20T16:48:00 - 南シナ海、各国「協議を」 東アジアサミット - 西日本新聞: …世界. 【プノンペン進藤卓也】東南アジア諸国連合(ASEAN、10カ国)と日米中韓など18カ国首脳による「東アジアサミット(EAS)… http://t.co/OqTrJoiR
  2012-11-20T18:09:38 - (@´・ω・) 本日もたくさんの相互フォローありがとうございます。 #フォローミー
  2012-11-20T18:10:46 - まだ、残席あります。お早めに! RT @******: @****** え!まだ席あるんですか!?
  2012-11-20T18:45:56 - 「王様のブランチ」先日『創造力なき日本』の取材を、スタジオにて受けました。お恥ずかしい、朝礼の様子等も撮られてしまい、まぁ、本の中でも言ってはいますが、実際の映像となると迫力あり過ぎで、またdisられる事でしょう。11月24日の特集で放送予定です!
+ 2012-11-20T18:48:01 - 維新、全「1区」擁立を断念 - 大分合同新聞: 日本維新の会の松井一郎幹事長は20日夜、衆院選で各都道府県1区に関し、みんなの党と選挙区調整を進めていることを明らかにした。全国で1区に独自候補 を擁… http://t.co/dWs0Q3En
  2012-11-20T18:50:24 - 鼻水がとまらなくなってきた。

連続型検知に必用なのは、 キーワードを含むドキュメント(上例で + を付けたところ)の到着時刻情報のみとなります。

それぞれの 分 未滿を切り捨て、 2012-11-20T15:00 からの相対時刻に直して入力値とし、 CLML の連続型バースト検知器で計算させてみた結果が以下です。

TS-BURST-DETECTION(20): (compute-burst-index '((18) (59) (60) (61) (62) (228)) 2 1)
((0 18) (0 59) (3 60) (3 61) (3 62) (0 228))

入力であるそれぞれの時刻に対応してバーストの強さを示す指標が出力されており、 2012-11-20T16:00〜2012-11-20T16:02 を、バーストとしてとらえている事がわかります。

次に本題である、列挙型のバースト検知を見てみましょう。 列挙型のバースト検知には、 バッチ と呼ばれる時間区切りと、 バッチ毎の全ドキュメント数及び関連ドキュメント数を数える事が必要になります。 この例では、1バッチを30分とし、バッチ始点時刻を 2012-11-20T15:00 とします。

ドキュメントをバッチに入れると以下の8つのバッチに分かれます。 この時点で、バッチ間隔よりも細かい時刻情報は抜け落ちてしまうことに注意します。 以下、それぞれのバッチに、 0) 1) … 7) の数字をふり、 バッチID と呼んで、バッチを識別するのに用いることにします。

0) [2012-11-20T15:00, 2012-11-20T15:30)
  1. 東通原発の断層を12月に調査 原子力規制委 - 日本経済新聞: 原子力規制委員会は20日、東北電力東通原子力発電所(青森県)の敷地内の断層を12月13〜14日に現地調査することを決めた。規制委は6… http://t.co/XHr36cXQ
  2. 維新とみんな、相互に推薦 競合しない小選挙区で - 日本経済新聞: 日本維新の会幹事長の松井一郎大阪府知事は20日、みんなの党と候補者が競合しない小選挙区で互いの公認候補を推薦し合う方向で調整して… http://t.co/p0jzyD0B
1) [2012-11-20T15:30, 2012-11-20T16:00)
  1. 連投4。 RT @******: 4、松井氏「私は府知事に就任してすぐ、府議会に『職員基本条例』を提案し、可決成立した。職員を評価し、5段階の最低ランクが2年連続続けば指導研修に 入る。それでも態度が改まらなければ辞めていただく」
2) [2012-11-20T16:00, 2012-11-20T16:30)
  1. 連投6 RT @******: 6、松井氏「党首討論で安倍総裁と野田総理が、議員定数削減についてやり取りしていたが、選挙が終わってからではなく、なぜ今やらないのかと疑問に思う。 本気でやろうと思えば今できるはず。選挙終了後もやらないだろう」
  2. 連投 7 RT @******: 7、松井氏「民主党政権では0増5減も出来ていない。その状況で、霞ヶ関の職員たちに『やれ』と指示したところでやるわけがない。まずは政治主導。政治家 が自ら身を切る覚悟をしっかり示すことで職員の意識は変わる」
  3. 連投8 RT @******: 8、松井氏「昨年『大阪府市統合本部』という『バーチャル大阪都』なる組織を作り、大阪府と市の二重行政を見直していっている。税金の無駄遣いを改めてい く。例えば、大阪市の病院の建て替えという問題がある。(続く)」
3) [2012-11-20T16:30, 2012-11-20T17:00)
  1. 「全1区擁立」断念=維新幹事長【12衆院選】 - 時事通信 http://t.co/a56f3Qci 2012-11-21 01:21:56
  2. 南シナ海、各国「協議を」 東アジアサミット - 西日本新聞: …世界. 【プノンペン進藤卓也】東南アジア諸国連合(ASEAN、10カ国)と日米中韓など18カ国首脳による「東アジアサミット(EAS)… http://t.co/OqTrJoiR
4) [2012-11-20T17:00, 2012-11-20T17:30)
5) [2012-11-20T17:30, 2012-11-20T18:00)
6) [2012-11-20T18:00, 2012-11-20T18:30)
  1. (@´・ω・) 本日もたくさんの相互フォローありがとうございます。 #フォローミー
  2. まだ、残席あります。お早めに! RT @******: @****** え!まだ席あるんですか!?
7) [2012-11-20T18:30, 2012-11-20T19:00)
  1. 「王様のブランチ」先日『創造力なき日本』の取材を、スタジオにて受けました。お恥ずかしい、朝礼の様子等も撮られてしまい、まぁ、本の中でも言ってはいますが、実際の映像となると迫力あり過ぎで、またdisられる事でしょう。11月24日の特集で放送予定です!
  2. 維新、全「1区」擁立を断念 - 大分合同新聞: 日本維新の会の松井一郎幹事長は20日夜、衆院選で各都道府県1区に関し、みんなの党と選挙区調整を進めていることを明らかにした。全国で1区に独自候補 を擁… http://t.co/dWs0Q3En
  3. 鼻水がとまらなくなってきた。

バッチ内のドキュメントを、 (全ドキュメント数, 関連ドキュメント 2 数) のペアで整理した結果が以下になります。

バッチIDバッチ(全ドキュメント数,関連ドキュメント数)
0[2012-11-20T15:00, 2012-11-20T15:30)(2,1)
1[2012-11-20T15:30, 2012-11-20T16:00)(1,1)
2[2012-11-20T16:00, 2012-11-20T16:30)(3,3)
3[2012-11-20T16:30, 2012-11-20T17:00)(2,0)
4[2012-11-20T17:00, 2012-11-20T17:30)(0,0)
5[2012-11-20T17:30, 2012-11-20T18:00)(0,0)
6[2012-11-20T18:00, 2012-11-20T18:30)(2,0)
7[2012-11-20T18:30, 2012-11-20T19:00)(3,1)

上表の「ペア」から成る列 ((2,1),(1,1),(3,3),(2,0),(0,0),(0,0),(2,0),(3,1)) が列挙型バースト検知の入力値となります。 列挙型のバースト検知は、あるバッチにおける、直前のバッチからの、 「関連ドキュメント数」もしくは「全ドキュメント数に対する関連ドキュメント数の比」 の急増を検知するものであり、この場合だと、 バッチID 1 と、バッチID 2 の二つ、 即ち、 [2012-11-20T15:30 2012-11-20T16:30) が、 捉えたいバースト期間の一つとなります。

このように、連続型と列挙型では、入力するデータ・検知される出力値がどちらも異なります。 下図は、出力値についての連続型と列挙型との違いを図示したものです。 連続型では、15 時 59 分から 16 時 2 分という時間間隔でバーストを検知できているのに対して、 列挙型では、「バッチの時間間隔」以上に細かい間隔では検知できないので、 時間的にいうと列挙型のほうがより「大まかな」捉え方になっています。

./continuous_vs_enumerate.20140404.png

連続型と列挙型の結果の図

バースト検知の内部処理

本章では、連続型と列挙型を対比させながら、バースト検知の内部処理について、簡単に説明します。

連続型も列挙型も、 バーストの表現にはオートマトンを用います。 オートマトンは、 連続型においては、バーストレベルを表現する無限個の状態を持ち、 列挙型においては、基底状態とバースト状態との2値状態を持ちます。

どちらの方式も、入力列に対し、コストの最小となる最適なオートマトンを与えることで、 各入力要素に対する状態(バーストレベル)が求まります。

コストとは、 状態遷移の起きにくさ を数値化したもので、 連続型では、「ドキュメント到着時間間隔が指数分布に従うとしたときの確率密度関数」、 列挙型では、「サンプル数をドキュメント総数とし、関連ドキュメント総数が二項分布に従うとしたときの確率密度関数」 からそれぞれ計算されます。

バーストの強さは、連続型においては状態そのものにあたりますが、 列挙型においては、状態は基底とバーストの二値しかありません。 そこで、 バースト状態と判定された期間における『基底状態へ遷移する場合のコスト値とバースト状態へ遷移する場合のコスト値との差』の和 を計算し、これをweight値と呼び、バーストの強さの指針とします。 weight値が大きいほど基底状態には遷移しにくく、より強いバーストであるといえます。

実データによる検証

以前に紹介した CLMLの連続型バースト検知ライブラリ に続いて、列挙型を実装してみました。 連続型での検証と同じ元データを用いて検証してみます。

期間は2012年11月01日〜2013年05月14日(UTC)、 バッチ間隔は1日とし、「『松井』を含む投稿」を関連ドキュメントとします。

実データ概要

以下は、日毎の関連ドキュメント数と、 全ドキュメントに対する関連ドキュメントの比、 をグラフ化したものです。

./r_and_ratio-of-d-and-r.2014032702.png

日毎の「関連ドキュメント数」と「(関連ドキュメント数)/(全ドキュメント数)」

実行結果

このグラフだけからでも、適切な閾値を設けてやればバースト検知は充分に可能なように見えますが、 実際に上データを列挙型バースト検知器にかけてみた結果と比較考察してみましょう。

CL-USER(10): test-batches  ; (全ドキュメント数 関連ドキュメント数) のリスト
((6041 4) (5881 0) (5297 0) (5315 1) (5837 12) (6148 6) (6402 2) (5906 2)
 (5760 3) (5396 5) ...)
CL-USER(11): (enumerate-kleinberg test-batches)  ; (ID1 ID2 Weight) のリスト
((18 21 20.41562f0) (30 32 7.550129f0) (34 35 6.1921034f0) (46 48 6.2835402f0)
 (56 59 74.399055f0) (151 153 40.37496f0) (185 186 16.75833f0))

上出力は、バースト期間が以下の 7 つであることを示しています。

期間バッチIDweight
2012-11-19/2118〜2020.42
2012-12-01/0230〜317.55
2012-12-05346.19
2012-12-17/1846〜476.28
2012-12-27/2956〜5874.40
2013-04-01/02151〜15240.37
2013-05-0518516.76

上記、イタリックで示した箇所であれば、単純な閾値設定によつての検知も可能と思われます。 しかし、太字で示したところまで採りたいとすれば、閾値設定をかなり注意深く設定する必要が生じます。

ここに示した列挙型バースト検知器は、(連続型と同じく)閾値設定が不要であるにもかかわらず、 捉えたいバーストを捉えている、という面で勝れていると言えます。

列挙型と連続型

次に、列挙型の結果と、連続型の結果とを比較してみましょう。 連続型の実行結果は、 前囘の記事 のものを使用しています。

以下は、列挙型の結果と連続型との結果を比較したグラフです。 横軸は「日」で、 連続型の値は、「その日で最も高いバーストレベル」を表示しています。

./kleinberg-result.20140331.png

列挙型の結果と連続型の結果

まず、ざっと上のグラフを眺めてみて言えることは、 連続型と列挙型とで、ほぼ同じ期間を『バースト状態』として検知出来ている、 ということです。

次に、連続型と列挙型で異なる挙動を示している例をとりあげて見てみます。

例 1 (2013-05-02/09)

この期間は、連続型では全期間バースト状態と検知できていて、 列挙型では 5 月 5 日しかバーストを検知できていない例です。 この時期は、関連ドキュメント数が以下のようになっています。

  • 2013-05-02:8
  • 2013-05-03:9
  • 2013-05-04:5
  • 2013-05-05:32
  • 2013-05-06:6
  • 2013-05-07:8
  • 2013-05-08:9
  • 2013-05-09:8

列挙型は5月5日の本當に急激な関連ドキュメント数の増加だけを検知しています。

この例より、小さなバーストも細かく検知するという意味では 列挙型よりも、連続型のほうが適しているといえます。

例 2 (2012-11-19/21)

この期間は、列挙型の weight 値に比べて 連続型のバーストレベルが極端に高い値になっています。 これは、11 月 21 日の 16 時台に関連ドキュメントが 15 個集中したことによるものです。 しかし、日単位で見ると 11 月 21 日の関連ドキュメント数は 32 と 「特に巨大な増加ではない」ことが、 この時期の weight 値がそれほど高くない原因です。

例 3 (2012-12-05 v.s. 2012-12-17/18)

この 2 つの期間は、 連続型では前者のほうがバーストレベルが高く出力され、 列挙型では後者のほうが weight が高く出力されている、 「連続型と列挙型で、バーストの強さの順番が異なる」例になっています。

列挙型の weight 値はバースト期間で和を取って定義される値であることから、 「バースト期間の長さ」にも重きが置かれます。ですので、 バースト期間の長さを考慮に入れたい場合は列挙型が適しており、 短期的な増加を主に知りたい場合は連続型が適していると言えます。

例 4 (2013-12-27/29)

この期間は 連続型でも列挙型でも高い数値になっています。 12 月 27 日に、関連ドキュメント数 60 と突出した上に、 翌 28 日も関連ドキュメント数 52 で、 「投稿の集中が長い期間続いた」 ことが挙げられます。

イベントと照し合せて

さて、バースト検知された日時に、 実際の出来事としては何が起こつていたのでしょうか。 ドキュメント本文と照らし合わせて検証してみます。

まず、例 1 の時期 (2013 年 5 月 2 日〜9 日) について見てみます。 この時期には「松井」関連の出来事として、以下のことがありました。

日付イベント
2013 年 5 月 2 日巨人、国民栄誉賞授与式概要発表
2013 年 5 月 3 日松井秀喜氏、帰国
2013 年 5 月 4 日神奈川県春季高校野球、桐蔭が優勝、桐光・松井登板せず
2013 年 5 月 5 日長嶋、松井両氏に国民栄誉賞を授与
2013 年 5 月 8 日長嶋、松井両氏と首相夕食会
2013 年 5 月 9 日松井秀喜氏、ニューヨーク到着

これらの中で最もインパクトの大きな出来事は 「長嶋、松井両氏に国民栄誉賞を授与」で、 この出来事のあった 2013 年 5 月 5 日は連続型・列挙型どちらもバースト状態と検知出来ています。 それ以外のそれほどインパクトの大きくないニュースのあった日については、 連続型はバースト状態と検知できていますが、列挙型ではバースト状態を検知できていません。 逆に、連続型では、特に何もニュースのなかった 5 月 6・7 日についても バースト状態と検知しています。 これらのことから、「『松井』について、何か出来事があった日を検知したい」という見方では、 連続型では False Positive が起きていて、 列挙型では False Negative が起きているといえます。

次に、例 2 の時期 (2012 年 11 月 19 日〜21 日) について見てみます。 この時期には「松井」関連の出来事として、以下のことがありました。

日付イベント
2012 年 11 月 19 日日本維新・松井幹事長、減税日本との合流を重ねて否定
2012 年 11 月 20 日日本維新・松井幹事長、全「1区」擁立を断念 みんなの党と選挙区調整
2012 年 11 月 21 日日本維新の会幹事長の松井一郎大阪府知事は、前宮崎県知事の東国原英夫氏に衆院選への出馬を要請。

しかし、連続型で強いバーストの原因となったのは上記のどれでもなく、 以下の連続投稿が原因です。 11 月 20 日の 16:00 から 16:09 の短期間に、 同一アカウントから 13 ドキュメントもの投稿がなされています。

Tue Nov 20 16:00:38 +0000 2012 - 連投6   RT @******: 6、松井氏「党首討論で安倍総裁と野田総理が、議員定数削減についてやり取りしていたが、選挙が終わってからではなく、なぜ今やらないのかと疑問に思う。本気でやろうと思えば今できるはず。選挙終了後もやらないだろう」
Tue Nov 20 16:01:12 +0000 2012 - 連投 7   RT @******: 7、松井氏「民主党政権では0増5減も出来ていない。その状況で、霞ヶ関の職員たちに『やれ』と指示したところでやるわけがない。まずは政治主導。政治家が自ら身を切る覚悟をしっかり示すことで職員の意識は変わる」
Tue Nov 20 16:02:37 +0000 2012 - 連投8   RT @******: 8、松井氏「昨年『大阪府市統合本部』という『バーチャル大阪都』なる組織を作り、大阪府と市の二重行政を見直していっている。税金の無駄遣いを改めていく。例えば、大阪市の病院の建て替えという問題がある。(続く)」
Tue Nov 20 16:03:00 +0000 2012 - 連投9   RT @******: 9、松井氏「(続き)これを大阪市単体でやれば57億円掛かるが、府と合同でやれば市の負担は30億円で済む。周産期医療など子供達の命を守る最先端医療を実現する病院。周産期医療は黒字の病院経営は中々できない。(続く)」
Tue Nov 20 16:03:28 +0000 2012 - 連投10   RT @******: 10、松井氏「(続き)市単体でやる場合のランニングコストを年8億円見込んでいた。府と合同でやれば市の負担は年3億円で済む。大阪の子供達をしっかりと守っていく、安全に子供達が産まれて来れる医療ができようとしている」
Tue Nov 20 16:03:54 +0000 2012 - 連投11  RT @******: 11、松井氏「民主党は政権を獲った時に16兆円見つけると言っていたがどうだったか?事業仕分けはどうだったか?天下り法人を0にするのはどうだったか?どれも実現していない。大阪府と市は天下りを0にした(続く)」
Tue Nov 20 16:04:17 +0000 2012 - 連投12   RT @******: 12、松井氏「(続き)どのように実現したのか。府・市の補助金が年300万円以上の団体に人事監察委員会による厳しい承認が必要な制度を敷いた。役所で決めて、団体に行く人がすぐポストに座れるような仕組みは見直した」
Tue Nov 20 16:04:41 +0000 2012 - 連投13   RT @******: 13、松井氏「大阪でスタートさせた様々な改革。霞ヶ関や永田町でも、ぜひやりたい。そのために、大阪で日本の維新の会に『頑張って来い』というご支持を頂かないと。大阪でやっている改革を国でやろうと思えば議席が必要」
Tue Nov 20 16:05:03 +0000 2012 - 連投14   RT @******: 14、松井氏「大阪で改革がやれている理由。橋下市長の力もあるが、府議会で過半数を獲れているから議会で議決ができる。いくら良いことを言っても、国会で議席を得なければ皆様との約束を果たせない」#iwakamiyasumi
Tue Nov 20 16:05:32 +0000 2012 - 連投15   RT @******: 15、松井氏「世界との競争に勝ち抜く次の世代を作るために、ゆとり教育がゆるみ教育になってしまった教育の改革をやらねばならない。今後も私学の高校無償化を続ける。これに500億円もかかるが大阪府は5年連続で黒字」
Tue Nov 20 16:05:52 +0000 2012 - 連投16   RT @******: 16、松井氏「徹底した行革をやりながら、お金を産み出しながら、府民にツケを回さないようにしながら、子供達の世代にもしっかりとお金を使いながらの財政運営で、教育改革を実行中だ。国にもこういうことをやらせたい」
Tue Nov 20 16:06:16 +0000 2012 - 連投17   RT @******: 17、松井氏「国の1000兆円の借金を返していくことも考えねばならない。少子高齢化社会の中で、人生の先輩の医療と福祉を支えていくために、毎年3兆円ずつ必要財源が増えていく。次の世代にそのままツケを回すのか」
Tue Nov 20 16:06:44 +0000 2012 - 連投18   RT @******: 18、松井氏「日本維新の会は良いことばかり言えない。政治は正直であるべき。厳しい話もする。その前に政治改革をし議会や議員が身を切り役所改革もやる。皆様にも国を変える大戦(おおいくさ)に一緒に立ち上がってほしい」

「『松井』について、何か出来事があった日を検知したい」という見方に立つと これらの投稿は何らかのフィルタをかける必要があるものですが、 連続型ではこの連続投稿に対して過敏に反応して、強いバーストと出力されています。 サンプリングデータの中にたまたまこれらの連続投稿が含まれてしまったために、 それが強く現れてしまっているともいえます。 一方で、列挙型だと、1 日のタイムスケールでバーストを検知するので、 この連続投稿が「均されて」、それほど高くない weight 値として出力されています。 つまり、 「全データを取得できなく、一部分だけサンプリングしたデータを用いてバースト検知を行う」 ような場合は、列挙型のほうが適しているといえます。

別のキーワードを使つてみる

この章では、別のキーワード「長嶋」で 列挙型バースト検知を行ってみます。

列挙型バースト検知の、連続型にはない大きな利点として、 異なるキーワードで結果の比較が出来ることが挙げられます。 これは、列挙型では入力値として「全ドキュメント」情報を含めていることによります。 連続型の場合は関連ドキュメント以外のドキュメントは全て抜け落ちるので、 同じ全ドキュメントを用いていたとしても、 「『松井』関連ドキュメントでのバーストレベル」と、「『長嶋』関連ドキュメントでのバーストレベル」 の比較には意味がありません。

列挙型バースト検知を行った結果は、以下の通りになります。

CL-USER(9): test-batches        ; (全ドキュメント数 関連ドキュメント数) のリスト
((6041 0) (5881 0) (5297 0) (5315 0) (5837 0) (6148 0) (6402 0) (5906 0)
 (5760 0) (5396 0) ...)
CL-USER(10): (enumerate-kleinberg test-batches)  ; (ID1 ID2 Weight) のリスト
((56 58 5.3232927f0) (151 155 49.28622f0) (166 167 6.435025f0)
 (182 191 37.318264f0))

上出力は、バースト期間が以下の 4 つであることを示します。

期間バッチweight
2012-12-27/2856〜575.32
2013-04-01/04151〜15449.29
2013-04-161666.44
2013-05-02/10182〜18937.32

『松井』の結果と合わせると、 特に強いバースト期間上位 5 件は、以下のようになります。

キーワード期間バッチweight
松井2012-12-27/2956〜5874.40
長嶋2013-04-01/04151〜15449.29
松井2013-04-01/02151〜15240.37
長嶋2013-05-02/10182〜18937.32
松井2012-11-19/2118〜2020.42

このように、列挙型の場合は 「異なるキーワードで網羅的にバースト検知を調べる」 ような方法にも適しています。

まとめ

Kleinbergの列挙型バースト検知器は、「バースト期間」として、 連続型とほぼ同じ期間に対応するバッチ群を検知することができました。

また、連続型との比較の結果、 バーストの微視的な変化を詳しく知りたい場合は連続型が適していて、 巨視的にざっと把握したい場合は列挙型が適しているといえそうな事もわかりました。

さらに、 列挙型は、(連続型では扱えない)同時刻に発生した複数のイベントを扱えることを確認しました。

Reference

  1. Jon Kleinberg, "Bursty and Hierarchical Structure in Streams", 2002
  2. Kleinberg のバースト検知

Footnotes:

1 そもそもKleinberg自身には、最初のモチベーションとして、 「自身の蓄積するメールについて、巨大なアーカイブを作るためのより良い方法を知りたい」 という問題意識があったようです。

2 ある特定のキーワードwを含むドキュメントのことを、参考文献 1. では 「関連ドキュメント」と呼んでいます。

Author: 数理システム知識工学部

Date: 2014-05-20 13:56:11 JST

Generated by Org version 7.8.11 with Emacs version 24

© Mathematical Systems Inc. 2014