DEIM Forum 2017 H6-1

Geo 識別不能性を用いた経路端点の曖昧化
浅田

真帆†

曹

洋††

吉川 正俊††† 京都大学工学部情報学科 〒 6068501 京都府京都市左京区吉田本町 36-1†† 京都大学情報学研究科 〒 6068501 京都府京都市左京区吉田本町 36-1
E-mail: †{asada,soyo}@db.soc.i.kyoto-u.ac.jp, ††yoshikawa@i.kyoto-u.ac.jp
あらまし

近年，スマートフォンの普及や GPS 測位機能の発達等により，人々の位置情報がかなり正確かつ容易に把握できるようになっている．このようなデータはマーケティングや都市計画など様々な場面に応用することができ，より有効に活用するためにそれらを売買する市場の整備も始まっている．しかし一方で，正確すぎる位置情報は個人を特定しかねないというプライバシリスクがあり，それを防ぐために位置情報の匿名化や曖昧化を行う必要がある．
また位置情報の中でも移動経路情報は特にプライバシリスクが高いと言われるが，その匿名化・曖昧化の技術は発展途上にある．そこで本論文では経路情報の匿名化・曖昧化に重点を置き，自宅のような経路端点を特定できず，しかも経路情報としての効用性を失わない手法を提案する．この手法において，プライバシ保護の側面では，位置情報匿名化に差分プライバシの概念を応用した Geo 識別不能性 (Geo-indistinguishability) という技術を利用する．また，元の経路が最短経路であるという前提の下，出力経路は途中まで入力経路と同じ経路を辿り，Geo 識別不能性を満たす
別の点へ最短経路を通って向かうという形にしており，この点で効用性を保つことも目指している．実データを用いた実験では，京都の道路ネットワーク上で様々な始点を持つ経路の曖昧化を行い，その出力経路の効用性を比較した．
キーワード

差分プライバシ1. は じ め に
近年，スマートフォンの普及や GPS 測位機能の発達等により，人々の位置情報がかなり正確かつ容易に把握できるようになっている．このようなデータは公私様々に応用することができる．位置情報の活用例としては以下のようなものが挙げられ
る [1]．
（ 1 ） ターゲティング
現在のユーザの位置情報からその時点で自社店舗の周辺にいる
ユーザに対して広告を配信したり，過去に過去にユーザが訪れた場所を基にユーザの嗜好や移動範囲を推測し，場所の推薦や図1提供しても良いと思うデータの条件 (全体)（n=1,059）[4]

住宅広告を配信したりする．Near（注 1） というターゲティング広告配信技術などがこれにあたる．今日では一点の位置情報だけ
でなく，その系列である移動経路を収集し活用する『リアル行動ターゲティング』という手法も用いられ始めている [2]．これはある一人のユーザの移動経路を複数集めることでその行動パターンを分析し，ユーザに合わせた広告をより効果的に配信するというものである．
（ 2 ） 道路交通情報の把握
リアルタイムで人々の位置情報の時空間データを分析して交通状況を把握したり，最適な移動ルートを推薦したりする．Google

Maps などで利用されている．
（ 3 ） 都市計画
都市で生活する人々の移動パターンや居住分布を分析し，都市計画に生かす．
（ 4 ） 公衆衛生

群衆の位置情報の分析を感染症の蔓延防止策に役立てる．
（ 5 ） 位置情報を用いたゲーム『Pokemon Go』など，位置情報がなければ有効に機能しない
アプリケーションがある．
以上のように位置情報が価値を持ち始める中で，より有用かつ多くの位置情報を手に入れるために，それらを売買する市場の整備が始まっている [1]．日本でも位置情報をはじめとしたパー
ソナル情報の流通を司る “情報銀行”の設立を目指す動きも起こっている [3]．
しかし一方で，正確すぎる位置情報は個人を特定しかねない，というプライバシリスクがある．そのため，図 1 に示すように，
人々の位置情報に対するプライバシ意識は非常に高いという調
査結果もある．こういったプライバシリスクを防ぐために，位置情報の匿名化や曖昧化を行う必要がある．また位置情報の中でも，移動経路情報は特にプライバシリスクが高い．例えば訪（注 1）：https://near.co/

れた場所の位置情報が四つ分かれば 95%の確率で個人を特定す

ライバシ情報が漏洩してしまう可能性がありプライバシリスク

