DEIM Forum 2016 F8-5

ユーザの嗜好の保存度合いを考慮した
位置プライバシ保護のためのダミー生成手法とその評価
水野

聖也†

原

隆浩†

Xing

Xie††

† 大阪大学情報科学研究科†† Microsoft Research Asia
E-mail: †{mizuno.seiya,hara}@ist.osaka-u.ac.jp, ††xing.xie@microsoft.com
あらまし

位置情報サービスでは，ユーザの位置情報をサービスプロバイダに送信するという性質から，プライバシに関する問題が指摘されている．その一方で，ユーザの嗜好情報に基づいてサービスのパーソナライズを行うなど，ユーザの要求するプライバシ基準を満たす範囲内で嗜好情報を活用するための研究も盛んに行われている．そこで，筆者らは，先行研究において，位置情報サービスにおけるユーザのプライバシを保護しつつ，嗜好情報の活用を可能とすることを目的として，ユーザの嗜好情報の保存度合いをユーザの要求に応じて制御可能なダミー生成手法を提案した．本稿では，FourSquare のデータセットを用いて，東京 23 区の地図上でこの提案手法をシミュレートし，嗜好の保存度合いの制御可能性およびプライバシ保護性の評価を行った．
キーワード

位置プライバシ，嗜好の保存

1. は じ め にGPS を搭載した端末の普及に伴い，位置情報サービスが数多く展開されるようになった．位置情報サービスでは，自身のと異なる可能性が高い．これは，プライバシの観点から嗜好情報も保護したいユーザには望ましい性質であるが，嗜好情報を公開することでパーソナライズされたサービスを受けたいユー
ザには，サービスの質を低下させる要因となる．

位置情報をサービスプロバイダに送信することにより，送信し筆者らは，先行研究において，訪問場所の意味情報の系列でた位置情報に対応したサービスが受けられる．しかし，その位あるカテゴリシーケンスのサポートをユーザの嗜好と定義し，置情報の管理はサービスプロバイダに委ねられるため，サービ

この嗜好の保存度をユーザの要求に応じて制御可能なダミー生

スプロバイダが攻撃を受けたり，サービスプロバイダ自身によ成手法を提案した [11]．本稿では，この提案手法の有効性を確る営利目的のデータの売買によって第三者に位置情報が露見し，認するため，シミュレーションによる評価実験を行った．

ユーザの位置プライバシが侵害される危険性が指摘されている．

以下では，2 章で関連研究を説明し，3 章で文献 [11] で提案

一方で，ユーザの嗜好に基づくサービスのパーソナライズ等，した手法の概要について述べる．4 章で本稿で行った評価につ

情報活用も重要視されるようになりつつある．それを受けてプ
ライバシ保護の分野でも，ユーザの要求するプライバシ水準を満たす範囲内で可能な限り多くの情報を公開し，サービスの質

いて述べ，最後に 5 章でまとめと今後の課題を述べる．

2. 関 連 研 究や，データ分析への利用可能性の向上につなげようとする動き

2. 1 ダミーを用いた位置曖昧化手法が活発になった [2] [3]．位置情報サービスにおいても，サービス

文献 [5] [9] [10] では，ダミーを用いた位置曖昧化手法が提案

利用履歴に基づくスポットの推薦などの研究が盛んに行われてされている．この手法では，ユーザはダミーの位置情報を複数おり，情報活用も考慮した位置プライバシ保護手法が望まれる．

生成し，自身の位置情報とともにサービスプロバイダに送信す

位置プライバシ保護を目的とした研究の一つとして，ダミー

る．ユーザは，送信した全ての位置情報に対する応答を受信すを用いた位置曖昧化手法がある．この手法では，ユーザがサーるが，その中から自身の位置に対する応答のみを選択すること

ビスプロバイダに位置情報を送信する際に，ユーザの実際の位により，自身の位置が特定されることを防止しつつ，サービス

置情報とともに，偽の位置情報であるダミーの位置情報を複数を受けることが可能となる．しかし，文献 [5] [9] で提案されて送信する．これにより，サービスプロバイダは，送信された情いる手法では，ダミーを生成する際にユーザの嗜好を考慮して報の中から実際のユーザの位置情報を一意に特定することがいないため，サービスプロバイダから観測可能なダミーとユー

困難になり，ユーザの位置が曖昧化される．しかし，従来のダザが混在した位置情報系列から計算できる嗜好情報は，ユーザ

ミーを用いた位置曖昧化手法の多くでは，ダミー生成の際に本来のものとは異なってしまう．これは，嗜好情報もプライバ

ユーザの嗜好を考慮していないため，ダミーがユーザと異なるシの観点から保護したいユーザには有用な性質であるが，嗜好

訪問傾向を示す．そのため，サービスプロバイダが観測可能な情報を公開してパーソナライズされたサービスを受けたいユー

情報であるユーザとダミーが混在した位置情報系列から抽出さザには，サービスの質を低下させる要因となる．

れる嗜好 (可観測な嗜好) は，本来のユーザの嗜好 (真の嗜好)

文献 [10] では，訪問場所のカテゴリ情報を考慮し，ユーザの訪問履歴中で頻出するパターンに従ってダミーを遷移させることでユーザとダミーの判別を困難にし，ユーザの訪問場所の傾向を知っている攻撃者に対して効果的にユーザの位置情報を曖
昧化する手法を提案している．この手法では，頻出パターンに従ってダミーを動作させるため，嗜好情報はある程度保存されると考えられるが，その度合いを制御することは難しい．
そこで筆者らは，文献 [11] において，嗜好の保存度をユーザの要求に応じて制御するためのダミー生成手法を提案した．こ

