DEIM Forum 2014 C4-3

時系列テキストにおけるクエリ依存の局所的な Emerging Topic の抽出
遠藤 結城†

戸田

浩之†

鷲崎

誠司††

† 日本電信電話株式会社 NTT サービスエボリューション研究所 〒 239-0847 神奈川県横須賀市光の丘 1-1†† 日本電信電話株式会社 NTT メディアインテリジェンス研究所 〒 239-0847 神奈川県横須賀市光の丘 1-1
E-mail: †{endo.yuki,toda.hiroyuki,suzaki.seiji}@lab.ntt.co.jp
あらましソーシャルメディアにおける時系列テキストを分析することで, 世の中で盛り上がっている話題 (Emerging

topic) を特定する研究が多く行われている. しかし既存手法の多くは, 与えられたデータセットにおいて大域的なEmerging topic を特定することが前提であるため, 任意の情報と関連する局所的な Emerging topic を特定するのが困難であった. この問題を解決するために, 本研究では関連文書の絞り込みと Non-negative Matrix Factorization (NMF)にもとづく Emerging topic 抽出の枠組みを提案する. 提案手法では膨大なテキストストリームにおいて, クエリをもとに Coverage 優先で関連文書を高速に絞り込む. 広く絞り込まれたデータにおいてはノイズとなる非関連文書が存在しうるため, クエリと関連性の高い Emerging topic を抽出するために, 従来の時間依存 NMF をさらにクエリ依存に拡張する. 評価実験を通して, 提案手法がベースラインと比較して効率的かつ高精度に局所的な Emerging topic を抽出できることを示す.
キーワード

Emerging topic, ローカルクラスタリング, トピックモデル, NMF, クエリ依存

1. は じ め に
IT 技術の目覚ましい進歩は, 我々の社会に情報の爆発的な増加をもたらしている. そのような状況の中で, 多くの人々が多様かつ膨大な情報を発信できるソーシャルメディアが注目を集めている. Twitter や Facebook に代表されるソーシャルメディア
においては, 人々が今何を感じているか, 何をしているかといった情報が時々刻々と発信されている. ソーシャルメディアにおける情報は時間の経過と共に変化していくことから, 我々の社会の状況を反映するある種の指標と捉えることができる. このソーシャルメディアを分析することにより, 企業の評判や広告の図 1 クエリ依存の局所的な Emerging topic の抽出例. 従来の手法では多様な話題が発信されているソーシャルメディアから, ユーザが望む Emerging topic を得られるとは限らない. これに対し提案手法ではクエリ依存で, 特定の情報と関連性の近い Emerging
topic を精度良く抽出する.

影響を評価するなどマーケティングへの活用が注目されている.
さらには, ソーシャルメディアにおけるトレンドトピックにもとく反映するものとして, 今多くのユーザが注目し盛り上がっ

づいて関連映像を推薦する Trend-aware recommendation [17]ている話題 (Emerging topic) があげられる. この Emerg-が提案されるなど, ソーシャルメディアの分析は幅広いコンテ

ing topic を 分 析 す る 研 究 が こ れ ま で 多 く 取 り 組 ま れ て きンツの流通や個人向けサービスへの応用も期待されている.

た [6], [12], [15], [20], [23], [25], [28]. これらの手法は時系列テ

ソーシャルメディアの分析を効果的な応用につなげるには,キストを入力することで, 単語の集合として表現された Emerg-

ユーザが知りたい情報をすぐに分析できることが重要である.

ing topic を推定することができる. しかしながら, 与えられた

例えば企業のマーケターは, 自身の企業や商品の評判は言うま

データセットにおいて大域的な Emerging topic を特定するこでもなく, 自身の企業と関連する周辺の企業や商品の評判につとが前提であるため, 任意の情報と関連する局所的な Emerging

いて可能な限り鮮度の高い情報を得て, 比較検討することで戦

topic を特定するのが困難であるという問題があった. そのた略を立案したいと考える. また Trend-aware recommendation

め, 多様な情報が発信されているソーシャルメディアからは,などへの応用を考えてもユーザの好みは多様であることから,ユーザが望む Emerging topic を得られるとは限らない. 例え

スポーツやアニメなどユーザの好みにもとづいた任意の情報とばソーシャルメディア全体において, 政治に関する話題の盛り

関連する世の中の話題を分析できることが望まれる. つまり,上がりが支配的である場合, マーケターや消費者が特定の商品

ソーシャルメディアにおける情報を広く浅く分析するだけでなや TV の放送内容などと関連する Emerging topic を知りたく

く, 狭く深く分析することで応用先が広がると考えられる.

とも, これらの手法では政治に関するトピックに他のトピック

ソーシャルメディアにおける情報の中でも, 社会の状況を強が埋もれてしまう. 加えてトピックモデルに代表されるこれら

トピック抽出の手法は, データ量に依存して大きな処理時間を

置 [24] など, マルチメディア分野への応用も期待されている. 時要するため, 大規模な計算機環境を利用できなければ, 膨大な系列テキストを分析しトピックを特定するアプローチは, キー

ソーシャルメディアから鮮度の高い情報を抽出するのは難しい.

ワードベース, 確率的なトピックモデルおよび非確率なトピッ

これに対し Chen ら [5] はソーシャルメディアから, 企業や大学

クモデルの三つに大別される.

など特定の組織に関する Emerging topic を検出する手法を提キーワードベースのアプローチとして, Weng と Lee は [25]

案した. しかし, 組織に関するテキストを集めるための分類器

単語発生頻度の時間変動の相関をもとに, 同じように盛り上がっを構築する際に, 組織のアカウント情報などを用いた正解デーている単語をクラスタリングすることで Emerging topic を検タを用意する必要があることに加え, 分類器の構築にも時間を出した. その際ウェーブレット解析を用いて時系列データから要する. 理想的には多様な情報に関する Emerging topic を効