ることができるという研究結果 [5] や，複数の経路情報を公開が高まってしまう点 [9] や，ここで紹介した手法がすべてそうすることにより，よく訪れる場所や自宅の場所などが特定されであったように，k-匿名化を行うには他のユーザの経路が複数てしまう可能性もある．しかしプライバシリスクの高さに反し必要であるという点がそれにあたる．次章で紹介する差分プラて，こういった経路データの匿名化や曖昧化の技術は発展途上

イバシの概念を用いた手法ではこのような欠点がない．

にある．
そこで，本論文では経路情報の匿名化・曖昧化に重点を置き，

3. 差分プライバシに基づく経路情報の保護

中でも自宅のような経路の端点を特定できず，しかも経路情報

3. 1 差分プライバシの定義としての効用性を失わない手法を考える．この手法において，差分プライバシ [10] とは，データベース中の個人データの含プライバシ保護の側面では，位置情報匿名化に差分プライバシ

まれるレコードの内容を攻撃者から保護しつつ，データベースの概念を応用した Geo 識別不能性 (Geo-indistinguishability)

全体に対する統計的解析を可能とする仕組みである [11]．以下という技術を利用する．また，元の経路が最短経路であるといにその数学的定義を述べる．

う前提の下，出力する経路は途中まで元の経路と同じ道を辿り，

数学的定義を行うための準備としてデータベースモデルにつGeo 識別不能性を満たす別の点へ最短経路を通って向かうといいて述べる．データベース D の要素となるレコードは属性のう形にしており，この点で効用性を保つことも目指している．

集合とし，属性の集合の取り得る値のインデクスを i とする．

また効用性を示す指標として入力経路と出力経路の誤差を考

ただし，i = 1, . . . , m である．以下では D を xi の出現回数でえ，経路始点やダミー端点を様々な位置にとりそれを比較する

表現し，これをヒストグラムと呼ぶ．これで表現された二つの実験を行った．ここで誤差として入力経路と出力経路が囲む面

データベース D ，D ′ の距離を定義するため，l1 ノルムを定義

積と，その二つの DTW(Dynamic Time Warping) 距離を計測する．

した．この実験結果からダミー端点の取り方や始点の位置と効［定義 1］（l1 ノルム） m 次元ベクトル x の l1 ノルム ∥x∥1 は用性の相関関係について検討した．

次式で定義される．

∥x∥1 =

2. 関 連 研 究

m
∑

|xi |

i=1

この章では経路情報の保護に関する先行研究を紹介する．前

これを用いると，ヒストグラムで表現された D と D ′ の距離は提として経路情報の公開には二つの手法があるとする．一つは∥D − D′ ∥1 となる．ここから差分プライバシの数理モデルを定

複数の経路をまとめて公開するものであり，それぞれの経路を義する．

一つのレコードとして考える．またもう一つの手法ではある一［定義 2］（差分プライベート） D ∈ Nm ，D ′ ∈ Nm とする．

つの経路を点の系列とみて公開するものであり，この見方をすメカニズム M が以下の条件を満たすとき，M は (ϵ, δ)-差分プる手法はまだ少ない．本論文では経路情報を後者のように見る

ライベートであるという．

こととする．

′m′∀S ⊂=Range(M ) 及び ∀D, D ∈ N に対して，∥D − D ∥1 = 1

2. 1 k-匿 名 化
k-匿名化 [6] とは近年最もよく用いられているプライバシ保
護技術の一つで，同じ属性を持つデータが k 件以上存在するであるとき′
P r[M (D) ∈ S] <= exp(ϵ)P r[M (D ) ∈ S] + δ（k-匿名性を満たす）ようにデータを変換することで、個人が特

なお，δ = 0 の場合，M は ϵ-差分プライベートという．

定される確率を k 分の 1 以下に低減させるというものである．

ここで ∀S ⊂=Range(M ) は，M が生成する可能性のあるデータ

複数の経路に対しこの手法を経路情報の保護に応用した手法
で用いられる概念が，(k, δ)-匿名化というものである [7]．ここ

ベースの部分集合の全てを意味する．

3. 2 差分プライバシを用いた経路情報の保護手法

で δ は保護を行いたい範囲を表すパラメータである．この手法

差分プライバシに基づき経路情報を曖昧化する手法の例としでは，x 軸と y 軸が平面上の点の位置を表し，z 軸が時間を表て，Jiang らの研究がある [12]．この研究では経路を点の系列