図1

匿名領域

図2

追跡可能性

の手法では，ユーザの嗜好を保存するダミーとユーザの嗜好と異なるダミーを，ユーザの要求する嗜好の保存度に応じた割合で混合することにより，嗜好の保存度の制御を試みる．

2. 2 位置情報を用いたパーソナライズに関する研究
近年，ユーザの位置情報を用いたサービスのパーソナライズ
に関する研究が盛んに行われている [1] [4] [8]．これらの研究では，各訪問場所への訪問回数に関するユーザ間の類似度に基づいた協調フィルタリングが用いられている．この際，各訪問場
所に対する訪問回数は，ユーザによって偏りが大きく，ユーザ間での共通部分が小さくなってしまうため，訪問場所の意味情

3. 2 実環境でダミーを生成する際に考慮している制約報であるカテゴリに訪問回数をマッピングしている．例えば，

連続的なサービス利用では，サービス利用間のダミーの位置

文献 [1] では，各訪問場所の訪問回数をカテゴリ毎に集計した関係において，その時間における地理的な到達可能性を考慮すものをユーザの嗜好としている．文献 [8] では，ある時点のサーる必要がある．例えば，あるユーザが一度サービスを利用してビス利用が，それ以前のサービス利用に基づき決定されるといから三分後に再度サービスを利用する場合に，直前のサービス

う想定のもと，訪問場所のカテゴリの遷移シーケンスをユーザにおけるどのエンティティ(ダミーおよびユーザを表す) の位置の嗜好としている．

からも三分以内に到達できない場所にダミーを配置しても，そこのような推薦を行うには，ユーザ間の類似度を計算するたれがダミーであると容易に特定されてしまう．そのため先行研めにカテゴリレベルでの情報のみを公開すれば十分である．ま究 [11] では，各サービス利用において，直前のサービス利用時

た，各カテゴリの訪問回数は，そのカテゴリを含むシーケンスの位置から到達可能な位置にダミーを配置している．

の発生回数の和として再現可能であるため，シーケンスを用い

3. 3 位置プライバシに関する要求

た嗜好モデルの方が汎用性が高い．

3. 3. 1 匿 名 領 域

そこで筆者らは，先行研究 [11] において，訪問場所のカテゴ

ユーザの位置プライバシを保護するためには，ダミーを識別

リシーケンスの発生率であるサポート (支持度) をユーザの嗜できないことだけではなく，どの程度の大きさの領域に位置情好と定義し，嗜好の保存度をユーザの要求に応じて制御するた報が曖昧化されているかも重要である．例えば図 1(a) のようめのダミー生成手法を提案した．

に，ダミーをユーザの周りに密集して配置した場合，ユーザが存在する可能性のある領域が絞り込めてしまう．ユーザの位置

3. 先行研究 [11] で提案した手法の概要を十分に曖昧化するには，図 1(b) のように広範囲に分散して本章では，先行研究 [11] における想定環境とダミー生成時にダミーを配置する必要がある．そこで先行研究 [11] では，Lu考慮している制約，プライバシ要求およびユーザの嗜好モデル

ら [5] の定義に基づき，ユーザとダミーで形成される凸包領域について説明し，提案したダミー生成手法の概要を述べる．

を匿名領域と定義し，この大きさがユーザの要求を達成できる

3. 1 想 定 環 境
先行研究 [11] では，チェックイン型の位置情報サービスを想ようにダミーを配置している．

3. 3. 2 追跡可能性

定している．そのためユーザの行動には，いくつかの訪問場所

短時間で連続的にサービス利用を行う場合，追跡可能性に対を訪問しながら移動する行動モデルを想定する．ユーザは，目する配慮も必要である．例えば図 2(a) のように，あるサービ的の訪問場所に到着した際に，先行研究 [11] で提案したダミー

ス利用時刻におけるエンティティの位置から次のサービス利用

生成手法を用いて自身の位置情報を保護しながらサービス利用

時刻において到達可能な範囲に対応する位置情報が 1 つしかなを行う．その際，訪問場所で Tm 秒以上滞在し，その後また次い場合，特定のエンティティのサービス利用が追跡できてしまの訪問場所への移動を開始する．ユーザの移動は，歩行によるう．この性質を追跡可能性と呼ぶ．追跡可能性が高い場合，目ものとし，公共交通機関等の利用は想定しない．

撃等によりユーザが一度特定された場合に，前後のサービス利ユーザの端末は地図情報や，ユーザのサービス利用履歴を十

用もユーザのものであると特定されてしまう．そのため先行研分保持しており，道路，訪問場所，訪問場所のカテゴリ，自身

究 [11] では，図 2(b) のように同時刻に同じ場所を訪問させるの嗜好情報をすべて把握しているものとする．

(共有地点を設定する) ことにより交差を発生させ，連続的なP res(Tu , To ) が 1 に近いほど嗜好が保存されていることを表す．逆に累積誤差が大きいとこの値は 0 に近づき，嗜好のプラ
イバシが保護されている状態であることを表す．

3. 6 文献 [11] の提案手法の概要
文献 [11] の提案手法では，ユーザの行動プラン tj0 ，要求ダ
ミー数 n，要求匿名領域 Ar ，ユーザの真の嗜好 Tu ，可観測な嗜好 To ，および嗜好の要求保存度 α = [0, 1] に基づき，n 個分

図 3 ユーザの嗜好を表す木のダミーの行動スケジュールを生成する．ここで，ユーザの行
動プランおよびダミーの行動スケジュールは，i 回目のサービス

サービス利用の追跡を防止している．

利用における訪問場所 vi とその訪問時刻 ti の組 < vi , ti > の系