ノイズとなる高周波成分を除去することで検出精度を向上させ率的に特定できる, より汎用的なアプローチが期待される.

た. 彼らの手法では単語単体で盛り上がりを検出しているのにそこで本稿では図 1 に示すように, 任意の情報と関連する

対し, Li ら [15] は Wikipedia のアンカーテキストなどの情報

Emerging topic を効率良く抽出する枠組みを提案する. 前述を用いて, 複数で意味を持つ単語の組み合わせ (セグメント) にのとおり関連研究の多くのアプローチは, 特定の情報に関するまとめ, セグメント単位で盛り上がりを検出した.

Emerging topic の抽出を想定していないことに加え, データ量

確率的なトピックモデルとして Probabilistic Latent Seman-に依存して多くの時間を要するという問題があった. これに対

tic Indexing (PLSI) [10] や Latent Dirichlet Allocation (LDA)

し本研究のアプローチは, まず膨大な文書データから関連文書[2] が知られている. これらを拡張することで時系列文書を扱えを集めることでデータ量を削減してから, 削減したデータに対るトピックモデルがいくつか提案されている [3], [6], [22], [23].

してトピックモデルを適用し Emerging topic を抽出する 2 段

Blei らの Dynamic Topic Model や [3] や Wang らの Contin-

階のステップからなる. 1 段階目のステップにおいては, デー

uous Time Dynamic Topic Models [22] は, マルコフ性にもとタ量にそれほど依存しない方法を用いることで高速に計算する.

づいて時間的に遷移するトピックをモデル化したものである.

この際, 汎用性や効率性の観点から分類器は用いずに, ユーザ

Wang ら [23] は過去のトピックの時間遷移にもとづいて, 未来が指定するキーワードの集合からなるクエリのみにもとづく局のトピックを予測するモデルとして TM-LDA を提案した. こ所的なクラスタリングにより, Coverage 優先で関連文書を網羅

れらはトピックの時間遷移を考慮しているが, 盛り上がりは考的に収集する. 1 段階目のステップは関連文書を広く高速に収慮されていない. Diao ら [6] はマイクロブログのコーパス全体集できる一方で, 収集された文書にクエリと無関係のノイズとで時間に依存して変化するトピックと, 各ユーザで時間に依存なる文書が混在する可能性がある. そこで 2 段階目のステップ

しないトピックがあるという仮定にもとづきトピックを抽出すにおけるトピックモデルとして, 新たな制約の付与による拡張

るモデルを提案し, 抽出したトピックをバースト検出のアルゴが容易な Non-negative Matrix Factorization (NMF) 採用し,リズムに適用することで, Emerging topic を抽出した.

これにもとづく従来の時間依存 NMF をさらにクエリ依存に拡

非確率的なトピックモデルとして, Dictionary Learning や張する. これにより, クエリと関連性の高い Emerging topic を

Non-negative Matrix Factorization (NMF) [14] にもとづいたより精度良く抽出する.

Emerging topic の抽出手法が提案されている [12], [20]. Ka-

本研究の貢献をまとめると以下のようになる.

siviswanathan ら [12] は Dictionary learning の目的関数の時•間変動量にもとづく新規文書の検出と, 検出した文書をクラスタ

クエリを用いた特定の情報に関する文書データの収集とEmerging topic 抽出のフレームワークの提案

リングし Emergint topic を推定する二段階のアプローチを提案•

クエリ依存および時間依存 NMF の提案した. さらに彼らはこのアプローチの最適化を, ストリームデー•

特定の情報と関連する Emerging topic を抽出するタス

タに対して効率的に行う方法を示した. Saha と Sindhwani [20]クについて Twitter データセットを用いた実験による提案手法

はこれを発展させ, NMF による Emerging topic の推定に応の有効性の検証用した. 彼らは NMF にトピックの盛り上がりや遷移を考慮し本稿の構成は以下のとおりである. まず 2. 節で関連研究について述べ, 3. 節で提案手法の概観を説明する. 次に 4. 節で関連た制約を加えることで, Emerging topic と滑らかに遷移する

Evolving topic の推定手法を示した.

文書の収集方法について述べ, 5. 節でトピックの抽出手法につしかしながら, これら全てのアプローチでは特定の情報と関いて述べる. 6. 節では提案手法を評価し, 最後に 7. 節で本稿を連する詳細な Emerging topic を抽出することを想定していな

まとめる.

2. 関 連 研 究

い. ソーシャルメディアには様々な分野の話題が存在するため,データ全体に手法を適用した場合, 最も数が多く盛り上がっている支配的なトピックが優先的に抽出されてしまう. 抽出する

ソーシャルメディアの時系列テキストにおけるトピック抽出

トピックの数を増やせば, 細かな Emerging topic を抽出できの手法は, マーケティングの分野のみならず地震などの災害検る可能性もあるが, 処理時間やメモリ利用量の観点から, 現実

知 [18] や選挙活動の反応予測 [21], 政治や経済の動向調査 [11]的な方法ではない. オンラインでデータを処理する既存手法 [9]など様々な目的で用いられている. 最近では再生数の増加が予であっても, 膨大な時系列テキストを実用的な時間で処理する

測される映像の推薦 [17] や映像配信における効率的なデータ配のは容易ではない. Zimmerman ら [28] や Xie と Xing [26] は

文書データをクラスタリングし, 個々のクラスタをさらにクラと記載する.

スタリングする 2 段階のアプローチにより, 大局的なトピック

Saha と Sindhwani は式 (1) の行列分解に対して, トピックとそれをさらに詳細化したトピックを検出する手法を提案した.

の強度の時間変動を考慮する正則化を組み込むことで, 盛り上

