DEIM Forum 2017 G7-3

時系列文書に対するトピックフォレストの構築と構造解析
伏見 卓恭†

佐藤 哲司†† 筑波大学図書館情報メディア系 〒 305–8550 茨城県つくば市春日 1–2
E-mail: †{fushimi,satoh}@ce.slis.tsukuba.ac.jp
あらまし Web 上には，ニュース記事やブログ記事，ウェブページ，学術文献など，時々刻々と大量の文書が投稿される．文書間には，関連する，あるいは，類似するという関係が強いものと弱いものが存在する．学術文献は引用，ブログ記事はトラックバック，ウィキペディア記事やウェブページはハイパーリンクという形で関連する文書とのつながりが明示されているが，ニュース記事に関しては関連する文書とのつながりが明示されない場合が多い．最も簡単な方法として，ニュース記事間の類似度を計算し，類似文書間にリンクを張ることで類似度ネットワークを構築する
方法があげられるが，時間軸を考慮するのは困難である．そこで本稿では，文書の意味的凝集性と時間的凝集性に基づき，時間発展する複数の木構造からなるトピックフォレスト構築手法を提案する．このトピックフォレストを可視化することで，文書への効果的なアクセス順序を提示できると考えられる．実データを用いた評価実験により，構築したトピックフォレストが意味的凝集性と時間的凝集性を有していることを示し，文書群へのアクセシビリティ向上の一助となることを確認する．
キーワード 時系列文書，ツリー構造，可視化

1. は じ め に上述の類似度ネットワーク構築法とネットワーク構造可視化手法を組み合わせることで，高次元多様体上のオブジェク

近年 Web 上には，ニュース記事やブログ記事，学術文献なト群を可視化する手法として，ISOMAP [4]，Locally Linear

ど，大量の文書が時々刻々と投稿されている．文書間には，関Embedding [5]，Laplacian Eigenmaps [6] があげられる．これ連する，あるいは，類似するという関係が強いものと弱いものらの手法でも，時間情報を付加することは困難である．

が存在する．学術文献は引用，ブログ記事はトラックバック，

本稿では，ISOMAP などのグラフ構造化とグラフ可視化を

ウィキペディア記事やウェブページはハイパーリンクという形組み合わせるフレームワークに基づき，時系列文書を効果的にで関連する文書とのつながりが明示されているが，ニュース記

可視化する手法を提案する．時系列文書を適切に可視化するこ事に関しては関連する文書とのつながりが明示されない場合とで，文書間の局所的な関係や全体像を客観的に把握できるよが多い．最も簡単な方法として，ニュース記事間の類似度を計

うに整理，かつ所望の文書へのアクセシビリティを高めること

算し，類似文書間にリンクを張ることで類似度ネットワークをを目標とする．具体的には，文書の意味的類似性と時間的凝集構築する方法があげられる．一般的な類似度ネットワーク構築

性に基づき，時間発展する複数の木構造からなるトピックフォ法として，Minimum Spanning Tree，Relative Neighborhood

レスト構築手法を提案する．そして，構築したトピックフォレGraph，k-NN Graph などが存在する．これらのグラフは，大ストを可視化する．

規模なオブジェクト群から類似のオブジェクトを検索するタス

本稿は以下のような流れである．2 章で提案手法について述

クである類似検索などでも用いられているが，時間発展する文べ，3 章で実データを用いて提案手法を評価し，結果に関して

書群の時間情報を加味するのは困難である．

考察する．4 章で関連研究について触れ，最後に本稿のまとめ

文書群の全体像を客観的に把握するための手段として，文書間の類似性に基づき，2 次元平面あるいは 3 次元空間に埋め込む
可視化手法が挙げられる [1]．類似性に基づく古典的な可視化法と今後の課題について言及する．

2. 提 案 手 法として，Principal Component Analysis，Multi-Dimensional

提案手法の枠組みでは，文書集合を D = {d1 , . . . , dN }，単Scaling などが存在する．線形に射影するこれらの可視化手

語集合を W = {w1 , . . . , wM } とし，各文書は語彙数 M 次元法では高次元ベクトルで表現される文書群を低次元へ埋め込の単語頻度ベクトル bi = [bi,j ]M
j=1 で表現する．ここで，bi,j

むのが困難であることが知られており，Sammon Mapping やは，文書 di における単語 wj の出現頻度を表す．任意の文書

Kernel PCA などの非線形手法も提案されている．さらに，

di と dj 間に類似度 ρ(di , dj ) = cos(bi , bj ) が得られたとき，文書のトピック（クラス情報）に着目した可視化手法である

閾値 α を定め，ρ(di , dj ) > α となる文書間にリンクを付与す

Fisher’s linear Discriminant Analysis，t-distributed Stochas-

ることで，トピックフォレストとよぶ木構造を構築する．構築

