DEIM Forum 2017 D8-5

バンディットアルゴリズムを用いた
特定地域から発信されたツイートの収集
上田 紗希†

山口 祐人††

北川 博之†††† 筑波大学システム情報工学研究科 〒 305–8573 茨城県つくば市天王台 1-1-1†† 国立研究開発法人産業技術総合研究所 〒 135-0064 東京都江東区青海 2-3-26††† 筑波大学システム情報系情報工学域 〒 305–8573 茨城県つくば市天王台 1-1-1
E-mail: †braose@kde.cs.tukuba.ac.jp, ††yamaguchi.yuto@aist.go.jp, †††kitagawa@cs.tsukuba.ac.jp
あらまし

本研究では Twitter から特定地域より発信されたツイートを収集する手法を提案する．ツイートの中にはユーザの現在の状況や周囲での出来事などユーザの現在位置と結びついている情報が多く含まれる．しかし Twitter はツイート収集のための API に利用制限があり，また発信地を示すジオタグが付与されたツイートの割合も非常に少ない．そこで本研究では，収集対象地域からツイートを発信する可能性の高いユーザを発見・フォローすることで対象地域のツイートを収集する手法を提案する．限られた時間の中で目的とするツイートを収集するために，ユーザの探索と発見したユーザからのツイートの収集のトレードオフを考慮する必要がある．そのため提案手法では, バンディッ
トアルゴリズムによりフォローするユーザを決定する．また，ユーザの位置情報に関する報酬は直接得ることが出来ないため，ツイート内容から推定する．また実データを用いた評価実験により，提案手法の有効性を示す．
キーワード

1. 序

Twitter，Focused Crawling，バンディットアルゴリズム

論

ツイートをリアルタイムに収集できる Streaming APIs（注 2） の中の statuses/sample は，投稿された全ツイートのうちランダムに

1. 1 研究の背景と目的選ばれた 1%を取得できる．しかし statuses/sample によってラ

今日では，ソーシャルメディアを通じて多くの人々が多様なンダムに収集されたツイートから収集者が目的とするツイート

情報発信を行うようになった．Twitter（注 1） は主要なサービスのを探すことは非効率的である．statuses/filter は，パラメタによ一つであり，ユーザはツイートと呼ばれる 140 文字以内の短文り設定した条件に合致したツイートを収集することができる．

を投稿することができる．Twitter には携帯端末からも手軽に

follow パラメタでは，一度に最大で 5000 ユーザまでのユーザ

アクセスすることができるため，投稿されたツイートの中にはID を指定することで，それらのユーザのツイートを取得するこユーザの現在の状況や周囲での出来事など，ユーザの現在位置とができる．また locations パラメタでは，経度と緯度の組み合と深く結びついた情報が含まれていることも多い．そのため，わせによる任意の範囲を指定することで、その範囲内のジオタ

特定の地域から発信されたツイートを収集することができれば，グが付与されたツイートを収集することができる．しかし先行その地域に対するマーケティング，イベント検出 [12] や災害分

研究 [5] によると，Twitter に投稿されたツイートのうち，ジオ析 [14] などに応用することが可能であると考えられる．

タグが付与されたツイートは全体のわずか 0.42%であり，多くツイートを収集する際に，大きく分けて 2 つの問題点があのユーザはプライバシ等の問題から自身の位置情報を明らかにる．1 つ目は収集者の計算機的，および時間的資源が限られてしていない．従って先に述べたような理由から Twitter の既存いることである．Twitter には常に大量のツイートが世界中かの枠組み内では，限られた時間の中で特定地域のツイートを多ら投稿されており，それらのツイートを取捨選択することなくく収集することは困難であると考えられる．

収集・保存し続けることは収集者にとって計算機資源上の大き本研究では収集対象地域から発信されたツイートを継続的にな負担である．また一般的に収集にかける時間は有限であるた

収集するために，その地域からツイートを投稿する可能性のめ，限られた時間の中で目的のツイートをできるだけ多く収集高いユーザを発見・フォローする．ユーザをフォローすることすることが求められる．2 つ目は Twitter はツイートを収集すによって特定地域からのツイート収集を行う場合，まず膨大なるための API を公開しているが，その枠組みの中で特定地域

Twitter ユーザの中から収集対象地域からツイートを投稿する可から発信されたツイートを収集することは難しいことである．

能性の高いユーザを探索することが必要である．またユーザのTwitter の API を用いる場合，時間あたりの利用回数や取得ツ探索と同時に，発見したユーザをフォローしそのツイートを収

イート数等には制限が設けられている．例えば投稿されている集することも求められる．一度にフォローできるユーザ数や収集期間は限られているため，収集者はこの二つの行動のトレー（注 1）：https://twitter.com/（注 2）：https://dev.twitter.com/streaming/publicドオフを考慮しながらツイートの収集を進めなければならない．

集したツイートそのものから直接報酬を得ることはできない．

そこで本研究では，バンディットアルゴリズム [13] を用いて特そのため本研究では収集したツイートのテキストを用いて発信

定地域からのツイートを収集する手法を提案する．バンディッ

地推定を行うことで報酬を推定し，推定された報酬に従ってバ

トアルゴリズムはデータの分布が未知である環境下で，得られンディットアルゴリズムを用いてフォローユーザの選択を行う．

る累積報酬が最大になるように行動の選択を繰り返し行うアルLi ら [10] はトピックに関するツイートを収集するために効

