DEIM Forum 2016 A2-4

時空間的な投稿数を考慮した密度に基づく適応的な
時空間クラスタリング手法
酒井達弘†

田村慶一 ††

北上

始 ††† , †† 広島市立大学大学院情報科学研究科 〒 731-3194 広島県広島市安佐南区大塚東 3-4-1
E-mail: †da65003@e.hiroshima-cu.ac.jp, ††{ktamura,kitakami}@hiroshima-cu.ac.jp
あらましソーシャルメディア上に投稿される位置情報付きのデータを用いて実世界で注目を集めているトピックの時空間的な変遷を分析する研究が行われている．我々は先行研究において，密度に基づく時空間クラスタリングを用いてトピックの時空間的な変遷をモニタリングする手法を提案している．先行研究のモニタリング手法で使用していた密度に基づく時空間クラスタリングでは，投稿数の多い地域と少ない地域，また投稿数の多い時間帯と少ない時間
帯がある場合に，適切に時空間クラスタを抽出できないため，トピックの発生を正確に把握することができなかった．
本論文では，この問題点を解決するために，密度に基づく適応的な時空間クラスタリングを提案する．提案手法は，
時空間クラスタの抽出の基準となる閾値を各地域と各時間帯において適応的に変化させることで，投稿数が多い地域と投稿数が少ない地域，また時間帯を区別することなく，時空間クラスタを抽出することができる．提案手法をモニ
タリング手法に導入し評価実験を行った結果，提案手法は従来手法と比較して，より高性能にトピックの発生を捉えることができた．

キーワード

時空間クラスタリング，密度に基づくクラスタリング，Twitter，ジオタグ付きツイート，ソーシャルメ

ディア

1. は じ め にの降っている地域の拡大や移動などをトピックの変化，大雨が止むことをトピックの消滅とする．先行研究では，時空間クラビッグデータへの関心の高まりとともに，ソーシャルメディ

スタの抽出と更新を行うことでトピックの時空間的な変遷を捉ア上に投稿されるデータを用いて実世界で注目を集めているト

えることができる．ある地域で大雨が降り始めるとその地域でピックを分析する研究が行われている．また，GPS 付きスマーは人々が盛んに大雨に関する投稿を始める．時空間的に密に投トフォンの普及により，位置情報付きのデータがソーシャルメ

稿されたジオタグ付きツイート集合を時空間クラスタとして抽ディア上に盛んに投稿されており，位置情報付きのデータを利出することで，トピックの発生を捉えることができる．また，用することで，トピックの時間変化だけでなく，空間的な変遷

トピックの変化に合わせて，抽出される時空間クラスタの大きも分析が可能となってきている [1]．例えば，Twitter 上では，

さが変化する．そして，時空間クラスタが抽出されなくなった

台風，大雨や大雪などの自然災害発生時にそれらの状況を伝え

地域は大雨に関するトピックが消滅したことを示す．

るジオタグ付きツイートが投稿されている [2]，[3]，[4]．このジ先行研究において評価実験を行った結果，大雨と大雪に関す

オタグ付きツイートを用いることで，自然災害が発生しているるトピックの時空間的な変遷をモニタリングできることを確認

地域と当該事象の時間変化把握することができる．

した．しかしながら，地域や時間帯によって投稿数に差異があ

我々は，先行研究 [5] において，Twitter 上に投稿されるジる場合に，時空間クラスタの抽出の基準となる閾値を適切に設

オタグ付きツイートを対象として，密度に基づく時空間クラス

定することが困難になるという問題が生じていた．図 1 に問題タリングを用いてトピックの時空間的な変遷をモニタリングすが起こる例を示す．図 1 の左側は普段の投稿数が多い地域である手法を提案している．この手法では，モニタリングの対象とり，右側は普段の投稿数が少ない地域であるとする．ここで，なっているトピックを含むツイートをナイーブベイズ分類器を

データ集合 A または B に合わせて閾値を設定すると，データ用いて取り出す．そして，当該トピックに関連するツイートが集合 A と B が時空間クラスタとして抽出される．閾値を下げ，盛んに投稿されている地域を，密度に基づく時空間クラスタリ

データ集合 C または D に合わせて閾値を設定すると，データングを用いて時空間クラスタとして抽出することで，当該ト集合 A，B，C と D が時空間クラスタとして抽出される．デー

ピックの時空間的な変遷をモニタリングすることができる．

タ集合 C と D は同じ程度でデータが密集しているが，データ

ここで，トピックの時空間的な変遷とは，ある地域において集合 C は普段の投稿数と比べると高密度であり，データ集合 D

トピックが発生，変化と消滅することを指す．例えば，トピッ

は普段の投稿数と比べると低密度であるという違いがある．こクを大雨としたとき，大雨の降り始めをトピックの発生，大雨のように地域や時間帯によって普段の投稿数を考慮した相対的ことを示した．Karimi ら [13] は，自然災害に関する内容のツ᫬㛫

イートの分類手法を提案している．しかしながら，これらの研究はツイートの分析や分類のみに焦点を当てている．本研究で䝕䞊䝍㞟ྜAは，ツイート分類と時空間クラスタリングを組み合わせること䝕䞊䝍㞟ྜCで，トピックの時空間的な変遷のモニタリングを可能にする．
また，Thom ら [14] は，ジオタグ付きツイートから異常を検出し，対話型のクラウドシステム上で可視化することで，発生した地震などの自然災害がどのくらい影響があるのか提示する䝕䞊䝍㞟ྜDシステムを開発した．Aramaki ら [15] は，ツイートにサポー䝕䞊䝍㞟ྜB⦋ᗘ

