DEIM Forum 2014 B4-3

実世界ユーザ行動予測の為の閲覧履歴に基づく欠損データ補間手法の提案
丸山 直樹†

若宮 翔子 ††細川 侑士 †豊和†

角谷 和俊 ††秋山河合由起子†† 京都産業大学コンピュータ理工学部 〒 603-8555 京都府京都市北区上賀茂本山†† 兵庫県立大学環境人間学部〒 670-0092 兵庫県姫路市新在家本町 1-1-12
E-mail: †{g1045074,akiyama}@cse.kyoto-su.ac.jp, ††s.wakamiya@gmail.com,†††{i1358103,kawai}@cc.kyoto-su.ac.jp, ††††sumiya@shse.u-hyogo.ac.jp
あらまし 近年，SNS から発せられる大量データを分析し有用な情報を抽出する研究や，それらの情報を用いて，災害時の被災支援へ応用するサービスが活発に行われている．本論分ではユーザの 閲覧操作履歴等を用いることで，実空間での将来のユーザ行動を予測する手法を提案し，構築したシステムを用いて評価実験を行う．具体的には，ユーザの操作・閲覧履歴から時間と場所に関係するデータを抽出・分類し，ベイズ推定等を用いて移動確率を算出する．
また，イベント発生に関しても，発生予測を行う．これにより，イベントが発生前及び発生直後に発生場所における居住者，訪問者，訪問予定者の判定が可能になる．本システムにより，地震などの災害発生前，または発生直後に各ユーザ毎に適切な避難経路や交通情報等を提供可能となる．
キーワード

災害情報，行動推定，情報推薦，協調フィルタリング

Naoki MARUYAMA† , Shoko WAKAMIYA†† , Yuji HOSOKAWA† , Yukiko KAWAI† , Toyokazu
AKIYAMA† , and Kazutoshi SUMIYA††† Computer Department of Science Engineering，Kyoto Sangyo University
Kamigamohonzan， kitaku， Kyoto-shi，Kyoto，603-8555 Japan†† School of Human Science and Environment, University of Hyogo
1-1-12 Shinzaike-honcho, Himeji, Hyogo, 670-0092, Japan
E-mail: †{g1045074,akiyama}@cse.kyoto-su.ac.jp, ††s.wakamiya@gmail.com,†††{i1358103,kawai}@cc.kyoto-su.ac.jp, ††††sumiya@shse.u-hyogo.ac.jp

1. は じ め にザの操作・閲覧履歴の URI より，ユーザが入力した駅名 (地名) と時刻を高い精度で抽出できることを確認し，ユーザに出近年，Twitter や Facebook から発せられる大量の CGM デー

発地あるいは訪問予定地のイベント情報を提示するシステムのタを分析し有用な情報を抽出する研究 [1] や，それらの情報を基本的な実現の可能性を示した．各ユーザ毎に適切な情報を提用いて，災害時の被災支援へ応用するサービス [2] が活発に行示するためには，将来ユーザがどこにいるかという位置推定をわれている．しかしながら，解析対象となるデータはユーザ行行う必要がある．しかし，交通案内サイトから地名と時刻の情動後に発生するため，イベント発生後の状況分析は可能である報を抽出するだけでは，位置推定を行うには不十分である．

が，イベント発生前や発生直後の情報提供は困難である．また，そこで，本研究では，ユーザの Web 閲覧操作履歴のログをこれらの研究は，震災等イベントの発生時後に多くのユーザに分析し，確率的にユーザの行動を推定することで，ユーザの位同一の内容を提示しているが，各ユーザごとに的確な情報を置推定精度の向上を目指す．本提案手法は，抽出された地名と迅速に提供するには至っていない．それに対し，我々は先行研

時刻の情報を用いて，まず最尤法により現在地の時刻における究 [3] において，各ユーザ毎への的確で迅速な情報提供を目的各地名に対する存在確率を抽出する．次にユーザの嗜好性ならとして，日本国内の複数の主要交通案内サイトを対象に，ユーびに習慣性から既知となる情報に対して操作・閲覧が不要にな

図 1 システム概要図る場合に，次の欠損データ補間手法を用いて行動確率を算出す場合は，query を入力した Web ページおよび出力結果の Web

る．

ページを分析し，抽出する．その際，登録した居住地以外の地

1) ユーザの過去の操作・閲覧履歴の類似性を用いた手法

名を訪問地の候補とする．また提案手法では，抽出された地名