す３次元空間を考える．このとき経路は (x, y, z) の系列集合とと見なし，入力された経路の始点と終点はそのまま出力すると見なすことができる．ここで匿名化したい経路を T とし，そし，その間の点の集合を，差分プライバシを満足し，かつ元ののそれぞれの時間における位置を中心とした半径 δ の円を考え

経路上の点から自然な距離かつ角度にある点の集合に変換する

る．全ての時間における点の位置がこの円の中に含まれる経路という手法を取っている．また Dong らの研究手法 [13] では，

を k − 1 個集めたとき，T は (k, δ)-匿名化されているといえる．

移動経路推薦システムにおいて，その分析元となる道路上のまた Huo らの研究 [8] では，一定時間以上滞在した場所を

ユーザそれぞれの移動経路の始点と終点を差分プライバシの概“stay point”と定義し，その点を通る経路の集合を用いて k-匿

念を用いて特定できないようになっている．このように差分プ名化を行う．

ライバシを用いた経路情報の保護手法の研究はいくつかあるがこのように k-匿名化を利用した経路情報保護の手法は多く

まだ数が少なく，次に述べるケースのように，現在存在する手あるが，同時に欠点もある．データ所有者を特定しようとする法の応用ができない場合もある．本論文で提案する手法の応用“攻撃者”が与えられた経路情報以外の情報を持っていた場合プ

例として，1. で述べた “リアル行動ターゲティング”を考えている．このとき扱うのは一人のデータ所有者の複数の経路情報

り，かつ元の経路に近いものとなるようにする．

であるが，このような場合に経路情報を曖昧化する手法は知ら

5. 1 手法の概要

れていない．また一般に，プライバシを保護するためには元の前提として，地図上の道路ネットワークは，枝に距離を表す

経路に雑音を加えることになるが，保護の度合いを大きくしよ

重みが付いた無向グラフ G(V, E, w) で表現されるとする．こうとして大きい雑音を加えると，出力経路の効用性が低下する．

こで，V は節点の集合，E は枝の集合，w : E → R+ は，各枝

プライバシ保護と効用性の向上のバランスが難しい問題である．

に重みを与える関数である．入力経路はこのグラフ内のノード

先述したように，本研究ではある一人のデータ所有者が，自宅と外出先の間の経路情報を雑音を加えて複数公開する場合を主な応用例として考え，差分プライバシの概念を用いて経路端を通る．
経路は x = [x1 , ..., xn ] のように表す．また，任意の二点

x, y ∈ V の間の最短経路を < x, y > で表す．

点を曖昧化する手法を提案する．このとき，元の経路は最短経

データ所有者は保護したい範囲を，保護したい端点 xn を中心と路であると仮定し，雑音を加えて得られる経路は，端点を曖昧した半径 r の円として指定することができる．この円を Cr (xn )化した上でしかも最短経路になるようにする．

のように表すものとする．またそのプライバシ保護レベル ϵ と，出力となる曖昧化された経路の端点であるダミー端点の個数 m

4. Geo 識別不能性を指定することができる．最終的に出力される経路の端点はこ

この章では，Geo 識別不能性 [14] の概念とそれを満足する手法について紹介する．

4. 1 概の複数のダミー端点からランダムに選ばれるとする．
また曖昧化された経路を出力する際の準備として，次の範囲

要を定義する．

まず始めに用語説明をする．X をユーザの存在しうる点の集［定義 4］（PTA(Possible Terminal Area)） 距離付き無向グラ

合とし，ユーザの存在しうる点をある曖昧化機構によって曖昧

フ G が与えられたときに，ある点 o から別の点 q までの最短化した結果得られる点の集合を Z とする．また，計算機構 K

経路中に点 p が現れるとき，q を（G における）点対 (o, p) のは，X 内のある点 x に対して，Z 上の確率密度分布を与える

possible terminal と呼ぶ．G における点対 (o, p) のすべてのとする．

possible terminal の集合を（G における）(o, p) の PTA (Pos′［定義 3］（Geo 識別不能性） 任意の二つの点 x, x においてsible Terminal Area) と呼ぶ．特別な場合として，点対 (o, o)

以 下 が 成 り 立 て ば ，機 構 K は ϵ-geo 識 別 不 能 性 (ϵ-geo-の PTA は G のすべての点となる．

indistinguishability) を満たすという [14]．
′dP (K(x), K(x′ )) <= ϵd(x, x )5. 1. 1 手法の流れ
手法の大まかな流れは以下の通りである．

•

STEP1(ダミー端点の選択)