トベクターマシン（SVM）やナイーブベイズなどの分類器を⤒ᗘ

適用し，インフルエンザの流行を検出するための手法を提案した．Aramaki らの手法では，各地域の投稿数の増減を求めるこ
図 1 先行研究の問題点とで，インフルエンザの影響度を提示している．Aramaki らとThom らの研究の研究は，我々の研究に最も近い研究であるが，な密度には違いがあり，データ集合 A，B と C が時空間クラス

彼らのシステムはトピックがどういう状況なのかということをタとして抽出されるような閾値を設定する方法を考える必要が把握することができない．本研究では，時空間クラスタリング
ある．
によってトピックの変遷を確認でき，ジオタグ付きツイートの本論文では，この問題点を解決するために，密度に基づく適本文からトピックの状況を把握することができる．
応的な時空間クラスタリングを提案する．密度に基づく適応的

Avvenuti ら [16] は，各地域の地震による損害を把握するたな時空間クラスタリングは，各地域，各時間帯における過去のめの EARS（Earthquake alert and report system）というシ

投稿数を考慮し，基準となる閾値を適応的に変化させる．密度ステムを開発している．Kim ら [17] は，トピックの時空間的なに基づく適応的な時空間クラスタリングを用いることで，投稿変化を可視化する mTrend というシステムを提案した．Kumar

数が多い地域と投稿数が少ない地域，また時間帯を区別するこら [18] は，道路上で発生した危険な状況を Twitter 上のユーザとなく，時空間クラスタを抽出することができる．
を用いて検出した．しかしながら，これらの手法は地域や時間提案手法をモニタリング手法に導入し，評価実験を行った．
帯によって投稿数が異なることを考慮できていない．
評価実験の結果，提案手法は従来手法と比較して，より高性能
また，密度に基づくクラスタリングのパラメータの変化によにトピックの発生を捉えることができた．

るクラスタリング結果の違いを分析するための手法，OPTICS

本論文の構成は以下の通りである．第 2 章では，関連研究をが提案されている [19]．OPTICS は，密度に基づくクラスタリ

述べる．第 3 章では，先行研究である (ǫ, τ )-密度に基づく時空

ングの距離の基準となるパラメータについて，様々な値を設定

間クラスタリングを用いたトピックのモニタリング手法とそのした際に各パラメータ値でどのようなクラスタリング結果が得問題点を示す．第 4 章では，提案手法である (ǫ, τ )-密度に基づられるのか，分析することができる．OPTICS を用いること

く適応的な時空間クラスタリングについて述べる．第 5 章では，で，データセットごとにパラメータを適切な値に設定すること

評価実験の実験結果を示し，第 6 章で本論文をまとめる．

ができる．しかしながら，OPTICS では，クラスタリングを行

2. 関 連 研 究う際には分析結果から一つのパラメータ値を決めてクラスタリ
ングを行う．本論文の提案手法では，一つの値を定めるが，そ近年，ソーシャルメディアサイトの発展とスマートフォンののパラメータの値を各地域，各時間帯によって適応的に変化さ
普及により，ソーシャルメディアサイト上の位置情報付きのせることで，データセットの中で適切な時空間クラスタを抽出
データは急速に増加している [6]．その中でも，最も普及しているソーシャルメディアサイトの一つである Twitter 上のジオタ
グ付きツイートを用いて，実世界で起こっているトピックを分析する研究が行われている [1]．例えば，Sakaki ら [7] は，位置情報付きのツイートから台風の軌道と地震の震源地を予測する手法を提案し，Ozdikis ら [8] も，Twitter 上に投稿される地震することができる．

3. (ǫ, τ )-密度に基づく時空間クラスタリングを用いたトピックのモニタリング手法
本章では，(ǫ, τ )-密度に基づく時空間クラスタリングを用いたトピックのモニタリング手法 [5] について説明する．

に関する情報から地震の場所を推定する研究を行った．これら

3. 1 モニタリング手法の概要のように，ジオタグ付きのツイートを用いることで地震や台風

図 2 に (ǫ, τ )-密度に基づく時空間クラスタリングを用いたトなどの自然災害をはじめとした緊急性のあるトピックの分析がピックのモニタリング手法の概要図を示す．モニタリングでは，可能となる [9]，[10]，[11]．

以降の処理を一定時間毎に実行する．ジオタグ付きツイートク

Murakami ら [12] は，2011 年に発生した東日本大震災時にローラを用いて Twitter からジオタグ付きツイートを収集し，投稿されたツイートを分析した．Vieweg ら [3] は，火災や洪水ジオタグ付きツイートデータベースに保存する．ナイーブベイなどの緊急的な状況に関する情報が Twitter 上に投稿される

ズ分類器 [20] を用いてモニタリング対象のトピックに関連する

䝰䝙䝍䝸䞁䜾ᑐ㇟䛾ᩍᖌ䝕䞊䝍

Twitter䝴䞊䝄

relevant
irrelevant䝆䜸䝍䜾௜䛝䝒䜲䞊䝖
䜽䝻䞊䝷
⾲♧

Ꮫ⩦
䝒䜲䞊䝖ศ㢮

䝆䜸䝍䜾௜䛝䝒䜲䞊䝖䝕䞊䝍䝧䞊䝇

