DEIM Forum 2013 A5-6

複数の移動平均における順序関係に基づくバースト検出吉本暁文†

数原良彦††

船越要††

鷲崎 誠司††† 奈良先端科学技術大学院大学情報科学研究科 〒 630–0192 奈良県生駒市高山町 8916–5†† 日本電信電話株式会社 NTT サービスエボリューション研究所 〒 239–0847 神奈川県横須賀市光の丘 1 番 1 号
E-mail: †akifumi-y@is.naist.jp, ††{suhara.yoshihiko,funakoshi.kaname,suzaki.seiji}@lab.ntt.co.jp
あらまし

実世界における盛り上がりをとらえるため，マイクロブログにおいて言及された実世界オブジェクトの頻度におけるバースト判定を用いることができる．しかし，地域によってマイクロブログにおける発言の絶対数に偏りが生じるため，頻度情報に基づく既存のバースト検出手法では閾値設定の問題があった．本研究では，複数の異なる期間における移動平均に着目し，異なる期間の移動平均の順序関係に基づくバースト判定手法を提案する．移動平均の順序関係に基づいてバースト判定を行うことで，閾値設定の問題を解決し，高精度に実世界の盛り上がりを捉えることが可能となる．本稿では Twitter データを用いて実世界オブジェクトに対するバースト判定を行い，提案手法の有効性を確認した．
キーワード

バースト検出，マイクロブログ，時系列データ

Akifumi YOSHIMOTO† , Yoshihiko SUHARA†† , Kaname FUNAKOSHI†† , and Seiji SUSAKI††† Graduate School of Information Science, Nara Institute of Science and Technology
8916–5 Takayama-cho, Ikoma, Nara, 630–0192 Japan†† NTT Service Evolution Laboratories, NTT Corporation
1–1 Hikari–no–oka, Yokosuka–shi, Kanagawa, 239–0847 Japan
E-mail: †akifumi-y@is.naist.jp, ††{suhara.yoshihiko,funakoshi.kaname,suzaki.seiji}@lab.ntt.co.jp
Key words burst detection, microblog, streaming data

1. は じ め にマイクロブログにおけるユーザの発言数の時系列に着目したとき，何らかの話題が盛り上がっている場合，それはユーザの発我々が日々利用している情報端末における通信品質の向上に言数の急激な増加として観測されるため，話題になっている出伴い，情報収集におけるスタイルが変わりつつある．ユーザ間来事の検出は発言数の時系列におけるバースト検出として捉えで情報をやりとりする場としてソーシャルメディアが広く普及ることができる．バーストとは，ある期間における数が通常とし，中でもマイクロブログは特にリアルタイム性が高く，実世大きく異なることを言い，このバーストの発生から終了までの界を観測する一種のセンサーとして考えられている [1]．こうし期間を検出することで実世界における盛り上がりを検出できる．

たマイクロブログにおける統計情報を利用することで，より高しかし，マイクロブログでは多様な話題が混在しているため，度な情報収集ができるようになる．本研究では，マイクロブロ

単に発言数のバースト検出を行うだけでは特定の話題の盛り上グにおいてこのような現実に起きている事態を検出するのに適がりを捉えることができない．そのため，従来のマイクロブロしたモデルを提案し，それが従来のモデルに比べて，マイクログを用いたバースト検出手法ではトピック検出を行い，トピッブログを通して実世界の出来事をより良く捉えることが可能でクごとにまとめられた発言数に対してバースト検出を行っていあることを示す．

る [2]．これに対し本稿では，発言の実世界における場所に対外出先での情報収集において，実世界で話題になっている出する紐付けを行ったデータを用いて，場所ごとのバースト検出来事が捉えられれば，ユーザはそれを参考に予定を決めるこを行う．これによりある場所に関係する話題を同じ場所の発言とができる．しかし，このような実世界の出来事をコンピューとしてまとめることができる．このようにすることで，トピッ

タによって直接観測することは困難であるため，ユーザ同士がク検出を行わずに実世界の盛り上がりを捉えることができる．

ソーシャルメディア上でコミュニケーションをとっている情報を観測することによってこれを予測することが考えられている．

A

B

20C

1816

元の頻度
14

移動平均(短)12

移動平均(長)123456

時刻頻度

頻度108642010元の頻度
8単位時間x2単位時間x56

図1

移動平均の関係42