2) 群衆行動との類似性を用いた手法と時刻の情報を用いて，まず最尤法により現在地の時刻におけこれら存在確率と行動確率より，将来にわたるユーザの行動をる各地名に対する存在確率を抽出する．次にユーザの指向性お予測する．それにより震災等のイベント発生時に，特にユーザよび習慣性により既知となる情報に対して操作および閲覧が不の土地勘 (地理や事情 についての知識) の有無に応じた的確で要である場合に欠損データ補間手法を用いて行動確率を算出す

迅速な情報提供を可能となる．

る．算出した存在確率および行動確率より，将来におけるユー

本論文では，将来におけるユーザの存在確率および行動確率を算出する手法について述べ，実装したシステムの有用性を検証する．

2. システム概要

ザの行動を予測する．最後に災害等のイベントが発生した際，ユーザに適した情報を提示する．
これにより，例えば図 1 のように，災害情報の場合，ユーザが居住者と分かれば，イベント発生場所の土地勘があると予測され，最低限のテキストでより多くの居住者へ避難警告を提示

本システムでは，Web サイトの閲覧履歴情報よりユーザのできる．訪問者と分かれば，イベント発生場所の地理情報に関行動推定を行い，イベントが発生した際にユーザが訪問者か訪する知識は居住者と比較すると浅いと考えられるため，訪問予問予定者かを判定し，ユーザごとに適したイベント情報を Web

定地周辺の避難場所への地図等の情報も同時に提示する．さら

ブラウザ上にポップアップ提示する．また，Web ブラウザ上に，訪問予定者にはイベント発生場所の地理情報の知識が浅いへのポップアップ提示はイベント情報により異なる．例えば，と考えられるがイベント発生場所に訪問中ではないのでテキス天気情報が更新された場合は Web ブラウザ上に小さくポップトでの警告を提示する．

アップ提示し，警報や注意報の場合は Web ブラウザ上に大きくポップアップ提示する．

3. Web 閲覧履歴を用いた地名抽出

提案システムの概要を図 1 に示す．まず，ユーザは Firefox

本研究では，閲覧履歴から交通情報や宿泊情報に関するサイの拡張機能をインストールする．その際にユーザは居住地であトの情報を行動推定に用いる．一般にユーザはブラウザを用いる地域名を選択し，登録する．拡張機能により，ユーザのブラて 意思決定を行う際に交通案内サイトや宿泊サイトの「フォーウジングの閲覧履歴情報である URI を取得する．本システムでム」 を用いて往路探索や宿泊場所の決定を行う．そこで本論文

は，一般にユーザはブラウザを用いて意思決定を行う際に交通

では， ユーザがフォームに入力した後に得られる URI そのも案内サイト等の「フォーム」を用いて往路探索の決定を行うたのから出発地，到着地，到着時刻等の情報を抽出する． ユーザめ，全ページを解析せず query を含む URI とその入出力 Web

行動推定は URI のうちフォームに入力された query 部分を用ページのみを解析する．それにより，コストの削減とユーザのいる．query は name 値=value 値のペアの連続値で構成されてプライバシーの考慮につながる．取得した URI の query 部分いる．解析対象となる URI は query を含む URI とし， またを用いて交通情報が含まれているかを判定し，出発地，到着地，そのフォーム入力ページ，出力ページのみを対象とする．URI日付，時刻の情報を抽出する．query 部分のみで抽出できないの query 部分の value 値を形態素解析する．形態素解析結果

の品詞が「地名」のキーワードを抽出し，value 値を地名と判の地名との移動時間を検出し，移動時間が長いと存在確率が低定する． なお，地名と判定されなかった URI は以降の出発地，くなるよう．重み log (t) として積算する．

到着地，日付，時刻の抽出を行わない．

例えば，T 時に到着地として東京，大阪とあった場合，T − X

そこで取得した地名の name 値がフォーム入力ページの時間前の到着地として奈良が算出されているとする．

HTML ソース内の name 値と一致し，かつ同じ行に「出発/乗その場合，奈良から大阪は X 時間より短い移動時間であるが，車」あるいは「到着/目的/下車」というキーワードを含んでい奈良から東京へは X 時間より短いとすると，その場合の時刻た場合，取得した地名が「出発地」あるい は「到着地」である

T のユーザの存在確率としては，大阪の方が高くなるものとすと判定する．

る．同様にして T + Y 時の到着地に対しての移動時間も時刻同じ行に「出発/乗車」あるいは「到着/目的/ 下車」というキーワードを含まない場合，取得した 2 つの地名の value 値にT の存在確率の重みとして用いる．
4. 2 欠損データ補間手法に基づく行動確率