但し，d(·, ·) はユークリッド距離である．ここで機構 K によっ

経路 x，保護範囲となる円の半径 r ，保護レベル ϵ，ダミー端点て計算された確率分布 K(x) と K(x′ ) の距離 dP (K(x), K(x′ ))の個数 m を入力．これらをもとに，Cr (xn ) の中で ϵ-Geo 識別について説明する．攻撃者の事前知識を，X 上の事前分布 π で不能性を満たす点を m 個出力し，それらを g1 , g2 , . . . , gm とす表す．ただし，π(x) は，場所 x に割り当てられた確率とする．

る (図 2)．

π と Bayes の法則から，K によって計算された Z(∈ Z) を観測することにより，事後確率分布 σ = Bayes(π, K, Z) が計算できる．ここで σ(x) = ∑ K(x)(Z)π(x)となる．これを用い′ K(x′ )(Z)π(x′ )xて得られるのがある集合 S 上の二つの分布 σ1 と σ2 の距離で(S)あり，dP (σ1 , σ2 ) = supS∈S | ln σσ21 (S)| と定義される．また ϵ は正の実数であり，距離単位のプライバシ保護レベルと考える．

ϵ-geo 識別不能性を満たす一つの機構が二次元ラプラス機構
である．ある点 x と，それを中心とする半径 A の円に含まれるある一点 x′ を考える．それぞれの点を入力した時、二次元

図 2 STEP1

ラプラス関数に従う雑音を加えることで出力されうる点の確率密度分布を計算することができる．このとき，２点それぞれを中心とする二次元ラプラス確率密度分布の差が小さければGeo 識別不能性を満たすという．ここで確率密度分布の差は
dP (K(x), K(x′ )) である．

5. 提 案 手 法
この章では，経路の端点が Geo 識別不能性を満足するように曖昧化された経路を出力する手法について述べる．入力する経路は最短経路であるとし，出力する経路も同様に最短経路であ•STEP2(xk の選択)

経路 x 中の点のうち以下の条件を満足する点 xk を選ぶ．

Cr (xn ) 内のすべての点は点対 (x1 , xk ) の PTA に含まれる．
しかし，Cr (xn ) 内の点のうち点対 (x1 , xk+1 ) の PTA には含
まれないものがある．
このような点は一意に求まることに注意されたい．概要を図 3に示す．

•

STEP3(経路の変換)

•

出力データ

以 下 に 示 す 処 理 を 行 い 曖 昧 化 さ れ た 経 路 x′=

[x1 , ...xk , x′k+1 , ..., x′l ] を出力データとする．
•

処理

入力データを出力データに変換する際の処理の流れは以下の通りである．

– STEP1
k を n − 1 とする．
5. 2. 1 に示す Goal-select の入力において，始点 xs を x[k − 1]，
中継点 xm を x[k] とし，処理を行う．このとき出力される集合

図 3 STEP2

V[xk−1 ,xk ] が，xn を中心とする半径 r の円に含まれるノードの集合を被覆するかどうかを調べる．被覆する場合は STEP2 へ，しない場合は k の値を 1 減らし，STEP1 の処理を再度行う．

– STEP2
5. 2. 2 に示す Geo-select を呼び出し，xn を中心とした半径 rの円の中で ϵ-Geo 識別不能性を満たすある m 個の点を計算し，その中から一つをランダムに選択し，ダミー端点 x′m とする．

x[k] から xn ’ に至る最短経路 < xk , x′l > を y = [xk , x′k+1 , ...x′l ]とする．

– STEP3
x の k 番目から n 番目までの要素 [xk , ..., xn ] を y に置き換え

図 4 STEP3

た経路 x′ = [x1 , ...xk , x′k+1 , ..., x′l ] を作成し，これを曖昧化さ

STEP1 で求めた m 個のダミー端点の中から一つをランダムにれた経路として出力する．

選択し，それを gl とする．STEP2 で求めた点 xk から gl に至5. 2. 1 Goal-selectる最短経路 < xk , gl > を求める．元の経路のうち始点から点始点と中継点を入力した際に，その最短経路の終点となりう′

xk までの経路と < xk , gl > を繋げた経路 x を，曖昧化された経路として出力する (図 4)．

5. 2 具体的な手法
経路 x 上の連続する２点 xk−1 ，xk をそれぞれ始点，中継点としたときに最短経路の終点となりうる点の集合 V[xk−1 ,xk ]を 5. 2. 1 に述べる Goal-select で求め，V[xk−1 ,xk ] が端点 xn をる点の集合を求める範囲を求める．

