DEIM Forum 2014 E4-4

位置情報を利用した情報配信のための習慣度算出手法
林亜紀†

松林 達史†澤田宏†† 日本電信電話株式会社 NTT サービスエボリューション研究所 〒 239–0847 神奈川県横須賀市光の丘 1-1
E-mail: †{hayashi.aki,matsubayashi.tatsushi,sawada.hiroshi}@lab.ntt.co.jp
あらまし

本研究では，行動が本人の習慣に沿っているかを示す「習慣度」を定義する．位置情報を利用した情報配信において，利用者と情報提供者双方のニーズに合った配信内容・タイミングの決定が課題となっている．従来法では自宅からの距離や履歴頻度を用いた習慣/非習慣判別により，ニーズの把握を試みた．提案法では，曜日・時間帯を考慮した複数の多項分布の重み付き線形和を用いた習慣度定義により，自宅近くにおける非習慣も含めた詳細な行動理解を実現する．チェックインログを使用した検証により，本人履歴にない場所を推薦可能なタイミングの検出に加え，同等の習慣度で他ユーザが訪問した場所の抽出から，例えば出張者同士の履歴の考慮が可能になるなどの効果を示す．
キーワード

位置情報，確率モデル, ソーシャルメディア，情報配信
表 1 飲食店情報配信において考えられるニーズの例

1. は じ め に

情報配信例

近年，モバイル端末の普及とソーシャルメディアの発展から，
位置情報の取得・蓄積が容易になり，様々なサービスが提供さ考えられるニーズ
確実性

意外性

行きつけ・日常

○?

△?

出張・旅行

△?

○?

れている．現在地情報の活用だけでなく，履歴頻度など蓄積ログの解析から，ユーザの行動を予測し，よりニーズにマッチした情報を配信する取り組みも行われている．しかしながら，現在地や居住地，本人履歴を利用した情報配信には，配信内容・
タイミングの決定において以下に述べる未解決の課題がある．
情報配信におけるニーズには，•

確実性：ユーザの行動傾向に沿った確度の高い情報•

意外性：ユーザが従来では知り得なかった情報の 2 側面が存在すると考えられる．例えば飲食店情報配信において，どちらを重視して考慮するべきかは，表 1 に示すように
時と場合に応じて異なり，好ましい考慮比率を定めることは困難である．会社出勤日の昼食時など日常時には，よく行く店舗の割引クーポンが好まれるが，例え会社近くであっても休日の昼食時には，普段より高級で，訪れたことのない店の情報が好まれる可能性がある．一方，出張時にはご当地料理を出す店舗が望まれる可能性や，普段からユーザが好んで食べているラー
メンを現地で食べられる店舗が好ましい可能性もある．既存サービスでは，履歴にある店が近隣にあればその店の情報を，
出張時には，現在地近くでよく行かれる店舗の情報配信を行うな行動をしている状態では意外性を考慮する必要がある．必ず
しも二者択一的な考慮が適切とは限らないが，適切な考慮比重とその内容を決定するための行動理解の一手段として，ユーザが習慣に沿った行動をしているのか，非習慣的な行動をしているのか (*) を推定する技術が必要であると考えられる．そこ
で，提案手法では，各ユーザが持つ「習慣」を抽出した上で，(*) を推定する習慣度という指標を新しく定義・算出する．な
お，「習慣」は例えば「A さんは平日の朝は品川駅付近の会社にいることが多い」などの行動傾向であり，ユーザ情報・時間情
報・位置情報から構成する．
提案する習慣度指標により，例えば出張中などの非習慣状態を検出し，本人履歴に加え，他人履歴を考慮できるタイミングを見極めることが期待される．また，配信内容について，出張者同士など状況が類似した他人履歴の抽出が必要であり，どのような他人履歴の考慮が効果的かを見極めることが求められる．
そこで，提案する習慣度の要件として以下の 2 つを設定する．

(2) 同一場所は複数ユーザから同等習慣度で訪問されやすい

(1) 直前の行動の習慣度が直後の行動でも持続しやすい

ことが多く，日常的に訪れる場所における未訪問店舗の推薦機



会を逃す例や，遠方への出張時にご当地料理店よりも現地で一要件 (1) により，直前の行動の習慣度が低ければ，直後の行動

般的によく行かれる社員食堂が提示されてしまう例もある．情においても非習慣的状態が続くと予測して，他人履歴を考慮し報配信では内容とタイミングが重要であり，ユーザの納得感にた意外性の高い情報を重視することが可能になる．また，要件

加え，店舗側の新規顧客開拓というニーズを考えた際に，いつ(2) により，出張者同士の履歴の考慮などが可能になる．

どのユーザにどの店舗を提示すれば快く来店されるかという

以下，2 章では，位置情報を利用した行動予測・情報配信に

課題の解決が望まれる．我々は，時と場合に応じた 2 側面の適関する既存研究の概要と本研究の位置づけを述べる．3 章では，

切な考慮によるユーザと情報提供者双方の満足度向上に向け，提案する習慣抽出モデルと習慣度算出手法について詳細に述べ

ユーザの行動理解技術の向上を目指す．

る．4 章では，提案手法を定性的・定量的に検証し，5 章で提前述の例のように，ユーザが本人の習慣に沿った行動を行っている状態では確実性を重視する場合が多く，一方で非習慣的案法を活用した情報配信について例を挙げて検討する．最後に，6 章にまとめと今後の課題を示す．

2. 既 存 研 究
習慣度の算出行動が習慣的であるか，非習慣的であるかを検出する研究と

表 2 チェックインデータの例
User ID

年月日

曜日

時間帯

Location ID

緯度

経度

58186

2010/01/08

月

21

12587

39.XX

-105.XX

58186

2010/05/20

火

21

12587

39.XX

-105.XX

58187

2010/06/12

日

07

31544

41.XX

-95.XX

して，自宅や勤務場所など訪問頻度の高い場所から遠いほど非表3