対する name 値がフォーム入力ペー ジの HTML ソース内のname 値と一致する行の間に「出 発/乗車」あるいは「到着/目的/下車」というキーワードを含むか判定する．
「出発/乗車」というキーワードを含む 場合，HTML ソース内の 2 つの name値を含む行間と同じ行数を name 値を含む行の前後で「出発/乗車」あるいは「到着/目的/下車」というキーワードが存在するか判定する．HTML ソース内の 1 つ目の name 値を含む行より前で「出発/乗車」，「到着/目的/下車」というキーワードを含まず，かつ HTML ソース内の 2 つ目の name 値を含 む
行より後に「到着/目的/下車」を含む行が存在すれば 1 つ目のname 値に対する value 値を「出発地」，2 つ目の name 値に図2対する value 値を「到着地」と判定する．

URI の query 部分の value 値に「/」あるいは「:」を含 む
場合，「日時」あるいは「時刻」であると判定する．
また，出力ページの HTML ソース内に「selected」で選 択されたキーワードを抽出し，キーワードに「年」，「月」，「 日 」，「 時 」，「 分 」というキーワードを含んでいた場 合「selected」で選択されたキーワードが「日時」あるいは 「時刻」であると判定する．
例えば上記から抽出されたデータによるユーザ A の入力，閲覧・操作履歴から抽出されるデータは表 1 のように抽出される．

行動推定図

前節の存在確率に加えて，操作・閲覧履歴が欠落した場合に個々のユーザの過去の履歴（習慣性）に基づき，欠損データを補間する．提案手法は，ユーザの過去の操作・閲覧履歴の類似性を検出し，類似性の高い地名集合のうち，欠損している地名への移動確率を算出する．

具体的には，過去に {X ，Y ，Z} の地名入力を行った後に {X ，Z} の地名を入力する場合，{X ，Y ，Z} の行動確率集合を A = {past pX ，past pY ，past pZ }，その後の入力 {X ，Z} の行動確率集合を B = {now pX ，now pY，now pZ } とし，以下の相関係数を算出する．なお，A の要素はユーザ名

年月日

出発地到着地2 で抽出した存在確率，Bave は存在確率の平均値，入力がな

A

2014

310 12 神奈川

東京

かった now pY は 0 とする．

A2014

310 12 神奈川

栃木A2014310 12 神奈川

埼玉

B2014

310 14

東京

大阪

B2014

310 14東京

奈良2014310 14栃木

埼玉

C時

√

Σni=1 (Ai − Aave )(Bi − Bave )2
Σni=1 (Ai − Aave )√2
Σni=1 (Bi − Bave )(2)

これに past pY 重み付き和として足し合わせることで，今回のデータで欠損している Y への行動確率 now pY が算出される．

表 1 ユーザの入力情報

但し，何度も同じ地名を調べていると判定された場合，はじめから now pY は 0 とはせず，今まで調べた回数に基づいた 0 より大きい値を与えることで，欠損データの補間をよりユーザの嗜4. 行動確率推定好性に近づいたものにすることが可能であると考える．前述と4. 1 最尤法による入力情報に基づいた存在確率

同様に，嗜好性が類似するユーザの特徴に基づき，欠損データ

2 で得られた情報から抽出した地名がどれだけの頻度で入力を補間する．ここでは，他ユーザとの類似性を相関係数によっされたかを，その行動の尤もらしさとして算出する．総入力回て算出する．これにより，ユーザが入力していない地名に対し数を n，その地名が入力された回数を k として以下の対数尤度て，嗜好性が類似したユーザが移動した地名集合のうち，欠損関数に代入し，L(p) = 0 となるような p の値を算出する．

している地名への移動確率が算出可能となる．

L(p) = log(p Ck ) + k log p + (n − k) log(1 − p)(1)

また，同時刻で閾値以上の地名が複数抽出された場合は，前後5. 実算出した結果，交通案内サイトの 1 ページあたりの閲覧時間は験20 秒ほどであることが分かる．

本実験では，開発したシステムの有効性を検証するため，以下の実験を行う．

1) ユーザ操作履歴に基づいた存在確率の妥当性の検証
2) 欠損データに対する補間手法の妥当性の検証
国内の抽出対象となる交通案内サイト８件を示す．これらのサイトより，出発地，到着地，日付，時刻の４項目の抽出を行い，回PV 操作時間

PV 割合

目的地 存在確率

判定

1回

82分

25 秒/ページ 福知山

1.0

正解

2回

143分

21 秒/ページ

守口

0.67

正解

3回

245分