3. 4 嗜好の定義
ユーザの嗜好には，訪問場所の意味情報の系列であるカテゴ
リのシーケンスのサポート (支持度) を用い，それを図 3 のように木構造で表現する．この木構造において，各ノードは，根からそのノードに到達するまでに辿ったノードが保持するカテゴリを順に並べたカテゴリシーケンスに対応する．各ノードに付与された数値は，そのシーケンスのサポート値を表し，その値はユーザのサービス利用履歴に含まれる行動スケジュールの総数 Ntj と，その履歴中でのシーケンス S の発生度数 n(S) を用いて次式で計算される．

n(S)Sup(S) =Ntj(1)

ユーザはサービス利用時に，ダミーを含めた位置情報をサー
ビスプロバイダに送信するため，サービスプロバイダが観測可列である．この手法では，ユーザの嗜好の保存度を制御するため，生成する n 個のダミーを要求保存度 α に応じて，⌊αn⌋ 個と ⌈(1 − α)n⌉ 個の 2 つのグループに分割する．以降では，前者を Preserving グループ，後者を Obfuscating グループと呼ぶ．

Preserving グループのダミーは，ユーザの嗜好を保存するために，真の嗜好 Tu 中のカテゴリシーケンスに従って動作させる．Obfuscating グループのダミーは，ユーザの嗜好を考慮せずに動作させる．ダミーの生成では Preserving グループ，

Obfuscating グループの順で，各ダミーの行動スケジュールを1 つずつ確定させていく．この際，id = i のダミーの生成には，ユーザの行動プランおよび生成済みである id < i のダミーの行
動スケジュールを考慮する．

3. 6. 1 Preserving グループのダミーの生成手順

能な情報は，ユーザとダミーの位置情報系列が混在したものとPreserving グループのダミー生成では，(1) ユーザの嗜好のなる．サービスプロバイダは，この情報を観測することでユー保存と，(2) ユーザの嗜好を知っている攻撃者に対する追跡可ザの嗜好を計算する．以降では，ユーザとダミーの混在する位

能性低下のための効果的な交差の 2 つの観点を考慮し，ユーザ

置情報系列の履歴から計算される嗜好を可観測な嗜好と呼び，の真の嗜好 Tu に従うユーザらしいダミーを生成する．この際

To で表す．これに対し，ユーザのみの位置情報系列の履歴から

ダミーは，3. 2 節で述べた到達可能性の制約を満たす必要があ計算される嗜好を真の嗜好と呼び，Tu と表記する．

るため，シーケンスを一つ定めたとしても，そのシーケンスに観測可能な情報から To を計算するには，観測した位置情報

従う経路を地図上から容易に発見できるとは限らない．これらの系列から発生したカテゴリシーケンスを計上し，(1) 式によの点を考慮し，まず，ユーザの真の嗜好 Tu 中に含まれるすべりサポートを計算すればよい．ただしこの際，交差によって，てのシーケンス S とそのシーケンス上に設定する共有地点 SP

各エンティティのカテゴリシーケンスが一意に決定できない場の組 < S, SP > に対し，上記 2 つの観点からスコアリングを合が生じる．その場合，発生した可能性のある全てのシーケン行い，各シーケンスを発生させる優先度を決定する．その後，スに対して発生度数の期待値を計算し，その期待値を発生度数

地図情報を参照し，優先度の高いシーケンスからそのシーケンとして計上することで嗜好情報を更新する．

スに従う経路の生成を試行し，到達可能性の制約を満たしつつ，

3. 5 嗜好の保存度の定義

ユーザの要求匿名領域が可能な限り満たせる経路をダミーの移嗜好の保存度 P res(Tu , To ) は，可観測な嗜好 To が真の嗜好動経路として確定させる．ここで，共有地点 SP は，地点を共Tu の情報をどの程度保存しているかを表す指標として，次式有させる id = k の生成済みエンティティek とその設定時刻 tiで定義される．

の組 < ek , ti > である．以降では，これらの手順を説明する．

P res(Tu , To ) = 1 −1
2X|Supo (S) − Supu (S)|{S∈SSetu ∪SSett }(2)a ) カテゴリシーケンスのスコアリング
ダミーに従わせるカテゴリシーケンスを決定するため，ユー
ザの真の嗜好 Tu 中に含まれるすべてのシーケンス S とそのここで，SSetu は真の嗜好 Tu に含まれるすべてのシーケンス

シーケンス上に設定する共有地点 SP の組 < S, SP > に対し，の集合，SSeto は可観測な嗜好 To に含まれる全てのシーケン(1) ユーザの嗜好の保存と (2) ユーザの嗜好を知っている攻撃

スの集合，Supu (S) は真の嗜好 Tu におけるシーケンス S の者に対する追跡可能性低下の 2 つの観点から次式でスコアリン

サポート値，Supo (S) は可観測な嗜好 To におけるシーケンス

グを行う．

S のサポート値である．この式において第二項は，二つの嗜好

Scores (< S, SP >)の木に含まれるシーケンスのサポート値の累積誤差を表し，こ= βScorepref (S) + (1 − β)Scorecross (< S, SP >)の値が小さいほど P res(Tu , To ) の値は 1 に近づく．すなわち，(3)

果を表すスコアの一部として導入する．Sek を交差相手のエンティティek が従うカテゴリシーケンス，l をシーケンス S および Sek のシーケンス長，S (i,j) をシーケンス S の i 番目の要素
から j 番目の要素までのサブシーケンス，{S1 , S2 } を シーケン
ス S1 の末尾にシーケンス S2 を結合したシーケンスを表すものとしたとき，distro < S, SP > は次のように計算できる．
(1,i)