tic Neighbor Embedding [2] や Parametric Embedding [3] もしたトピックフォレストを，角度と半径により座標が決定され提案されている．これらの可視化手法でも時間情報を考慮する

る極座標平面に埋め込む．全文書集合 D とパラメータ α を入のは困難である．

力として与え，以下の手順で各文書を可視化する：

（ 1 ） トピックフォレスト構築；

れのツリーを極座標平面上に可視化する手法について説明する．

（ 2 ） 各ツリーを極座標可視化；

ツリーにおける第 s 階層と第 s + 1 階層ノード群を二部グラフ

各手順の詳細を次節以降で説明する．

としてとらえ，座標ベクトル群 Xs と Xs+1 を決定する．Vs

2. 1 トピックフォレスト構築法と Vs+1 のノードはそれぞれ半径 rs ，rs+1 の円上に配置する．

与えられた文書集合に含まれる文書 d をノードとみなし，類似

ここでは，第 1 階層と第 2 階層のノード群の座標を決定す度の高い文書間にリンクを付与することで，ツリー T = (V, E)

1 ,N2
る方法について説明する．隣接行列 A = [ai,j ]N
i=1,j=1 に対しを構築する．具体的には，文書 di ∈ D が投稿された時刻をて多次元尺度法などと同様に中心化を施し，中心化隣接行列

di .time としたとき，投稿された時刻が早い文書から順にツリーÃ = [ãi,j ] を得る．そして，座標ベクトル群 X1 と X2 を適切にノードとして追加する．つまり，時間発展するツリーを構築すに初期化し，以下に示す目的関数を最大にするように反復的にることになる．具体的には，文書 di が投稿された時刻より前に求める．

投稿された文書集合を D(di ) = {d ∈ D ; d.time < di .time} と表す．文書 di について，各文書 d ∈ D (di ) との類似度 ρ(d, di )を計算し，最も類似する文書ノード dˆ から di にリンクを付与

J(X1 , X2 ) =

N1 N2
∑
∑
i=1 j=1

ãi,jxTi xjr1 r2+

1∑
λi (r12 − xTi xi )
2 i=1

+

1∑
µj (r22 − xTj xj ).
2 j=1

N1

する：

P (di ) = dˆ = arg max ρ(d, di )N2

d∈D (di )V ← V ∪ {di }, E ← E ∪ {(dˆ −→ di )}(1)

ここで P (di ) は，文書ノード di の親ノードを意味する．すな

ここで，λi と µj は，各円周上に配置するための制約を表す

わち，既に投稿されている（＝既にツリーの一部になっている）

ラグランジュ乗数である．式 (1) において ri1 r2j = cos θi,j で

ノード d ∈ D (di ) のうち，最も類似するノードの子ノードとしあり，隣接するノードどうしが原点から見て同じ方向に配置さて，di をツリーに追加する．

れることによって，J(X1 , X2 ) は最大化される．すなわち，同次に，類似度閾値パラメータ α を導入する．すなわち，文書ˆ di ) = maxdi について，最大類似度 ρ(d,(d ) ρ(d, di ) が閾じようなノードと隣接するノードどうしを同一方向に，異なるd∈Diˆ di ) > α) 場合のみ dˆ から di にリンクを張
値 α を超える (ρ(d,り，そうでない場合にはリンクを付与せず，di は新たなツリー

xT x

ノードと隣接するノードを異なる方向に配置する．
また，ベクトル群 X2 を固定すれば，第 1 階層ノードの座標ベクトル xi の最適配置は以下のように求まる．

の根（root）となる．このことを便宜上，P (di ) = di と記す．


 arg max ρ(d, di )P (di ) =xi =ˆ di ) > α)
