DEIM Forum 2012 F5-5

時系列トピックモデルにおけるバーストの同定
高橋 佑介†1横本大輔†1神門典子†5福原宇津呂武仁†2知宏†6中川吉岡真治†3河田裕志†7清田陽司†7容英†4†1 筑波大学大学院システム情報工学研究科 〒 305-8573 茨城県つくば市天王台 1-1-1†2 筑波大学システム情報系知能機能工学域 〒 305-8573 茨城県つくば市天王台 1-1-1†3 北海道大学大学院 情報科学研究科 〒 060-0808 北海道札幌市北区北 8 条西 5 丁目
†4 (株) ナビックス 〒 141-0031 東京都品川区西五反田 8-3-6†6 独立行政法人 産業技術総合研究所 サービス工学研究センター 〒 135-0064 東京都江東区青梅 2-3-26†5 国立情報学研究所 〒 101-8430 東京都千代田区一ツ橋 2-1-2†7 東京大学 情報基盤センター 〒 113-0033 東京都文京区本郷 7-3-1あらまし 本論文では，時系列ニュースを対象として，情報集約を行うための二種類の方式として，バースト解析およびトピックモデルの 2 つの手法の考え方を組み合わせることにより，トピックのバーストを検出する方式を提案する．
時系列ニュースにおけるバーストとは，世の中における特異な出来事に対応して，ある時期からその出来事に関連するニュース記事が急激に増加する現象を指す．バーストを検出するための代表的な手法として，Kleinberg のバースト解析が挙げられる．この手法においては，一般的に，バーストの検出はキーワード単位で行われる．一方，文書集合におけるトピックの分布を推定するものとして LDA (latent Dirichlet allocation) や DTM (dynamic topic model) に代表されるトピックモデルがある．トピックモデルを適用することにより，ニュース記事集合全体の情報を，いくつかのトピックに集約することができる．以上の既存技術をふまえて，本論文では，DTM を用いて推定したトピックに対して Kleinberg の手法を適用することで，トピック単位のバーストが検出可能であることを示す．
キーワード 時系列ニュース, トピック，バースト, 集約

Identifying Bursts in Time Series Topic Model
Yusuke TAKAHASHI†1 , Daisuke YOKOMOTO†1 , Takehito UTSURO†2 , Masaharu
YOSHIOKA†3 , Yasuhide KAWADA†4 , Noriko KANDO†5 , Tomohiro FUKUHARA†6 , Hiroshi
NAKAGAWA†7 , and Yoji KIYOTA†7†1 Grad. Sch. of Systems and Information Engineering, University of Tsukuba, Tsukuba, 305-8573, Japan†2 Faculty of Engineering, Information and Systems, University of Tsukuba, Tsukuba, 305-8573, Japan†3 Grad. Sch. of Information Science and Technology, Hokkaido University, Sapporo, 060-0808, Japan†4 Navix Co., Ltd. Tokyo 141-0031, Japan†6 Center for Service Research, National Institute of Advanced Industrial Science and Technology,Tokyo, 135-0064, Japan†5 National Institute of Informatics, Tokyo 101-8430, Japan†7 Information Technology Center, University of Tokyo, Tokyo 113-0033, Japan
Key words time series news, topic, burst, aggregation

1. は じ め に
現代の情報社会においては，多種多様な情報が氾濫し，いわゆる情報爆発の問題が深刻であり，氾濫する情報の集約や，俯瞰を行うための技術の確立が強く望まれている．中でも，情報爆発が最も顕著に現れているのはウェブであり，ウェブ上の情図 1 時系列ニュースにおけるトピックのバースト報爆発の問題に取り組んだ研究が盛んに行われている．例えば，バースト解析の技術においては，ストリームデータの時間軸方向の密度から世の中の異変や特異な出来事を捉えることができ

2. Kleinberg のバースト解析アルゴリズム
本研究では，Kleinberg の考案したバースト解析アルゴリズ

る．また，別のアプローチとして，トピックモデルのように文ム [5] を用いた．このアルゴリズムを用いることで，文書スト書集合における主要なトピックを推定することのできる技術もリーム中のあるキーワードのバースト期間と非バースト期間と存在する．

を自動で切り分け，各キーワードに対してバースト度を付与す

バースト解析は，一般には，電子メールやウェブ上のニューることが可能になる．

ス記事のようなストリームデータに対して適用される．そこで

2. 1 enumerating バースト