本研究ではマイクロブログとして Twitter（注 1）を利用し，前処理として発言に対する実世界に存在するオブジェクトの対応付

012345678910111213141516

時刻けを行ったデータを用いる．オブジェクトの表記と緯度経度はWikipedia の情報を利用した．Twitter に元々備わっているジ

図2

元の頻度に対する敏感さの違い

オタグという緯度経度情報があるが，これが付与されている発言は非常に数が少ないため，このデータにおける場所の対応付けは発言内容から推定している．本稿ではこの場所の対応付けについては所与のものとし，提案手法の範疇外とする．

2. 関 連 研 究

3. 提 案 手 法
頻度の時系列から，時刻 t までの期間 A における単位時間あたりの頻度情報を計算することで，時刻 t における期間 A の移動平均を得る．

Kleinberg [3] のバースト検出手法は 2 つの連続して到着した

図 1 で，移動平均（短）は短い期間，移動平均（長）は長い事象の間隔が指数分布に従うと仮定して，無限状態オートマト期間における移動平均である．この例では時刻 t における移動ンを用いてバーストをモデル化している．状態遷移のコスト平均のうち，短い期間を時刻 t から t − 1 まで，長い期間を時刻と事象の到着時間の予測との差のコストを最小化する最適なt から t − 2 までと仮定する．すなわち，時刻 t における元の頻系列を計算するため，この手法は計算量が大きく，Twitter の度を c(t) としたとき，時刻 t と t − 1 における平均 c(t)+c(t−1)
2ような規模の大きなストリーミングデータでは扱いにくい [4]．

が移動平均（短）の値である．これに対し，時刻 t から t − 2Zhijian ら [5] のバースト検出手法ではパラメータとして通常における平均 c(t)+c(t−1)+c(t−2)
が移動平均（長）の値である．
3時の頻度の上限として閾値を設定し，この上限を超えた状態を元の頻度と移動平均（短），移動平均（長）のピークをそれバーストとする．この方法では，通常時の頻度の大小に応じてぞれ A，B，C に示す．A が本来の盛り上がりであり，バース異なる閾値を設定する必要がある．実世界における各場所の発ト検出においてこの時刻を含んだ範囲を検出することが望まし

言系列はその場所によって通常時の頻度が大きく異なるため，い．しかし B は A よりも後の時刻にあり，C はそれよりもさ

この手法では，実世界における各場所に対して個別に適切な閾らに後の時刻にある．このように，移動平均におけるピークは，値を設定しなければならず，場所の数に応じたパラメータが必

その移動平均の期間が長いほど元の頻度におけるピークの時刻要になり，利用が困難となる．

より遅くなりやすい．そのため，移動平均に対して閾値を用い一方で，株価におけるテクニカル指標から着想を得たバース
ト検出手法として MACD [4] がある．これは頻度の時系列に対てバースト検出を行うと，元の頻度のピークよりも遅れてバーストが検出される場合がある．

して長い期間の移動平均と短い期間の移動平均の差をとり，こ図 2 では，元の頻度と期間がそれぞれ単位時間 ×2，単位時の値の移動平均に対して現在の頻度が上回ればバーストであ間 ×5 の移動平均を示している．この例で単位時間 ×2 は単位ると判定する手法である．これにより，過去の値に基づいた判

時間 ×5 に比べて元の頻度に応じた頻度の変化が大きい．この定が可能となるため，通常時の頻度が異なる複数の時系列に対ように，移動平均の期間が短いほどノイズの影響を受けやすい．

して，別個にパラメータを用意する必要がなくなる．しかし，そこで提案手法では，複数の移動平均を用いてピークの遅れ過去の値が設定されたウインドウ幅に渡って上昇傾向にある場とノイズの影響を解決する．

合，現在の頻度が下降するとバーストでない状態と判定される．

異なる 2 つの期間における移動平均の場合，過去から現在に従って MACD によるバースト期間は閾値設定によるバーストかけて頻度が増加傾向にある場合は，移動平均（短）が移動平期間より短くなりやすい．また，実世界における盛り上がりの均（長）より大きくなりやすく，減少傾向にある場合はこの関開始時刻よりも検出された期間の開始時刻が遅れる問題がある．

係が逆になりやすい．図 1 の円で囲った範囲において，移動平均（短）と移動平均（長）の大小関係が移動平均（短）> 移動平均（長）となっている．このような，頻度が増加傾向にある（注 1）：https://twitter.com