(ρ(d,

N2
∑
r1
ãi,j xj
x̃i , x̃i =∥x̃i ∥j=1(2)

d∈D (di )di(otherwise)

適切な閾値 α を設定することで，異なるトピックの文書群は異なるツリーを形成する．以降，この一連の手順により得られるツリー群をトピックフォレストと呼ぶ．α < 1 の値が大きいほどツリーの数は増え，α = 0 で単一のツリーとなる．
次に，投稿間隔パラメータ λ を導入する．文書 di につい て ，投 稿 間 隔 di .time − dj .time に 従 い リ ン ク 付 与 確 率

λ exp(−λ(di .time − dj .time)) を与える．これにより，上記

第 1 階層の文書ノード di の座標ベクトル x̃i は，第 2 階層ノードの隣接するノードの座標ベクトル xj の合成ベクトルで計算される．そして半径 r1 上にくるように正規化している．
同様に，ベクトル群 X1 を固定すれば，第 2 階層ノードの座
標ベクトル xj の最適配置は以下のように求まる．

xj =

N1
∑
r2
ãi,j xix̃j , x̃j =∥x̃j ∥
i=1(3)

極座標可視化法のアルゴリズムを以下に示す．

の方法で親ノードとして選定した文書ノードとの投稿間隔が大きくなるにつれて，リンク付与確率が低くなる．
各ツリーにおける根 root を 0 階層とし，根からのグラフ距離により各ノードを第 s 階層ノード群 Vs = {d; dist(d, root(d)) =s} のように階層に分ける．第 s 階層のノード数を Ns = |Vs | とする．また，文書ノード di の子ノード集合を C(di ) とし，その（ 1 ） ベクトル群 X1 と X2 を初期化する；（ 2 ） ベクトル群 X2 を固定し，ベクトル xi を求める；（ 3 ） ベクトル群 X1 を固定し，ベクトル xj を求める；（ 4 ） 目的関数 J(X1 , X2 ) の変化が十分小さければ終了する；（ 5 ） （2）へ戻る；

要素を C(di ) ∈ C(di ) と表記する．トピックフォレストにおいこのアルゴリズムは HITS アルゴリズム [8] と類似した構造をて，定義より必ず P (di ).time < di .time が成り立つが，P (di )持つことが分かる．ただし，ベクトル群に対して 2 重の中心化の di 以外の子ノード dj に対して，C(dj ).time > di .time はを施す点，および，正規化の施し方の点に特徴を持つ．提案ア成り立つとは限らない．

ルゴリズムの 1 反復は，2 部グラフのリンク数に比例した計算

2. 2 極座標可視化法

量となる．よって，ネットワーク可視化の代表手法の一つバネ

二部グラフにおける 2 つのノード集合を同心円上に配置するモデル法 [9] などの非線形最適化が必要な可視化法と比較して，

手法 [7] をベースとして，構築したトピックフォレストのそれぞ

高速な方法である．

上記の手順により，第 1 階層と第 2 階層ノードの最適配置がな違いがある．この違いは，後述する可視化結果にも表れてお求まった．次いで，第 2 階層と第 3 階層ノードの関係性からそり，類似の文書を探索するという観点では，TF の方が優れてれらの最適配置を求める．

いると言える．
図 1(d) に，以下に示す平均類似度の値をプロットした：

3. 評 価 実 験

1 ∑ρ(d, P (d))|V|

実ニュース記事データに対する提案手法の処理結果について，1) 構築したトピックフォレスト（TF）の構造，2) 高次数
ノード，3) 可視化，4) アノテーションの観点から Minimum

Spanning Tree（MST）と比較して評価する．

以下，この値を平均隣接類似度と呼ぶ．図 1(d) から，α の値を大きくするにつれて，平均隣接類似度も高くなることがわ
かる．これは当然の結果である．なぜならば，TF 構築時に，

3. 1 データセット
提案手法の評価に際して，2014 年 4 月から 6 月までの Yahoo!
ニュースの 6,450 記事を用いる．含まれる語彙数は 31,090 であり，記事間の類似度としてベクトル空間モデル [10] で頻繁に用いられる単語頻度ベクトル（Bag Of Words）間のコサイン
類似度を採用する．データ中の主要な記事として，小保方晴子
氏の STAP 細胞問題，田中将大投手の MLB 移籍，セウォル号沈没事故などが含まれる．

ρ(di , dj ) > α である文書間にリンクを付与しているからである．すなわち，図 1(d) においては，平均隣接類似度は必ず閾
値 α より大きくなる．さらに，α > 0.1 で MST よりも高い値になることがわかる．
図 1(e) に，各文書に付与されているカテゴリの偏り具合をジニ係数により計算した値をプロットした．すなわち，ジニ係数の値が高いほど，各ツリーには限られたカテゴリが偏って含まれることを意味する．逆にジニ係数の値が低いほど，多くのカ3. 2 トピックフォレストの構造提案手法により構築したトピックフォレスト（TF）について，閾値パラメータ α を変化させた際の構造について評価する．図 1 に，横軸を α ，縦軸を各種統計量の値としたグラフを示す．図中の黒い実線は，MST における統計量の値を示す．
図 1(a) は，TF を構成するツリー数の推移と各ツリーに含まれる文書ノード数のジニ係数の値である．ジニ係数は，各ツリーのノード数に大きな差がある場合に 1 に近づき，均等な場
合に 0 に近づく．MST は単一のツリーであり結果は自明であるため，この図には示していない．なお，パラメータ α におけるツリー数を Kα ツリー T k (k = 1, . . . , Kα ) に含まれるノー
ド数を N (k) = |V (k) | とし，ジニ係数は以下のように計算した：∑Kα −1 ∑Kα(k)− N (h) |k=1
h=1 |N.
∑Kα(Kα − 1) k=1

d∈V

(4)