•

入力データ

– グラフ G(V, E, w)
始点 xs ，中継点 xm ともに，このグラフ上のノードであるとする．

– 始点 xs

中心とした半径 r の円を被覆するような点 xk を発見する．ま– 中継点 xm

た，5. 2. 2 に示す Geo-select により，プライバシ保護を行いた•

い範囲の中で Geo 識別不能性を満足する点 gl を求める．元の出力データ

最短経路の終点となりうる点の集合 V[xs ,xm ] を出力とする．

経路の始点から xk までの経路と，xk から gl までの最短経路•< xk , gl > を繋げたものを曖昧化された経路として出力する．

– STEP1•

入力データ– グラフ G(V, E, w)
地図上の道路ネットワークを表す．ノードとエッジの繋がり，処理

Dijkstra 法を用いて，xs を始点とした時にグラフ上のそれぞれのノードに至る最短経路を求める．

– STEP2ノード間のコスト，ノードの地図上における緯度経度を情報とSTEP1 で求めた最短経路の集合の中から xm を通るものを探索して持つ．

し，見つかった場合にはその経路の xm 以降のノードを V[xs ,xm ]– 経路 x = [x1 , ..., xn ]x[i] は x の i 番目の点，即ち xi であるとする．
– 半径 rxn が曖昧化された点 x′l は，xn を中心とした半径 r の円の中にあるとする．

– 保護の度合い ϵxn を中心とした半径 r の円の中におけるプライバシ保護レベ
ル．これが小さくなればなる程プライバシ保護の度合いは小さくなる．

に追加する．

– STEP3
すべての最短経路に対して STEP2 の処理が終われば，V[xs ,xm ]を出力する．

5. 2. 2 Geo-select4. において定義した Geo 識別不能性を満足する点を選択する．
•

入力データ

– グラフ G(V, E, w)
それぞれのノードは地図上の緯度・経度の情報を持つ．

– 点x

6. 実 験 方 法

グラフ上の保護したいある一点．

– 半径 r

6. 1 実験の概要– 保護の度合い ϵ

経路端点を Geo 識別不能性を用いて曖昧化することにより，– 出力する点の個数 m

プライバシ保護は既に保障されている．したがって，端点を曖– パラメータ u, δθ昧化することにより出力された経路の効用性を本実験で確かめ

Geo 識別不能性を満たす点を出力するメカニズムの精度を調整

たい．効用性を測るにあたっての指標を入力経路と出力経路のするパラメータ．

誤差とし，２種類の値を用いた．一つは入力経路と出力経路が•囲む範囲の面積 A(m2 ) としてそれを計測した．ここで，面積出力データ

点 x を中心とした半径 r の円の中で ϵ-Geo 識別不能性を満たの計算には地図蔵（注 1） を利用している．またもう一つの効用性

すある m 個の点 g1 , g2 , . . . , gm を出力する．

の評価指標として，次の値を定義する．

•［定義 5］（RPD (Relative Path Distance)） 始点が同じある

処理

二つの経路 x = [x1 , x2 , . . . , xl ], y = [y1 , y2 , . . . , ym ] (x1 = y1 )– STEP1
点 x とグラフ上のそれぞれのノードのユークリッド距離を計算を考える．x 上の各点と始点の間の距離の，x 全体の長さに対し，x を中心とした半径 r の円の中にあるグラフ上の点の集合

する割合 rx = [r1 , r2 , . . . , rl ] を求める．y 上で y 全体の長さR を求める．

に対して r の割合をとる点の系列 yx = [yx1 , . . . , yxl ] を求め，– STEP2

これを x に対する y の relative path と呼ぶ．x と yx の対応ある範囲 rmax の中で epsilon-geo 識別不能性を満足するためする点の距離の総和を x に対する y の RPD (Relative Pathには，以下の定理を満たす必要がある．

Distance) と呼ぶ．

［定理 1］ rmax < u/δθ ，q = u/rmax δθ であるとする．この時この値において入力経路を x，出力経路を y としたときの RPD′

を D(km) とし，これを計測した．ここで，入力経路の始点をϵ, ϵ は以下の式を満足する．
′

ϵ′ +

1
q + 2eϵ u <ln
ϵu q − 2eϵ′ u =この時，メカニズム Kϵ′ によって出力される点は rmax の範囲の′中で ϵ -Geo 識別不能性を満たす．つまり，d(x0 , x), d(x′0 , x) <=rmax であれば次式が成り立つ．
′