しかしここで抽出されるトピックは, データ全体で支配的なトがっているトピック (Emerging topic) を精度良く抽出していピックを詳細化したものであるため, 詳細化されたトピックも特る. なおトピックの強度とは, 特定のトピックに関連する文書

定の情報に関係するものであるとは限らない. またソーシャルの量を表す. 具体的には, トピックの強度の時間変化量が小さ

メディアにおける膨大なテキストデータから, Emerging topic

いほどペナルティを課す制約を次式の正則化項として加える.

を抽出するには多くの時間を要する.
これに対し Chen ら [5] はソーシャルメディアから, 企業や大学など特定の組織に関する Emerging topic を検出する手法

min
em

W

∑

T
−1
∑

ci max(0, ν − (DFSwj )i )2(2)

wj ∈Wem i=1を提案した. この手法では組織に関する公式アカウントやキー

em
ここで, Wem ∈ Rm×k
は列成分が Emerging topic に該当>0

ワード検索結果から得られた文書を教師データとして構築したする W の部分行列であり, wj は j 番目の列ベクトルであ分類器を用いて, 他の関連する文書を分類し収集している. さる. また kem は Emerging topic の数である. S は同じタイらに収集したデータをインクリメンタルにクラスタリングし,ムステップに存在する文書群のトピック分布の和を計算する

そのクラスタにおける文書数やユーザ数の変化に応じて分類器

T × m の行列であり, ある時刻を示す行において, ある列の文=により Emerging topic か否かを判定する. 彼らの研究目的は書が投稿されていれば, その要素の値は 1 を取る. ここで T は本研究と近いが, この手法は関連データを収集するために, 各々

タイムステップの総数を表す. F はトピックの強度の時間的の組織について分類器を構築する必要がある. しかしソーシャ

変動を平滑化しノイズを除去するための T × T の行列であり,ルのメディアの情報は刻一刻と変化するため, 一度構築した分

Hodrick-Prescott Filter [7] と呼ばれている. D は勾配作用素

類器では時間の経過に伴い関連文書の収集精度が低下すると予として働く (T − 1) × T の行列であり, 例えば Di,i = −1 およ想される. さらに新たな対象に関する文書を収集する度に, 組

び Di,i+1 = 1 のような値を取る. これによりあるステップと一織に関するユーザアカウントなどの教師データを集め分類器をつ前のステップとのトピックの強度の差分を計算する. この正構築する手間を要する. 提案手法は, 教師データなしでクエリ

則化項はこれらトピック強度の差が小さいほど, 定数 ν によりのみを用いて関連データを広く効率的に集め, さらにクエリとペナルティを課すように設計されている. また, ci はタイムス

近い Emerging topic を時間依存およびクエリ依存の NMF に

テップ i 毎の重みを表しており, 古い情報ほどペナルティを小もとづいて抽出する. これにより, 特定の組織だけでなく, 多様

さくするように設定される.

な情報と関連する Emerging topic を効率的かつ精度良く抽出できるより汎用的な手法の確立を目指す.

なお Saha と Sindhwani は Wem にあたる Emerging topicに加えて, 時間の経過と共に徐々に遷移する Evolving topic も

2. 1 時間依存 NMF

考慮しているが, 本研究では任意の情報と関連する Emerging

本節では提案手法の背景技術となる時間依存 NMF について簡

topic の抽出に焦点を当てる. Evolving topic の考慮は提案手潔に述べる. 一般にトピックモデルとして用いられる NMF [27]

法と競合するものではなく, 提案手法を Evolving topic を考慮

は, bag-of-words モデルを用いて表現された文書の特徴ベクトするために拡張することも可能である.

ルを複数合わせた行列を入力としたとき, 各文書に対するトピックの分布である文書トピック行列, 各トピックに対する単語の分布であるトピック単語行列を出力する. これらの行列は入力文書における単語の共起性にもとづいて推定される.

3. 提案手法の概観
ソーシャルメディアから任意の情報と関連する Emerging

topic を抽出する本研究のアプローチは 2 段階のステップから

この NMF を拡張することで, 時系列データにおいて Emerg-

なる. 1 ステップ目においては膨大な文書データから, クエリに

ing topic を抽出する手法が Saha と Sindhwani によって提もとづいて関連文書を Coverage 優先で高速に絞り込みデータ

案されている [20]. この手法は, ある時間区間における文書量を削減する. この際広く収集されたデータにおいては, ノイ

データに対して NMF を適用する. あるタイムステップを tズとなる非関連文書が混在する可能性がある. そこで 2 ステッ, 時間区間を表すタイムウィンドウのサイズを w , このときプ目として, 絞り込まれたデータに対してクエリとより関連性の文書数を m , 単語数を n としたときの文書群の特徴量をの高い Emerging topic を抽出するトピックモデルを提案する.

X(t − w + 1 : t) ∈ Rm×n
(Rm×n
は正の実数からなる m × n
>0
>0
=

=

の行列集合) とすると各ステップの処理の流れについて, 図 2 を用いて説明する.
まず 1 段階目のステップにおいては, ソーシャルメディアからX(t − w + 1 : t) ≈ WH

(1)

発信されるテキストストリーム (ソーシャルストリーム) を入力とし, 文書の関係を表すグラフを生成する. ここで文書とは,として近似される文書トピック行列 W ∈ Rm×k
およびトピッ>0

例えばユーザが投稿する一つのテキストメッセージのことを表

ク単語行列 H ∈ Rk×n
を推定する.
>=0

ここで k はトピック数です. このグラフは文書が入力される度にオンラインで更新されある. このとき, W および H の各要素は非負値であるというる. 次にこのグラフと入力されたクエリを用いて局所的にクラ制約をもつ. 以降は表記の簡単化のため, X(t − w + 1 : t) を X