習慣であるとするもの [3], [6], [11]，移動距離が通常時の 2 倍以上であれば非習慣とするもの [4]，移動時間の長短で判別するもの [10] がある．単位時間内の訪問場所の多様性から旅行者とい入力情報の表現

入力情報

表現

入力情報

表現

User IDu

曜日 [月曜-日曜]

dLocation IDl

時間帯 [1-24]t

う非習慣を検出する手法 [8] も提案されている．しかしながら，
これらのルールベースの手法では，習慣抽出時に時間情報を考慮しないため，例えば「会社近くにおける家族との休日の買物」「いつもより遅い/早い帰宅」などの，日常的によく行く場所への弱い非習慣を含めた詳細な習慣度は定義されていない．
他人履歴を考慮した行動予測・情報配信
他人履歴を活用した行動予測・情報配信を行う研究として，
ユーザ別場所頻度分布 [2], [14] や，時間を考慮したユーザ別場
所頻度分布 [12] を元にしたユーザのクラスタリングによる協調
フィルタリングが提案されている．習慣時と非習慣時のログが混在した状態で類似ユーザを抽出するため，普段類似した場所に行くユーザの行動が非習慣時にも類似するとは限らず，適切な推薦が実現できない場合がある．Malmi ら [9] は訪問時間分
布を元にした場所間のクラスタリングにより，他人ログを活用した行動予測によるコールドスタート問題の解決を図っている
が，習慣・非習慣の区別なく訪問傾向を抽出している．
一方，ログの習慣/非習慣性を考慮した情報配信も行われているが，現在地にログが多いユーザの習慣を強く考慮する手法 [13] では，社員食堂や自宅が推薦されてしまう可能性がある．
倉島ら [6], [7]，Leung ら [8] は非習慣行動時の習慣を反映した情報配信を提案しているが，前述のように習慣/非習慣の抽出がルールベースとなっていることに加え，習慣行動時の履歴は考慮しないため，ユーザが普段好んでいるラーメン店を出張先でも提示する，などの嗜好の反映は想定していない．
本人履歴と他人履歴の両方を考慮した行動予測・情報配信
上述した行動予測・情報配信手法では，本人履歴と他人履歴のどちらをどのようなタイミングで優先させるかは考慮せず，

マルコフモデルと掛け合わせることにより，行動予測精度を向上させたが，「月曜 8 時台」など曜日と時間帯の両方を考慮した習慣は抽出していなかった．
提案手法との比較提案手法では，様々な場所に対して，曜日・時間帯依存性を考慮した複数の尺度を持つ多項分布の重み付き線形和により，習慣をモデル化する．従来は検出できなかった，よく行く場所
への非習慣状態を含めて習慣/非習慣状態を検出できる．提案
手法では連続値を取る指標として習慣度を定義する．この習慣度算出により，他人の履歴を考慮するべきタイミングの決定を支援することが可能になるだけでなく，適切に個人履歴と他人履歴の両方を考慮することができると期待される．習慣度の値から，どの程度本人の履歴から次の行動が予測できない状態であるかを把握できることによる．また，他人履歴の考慮内容について，各行動の習慣度を参照することにより，非習慣行動同士のログの考慮，習慣時の嗜好の考慮などが可能になり，満足度の向上が期待される．加えて，昼食時には飲食店情報を配信する，などの配信タイミングの向上も可能になると考えられる．

3. 提 案 手 法
3. 1 提案手法概要と使用データ
本稿では，位置情報を利用した情報配信において，効果的な配信内容・タイミング決定を支援する習慣度算出手法を提案す
る．手法の概要は以下の通りである．



個人毎の周期的習慣 (曜日・時間帯を考慮した

一律に他人履歴の一部を考慮しており，1 章で述べた確実性の

各訪問場所への頻度分布) の抽出

考慮が不十分な場合が生じると考えられる．習慣時には習慣に沿った場所を提示し，非習慣行動時には友人の訪問場所を推薦

Step2: 習慣度の算出
Step1 で抽出した個人周期的習慣をもとに，各行動のする手法 [3] が提案されているが，習慣として抽出する場所が習慣度（習慣への当てはまり度合い）を算出

自宅・会社など少数であること，必ずしも非習慣時に友人の影響を受けるとは限らないことが懸念される．

使用データの概要，実験設定を述べた後，3. 2 節で Step1，3. 3

習慣の抽出



Step1: 確率モデルによる習慣の抽出



節で Step2 の詳細を説明する．

位置情報に基づく習慣を抽出する研究として，一次マルコフ

本稿では，Stanford 大学が公開しているチェックインログ（注 1）

モデルにより場所遷移の習慣を抽出するもの [1]，曜日や時間への適用により提案手法を評価する．Gowalla, Brightkite の 2

帯に依存しないユーザの定常的な興味を抽出するもの [6], [7] がつのサイトのログが公開されており，Cho ら [3] の研究でも用挙げられるが，曜日や時間帯に依存する習慣の抽出は未実現でいられている．問題を簡潔にするため，チェックインデータをあった．一方，Cho ら [3] は時間を考慮して各ユーザが頻繁に使用して検証を行うが，GPS など連続的な位置情報ログへの訪問する場所を抽出したが，自宅・勤務地など限られた場所の適用も可能である．データの例を表 2 に示す．User ID, チェッ

みを抽出していた．Gao ら [5] は様々な場所の曜日・時間帯別の訪問頻度変遷をガウス分布を用いて表現した習慣を抽出し，（注 1）：http://snap.stanford.edu/data/#locnet

表 4 データの規模
Brightkite

データ期間

2009/06-2010/10

2008/04-2010/10

ログ数

50,785 ログ332,716 ログ

14,837 箇所

ユーザ数

1,164 人

3,194 人約 50.0 ログ

約 104 ログーザ
数100000Gowalla

10000

Brightkite

100

=

10

訪 0.40
問 0.30確 0.20率 0.10
0.00

=

A
A
A
A
A
A

8
8
8
8
8
8

水 駅
水 カフェ
水 カフェ
水 本屋
水 駅
水 駅

周期的習慣の算出例