ϵd(x0 ,xo )Kϵ′ (x′0 )(x)Kϵ′ (x0 )(x) <=es，ダミー端点を d としたときの誤差をそれぞれ As,d ，Ds,d とする．誤差が小さくなればなるほど，効用性は大きくなると考える．
本実験では経路端点 o を図 5 の中心にあたる四条烏丸に固定し，出力されるダミー端点を３個として２種類の実験を行った．
一つは端点からの方角が異なる４点を始点とする四つの経路を入力として，異なるダミー端点を持つ経路をそれぞれ三つずつ

ϵ を rmax = diam(r) とした時に定理 5. 2. 2 を満たす最大の値

出力し，合計 12 個の曖昧化した経路とそれぞれの元の経路と′ϵ に変換する．ここで diam(r) は x を中心とした半径 r の円の誤差を比較した．これにより入力経路の始点とダミー端点のの中のそれぞれのノードの最大距離である．

位置関係が誤差にどのような影響を与えるのかを検証した．またもう一つの実験では，端点と始点の距離，Cr (o) の半径 r を– STEP3x を極座標 (r, θ) に変換する．ここで出力されうる点を x0 と変化させた時の誤差を比較し，この二つのパラメータの相関関すると，r は x と x0 の距離，θ は直線 xx0 と x 軸のなす角で係を調べた．
ここで，入力経路の始点と r を固定した時に最大・最小のある．

A または D を生成するダミー端点をそれぞれ dmax ，dmin と– STEP4
x を中心とする半径 r の円内の任意の点が出力される確率を p′とすると，雑音 r は

1
p−1
r′ = Cϵ−1(W−1 ( ′ ) + 1)
′ (p) = −ϵ′ϵと計算できる．ここで，W−1 は Lambert 関数である．
′

する．

6. 2 データセット
本論文は道路ネットワーク上の経路曖昧化手法の提案を行っている．したがって公開されている道路ネットワークとして，

Open Street Map Japan（注 1） より，図 5 に示す範囲の京都市のまた，雑音 θ は乱数となる．

道路データを取得した．またこのデータに対し，非連結な頂点

ここで計算した (r ′ , θ ′ ) を (r, θ) に加え，緯度・経度の形に変換を省く等の前処理を行っている．この処理を行った結果，頂点した点 x′ を求める．

数は 3742 個となった．

– STEP5
STEP1 で求めた集合 R に含まれる点の中で x′ に最も近いものを g1 とする．

6. 3 経路曖昧化の一例
実際の経路に本論文の提案手法の処理を行った結果出力された経路の例を図 6 に示す．

– STEP6
STEP1〜STEP5 の処理を m 回行い g1 , g2 , . . . , gm を求め，これを出力とする．

（注 1）：http://japonyol.net/editor/calculate.html（注 1）：https://openstreetmap.jp/

6. 5 半径 r と経路端点から始点までの距離の差異による比較

6. 5. 1 実験の概要
本論文で提案する手法では，Cr (o) の半径 r を指定することができる．これが大きくなればなるほど，より端点 o から遠い位置にある点がダミー端点として出力されるようになる．実際の点から遠い位置にある点を端点とすることにより，誤差が大
図 5 Open Street Map Japan から取得した範囲

きくなり出力経路の効用性が小さくなる怖れがある．
また一方で，誤差が効用性に与える影響は入力経路の長さによって異なる．たとえばある経路 x = [x1 , . . . , xn ] とその部分
経路 xi,n = [xi , . . . , xn ] を考えたとき，x に対する出力経路は

x′ = [x1 , ...xk , x′k+1 , ..., x′l ] となり，xi,n に対する出力経路は′′′i<= k のときを考えると，xi,n = [xi , ...xk , xk+1 , ..., xl ] となる．
このとき誤差は x，xi,n に対して同じ値をとるが，x と x′ の異なる点の占める割合は x と x′i,n のそれよりも大きくなることは明らかである．したがって誤差について入力経路の長さにADよる相対評価を行う必要があり，その値を Ac = |x|，Dc = |x|

図 6 元の経路 (緑) と曖昧化を行った経路 (オレンジ) (r = 1.0(km)，とする．ここで，|x| は経路 x の長さとする．
以上より本実験では，Cr (o) の半径 r と経路端点から始点まϵ = 0.01)での距離という２種類のパラメータを変化させた場合の A と