は，ある時からある話題に関する記述が急激に増加するようなenumerating バーストのアルゴリズムは，離散時間で送られ現象が起こることがあり，こういった現象を，ある話題に関する文書の集合に対して適用される．本稿では，各日ごとのニューるバーストと呼ぶ．代表的なアルゴリズムである Kleinberg のス記事集合を一つの文書集合の単位とし，以下では単に，記事バースト解析 [5] では，時系列に沿った各キーワードのバース集合と呼ぶ．

ト度の変化や，バーストしているか否かの判定，バースト度によるキーワードのランク付けをすることができる．

最も簡単なモデルでは 2 状態オートマトン A2 を定義し，2つの状態を非バースト状態 q0 ，バースト状態 q1 とおく．入力

一方，トピックモデルにおいては，文書が生成される背景にに対して状態が遷移することにより，2 つの状態を切り分ける．

は，潜在的にいくつかのトピックがあることを想定し，文書の目的とする記事（注 1）を「関連記事」，そうでない記事を「非関連生成尤度を高めるようにモデルのパラメータを訓練する．ト記事」として扱い，バーストか否かは，記事集合中の関連記事

ピックモデルの一種である DTM (dynamic topic model) [3] にの割合によって決まる．

おいては，時系列情報を持つ文書集合を情報源として，時系列解析期間において，m 個の記事集合 B1 , . . . , Bm が離散時間にそって，各単位時間ごとに，文書ごとのトピックの分布と，で送られてくる状況を考える．t 番目の記事集合を Bt とし，そトピックごとの語の分布を求めることができる．の記事集合に含まれる記事の数を dt とおく．文書集合には関以上をふまえて，本論文では，キーワードではなくトピックを対象としてバースト解析を行うことを目的とする．具体的に連記事と非関連記事が含まれ，Bt に含まれる関連記事の数をm

rt とおく．解析期間における全ての記事の数 D は D =は，DTM によって解析期間におけるトピックの分布を推定し，提案手法に基づいて各トピックの関連文書数を定義する．これにより，トピックに対して Kleinberg のバースト解析手法が適用できるようになる．
実際に，ウェブ上の時系列ニュースを対象にして本手法を適用することにより，図 1 に示すように，特定の期間において集中して記事が観測されるチリ地震やバンクーバー五輪に関するバーストを，トピックの単位で検出することができるようになった．

dt ，
t=1m

解析期間における全ての関連記事の数 R を R =rt と表す
t=1

ことができる．
次に，オートマトンの 2 状態にそれぞれ期待値を割り当てる．
初期状態である非バースト状態 q0 には，解析期間全体から算出した期待値 p0 = R/D を割り当てる．バースト状態 q1 には，p0 にパラメータ s をかけた値である p1 = p0 s を割り当てる．
（注 1）：例えば，特定のキーワードを含む記事．

表 1 DTM によって推定されたトピック (3 月 1 日時点)
人手でトピックにp(w|z) の高いキーワード付与したラベル（上位 10 キーワード）

経済

ドル，ユーロ，上昇，市場，動き，相場，円高，売買，発表，取引トヨタリコール事件

トヨタ，リコール，問題，社長，公聴会，トヨタ自動車，米国，無償，中国，加速選手，女子，日本，バンクーバー，3 月 1 日，日本時間

バンクーバー五輪

バンクーバー五輪，銀メダル，大会，男子

自然現象

津波，チリ，メートル，被害，午後，沿岸，午前，地震，センチ，発生

日本の政治

首相，政府，予算，国会，民主党，政策，衆院，法案，審議，方針

小沢一郎違法献金疑惑

民主党，北教組，選挙，自民党，参院選，幹事長，議員，政治，資金，事件

海外の政治

中国，大統領，米国，日本，政府，北朝鮮，関係，交渉，禁煙，国際企業

社長，企業，販売，会社，開発，生産，日本，発表，大手，工場

企業の業績

10，カ月，発表，連続，価格，01，26，12 月，20，00

交通

運転，事故，キロ，合わせ，午後，午前，自転車，東京，メートル，時間

裁判

被告，判決，裁判員，裁判，事件，被害者，裁判長，男性，懲役，検察

スポーツ，製品情報

ネット，サイト，インターネット，発売，携帯電話，パソコン，サービス，機能，発表，情報

普天間問題

知事，問題，政府，米軍，沖縄，首相，受け，沖縄県，外相，普天間

芸能

監督，映画，作品，放送，舞台，東京，人気，ドラマ，午後，主演

刑事事件