ザ，時間帯，曜日，場所を全て限定してチェックイン回数を数

Gowalla

え，Cl,d,u ではユーザ，曜日，場所を限定し，時間帯は限定せず

Brightkiteにチェックイン回数を数える．従って，Cl,d,u =

1000

場
所
数

= 本屋

= カフェ
=

図2

ログ数と場所数の関係

ログ数とユーザ数の関係

ユ=駅

115,276 箇所

平均ログ数/ユーザ

1000さんの場所 へのチェックイン回数
さんの水曜 時台の総チェックイン回数

本屋
カフェ
駅

Gowalla

場所数

0.60
0.50

= 、 = 、 = 水の場合のMUPTD

項目

∑

t

Cl,t,d,u である．周期的習慣 M UP T D の算出例を図 2 に示す．実際の l の100
10

値は Location ID であるが，ここでは例として駅，カフェ，本

1

1
1

10

100

1000

1

10000

10

100

1000

屋とした．u = A, t = 8, d = 水のログを抽出した上で，各場所

10000

ログ数

ログ数

への訪問確率を算出する．時間帯を考慮する M UP T D ，M UP T

図 1 ユーザ・場所毎の利用ログ数

では，σ=0.3 とした 1 次元の Gaussian フィルターを用いて平滑化を行った．実際の記録時間帯に近いほどチェックイン回数

クイン日時，Location ID，緯度経度を属性として持つ．同一が大きくなるが，前後の時間帯にも値が入る．σ の値は，4. 3の緯度経度の組を持つ場所に対し，同一の Location ID が割り節で示す習慣抽出モデルの検証で決定した．

振られており，提案手法による習慣抽出では Location ID を場

3. 3 Step2:習慣度の算出所として用いている．入力データから得られる情報を，表 3 の

Step1 の習慣抽出モデルを利用して，各行動が習慣的な行動ように表現する．全ての情報を Gowalla，Brightkite のチェッなのか，非習慣的な行動なのかを調べる習慣度算出手法を提案

クインログから得ることができる．公開データに含まれるログ

する．Step1 で定義した習慣のうち，M UP では駅やコンビニのうち，本稿の実験では日本国内のデータだけを抜粋する．国など時間規則性はないがよく行く場所が抽出される．M UP D

内データの規模を表 4 に示し，図 1 にログ数とユーザ数の関係

では出張の多い会社員にとっての会社，M UP T では営業時間（左）とログ数と場所数の関係（右）を示す．

帯の決まっている飲食店，M UP T D では出張が少ない会社員に

3. 2 Step1:確率モデルによる習慣の抽出

とっての会社などが抽出される．このように，習慣モデルによ本手法では情報配信内容だけでなく，タイミングの向上も目り，抽出されやすい場所が異なるため，本手法ではこれらの 4指している．それ故，曜日や時間帯といった時間情報を活用しつの習慣から算出された習慣度を組み合わせて，各行動の習慣

た習慣抽出モデルを提案する．習慣度算出の際に，例えば休日度を算出する．組み合わせにより，訪問総数はあまり多くないに会社近くの商業施設へ家族で行った時など，よく行く場所にが，月に 1 度位の頻度で日曜日に訪れる商業施設などへの訪問

おける非習慣状態を検出することが可能になる．Gao らは曜についても，やや習慣的であることを検出することができる．

日・時間帯をそれぞれ考慮した習慣の積算を行ったが，提案手各ログが習慣的なのか，非習慣的なのかを示す指標 R を以法のような習慣・非習慣検出に利用する習慣抽出モデルとして

下のように定義する．

は，「月曜 8 時台」など曜日と時間帯の両方を考慮した習慣が抽R = wP RP + wP T D RP T D + wP D RP D + wP T RP T (1)

出できず，不十分な部分があった．提案手法では，曜日と時間帯の両方を考慮した習慣と，曜日・時間帯を考慮しない習慣を

第 1 項は曜日時間帯考慮なし習慣度，第 2 項は曜日時間帯考慮加えたモデル化により，柔軟な習慣度算出を実現する．

習慣度，第 3 項は曜日のみ考慮習慣度，第 4 項は時間帯のみ考提案モデルでは，個人 (P :Personal) の周期的習慣を検出す

慮習慣度を表す．各習慣度の算出方法は以下の通りである．

る．曜日・時間帯ともに考慮なしの習慣，曜日・1 時間刻みのM UP T D − µ
M UP − µ, RP T D =,σPσP T D
M UP D − µ
M UP T − µ
RP D =, RP T =
σP D
σP T

RP =

時間帯両方を 24 × 7 = 168 次元の 1 週間単位で考慮した習慣(T D:Time, Day of the week)，曜日のみを考慮した習慣 (D)，時間帯のみを考慮した習慣 (T ) の 4 種類を，それぞれ多項分布(M U :Multinomial) を用いて以下のように表す．



M UP : P (l|u) = Cl,u /

∑
l

Cl,u

M UP T D : P (l|t, d, u) = Cl,t,d,u /∑外れ値検定の際に一般的に使用される尺度を参照した．ここで，

式 (2) で算出される各習慣度の値について，習慣度が負の値を取る際にも，値が大きいほど習慣度が高くなるようにするため

Cl,t,d,uに，R <= 0 の場合のみ以下のような補正を実施する．

∑
Cl,d,u∑ll

M UP D : P (l|d, u) = Cl,d,u /M UP T : P (l|t, u) = Cl,t,u /lCl,t,u(2)



RP X ← −RP X − 1.0 (if RP X <
= 0)

(3)

Cl は場所 l におけるチェックイン回数 (Count)，すなわちログ数

RP X は式 (2) で算出される 4 種類の習慣度をまとめて表現しを示す．t, d, u は表 3 の通りである．例えば Cl,t,d,u では，ユーたものである．補正を行う理由の詳細は後述する．µ は頻度分

く，負の場合は値が大きいほど習慣度が低くなり，値の大小関
頻度分布A

頻度分布B

1

1

場所毎の
訪問頻度
分布
MUPT