スタリングを行い, 特定のクエリと関連する文書と接続関係の=図 2 提案手法の処理の流れ. まずソーシャルストリームを入力とし, オンラインで文書の関係を表すグラフを生成・更新する. 次にユーザによって指定されたクエリとなる特定のキーワード群をもとに, クエリを含む文書のノードと関係の近いノードの文書を絞り込む. 絞
り込んだ文書に対して時間とクエリを考慮した NMF を適用し, 特定の情報と関連する
Emerging topic を抽出する.

近いノードの文書をグループ化することで, クエリと関連性のコーパスから計算した df により定義し, df が規定値よりも小近い文書を絞り込む. この際のクエリは, ユーザが任意の情報をさい単語, つまり多くの文書に表れない単語を特徴的とする.

示すキーワード群として指定する. グラフの生成およびクエリ

最後に新たに追加された文書 di のノードに対して, 予め与えにもとづく関連文書の収集については 4. 節で示す. 2 段階目のたタイムウィンドウ w よりも古いノードを削除する. すなわ

ステップにおいては, 削減したデータに対しトピックモデルをち, ノード集合 V において最も古いノード do ∈ V を取得し,適用し, Emerging topic を抽出する. トピックモデルとしては,dti − dto > w である場合にノード do に接続しているエッジお

制約の付与による拡張が容易な NMF を採用し, 2. 1 節で述べ

よびノード do を削除する. この処理は, dti − dto > w を満たす

た従来の時間依存 NMF をさらにクエリ依存に拡張する. NMF

ノード do がなくなるまで繰り替えし行う.

にもとづく Emerging topic の抽出については 5. 節で述べる.

4. 2 グラフからの関連文書の収集

4. 関連文書の収集

前節で生成したグラフからクエリと関連する文書を高速に絞り込むため, ローカルクラスタリングのアルゴリズム [1] を応膨大な量のソーシャルストリームから時間をかけずに関連文用する. ローカルクラスタリングはシードとなるノードから,書を広く収集する. そのために高速に局所的なデータをクラス

Conductance と呼ばれる指標をもとに局所的にクラスタリング

タリングできるアルゴリズムとして, 理論計算機科学の分野にする手法である. Conductance はサブグラフにおけるノード間おいて提案されているローカルクラスタリング [1] を文書デーを結合するエッジの密度と, サブグラフとサブグラフ外のノータの収集に応用する. それに伴い, まず文書の関係性を表すグラドとを結合するエッジの疎性をもとに決まる値である. サブグ

フをオンラインで構築する. 文書の関係性を定義するため本稿

ラフ S における Conductance ϕ は次式によって定義される.

では, 特徴的な単語が互いに共起している文書は関連があるという仮定を置く. 以下, 4. 1 節ではグラフの生成, 4. 2 ではロー
カルクラスタリングを用いた関連文書の収集について述べる.

ϕ = ∂(S)/µ(S)(3)

ここで ∂(S) はサブグラフ S のノードとサブグラフ外のノード

4. 1 グラフ生成にもとづく文書の関係性構築とをつなぐエッジの数, µ(S) は S のノードの次数の総和であソーシャルストリームに対して, 文書との関係性を構築する

る. Conductance はグラフ全体の情報を考慮する指標ではない

ためにグラフをオンラインで生成する. 生成するグラフを無向が, 特定のノードと局所的に類似した要素をクラスタリングでグラフ G = (V, E) としたとき, V を現在の分析対象とする文

きる. 加えて計算量がグラフ全体のサイズにさほど依存しない

書集合 D における個々の文書 di をノードとするノード集合, E

特徴がある.

をノード di をつなぐエッジ集合とする. ソーシャルストリー

具体的なアルゴリズムを簡単に説明する. 最初にシードとムとして新たな文書 di が入力されると, 文書のノードがグラフなるノードを決める. 次にシードを起点にランダムウォーク

G のノード集合 V に追加される. このとき di は bag-of-wordsにもとづいて隣接するノードに移動しながら, 付近のノードをモデルを用いて単語の集合として表現されている. また同時に一つのサブグラフにまとめる処理を繰り返す. 繰り返し中に文書が投稿された時刻 dti を持つ.

Conductance がしきい値よりも小さい場合に処理を打ち切り,

文書間の関係性は, 特徴的な単語の共起数によって定義する.

その時点でのサブグラフをクラスタリング結果として出力する.

具体的には, 新しい文書 di とグラフ内の文書 dr ∈ V における本研究ではクエリと関連する文書を集めるため, ローカルク

特徴的な単語の共起数が規定値以上のときに, これらは関連しラスタリングのシードとなるノードを, クエリを含む文書のノーているとし各ノードをエッジで接続する. この際 dr は全てのドとする. またクエリが複数ある場合は, 各クエリについてシーノードを探索する必要はなく, 単語をキーとした各ノード群へ

ドをそれぞれ選択し, それぞれのシードについてローカルクラのハッシュテーブルを作成することで di の単語数に応じた探索

スタリングを行い, 得られたクラスタを結合する. このクラスを行い, ノード数にほとんど依存しない時間で関連文書のノータにおいてグループ化された文書集合をクエリと関連するもの

ドを探すことができる. また単語の特徴度は予め用意した文書とみなし, 次節における Emerging topic の抽出に用いる.

5. Emerging topic の抽出
図 3 に NMF による Emerging topic の抽出処理の概要を示
す. ローカルクラスタリングで絞り込んだ, ある時間区間の文書
データに対して NMF を適用する. 2. 1 節において述べた時間
依存 NMF と同様に入力となる文書単語行列において, 行に対応する文書はタイムステップごとに区切られ, 各タイムステッ
プ毎のトピックの盛り上がりの変化をもとに Emerging topicを抽出する. この際, ノイズとなる非関連文書を含む文書デー
タから, 特定の情報と関連する Emerging topic を精度良く抽出するために時間依存 NMF を拡張する. 次節では, NMF の拡張に応じた目的関数を設定する.
なお本研究では NMF を適用する文書の特徴量として, 自然
言語処理の分野において一般的に多く用いられる TFIDF [19]を利用する. TFIDF にもとづく行列 X の特徴量は次の通りである.