ゴリズムである．バンディットアルゴリズムでは多くの報酬を果的なキーワードを自動的に検出する手法を提案した．Li らの得ることのできる選択肢を探す「探索」と，多くの報酬が得ら

手法ではツイートを収集するための検索キーワード集合を決定れると判明した選択肢を選んで実際に報酬を獲得する「活用」

し，収集したツイートに含まれる語句をもとに一定時間ごとにの二つのトレードオフを考慮しながら累積報酬の最大化を目指

検索キーワードを更新する．本研究はキーワードによる検索です．本研究では収集対象地域とフォロー対象の候補となるユーはなくユーザのフォローによってツイートを収集する点においザ集合を入力し，その地域から発信されたツイートを出力として Li らの手法とは異なっている．

て受け取るという状況を想定する．提案手法ではバンディット

2. 2 ユーザおよびツイートの位置推定手法

アルゴリズムにおける選択をユーザのフォロー，報酬をユーザ

Twitter における位置推定手法は，1) ユーザの居住地推定手から得られる対象地域から発信されたツイート数と位置付ける

法，2) ツイートの発信地推定手法の 2 種類に分けることがでことで，ツイート収集問題にバンディットアルゴリズムを適用

きる．

する．本研究における累積報酬の最大化は，対象地域から発信

2. 2. 1 居住地推定手法されたツイートの最終的な収集数を最大化することに該当する．

ユーザの居住地推定に関わる手法は多く提案されている．居一般にバンディットアルゴリズムにおける報酬は，行動を選住地推定に関する既存手法として，投稿されたツイートの内容

択することによって明確に与えられる．しかし本研究の場合，を用いるコンテンツベース手法と，ユーザのソーシャルグラフ

ジオタグが付与されたツイートの割合は非常に小さく，ツイーを用いるグラフベース手法がある．

トから直接位置情報に関する情報を得て報酬を計算することはコンテンツベース手法の一つとして，Cheng ら [5] はローカ

できない．そこで収集したツイートのテキストを用いて発信地

ルワードを用いてユーザの居住地推定を行う手法を提案した．

推定を行うことでユーザが対象地域からツイートを投稿した確

ローカルワードとはその単語を投稿したユーザの居住地に偏率を計算し，それを報酬とする．

りがあるような単語のことである．また，Yamaguchi ら [16] は本研究の貢献は以下に示す 2 点である．

ソーシャルストリームから検出された地理的局所性を持つイベ(1) テキストから推定した報酬を用いるバンディットアルゴ

ントを用いてユーザの居住地推定を行う手法を提案した．

リズムにより，特定地域から発信されたツイートを継続的に収集する手法を提案する．

(2) 実際の Twitter データを用いた評価実験により，提案手法によるツイート収集の有効性を示す．
提案手法の有効性を示すため本研究で行う評価実験は以下の2 つである．
•

報酬の推定方法の評価：提案手法における報酬の推定方法が適切なものであるかを検証する．複数の報酬推定方法を比グラフベース手法として，Backstrom ら [3] や Clodoveu [6] は，ソーシャルメディアユーザの友人関係に着目して居住地を推定する手法を提案した．これらの手法ではソーシャルメディア上
で友人関係にあるユーザ同士は現実の居住地も近い可能性が高いとし，ユーザの居住地を推定している．
しかし，これらの手法の目的はユーザの居住地を推定することであり，特定地域から発信されたツイートを収集するという本研究の目的とは異なっている．

較し，提案手法で用いる推定方法が対象地域から発信されたツ2. 2. 2 発信地推定手法

イートを最も多く収集できることを示す．

ユーザの発信地推定に関わる手法はこれまでにもいくつか提•提案手法と他手法の比較：提案手法とベースライン手法

案されている．Kinsella ら [9] はジオタグ付きツイートから各地の比較を行い，提案手法が対象地域から発信されたツイートを域の言語モデルを構築し，この言語モデルからツイートの発信

最も多く収集できることを示す．

地を推定する手法を提案した．Priedhorsky ら [11] は混合ガウ

2. 関 連 研 究
2. 1 特定トピックに関するツイート収集手法

ス分布を用いる手法を提案した．Ikawa ら [8] は，ユーザの過去の投稿内容からツイートの位置情報とキーワードの関連付けを行う手法を提案した．

ある特定のトピックに関するツイートを Twitter から収集す

しかし，これらの手法の目的は個々のツイートの発信地を明る研究として，Gisselbrecht らは WhichStreams? [7] を提案した．

らかにすることである．本研究では一つの地域に焦点を当てそ

この手法はバンディットアルゴリズムを用い，あるトピックとの地域から発信されたツイートを収集するため，対象の地域以関係が深いユーザの投稿を収集する手法である．Gisselbrecht

外から発信されたツイートは必要としていない．そのため，こらの手法では本研究と同様にバンディットアルゴリズムを用い

れらの既存手法では対象地域外に推定された大半のツイートのており，収集したツイートから得られる報酬に従ってフォロー

収集データや収集に要した時間が無駄になるという問題点があ

ユーザの再選択を行う．しかし本研究では多くの場合ツイート

る．本研究ではバンディットアルゴリズムを用いて対象地域かの発信地が未知であるため，Gisselbrecht らの手法と違い，収らツイートを投稿する可能性の高いユーザを探索・フォローし，

効率的にデータを収集する．

表1

3. バンディットアルゴリズム
バンディット問題 [2] はデータの分布が未知である環境下での選択の最適化を考える問題である．バンディット問題では毎

記号と定義

記号

定義

u

ユーザ

t

タイムウィンドウl