訪
問 0.5
確
率 0

習慣度
R PT

習慣度高 場所2,10 : 0.32…
場所10 : 0.89…
場所3,5,7,9 : -0.78… 習慣度低 場所1,3-9 : -0.84…

図3

= . ,

≅ .

= . ,

訪
問 0.5
確
率 0

1 2 3 4 5 6 7 8 9 10場所

≅ .

のみ大小関係を反転させることで，値の正負に関わらず，値が1 2 3 4 5 6 7 8 9 10
場所

習慣度中
習慣度低

習慣度算出の例（時間帯のみ考慮習慣度 RPT の算出例）

布の平均を示す．σP , σP T D , σP D , σP T は，それぞれ頻度分布

M UP , M UP T D , M UP D , M UP T の標準偏差を示す．式 (2) の各式を M UP X (4 種類の周期的習慣をまとめた表現) について解くと M UP X = RP X σP X + µ となる．習慣度 RP X は，平均 µ から M UP X が標準偏差 σP X の RP X 倍離れていることを示し，分布内でどれくらい突出しているかを表す．習慣度が大きいほど R, RP X は大きい値を取る．
本手法では学習データ中に含まれる全場所に対する頻度分布を考える．該当時間帯に本人のログが 1 つも存在しない場所への訪問確率も定義され，その確率は全て 0 となる．全場所への訪問確率の和が 1 であることから，頻度分布の平均 µ は，全場
所数を |L| とするとユーザ・時間帯に関わらず全て 1/|L| となる．標準偏差 σ の値や習慣度の正負を決める µ を，全ユーザに共通な全場所への頻度分布から算出したのは，習慣度の大小を複数ユーザ間で比較することも想定したためである．M UP Xの確率が非常に小さく 1/|L| 未満の場合，各習慣度 RP X は負の値を取る．これは習慣度が特に低い状態と捉えられる．
習慣度の算出例
習慣度算出の例を図 3 にしめす．ユーザの特定時間帯における頻度分布 M UP T を表す 2 つの頻度分布 A,B から，時間帯のみ考慮習慣度 RP T を算出する例を考える．全場所数は 10 である．訪問確率 > 0 の場所にいた場合，習慣度算出では，そのログで訪問されている場所へのその時間帯における訪問確率が突出しているかを調べる．従って，訪問確率がともに 0.5 である場所 10 にいた場合，同確率で場所 2 にいる可能性もある頻度分布 B よりも，頻度分布 A の方が習慣度は高くなる．
一方，訪問確率が 0 の場所にいた場合，習慣度は負の値を取る．|L| は全員分のログに記載されている全場所数の合計となるため，手元のデータでも 100,000 など非常に大きい値となる∑ことが多く，

l

係が正負により異なる．そこで，式 (3) により，値が負の場合

Cl,u << |L| であるためである．本人の訪問

が 1 度でもあれば式 (2) で算出される RP T が RP T > 0 となる．一方，1 度も訪問がない場合には，RP T <= 0 となり，その時間帯における頻度分布のばらつきが B のように大きいほど習慣度は小さくなる．分布 B ではその時間帯にいる可能性がある

大きいほど習慣度が高くなるよう補正を行う．提案する習慣度
指標ではその時間帯におけるログが存在しない非習慣状態に対しても，頻度分布の分散に応じて異なる習慣度を出力できる．
各習慣度を足し合わせる重みについてそれぞれの習慣度を足し合わせる重みは，該当時間刻みにおけるログ数を考慮して以下のように求める．

wP = 1.0, wP T D =Ct,d,u,max Ct,d,u
t,d

Cd,u
Ct,u
wP D =, wP T =max Cd,umax Ct,ud(4)t

式 (4) の分母について，例えば maxt,d Ct,d,u は最もチェックイ
ン回数が多い曜日・時間帯（月曜 8 時台など）のチェックイン
回数を示す．重み w を導入することにより，例えば M UP T D
で，学習データ中の予測したい曜日・時間帯のログが他の曜日・時間帯に比べて少ない場合には，M UP T D の考慮比率を下げることが可能になる．maxt,d Ct,d,u = 120 のユーザの wP T D
を考える．[Case1:該当曜日・時間帯に場所 A へのログ 1 回のみがある場合]，場所 A の訪問確率が 100%で，それ以外の場
所への訪問確率は 0%の頻度分布が作成される．一方，[Case2:
該当曜日・時間帯に 100 回分のログがあり，そのうち 100 回
全てが場所 A への訪問の場合] も確率頻度分布は同様になる．
場所 A への訪問確率は同じだが，式 (4) を用いると，[Case1]
では wP T D = 1/120，[Case2] では wP T D = 100/120 となり，[Case1] の方が M UP T D の考慮比重が低くなる．母集団となる
ログ数が多い [Case2] の方が，習慣として信頼度が高いと考えられるため，習慣抽出時に母集団となるログが少なかった場合
は，その周期的習慣の考慮比率を下げて習慣度の足し合わせを実施する．4 種類の多項分布の重み付き線形和により，行動パ
ターンが必ずしも一定ではないユーザの習慣も表現できる．

4. 評価と考察
習慣度算出手法及び習慣抽出モデルの評価を行う．3. 1 節で示したデータを用いた．実験設定として，100 ログ以上ある
ユーザについて，各ユーザのログのうち 80%を学習データ，残り 20%をテストデータとした．100 ログ未満のユーザのログは
全て学習データとした．100 ログ以上のユーザは Gowalla では

109 人，Brightkite では 671 人であった．同一ユーザの同一時間帯におけるの同場所への連続的な訪問は，初回のみを残した．

場所が少数であるのに対し，分布 A ではその時間にいる可能性

4. 1 習慣度算出手法の定性的評価がある場所が 6 箇所あり曖昧なため，未訪問の場所にいる場合

テストデータ中の各ログの習慣度を算出し，場所毎に全ユーの習慣度は頻度分布 A の方が若干高くなる．

ザによる習慣度を平均した結果，習慣度が特に高かった場所と各習慣度の補正について低かった場所を図 4 に示す．習慣性が高いと予想されるオフィ