容疑者，容疑，逮捕，事件，女性，捜査，県警，男性，死亡，発表

地域

販売，合わせ，イベント，店舗，商品，人気，発売，作品，デザイン，東京

学校，コラム自分，子ども，生徒，学校，参加，家族，ながら，児童，受け，しょう

社会

対象，受け，調査，採用，制度，年度，学生，以上，企業，期間

医療

病院，患者，受け，医師，医療，研究，教授，検査，発表，手術

地方の行政

年度，市長，地域，計画，施設，予算，議会，県内，自治体，整備

ただし，s > 1 であり，p1 <= 1 となるような s でなくてはなら

態の系列 q を通るためのコスト関数を定義する．

ない．s の値が小さいほど，記事集合中の関連記事の割合が低くてもバーストと見なされやすくなる．
解析は，m 個の記事集合が与えられたときの，状態の系列を通るためのコスト計算によって行う．考えられる状態の系列のうち，最も系列のコストが小さいものが解となり，その系列の状態に応じて，バースト期間と非バースト期間を決定する．
状態遷移は dt と rt が入力となって決まる．状態の系列は

q = (qi1 , . . . , qim ) と表され，qim は，m 番目の記事集合によって決定された状態 qi (i = 0, 1) である．記事集合中の関連記事が二項分布 B(dt , pi ) にしたがって現れるという考えに基づき，状態 qi にいることに対してコストを与える関数 σ(i, ri , dt ) を以下のように定義する．

σ(i, rt , dt ) = − lnd t rtp (1 − pi )dt −rtrt im−1c( q | rt , dt ) =m

τ (it , it+1 )+t=0

σ(it , rt , dt )t=1

オートマトン A2 は二つのパラメータ s，γ によって決まることから，A2s,γ と表記される．本実験では，s = 2，γ = 1 として A22,1 のオートマトンを用いている．

2. 2 キーワードのバースト度
Kleinberg のバーストアルゴリズムでは，ある期間における各キーワードのバーストの強さを表す尺度としてバースト度を用いる．
期 間 tk , . . . , t l に お け る キ ー ワ ー ド w の バ ー ス ト 度

bw(tk , tl , w) は以下の式で定義される．
tl

σ(0, rt , dt ) − σ(1, rt , dt )bw(tk , tl , w) =t=tk

ただし，閾値付近の入力が続くなどして頻繁に状態遷移が起こ

なお，今回 は 1 日ごとに バース ト度を 算出 してい るため ，ると，途切れ途切れにバースト状態と非バースト状態が切り替

tk = tl ( = t) である．したがって，その際のバースト度はわり不自然である．そこで，現在の状態 qi から次の状態 qj へ，次のように表すことにする．

状態遷移を妨げるための関数 τ (i, j) を定義する．

τ (i, j) =(j − i)γ0

(j > i)(j <= i)τ は，パラメータ γ によって調節されるが，特に理由がない場
合は γ = 1 とする．

bw(t, w) = bw(t, t, w)

3. トピックモデル
本研究では，トピックモデルとして DTM (dynamic topicmodel) [3] を用いる．DTM は，語 w の列によって表現される

以上に述べた，ある状態 q にいることに対してコストを与え時間情報を含んだ文書の集合と，トピック数 K を入力とし，各る関数 σ と，状態遷移にペナルティを課す関数 τ を使って，状単位時間について，各トピック zn (n = 1, . . . , K) における語

w の確率分布 p(w|zn ) (w ∈ V ) ，及び，各文書 b におけるト表 2 バースト同定結果に対する主観評価
検出した

ピック zn の確率分布 p(zn |b) (n = 1, . . . , K) を推定する．こ期間

こで，V は文書中に出現する語の集合である．

正解数

適合率

820.75の数

DTM は，潜在的ディリクレ配分法 (LDA, Latent Dirichlet2010 年

Allocation) [4] とは異なり，文書集合中の時系列情報を考慮しているため，日付等の単位時間を超えて同一トピックを追跡可

バースト

2月1日

109〜3 月 31 日

能である．
本 論 文 で は ，p(w|zn ) (w ∈ V ) ，及 び ，p(zn |b) (n =1, . . . , K) の推定においては，Blei らによって公開されたツール（注 2）を用いた．ハイパーパラメータ α と，トピック数 K は，それぞれ α = 0.01，K = 20 とした．

