Kleinberg のバースト検知

はじめに

時系列データにおいてイベントが急激に増加したことを検出する手法の一つである、Jon Kleinberg のバースト検知アルゴリズムを紹介します。

Jon Kleinberg が考案したバースト検知のアルゴリズムは、 Bursty and Hierarchical Structure in Streams に示されています。 この手法を用いることによって、例えば、あるマイクロブログサービス上で、 ある話題がどの程度の期間、どの程度の盛り上がりをみせたのかを捉えることができます。

バースト検知

バースト検知とは時系列データに対する異常検出の一つで、 イベントの集中的な発生を検出することを言います。 例えば、マイクロブログサービス上で、 ある単語(商品名など)に対する投稿が急激に増えることがあります。 このような現象を「バースト」と呼び、 これを検出する用途にバースト検知は使われます。

バーストを自動的に検出できるようになれば、 バースト検知の手間を大幅に削減することが可能となり、 結果としてバースト発生時の状況を効率よく解析することができるようになります。

Kleinberg のバースト検知

Kleinberg は Bursty and Hierarchical Structure in Streams の中で、2つのバースト検知の手法を示しています。 一つ目の方法は、時々刻々と発生する連続的な時系列のイベントに対する手法(以下「連続型」と呼ぶ)、 もう一つは、単位時間毎に発生したイベントを数え上げた離散的な時系列のデータに対する手法です。

どちらの手法も、バーストのレベルを表現したオートマトンを使用します。 時系列データの各要素に対してバーストレベルが 1 つ定まります。 時系列データの各要素におけるバーストレベルはコスト関数を用いて計算され、 コスト関数の値が最も低いレベルがその要素に割当てられます。

../image/automaton.png

コスト計算によるバーストレベルの選択(連続型の場合)

Kleinberg バースト検知の特徴

Kleinberg のバースト検知では、時系列データの各要素毎に確率モデルを定義しています。 確率モデルは、時系列データの次の要素におけるバーストレベルの計算に使用しているだけであるため、 「異常を検出する」という性質上、 観測期間を通して確率モデルの仮定を置くことが難しいデータに対して、 特に適した手法と言えます。

もう一つの特徴としては、 一時的なバーストに反応しにくいアルゴリズムであることがあげられます。 このアルゴリズムは、バースト方向よりも、同じもしくは定常方向に遷移しやすい性質があるため、 一時的なバーストに反応しにくくなっています。

Kleinberg のバースト検知例

統計・機械学習パッケージ CLML のバースト検知ライブラリを使用して、Kleinberg の連続型のバースト検知による実行例を示します。

データの準備

あるマイクロブログサービスへの 2012年11月1日 から 2013年5月14日 までの投稿内容と投稿時刻から、時系列データを作成しました。 投稿内容に「長嶋」「松井」「長嶋と松井」を含む場合を 1、含まない場合を 0 として、 時系列データファイル burst-nagashima-matui.sexp に保存しました。保存したファイルの一部を以下に示します。

(("time"                      "長嶋" "松井" "長嶋&松井")
 ("2012-11-01T08:10:43+09:00"  0      1      0)
 ("2012-11-01T11:58:32+09:00"  0      1      0)
 ("2012-11-01T20:37:18+09:00"  0      1      0)
 ("2012-11-01T20:33:52+09:00"  0      1      0)
 ("2012-11-02T06:31:04+09:00"  0      1      0)
 ("2012-11-04T15:43:26+09:00"  0      1      0)
 ("2012-11-05T11:27:31+09:00"  0      1      0)
 ...
)

このファイルを読み込んで、CLML の時系列データ構造を作成します。