テゴリが均等に含まれていることを示す．図 1(e) から，MSTと比較して TF の方が有意にジニ係数が高いことがわかる．閾
値を設定して異なるトピックの文書ノードが異なるツリーに属するため，このような結果になり，TF の狙い通りの結果になったと言える．以上のことより，MST では単一のツリーとなり，異なるトピックの文書ノードが含まれるが，TF では異なるト
ピックの文書ノードは異なるツリーとなり，各ツリーには意味的凝集性があることが示された．
図 1(f) に，以下の式で計算される隣接する文書ノード間の投稿された時刻の間隔の平均値（以下，平均隣接投稿間隔）をプロットした：1 ∑|d.time − P (d).time|.
|V|d∈V

図 1(f) から，MST と比較して隣接ノード間の投稿間隔は小さ

ただし，ノード数 1 のツリーはカウントしない．図 1(a) からい，すなわち，より関連の強い文書ノード同士がつながっておわかることとして，り，各ツリーには時間的凝集性があることが示唆された．

•

α = 0 の際には単一のツリーとなる.

3. 3 高次数ノード•

α が大きくなるにつれてジニ係数は減少する．

次に，TF において高次数なノードを 3 ノード取り上げ，そ•α = 0.23 でツリー数が最大となる．

図 1(b) に，以下の式に示す次数分布のべき指数 a の値をプロットした．

の性質について定性的に評価する．上述の評価実験の結果を参考にして，表 1 にツリー数が最も多くなった α = 0.23 における高次数ノードを示す．表 1 を見ると，データ中で初期に投稿

DegDist(degree) = b × degree−a

された「マー君 メジャー初登板で勝利」という記事は，次数 15でツリーの中では高次数ノードである．その子ノード群を見る

図 1(b) から，MST と比較して TF のべき指数は小さいことがと，同様の内容の「マー君初勝利 何度もうれしい」や田中将大わかるが，0 < α < 0.2 あたりで 2 < a < 3 となり，実ネット

投手の妻である”里田まい”に関する記事「里田まい 特等席でワークと同様にスケールフリー性を有することがわかる．単一

マー君応援」が存在する．これらの記事の子孫として，”田中将ツリーとなる α = 0 においても，TF は MST と幾分か差があ大投手”に関する連日の話題が多くを占めていた．また，同一のることがわかる．MST は，TF の総ノード数，総リンク数と等

内容ではないものの関連する”マートン”，”黒田投手”，”ダル

しいが，次数分布は異なることが明らかとなった．

ビッシュ投手”なども子ノードとして存在している．これらの

図 1(c) に，TF の各ツリーの深さの平均と MST の深さプ

記事の子孫として，”田中将大投手”の内容ではなく”黒田投手”

ロットした．図 1(c) から，両者の深さには大きな違いがあるや”ダルビッシュ投手”などの話題が連なっており，高次数ノーことが見て取れる．単一ツリーとなる α = 0 においても，大きド「マー君 メジャー初登板で勝利」を機に分岐していた．

3.5

0.6

200

0.4

#Trees

300

100

0.2

0.2

0.4
0.6
Threshold α

0
1

0.8

80

2.5
2
1.5
1

0
0

(a) ツリー数とサイズのジニ係数

Average gini coefficient on node category

0.9
0.8
0.7
0.6
0.5
0.4

0.4
0.6
Threshold α

0.8

50
40
30

10

0.2

0.4
0.6
Threshold α

0.8

0
0

1

0.2

0.4
0.6
Threshold α1(d) 平均隣接類似度

1

0.8

1

(c) 深さ

0.9
0.8
0.7
0.6
0.5
0.4

0

0.8

25

1

0.2

60

(b) 次数分布のべき指数

1

0

70

20

0.5

Average interval between adjacent nodes

0
0

90

3
Average depth of each tree

0.8
Gini coefficient on tree sizes

400

Average similarity between adjacent nodes

100

1

Average exponent of degree distribution

500

0.2

0.4
0.6
Threshold α

0.8

20

15

10

5

0
0

1

0.2

(e) カテゴリジニ係数

0.4
0.6
Threshold α(f) 平均隣接投稿間隔

図 1 閾値パラメータ α に対する TF 構造の変化

高次数ノード「小保方氏 理研で研究続けたい」においても同様の傾向が見受けられた．”小保方氏本人”に関する記事，所属する組織である”理研”に関する記事，同分野の他の教授”山中教授”や”科学技術分野における不正”に関する記事を子ノードとしてもち，さらにそれを機に分岐している．
高次数ノード「ケミストリー堂珍が離婚へ」においても同様

1∑ T
x(h) (HN GHN )x(h)22

M(X) =h=1•(e) スペクトラル埋込法（SE 法）
S(X) =

2∑

xT(h) Lx(h)h=1の傾向が見受けられた．離婚というキーワードで他の夫婦（つにより α = 0 とした際の TF を可視化した結果を示す．ここで，ちやかおり／布川敏和，能世あんな／重松隆志など）の離婚話