᪂䛧䛟ධຊ䛥䜜䛯䝒䜲䞊䝖䝒䜲䞊䝖䜽䝷䝇䝍䝸䞁䜾

䝖䝢䝑䜽䜢ྵ䜐䝒䜲䞊䝖

図 3 定義 1 と 3 の例
図2モニタリング手法の概要

きツイート間の投稿間隔を求める関数である．
関連ジオタグ付きツイートとそれ以外のツイートに分類を行う．
関連ジオタグ付きツイートとこれまでに抽出された時空間クラスタ集合を入力として，(ǫ, τ )-密度に基づく時空間クラスタリ
ングを用いて新しく時空間クラスタ集合を抽出する．(ǫ, τ )-密度に基づく時空間クラスタリングについては，3.3 節で説明す
る．抽出された時空間クラスタの内容を地図上に表示し，ユー

図 3 に例を示す．関連ジオタグ付きツイート rgtp から距離ǫ 以内に，rgt1 ，rgt2 と rgt3 の 3 つ，また，rgtp から投稿間
隔 τ 以内にも，rgt1 ，rgt2 と rgt3 の 3 つの関連ジオタグ付き
ツイートが存在する．この時，rgtp の (ǫ, τ )-密度に基づく近傍
は，rgt1 ，rgt2 と rgt3 の 3 つとなる．また，rgtq の (ǫ, τ )-密度に基づく近傍は，rgt4 の 1 つとなる．

ザへ提示する．
ここで，時空間クラスタの核となる関連ジオタグ付きツイー

3. 2 データ定義

トの (ǫ, τ )-密度に基づく近傍には，M inRGT （ユーザパラメー

ジオタグ付きツイートを gti と表記し，その集合を GT S =タ）以上の関連ジオタグ付きツイートが存在すると定義する．

{gt1 , · · · , gtn } とする．ここで，gti は文書データ texti ，投稿
時間 pti と位置情報 pli の 3 つから構成される．本研究では位置

そして，(ǫ, τ )-密度に基づく時空間クラスタリングでは核となる関連ジオタグ付きツイートの (ǫ, τ )-密度に基づく近傍を結合情報として経度，緯度を用いる．また，モニタリングの対象としていくことで，クラスタリングを行う．
しているトピックの内容を含むジオタグ付きツイートを関連ジ

3. 4 先行研究の問題点

オタグ付きツイート rgtj （= gtφ(j) ）と呼ぶ．関連ジオタグ付先行研究で用いられている (ǫ, τ )-密度に基づく時空間クラス

きツイート集合を RGT S = {rgt1 , · · · , rgtm } とすると，GT S
タリングは，時空間的に高密度な時空間クラスタを抽出する
は RGT S を包含しており（RGT S ⊂ GT S ），次の単射で表現ために有効な手法である．しかしながら，データの分布によっされる．
ては，時空間クラスタを抽出することが困難な場合がある．こφ(j) : RGT S → GT S; rgtj 7→ gtφ(j)(1)

れは，地域や時間帯によって投稿数には差異があり，適切なM inRGT を設定しなければならないからである．投稿数の多
3. 3 (ǫ, τ )-密度に基づく時空間クラスタリング

い場合と少ない場合に分けて M inRGT を設定する方法が考え

密度に基づく空間クラスタリング [21]，[22] では，データが密られるが，このような時空間的な投稿数の差異は三次元的に複集している部分を空間クラスタ，密集していない部分を空間ク雑に生じているため，手作業で行うのは困難である．例えば，ラスタではないと定義し，空間クラスタを抽出する．(ǫ, τ )-密度に基づく時空間クラスタリング [23] は，密度に基づく空間ク

高密度な地域に合わせて M inRGT を設定すると，図 1 のデー
タ集合 C のような，高密度な地域から考えれば低密度であるがラスタリングを拡張し，ジオタグ付きツイートの位置情報と投周辺の投稿数から考えると高密度な地域，つまり，局所的に高稿時間に着目し，距離が ǫ 以内であり，投稿間隔が τ 以内であ密度な時空間クラスタを抽出できない．反対に，低密度な地域
るジオタグ付きツイートを (ǫ, τ )-密度に基づく近傍と定義してに合わせて M inRGT を設定すると，投稿数の多い地域では，いる．

図 1 のデータ集合 D のような，周辺の投稿数から考えると低［定義 1］（(ǫ, τ )-密度に基づく近傍） 関連ジオタグ付きツイー

密度な時空間クラスタが抽出されてしまう．

ト rgtp の (ǫ, τ )-密度に基づく近傍を ST N(ǫ,τ ) (rgtp ) と表記し，
以下のように定義する．

4. (ǫ, τ )-密度に基づく適応的な時空間クラスタリング

ST N(ǫ,τ ) (rgtp ) = {rgtq ∈ RGT S |dist(rgtp , rgtq ) <= ǫ and iat(rgtp, rgtq ) <= τ } (2)

本章では，提案手法である (ǫ, τ )-密度に基づく適応的な時空間クラスタリングについて述べる．

関数 dist は経度・緯度などの座標値を使って，ジオタグ付きツ4. 1 概イート間の空間上の距離を求める関数，関数 iat はジオタグ付

3.4 節であげた問題点を解決するためには，各地域，各時間

要᫬㛫

帯であるが，地域が異なり，普段の投稿数が少ない地域である
ため，時空間投稿密度が小さくなっている．
0.0
rgt1
rgt3

䠍䠎᫬
䠍䠍᫬