Supu (S) + Supu ({Sek , S (i+1,l) }),Supsum(5)= Sup (S) + Sup ({S (1,i) , S (i+1,l) })distro(< S, SP >) =図4

Supsum嗜好を知っている攻撃者に対する交差の効果

u

u

ek

+ Supu (Sek ) + Supu ({S (1,i) , Se(i+1,l)})k
交差を設定する際には，交差回数が時刻間で均一になることが望ましい．これは，同時刻に集中して交差が発生した場合に，ダミーとユーザが密集することによって，匿名領域が小さくなるためである．また，ユーザに集中して交差を設定した場合，交差回数が他のエンティティと比べて多いものがユーザであると容易に特定されてしまう．そのため，特定のエンティティに交差が集中することを防ぎ，エンティティ間の交差回数についても均一化を図る必要がある．

図5

嗜好の保存が阻害される交差と阻害されない交差

交差が発生した場合，サービスプロバイダはそれらの発生した
期待度数を計上することによって，可観測な嗜好 To を計算する．

ここで，Scorepref は嗜好の保存のためのスコア，Scorecross

そのため，上記だけでは，ユーザの嗜好の保存を阻害する交差をは追跡可能性低下のためのスコアであり，β = [0, 1] は，両ス発生させてしまう可能性がある．例えば，図 5(a) のように，共有コアの重みを決定するパラメータである．本稿では，事前実験地点までのシーケンスが異なるような共有地点を設定した場合，に基づき，この値を β = 0.25 と定めた．

サービスプロバイダによってシーケンスは，Caf e → Gym →（ 1 ） 嗜好の保存のためのスコア Scorepref

Caf e → BookStore，Caf e → Gym → Library → Gym，

シーケンス S のシーケンス長を l，SSetu,l をユーザの真の嗜

BookStore → Gym → Caf e → BookStore，BookStore →好 Tu 中に含まれる長さ l のシーケンスの集合としたとき，シー

Gym → Library → Gym が，それぞれ 0.5 回ずつ発生したもの

ケンス S の嗜好の保存に対する効果を表すスコア Scorepref (S)と計上され，本来のダミーによって生成されたシーケンスであるは次式で表される．
Scorepref (S) =BookStore → Gym → Library → Gym というシーケンスのSupu (S) − Supo (S)max {Supu (Sj ) − Supo (Sj )}(4)

Sj ∈SSetu,l

発生度数が，BookStore → Gym → Caf e → BookStore という意図しないシーケンスに分散してしまう．これを防ぐには，図

この式において，分子は真の嗜好に対する可観測な嗜好におけ5(b) のように，共有地点を設定する時刻までのシーケンスが同るサポート値の不足を表し，分母はそれを正規化するための項

一となるようにする必要がある．これにより Caf e → Gym →である．これにより，2 つの嗜好の差分を埋められるシーケンス

Library → Gym，Caf e → Gym → Caf e → BookStore とが優先的に選択されるため，嗜好の保存度の向上が見込まれる．

いうダミーとユーザによって本来生成されていたシーケンスが（ 2 ） 追跡可能性低下のためのスコア Scorecross

1 度ずつ発生したと計上されるようになり，嗜好の保存度の制

ユーザの真の嗜好 Tu を知っている攻撃者に対しては，単純に交差を多く発生させるだけでは追跡可能性を十分に低下させられない．例えば，ユーザの真の嗜好 Tu を図 3 のものとした
とき，図 4(a) のようにダミーをユーザの真の嗜好 Tu 中に含まれないサポート値が 0 であるシーケンスで交差させたとしても，サポート値が 0.05 であるシーケンスに従って移動している位
置情報がユーザのものであると容易に特定されてしまう．そのため，嗜好を知っている攻撃者に対して効果的に追跡可能性を御可能性の向上が見込まれる．
以上を考慮して，嗜好を知っている攻撃者に対する交差の効
果を表すスコア Scorecross を次式で定義する．
δ · distro(< S, SP >),Scorecross (< S, SP >) =1 + n3sh (ek ) + n2sh (ti )1 (S (1,i) = Se(1,i) )kδ=0 (otherwise)(6)低下させるには，ダミーを図 4(b) のように，サポート値の高nsh (ek ) はエンティティek に設定済みの共有地点数，nsh (ti ) は

いシーケンスに従わせた上で交差させる必要がある．

時刻 ti に共有地点を設定済みのエンティティ数を表す．

ここで，あるエンティティの位置情報がユーザのものであるb ) 経路の決定方法

確率をユーザ確率と定義し，交差発生時に期待されるダミーに

スコアリングによって決定したシーケンス S と共有地点 SP

対するユーザ確率の配分 distro(< S, SP >) を考え，交差の効を基に，地図情報を参照し，到達可能性の制約を満たすダミー表1

シミュレーションにおけるパラメータ

4. 評 価 実 験

パラメータ

値

領域 [m2 ]4000 × 14000

交差点数325946

訪問場所数278153

訪問場所のカテゴリ数

10

サービス利用間隔 [s][480, 720]

ミュレーションにおける各パラメータを表 1 に示す．訪問場

歩行速度 [km/h][4.0, 6.0]

所には，FourSquare API（注 1） を用いて取得した Venue を用い