21 秒/ページ

姫路

0.5

正解

4回

338分

24 秒/ページ

彦根

0.454

不正解

それらの情報から各時刻に対するユーザの行動推定を行う．ま表 4 ユーザ A(49 歳) の実験結果

た，今回は出発地および到着地は JUMAN で地名と判定出来るものを対象とする．

交通案内

表2回

PV 操作時間

1回

113分

27 秒/ページ 福知山

PV 割合

目的地 存在確率

1.0

判定
正解

番号

サイト名

2回

214分

19 秒/ページ

池田

0.73

正解

1

ジョルダン

3回

265分

19 秒/ページ

西宮

0.57

正解

2Yahoo!路線情報

4回

255分

20 秒/ページ

草津

0.5

正解

3

駅探

表 5 ユーザ B(52 歳) の実験結果

4goo 路線

5Google 乗換案内

6エキサイト乗り換え案内

回

PV 操作時間

7

ハイパーダイヤ

1回

41分25 秒/ページ 福知山

1.0

正解

8NAVITIME

2回

123分25 秒/ページ

守口

0.5

正解

3回

245分

21 秒/ページ

西宮

0.375

不正解

4回

245分

21 秒/ページ

彦根

0.54

正解

実験に使用したサイトのリスト

表6

5. 1 実 験 環 境

PV 割合

目的地 存在確率

判定

ユーザ C(26 歳) の実験結果

Web サイトを操作・閲覧するブラウザは JavaScript で記述
した拡張機能をインストールした Firefox バージョン 18.0 を利用し，ユーザの行動推定に必要なアクセス履歴を取得する．
データベースは SQL version 3.6.12 を用いた．取得した URIは WebSocket 通信を採用し，リアルタイムに取得管理する．
実験対象者は，20 代から 50 代の男女４名である．

回

PV 操作時間

1回

111分10 秒/ページ 福知山

1.0

正解

2回

224分

18 秒/ページ

守口

0.5

正解

3回

153分20 秒/ページ

明石

0.75

正解

4回

183分17 秒/ページ

米原

0.33

不正解

5. 2 ユーザ操作履歴に基づいた存在確率の妥当性の検証
回

1回

候補地
福知山

-

西宮

4回

近江八幡
表3

目的地 存在確率

判定

表 7 ユーザ D(22 歳) の実験結果

5. 3 欠損データに対する補間手法の妥当性の検証

-

-

-

-

姫路

明石

-

手法により，他の全てのユーザから重み付き和として各候補地

草津

彦根

米原

に対する移動確率を算出し，それを 5.2 での値に付与すること

2 回 池田 (大阪) 守口 (大阪)
3回

PV 割合

提示情報

次に，他ユーザの抽出データとの相関性を用いたデータ補間

で，入力データだけでは閾値にとどいていなかったような存在確率を閾値以上に導くことで，欠損データに対する補間手法の実験対象者には，出発地が奈良駅であることを告げ，候補地妥当性を検証することとする．

を提示する (表 3)．被験者は，出発地から候補地までのアクセスを表 2 のサイトを用いて自由に調べる．調べた結果から，被ユーザ名 目的地

5.2 での移動確率 5.3 を用いた移動確率

判定

験者は目的地を選択する．ただし，１回目は候補地が１カ所なA

彦根

0.454

0.567

正解

ので，目的地も同じである．本実験では，複数の選択肢の中か

C

西宮

0.375

0.5125

正解

D

米原

0.33

0.38

不正解

ら１つを選択する行為に対する実験を想定しており，2 回目以

表 8 5.3 の検証結果

降は，各候補地の距離は同一県内とした．
提案する存在確率は，これらの閲覧履歴を用いて算出するが，本実験では (1) を用いて閾値を 0.5 とした．各ユーザの試行結果を表 4 から 7 に示す．正解率は全体の 81%であった．候補地が 2 つ以内の場合においては 100%で正解することが出来た．
試行回数となる閲覧ページ数 (PV) と操作時間から平均 PV を

表 8 には，表 4 から 7 に示した結果のうち，不正解であった
データ 3 つに着目し 5.3 の補間手法を用いている．この結果から，5.2 だけでは不正解であった 3 つのデータのうち，2 つが閾値をこえ，正解データとなった．

5. 4 考察

実験結果から，候補地が少ない場合においては高い精度で行るであろう場所に，ユーザの状況に適した情報を提示することが可能となる．