4. 3 諸 定 義᫬✵㛫ᢞ✏ᐦᗘ

䠎䠏᫬

本節では，(ǫ, τ )-密度に基づく適応的な時空間クラスタリン
グの諸定義について説明する．
［定義 3］（核/周辺 関連ジオタグ付きツイート） 関 連 ジ オ タ

䠍䠌᫬
rgt2

グ 付 き ツ イ ー ト rgtp に つ い て ，|ST N(ǫ,τ ) (rgtp )|

1.0
䠌᫬

>

AT (rgtp, M axM inRGT ) を 満 た す と き ，rgtp を 核 関 連
ジ オ タ グ 付 き ツ イ ー ト，反 対 に ，|ST N(ǫ,τ ) (rgtp )| <=ᗙᶆ✵㛫AT (rgtp, M axM inRGT ) であるとき，rgtp を周辺関連ジオ

図 4 時空間投稿密度の例

タグ付きツイートと呼ぶ．
帯によって適切な閾値を設定しなければならない．(ǫ, τ )-密度

図 3 を使い，例を示す．M axM inRGT = 3，lstd(rgtp) =0.8，lstd(rgtq ) = 0.8 とすると，AT (rgtp, M axM inRGT ) =に基づく適応的な時空間クラスタリングでは，各地域，各時間

2.6，AT (rgtq , M axM inRGT ) = 2.6 となる．つまり，関連ジ
帯によって適応的に変化する新しい閾値を定義する．具体的に，オタグ付きツイート rgtp は核関連ジオタグ付きツイートであ
各地域，各時間帯の過去における投稿数を時空間投稿密度としり，関連ジオタグ付きツイート rgtq は周辺関連ジオタグ付きて定義し，時空間投稿密度を用いて閾値を適応的に変化させる．
ツイートである．
投稿数の多い地域，投稿数の多い時間帯では閾値は高く，投稿数の少ない地域，投稿数の少ない時間帯では閾値は低く設定さ［定義 4］（(ǫ, τ )-密度に基づいて適応的に直接到達可能） 関連

れる．したがって各地域，各時間帯にとって適切な閾値が設定

ジオタグ付きツイート rgtq が rgtp の (ǫ, τ )-密度に基づく近傍に存在し，|ST N(ǫ,τ ) (rgtp )| > AT (rgtp, M axM inRGT ) を満することができる．

たす時，関連ジオタグ付きツイート rgtq は rgtp から (ǫ, τ )-密

4. 2 適応的な閾値度に基づいて適応的に直接到達可能であると表現する．
本節では，適応的な閾値について説明する．
［定義 2］（適応的な閾値） 関連ジオタグ付きツイート rgtp の［定義 5］（(ǫ, τ )-密度に基づいて適応的に到達可能） 関連ジオ

適応的な閾値を AT (rgtp, M axM inRGT ) と表記し，以下のよ

タグ付きツイート rgtp+1 が rgtp から (ǫ, τ )-密度に基づいて適応的に直接到達可能である，関連ジオタグ付きツイート列

うに定義する．

(rgtp, rgt(p+1) , · · · , rgt(p+l) ) を考える．この時，関連ジオタグ
AT (rgtp, M axM inRGT ) =(M axM inRGT − 1) × lstd(rgtp) + 1

付きツイート rgt(p+l) は rgtp から，(ǫ, τ )-密度に基づいて適応(3)

的に到達可能であると表現する．

関数 lstd(rgtp) は rgtp の時空間投稿密度を返す関数であり［定義 6］（(ǫ, τ )-密度に基づいて適応的に接続） 関連ジオタグ(0 <= lstd(rgtp ) <= 1)，M axM inRGT はユーザが与えるパラ付きツイート rgtp と rgtq とが rgto から (ǫ, τ )-密度に基づメータである．

い て 適 応 的 に 到 達 可 能 で あ り，rgto が |ST N(ǫ,τ ) (rgto )| >時空間投稿密度は過去に投稿されたジオタグ付きツイートの統計量から算出する．まず，対象とする時空間領域を 3 次元の時空間グリッドに分割（divlng × divlat × divtime ）する．次に，AT (rgto, M axM inRGT ) を満たす時，rgtp と rgtq とは (ǫ, τ )密度に基づいて適応的に接続していると表現する．

4. 4 (ǫ, τ )-密度に基づく適応的な時空間クラスタ

各時空間グリッドに含まれる過去に投稿されたジオタグ付きツ(ǫ, τ )-密度に基づく適応的な時空間クラスタリングでは，時イートの数をカウントする．関数 lstd は次の式で正規化した値

空間的に密集している関連ジオタグ付きツイート集合を (ǫ, τ )密度に基づく適応的な時空間クラスタと定義する．

を返す．

lstd(rgtp) =stnum(geo gid(rgtp)) − stnummin
stnummax − stnummin(4)［定義 7］（(ǫ, τ )-密度に基づく適応的な時空間クラスタ） 関連
ジオタグ付きツイート集合 RGT S において，(ǫ, τ )-密度に基づ

ただし，関数 stnum(i) は時空間グリッド i のジオタグ付きツく適応的な時空間クラスタ astc は次の 2 つの条件を満たす部

イート数を返す関数である．geo gid(rgtp) は rgtp が属する時

分関連ジオタグ付きツイート集合である．

空間グリッドの ID を返す関数である．stnummax と stnummin（1）は最大数と最小数である．