先 行 研 究 [11] の 提 案 手 法 の 有 効 性 を 検 証 す る た め ，FourSquare のデータセットを用いて，東京 23 区の地図上で実際のユーザのサービス利用を再現し，評価実験を行った．シて実際の訪問場所の分布を再現し，訪問場所のカテゴリにはの移動経路を生成する．具体的には，決定した SP を起点にそれ以前とそれ以降のサービス利用時刻におけるダミーの訪問場
所を順に決定する．ある時刻 ti におけるダミーの訪問場所をvti としたとき，時刻 ti+1 におけるダミーの訪問場所 vti+1 を次の手順で決定する．まず初めに，vti から時刻 ti+1 までの間に到達可能な範囲にある訪問場所のうち，カテゴリシーケンスに従ったカテゴリに該当する訪問場所を全て取得する．vti+1
は，この中から選択するが，この際，これらの訪問場所に対し
次式でスコアリングを行い，スコアが最も高くなるものを次の訪問場所として決定する
SimAr −CAr
(1+nreach (vti ))2α−1
Scorev (vti ) =1|SimAr −Ar |(1+nreach (vti ))2α−1てた（注 2）．ユーザの行動スケジュールの生成には，文献 [7] で用いられているチェックインのデータセットを利用した．ただし，このデータセットには，公共交通機関や自動車を用いた移動が含まれているため，次の手順で歩行のみによる行動スケジュー
ルに変換し，それを基にユーザの嗜好モデルを構築した．
（ 1 ） チェックイン時刻の間隔が 2 時間以上となっている部
分でチェックイン系列を分割し，それぞれを 1 つのユーザの行
動スケジュールとした．
（ 2 ） 各行動スケジュールで訪問場所をカテゴリ情報に変換
し，(1) 式によりサポート値を計算することで，ユーザの真の(CAr <= Ar )(otherwise)(7)

ここで，CAr は生成済みのダミーとユーザから形成される匿名領域の大きさ，SimAr は訪問場所 vti を次の訪問地点として決定した場合に形成される匿名領域の大きさ nreach (vti ) は，
時刻 ti に訪問場所 vti に到達可能な生成済みエンティティの数を表す．すなわち，生成済みのダミーとユーザから形成される
匿名領域の大きさと要求匿名領域の大きさを比較し，それが要求匿名領域より小さい場合，匿名領域の増分が大きくなるように次の訪問場所を選択し，逆に，既にこれが要求匿名領域より大きい場合，匿名領域の大きさが要求匿名領域 Ar に最も近くなる地点を次の訪問場所として決定する．その際，要求保存度が高い場合には他の生成済みエンティティから到達しにくい訪問場所を選択することで意図しない交差を抑制し，嗜好の保存度の向上を図る．

3. 7 Obfuscating グループのダミーの生成手順
Obfuscating グループのダミーは，ユーザの嗜好を考慮せずに動作させることで，ユーザの嗜好を保護する．さらに，設定されている共有地点数が少ないエンティティとの間に共有地点を設定することで，嗜好を知らない攻撃者に対する追跡可能性の低下を図る．具体的にはまず，設定されている共有地点数が最小のエンティティを取得する．さらに，共有地点を設定されているエンティティ数が最小の時刻を検索し，この時刻において，取得したエンティティとの共有地点を設定する．この共有地点を基準に，カテゴリシーケンスの制約を除き，Preserving
グループと同様の方法で経路を生成することでダミーの行動ス
ケジュールを決定する．

FourSquare で定められた第 1 階層のカテゴリ 10 種類を割り当

嗜好 Tu を構築した．
（ 3 ） 各行動スケジュールにおけるカテゴリシーケンスが保存されるようにしつつ，それぞれ前のサービス利用の時刻から最短経路を通って [8, 12] 分の移動時間で到達できる経路となる
ように訪問場所を変換した．
評価では，上記の手順により生成されたユーザの行動スケ
ジュール系列，および真の嗜好 Tu をダミー生成の際の入力とする．具体的には，行動スケジュール系列の先頭から各行動ス
ケジュールをユーザの行動プランとみなしてダミーを生成し，その結果に対して 4. 1 節で定義する各評価指標を計算した．

4. 1 評 価 指 標•

嗜好の保存度生成されたダミーの行動スケジュールに基づき可観測な嗜好 Toを構築し，式 (2) を用いて実際の嗜好の保存度を計算する．これが嗜好の要求保存度 α = [0, 1] に対し，どのように変化するかを調べることで，提案した手法における嗜好の保存度の制御可能性を検証する．

•

AR-Count / AR-Size

サービス利用の総数に対し，要求された匿名領域のサイズをダ
ミーの配置によって実際に達成できた回数の割合を AR-Count，
達成できた匿名領域の平均面積の要求匿名領域に対する割合を

AR-Size と定義する．これらが高い場合，ユーザの要求に対して，十分に位置曖昧度を確保できていることを表す．

•

MTC

文献 [6] の定義に基づき，追跡可能性を評価するための指標である MTC を次のように定義する．攻撃者から見たある位置情報がユーザのものである確率をユーザ確率と呼ぶ．ある時点において，目撃等によりユーザが特定された場合，ユーザ自身の（注 1）：https://developer.foursquare.com/docs/venues/search（注 2）：https://developer.foursquare.com/categorytreeユーザ確率は 1 となり，他のダミーのユーザ確率は 0 となる．

の嗜好 Tu が図 3 のものであるとしたときのユーザ確率の配分

ここで，エンティティ間で図 2(b) のように交差が発生した場を図 7 を用いて説明する．図は，時刻 t1 においてユーザ確率

合，交差前後の遷移の対応関係が一意に定まらなくなるため，がそれぞれ α，β であるユーザとダミーが時刻 t2 において交差

それらのエンティティ間でユーザ確率が配分される．この条件した際のユーザ確率の配分を表している．式 (9) に基づき，交下で MTC は，ユーザが特定された時点から各エンティティekX
p(k) log2 p(k) が差後のユーザのユーザ確率 γ は，のユーザ確率 p(k) のエントロピー H = −γ = P r(X3 = Caf e2)