ツイートの発信地l̂

収集対象地域回の試行で有限の集合内から選択を行い，その選択に対して報

p

ツイート

酬を受け取る状況を考える．このとき試行回数には制限があり，

U

ユーザ集合

各選択に対する報酬の分布は事前に分かっていないものとする．

Ut

タイムウィンドウ t におけるフォローユーザ集合

バンディット問題の最終的な目的は，このような制約下で最終P

ツイート集合的に得られる累積報酬を最大化することである．

PL

発信地が公開されているツイート集合

PU

発信地が公開されていないツイート集合

L

発信地集合

累積報酬を最大化するために，選択者は「探索」と「活用」という二種類の行動を使い分ける．得られる報酬の分布は未知であるため，選択者は複数回の試行を行って報酬の分布を調べる必要がある．この行動が探索である．一方で，報酬の少ない選択を繰り返し行うことは損であり，より良い選択肢を探索す
ると同時に現時点で多くの報酬を得られる選択肢を何度も選ぶことも求められる．この行動を活用と呼ぶ．選択者はこの「探索」と「活用」の二つの行動のトレードオフを考慮しながら，累積報酬を最大化することを目指す．
バンディット問題に関するアルゴリズムは，UCB アルゴリズ
ム [2] や ϵ-greedy アルゴリズム [15]，softmax アルゴリズム [4]，Thompson sampling アルゴリズム [1] など数多く提案されている．UCB アルゴリズムは各選択肢の現時点までの試行回数を

図 1 提案手法全体図．提案手法の処理の流れを示す．提案手法ではユーザ集合と収集対象地域が与えられたとき，バンディットアル

考慮しながら探索と活用のバランスをとるアルゴリズムであゴリズムを用いて対象地域から発信されたツイートの収集を行う．

る．ϵ-greedy アルゴリズムはある一定の確率 ϵ でランダムな選択を行い，確率 1 − ϵ で現時点で最も報酬の期待値が高い選択を行うアルゴリズムである．softmax アルゴリズムは ϵ-greedy
アルゴリズムの探索において，選択によって得られる報酬が明らかになっている場合でも，報酬の大小に関わらず全ての選択を等しい確率で行ってしまうという欠点を解決する手法である．

softmax アルゴリズムでは，探索の際に報酬の比によって確率的に選択を行うことで，より大きな報酬が得られる選択を高い確率で試行できる．Thompson sampling アルゴリズムは全ての選択肢の報酬に対して予め事前分布を仮定しておき，その後は得られた報酬によって更新された事後確率に従って選択を行う

このとき，対象地域から発信されたツイート収集問題を次のように定義する．ユーザ集合 U ，収集対象地域 ˆl，収集期間 Tが与えられたとき，以下の二つの制約下で最終的なツイート収
集数 | {pi ∈ P | li = ˆl} | が最大となることが期待される各タ
イムウィンドウ t においてフォローするユーザ集合 U t の系列{U 1 , U 2 , ..., U T } を出力する．
•

毎タイムウィンドウでユーザ集合 U から K ユーザを選出してフォローする．

•

収集期間 T の間，ユーザからツイートを収集する．

アルゴリズムである．

5. 提 案 手 法

4. 問 題 定 義

5. 1 手 法 概 要
本研究は，対象地域から発信されたツイートを収集すること

本章では，本研究で用いる用語および本研究で扱う問題を定義する．本研究では連続した時間を一定時間ごとに区切り、一つ一つの時間帯をタイムウィンドウと呼ぶ．各タイムウィンド
ウにおいてユーザをフォローし，ツイートを収集する．それぞれの投稿におけるユーザ u，タイムウィンドウ t，発信地 l を合わせてツイート p = (u, t, l) と定義する．ユーザ，ツイート，
発信地の集合をそれぞれ U ，P ，L で表す．ツイートは発信地

l が Twitter 上で公開されているツイート p ∈ P L と，公開されていないツイート p ∈ P U とに分けられ，P = P L ∪ P U となる．またタイムウィンドウ t においてフォローするユーザをフォローユーザ集合 U t で表す．収集対象地域を ˆl で表す．これらの記号の定義を表 1 にまとめる．

を目的とする．提案手法では対象地域からツイートを発信する
可能性の高いユーザをフォローすることによってそのユーザのツイートを収集する．そこでツイート収集問題にバンディット
アルゴリズムを適用し，ユーザのフォローを選択，ユーザから得られる対象地域から発信されたツイート数を報酬ととらえることで，一定時間ごとにフォローユーザの選択を繰り返し行
う．これは，過去に頻繁に対象地域からツイートを投稿しているユーザは今後も対象地域を訪れてツイートを投稿する可能性が高いという仮定に基づいている．また，発信地を示すジオタ
グが付与されているツイートはごく少数であり，ツイートの位置情報を得て報酬を計算することは多くの場合不可能であるという問題点がある．そのため，ツイートのテキストを用いて発信地推定を行うことでユーザが対象地域からツイートを投稿し学習データには事前に収集したジオタグ付きツイートを用い，クラスは発信地が対象地域 ˆl であるか否かの二通りとした．ナ

た確率を計算し，そのユーザから得られる報酬を推定する．

イーブベイズ分類器にはラプラススムージング用いた．本研

提案手法の流れを図 1 に示す．提案手法ではフォロー候補

究では特徴ベクトル X をタイムウィンドウ t 間に収集したツユーザ集合と収集対象地域が入力として与えられる．提案手法