Xi,j =

log2 (1 + T F (i, j)) × IDF (j)Ci

図 3 時系列文書データから, 時間およびクエリ依存 NMF による
Emerging topic 抽出処理の概要. タイムウィンドウ w の区間においてローカルクラスタリングで絞り込んだ関連文書から, NMFの入力となる行列 X を計算する. この際 X は複数のタイムス
テップの文書の特徴量から構成される. X を NMF により Wと H に分解する. これらは提案手法の制約により, クエリ依存
かつ時間依存なトピックに関するもの (Wqem , Hqem ) と, クエ
リ非依存かつ時間非依存なトピックに関するものに分けられる.

上がりを検出するために, 特定のトピックにクエリが出現しな(4)い場合ペナルティを与える項 Eq を定義する.

ここで, Xi,j は行 i 列 j における行列 X の要素, T F (i, j) は文
書 i における単語 j の出現頻度であり, IDF (j) は全文書数にi

対して単語 j が出現する文書数の割合の逆数の対数をとった値を表す. また Ci は X の各行ベクトルを正規化する定数である.

n
∑∑

kqem

Eq =

2
max(0, Qi,j − Hqem
i,j )

(7)

j
k

ここで Hqem ∈ R>qem0=×n

は行成分がクエリと関連する Emerg-

5. 1 目的関数の設定

ing topic に該当する H の部分行列である. Q は kqem × n のクエリと関連性の高い Emerging topic を抽出するために, 各行列であり, クエリに該当する単語の列成分に定数 η を, それトピックにおいてクエリと関連して盛り上がっている内容と,以外の成分には 0 を持つ. Eq は Hqem の各要素が Q よりも大それ以外の内容とに分かれることを狙い NMF の目的関数を設きくなるように制約を与える. これによりクエリの単語や共起定する. 具体的には時間依存制約およびクエリ依存制約をもと性の近い単語を, 特定のトピック中に表れやすくする効果が期に, 以下の目的関数を最小化する問題として定式化される.

待できる. Eq と Et の両方の制約を考慮することで, クエリとデータ依存性: 一般的に NMF は式 (1) における左辺と右辺のの関連性の近い Emerging topic を抽出する.

二乗誤差や KL Divergence が最小になるように WH を求め5. 2 最 適 化

る. すなわち WH が X に近づくように解を求める. したがっ

前節で定義した目的関数を最小化するように, 文書トピック
行列 W およびトピック単語行列 H を最適化する. データ依存て, 文書データに依存する項は項, 時間依存項およびクエリ依存項, パラメータの非負性を考慮

Ed = ||X − WH||2F(5)と定義される. ここで || · ||F はフロベニウスノルムを表す.
時間依存性: Emerging topic を抽出するために, Saha と Sind-

すると, 最終的な目的関数および求める W と H は次のようになる.

E = Ed + λt Et + λq Eq(8)W, H = arg min E(9)hwani [20] の制約式 (2) にもとづく時間依存の制約を与える.
この際クエリと関連する Emerging topic を抽出するために, ク
エリと関係の近いトピックの強度の時間変化量が小さいほどペナルティを与えるように修正した正則化項 Et を定義する.

Et =

∑

T
−1
∑

W,H>
=0

ここで λt および λq はそれぞれの項により与える制約の重みを表すパラメータである. 式 (8) は非凸な関数であることから,

ci max(0, ν − (DFSwj )i )2(6)

wj ∈Wqem i=1

W または H を固定した凸関数を交互に最適化して解を求める方法が一般的である. 最適化の方法は交互最小二乗法や最急降

m×kqemこ こ で, Wqem ∈ R>0

は列成分がクエリと関連する

下法, アクティブセット法 [13] など様々な手法が提案されていEmerging topic に該当する W の部分行列であり, wj はそる. 本研究では大きな行列の処理も想定されることから, 省メ=の j 列目のベクトルである. また kqem はクエリと関連する

モリで計算可能な L-BFGS-B [4] 法を用いて実験を行った. 目

Emerging topic の数である. 後述のクエリ依存制約を与えるト的関数は非凸な関数であるため大域的な最適解を求めることはピックに対してのみ時間依存制約を与えることで, 盛り上がっ

難しい. そのため W や H を最適化する際には, いくつかのパているトピックの中でもクエリと関連するものを抽出する.

ターンによるランダムな値で初期化を行い, 目的関数が最も小

クエリ依存性: クエリと関係の近いトピックについてのみ盛りさくなったものを最終的な推定値とした.

Algorithm 1 Query dependent emerging topic extraction
Input: text graph G, query terms Q,
topic size k, kqem , hyperparameters ν, η, λt , λq
k×n
Output: W ∈ Rm×k
>0 , H ∈ R >0
=

1: D

Q

タセットに対して, 提案手法でどれだけ精度よくオリンピックに関連する Emerging topic を抽出できるかを評価する. これらのデータセットは, オリンピックに関連するものが 57,306 ツ=← LocalClustering(Q)

2: X(t − w − 1 : t) ← CalculateF eatures(Dリンピックの関連ツイートと非関連ツイートを混在させたデーイート, 関連しないものが 329,238 ツイートであった. なお, 日Q)

3: Q ← CalculateQueryDependentM atrix(Q)

本語の文章を単語単位に分割するために, 形態素解析エンジンの MeCab（注 1）を用いた.

4: Initialize W and H to random distribution

6. 2 関連文書の収集精度

5: while not(converge) do

提案手法により, どれだけ正確かつ網羅的に関連文書を集め

6:

W ← arg minW >0 E