ワードのうち上位 10 キーワードを示す．なお，DTM では各日ごとにトピックがもつ語の確率分布が変化するが，今回の解析期間において p(w|z) の高い上位 10 キーワードは各日ごとに大4. トピックモデルのバースト解析方式きく変化しなかったため，表 1 においては，2010 年 3 月 1 日

Kleinberg のバースト解析は，各日における文書数 dt と，その日の関連文書数 rt を入力として，解析期間におけるバースト状態と非バースト状態を切り分けて出力する手法である．したがって，Kleinberg の手法を用いてトピックのバーストを測るためには，各日における各トピックの関連文書数 rt が得られれば良い．そこで，本手法ではトピック zn の関連文書数 rt を以下のように定義することで，トピックのバースト解析を行う．

p(zn |b)rt =たトピックのラベルと，各トピックについて p(w|z) の高いキー

時点のキーワードを示す．

5. 2 トピックのバーストの同定「バンクーバー五輪」，「自然現象」，「経済」，「社会」の 4 つのトピックに対して，本手法を用いてバーストの同定を行った結果を図 2 ∼ 図 5 に示す．図 2 からは，バンクーバー五輪の開催期間中に正しくトピックのバーストが検出されている様子が「自然現わかる．また，図 3 からは，地震などが発生した際に，象」のトピックがバーストしていることがわかる．一方，図 4，「経済」，「社会」のよう毎日定常的に報道
および，図 5 からは．

b

されるトピックが，期間全体を通してバーストしていない様子m

これより，解析期間における全ての関連記事数 R =rt が求t=1m

dt でまり，それを解析期間における全ての記事の数 D =t=1がわかる．
以上のことは，本手法を用いることにより，時系列ニュースにおいて，あるトピックについての報道が頻繁に行われている期間を，トピックのバーストとして検出可能であることを示し割ることにより，解析期間全体における期待値 p0 = R/D を算ている．各日におけるバースト同定結果が適切であるか否かに出する．

ついて主観評価を行った結果を表 2 に示す．

また，これにより期間 tk , . . . , tl におけるトピック zn のバー
スト度 bz(tk , tl , zn ) を以下の式により算出することができる．

2010 年 2 月 1 日 ∼ 3 月 4 日の期間において，「トヨタリコール事件」，「小沢一郎違法献金疑惑」，「バンクーバー五輪」，「自tl

σ(0, rt , dt ) − σ(1, rt , dt )bz(tk , tl , zn ) =5. 3 トピックのバースト度

t=tk

然現象」の 4 つのトピックのバースト度 bz(t, zn ) をプロットしたものを図 6 に示す.

なお，今回は 1 日ごと にバー スト度 を算出 して いるた め，

図より，2 月 5 日付近では，「小沢一郎違法献金疑惑」，「トヨtk = tl ( = t) である．したがって，その際のバースト度はタリコール事件」のバースト度が他のトピックよりも高くなっ次のように表すことにする．ていることがわかる．しかし，バンクーバー五輪が開催された

bz(t, zn ) = bz(t, t, zn )

5. 分

析

2 月 13 日付近からは，「バンクーバー五輪」がもっともバースト度の高いトピックなっており，さらにその後の 3 月 1 日付近「バンでは，2 月 27 日にチリで発生した大地震の影響により，クーバー五輪」を抑えて「自然現象」のトピックが上位になっ対象とした解析期間は，2010 年 2 月 1 日 ∼ 3 月 31 日であている様子がわかる．このことからわかるように，トピックの（注 3）

バースト度の尺度を用いることで，バーストするトピック間の5. 1 DTM によるトピックの推定優劣を定量化することができ，さらにその優劣が時系列方向にはじめに，解析期間におけるニュース記事データに対して変動する様子を観測することができる．

る．

DTM を用いてトピック推定を行った．表 1 に，人手で付与し（注 2）：http://www.cs.princeton.edu/~blei/topicmodeling.html