式 (2) の各習慣度の最小値は −1.0 程度であるのに対し，最スや住宅，低いと予想されるイベント会場や観光地がそれぞれ

大値は場所数に応じて変化する．場所数が 100,000 個程度の実抽出された．図中の括弧内の数字は，学習データにおけるログ験で，最大値はユーザによっては 1,000 を超えた．式 (2) で算数を示す．必ずしも訪問回数の大小だけで習慣度が決定されて出される値は，習慣度が正の場合は値が大きいほど習慣度が高いないことが分かる．

Gowalla

Brightkite

習慣
非習慣

田町(258), 品川(365),
大崎(169), 青山(19),
オフィス 区役所(83), 品川(81)ミッドタウンオフィス(168)鶴見(205), 大宮(184), 戸塚(72),
練馬(321), 三鷹(359), 川口(186),
住宅地 経堂(82), 茅ヶ崎(211)
茅ヶ崎(124), 新習志野(53)新木場(10), 国際展示場(1),イベント 幕張(12)幕張(11)
羽田空港(48), 成田空港(68),
新横浜駅(39)

空港、 成田空港ゲート(66),
新幹線 成田空港ビル(27), 新横浜駅(42)

舞浜(13), 京都(67), 中華街(7),六本木ヒルズ(56), 竹下通り(8)

観光地 六本木ヒルズ(18), 科学未来館(6),京都(16), 富士山(13), お台場(101),
ミッドタウン広場(3)

図4

場所毎に全ユーザで平均した習慣度

図 6 1 ユーザの習慣度算出結果の変遷＜周期性学習結果＞
MUPTD
0.3
訪 0.2
問 0.1
確
0

MUPD

0.2

MUPT

0.1

0.05

0

0

1
22
43
64
85
106
127
148

率

0.1

1234567

1 7 1319

曜日

時間帯

曜日×時間帯＜周期性学習パラメータ別の習慣度変遷＞
図 5 1 ユーザの習慣度算出結果（場所毎平均）

1 ユーザで場所毎に平均した習慣度
図 5 は Gowalla の 1 ユーザのテストログに対して，場所毎に平均した習慣度を，緯度経度情報を参照して配置したものである．ログ数が多いユーザのうち，RP と RPT D の差が大きいユーザを選出した．個人情報の保護のため，背景に地図を載せることは避けた．図中の線は一部の鉄道を示す．赤色に近いほど非習慣状態，紫色に近いほど習慣状態を示す．赤色は習慣
度が負の場合，残りの 8 色は習慣度が正のものについて，値の大小で 8 等分した．図中 a,b のように習慣度の高い紫色が集中している場所の周辺にも，習慣度が低い橙色などが見られる．

1回目
2回目
3回目
4回目
5回目
6回目
7回目
8回目
9回目
10回目
11回目
12回目
13回目
14回目
15回目
16回目
17回目
18回目
19回目

day hour 習慣度
金
21 115.37
土
22 79.68
日
22 81.84
月
20 175.91
火
20 160.71
水
21 111.77
木
22 71.91
金
20 146.91
土
19 90.11
月
21 121.85
火
22 76.17
水
21 111.77
木
21 107.6
金20 146.91
土
21 89.28
日
15 67.47
月
20 175.91
火
20 160.71
水20 165.01

200
180
160
140
習120
100
慣 80
度 60
40
20
0
-20

1 3 5 7 9 11 13 15 17 19

訪問 （回目）allR

P-MultR

R
PTW-mult

PW-mult
R

PT-MultR

図 7 1 ユーザの特定場所への習慣度変遷

頻繁に訪問する場所からの距離が遠いほど非習慣とする従来の方法では検出できない非習慣が検出できた．

し，1 日の中を 1 時間ずつ 24 分割して描画位置を決定した．縦図の下部分は a の周辺を拡大したものである．吹き出し中

軸は場所を表す．テストデータに登場した順に，下から表示をの括弧内の数字は，学習データ中の訪問回数である．駅や予備割り当てた．最下段には全場所における習慣度の変遷をまとめ

校の習慣度が最も高く，ハンバーガー店やコンビニの習慣度がて表示した． 桃色の矩形で囲まれた場所（予備校）を見ると，次いで高い．一方，同じハンバーガー店でも習慣度が低いもの

ほぼ毎日訪問しているものの，その習慣度には微妙な変化があも見られ，非習慣的にこのハンバーガー店や牛丼店，ラーメンることが分かる．この予備校における周期性習慣の抽出結果と，店を訪問していることが分かる．習慣度の値を詳細に観察する

各訪問における習慣度変遷の詳細を図 7 にまとめた．比較的習と，必ずしも学習データ中の訪問回数が多いほど習慣度が高く

慣度の低い 2 回目 (2 日目)，3 回目 (3 日目)，11 回目 (12 日目)

はなっておらず，訪問時期が不規則なスーパーに比べ，訪問時

は訪問時間帯や曜日が習慣と異なるため，習慣度が低いことが期が規則的な飲食店の方が平均習慣度が高いことが分かった．

分かる．例えば 11 回目の訪問は従来よりも遅い時間に予備校

1 ユーザのログ毎の習慣度変遷にいた事例であると考えられる．この後の訪問を調べると，非図 6 は同じユーザの 21 日分のテストデータの習慣度変遷を習慣的にラーメン店を訪問していることが分かった．帰りが遅時系列に沿って可視化したものである．横軸の点線は日付を示れたため，普段あまり利用しない飲食店で食事をしたと考えら

れる．11 回目の訪問だけでなく，図 6 で楕円で囲まれているよ
うに，いつも訪れている場所への訪問にも関わらず訪問時間帯
が非習慣的だった場合，その前後にも非習慣行動が続きやすい
ことが可視化結果から分かる．このような非習慣行動を続けているタイミングで，本人履歴がない，新規性・意外性の高い飲食店を推薦するなどといった情報配信への活用が考えられる．