イート毎に作成する．まず，位置情報が既知であるツイートをの処理は大きく以下の三つのステップに分けられる．この三つ用い，特徴語として名詞を抽出する．そして抽出された特徴のステップをタイムウィンドウごとに繰り返す．

語から bag-of-words に従ってツイートを特徴ベクトルで表す．

（ 1 ） ユーザの選択：タイムウィンドウ t におけるフォロー

bag-of-words は，ベクトルの各次元を一つの単語に対応付け，

ユーザ集合をバンディットアルゴリズムを用いて決定する．

各文書内のその単語の頻度を値とするベクトル表現方法である．

（ 2 ） ツイートの収集：フォローユーザ集合に含まれるユー

特徴語集合を W = {w1 , w2 , ..., wn } とし，ツイート p 内でのザのツイートをタイムウィンドウ t の期間内，収集する．

単語 wi の出現回数を n(wi , p) で表すとき，ツイート p の特徴（ 3 ） 報酬の推定：収集したツイートを元に，各ユーザからベクトル X は以下の式で表される．

得られた報酬を推定する．

X(p) = (n(w1 , p), n(w2 , p), ..., n(wn , p))

5. 2 ユーザの選択(3)

ユーザの選択では，タイムウィンドウ t においてフォローすしかし実際のデータにおいては，対象地域外から投稿されたるユーザ集合を決定する．バンディットアルゴリズムは複数存

ツイートの数は対象地域から投稿されたツイートの数を大きく在するが，本研究ではその中の一つである ϵ-Greedy アルゴリズ

上回るという問題がある．このようなクラスの分布の偏りによム [15] を用いる．ϵ-Greedy アルゴリズムは通常は最も報酬の高る影響を解消するため，class mass normalization（CMN）[17] をい選択肢を選択する活用を行いながら，同時に確率 ϵ で全選択用いる．CMN は学習データのクラスの分布と現実のデータの肢の中からランダムに選択肢を選ぶ探索を行うアルゴリズムでクラスの分布とが大きく異なるような場合に分類結果の補正をある．探索を行うことで，エージェントは現時点で最も報酬の行う．label 1 と label 0 の二つのクラスが存在し，サンプル i が高い選択よりもより良い選択の可能性を探ることができる．

label 1 に分類される確率を f (i) とするとき，通常の分類では提案手法の場合では，確率 ϵ で報酬とは無関係にランダムなユーザ選択を行い，確率 1 − ϵ で最も報酬の期待値が高いユー
ザを選択する．タイムウィンドウ t 時点でのユーザ u の報酬の期待値 Qu,t は以下の式で与えられる．
 0(Fu,t−1 = 0)
Qu,t =∑t−11

gu,i (otherwise)
Fu,t−1