HN = IN − N1 1N 1TN は中心化行列，L はグラフラプラシアン

題が子ノードとしてつながっており，その子孫として各夫婦の話題に分岐している．

行列，x(h) は全ノードの座標ベクトルのうち h 次元の値を並べたベクトルである．また，ρ(m, n) = exp(−||xm − xn ||2 /2)

このように，高次数ノードは関連する記事を子ノードとしてとした．さらに，多様体学習の代表手法である (f) ISOMAP

多く持ち，より密に関連する記事群へ枝分かれする分岐点の役（k-NN 法によるグラフ構築，ダイクストラ法によるノード間距割を果たしていることが示唆された．

離計算，多次元尺度構成法による可視化）による結果も示す．

3. 4 可視化結果

図 2 に，各可視化結果を示す．図中のノードの色は，対応す

次に，提案手法における可視化技術である極座標可視化法

る文書のカテゴリを表している．図 2(a) を見ると，時系列文（PCE 法）について評価する．以下の代表的なネットワーク可視

書が投稿時刻の順に従い同心円状に，かつ，リンクで結ばれた化手法と比較する．構築したグラフの隣接行列を A = [au,v ]，グ

関連文書や同一カテゴリの文書（同一色のノード）が原点からラフ上でのノード u, v 間の距離を要素とした行列を G = [gu,v ]見て同一方向に布置されており，半径と角度という軸により興とする．

味のある文書へのアクセシビリティが高いように見受けられる．

•(b) ばねモデル（SF 法）
K(X) =

N
−1
∑

N
∑

m=1 n=m+1

•

1
2
2gm,n

図 2(b) と (c) を見ると，ツリー構造がリンクの重なりなく平面に埋め込めるため，効率よく平面上に布置されており，かつ，(gm,n − ∥xm − xn ∥)2(c) クロスエントロピー法（CE 法）

C(X) = −

N
−1
∑

N
∑

し，提案手法と比較すると，文書の投稿順序は可視化結果に陽に反映されていない．さらに，SF 法と CE 法はニュートン法に基づく非線形最適化をしているため，布置座標を計算するの{am,n ln ρ(m, n)+(1−am,n ) ln(1−ρ(m, n))}m=1 n=m+1•

同一カテゴリ文書が近傍に布置されていることがわかる．しか(d) グラフ距離に基づく多次元尺度構成法（G-MDS 法）に多大な時間がかかる．一方 PCE 法では，HITS アルゴリズ
ムなどと同様なパワー法に基づく最適化をしているため，非常に高速に布置座標を計算できる．
図 2(d) と (e) を見ると，ノードが重なり合い文書間の関係

(a) 提案手法（TF+PCE）(b) TF+SF(c) TF+CE(d) TF+G-MDS(e) TF+SE(f) ISOMAP（4-NN+G-MDS）
図 2 α = 0 の TF の可視化結果が不鮮明である．G-MDS 法と SE 法は線形な手法であるため，間の関連が反映された結果となっている．ツリーを構築する提高速である一方で解の品質が良くなく，このような結果になっ案手法とは異なり k-NN グラフを構築するため閉路が存在し，たと考えられる．

文書間の順序関係が反映できない．一方提案手法では，TF 構

図 2(f) を見ると，同一カテゴリの文書が近傍に位置し，文書

築時に順序関係を考慮しているため，文書群の流れが陽にわか表 1 α = 0.23 の TF における高次数ノードの例
親【次数 15】マー君 メジャー初登板で勝利

子1

マー君初勝利 何度もうれしい子2

里田まい 特等席でマー君応援子3

マートン 7 打点でも阪神連敗

子4

ダル今季初勝利 エースの底力

子5

黒田 本拠地開幕戦で初勝利

子6

ヤ軍 16 失点大敗 内野手が登板

子7

マー君 ブーイング必至も不敵子8

マー君 2 者連続被弾も 3 勝目子9日本人トリオ 依存高まるヤ軍子 10 田中 4 失点降板 連勝止まるか
子 11 前回黒星マー君 1 失点で 7 勝目
子 12 田中 8 勝 防御率トップを維持
子 13 マー君 月間 MVP に初選出
子 14 第 2 のマー君 米メディア特集

図 3 MST+SF

子 15 「14 年版マー君」に川崎脱帽
親【次数 11】小保方氏 理研で研究続けたい子1

Twitter にみる小保方氏会見

子2

小保方氏 理研に不服申し立て

子3

小保方氏応援 tweet 批判の 2 倍ルとする．いま，H 次元の射影ベクトルを f とする．ここで，∑2∥f ∥ = H
h=1 fh = 1 とする．このとき，ベクトル f 上への座子4