と rgtq ∈ RGT S について，(ǫ, τ )-密度に基づく適応的な時

任意の関連ジオタグ付きツイート rgtp ∈ RGT S

図 4 に例を示す．この例では，全時空間が 3 × 3 × 24 の時

空間クラスタ astc に関連ジオタグ付きツイート rgtp が所属

空間に分割され，各地域，また，各時間帯において時空間投稿（rgtp ∈ astc）し，関連ジオタグ付きツイート rgtq が rgtp か

密度が変化している．関連ジオタグ付きツイート rgt1 と rgt2

ら (ǫ, τ )-密度に基づいて適応的に到達可能であれば，rgtq はとは同一地域に存在しているが，時間帯が異なる．関連ジオタ

astc に所属（rgtq ∈ astc）する．

グ付きツイート rgt1 は日中であり，時空間投稿密度が rgt2 よ（2）

りも高い．関連ジオタグ付きツイート rgt3 は rgt1 と同一時間に所属する任意の関連ジオタグ付きツイート rgtp ∈ astc と(ǫ, τ )-密度に基づく適応的な時空間クラスタ astc

rgtq ∈ astc は，(ǫ, τ )-密度に基づいて適応的に接続している．
4. 5 アルゴリズム

input : rgt - 新しく取得した関連ジオタグ付きツイート, RGT S- これまでに取得した関連ジオタグ付きツイート集合,(ǫ, τ )-密度に基づく適応的な時空間クラスタリングのアルゴ

AST CS - 前回抽出した時空間クラスタ集合,

リズムを Algorithm1 に示す．新しく取得した関連ジオタグ付

ǫ, τ , M axM inRGT - ユーザパラメータ

きツイート，これまでに取得した関連ジオタグ付きツイート集

output: AST CS ′ - 更新された時空間クラスタ集合

合，前回抽出された時空間クラスタ集合（AST CS ）を入力し，

N RGT ← GetNeighborhood(rgt,ǫ,τ );′更新された時空間クラスタ集合（AST CS ）を出力する．関連

for i ← 1 to |N RGT | do
nrgt ← nrgti ∈ N RGT ;ジオタグ付きツイートを取得したとき，新たに取得した関連ジオタグ付きツイートの (ǫ, τ )-密度に基づく近傍に存在する関連ジオタグ付きツイートのみに影響があるため，それらの関連ジ

ST N ← GetNeighborhood(nrgt,ǫ,τ );if |ST N | > AT(nrgt, M axM inRGT ) thenif IsClustered(nrgt) == f alse thenastc ← MakeNewCluster(nrgt);

オタグ付きツイートを対象に再クラスタリングを行う．また，
再クラスタリングの際に，二つの (ǫ, τ )-密度に基づく適応的な

end

時空間クラスタが結合し，一つとなることもある．

else
astc ← GetCluster(nrgt,AST CS);

Algorithm1 を詳しく説明する．
（ 1 ） 新しく取得した関連ジオタグ付きツイート rgt の (ǫ, τ )-end
EnQueue(Q,ST N );

密度に基づく近傍を取得し，再クラスタリングの対象として
while Q is not empty do

N RGT に挿入する．

qrgt ← DeQueue(Q);（ 2 ） N RGT から関連ジオタグ付きツイート nrgt を 1 つ取

ST N ← GetNeighborhood(qrgt,ǫ,τ );り出す．ただし，N RGT が空ならば（9）へ進む．

if |ST N | >AT(qrgt, M axM inRGT ) then

（ 3 ） nrgt が核関連ジオタグ付きツイートであるかチェック

if IsClustered(qrgt) == true thenする．もし，核関連ジオタグ付きツイートであれば（4）を実

astc′ ← GetCluster(qrgt,AST CS);行し，核関連ジオタグ付きツイートでなければ（2）に戻る．

astc ← AppendClusters(astc,astc′ );end（ 4 ） nrgt が時空間クラスタに所属していれば，nrgt の所

else

属する時空間クラスタを取得し， astc とする．時空間クラス

astc ← astc ∪ qrgt;

タに所属していなければ，新たに時空間クラスタ astc を作成
する．

EnNniqueQueue(Q,ST N );イート集合としてキュー Q に挿入する．

end
end
end

（ 6 ） Q から関連ジオタグ付きツイート qrgt を取り出し，次AST CS ← AST CS ∪ astc;（ 5 ） nrgt の (ǫ, τ )-密度に基づく近傍を関連ジオタグ付きツの処理を行う．
（ a ） qrgt が核関連ジオタグ付きツイートであるかチェッ
クし，核関連ジオタグ付きツイートであれば，（b）へ移る．
核関連ジオタグ付きツイートでなければ（7）へ進む．
（ b ） qrgt が時空間クラスタに所属していれば（i）を，時空間クラスタに所属していなければ，（ii）を実行する．

end
end
AST CS ′ ← DeleteOldCluster(ASTCS );return AST CS ′ ;Algorithm 1: (ǫ, τ )-密度に基づく適応的な時空間クラス
タリングアルゴリズム

i. qrgt の所属する時空間クラスタ astc′ と astc
評価実験の結果を示す．

を結合する．

ii. qrgt を astc に挿入する．qrgt の (ǫ, τ )-密度に基づく近傍から，キュー Q に存在しない関連ジオタグ