られるか否かを検証する. 前述のデータセットを用いて「オリ7:H ← arg minH >0 E

ンピック」をクエリとして関連データを収集した際に, オリン

8:Check convergence based on relative change in objec-

ピックと関係するラベルが付与された Tweet の収集精度を適

tive value E < ϵ

合率 (P recision), 収集量を再現率 (Recall) によって評価する.

==

本実験においては, 提案手法を含む下記の手法を比較する.

9: end while

最後に, 本研究のクエリ依存 Emerging topic 抽出アルゴリ
ズムを Algorithm 1 にまとめる.

•

KS: キーワードサーチによりクエリを含む文書を取得.

•

LC@θ: オンラインで更新される文書グラフに対してロー

カルクラスタリングを適用. θ は Conductance を基準に, クラスタリングアルゴリズムのイテレーションを打ち切るしきい値.

6. 評

価

提案手法の有効性を以下の三つの観点から検証する.
（ 1 ） 関連文書収集の精度

文書データをグラフに保持するタイムウィンドウ w およびロー
カルクラスタリングを適用する間隔は 1 時間とした.
表 1 に実験結果を示す. KS による結果は P recision が 0.7（ 2 ） 特定の情報と関連する Emerging topic 抽出の精度であり, オリンピックと関連する文書をある程度正確に集められ（ 3 ） 処理時間ているものの, Recall が 0.019 であり全然網羅的に集められて関連文書収集の精度とは, 4. 節で述べた方法により, クエリと関いないことがわかる. これに対し, LC による結果は P recision

連する文書をどれだけ集められるかという観点である. また, 収は KS と同程度の値であり, Recall も比較的高い値であること集したデータに対して 5. 節で述べた時間依存かつクエリ依存のから, ある程度関連する文書を比較的多く集められている. こトピック抽出により, どれだけ特定の情報と関連する Emergingのときクラスタリングを打ち切る基準となる Conductance の

topic を精度良く抽出できるかを評価する. 処理時間について

しきい値 θ が小さいほど, より広い範囲で関連データを収集す

は, 関連データをローカルクラスタリングで高速に絞り込むこるため Recall が上昇し P recision が低下する. パラメータにとで, Emerging topic 抽出の枠組みにおいて処理時間にどのよる結果の変動はあるものの, 文書グラフのローカルクラスタ

程度の違いが生じるかを検証する. 以下本実験に用いたデータ

リングによる本研究のアプローチは, 単純なキーワードサーチ

セットについて説明した後, それぞれの評価について述べる.

よりも高精度に関連データを収集できていることを確かめられ

6. 1 データセット

た. この絞り込まれたデータにおいて NMF を適用することで,今回はトレンド抽出の情報源としてソーシャルメディアの中

特定の情報と関連する Emerging topic を効率的に抽出できるでも即時性が高く, 情報量の多いマイクロブログの Twitter をと考えられる.

用いる. 関連する文書の収集や Emerging topic の抽出について

表 1

提案手法の精度を評価するために, Twitter API を用いて収集された日本語 Tweet に対して, 予め想定したキーワードと関連

デ ー タ 収 集 の 精 度.

P は P recision, R は Recall, F1 はF − measure, TP は True positive, FP は False positive,
FN は False negative を表す.
Method

P

R

F1

TP

FP

KS

0.73

0.020

0.039

1138

419

56168

リンピックをキーワードと想定し, 関連データとして 2012/7/30

LC@0.6

0.83

0.45

0.58

25882

5326

31424

から 2012/8/5 までのロンドンオリンピックに関連するツイー

LC@0.2

0.64

0.62

0.63

35664

20153

21642

するツイートにその内容を表すラベルの付与を行う. 今回はオFNトを用いることとした. 本実験では, 人手によりオリンピックと関係の深いハッシュタグをラベルとして選び, そのラベルの6. 3 Emerging topic の抽出精度付与されたツイートを関連データとした. オリンピック関連す特定の情報と関連する Emerging topic の抽出精度を検証

るハッシュタグとしては, 例えば# 柔道や# 体操などを選択しするために, まず評価指標について簡潔に述べる. 本実験

た. 簡単のため各 Tweet に複数の関連ハッシュタグが付与されでは Saha と Sindhwani [20] も用いた指標である Jensen −ているものは, データセットから除外した. 一方, オリンピック

ShannonDivergence (JSD) を利用して, 真のトピックにおけと関係のないツイートとして, オリンピックと関係のないハッる単語の分布と, 推定されたトピックにおける単語の分布を比較

シュタグが付与されたツイートを用いることとした. これらオ
（注 1）：http://mecab.googlecode.com/svn/trunk/mecab/doc/index.html

図 4 ある時間帯におけるオリンピックと関連するツイート量の時間変化 (左) と対応する時刻
におけるトピックの抽出精度 (右の四つ). 抽出精度は各ラベルに関する真のトピックと推定されたトピックとの JSD にもとづいており, 値が小さいほど高精度であることを表す.
左図において数が増加し盛り上がっているラベルについて, 該当する時刻の JSD が小さいほど, Emerging topic を精度良く抽出できていることになる.

する. 真のトピックは特定のラベルが付与された文書は同じト

表 2 各ラベルが最も盛り上がった時刻において各手法で得られたトピックであるという仮定のもと, トピックモデルを用いてあらか

ピックと真のトピックとの JSD および全ラベルの JSD の平均.

じめ計算しておく. 今回はオリンピックに関連する# 体操や#Method

# 柔道

# 卓球

# 競泳

# 体操

全ラベルの平均Baseline

0.212

0.353

0.212

0.228

0.253

LC

0.178

0.275

0.195

0.235

0.221

LC+Q

0.106

0.250

0.100

0.113

0.142