6. 4 経路始点とダミー端点の位置関係の差異による比較

Ac ，D と Dc を比較する．半径 r を 0.3km，1.0km，2.0km と

6. 4. 1 実験の概要変化させた時，それぞれダミー端点 d11 , . . . , d13 ，d21 , . . . , d23 ，

本論文で提案する手法ではダミー端点の候補となる点は複d31 , . . . , d33 を出力した．また経路始点は端点からの距離の異数個出力される．したがってどの点をダミー端点とするかになる３点 s1 , s5 , s6 を用いた．それぞれの点の地図上の位置をより誤差は異なってくる．本実験では，端点から見て北東，北

図 10 に示す．

西，南西，南東に位置する４点 s1 , s2 , s3 , s4 を入力経路の始点

6. 5. 2 結とし，ダミー端点を r = 0.3km とした時に Cr (o) に含まれる•３点 d1 , d2 , d3 とし，それぞれの組み合わせに対して出力され得られた実験結果を３種類に分けて示す．dmin ，dmax に対る Asi ,dj , Dsi ,dj (i = 1, 2, 3, 4, j = 1, 2, 3) の値を比較した．始する A の値と入力経路の始点と r を固定した時の三つのダミー

点，端点，ダミー端点の地図上の位置を図 7 に示す．

端点を用いた出力経路の A の平均値をそれぞれ図 11，12，13

果

絶対評価

に示す．また D に関するそれぞれの値を図 14，15，16 に示す．
この結果から，図 11，14 のように誤差が小さくなるダミー端
点を選択できた場合は，r が大きくなればなるほど誤差も大きくなることが確認された．また，図 12 の点 s5 の A の値から，ダミー端点の選択の仕方によっては誤差が極端に大きくなってしまう場合もある．
またこの結果からは入力経路の始点と端点の距離と誤差の相関性は確認できなかったが，6. 5. 1 で述べたようにこの距離が効用性に与える影響は大きいと考えられる．次でその検証を行う．
図 7 実験に用いた経路群の始点，端点，ダミー端点

•

相対評価

得られた実験結果を３種類に分けて示す．dmin ，dmax に対す

6. 4. 2 結果る A の値と入力経路の始点と r を固定した時の三つのダミー端

誤差の計測結果を表 8，9 に示す．図中の黄色い線で囲まれ点を用いた出力経路の A の平均値をそれぞれ図 17，18，19 にているものが最小の誤差をとる全体の結果として，A，D とも示す．また D に関するそれぞれの値を図 20，21，22 に示す．

に，始点からの距離が近いダミー端点の方が誤差が小さくなる

この結果から，入力経路が長い場合は誤差が効用性に与える傾向にあることが確認された．しかし始点 s3 の結果のように，影響が小さいことがわかる．したがってそのような場合には r出力される経路によってはそれが成り立たない例もあるため，を大きくしてダミー端点を経路端点から離れた場所にとってプ

距離以外の影響を与える因子について検討することを今後の課

ライバシ保護の度合いを大きくしても，効用性の損失が少なく題としたい．

て済むという可能性が示された．

図8

経路始点とダミー端点の位置関係が異なる場合の A の値

図 9 経路始点とダミー端点の位置関係が異なる場合の D の値さによっては r を大きくしてプライバシ保護の度合いを大きくしても効用性の損失が少なくて済む可能性が示された．
以上のように，本研究では，プライバシ保護と効用性の保持を両立する経路を得る手法を提案した．
今後，異なるデータセットを用いた実験の実施や，より実用性を考えて経路端点だけでなく中間点の曖昧化への応用の研究を行う予定である．

文
図 10

実験に用いた経路群の始点，端点，ダミー端点