サンプル i は一般に以下の式に従ってクラス li に分類される．
{
label 1 (f (i) > 12 )li =(4)label 0 (otherwise)
一方、CMN を用いる場合，サンプル i は以下のように分類さ

(1)

れる．

{

i=1

ただし，gu,t はタイムウィンドウ t におけるユーザ u の報酬，

Fu,t−1 はタイムウィンドウ t − 1 までにユーザ u がフォローされた回数とする．あるタイムウィンドウにおいて一度にフォローできるユーザ数を K とするとき，この選択を K 回繰り返し行うことで，フォローするユーザ集合を決定する．なお，1 度
目の選択については全ユーザの累積報酬が 0 であるため，フォローユーザ K 人をランダムに選択する．

5. 3 ツイートの収集
選択したフォローユーザ集合のツイートをタイムウィンドウt の期間内，収集する．ツイートの収集には Streaming APIs のli =label 1(i)(q ∑f (i)> (1 − q) ∑ 1−f)
f (i)(1−f (i))

label 0(otherwise)i(5)

このとき，q は理想的な label 1 の割合である（実験ではデータから算出する）．
タイムウィンドウ t において，ナイーブベイズ分類器から推定されるユーザ u のツイート pi の発信地が対象地域 ˆl である確ˆ率を P (l|pi )，タイムウィンドウ t 内でユーザ u から発信されたツイート集合を Put とする．このときタイムウィンドウ t でのユーザ u の報酬 gu,t は，Put に含まれる全ツイートの P (ˆl|pi )の CMN による補正値の和として以下の式で与えられる．

中の statuses/filter より follow パラメタを用いる．

gu,t =∑cppip
cpi + cnpit(6)pi ∈Pu5. 4 報酬の推定
タイムウィンドウ t の終了後，フォローユーザから得られた報酬の推定を行う．まず，タイムウィンドウ t 間に収集したツイートから，各ツイートの発信地が対象地域である確率を計算∑f (i) ，(1 −た だ し こ の と き ，cppi ，cn
pi は 式 5 に お け る q
f (i)
i

(i)
q) ∑ 1−f) に該当するため，(1−f (i))
iする．確率を計算するために，提案手法ではナイーブベイズ分P (l̂|pi )p cpi = q ∑ ∑t P (l̂|pj )u

類器（Naive Bayesian Classifier）を用いる．入力として特徴ベ
る確率は以下の式で計算される。．

P (L)P (X|L)∝ P (L)P (X|L)
P (X)pj ∈Pu1−P (l̂|pi ) cn
pi = (1 − q) ∑ ∑t (1−P (l̂|p ))u

クトル X （後述）が与えられたとき，クラスラベルが L であ

P (L|X) =i

pj ∈Pu

(7)

j

となる．

(2)

推定された報酬を用いて，タイムウィンドウ t + 1 で再びフォローするユーザ集合を選択する．

t(A) u ∈ UA
：タイムウィンドウ t 内でジオタグ付きツイート

6. 評 価 実 験p ∈ P L を 1 件以上投稿した．
t(B) u ∈ UB
：タイムウィンドウ t 内でツイートを 1 件以上

6. 1 実 験 設 定
提案手法の有効性を検証するため，実際のツイートを用いて投稿したが，その全てがジオタグの付与されていないツイート

特定地域から発信されたツイートの収集を行った．実験は全て

p ∈ P U である．

64bit Windows8.1， Intel Core i7-4820K@3.70GHz CPU， 32GB(C) u ∈ UCt ：タイムウィンドウ t 内でジオタグの有無に関わRAM で構成された PC 上で行った．提案手法のプログラムはらずツイートを 1 件も投稿していない．

Python で記述し，ライブラリは scikit-learn，Numpy を用いた．

上記のように分類したユーザ u について，タイムウィンドウ t

まず，Streaming APIs の statuses/filter を用い，2016 年 5 月 30

での対象地域から発信されたツイート収集数 nu,t を以下のよ

日から 2016 年 6 月 7 日の間に日本国内のジオタグ付きツイー
トを収集した．次に収集したジオタグ付きツイートをユーザごうに計算し，その合計を評価に用いた．

•(A) のユーザ：ユーザ自身が投稿したジオタグ付きツイーとに集計した後，収集数の多い上位 2 万ユーザを選出し，実験

トの情報からユーザが対象地域から発信したツイート数を推算に用いるため，これらのユーザのツイートを 2016 年 7 月 16 日

する．タイムウィンドウ t においてユーザが投稿したツイート

16 時から 2016 年 8 月 10 日 16 時までの期間収集した．収集し数とジオタグ付きツイート数から対象地域から発信されたツたツイートのうち，ユーザがリツイートしたツイートを除いた

イートの割合を計算する．

ものをテストデータセットに含めた．テストデータセット内にnu,t =

含まれる最終的なツイート総数は 7,992,311 件であった．
今回，人口の異なる複数の地域で検証を行うため，東京 23区，京都市，横浜市，つくば市の 4 地域を対象地域として設定した．ナイーブベイズ分類器の学習データとして用いるため，各対象地域について対象地域内とそれ以外の日本国内地域から，
テストデータセットには含まれないジオタグ付きツイートをそれぞれ 1 万件ずつ収集した．特徴語を抽出する際の形態素解析には MeCab（注 3） を用い，辞書は IPA 辞書 （注 4） を使用した．提案手法のパラメタについては事前の予備実験より，K = 1000，•| {pi ∈ (P L ∩ Put ) | l = ˆl} || Put |
| P L ∩ Put |(8)(B) のユーザ：ユーザが投稿したジオタグ付きツイートがないため，(A) のユーザのツイートの情報を用いてユーザが対象地域から発信したツイート数を推算する．タイムウィンド
ウ t における (A) の全ユーザの nu,t の合計と総ツイート数から対象地域から発信されたツイートの割合を計算する．
∑
u∈U t nu,t
nu,t = ∑ A t | Put |u∈U t Pu

(9)A

ϵ = 0.5，タイムウィンドウの長さは 4 時間とした．また，CMNのパラメタ q を設定するため，テストデータセットには含まれない日本国内のジオタグ付きツイートを別途 10 万件収集した．

•(C) のユーザ：タイムウィンドウ T 内でツイートを 1 件も投稿していないため，収集数は 0 である．

実際に実験に用いたパラメタ q の値について，表 2 に示す．
表 2 パラメタ q の値
対象地域

東京都 23 区

q

京都市

(10)

6. 3 実験結果と考察

横浜市 つくば市

0.13 0.01927 0.02356

nu,t = 00.00251

提案手法の有効性を，以下の点から検証した．
（ 1 ） 報酬の推定方法の評価（ 2 ） 提案手法と他手法の比較

6. 2 評 価 方 法
本実験では対象地域から発信されたツイートの収集数によって評価を行った．実際に収集したツイートの大部分はジオタグが付与されておらず，ツイートそのものからそのツイートの発信地を判断することは難しい．そのため，本実験では以下の方法によってジオタグが付与されていないツイート p ∈ P U の発信地を推測し，対象地域から発信されたツイートの収集数を計算した．
タイムウィンドウ t におけるフォローユーザ集合 U t に含まれるユーザ x は，収集されたツイートに従って以下の三種類のtt
ユーザ集合 UA，UB
，UCt に分類される．

6. 3. 1 報酬の推定方法の評価
本実験では，提案手法で用いた報酬の推定方法が対象地域から発信されたツイートの収集に適しているのかを検証した．今回は，以下の 2 点を比較した．

•

特徴語の効果：提案手法では特徴語に名詞を用いた．特徴語に KL ダイバージェンスによって抽出された単語を用いた手法と提案手法とを比較する．

•

ナイーブベイズ分類器に用いる特徴ベクトルの作成方法の効果：提案手法ではツイートごとに特徴ベクトルを作成し，ナイーブベイズ分類器による確率計算を行った．同一ユーザのタイムウィンドウ内でのツイートを一つのテキストにまとめる
ことで特徴ベクトルを作成しナイーブベイズ分類器による確率計算を行う手法と提案手法とを比較する．

（注 3）：http://mecab.googlecode.com/svn/trunk/mecab/doc/index.

実験では上記 2 点の組み合わせによる報酬の推定方法を提案手

html法で用いた計算式以外に 3 つ用意し，計 4 つの推定方法の比較（注 4）：https://drive.google.com/uc?export=download&

id=0B4y35FiV1wh7MWVlSDBCSXZMTXMを行った．

である確率 P (ˆl|su,t ) をナイーブベイズ分類器によって計算し，CMN による補正を行う．
また，報酬の推定時にはユーザが投稿したツイート数を考慮する．タイムウィンドウ t におけるユーザ x の報酬 gu,t は以下の式で与えられる．

gu,t =(a) 東京都 23 区

cpsu,tlog(| Put | +1)pcsu,t + cn
su,t

ただしこのとき， cpsu,t = q ∑ P (l̂|su,t )P (l̂|s(b) 京都市u,t )
1−P (l̂|su,t )= (1 − q) ∑u,tu∈U t (1−P (l̂|su,t ))

 cn
s

u∈U t

(12)

(13)

とする．

6. 3. 2 比 較 手 法
提案手法と比較するために実際に用いた報酬の推定方法は以下の 3 つである．
(c) 横浜市

図2•(d) つくば市

報酬の推定方法の比較．x 軸はタイムウィンドウを表し，y 軸は各タイムウィンドウまでの対象地域から発信されたツイートの累
計収集数を表す．どの地域の場合でも特徴ベクトルをツイートごとに作成する手法が最も多くのツイートを収集できている．

計算方法 1 (KL / Per Tweet)：特徴語に KL ダイバージェ

ンスによって抽出された単語を用いる．特徴ベクトルの作成は提案手法と同じ手法を用い，ツイートごとに作成する．報酬の計算式は提案手法と同様に式 (6) を用いる．

•

計算方法 2 (Noun / Window)：特徴語に名詞を用いる．特徴ベクトルは同一ユーザのタイムウィンドウ内でのツイートをKL ダイバージェンスによる特徴語の抽出 特徴語の効果の比

一つの文章にまとめたテキスト s から作成する．報酬の計算式

較では，特徴語に KL ダイバージェンスによって抽出された単は式 (12) を用いる．

語を用いる手法を新たに作成した．KL ダイバージェンスは，2•計算方法 3 (KL / Window)：特徴語に KL ダイバージェン

つの確率分布の差異を計る尺度である．特徴語の抽出では，単スによって抽出された単語を用いる．特徴ベクトルは同一ユー

語 w の離散確率分布を Qw ，ラベルの離散確率分布を P とし

ザのタイムウィンドウ内でのツイートを一つの文章にまとめたて，各単語について KL ダイバージェンスを計算する．いずれ

テキスト s から作成する．報酬の計算式は式 (12) を用いる．

かのラベルの値をとる確率変数 l があるとき，Qw (l) は単語 w

6. 3. 3 実験設定・結果のラベル l での発生確率を表す．また，P (l) はラベル l の発生実験ではテストデータセットより，2016 年 7 月 16 日 16 時か確率である．このとき，Qw からみた P の KL ダイバージェンら 2016 年 7 月 31 日 16 時までの計 360 時間分のツイートデースは以下の式で計算される．

タを用いた．実験に用いたツイート数は計 4,874,303 件である．

DKL (Qw ∥ P ) =∑l

Qw (l)Qw (l)log
P (l)実験は 5 回行い，その平均値を結果として示す．実験結果を図(11)2 に示す．
実験結果から 4 地域全ての場合で，提案手法を含む特徴ベク

本実験ではまず位置情報が既知であるツイートから名詞を抽出

トルをツイートごとに作成する手法が最も多くのツイートをし，ラベルを対象地域から発信されたツイートと対象地域外か収集できていることが分かる．これは，特徴ベクトルをタイムら発信されたツイートの 2 つに分けることで各単語の KL ダ

ウィンドウ内でのツイートを一つの文章にまとめたテキストか

イバージェンスを計算した．計算された各単語の KL ダイバーら作成する手法では，途中でユーザの対象地域外への移動やそジェンスのうち，値が大きいものから上位 500 語を特徴語としの地域に関係のないツイートが含まれていた場合に，その影響て用いた．

を大きく受けてしまうからだと考えられる．ナイーブベイズ分

特徴ベクトルの作成 ナイーブベイズ分類器に用いる特徴ベク

類器では特徴語の出現確率の積によって，ツイートの確率値をトルの作成方法の効果の比較では，報酬推定の際，同一ユーザ

計算している．そのため，出現確率が低い単語が含まれていたのタイムウィンドウ内での全ツイートから一つの特徴ベクトル場合，その影響よって最終的に算出される確率値は小さくなっを作成し，ナイーブベイズ分類器による確率値の計算を行う手てしまうと考えられる．タイムウィンドウ内の複数のツイート

法を新たに作成する．特徴ベクトルの作成ではまず，同一ユーを一つにまとめて特徴ベクトルを作成する場合，そのツイート

ザがタイムウィンドウ内で投稿した全てのツイートのテキスト

全てにこのような影響が及んでしまう．Twitter ではユーザの移を繋げて一つの文章ととらえ，テキスト s とする．その後テ動やツイートが言及する話題が頻繁に変わることが考えられる

キスト s から特徴語を抽出し，提案手法と同様に bag-of-words

ため，1 つのツイートの内容の影響を他のツイートが大きく受に従って特徴ベクトルを作成する．その後発信地が対象地域

けないよう考慮することが効果的であると考えられる．

また，東京都 23 区，京都市，つくば市の 3 地域では特徴語に名詞を用いる提案手法が最も良い結果となっている．ツイートは 140 字以内という制限があるため，その中で用いられる単語は多くない．KL ダイバージェンスによって抽出された単語を用いる場合，特徴語となる単語数が名詞全てを用いる場合よりも少なくなる．そのため一つのツイート中に含まれる特徴語が少ない，または全く特徴語が含まれないツイートが増え，結果的に推定の手がかりが少なくなってしまうからだと考えられる．

6. 4 他手法との比較実験(a) 東京都 23 区(b) 京都市(c) 横浜市(d) つくば市

本実験ではベースラインとなる比較手法と提案手法とを比較し，提案手法が効果的に対象地域からのツイートを収集できているかを評価した．ベースラインとして用いたのは以下の 3 つの手法である．

•

Statistics N TW：対象地域からツイートを発信する可能性が高い K ユーザを探し，そのユーザをフォローし続けることでツイートを収集する．最初の N タイムウィンドウまではランダムに選出した N K ユーザを順番に一度ずつフォローし，

N + 1 タイムウィンドウ以降は N タイムウィンドウまでに得られた報酬上位 K ユーザをフォローし続ける．

•

図 3 ベースラインとの比較（150 タイムウィンドウ）．x 軸はタイム
ウィンドウを表し，y 軸は各タイムウィンドウまでの対象地域か

Number：ツイート数の多いユーザをフォローすることでら発信されたツイートの累計収集数を表す．全地域で提案手法がツイートを収集する．タイムウィンドウ内で投稿されたツイー比較手法を最終的なツイート収集数で上回っていることが分かる．

ト数を報酬とする ϵ-Greedy アルゴリズムを用いてフォローユー
ザを選出する．報酬の期待値の計算は提案手法と同じく式 (1)
を用いる．

•

と Statistics 18T W の差は大きい．Statistics の場合，収集開始から N タイムウィンドウまではユーザを順にフォローしてRandom：ランダムにフォローユーザを選びツイートをどのユーザが対象地域からツイートを発信する可能性が高いか収集する．毎タイムウィンドウ，ユーザ集合の中からランダム調べる必要があり，この期間に仮に対象地域からツイートを発に K ユーザを選出する．

信する確率の高いユーザを発見できたとしても，そのユーザを

N umber のパラメタ ϵ については ϵ = 0.5 とした．実験は各フォローすることができるのは N + 1 タイムウィンドウ以降

手法 20 回ずつ行い，その平均値を結果として示す．実験結果になってしまう．提案手法の場合，バンディットアルゴリズム

を図 3，図 4 に示す．

を用いることで対象地域からツイートを発信する可能性が高い

図 3 から，4 地域全ての場合で提案手法が全比較手法を最終ユーザを探す「探索」と，実際に可能性が高いとわかったユー的なツイート収集数で上回っている．Statistics では最初の N

ザのツイートを収集する「活用」の二つを同時に行うことがで

タイムウィンドウの報酬からフォローするユーザを決定するた

きるため，収集開始直後からツイートが集まりやすいという利め，N + 1 タイムウィンドウ以降にフォローユーザが対象地域点がある．

を訪れなくなったり，逆にフォロー外のユーザが対象地域を訪さらに，4 地域のうち，人口の少ない京都市，横浜市，つくれるようになったとしてもユーザの行動の変化には対応でき

ば市は人口の多い東京都 23 区に比べて提案手法と比較手法間ない．提案手法ではバンディットアルゴリズムを用いることでの最終的なツイート収集数の差が大きくなった．人口の少ない

ユーザの行動の変化に合わせてフォローユーザを変更すること

地域では膨大なユーザ集合の中からその地域を訪れるユーザをができ，より効率的に対象地域から発信されたツイートを収集探すことは困難であると考えられるが，提案手法の場合はこのできたと考えられる．また，N umber ではツイートを多く投稿

ような条件下でもユーザを探索しながら効率的に対象地域からするユーザをフォローするためにバンディットアルゴリズムをのツイートが収集できている．

用いた．しかし，ツイートを多く投稿するユーザは必ずしも対象地域からツイートを発信しているとは限らない．提案手法で

7. 結

論

は報酬の推定の際にユーザが対象地域からツイートを投稿した

本研究では Twitter から特定地域より発信されたツイートを確率を考慮することで，適切なユーザをフォローすることがで収集する手法を提案した．本研究では過去に頻繁に対象地域かきたと考えられる．

らツイートを投稿しているユーザは今後も対象地域を訪れてツまた，図 4 は実験結果のうち，開始から 25 タイムウィンド

イートを投稿する可能性が高いという仮定に基づき，バンディッ

ウ目までを拡大したものである．最終的なツイート収集数でトアルゴリズムを用い，ユーザのフォローを選択，ユーザからは，提案手法の他に Statistics 18T W も比較的多くのツイー得られる対象地域から発信されたツイートを報酬ととらえるこトを収集できているが，収集開始直後に着目すると，提案手法

文(a) 東京都 23 区(b) 京都市(c) 横浜市(d) つくば市

図 4 ベースラインとの比較（25 タイムウィンドウ）．x 軸はタイ
ムウィンドウを表し，y 軸は各タイムウィンドウまでの対象地域から発信されたツイートの累計収集数を表す．提案手法とStatistics 18T W の差は大きい．

とで，一定時間ごとにフォローユーザの選択を行った．また，発信地を示すジオタグが付与されているツイートはごく少数であり，ツイートから位置情報に関する報酬を直接得ることができないという問題点があった．そのため，ツイートのテキストを用いて発信地推定を行うことでツイートから得られる報酬を推定した．本研究の貢献は，以下の 2 点である．

(1) バンディットアルゴリズムを用いて，特定地域から発信されたツイートを継続的に収集する手法を提案した．また，直接得られない報酬をツイートのテキストから推定する手法を提案した．
（第 5 章）(2) 実際の Twitter データを用いた評価実験により，提案手法によるツイート収集の有効性を示した．
（図 2，図 3）
今後の課題として以下の 3 つが挙げられる．まず，提案手法
内で用いた報酬の推定方法よりもさらに有効な報酬推定の方法を検討し，より効率的なツイート収集を行うことである．提案
手法では発信地推定にナイーブベイズ分類器を用いたが，他の分類機の検討により推定の精度を高めることが挙げられる．また提案手法ではツイートごとに発信地推定を行ったが，投稿間隔の短い前後のツイートの内容を考慮するなどの手法も考えられる．2 つ目に他のバンディットアルゴリズムの検討が挙げられる．提案手法では ϵ-greedy アルゴリズムを用いたが，バン
ディットアルゴリズムは他にも様々な手法が存在するため，より効果的な手法の検討が考えられる．最後に，今回は最長で 600
時間分のデータを用いて実験を行ったが，より長期的な実験を行った場合にも提案手法はユーザの行動の変化に対応しながらツイートの収集が可能であるか検証することが考えられる．

献[1] Shipra Agrawal and Navin Goyal. Analysis of thompson sampling
for the multi-armed bandit problem. In COLT, pp. 39–1, 2012.
[2] Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Mach. Learn., Vol. 47, No.
2-3, pp. 235–256, May 2002.
[3] Lars Backstrom, Eric Sun, and Cameron Marlow. Find me if you can:improving geographical prediction with social and spatial proximity.
In Proceedings of the 19th international conference on World wideweb, pp. 61–70. ACM, 2010.
[4] Nicolò Cesa-Bianchi and Paul Fischer. Finite-time regret bounds forthe multiarmed bandit problem. In ICML, pp. 100–108. Citeseer,
1998.
[5] Zhiyuan Cheng, James Caverlee, and Kyumin Lee. You are where
you tweet: A content-based approach to geo-locating twitter users.
In Proceedings of the 19th ACM International Conference on Information and Knowledge Management, CIKM ’10, pp. 759–768, New
York, NY, USA, 2010. ACM.
[6] Clodoveu A Davis Jr, Gisele L Pappa, Diogo Rennó Rocha
de Oliveira, and Filipe de L Arcanjo. Inferring the location of twitter
messages based on user relationships. Transactions in GIS, Vol. 15,
No. 6, pp. 735–751, 2011.
[7] Thibault Gisselbrecht, Ludovic Denoyer, Patrick Gallinari, and Sylvain Lamprier. Whichstreams: A dynamic approach for focused data
capture from large social media. In Proceedings of the Ninth International Conference on Web and Social Media, ICWSM 2015, University of Oxford, Oxford, UK, May 26-29, 2015, pp. 130–139, 2015.
[8] Yohei Ikawa, Miki Enoki, and Michiaki Tatsubori. Location inference using microblog messages. In Proceedings of the 21st International Conference on World Wide Web, WWW ’12 Companion, pp.
687–690, New York, NY, USA, 2012. ACM.
[9] Sheila Kinsella, Vanessa Murdock, and Neil O’Hare. ”i’m eating asandwich in glasgow”: Modeling locations with tweets. In Proceedings of the 3rd International Workshop on Search and Mining Usergenerated Contents, SMUC ’11, pp. 61–68, New York, NY, USA,2011. ACM.
[10] Rui Li, Shengjie Wang, and Kevin Chen-Chuan Chang. Towards
social data platform: Automatic topic-focused monitor for twitter
stream. Proc. VLDB Endow., Vol. 6, No. 14, pp. 1966–1977, September 2013.
[11] Reid Priedhorsky, Aron Culotta, and Sara Y Del Valle. Inferring theorigin locations of tweets with quantitative confidence. In Proceedings of the 17th ACM conference on Computer supported cooperative
work & social computing, pp. 1523–1536. ACM, 2014.
[12] Takeshi Sakaki, Makoto Okazaki, and Yutaka Matsuo. Earthquake
shakes twitter users: real-time event detection by social sensors. In
Proceedings of the 19th international conference on World wide web,pp. 851–860. ACM, 2010.
[13] Richard S Sutton and Andrew G Barto. Reinforcement learning: An
introduction, Vol. 1. MIT press Cambridge, 1998.
[14] Sarah Vieweg, Amanda L Hughes, Kate Starbird, and Leysia Palen.
Microblogging during two natural hazards events: what twitter may
contribute to situational awareness. In Proceedings of the SIGCHI
conference on human factors in computing systems, pp. 1079–1088.
ACM, 2010.
[15] Christopher John Cornish Hellaby Watkins. Learning from Delayed
Rewards. PhD thesis, King’s College, Cambridge, UK, May 1989.
[16] Yuto Yamaguchi, Toshiyuki Amagasa, Hiroyuki Kitagawa, and Yohei
Ikawa. Online user location inference exploiting spatiotemporal correlations in social streams. In Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge
Management, pp. 1139–1148. ACM, 2014.
[17] Xiaojin Zhu, Zoubin Ghahramani, John Lafferty, et al. Semisupervised learning using gaussian fields and harmonic functions. In
ICML, Vol. 3, pp. 912–919, 2003.