卓球などのラベルが付与された各々のツイートから, 真の# 体操トピックや# 卓球トピックを計算する. これら真のトピックと, 様々なラベルのツイートが混在したデータセットに各手法を適用し得られたトピックとの JSD を比較する. 各々のラベルの付与されたツイート数が増加し盛り上がっている時点で, 対応するトピックに関する JSD が減少しているほど, Emerging

topic の抽出精度が高いと考えることができる. ページ数の都
合上詳細は省くため, 評価値の算出などは Saha と Sindhwaniの文献 [20] を参照されたい.
前述の JSD による評価指標を用いて, 下記の Baseline と提案手法を比較する.

•

Baseline: Emerging topic を抽出するための時間依存制

約 [20] を付与した NMF を全データに対して適用.

•

LC: 時間依存 NMF をローカルクラスタリングにより絞り込んだ関連データに対して適用.

•

LC+Q: 時間依存かつクエリ依存 NMF をローカルクラ

スタリングにより絞り込んだ関連データに対して適用.
本実験において用いたパラメータは, タイムウィンドウ w を 1
時間としタイムステップを 20 分とした. また, ローカルクラス
タリングの Conductance のしきい値は 0.2, NMF におけるパラメータは k = 5, kqem = 4, ν = 20, η = 1, λt = 10 および

λq = 1000 とそれぞれ経験的に設定した.
図 4 および表 2 に評価結果を示す. 図 4 において, 左はある
時間帯における各ラベル付きツイート量の時間変化であり, 右の四つは対応する時刻において各手法を適用して得られたト
ピックとラベル毎の真のトピックとの JSD を示している. また表 2 は各ラベルに関する話題が最も盛り上がっている時刻の