動の推定に成功しているが，候補地が増えると精度が低くなることが分かる．これは，候補地が多くなるとユーザの PV が増加し，目的地となる地名以外を調べたページでの操作回数が増え，目的地の推定が難しくなることが考えられる．例えば，交通手段が複数ある候補地では，各手段での移動について一通り

謝辞調べた上で，値段や乗り換え回数などを比較しなければならな

本 研 究 の 一 部 は ，総 務 省 戦 略 的 情 報 通 信 研 究 開 発 制 度

いため，PV が増加し，その候補地での存在確率が高くなりや(SCOPE) の一環として実装されたものである. ここに記しすい． そのため，各ユーザの操作履歴だけでは，信憑性の高いて謝意を表す．

データを算出することが難しいことがわかる．そこで，他ユーザの抽出データを用いることでより信憑性の高いデータを算出することができることが 5.3 の実験結果から考察される．
また，結果の中の 3 つの不正解データのうちの 1 つは 5.3 の手法を用いても移動確率が低いままであった．そこで表 8 の不正解データの目的地に着目すると，5.3 を用いて閾値をこえたデータの目的地は，表 4 から 7 の他ユーザの目的地として選ばれていることが見て取れる．しかし，ユーザ D の目的地として選んだ米原は他のユーザが目的地として選ばなかった地名であることがわかる．この結果により，この手法では，類似した嗜好性を持つユーザが他のユーザの中に含まれていない場合において，データ補間の精度に影響が出てくることが考えられる．

6. 関 連 研 究
Twitter の公共アカウントのツイート内容とフォロワーの推移を分析し，災害時における Twitter での公共機関のアカウン
トのガイドラインの作成を行った研究 [4] や Twitter に投稿された実生活情報から有用性の高いものを抽出し局面に応じた 記事をユーザに提示するシステムの提案手法 [8] がある．これらが災害等のイベントが発生した際に多くのユーザに同一の情報を提示するのに対し，本研究ではユーザの位置推定に基づき各ユーザに適した情報を提示する点で異なる．アクセス履歴からユーザの行動を推定する手法に，Web サイトのアクセス履歴からユーザの傾向を読み取り，次にどのページを閲覧するかを予測するシステム [6] や機械学習手法により Web 上におけるユーザの行動推定を行うシステム [7] 等が研究されている．これらが次に閲覧するであろうページの予測とい う仮想的な行動の推定を目的としているのに対し，本研究では ユーザの位置推定という現実の行動の予測を行い，それに基づく適切な情報をユーザに提示するということを目的としている点で異なる．

7. ま と め
本研究では，Web の操作・閲覧履歴情報に基づき，最尤法による存在確率と欠損データ補間に基づく行動確率を算出することで，ユーザの将来の行動を推定する手法を提案し，プロトタイプを構築した．ユーザが Web ページに実際に入力した情報だけでなく，過去の入力や他ユーザの履歴により入力された情報を用いることで，欠損データの補間ならびに行動推定の実現の可能性を示すことができた．本手法を用いて，災害等のイベントが発生した際におけるユーザの現在地，または将来移動す文

献[1] Leah Hoﬀmann．Looking back at big data Communicationsof the ACM，Vol.56 Issue.4，pp.21-23，April 2013．
[2] 小出明弘，斉藤和巳，鳥海不二夫，風間一洋，松尾真人，デンド
ログラムを用いた震災時における Mention・Hashtag ツイートの利用傾向分析．WebDB フォーラム 2012[3] 細川侑士, 西村直也, 白石優旗, 河合由起子, 秋山豊和, ユーザ行
動抽出に基づく訪問者に対する災害等イベント情報発信システ
ムの提案, DEIM Forum 2013.
[4] 吉村直子，井上智雄，東日本大震災前後のマイクロブログサー
ビス Twitter における故郷アカウントの利用分析，情報処理学会報告，2012-GN-83(5)，1-8，2012．
[5] 山本雅人，小笠原寛弥，鈴木育男，吉川正志，東日本大震災時の Twitter における情報伝播ネットワーク，情報処理 53(11)，1184-1191，2012．
[6] 近徳高, 高井秀人, 上里福美.Web サイト訪問者のページ閲 覧行
動予測システム. 東京工芸大学工学部紀要,Vol.27 No.1, 2004.
[7] 大塚大輔, 久保山哲二, 安田浩.Web アクセスログからの閲覧 者の行動分析. 電子情報通信学会総合大会講演論文集,D-9-22, 2011[8] 山本修平, 佐藤哲司. Twitter からの実生活情報の抽出法の提案. 第 4 回データ工学と情報マネジメントに関するフォーラム(DEIM Forum 2012)F3-4，2012.