5. 1 データセットと実験内容
評価実験では，モニタリング手法の時空間クラスタリング部
分について，従来手法 [5] と提案手法を用いた場合で比較を行付きツイートを Q に挿入する．
（ 7 ） キュー Q が空であれば（8）へ移る．空でなければ（6）う．モニタリングの対象とするトピックを「大雨」と「大雪」へ戻る．

とし，2014 年 6 月と 7 月に投稿されたジオタグ付きツイート（ 8 ） 時空間クラスタ集合 AST CS に astc を加え，
（2）へを用いてトピック「大雨」を，2014 年 1 月と 2 月に投稿された戻る．

ジオタグ付きツイートを用いてトピック「大雪」の評価を行う．

（ 9 ） AST CS から，現在時刻から τ 前までに更新がない時パラメータとしては，ǫ = 5km，τ = 3600sec を用いた．

空間クラスタを削除し，AST CS とする．AST CS を更新さ

従来手法のパラメータ M inRGT と提案手法のパラメータ

れた時空間クラスタ集合として出力する．

M axM inRGT はそれぞれ 2 から 10 まで変化させて実験を′′

5. 評 価 実 験
提案手法を評価するために，評価実験を行った．本章では，行った．時空間投稿密度を求める対象領域は日本の最西端の緯度・経度 (24.4494, 122.93361) と最北端の緯度・経度 (45.5572,

148.752) からなる矩形とし，パラメータは divlng = 1, 000，

表 1 大雨が観測された 16 日間に収集したツイート数
日付
ツイート数 関連ツイート数
2014/6/4
3250952249
2014/6/6
3121456401
3305404433
2014/6/7
2014/6/13
3465072589
340675750
2014/6/16
2014/6/22
4118634172
355384700
2014/6/23
2014/6/25
3934412331
4419594838
2014/6/29
2014/7/3
3417704738
3767344173
2014/7/7
2014/7/8
3668871405
3747074704
2014/7/9
2014/7/10
3950614803
3837041763
2014/7/11
2014/7/19
4124035369
表 2 大雪が観測された 11 日間に収集したツイート数
日付
ツイート数 関連ツイート数
2014/1/10
2823702665
2014/1/14
284215981
283809995
2014/1/17
2014/2/6
2840652821
35086727823
2014/2/8
2014/2/11
2896283564
3061063953
2014/2/13
2014/2/14
37836821834
25637810060
2014/2/15
2014/2/16
3077085121
2621452325
2014/2/18

M inRGT
2
3
4
5
6
7
8
9
10

表 3 従来手法の抽出クラスタ数「大雨」のクラスタ数 「大雪」のクラスタ数
1325
1762
928
1150
670
809
534
633
420
497
342
437
304
375
246
320
224
280

M axM inRGT
2
3
4
5
6
7
8
9
10

表 4 提案手法の抽出クラスタ数「大雨」のクラスタ数 「大雪」のクラスタ数
2163
2879
2125
2813
1880
2424
1714
2291
1598
2039
1485
1897
1372
1750
1306
1720
1202
1652

確認は人手によって行った．
図 5 と図 6 にトピック「大雨」とトピック「大雪」の再現率をそれぞれ示す．図 5 と図 6 は，各 M inRGT ，各 M axM inRGTにおける実験結果を，横軸を抽出クラスタ数，縦軸を再現率とした散布図で示している．図 5 より，提案手法を用いた場合のトピック「大雨」の再現率は M axM inRGT を 2 から 10 まで

divlat = 1, 000，divtime = 24 を用いた．また，統計データと変化させても約 80%から大きな変化がないのが分かる．一方，

して 2013 年 12 月 13 日から 23 日の間に投稿された 3,301,605

従来手法を用いた場合，トピック「大雨」の再現率は約 70%か件のジオタグ付きツイートを用いて，時空間投稿密度を算出

ら約 30%まで落ちている．また，従来手法で抽出クラスタ数

した．

5. 2 再現率の比較
まず，投稿数の少ない地域や時間帯で時空間クラスタを抽出

1325，提案手法で抽出クラスタ数 1306 の場合を比べると，提案手法が抽出クラスタ数が少ないにもかかわらず，再現率は高くなっている．図 6 より，トピック「大雪」についても，トすることができたかについて，新聞報道に基づき評価を行う．
ピック「大雨」ほどの差はないが，提案手法が従来手法よりも実験期間に日本で大雨が観測された 16 日間，大雪が観測され高再現率であることが分かる．以上の結果より，従来手法でた 11 日間に注目し，「大雨」と「大雪」に関するトピックが報道

M inRGT を増加させると高密度な地域のみが抽出されるが，されている新聞記事（注 1） から，記事に記載されている地域（市提案手法では適応的に閾値が地域，また，時間帯によって変化町村）を抽出した．新聞記事から抽出した各地域から，本実験するため，再現率の低下を防ぐことができたといえる．
で用いたデータセット中でジオタグ付きツイートが 1 件も投稿

しかしながら，検出できていない地域も存在する．検出できされていない地域は取り除いた．その結果，6 月と 7 月に大雨なかった理由としては，対象の地域に複数のジオタグ付きツと報道されていた地域は 77，1 月と 2 月に大雪と報道されていイートが投稿されていたとしてもジオタグ付きツイート間の距た地域は 89 となった．なお，同じ地域であっても別々の日に離や投稿間隔が，パラメータ ǫ = 5km と τ = 3600sec より離報道があれば別々にカウントしている．
れていることがあり，時空間クラスタを抽出できなかった．今
表 1 と表 2 に実験期間の 16 日間と 11 日間に収集したジオタグ