iPS 臨床研究に向け準備着々標ベクトル群の射影値から構成される N 次元縦ベクトルは Xf

子5

慈恵医大 科研費を不正申請かとなる．よって，属性値ベクトル y をアノテートする妥当な方子6

偽医者 県財団だまし講演 14 回

向として，次式を最大にする射影ベクトル f を考える．

子7

笹井氏 STAP 論文撤回が適切

子8

山中教授 過去の切り貼り否定

子9

降圧剤 千葉大論文も改ざんか

現頻度を用いて y = [b1,j , · · · , bN,j ]T の N 次元属性値ベクト

F (f ) = yT Xf .

(5)

PCE 法により得られた座標ベクトル群 X を上述のように正規

子 10 小保方氏の指導役 STAP は本物化することで，式 (5) で定義した F (y) はベクトル Xf と y の子 11 理研 STAP で遠のく新法人指定
親【次数 6】ケミストリー堂珍が離婚へ相関係数と等価になる．よって，式 (5) で定義した r = F (f )子1

堂珍離婚報道 妻サイドは否定を以下では簡単に相関と呼ぶ．

子2

つちや ふっくんと離婚の決意

子3能世あんな、重松隆志と離婚

子4

A・バンデラス、女優と離婚か子5

高岡早紀の妹 離婚報道に驚き

子6

カイヤ 離婚は「分からない」

式 (5) の相関を最大化する f̂ はラグランジュ乗数法より以下
となる．

f̂ =

1
XT y.
∥XT y∥(6)

一方，式 (6) を式 (5) に代入すれば以下を得る．
る可視化結果を実現できている．

F (f̂ ) = ∥XT y∥.

(7)

最後に図 3 は，投稿時刻は考慮せず文書間の類似度だけで構築した MST をばねモデルで可視化したものである．前述した

よって，属性値ベクトル y を H 次元空間に埋め込むアノテー

とおり，ツリー全体の深さや直径が大きい点が TF との顕著なションとして，その方向と相関を，それぞれ式 (6) と 式 (7) で違いである．

規定する次式のベクトル（矢印）と定義する．

3. 5 アノテーション

Annot(y) = XT y.

(8)

この節では，提案手法の出力である可視化結果において，原点から見て同一方向に関連する文書ノード群が布置されてい明らかに，属性値ベクトル y に対して，式 (6) の矢印が長けれるかについて，アノテーションの観点から評価する．PCE 法

ば相関が高く有意なアノテーションと言えるが，矢印が短けれ

座標ベクトばアノテーションが困難なことを意味する．本稿では，全てのを用いる．ここで，座標ベクトル

単語 j に関して，属性値ベクトル y を構築しアノテーション