6. 関 連 研 究
文献 [8] では，キーワードのバースト度から，各日におけるト（注 3）：日経新聞 (http://www.nikkei.com/)，朝日新聞 (http://www.asahi.

ピックのバースト度を算出する手法を提案している．具体的にcom/)，読売新聞 (http://www.yomiuri.co.jp/) の各新聞社のサイトから収集

は，DTM を用いて各日のトピックごとの各キーワードの条件した 6,710 記事，10,976 記事，および，9,117 記事の合計 26,896 記事．

図 2 トピック「バンクーバー五輪」におけるバーストの同定結果

図 3 トピック「自然現象」におけるバーストの同定結果

図 4 トピック「経済」におけるバーストの同定結果

図 5 トピック「社会」におけるバーストの同定結果付き確率と，その日におけるキーワードのバースト度との積のるか否かの判定は，その日のバースト度が閾値を超えたか否か和を求める．また，ある日においてトピックがバースト状態あによって行なっている．そのため，人手でバースト度の閾値を図 6 トピックのバースト度の時系列推移調整する手順を経る必要がある点が短所となる．一方，本研究スにおけるトピックの特徴やトピック同士の相関関係をいっそでは，トピックの関連文書数を定義することにより，Kleinbergう明らかにできることを示した．提案手法の詳細な評価項目との提案するキーワードのバースト解析を行う枠組みをそのままして，バースト期間の長短とバースト同定精度との間の相関に用いてトピックのバーストを同定する．そのため，バースト度ついて分析するとともに，適合率だけでなく再現率の評価を行についての閾値を人手で調整する必要がない点が有利である．

う枠組みを実現する．また，トピックモデルを適用する際のト

文献 [6], [7] においては，Kleinberg のバースト解析手法を用ピック数として，多様な粒度でのトピック推定を行った後，そいて選定したバーストキーワードに対して，トピックへの集約れぞれのトピック数のもとでのバースト同定を行うことにより，を行う枠組みを提案している．しかし，これらは本研究とは異階層的なトピックにおけるバースト同定性能の評価を行う．

なり，DTM や LDA 等のトピックモデルを用いていない．文

本論文では，まずトピックモデルによってトピックを推定し，

献 [7] ではバースト度の高い上位 20 キーワードを含む文書をそれを対象として Kleinberg のバースト解析を行っているが，クラスタリングし，その結果を基に，話題ごとのキーワード今後は，トピック推定の段階でバーストの同定を行うモデルをの集約を行なっている．一方，文献 [6] では，共起度によって開発する．また，On-line LDA [1] などを利用し，本手法のオバーストキーワードを集約したものをトピックとし，トピックンライン化についても取り組む．のバースト度やトピック間の関係性をグラフで視覚的に表示する手法を提案している．トピックのバースト度は，集約されたキーワードの中で，そのうち最もバースト度の高いキーワードのバースト度を採用している．
本研究では，トピック同士を比較する尺度としてバースト度を用いたが，文献 [2] では，トピックモデルにおいて意味のないトピック (J/I; Junk/Insigniﬁcance Topic) の語の分布を定義し，LDA によって推定されたトピックと J/I との分布間の距離を測ることでトピック同士を比較する手法を提案している．

7. お わ り に
本論文では，DTM によって時系列ニュースにおけるトピックを推定し，それらのトピックの関連文書数を定義することにより，Kleinberg のバースト解析アルゴリズムを用いてトピックのバーストの同定を行う手法を提案した．
これにより，キーワードに比べてより情報の単位が大きいトピックのバーストをとらえることが可能になり，時系列ニュー文

献[1] L. AlSumait, D. Bardara, and C. Domeniconi. On-Line
LDA: Adaptive topic models for mining text streams withapplications to topic detection and tracking. In Proc. 8thICDM, pp. 3–12, 2008.
[2] L. AlSumait, D. Bardara, J. Gentle, and C. Domeniconi.
Topic signiﬁcance ranking of LDA generative models. In
Proc. ECML/PKDD, pp. 67–82, 2009.
[3] D. M. Blei and J. D. Laﬀerty. Dynamic topic models. In
Proc. 23rd ICML, pp. 113–120, 2006.
[4] D. M. Blei, A. Y. Ng, and M. I. Jordan. Latent Dirichlet
allocation. Journal of Machine Learning Research, Vol. 3,pp. 993–1022, 2003.
[5] J. Kleinberg. Bursty and hierarchical structure in streams.
In Proc. 8th SIGKDD, pp. 91–101, 2002.
[6] K. Mane and K. Borner. Mapping topics and topic bursts
in PNAS. In Proc. PNAS, Vol. 101, Suppl 1, pp. 5287–5290,2004.
[7] 高橋佑介, 宇津呂武仁, 吉岡真治. ニュースにおけるバーストキー
ワードの話題への集約. 第 3 回 DEIM フォーラム論文集, 2011.
[8] 高橋佑介, 横本大輔, 宇津呂武仁, 吉岡真治. ニュースにおけるトピックのバースト特性の分析. 情報処理学会研究報告, Vol.
2011, No. (2011–NL–204), 2011.