閾値 T を超えるまでにかかる平均時間と定義される．なお，本= αP r(X3 = Caf e2|X2 = Gym1, X1 = Caf e1)

稿では T = 1 とした．すなわち，ユーザの各行動スケジュール+ βP r(X3 = Caf e2|X2 = Gym1, X1 = BookStore1)を tjk ，ユーザの行動スケジュールの総数を Ntj ，tjk におけるサービス利用の総数を n(tjk )，tjk において時刻 ti でユーザがと計算できる．ここで，Ci をユーザが時刻 ti において訪問し特定されてから H > T となるまでにかかる時間を T C(tjk , ti )た訪問場所のカテゴリを表す確率変数とすると，とすると，MTC は次式で計算される．

γ = αP r(C3 = Caf e|C2 = Gym, C1 = Caf e)

Ntjn(tjk )

は，tjk において，最後のサービス利用時刻 tn(tjk ) までに H > T+ βP r(C3 = Caf e|C2 = Gym, C1 = BookStore)P
C P r(C4 , C3 = Caf e, C2 = Gym, C1 = Caf e)= α P4 P
C4C3 P r(C4 , C3 , C2 = Gym, C1 = Caf e)P
C P r(C4 , C3 = Caf e, C2 = Gym, C1 = BookStore)+ β P4 P
C4C3 P r(C4 , C3 , C2 = Gym, C1 = BookStore)を達成できたユーザ特定時刻 ti の数である．この指標は，ユーと置き換えられる．ここで，Pr(S) をユーザがシーケンス S にザが特定されてから再び曖昧化されるまでにかかる平均時間で従って遷移する結合確率とすると，サポート値との関係は，あるため，この値が小さければ追跡可能性が低いことを表す．

Sup(S)
P r(S) = P
Sup(S)MT C =X
1
1 X
T C(tjk , ti )Ntjnachieve (tjk ) i=1

(8)

k=1

ただし，T C(tjk , ti ) は，時刻 tn(tjk ) までに H > T が満たせない
場合は 0 と見なし，MTC の計算には考慮しない．nachieve (tjk )本研究では，攻撃者として，嗜好を知らない攻撃者と嗜好を(10)知っている攻撃者の両方を想定し，それぞれに対する MTC をで あ る ．こ の 例 に お い て ，ユ ー ザ が と り 得 た シ ー ケ ン

評価する．これらの攻撃者は背景知識が異なるため，交差が発ス は ，Su,1 = Caf e → Gym → Caf e → BookStore，

生した際のユーザ確率の配分が異なる．以下でそれぞれの攻撃

Su,2者を想定した場合のユーザ確率の配分について説明する．

ミ ー が と り 得 た シ ー ケ ン ス は ，Sd,1 = BookStore →a ) ユーザの嗜好を知らない攻撃者の場合

=

Caf e

→

Gym

→

Library→

Gym，ダGym → Caf e → BookStore，Sd,2 = BookStore →まず一般的に，図 6 のように，時刻 ti において，ユーザ確率

Gym → Library → Gym で あ り，そ れ ぞ れ の サ ポ ーが α で訪問場所 v1 に存在するユーザと，ユーザ確率が β で訪

ト 値 は 図 3 か ら ，Supu (Su,1 ) = 0.05，Supu (Su,2 ) = 0.02，

問場所 v2 に存在するダミーが時刻 ti と ti+1 の間で交差し，そSupu (Sd,1 ) = 0.06，Supu (Sd,2 ) = 0.01 と求まる．よって，れぞれ訪問場所 v4 , v3 に遷移した場合のユーザ確率の配分を考える．Xi をユーザが時刻 ti で訪問した訪問場所を表す確率変数とすると，交差後のそれぞれのユーザ確率は P r(Xi+1 ) と表され，次のように計算できる．
X
P r(Xi+1 ) =P r(Xi+1 |Xi )P r(Xi )(9)Supu (Sd,1 )Supu (Su,1 )+βSupu (Su,1 ) + Supu (Su,2 )Supu (Sd,1 ) + Supu (Sd,2 )
0.05
0.06
0.05α + 0.06β
=α
+β
=
,
0.02 + 0.05
0.06 + 0.01
0.07

γ=α

同様に，

Xi

すなわち，図 6 の場合，

γ = P r(Xi+1 = v4 )= αP r(Xi+1 = v4 |Xi = v1 ) + βP r(Xi+1 = v4 |Xi = v2 )
=

α+β
,
2

δ = P r(Xi+1 = v3 )= αP r(Xi+1 = v3 |Xi = v1 ) + βP r(Xi+1 = v3 |Xi = v2 )α+β=2となる．この配分方法に基づく MTC を MTC1 とする．

b ) ユーザの嗜好を知っている攻撃者の場合
ユーザの真の嗜好 Tu を把握している攻撃者に対しては，ユー
ザ確率の配分を Tu に含まれるサポート値に基づいて行う．真

δ=α

0.02
0.01
0.02α + 0.01β+β=
0.05 + 0.02
0.06 + 0.01
0.07と計算できる．この配分方法に基づく MTC を MTC2 とする．

•

CR (Confusion achieving Ratio)

式 (8) における Ntj ，n(tjk )，nachieve (tjk ) を用いて，追跡可能性を評価するためのもう一つの指標として CR を定義する．
Ntj
1 X nachieve (tjk )
(11)
CR =
Ntj
n(tjk )
k=1