60

Level 350

Level 240
頻度A+B+C+D

A+B+C

A+B

Level 1

30

Level 020

A

B+C+D

B+C
B

C+DC

D梅田10

図 4 Aggregation Pyramid

西武ドーム

00:30
2:00
3:30
5:00
6:30
8:00
9:30
11:00
12:30
14:00
15:30
17:00
18:30
20:00
21:30
23:00

きく設定することにより，移動平均 (短) の値が移動平均 (長)に比べて著しく大きくならない限り，バースト開始と判定されない．最長の移動平均の値が全ての移動平均に対して上回る時

時刻

刻を終了時刻とする．
図 3 絶対頻度の異なりバーストの範囲を検出するために，時刻 t がバーストの範囲時の移動平均の大小関係をバーストの開始，減少傾向にある時の移動平均の大小関係をバーストの終了として検出することで，円で囲った範囲をバーストとして検出するアルゴリズムを提案する．
図 3 は実世界オブジェクトにおける絶対頻度の異なり具合を示したものである．それぞれの時系列において，絶対頻度の値の大きさは異なるため，頻度に関する閾値をパラメータに要す
るバースト検出では時系列の数に応じた数のパラメータを用意しなければならない．複数の移動平均の関係を用いるバースト検出ではこのような閾値のパラメータを用いず，絶対頻度の異なりに特別な対応を必要としない．
時刻 t における単位時間あたりの頻度を cell(0, t) とする．ここで Twitter における単位時間は 1 分とする．単位時間よりも長い期間について，単位時間あたりの頻度数に換算したものを移動平均として保持する．ここで，例えばレベル 1 の移動平均は単位時間の 2 倍（すなわち 2 分），レベル 2 の移動平均は単位時間の 3 倍（すなわち 3 分）の期間における単位時間あたりの頻度とする．このときレベル i (ただし i >= 1) の移動平均cell(i, t) は (1) 式を用いて計算することができる．
cell(i, t) =1cell(0, t − n)i + 1 n=0

移動平均同士で短い期間における移動平均が上回るときとする．
終了条件は最長の移動平均が他の全ての期間の移動平均を上回るときとする．

3. 2 効率的な実装
複数の異なる期間における移動可算を同時に保持し，効率よく計算するためのデータ構造として Aggregation Pyramid(AP) [6] があり，時系列のデータにおけるバースト検出に用いられている．AP は図 4 に示すような N レベルによるピラミッド型のデータ構造で，サイズ N のウインドウ幅の時間に対するデータを保持する．レベル 0 は N 個のセルからなり，それぞれのセルが単位時間あたりの頻度情報を保持する．レベル L

3. 1 アルゴリズム

iXの開始か終了かを判定する．開始条件は全ての長さが隣り合うのセルは L + 1 個の，レベル 0 におけるセルの可算値を保持している．これにより AP は時系列における異なるウインドウ幅に対する可算値を同時に保持するデータ構造としての性質を持
つ．移動加算を単位時間あたりの頻度に変換することで，新たに到着した移動平均を O(N ) の計算量で更新できるため，移動平均を効率的に計算できる．

4. 評

価

我々の提案手法が実世界オブジェクトに対して頑健なバース(1)

このように，提案手法では異なる期間の移動平均における値の関係に基づいてバースト判定を行う．
提案手法では以下の開始条件を満たす時刻から，終了条件を満たす時刻までをバースト区間として抽出する．

ト検出手法であるかを確認するため，Twitter データに対して同手法を適用して評価を行う．

4. 1 データセット
2012 年 1 月 1 日から 6 月 30 日までにおける Twitter Public
Timeline 10% のデータのうち日本語ツイートに対して実世界オブジェクトの対応付けを行った．実世界オブジェクトの対応付けには，日本語 Wikipedia のうち，緯度経度情報を持つ見出

開始条件∀i ∈ {i ∈ Z+ |i < h}cell(i, t) > cell(i + 1, t) · weight(i, i + 1)
終了条件
∀i ∈ {i ∈ Z+ |i < h}cell(h, t) > cell(i, t)

し語 30,105 件と対応する緯度経度を利用した．これらの見出
し語を含むツイートを，当該実世界オブジェクトに言及していると仮定し，実世界オブジェクトの頻度情報としてカウントした．これにより，各実世界オブジェクトに対して約 6ヵ月間のツイート頻度の時系列情報を得た．すなわち，30,105 件の時系列データであり，提案手法を適用する際には 30,105 個の APを用いることとなる．