は重心が 0 に，各座標値の自乗和が 1 となるように正規化∑されているとする．すなわち， N
i=1 xi = 0，任意の次元 h
∑N 2
<
x
=
1
である．一方，アノテーション
H)
で
h
(1 <
= =
i=1 i,h対象とする文書ノードの属性値を各文書に出現する単語 j の出を試みる．そして，相関が上位の単語によりアノテーションをにより求めた N 個の文書ノードの H 次元
ル群 X = {x1 , · · · , xN }

T

（注 1）

付与することで，提案手法による可視化結果において，上位単語で特徴づけられる関連文書群が原点から見て同一方向に密集しているか評価する．
図 4 に，α = 0.23 の TF のうち大きなツリー 3 つに対する（注 1）：本稿では 2 次元極座標平面に可視化しているため，H = 2 である．

アノテーション結果を示す．相関ランキング上位 5 単語による

(a) 第 1 ツリー （野球）(b) 第 2 ツリー （中東情勢）(c) 第 3 ツリー（STAP 問題）

赤矢印：「イチロー」r = 0.49，

赤矢印：「イラク」r = 0.57，

赤矢印：「都内」r = 0.48，

緑矢印：「西武」r = 0.45，

緑矢印：「イスラム」r = 0.54，

緑矢印：「笹井」r = 0.45，

青矢印：「田中」r = 0.44，

青矢印：「バグダッド」r = 0.49，

青矢印：「幹細胞」r = 0.44，

黄矢印：「ダルビッシュ」r = 0.42，

黄矢印：「バント」r = 0.48，

黄矢印：「若山」r = 0.44，

桃矢印：「外野」r = 0.41

桃矢印：「イスラム教」r = 0.46

桃矢印：「証拠」r = 0.43

桃ノード：カテゴリがスポーツの文書

緑ノード：カテゴリが国際関係の文書

赤，水ノード：カテゴリが社会，科学の文書

図 4 α = 0.23 の TF に対するアノテーション結果

アノテーション矢印を示す．図中矢印の色は，キャプションにロットしている．本稿のトピックフォレスト構築時にも，投稿示している単語によるアノテーションを意味する．ノードの色間隔と文書間の類似度を考慮する点で関連する研究であるが，は，対応する文書のカテゴリを意味する．図 4(a) では，赤い各文書を極座標平面に布置する点，クラスタとしてまとめず各矢印の方向に「イチロー」という単語が出現する文書ノードが文書を可視化する点，ツリー構造としての文書間の関係を表現

多く存在することを表している．他の矢印でも同様に，各単語する点で異なる．

が出現する文書ノードが矢印の方向に多く存在することを意味

キーワード抽出や特徴選択の技術を用いて重要な単語

する．図 4(a) の結果より．提示した 5 単語に関して高い相関やトレンドワードを抽出し，その頻度をプロットすること係数を示しており，同一単語を有する関連文書が原点から見てで時系列全体を俯瞰する手法として，MemeTracker [12] や同一方向に布置されていることが示された．

EventRiver [13]，CloudLines [14]，STREAMIT [15] などがあ

図 4(b) では，上位 5 単語によるアノテーションの結果がする．Keim らの EventRiver [13] では，日々の出来事（イベン

べて同一方向を指している．右上および右下方向には，「ロシト）について記されたニュースやブログの記事群に対して，短

ア・ウクライナ情勢」に関する文書が散在しており，方向的にいタイムスパンのバケツに文書を分ける．バケツ内の文書をク広く分布しているため，布置座標と単語分布に強い相関が得ら

ラスタリングすることで，temporal-locality クラスタと呼ぶ時れない．これが起因して，相関上位の単語として，方向的にま間的凝集性と意味的凝集性の高い文書群に分割する．そして，

とまっている「イラク情勢」に関する文書ばかりが得られてし得られたクラスタ群をメタクラスタリングすることで，時間的まったと考えられる．

に離れていても内容的に類似するような，長期間にわたるイベ

図 4(c) では，図 4(a) と同様に，比較的高い相関係数が得らントに関する文書クラスタを一つのグループとしてまとめあげ

れ，各矢印の方向に同一単語が出現する関連文書が布置されてることができる．横幅をグループの生存時間，縦幅を各時点でおり，提案手法による可視化結果の有用性が示唆された．

の影響度とした成長曲線を描くことで，イベントの起点や終点，

4. 関 連 研 究盛り上がりなどが一目瞭然となり，関連イベントの発見も可能にする可視化結果を実現している．

本稿では，時系列文書群に対して，投稿順序を保持し，類似Krstajic らの CloudLines [14] は，あるキーワードを含むする文書群をつなぐことによりツリー群を構築し，効果的に可ニュース記事群を時間軸上に点としてプロットする．カーネル

視化する手法を提案した．時系列文書可視化の関連研究として，密度推定により投稿間隔が密なイベントを重要なイベントとし，Ishikawa らの T-Scroll がある [11]．このシステムでは，時間的点のサイズや透明度に反映させる．プロットされた点群は時間に離れた文書間の影響力が，指数的に小さくなる重みを導入し軸上で連なることで線となり，重要なイベントが発生した箇所

た類似度を定義し，k-means 法によりインクリメンタルなクラでは濃く太い線となる．このような工夫により，短時間で出現

スタリングを実現している．そして，隣接時刻間のクラスタ間頻度の高い記事を目立たせる可視化手法を提案している．イベに関連度を定義し，関連度の強いクラスタ間にリンクを付与す

ントの全体像を俯瞰することができ，各イベントを拡大するこることで，各時刻におけるクラスタリング結果を時間軸上にプとでその詳細を把握することができる．

これらの既存技術では，横軸に時間軸を設定し，各トピックやトレンドの変化をプロットすることで全体像を把握できるよ
うに工夫されている．さらに，ユーザが興味あるトピックやトレンドを選択することで，より詳細な情報を入手できる点で優れている．本稿の提案手法がこれら既存技術と異なる最大のポイントは，各話題やトピックが時間発展する中で複数の観点に分岐する様子をツリー構造により表現できる点である．各話題
においては，一般的に情報が広がっていく傾向にあるため，極座標可視化のように，原点付近では描画領域が限られていても，原点から離れる（半径が大きくなる）につれて描画領域が広くなるのもメリットの一つである．

Alsakran らの STREAMIT [15] は，あるスナップショットにおける文書群を粒子として扱い，文書粒子間の類似度に基づき力学モデルにより 2 次元平面での最適配置を計算する．すなわ
ち，類似する文書粒子は平面上で近傍に，類似しない文書粒子
は遠くに配置される．新規に追加される文書に対して，動的に最適配置を再計算し，各スナップショットでの最適配置をアニ
メーションにより表示する．平面に配置された文書粒子に対して，ドロネー三角形によるグラフを構築し，閾値パラメータより長いリンクを切断することで，文書クラスタを形成する．この点は，閾値より離れた文書ノードを別のツリーとする提案手法と類似している．一方で，極座標平面の半径により時間軸を表現する我々の提案手法とは異なり，アニメーションにより対応する文書クラスタの変化を表現する点で大きく異なる．すな
わち，STREAMIT は，時系列データの俯瞰という観点ではデメリットがある．

5. お わ り に本研究では，ユーザの興味ある文書へのアクセシビリティ向上をめざし，時々刻々と投稿される時系列文書群を意味的凝集性と時間的凝集性の観点で適切に可視化する手法を提案した．
提案手法におけるトピックフォレスト（TF）は，類似の文書
ノードの投稿順序を保存した構造を実現し，極座標可視化法（PCE）は，原点から見て同一方向に関連文書を布置できることを実験により確認した．
今後の課題として，各文書が投稿された時刻を極座標可視化法における半径に反映するなどの拡張をすることで，より効果的な可視化をめざす．TF では，ツリー構造により話題の発展，分岐を表現できたが，話題の収束に関しては表現できない．複数の文書をまとめる文書を DAG 構造などにより表現することも今後の課題となる．さらに，本稿の実験では，TFIDF のコサイン類似度を用いたが，分散表現などによる文書間の類似度を用いることも理論上は可能であるため，他の類似度指標と可視化法の親和性についても検証が必要である．
謝辞 本研究は，JSPS 科研費 16K16154 の助成を受けたものです．
文

献[1] A. Šilić and B.D. Bašić, “Visualization of text streams: A
survey,” pp.31–43, Springer Berlin Heidelberg, Berlin, Heidelberg, 2010.
[2] L. van derMaaten and G.E. Hinton, “Visualizing highdimensional data using t-sne,” Journal of Machine Learning

Research, vol.9, pp.2579–2605, 2008.
[3] T. Iwata, K. Saito, N. Ueda, S. Stromsten, T.L. Griﬃths,
and J.B. Tenenbaum, “Parametric embedding for class visualization,” Advances in Neural Information Processing Systems 17, eds. by L.K. Saul, Y. Weiss, and L. Bottou, pp.617–
624, MIT Press, 2005.
[4] J.B. Tenenbaum, V. Silva, and J.C. Langford, “A Global
Geometric Framework for Nonlinear Dimensionality Reduction,” Science, vol.290, no.5500, pp.2319–2323, 2000.
[5] S.T. Roweis and L.K. Saul, “Nonlinear dimensionality reduction by locally linear embedding,” SCIENCE, vol.290,
pp.2323–2326, 2000.
[6] M. Belkin and P. Niyogi, “Laplacian eigenmaps and spectral techniques for embedding and clustering,” Advancesin Neural Information Processing Systems 14, pp.585–591,
MIT Press, 2001.
[7] T. Fushimi, Y. Kubota, K. Saito, M. Kimura, K. Ohara,and H. Motoda, “Ai 2011: Advances in artificial intelligence: 24th australasian joint conference, perth, australia,
december 5-8, 2011. proceedings,” chapter Speeding Up Bipartite Graph Visualization Method, pp.697–706, Springer
Berlin Heidelberg, 2011.
[8] J.M. Kleinberg, “Authoritative sources in a hyperlinked environment,” J. ACM, vol.46, pp.604–632, Sept. 1999.
[9] T. Kamada and S. Kawai, “An algorithm for drawing general undirected graphs,” Inf. Process. Lett., vol.31, pp.7–15,
April 1989.
[10] G. Salton, A. Wong, and C.S. Yang, “A vector space model
for automatic indexing,” Commun. ACM, vol.18, no.11,
pp.613–620, Nov. 1975.
[11] Y. Ishikawa and M. Hasegawa, “T-scroll: Visualizing trends
in a time-series of documents for interactive user exploration,” pp.235–246, Springer Berlin Heidelberg, Berlin,
Heidelberg, 2007.
[12] J. Leskovec, L. Backstrom, and J.M. Kleinberg, “Memetracking and the dynamics of the news cycle,” KDD,
pp.497–506, 2009.
[13] D.A. Keim, D. Luo, J. Yang, W. Ribarsky, and M. Krstajic,“Eventriver: Visually exploring text collections with temporal references,” IEEE Transactions on Visualization &Computer Graphics, vol.18, pp.93–105, 2010.
[14] M. Krstajic, E. Bertini, and D.A. Keim, “Cloudlines: Compact display of event episodes in multiple time-series.,”IEEE Trans. Vis. Comput. Graph., vol.17, no.12, pp.2432–
2439, 2011.
[15] J. Alsakran, Y. Chen, D. Luo, Y. Zhao, J. Yang, W. Dou,and S. Liu, “Real-time visualization of streaming text with aforce-based dynamic system,” IEEE Comput. Graph. Appl.,
vol.32, no.1, pp.34–45, Jan. 2012.