CR は，ユーザの行動スケジュール全体のうち，最初のサービス利用からどの程度の割合のサービス利用までのユーザ特定に対し，最終サービス利用時刻までにユーザの曖昧性を回復することができたかを表す．そのため，この値が高いほど追跡可能性が低いことを意味する．嗜好を知らない攻撃者を想定した場合のユーザ確率の配分方法に基づいて計算される CR を CR1，
嗜好を知っている攻撃者を想定した場合の CR を CR2 とする．

図6

図7

嗜好を知らない攻撃者からみたユーザ確率の配分

嗜好を知っている攻撃者からみたユーザ確率の配分
表2

各ユーザのチェックインデータの特徴

図8

真の嗜好のヒストグラム

図 10

嗜好の保存度の収束値

図9

図 11

嗜好の保存度の遷移

可観測な嗜好のヒストグラム(要求保存度 1.0)

ら，提案手法は，嗜好を保存するダミーと嗜好のプライバシをパラメータ名値

総チェックイン数1322

保護するダミーの割合を要求に応じて混合することで，嗜好の行動スケジュール数 (経路数)251

保存度を制御できていることを確認した．

1 行動スケジュール中の平均サービス利用回数

5.1

次に，要求保存度を 1.0 とした際の可観測な嗜好のヒストグ

平均サービス利用間隔 [s]594.4

ラムを図 11 に示す．ただし，このヒストグラムでは，ユーザの真の嗜好に含まれないシーケンスは省略している．このグラ

4. 2 評 価 結 果

フを図 8 と比較すると，類似性が高いことがわかる．しかし，本評価では，ユーザの嗜好情報を十分に確保するために，デー

嗜好の保存度は 0.73 程度に留まっている．これは，意図しない

タセットに含まれるユーザのうち，特にチェックイン数の多かっシーケンスが計上される交差が発生していることに起因する．

たユーザを選出し評価を行った．ユーザのチェックインデータ

真の嗜好においてサポート値が 0 でないシーケンスの数が 130の特徴は表 2 の通りである．

個であるのに対し，可観測な嗜好では，サポート値が 0 でない

ユーザの真の嗜好のヒストグラムを図 8 に示す．このヒスト

シーケンスが 3601 個存在する．しかし，意図しないシーケン

グラムにおいて，横軸は真の嗜好中の各カテゴリシーケンス，

スのサポート値はユーザの真の嗜好に含まれるシーケンスのサ

縦軸がそのシーケンスのサポート値に対応し，各シーケンスをポート値と比べると小さいことが確認されたため，パーソナラ

サポート値により降順にソートして表示している．一部のシーイズ等に用いる際には，これらをフィルタリングすることによ

ケンスのサポートが高くなっていることから，普段よく行ってり十分なパフォーマンスを期待できると考えられる．

いる行動パターンがあることがうかがえる．

次に，要求保存度に対する AR-Count，AR-Size の変化を図

本評価では，このユーザに対し，要求保存度 α を変化させな

12，図 13 に示す．AR-Count，AR-Size ともに要求保存度 1.0

がら提案したダミー生成手法を適用し，各評価指標の値の変化の場合と 0.0 の場合で達成率が大幅に低下している．1.0 の場を調べた．なお，要求匿名領域は Ar = 15002 [m2 ]，ダミー数合に低下するのは，要求保存度が増加すると，ユーザの真の嗜

は n = 9 とした．まず，各ユーザの行動スケジュールの系列に好に含まれるシーケンスに従って移動するダミーの数が増加す提案手法を適用した際の，実際の嗜好の保存度の遷移を図 9 にるためである．すなわち，カテゴリシーケンスの制約を満た示す．このグラフにおいて，横軸はユーザの行動スケジュール

し，かつ匿名領域の要求を満たせる経路の発見が実環境におい

系列中の各行動スケジュールに対応し，縦軸は，その系列の先て困難であることを意味する．一方，要求保存度が 0.0 の場合

頭から順にダミー生成を行った結果の累積から計算される嗜好にも AR-Count，AR-Size ともに小さい値となっている．これの保存度を表す．この結果から，行動スケジュール系列が進む

は，提案した手法で他の生成済みエンティティからの到達可能につれて，嗜好の保存度が一定の値に収束する傾向があること性を考慮している影響である．要求保存度が小さい場合，他のがわかる．そのため，以降では，最後の行動スケジュールに対生成済みエンティティから到達しやすい訪問場所が選択されるするダミー生成が終了した時点の嗜好の保存度の値を収束値とことでエンティティが密集しやすくなるため，匿名領域が小さし，この値を用いて嗜好の保存度の制御可能性について論じる．

くなったと考えられる．

嗜好の要求保存度に対する嗜好の保存度の収束値の遷移を図 10

各ユーザにおける MTC と CR の評価結果を図 14，図 15 にに示す．このグラフから，要求保存度の増加に対し実際の嗜好示す．図 14 において，各プロットに付記した数値は，ユーザの保存度が概ね線形に増加していることがわかる．このことかの曖昧化を一度でも達成できた行動スケジュールの数，つまり，

平均の計算に用いられた追跡可能時間の数を表す．

MTC1 は要求保存度の値に対する変化が小さい．提案した手法では，各ダミー生成時に 1 つしか共有地点を設定していないが，各要求保存度に対する MTC1 の平均値は，704.1 秒と十分に小さい値を維持できている．ユーザの平均サービス利用間隔
はそれぞれ 594.4 秒であるので，平均で 1.2 回程度のサービス
利用の間に再び曖昧性を回復できたことを表す．このことから，

8 ∼ 12 分程度の間隔でサービス利用が起こる場合，適度な大き

図 12

AR-Count