4. 2 習慣度算出手法の定量的評価
連続ログ間の習慣度持続性に関する分析

1 章において，(1) 配信直前の行動における習慣度が，直後の図 8 連続ログ間の習慣度変化

行動でも持続しやすく，直前の習慣度により配信タイミングを決定できるという習慣度の要件を設定した．遷移時間が 2 時間
以内で連続している 2 ログ間の習慣度差を算出し，閾値以下であった割合を求めたところ，Gowalla で 73.2%，Brightkite で81.2%であった．全ユーザの習慣度の (最大値 − 最小値) × 0.1
を閾値とした．同一ユーザの任意のログ間について同様に習慣度差を算出した場合，閾値以下であった割合は Gowalla で

図 9 場所毎の平均習慣度と習慣度のばらつきの関係

55.8%，Brightkite で 52.9%であり，2 時間以内に連続するロ
グでは，任意のログ間に比べ，習慣度差が小さいことが分かっ

度の差を平均したところ，Gowalla で-3.35，Brightkite で-8.11

た．従って，直前の行動ログの習慣度による配信タイミングのであった．習慣度差の平均が負の値を取るということは，非習決定が有効であると考えられる．

慣状態（習慣度は小さい）から習慣状態（習慣度は大きい）へ

連続ログ間における習慣度変化の相関分析の変化が少ないことを示す．特に習慣度が低い時に，本人履歴

習慣度と配信内容の相関を詳細に調べるために，2 時間以にない場所を推薦することが有効であると考えられる．

内に連続する 2 ログ間の習慣度変化について相関分析を行っ以上の分析から，直前の行動の習慣度と，次の行動の習慣度

た．n − 1 番目のログにおける習慣度 Rn−1 と n 番目のログには一定の相関があり，特に非習慣行動時には，非習慣行動をにおける習慣度 Rn の関係を分析した．相関分析では，2 つの続ける可能性が高いため，他人の履歴を利用した情報配信を行

確率変数 x,y 間の相互依存性を分析し，2 変数間にどの程度直うことが有効な可能性があることが示された．直前の行動の習線的な関係があるかを示す相関係数の値を求める．相関係数

慣度を，情報配信における配信タイミングとその内容決定に活

は

∑n

i=1

(xi − x)(yi − y)/

√∑n

i=1

(xi − x)2

√∑n

i=1

(yi − y)2

用できると期待される．

で求められ，-1 から 1 の間の実数値を取る．1 に近い場合に場所毎の習慣度のばらつきについては 2 変数間に正の相関があることを，-1 に近い場合には負の1 章において，(2) 同一場所は複数ユーザから同等の習慣度で相関があることを示す．ここで，x，y はそれぞれ，x = {xi }，訪問されやすいという習慣度の要件を設定した．特に非習慣状

y = {yi } の相加平均である．R の値が大きい場合，小さい場

態にあるユーザに対して，同等の習慣度を持つ他人のログを考合両方について分析を行うため，R + ϵ の常用対数を取った値慮することが考えられる．ここでは，あるユーザに非習慣的にを用いた．習慣度は最小値が-1.0 である 4 種類の習慣度の線形訪問される場所が，他のユーザからも同等の習慣度で訪問され和であったことから，ϵ = 4.0 とした．Rn−1 と Rn の関係をやすいかどうかを検証する．3 ユーザ以上から訪問されている

図 8 に示す．Gowalla，Brightkite の相関係数はそれぞれ 0.60，

場所への訪問を抽出した上で，各場所の習慣度平均と習慣度の0.72 であり，ともに正の相関が見られた．直前，直後の習慣

ばらつき（標準偏差）の関係を分析した（図 9）．図中の横軸に度がともに負となった領域に限定して相関係数を算出すると，平行な太線は，抽出したログ全体の標準偏差を示す．Gowalla,

Gowalla で 0.87，Brightkite で 0.72 となり，特に Gowalla で

Brightkite ともに，全ログの標準偏差に比べて，同一の場所で強い相関関係があることが分かった．偶然このような相関関係

はばらつきが少ない．また，特に平均習慣度が低い場所についが観測される確率を示す P 値は，すべて 2.2e-16 未満と十分にて，標準偏差も小さい傾向があることが分かり，非習慣状態に小さい値であった．提案手法では，習慣度が負になる場合につおいて，同等の習慣度で訪問されやすい場所を提示することがいても，その時間帯の分布のばらつきから習慣度を変化させて有効であると考えられる．

いるが，その定義が効果的であることが示された．
連続ログ間の習慣度変化の平均値による分析

4. 3 習慣抽出モデルの定量的評価
Step2 の習慣度算出時に，時間帯や曜日の考慮有無に応じて，直前の行動の習慣度と直後の行動の習慣度の関係について，

4 つの習慣を重みづけして足し合わせた．この組み合わせの効4. 1 節において，1 人のユーザの習慣度変遷の定性的評価によ果を検証する．式 (4) と同様の重み付けで 4 つの習慣を組みり，特に非習慣行動を行っている際に，続けて非習慣行動を行合わせた頻度分布を用いた行動予測精度評価により検証する．

う場合があることが示唆された．これについて，統計的な検証

Step2 の習慣度算出時と同様に，Step1 で抽出した 4 種類の習を実施する．移動時間が 2 時間以内で連続する 2 ログ間の習慣

慣を組み合わせた M UP ALL を以下のように求める．重み w
bは式 (4) と同様に求めるが，全場所への訪問確率の和を 1 にする

表 5 習慣を利用した行動予測精度結果
モデル

ために，w
bP + wbP T D + w
bP D + w
bP T = 1.0 とする．

GowallaBrightkite

p@5

p@1

p@5

p@1

(a) M UP

29.6

10.9

40.6

22.0

(b) M UP T D

28.8

12.2

35.1

21.0

(c) M UP D

28.0

10.5

38.0

22.0

(d) M UP T

32.4

14.0

40.1

23.0

(e) M UP ALL

33.2

14.3

40.8

23.8

(f) 0.3M UP ALL + 0.7M MGP

39.9

20.0