7. お わ り に本研究では，プライバシ保護と経路情報としての効用性保持を両立する経路情報の曖昧化を目的として，Geo 識別不能性を用いた経路端点の曖昧化手法を提案している．提案手法では入力経路の端点 o を中心とした半径 r の円 Cr (o) の中で Geo
識別不能性を満たす点をダミー端点として複数求め，その中から一点を選択してそれを端点とする経路を出力する．この手法によって求められた経路は，その端点はプライバシ保護が成り立っているだけでなく，途中までは入力経路と同じ道を辿ることから効用性の損失も少ない．
評価実験では効用性を入力経路と出力経路の誤差とみて，京都市の実際の道路ネットワークを用いた様々な経路データを使って比較を行った．変化させたパラメータの異なる２種類の実験を行っており，一つの実験では経路始点とダミー端点の位
置関係の差異による効用性の比較を行い，ある始点に対しどのような位置にあるダミー端点を選択すればよいかを検証した．
実験結果から，ダミー端点を始点から近い距離にあるものを選択した場合の方が効用性が大きくなる傾向にあることが確認された．またもう一方の実験では Cr (o) の半径 r と入力経路の長さを変化させ，それぞれが効用性に与える影響を調べた．この実験結果からは，r が大きくなればなるほど絶対的な効用性は小さくなるが，経路が長い場合は誤差が効用性に与える影響は相対的に小さいことが確認された．したがって，入力経路の長献[1] Kanza, Yaron and Samet, Hanan, ”An online marketplace
for geosocial data,” Proceedings of the 23rd SIGSPATIALInternational Conference on Advances in Geographic Information Systems, ACM, pp. 10:1-10:4 , 2015.
[2] 横山 隆治, 楳田 良輝, ” リアル行動ターゲティング,” 日経 BP
社, 2015.
[3] 情報銀行, http://www.information-bank.net/index.html[4] NTT データ研究所：”パーソナルデータに関する一般消費者の意識調査 (2016),” http://www.keieiken.co.jp/aboutus/
newsrelease/161122/supplementing01.html[5] De Montjoye, Yves-Alexandre and Hidalgo, César A andVerleysen, Michel and Blondel, Vincent D, ”Unique in thecrowd: The privacy bounds of human mobility,” Scientificreports, Vol.3, 2013.
[6] Sweeney, Latanya, ”k-anonymity: A model for protecting
privacy,” International Journal of Uncertainty, Fuzzinessand Knowledge-Based Systems, Vol. 10, No. 05, pp. 557570, 2002.
[7] Abul, Osman and Bonchi, Francesco and Nanni, Mirco,”Never walk alone: Uncertainty for anonymity in moving
objects databases,” Data Engineering, 2008. ICDE 2008.
IEEE 24th International Conference on, IEEE, pp. 376–385,
2008.
[8] Huo, Zheng and Meng, Xiaofeng and Hu, Haibo and Huang,
Yi, ”You can walk alone: trajectory privacy-preserving
through significant stays protection,” International Conference on Database Systems for Advanced Applications,
Springer, pp. 351–366, 2012.
[9] Narayanan, Arvind and Shmatikov, Vitaly, ”Robust deanonymization of large sparse datasets,” Security and Privacy, 2008. SP 2008. IEEE Symposium on, IEEE, pp. 111–
125, 2008.
[10] Dwork, Cynthia, ”Diﬀerential privacy,” Encyclopedia of
Cryptography and Security, Springer, pp. 338–340, 2011.
[11] 中川裕志, ” プライバシー保護入門：法制度と数理的基礎,” 勁草書房, 2016.

図 11dmin に対する A の値

図 12

dmax に対する A の値

図 13

始点と r を固定した場合の A の平均値

図 14dmin に対する D の値

図 15

dmax に対する D の値

図 16

始点と r を固定した場合の D の平均値

図 17dmin に対する Ac の値

図 18

dmax に対する Ac の値

図 19

始点と r を固定した場合の Ac の平均値

図 20 dmin に対する Dc の値

図 21

dmax に対する Dc の値

図 22

始点と r を固定した場合の Dc の平均値

[12] Jiang, Kaifeng and Shao, Dongxu and Bressan, Stéphane
and Kister, Thomas and Tan, Kian-Lee, ”Publishing trajectories with diﬀerential privacy guarantees,” Proceedingsof the 25th International Conference on Scientific and Statistical Database Management, ACM, p. 12, 2013.
[13] Dong, Roy and Krichene, Walid and Bayen, Alexandre M
and Sastry, S Shankar, ”Diﬀerential privacy of populations
in routing games,” 2015 54th IEEE Conference on Decision
and Control (CDC), IEEE, p. 2798–2803, 2015.
[14] Andrés, Miguel E and Bordenabe, Nicolás E andChatzikokolakis, Konstantinos and Palamidessi, Catuscia,”Geo-indistinguishability: Diﬀerential privacy for locationbased systems,” Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security, ACM, p.
901–914, 2013.

[15] Berndt, Donald J and Cliﬀord, James, ”Using dynamic time
warping to find patterns in time series,” KDD workshop,
Vol. 10, No. 16, pp. 359–370, 1994.