図 13

AR-Size

図 14

MTC

図 15

CR

さの領域にダミーを配置すれば，意図的な交差を設定しない場
合でも，嗜好を知らない攻撃者に対しては容易にユーザの曖昧性を回復することが可能であることがわかる．そのため，CR1
は常に達成率が 0.8 以上の高い値を維持できている．
一方，MTC2 は要求保存度が高くなると上昇している．これは，MTC2 要求保存度が低い場合に，曖昧化を一度も達成できなかった行動スケジュール数が多いことに起因する．MTC の計算では，その行動スケジュール終了時までに曖昧化の条件が達成されない場合，その追跡可能時間は計算に含められない．

謝

要求保存度が小さい場合，ユーザの嗜好を考慮したダミーの数

本研究の一部は，文部科学省科学研究費補助金・基盤研究も少なくなるため，曖昧化の条件を達成できた回数が減少して(A)(26240013)，および日立財団研究助成「倉田奨励金」の研いる．そのため，平均の計算に考慮された追跡可能時間の数が究助成によるものである．評価で利用した東京 23 区の地図デー

著しく少なくなり，MTC2 が小さくなったと考えられる．逆タは一般財団法人日本デジタル道路地図協会より貸与されたもに，要求保存度が高い場合は，曖昧化を達成できた回数が増加のである．ここに記して謝意を示す．

しているが，その際，要求保存度が小さい場合には考慮されな
かった長い追跡可能時間が平均の計算に考慮されるようになり，

MTC2 が増加したと考えられる．そのため，CR2 は，要求保存度が小さい場合にはほぼ 0 となっている．この結果は，嗜好を知っている攻撃者の追跡能力の高さを示唆しており，嗜好を考慮しないダミー生成手法では，サービス利用を追跡される危険性が極めて高いことを意味する．それに対し提案手法では，
要求保存度を高く設定することで，CR2 の値に改善が見られ，その値は，要求保存度を 1 とした場合に平均で 0.44 となっている．この値は，平均すると行動スケジュール前半でのユーザの特定に対し，最後のサービス利用までの間にユーザの曖昧性を回復できたことを意味する．この結果から，ユーザの嗜好を考慮することは，嗜好の保存の観点のみでなく，位置プライバ
シ保護の観点からも極めて重要であるといえる．

5. お わ り に
本稿では，先行研究 [11] で提案した手法の有効性を確認する
ために，FourSquare のデータセットを用いてシミュレーション評価を行った．評価の結果，提案手法では，ユーザの嗜好を保存するダミーとユーザの嗜好と異なるダミーをユーザの要求する保存度に応じた比率で生成することで，嗜好の保存度を制御可能であることを確認した．また，ユーザの嗜好を考慮してダミーを生成することで，従来手法よりもユーザの嗜好を知っている攻撃者に対する追跡可能性を低下できることを確認した．
今後は，公共交通機関を利用するユーザに対しても効果的にダミーが生成できるように，手法の拡張を行う予定である．

辞

文

献

[1] Bao, J., Zheng, Y. and Mokbel, M. F.: Location-based andPreference-aware Recommendation Using Sparse Geo-social
Networking Data, In Proc. GIS, pp. 199–208 (2012).
[2] Chen, R., Acs, G. and Castelluccia, C.: Differentially Private Sequential Data Publication via Variable-length Ngrams, In Proc. CCS, pp. 638–649 (2012).
[3] Götz, M., Nath, S. and Gehrke, J.: MaskIt: Privately Releasing User Context Streams for Personalized Mobile Applications, In Proc. SIGMOD, pp. 289–300 (2012).
[4] Li, Q., Zheng, Y., Xie, X., Chen, Y., Liu, W. and Ma, W.Y.: Mining User Similarity Based on Location History, In
Proc. GIS, pp. 34:1–34:10 (2008).
[5] Lu, H., Jensen, C. S. and Yiu, M. L.: PAD: Privacy-area
Aware, Dummy-based Location Privacy in Mobile Services,
In Proc. MobiDE, pp. 16–23 (2008).
[6] Shokri, R., Freudiger, J., Jadliwala, M. and Hubaux, J.-P.:
A Distortion-based Metric for Location Privacy, In Proc.
WPES, pp. 21–30 (2009).
[7] Yang, D., Zhang, D., Zheng, V. W. and Yu, Z.: Modeling
User Activity Preference by Leveraging User Spatial Temporal Characteristics in LBSNs, IEEE Trans. SMC, Vol. 45,
No. 1, pp. 129–142 (2015).
[8] Ying, J. J.-C., Lee, W.-C., Weng, T.-C. and Tseng, V. S.:
Semantic Trajectory Mining for Location Prediction, In
Proc. GIS, pp. 34–43 (2011).
[9] 加藤 諒，原 隆浩，Xie, X.，岩田麻佑，西尾章治郎：ユーザの行動プランの変更を考慮したダミーによるユーザ位置曖昧化手法，第 7 回データ工学と情報マネジメントに関するフォーラム
論文集 (2015).
[10] 加藤 諒，松野有弥，原 隆浩，荒瀬由紀，Xie, X.，西尾章治郎：ユーザの訪問場所の傾向を考慮したダミーによるユーザ位置曖
昧化手法，情報処理学会マルチメディア，分散，協調とモバイル
シンポジウム論文集，Vol. 2014, pp. 1174–1181 (2014).
[11] 水野聖也，原 隆浩，Xie, X.：位置プライバシ保護のための嗜好の保存度合いを考慮したダミー生成手法の検討，情報処理学会
研究報告，Vol. 2015-DPS-165, No. 6, pp. 1–7 (2015).