48.8

34.1

番目の場所 ln+1 への行きやすさを表す遷移確率が有効である(g) M UP D × M UP T × M MP (Gao ら）

29.6

17.1

33.4

24.8

と示されており，Gao らの手法でも個人ログから抽出した遷移(h) M UP ALL × M MP (参考）

30.6

17.8

34.5

26.4

M UP ALL = w
bP M UP + w
bP T D M UP T D+ w
bP D M UP D + w
bP T M UP T

(5)

位置情報に基づく行動予測では，定食屋 A に来た人は，その後カフェB へ行くことが多いなど，n 番目の場所 ln から n + 1

習慣と周期的習慣を掛け合わせた確率を算出する．そこで，提
4.00
3.50

案手法においても，周期的習慣に加え，遷移習慣を考慮する．

GowallaBrightkite

占 3.00有 2.50率 2.001.50

ここでは，各場所から各場所への遷移確率を算出し，個人だけ[% 1.00]

でなく，全ユーザ (G:Global) についてもそれぞれ遷移習慣を

0.50
0.00

MUPTD
MUP
MUPD
MUPT

抽出する．これは，本人の習慣に従わない行動をしている際に，全体の遷移習慣を合わせて利用すると，行動予測精度が向上する可能性があると考えられるためである．遷移習慣は一次マル

○

×

×

×

○

○

○

×

×

×

×

○

○

○

×

○

×

×

○

×

×

○

○

×

○

×

○

○

×

×

○

×

×

○

×

○

×

○

○

○

×

○

×

×

×

○

×

× ○
× ○ ○
各モデルの正答/誤答

○

○

○

×

コフモデル (M M :Markov Model) により算出する．各遷移習
図 10

慣の抽出方法を以下に示す．M MGP では，ln を出発する本人の遷移履歴がある場合は M MP を，本人履歴はないが全体遷
移履歴のみがある場合は M MG を使い分ける．



M MP (個人遷移習慣): Pu (ln+1 |ln )M MGP =



では誤答だが，提案モデルで考慮に加えた M UP T D や M UP

では正答となったログが，全体の 3-4%存在することが分かる．
また，M UP T では正答になるが，M UP D では誤答になるログ

M MG (全体遷移習慣): P (ln+1 |ln ){各周期的習慣の予測性能比較

が 10%近くある．4 つの周期的習慣を適切に組み合わせること

M MP

(if

Pu (ln+1 |ln ) > 0)

M MG(else if

P (ln+1 |ln ) > 0)で，従来法では誤答となるログに対して正答できると期待される．図 10 において全てのモデルで正答だったものが Gowalla で



Gao らの手法では，周期的習慣と遷移習慣を独立と捉えて掛け合わせて用いていたが，掛け合わせを行うと，周期的習慣，
遷移習慣のどちらかが 0 に近い場合に，他方の確率が反映されないという問題がある．そこで，提案手法においては，M U に
よる訪問確率と M M による訪問確率の重み付き線形和で各場所への訪問確率を算出する．各習慣の重みは予測精度による検証から 0.3M U + 0.7M M とした．
予測するテストログの中には，非習慣行動のログも混在しているため，予測精度には限界があるが，習慣的行動の予測精度評価により，提案法による習慣抽出モデルがもたらす効果を定量的に評価できると期待される．テストデータ中の訪問の曜
日・時間帯と，1 つ前の訪問場所を与えた上で全場所への訪問確率を算出し，そのうち上位 5 個 (p@5) または 1 個 (p@1) を出力することで，正答率を計算する．すなわち，n + 1 番目の訪問場所 ln+1 を，P (ln+1 |ln , u, t′ , d′ ) が大きいものから k 個選
ぶ p@k 評価を行う．t′ , d′ はそれぞれ n+1 番目のログの時間
帯，曜日を示す．予測精度は正答回数/総予測回数で算出し，単位は%とする．総予測回数は Gowalla で 5,511 回，Brightkite
で 32,254 回であった．
表 5 に各習慣を利用した行動予測精度をしめす．4 つの習慣を組み合わせた (e) M UP ALL を用いることにより，各習慣を単独で利用する (a)-(d) に比べ，精度が向上することが分かった．

(a)-(d) の各周期的習慣の予測性能を比較したものを図 10 に18.38%，Brightkite で 29.03%あり，全モデルで誤答だったもの
が Gowalla で 57.83%，Brightkite で 52.04%であった．いずれ
かのモデルで正答できたものは Gowalla で 42.17%，Brightkite
で 47.96%であり，4 モデルの組み合わせ方法の改良により，最大でこの精度までの向上が期待できる．4 つの習慣を組み合わせて重み付き線形和を取る際の適切な重み w を，ユーザや時間に応じて学習させるなどの改良も考えられる．
本人と全ユーザの遷移習慣を組み合わせて利用した M MGPとの線形和を取った (f) を用いると，さらに精度が向上した．
曜日考慮習慣，時間帯考慮習慣，個人遷移習慣をそれぞれ独立と捉えて掛け合わせた Gao らのモデル (g) の精度を上回ってい
る．参考のために，提案した M UP ALL を周期的習慣として用いた上で，Gao らと同様に個人遷移習慣との掛け合わせを行った (h) を見ると，曜日・時間帯を独立と考えた Gao らの (g) よりも精度が高いことが分かり，遷移習慣との組み合わせ方法改良による効果を取り除いた場合においても，M UP ALL が有効であることが分かる．以上のように，4 つの習慣を組み合わせ
た M UP ALL は，単独で用いる場合，遷移習慣と組み合わせて用いる場合の両方において効果があり，習慣度算出においても，同様の組み合わせを行うことが有効であると考えられる．遷移
習慣の抽出方法，周期的習慣・遷移習慣の組み合わせ方法にも改良を加えることにより，Gao らの既存手法に比べて，p@5 で10%以上の精度向上が見られることが示せた．

示す．縦軸は総予測数に対する占有率を示す．左の 2 つの棒グラ

5. 提案手法を活用した情報配信の検討

フを見ると，Gao らの研究でも抽出していた M UP D ，M UP T

4. 2 節で示したように，連続する 2 ログ間の習慣度は正の相

無視することが可能になると期待される．また習慣の変容を考慮することにより，例えば A さんがある場所に 3 か月に一度訪問するという習慣がある場合に，1 年以上来なければ習慣が変容したとみなして習慣を更新するとともに，クーポン配布など何らかのアクションを行う，などの応用が考えられる．さらに，習慣度変化の状態遷移をモデル化することにより，人や場所に応じた確実性・意外性の考慮比率をより詳細に推定することも検討している．
文図 11

淡路夢舞台付近の習慣度平均

関を持つ場合がある．従って，情報配信を行う直前のログの習慣度を利用し，習慣度が高いほど本人の履歴を，習慣度が低いほど他人の履歴を強く考慮した情報配信が考えられる．本人の履歴を利用した情報配信では，4. 3 節で示した行動予測結果が活用できる．習慣度が低い場合には，本人の履歴ではなくジャンル情報などを活用することにより，本人の嗜好のみを反映することも考えられる．一方，他人の履歴を利用した情報配信について，4. 2 で述べたように，情報を配信したいユーザと同等の習慣度を持つ場所を推薦することが考えられる．一例として
図 11 は淡路島の淡路夢舞台付近における，全ユーザのログを用いた場所毎の習慣度平均を表す．例えば配信対象のユーザが(a) ウェスティンホテルを非習慣的に訪れている場合，比較的平均習慣度が高い (b) の広東料理店よりも，平均習慣度が低い(c) の淡路ハイウェイオアシスを推薦する方が適切である可能性がある．実際，(c) では淡路島のご当地料理の 1 つである鯛料理を食べることができ，非習慣的に訪れているユーザが満足する推薦結果となる可能性が高いと考えられる．提案手法では，ログが多くない場所においても，既に訪れたことがあるユーザのログから各場所の平均習慣度を算出することができ，それを配信対象のユーザの習慣度と関連付けて活用することができる．

6. まとめと今後の予定
位置情報ログを活用した情報配信の満足度向上に向け，ユー
ザ行動理解の指標として行動の「習慣度」を定義した．情報配信における習慣/非習慣状態推定の必要性とその要件を検討し，時間的特徴を考慮した習慣抽出モデルと，従来よりも詳細な行
動習慣度算出手法を提案した．加えて，チェックインログを用いた習慣度算出結果の定量的・定性的評価と情報配信への活用
例を示し，提案法の有用性を示した．
今後は，習慣抽出において，曜日・時間帯に対する 1 週間毎の周期的習慣だけでなく，1 週間という単位を取り払ったその他の周期的習慣や，習慣の変容を考慮していきたい．現在の手法では学習データに含まれる非習慣行動のログが大量に存在した場合，それらも習慣として学習してしまう可能性がある．習慣を 1 週間周期ではなく連続的に捉えることにより，短期間にしか存在しなかったログを非習慣として扱い，習慣抽出段階で

献[1] D. Ashbrook and T. Starner. Using gps to learn significant locations and predict movement across multiple users.
Personal and Ubiquitous Computing, 7(5):275–286, 2003.
[2] C. Cheng, H. Yang, I. King, and M. R. Lyu. Fused matrix factorization with geographical and social influence inlocation-based social networks. In AAAI, 2012.
[3] E. Cho, S. A. Myers, and J. Leskovec. Friendship and mobility: user movement in location-based social networks. In
Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pages
1082–1090. ACM, 2011.
[4] E. Davami and G. Sukthankar. Online learning of userspecific destination prediction models. HUMAN JOURNAL, 1(3):144–151, 2012.
[5] H. Gao, J. Tang, and H. Liu. Mobile location prediction in
spatio-temporal context. In Nokia Mobile Data Challenge
2012 Workshop. p. Dedicated task, volume 2, 2012.
[6] T. Kurashima, T. Iwata, T. Hoshide, N. Takaya, and K. Fujimura. Geo topic model: joint modeling of user’s activity
area and interests for location recommendation. In Proceedings of the sixth ACM international conference on Web
search and data mining, pages 375–384. ACM, 2013.
[7] T. Kurashima, T. Iwata, G. Irie, and K. Fujimura. Travel
route recommendation using geotags in photo sharing sites.
In Proceedings of the 19th ACM international conference on
Information and knowledge management, pages 579–588.
ACM, 2010.
[8] K. W.-T. Leung, D. L. Lee, and W.-C. Lee. Clr: a collaborative location recommendation framework based on coclustering. In Proceedings of SIGIR, pages 305–314, 2011.
[9] E. Malmi, T. M. T. Do, and D. Gatica-Perez. From
foursquare to my square: Learning check-in behavior frommultiple sources. 2013.
[10] A. Monreale, F. Pinelli, R. Trasarti, and F. Giannotti.
Wherenext: a location predictor on trajectory pattern mining. In Proceedings of the 15th ACM SIGKDD international
conference on Knowledge discovery and data mining, pages
637–646. ACM, 2009.
[11] B. Shaw, J. Shea, S. Sinha, and A. Hogue. Learning to rank
for spatiotemporal search. In Proceedings of the sixth ACM
international conference on Web search and data mining,
pages 717–726. ACM, 2013.
[12] Q. Yuan, G. Cong, Z. Ma, A. Sun, and N. M. Thalmann.
Time-aware point-of-interest recommendation. In Proceedings of the 36th international ACM SIGIR conference on
Research and development in information retrieval, pages
363–372. ACM, 2013.
[13] Y. Zheng, L. Zhang, X. Xie, and W.-Y. Ma. Mining interesting locations and travel sequences from gps trajectories. In
Proceedings of the 18th international conference on World
wide web, pages 791–800. ACM, 2009.
[14] D. Zhou, B. Wang, S. M. Rahimi, and X. Wang. A studyof recommending locations on location-based social networkby collaborative filtering. In Advances in Artificial Intelligence, pages 255–266. Springer, 2012.