JSD を示している. 各ラベルに関する話題が最も盛り上がっている時刻は, 単純に図 4 左において各ラベルのツイート量が最も多い時刻とした. Baseline の結果においては, 各ラベルのツイートが盛り上がっている時刻において, 顕著な JSD の減少がみられない箇所 (例えば# 競泳の 20 時前後や# 体操の 18時前後など) が存在する. これはオリンピックと関係のないト
ピックが混在しているデータセットの影響を受けているため,
オリンピックと関連する Emerging topic を精度よく抽出できていないと考えられる. 一方 LC は, Step1 で「オリンピック」

をクエリとしたローカルクラスタリングにより関連データに絞ることで, 表 2 からも例えば# 競泳について Emerging topicの抽出精度が向上しているのがわかる. しかしながら, LC だ
けではデータを十分に絞りきれない場合もあり, データ量を削減することで高速にトピックを抽出できるものの, 表 2 の体操に示すように精度が向上しない場合も多くみられる. これに対し LC+Q は, Step2 でさらにクエリ依存制約を与えた時間依存

NMF を適用することで, さらなる精度向上が確認できる.
6. 4 処理時間と定性的な結果
提案手法は Python 言語で実装し, NMF の L-BFGS-B 法
による最適化にはライブラリとして Numpy, SciPy を用いた.
実装したプログラムは CentOS 5.5, Intel Xeon5650 2.66GHz

6Core HT x 2, 48GB RAM の環境で実行した.
図 5 にある時刻におけるツイートに Baseline と提案手法(LC+Q) を適用した場合の処理時間および抽出された Emerging topic の例を示す. NMF はデータ量に依存して計算量が大きく増大してしまうため, ベースラインは 1388 秒の時間を要している. 一方提案手法は関連データを絞り込む処理に 0.8 秒,

NMF の処理に 65.4 秒の時間を要しており, ベースラインと比較して約 20 倍の速度で処理できている. 本研究における処理時間の削減のポイントは, データ量にほぼ依存しないアルゴリ
ズムであるローカルクラスタリングにより, データ量を削減してから NMF を適用していることであり, NMF の最適化による処理速度は考慮していない. そのため NMF を並列に計算する手法 [16] などを用いることで, さらなる高速化が期待できる.
抽出されたトピックについては, Baseline がデータ全体で支配的なトピックを抽出してしまっているのに対し, 提案手法はオリンピックに関係するトピックを抽出できていることがわかる. 図 5 に抽出した全てのトピックを示していないが, Baseline
によって抽出されたどのトピックも, オリンピックに関連する内容と該当するものはなかった. また今回は定量的評価のために, ラベルとして使える多様なハッシュタグがあるオリンピッ
クの開催時期のデータセットを用いたが, 他のデータセットに

図 5 提案手法 (LC+Q) と Baseline による処理時間および抽出される Emerging topic の例.

提案手法を適用することで, 図 1 に示すような Emerging topicを抽出するできることも確認した.

7. お わ り に
本稿ではソ ーシャルメディアから任意の情報と関連す る

Emerging topic を抽出する枠組みを提案した. 多様な情報と関連する Emerging topic を抽出する汎用的なアプローチを実現するため, 提案手法では教師データを用いずにクエリのみを用いて, クエリと関連する Emerging topic を精度良く抽出することを課題とした. 提案手法では, 一段階目のステップとして文書の関係性を表すグラフをオンラインで生成し, グラフにローカルクラスタリングを適用することでクエリと関連する文
書を高速に収集する. これにより, 特定の情報と関連するデー
タを広く集めると同時に, 次ステップにおけるトピックモデルの処理速度を大幅に削減できる. この際広く絞り込まれた文書
データにおけるノイズである非関連文書を考慮するため, さらに NMF を用いた Emerging topic 抽出手法をクエリ依存に拡張した. 評価実験では特定の情報と関連する Emerging topicの抽出精度および処理時間の観点で, ローカルクラスタリング
によるデータの絞り込みと, 時間依存かつクエリ依存 NMF による枠組みの有効性を示した.
現在の手法は Emerging topic の抽出精度がクエリの粒度やトピック数などに依存してしまうと考えられる. そこで今後の課題として, トピック数を自動で適切な値に決定するノンパラメ
トリックなアプローチ [10] などを応用することで, さらなる精度向上を目指すことがあげられる. また高速化について, 今回は関連文書の収集についてのみに注目しているため, NMF を並列に最適化するアルゴリズムを提案手法の枠組みに組み込むことで, 更なる高速化が期待できる. また提案手法を Trend-aware

recommendation [17] などに応用することも興味深い.
文

献[1] Andersen, R. and Peres, Y.: Finding Sparse Cuts Locally
Using Evolving Sets, Proc. of STOC’09, pp.235-244, 2009.
[2] Blei, D. M., Ng, A. Y. and Jordan, M. I.: Latent dirichlet allocation, In Journal of Machine Learning Research, 3,
pp.993-1022, 2003.
[3] Blei, D. M. and Laﬀerty, J. D:Dynamic topic models, In
Proc. of ICML’06, pp.113-120, 2006.
[4] Byrd, R. H., Lu, P. and Nocedal, J.: A Limited Memory Algorithm for Bound Constrained Optimization, SIAM Journal on Scientiﬁc and Statistical Computing, 16, 5, pp.11901208, 1995.
[5] Chen, Y., Amiri, H., Li, Z. and Chua, T.-S.: Emerging
topic detection for organizations from microblogs, In Proc.

of SIGIR’13, pp.43-52, 2013.
[6] Diao, Q., Jiang, J., Zhu, F., Lim, E.-P.: Finding bursty topics from microblogs, In Proc. of ACL’12, pp.536-444, 2012.
[7] Hodrick ,R. J. and Prescott, E. C.: Postwar U.S. Business Cycles: An Empirical Investigation, Journal of Money,
Credit, and Banking, 29, pp.1-16, 1997.
[8] Hoﬀman, M. D., Blei, D. M. and Cook, P. R.: BayesianNonparametric Matrix Factorization for Recorded Music,
In Proc. of ICML’10, pp.439-446, 2010.
[9] Hoﬀman, M. D., Blei, D. M. and Bach, F. R.: Online
learning for latent dirichlet allocation, In Proc. of NIPS’10,
pp.856-864, 2010.
[10] Hoﬀman, T.: Probabilistic latent semantic analysis, In
Proc. of SIGIR’99, pp.50-57, 1999.
[11] Jin, X., Gallagher A. C., Cao L., Luo, J. and Han, J.: The
wisdom of social multimedia: using ﬂickr for prediction andforecast, In Proc. of ACM MM’10, pp.1235-1244, 2010.
[12] Kasiviswanathan, S. P., Melville, P., Banerjee, A. andVikas, S.: Emerging topic detection using dictionary learning, In Proc. of CIKM’11, pp.745-754, 2011.
[13] Kim, H. and Park, H.: Non-Negative Matrix Factorization
Based on Alternating Non-Negativity Constrained Least
Squares and Active Set Method, SIAM Journal on Matrix
Analysis and Applications, 30, 2, pp.713-730, 2008.
[14] Lee, D. D. and Seung, H. S.: Learning the parts of objects
by non-negative matrix factorization, Nature, 401, pp.788791, 1999.
[15] Li, C., Sun, A. and Datta, A.: Twevent: segment-based
event detection from tweets, In Proc. of CIKM’12, pp.155164, 2012.
[16] Liu, C., Yang, H.-C., Fan, J., He, L.-W., Wang, Y.-M.:
Distributed nonnegative matrix factorization for web-scale
dyadic data analysis on mapreduce, In Proc. of WWW’10,
pp.681-690, 2010.
[17] Roy, S. D., Mei, T., Zeng, W. and Li, S.: SocialTransfer:
Cross-Domain Transfer Learning from Social Streams forMedia Applications. In Proc. of ACM MM’12, pp.649-658,
2012.
[18] Sakaki, T., Okazaki, M. and Matsuo, Y.: Earthquake shakes
twitter users: real-time event detection by social sensors. In
Proc. of WWW’10, pp.851-860, 2010.
[19] Salton, G. and Buckley, C.: Term-weighting approaches in
automatic text retrieval, Information Processing and Management: an International Journal, 24, 5, pp.513-523, 1988.
[20] Saha, A. and Sindhwani, V.: Learning evolving and Emerging topics in social media: a dynamic nmf approach withtemporal regularization, In Proc. of WSDM’12, pp.692-702,
2012.
[21] Tumasjan, A., Sprenger, T. O., Sandner, P. G. and Welpe, I.
M.: Predicting elections with twitter: What 140 charactersreveal about political sentiment. In Proc. of ICWSM’10,
pp.178-185, 2010.
[22] Wang, C., Blei, D. B. and Heckerman, D.: Continuous Time
Dynamic Topic Models, CoRR, abs/1206.3298, 2012.
[23] Wang, Y., Agichetein, E. and Benzi, M.: TM-LDA: eﬃcientonline modeling of latent topic transitions in social media,
In Proc. of KDD’12, pp.123-131, 2012.
[24] Wang, Z et al: Propagation-based social-aware replication
for social video contents, In Proc. ACM MM’12, pp.29-38,
2012.
[25] Weng, J. and Lee, B.-S.: Event Detection in Twitter, In
Proc. of ICWSM’11, pp.401-408, 2011.
[26] Xie, P. and Xing, E. P.: Integrating Document Clusteringand Topic Modeling, CoRR, abs/1309.6874, 2013.
[27] Xu, W., Liu, X. and Gong, Y.: Document clustering basedon non-negative matrix factorization, In Proc. of SIGIR’03,
pp.267-273, 2003.
[28] Zimmermann, M., Ntoutsi, I. and Siddiqui, Z. F.,
Spiliopoulou, M. and Kriegel, H.-P.: Discovering global andlocal bursts in a stream of news, In Proc. of SAC’12, pp.807812, 2012.