後，パラメータ ǫ と τ を適応的に変化させる方法を導入する必付きツイート数とツイート分類によって抽出された関連ジオタグ
要がある．
付きツイート数を示す．また，各 M inRGT と M axM inRGT

5. 3 抽出された時空間クラスタの評価において抽出された時空間クラスタ数を表 3 と表 4 に示す．表

抽出された時空間クラスタを地図上で確認し，抽出地域とツ3 と表 4 には，各 M inRGT と M axM inRGT において，各日

イート内容の評価を行う．なお，この実験では M inRGT = 5，付で抽出された時空間クラスタ数を合計した値を示している．

M axM inRGT = 5 として行う．

「大雨」，「大雪」と報道された地域を検出できたかどうか

図 7(a) と図 7(b) に，7 月 3 日午前 7 時に北九州にて抽出さの判定は，対象の地域において時空間クラスタが抽出され，ツれた時空間クラスタを地図上に示す．地図上の時空間クラスタ
イートの内容が当該トピックの内容と一致していれば検出できは，中心点のみを傘マークまた雪マークのアイコンで示していたと判定した．抽出された時空間クラスタとツイートの内容のる．赤丸で示した時空間クラスタは提案手法でのみ抽出され，（注 1）：2014 年 1 月，2 月，6 月と 7 月に発刊された朝日新聞の朝刊と夕刊

7 月 3 日の夕刊と 7 月 4 日の朝刊において，7 月 3 日の午前中

ᚑ᮶ᡭἲ

ᥦ᱌ᡭἲ

100

෌⌧⋡(%)

90
80
70
60
50

40
30
0

500

図5

1000 1500
䜽䝷䝇䝍ᩘ

2000

2500
(a) 従来手法を用いた結果

図 8 2 月 8 日に関東地方で抽出された時空間クラスタ

トピック「大雨」の再現率

ᚑ᮶ᡭἲ

ᥦ᱌ᡭἲ

(b) 提案手法を用いた結果ングを提案した．(ǫ, τ )-密度に基づく適応的な時空間クラスタ

100

リングでは各地域，また各時間の統計的な投稿密度を用いるこ෌⌧⋡(%)

90
80とで，時空間クラスタを抽出するときに基準となる閾値を適応

70

的に変化させている．提案手法を用いることで，投稿数が多い

60

地域と少ない地域や時間帯を区別することなく時空間クラスタ

50を抽出することができる．提案手法を実際に実装し， Twitter40

上に投稿されたジオタグ付きツイートを用いて，トピックを

30
0

500

1000 1500 2000 2500 3000
䜽䝷䝇䝍ᩘ

「大雨」と「大雪」と設定し，評価実験を行った．評価実験の結果，提案手法は従来手法と比較して，より高性能にトピックの発生を捉えることができた．

図6

トピック「大雪」の再現率

これからの課題として，普段の投稿数が多い地域または時間帯において，抽出されるべきではない時空間クラスタを削除することができたかについて評価することがあげられる．評価実験において，再現率を求めることにより普段の投稿数が少ない
地域または時間帯において，トピックが取り上げられている地域を時空間クラスタとして検出できることを評価したが，精度については評価を行えていないため，今後，行う必要がある．

謝

辞本研究の一部は，JSPS 科研究費 26330139 と広島市立大学・(a) 従来手法を用いた結果(b) 提案手法を用いた結果

特定研究費の支援により行われた．
図 7 7 月 3 日に九州地方で抽出された時空間クラスタに大雨であったと報道されていた地域（福岡県朝倉市と大分県中津市）である．表 5 に，この二つの時空間クラスタに含まれていた全てのジオタグ付きツイートを示す．表 5 より，「大雨」
である状況を伝えているジオタグ付きツイートを抽出できているのが分かる．
図 8(a) と図 8(b) に，2 月 8 日午前 4 時に関東地方にて抽出された時空間クラスタを地図上に示す．2 月 8 日と 9 日の朝刊
では，2 月 8 日の未明から関東地方で大雪が観測されたと報道されている．図 8(a) と図 8(b) より，深夜の投稿が少ない時間帯において提案手法は従来手法と比較して多くの時空間クラス
タが抽出できており，トピック「大雪」の発生を捉えることができた．

6. ま と め
本論文では，(ǫ, τ )-密度に基づく適応的な時空間クラスタリ

文

献[1] Jie Yin, A. Lampert, M. Cameron, B. Robinson, and
R. Power. Using social media to enhance emergency situation awareness. Intelligent Systems, IEEE, Vol. 27, No. 6,
pp. 52–59, Nov 2012.
[2] Krishna Y. Kamath, James Caverlee, Kyumin Lee, andZhiyuan Cheng. Spatio-temporal dynamics of online memes:
A study of geo-tagged tweets. In Proc. 22nd International
Conference on World Wide Web, WWW ’13, pp. 667–678,
2013.
[3] Sarah Vieweg, Amanda L. Hughes, Kate Starbird, andLeysia Palen. Microblogging during two natural hazards
events: What twitter may contribute to situational awareness. In Proc. SIGCHI Conference on Human Factors in
Computing Systems, CHI ’10, pp. 1079–1088, 2010.
[4] Mai Miyabe, Asako Miura, and Eiji Aramaki. Use trend
analysis of twitter after the great east japan earthquake. In
Proc. ACM 2012 Conference on Computer Supported Cooperative Work Companion, CSCW ’12, pp. 175–178, 2012.
[5] Tatsuhiro Sakai and Keiichi Tamura. Real-time analysis application for identifying bursty local areas related to emergency topics. SpringerPlus, Vol. 4, No. 162, 2015.
[6] Mor Naaman. Geographic information from georeferenced表 5 7 月 3 日の 7 時 47 分に朝倉市と中津市で抽出されたジオタグ付きツイートID