TS-BURST-DETECTION(17): (setf ts
                          (time-series-data (read-data-from-file "sample/burst-nagashima-matsui.sexp")
                                            :time-label 0
                                            :except '(0)))
#<TIME-SERIES-DATASET >
DIMENSIONS: 長嶋 | 松井 | 長嶋&松井
TYPES:      NUMERIC | NUMERIC | NUMERIC
NUMBER OF DIMENSIONS: 3
FREQUENCY:  1
START:      (1 1)
END:        (976 1)
POINTS:     976
TIME-LABEL: time
TS-BURST-DETECTION(18): 

「長嶋」のバースト検知

作成した時系列データ構造の「長嶋」列のデータ(1次元目のデータ)を使用してバースト検知を行い、その結果をグラフに表示してみます。 このグラフでは、左側にバーストレベルが変化した時刻が表示され、 右側にバーストレベルが "+" の数で記されます。

TS-BURST-DETECTION(18): (setf bi
                          (continuous-kleinberg ts
                                                :time-reader #'date-time-to-ut
                                                :if-overlap :delete
                                                :column-number 0))
((0 "2012-11-13T20:09:25+09:00") (0 "2012-11-22T21:09:32+09:00")
 (0 "2012-11-22T21:22:11+09:00") (0 "2012-12-07T12:32:43+09:00")
 (0 "2012-12-10T21:40:09+09:00") (0 "2012-12-16T09:11:00+09:00")
 (0 "2012-12-28T07:31:06+09:00") (2 "2012-12-28T07:31:07+09:00")
 (2 "2012-12-28T08:45:23+09:00") (2 "2012-12-28T11:55:39+09:00") ...)
TS-BURST-DETECTION(19): (print-burst-indices bi)
2012-11-13T20:09:25+09:00 |
2012-12-28T07:31:06+09:00 |++
2012-12-28T22:15:02+09:00 |
2013-04-01T15:11:01+09:00 |+++++++
2013-04-01T22:00:00+09:00 |++++
2013-04-02T07:42:01+09:00 |+++
2013-04-03T09:10:27+09:00 |++
2013-04-04T16:56:16+09:00 |
2013-04-16T10:12:03+09:00 |++
2013-04-16T18:55:03+09:00 |
2013-05-02T13:39:07+09:00 |+
2013-05-05T05:18:03+09:00 |+++
2013-05-05T12:55:24+09:00 |+++++
2013-05-05T13:48:03+09:00 |++++++++
2013-05-05T14:01:07+09:00 |+++++++
2013-05-05T14:11:01+09:00 |++++++
2013-05-05T14:55:02+09:00 |+++++
2013-05-05T22:41:08+09:00 |++++
2013-05-06T00:21:07+09:00 |+++
2013-05-09T00:01:50+09:00 |++
2013-05-09T18:05:02+09:00 |
2013-05-14T04:55:05+09:00 |
NIL
TS-BURST-DETECTION(20):

バーストレベルの高い日に何があったのかを調べてみると、次のようなイベントがありました。

日付イベント
2012-12-28松井の引退表明
2013-04-01長嶋・松井に国民栄誉賞授与を検討
2013-04-16長嶋・松井に国民栄誉賞授与正式決定
2013-05-05東京ドームで授与式

この結果から、「松井の引退表明 によって"長嶋"を含む投稿が増えた」という関連性が見えます。 また、国民栄誉賞の授与式 は、 その発表があった時以上にバーストし、 授与式が終わった後も数日間、話題となって盛り上がっていたことがわかります。

「松井」のバースト検知

一方、「松井」のデータ(2次元目のデータ)についてはどのような結果になるでしょうか。解析してみます。

TS-BURST-DETECTION(20): (print-burst-indices
                         (continuous-kleinberg ts
                                               :time-reader #'date-time-to-ut
                                               :if-overlap :delete
                                               :column-number 1))
2012-11-01T08:10:43+09:00 |
2012-11-19T07:27:38+09:00 |+
2012-11-20T11:13:36+09:00 |++
2012-11-21T00:12:01+09:00 |++++
2012-11-21T00:59:14+09:00 |+++++++
2012-11-21T01:06:44+09:00 |++++
2012-11-21T01:33:00+09:00 |+++
2012-11-21T12:39:01+09:00 |+
2012-11-21T16:18:00+09:00 |
2012-12-01T05:54:01+09:00 |+
2012-12-03T00:09:19+09:00 |
2012-12-05T17:11:03+09:00 |+++
2012-12-05T19:40:00+09:00 |+
2012-12-05T21:48:01+09:00 |
2012-12-17T13:36:45+09:00 |+
2012-12-18T15:33:00+09:00 |
2012-12-27T23:03:15+09:00 |+
2012-12-28T01:24:06+09:00 |++++++
2012-12-28T01:57:32+09:00 |++++
2012-12-28T05:55:28+09:00 |+++++
2012-12-28T06:51:02+09:00 |++++++
2012-12-28T08:55:49+09:00 |+++++
2012-12-28T09:04:57+09:00 |++++
2012-12-28T22:15:05+09:00 |+++
2012-12-29T00:14:08+09:00 |++
2012-12-29T21:53:06+09:00 |
2013-04-01T13:31:53+09:00 |++
2013-04-01T14:45:16+09:00 |++++
2013-04-01T15:11:01+09:00 |+++++
2013-04-01T22:00:00+09:00 |++
2013-04-02T11:21:55+09:00 |+
2013-04-03T19:50:46+09:00 |
2013-05-02T18:31:02+09:00 |+
2013-05-05T12:55:28+09:00 |+++
2013-05-05T13:48:03+09:00 |++++
2013-05-05T15:12:27+09:00 |+++
2013-05-06T00:55:11+09:00 |+
2013-05-10T01:10:10+09:00 |
2013-05-14T23:42:42+09:00 |
NIL
TS-BURST-DETECTION(21):

「松井」に関しては、 5/5 の東京ドームで授与式 よりも 長嶋・松井に国民栄誉賞授与を検討 の方がバーストしており、更に 引退表明 の方がバーストしていたことがわかります。

なお、11/21 のバースト は、 日本維新の会の松井一郎幹事長に関する投稿によるバーストでした。

検証

では、正しくバーストを検出できているのか、元のデータと比較して検証してみます。

以下は、「長嶋」を含む投稿の1日ごとの投稿数(青線)と、 Kleinberg の連続型のバースト検知で得られたバーストレベル(赤線)のグラフです。

../image/burst-nagashima.png

投稿数の増減に合わせてバーストレベルが変動していることがわかります。 ただし、投稿数の小さな増減に対しては反応せず、定常状態を維持しています。 また、1日ごとの投稿数としては 5/5 よりも 4/1 の方が多いにもかかわらず、 5/5 は短時間に集中して投稿が行われたために 4/1 よりも高いバーストレベルを得ることができています。 これらのことから、バースト検知として精度の良いものと言えるでしょう。

まとめ

このレポートで使用したデータに関して言えば、 Kleinberg の連続型のバースト検知は非常に精度の良いものでした。

バースト検知のアルゴリズムはいくつかありますが、 離散的な時系列データを使用するアルゴリズムでは、 その時系列データの時間間隔をどのように設定するか(1時間なのか1日なのか)によって、 結果に違いが出てきてしまいます。 その点、Kleinberg の連続型のバースト検知アルゴリズムでは時間間隔を考慮する必要がないため、 よりバースト検知に適した手法であると言えるでしょう。

ただし、利用するうえで気をつけなければならない点があります。

まず、異なる時系列データ間でバーストレベルを比較することに意味がありません。 バーストレベルは解析対象となる時系列データの中で相対的に決められるものだからです。 つまり、先に示した「長嶋」と「松井」のバースト検知の結果で 5/5 の授与式のバーストレベルを比較し、「長嶋の方が松井よりバーストしていた」と言うことはできません。

また、同じ時刻のデータ(前後の時間の差が0になるデータ)がある場合、コスト計算の過程で無限大が出てくるため、 正しく計算することができません (CLML では同時刻のデータを削除する機能が付いています)。

Kleinberg の連続型のバースト検知アルゴリズムを利用するにあたって、 このようにいくつか気をつけなければならないことはありますが、 精度の良い結果を得られるバースト検知アルゴリズムだと思います。

Reference

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

Date: 2013-05-31T18:39+0900

Generated by Org version 7.9.2 with Emacs version 24

© Mathematical Systems Inc. 2013