ここで Z+ は自然数集合 (0 を含む)，h はあらかじめ設定し4. 2 実 験 条 件

た移動平均の最大レベル，weight(i, i + 1) は異なる期間の移動

ベースラインとして，移動平均に対する閾値に基づく検出と，平均の順序関係に対する重みを表す．この重みパラメータを大頻度の変化量に対する閾値に基づく検出を用いた．閾値につい図 5 実験結果：2012 年 4 月 5 日大森北ては複数のパラメータを利用し，比較を行った．利用したパラメータについては結果で述べる．

4. 3 結果

認できる．

5. ま と め

提案手法の有効性を確認するため，2012 年 4 月 6 日の「大本稿では，実世界における盛り上がりをとらえるため，マイ森北」に対するバースト検出結果を図 5 に示す．図 5 においてクロブログにおいて言及された実世界オブジェクトの頻度におy 軸は時刻を表し，折れ線が単位時間あたりの頻度を表す．長けるバースト判定に適したバースト検出手法を提案した．提方形で示した範囲が各手法によるバースト検出範囲を示す．複案手法では，単位時間あたりの頻度情報を元に計算した異な数のパラメータの結果を視覚的に表示するため，長方形の高さる期間の移動平均の順序関係に基づいてバースト判定を行う．

を変化させているが，長方形の高さ，すなわち x 軸に定量的なTwitter データを用いて実世界オブジェクトの言及数に対する意味合いは無いことに注意する．

バースト判定を行い，提案手法を用いて頑健なバースト判定が図 5 に示す凡例の読み方を説明する．単 > ∗ と記述された手法は単純頻度に対する閾値に基づくバースト検出手法で，右側の値を超えた場合にバーストと判定する．以降，単純頻度に対する閾値に基づくバースト検出手法を「単」と呼ぶ．差 > ∗ と記述された手法は，単純頻度の変化量，すなわち差分に対する閾値に基づいてバースト検出手法で，差分が右側の値を超えた場合にバーストと判定する．以降，差分に対する閾値に基づくバースト検出手法を「差」と呼ぶ．最も低い長方形で表現されたバースト判定範囲が提案手法によるものである．それ以外の手法については，考察に影響を与えないため，説明を省略する．
それぞれの手法に対するバースト検出結果について述べる．
単 > 10 から単 > 70 は元の頻度において閾値がその値を上回った範囲，同様に差は元の頻度の現在と直前の単位時間の差分における閾値，AP 頂点は AP の頂点セルにおける閾値となっている．
「単」手法をパラメータ毎に比較すると，閾値が 10 のような低い値でなければ再現率が低い．
「差」手法をパラメータ毎に比較すると，範囲では，絶対頻度が低い場合には低い閾値でもほとんど検出されていない．提案手法ではバーストの開始には最も早く反応し，途中一時的に頻度の下がる時刻でもバースト範囲を維持し，大きな頻度低下によってバースト範囲を終了しており，頑健なバースト検出のの性質を備えていることが確可能であることを確認した．
文

献[1] Sakaki Takeshi, Okazaki Makoto and Matsuo Yutaka,
Earthquake shakes twitter users: real-time event detection by social sensors , In Proceedings of19th International
Conference on World Wide Web, pp. 851-860, 2010.
[2] Qiming Diao, Jing Jiang, Feida Zhu and Ee-Peng Lim,
Finding bursty topics from microblogs , In Proceedingsof the 50th Annual Meeting of the Association for Computational Linguistics, pp. 536-544, 2012.
[3] Jon Kleinberg,Bursty and hierarchical structure instreams , In Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data
Mining, pp. 91-101, 2002.
[4] Dan He and D. Stott Parker, Topic dynamics: an alternative model of bursts in streams of topics , In Proceedingsof the 16th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 443-452, 2010.
[5] Zhijian Yuan, Yan Jia and Shuqiang Yang, Online burst
detection over high speed short text streams , In Proceedings of the 7th international conference on ComputationalScience, pp. 717-725, 2007.
[6] Xin Zhang and Dennis Shasha, Better burst detection ,In Proceedings of 22nd International Conference on DataEngineering, pp. 146, 2006.