ツイート本文1-1 雨やばー学校行くの怖ー
1-2 雨やばし (笑) 昼から結婚式の打ち合わせ (((o(*▽*)o))) 昼からやむって言いよるけど本当にやむとかな (￣Д￣)
1-3 雨ヤバイから学校休みにして〜 お願い〜
2-1 さて雨の中仕事いやだー たまにはゆとりてー
2-2 さて、仕事や！(;o;) しかも雨やー……朝からテンション下がるわー m(。≧Д≦。)m おなかすいた (笑) 今日頑張れば明日休みだ！
頑張ろーっと (´・ω・‘)
2-3 もう、雨で止まるくらいやったら豊肥本線爆発せんかな笑
2-4 おはょん笑 大分は雨だよー

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

social media data. SIGSPATIAL Special, Vol. 3, No. 2, pp.
54–61, 2011.
Takeshi Sakaki, Makoto Okazaki, and Yutaka Matsuo.
Earthquake shakes twitter users: Real-time event detection
by social sensors. In Proc. 19th International Conferenceon World Wide Web, WWW ’10, pp. 851–860, 2010.
Ozer Ozdikis, Halit Oguztuzun, and Pinar Karagoz. Evidential location estimation for events detected in twitter. In
Proc. 7th Workshop on Geographic Information Retrieval,
GIR ’13, pp. 9–16, 2013.
Karl Kreiner, Aapo Immonen, and Hanna Suominen. Crisis
management knowledge from social media. In Proc. 18th
Australasian Document Computing Symposium, ADCS ’13,
pp. 105–108, 2013.
Marcelo Mendoza, Barbara Poblete, and Carlos Castillo.
Twitter under crisis: Can we trust what we rt? In Proc.
First Workshop on Social Media Analytics, SOMA ’10, pp.
71–79, 2010.
Cindy Hui, Yulia Tyshchuk, William A. Wallace, Malik
Magdon-Ismail, and Mark Goldberg. Information cascades
in social media in response to a crisis: A preliminary modeland a case study. In Proc. 21st International Conference
Companion on WWW, pp. 653–656, 2012.
Akiko Murakami and Tetsuya Nasukawa. Tweeting about
the tsunami?: Mining twitter for information on the tohoku earthquake and tsunami. In Proc. 21st International
Conference Companion on World Wide Web, WWW ’12
Companion, pp. 709–710, 2012.
Sarvnaz Karimi, Jie Yin, and Cecile Paris. Classifying microblogs for disasters. In Proc. 18th Australasian Document
Computing Symposium, ADCS ’13, pp. 26–33, 2013.
D. Thom, H. Bosch, S. Koch, M. Worner, and T. Ertl. Spatiotemporal anomaly detection through visual analysis ofgeolocated twitter messages. In Proc. 2012 IEEE Pacific
Visualization Symposium, pp. 41–48, 2012.
Eiji Aramaki, Sachiko Maskawa, and Mizuki Morita. Twitter catches the flu: Detecting influenza epidemics using twitter. In Proc. Conference on Empirical Methods in Natural
Language Processing, EMNLP ’11, pp. 1568–1576, 2011.
Marco Avvenuti, Stefano Cresci, Andrea Marchetti, Carlo
Meletti, and Maurizio Tesconi. Ears (earthquake alert
and report system): A real time decision support systemfor earthquake crisis management. In Proc. 20th ACM
SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’14, pp. 1749–1758, 2014.
Kyoung-Sook Kim, Ryong Lee, and Koji Zettsu. mtrend:
discovery of topic movements on geo-microblogging messages. In Proc. 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems,
GIS ’11, pp. 529–532, 2011.
Avinash Kumar, Miao Jiang, and Yi Fang. Where not togo?: Detecting road hazards using twitter. In Proc. 37th
International ACM SIGIR Conference on Research & Development in Information Retrieval, pp. 1223–1226, 2014.

[19] Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel,and Jörg Sander. Optics: Ordering points to identify theclustering structure. In Proc. 1999 ACM SIGMOD International Conference on Management of Data, SIGMOD ’99,
pp. 49–60, 1999.
[20] Christopher D. Manning, Prabhakar Raghavan, and Hinrich
Schütze. Introduction to Information Retrieval. Cambridge
University Press, 2008.
[21] Jörg Sander, Martin Ester, Hans-Peter Kriegel, and Xiaowei
Xu. Density-based clustering in spatial databases: The algorithm gdbscan and its applications. Data Mining andKnowledge Discovery, Vol. 2, No. 2, pp. 169–194, 1998.
[22] Martin Ester, Hans-Peter Kriegel, Joerg Sander, and Xiaowei Xu. A density-based algorithm for discovering clusters
in large spatial databases with noise. In Proc. Second International Conference on Knowledge Discovery and Data
Mining, pp. 226–231, 1996.
[23] Keiichi Tamura and Takumi Ichimura. Density-based spatiotemporal clustering algorithm for extracting bursty areasfrom georeferenced documents. In Proc. 2013 IEEE International Conference on Systems, Man, and Cybernetics,
SMC 2013, pp. 2079–2084, 2013.