PhD Thesis Review, No.10

学位論文紹介

系列データの匿名化に関する研究

表 1 系列データ:移動軌跡

表 2 系列データ:医療データ

lt

ID

傷病

薬剤

Alice

A Study on Data Anonymization for Series Datau(10, 5)

11ax

Alice
Alice

(15, 5)(18, 8)23

23abyx

高橋 翼 ♥

Alice(18, 10)44byBob(10, 5)

15ax

Tsubasa TAKAHASHI

Bob(9, 4)

26az

Bob(8, 3)3

7cx

Bob(8, 3)48cw

本稿では，学位論文として取り組んだ系列データの匿名化に関する研究の概要を紹介する．この研究では，系列データに対する連続的な匿名化と，系列中の属性値間の値の特定を困難に

表 3 匿名化の実行例

する匿名化 (関係多様化) について新たな手法の提案と評価を(a) 元テーブル行った．

ID

年齢

性別

病名

年齢

性別

病名

122

男かぜ

22

男かぜ

2328
33

男

HIV
HIV

2833

男

男

男

HIV
HIV

436

男

かぜ

36

男

かぜ

542

女

ガン

42

女

ガン

648

女

ガン

48

女

ガン

This paper presents a summary of a study on
data anonymization for series data. This study is focus on a continuous anonymization method for trajectory stream and an anonymization which ensuresrelation diversity among attributes.

1.

(b) ID を削除したテーブル(c) 2-匿名化したテーブル

はじめに(d) 2-多様化したテーブル

年齢

性別

病名

年齢

性別

病名

[20, 29]

男

かぜ[20, 29]

男かぜ[20, 29]

男HIV[20, 29]

男HIV[30, 39]

男HIV[30, 49]

ANYHIV[30, 39]

男

かぜ[30, 49]

ANY

かぜ

野で新たな発見やサービスの発展が期待できる．系列データ[40, 49]

女ガン[30, 49]

ANY

ガンの例として，移動軌跡，医療データをそれぞれ図 1，図??に示[40, 49]

女ガン[30, 49]

ANYガン

近年，パーソナルデータが大量に蓄積され，第三者提供や二次活用による活用が期待されている．特に，パーソナルデータのシーケンスである系列データからは，系列中のパターンや因果関係といった高度な分析を実現できる．このような系列データをデータ保有者以外も利活用可能になれば，様々な分す．しかし，パーソナルデータの第三者提供や二次活用に際しては，プライバシへの配慮が必要となる．

1.1

データ匿名化

従来，氏名や会員番号などの直接識別子 (明示的識別子,Explicit Identifier) を削除するといった処理が匿名化として認知されてきた．k-匿名化 [1] に代表されるデータ匿名化では，1 つ以上の属性の組合せでレコードを識別し得る属性である準識別子 (Quasi-identifier, QI) を加工することで，レコードの識別を困難にする．さらに，レコードの特定だけでなく，他人に知られたくない属性であるセンシティブ属性 (SensitiveAttribute, SA) の特定を困難にする (ℓ-多様化 [2]) など，攻撃のモデルに合わせた匿名化手段が研究されている．

1.2

系列データの匿名化

系列データに対する既存の匿名化技術は，蓄積された複数の属性値の系列に対して静的に匿名化を行う技術であり，連続的♥

正会員 筑波大学，日本電気株式会社クラウドシステム研究
所 t-takahashi@nk.jp.nec.comに蓄積されていくデータを逐次匿名化することができなかった [3][4]．また，個人が特定されずともある属性の値が他の属性群から特定されてしまう場合がある．このようなときに，系列データの属性間の関係を多様化するような加工には，属性値や属性間の関係を大きく曖昧化してしまう問題があった．

1.3

本研究の貢献

本研究では，系列データの連続的な利活用をプライバシを考慮しながら実現するために，主に移動軌跡ストリームを対象とした連続的匿名化手法を提案する．また，センシティブ属性間の多様性の保証を，属性値を加工せずに実現する関係多様化を導入し，さらに関係の曖昧性を抑止しながら関係多様化を実現する手法を提案する．
提案手法を用いることで，系列データの提供をプライバシに配慮した形で実現し，特にリアルタイムな移動軌跡の提供や，属性間の関係に多様性 が保証された系列データの提供が，あ110-1

日本データベース学会

PhD Thesis Review, No.10

学位論文紹介t3
t2
t1
1234%56789

!"

#$
併合

ti+2

ti+2

ti+1

ti+1

ti

tit0
k=4
$ %&'()*!"#A !"#B!"#D+ ,-./0'()*!"#C

図2図 1 移動軌跡の連続的匿名化

る一定の精度を維持しつつ匿名性が保証された形で実現する．

2.

移動軌跡ストリームの連続的匿名化

2.1

概要

動的再構成

移動軌跡ストリーム中の位置情報 l を汎化して，複数の移動軌跡ストリームが滞在する場所が共起するようにすることで，ある場所に滞在する移動軌跡ストリームがどのデータ主体のものであるのか，識別を困難にすることができる．本研究で位置情報の時系列である移動軌跡は，ユーザの移動経路や生活の動線を表す情報である．一方で，移動軌跡はユーザに特有の情報であるため，移動軌跡中のいくつかの位置情報から移動軌跡を識別することや，個人を特定することが可能である．識別，特定されることによって，センシティブな滞在先の漏洩が生じ得る．さらに，リアルタイムに移動軌跡を提供するようなは，以下の移動軌跡の k-匿名性の充足を考える．
定義 3 (移動軌跡の k-匿名性) 移動軌跡ストリーム τu (または∗) は，時間 [ti , tj ] に共通の場所に汎化移動軌跡ストリーム τtid

滞在する他の移動軌跡ストリームが k − 1 個存在するとき，時間 [ti , tj ] に k-匿名性を満たす．

2.3

状況下では，追跡や監視といった脅威に晒される．

提案手法 CMOA

タイムスタンプ t を付加して信頼できるプラットフォームに蓄提案手法 CMOA は，移動軌跡ストリームを一定の面積(σ) 以下に加工をして連続的に k-匿名化を行う手法である．
CMOA は，移動軌跡の各位置情報を k 個以上の移動軌跡が常に包含されるように汎化する．ここで，汎化された移動軌跡が等価な移動軌跡を等価クラスと呼ぶ．k-匿名性を維持し続けるためには，既に匿名かして公開したデータと k 以上の移動軌跡が同じ等価クラスに属し続けることが必要になる．しかし，同じメンバで等価クラスを形成し続けると，メンバの移動方向が変わることで汎化の度合いを大きくなってしまう (図 1)．
そこで，移動軌跡ストリームの等価クラスの組み替え (動的再構成) を導入し，位置情報の精度を σ に保つ．

積されるものとする．l の例として，緯度・経度によって表さ2.3.1

本研究では，移動軌跡をリアルタイムに提供するための連続的匿名化に関する問題を扱う．提案匿名化手法 CMOA(Continuous Moving Objects Anonymization) は，新たに測位された移動軌跡の増分位置情報を，既に匿名化された匿名移動軌跡を考慮しながらリアルタイムかつ連続的に匿名化を行う手法である．また，時々刻々と変化する人々の移動に合わせて匿名グループの構成を動的に再構成することで，過度な抽象化を抑制する．

2.2

移動軌跡ストリームの k-匿名性

各ユーザの位置情報 l は一定のインターバル毎に測位され，動的再構成

動的再構成では，分割と併合による再構成を行う (図 2)．分れる座標等がある．
定義 1 (移 動 軌 跡 ス ト リ ー ム):

データ主体 u の移動軌

跡 ス ト リ ー ム は 位 置 情 報 の 時 系 列 で 表 さ れ る:

τu ={(u, l0 , t0 ), (u, l1 , t1 ), . . . , (u, llast , tlast )}(t0 < t1 < . . . <tlast )．ここで，tlast は最新のタイムスタンプ (現在時刻) とする．また，時刻 t の位置情報は τu [ti ](= l) と表す．
∗∗

ここで汎化した位置情報を l とし，l のシーケンスから成を 2 分割する．分割を繰り返すことで面積を小さく保つことができるが，一定以上の分割を行うと，k-匿名性を充足した分割が不可能になる．分割不可能な場合には，近傍の等価クラスとの併合を行い，十分なメンバ数を持った新たな等価クラスを作る．併合後に分割が行われると k-匿名性に違反してしまう場合があり，このときには TID の再割当を行う．ID の再割当が生じると，移動軌跡をトレーサビリティが毀損し，匿名化る移動軌跡ストリームを汎化移動軌跡ストリームとする．
∗τtid=∗∗∗{(tid, l1 , t1 ), (tid, l2 , t2 ), . . . , (tid, lm , tm )} (t1 < t2 <. . . < tm ). tid は汎化移動軌跡ストリームの識別子であり，ランダムに割り当てた値を用いる．

定義 2 (汎 化 移 動 軌 跡 ス ト リ ー ム):

割では，メンバ数が 2k 以上かつ面積が σ を超えた等価クラスデータの有用性が低下してしまう．
そこで併合を行う際には，併合後の等価クラスがどの程度トレーサビリティを維持できるかを評価して，この評価値が高い等価クラス群で併合を行う．このトレーサビリティの維持可

210-2

日本データベース学会

PhD Thesis Review, No.10

学位論文紹介20000

表518000

表 4 汎化データ

16000
14000
NergizNWA(δ=250)
NWA(δ=500)

RM

12000
10000
8000

CMOA(σ=250!250)
CMOA(σ=500!500)
NoReform

6000
400020000020406080Time Stamp100120

能度合いを以下の評価式 E(c[t]) で評価する．

E(c[t]) =)σ(1 + log2 |c[t]|kS(c[t])薬剤a/ba/ba/ba/ba/ca/ca/ca/cx/yx/yx/yx/yw/xw/xx/zx/z(a) 傷病(b) 薬剤

CID

傷病

CID薬剤

1111abab1
111xyxy2
233acac2233xwxz(1)割し，対応関係を曖昧化する関係多様化という操作を導入する

ここで，S(c[t]) は時刻 t におけるクラス c の面積である．

2.4

傷病

関係多様化データ(表 5(a)，表 5(b))．このとき，センシティブ属性を汎化せずに評価手法の有効性を評価するために，匿名化した移動軌跡の精度(解像度) の評価と計算時間の計測を行った．
実験用のデータセットとして，東京大学が提供している人の流れデータ (PFLOW[5]) を利用した．PFLOW からランダムに 10 万人分の 2 時間分の移動軌跡を抽出して利用した．
図 2.4 は提案手法 CMOA と，動的再構成をしない連続的匿名化 (No Reform)，静的な手法 (NWA[3] と Nergiz 方式 [4])と解像度の比較を行った結果を示している．RM は位置情報の解像度を表す指標であり，大きいほど詳細な位置情報であることを表す．提案手法は，動的再構成によって一定以上の解像度を維持していることがわかる．一方，動的再構成のない手法は解像度が単調減少していることがわかる．移動軌跡の全容が分かった上で匿名化する静的手法と比べて，提案手法は解像度が低い．ただし，一部静的手法の解像度に近づいており，一定の有用性は有していると言える．
以上より，移動軌跡をリアルタイムかつ連続的に k-匿名化する提案手法が，ある一定の位置情報の精度を保証しながら匿名化できることが分かった．なお，位置情報の精度だけではなく，一定のトレーサビリティを保証できるようにすることは今後の課題の一つであると考えている．

関係多様性を保証することができる．本研究では，関係の曖昧化を抑制しながら関係多様化する手法を実現する．

3.2

関係多様化

以降では，関係多様化されたテーブル Ti と Tj の二項関係を対象に議論する．3.1 節で述べたセンシティブ属性値の特定を防ぐためには，センシティブ属性 Si に対応する他のセンシティブ属性 Sj の属性値が一定の種類以上存在することを保証する必要がある．
二項関係にあるセンシティブ属性に対して，一方のセンシティブ属性値から特定可能な他方のセンシティブ属性値の種類数を表す関係の多様性指標 (ℓ1 ,ℓ2 )-関係多様性を定義する．
定義 4 ((ℓ1 ,ℓ2 )-関係多様性) 任意のタプルについて，センシティブ属性 Si から特定可能なセンシティブ属性 Sj の属性値の種類数が ℓ2 以上，Sj から特定可能なセンシティブ属性 Siの属性値の種類数が ℓ1 以上のとき，(Si , Sj ) に二項関係を持
つ Ti と Tj は (ℓ1 ,ℓ2 )-関係多様性を満たす．

属性間の相関や変化を観察することができる．一方で，あるセ

ここで同一の CID を持つタプルの集合をクラスと呼ぶ．
(ℓ1 ,ℓ2 )-関係多様性を保証する (ℓ1 ,ℓ2 )-関係多様化を行うと，Si の値はサイズ ℓ1 以上の集合に，Sj の値はサイズ ℓ2 以上の集合となる．よって，(Si , Sj ) の二項関係は，集合間の二項関係へと曖昧化される．
関係多様化によって混入するオリジナルの関係には存在しない関係をノイズとし，クラス中のオリジナルの関係とノイズとの比を表す関係ノイズ比 RN R を以下のように定義する．

ンシティブ属性に関する知識から他のセンシティブ属性値が定義 5 (関係ノイズ比)

3.

センシティブ属性間の関係多様化3.1

概要

複数のセンシティブ属性を持ったパーソナルデータからは，特定され得る．この特定を防ぐためには，あるセンシティブ属性から他のセンシティブ属性が一意に対応付かないように，セRN R(c) =ンシティブ属性間の対応関係が多様 (多対多) になること (関係多様性) を保証する必要がある．しかしながら，属性間の対応関係の多様化を実現するためには，表 4 のように属性値が過|Si (c)||Sj (c)||R(c)|(2)

ここで，|Si (c)| は c の Si の属性値の種類数を表す．|R(c)| はc の元の関係の種類数である．RN R(c) は 1 以上の値を取り，最小値 (1) のとき，クラスにノイズが混入していないことを表度に加工されてしまう問題がある．
そこで，センシティブ属性をそれぞれ異なるテーブルへと分す．ノイズの混入のないクラスをノイズレスクラスと呼ぶ．

310-3

日本データベース学会

PhD Thesis Review, No.10

学位論文紹介

$"!"
#"

%"

$"!"
&"%"

C (X) = 2

$"

!"
'"

%"

C (Y ) = 3

$"

3.5
3(%"

C (Z ) = 2

RNR!"

C (W ) = 1

NLC(2,2)

2.5

DGRL(2,2)
DG(2,2)

2

NLC(3,3)
DGRL(3,3)

1.5

DG(3,3)図 3 前提部の ℓ1 -多様化 ((ℓ1 , 1)-関係多様化)

10

2000

4000

6000

8000

10000

|T|!"
$"
%"

#"
&"

!"
$"
%"

#"'"

!"
$"
%"

&"'"

!"
$"
%"

#"

図5

関係ノイズ比(4.

おわりに

本稿では，系列データの匿名化に関する研究の概要を紹介し

図 4 結論部の ℓ2 -多様化 ((ℓ1 , ℓ2 )-関係多様化)た．特に，移動軌跡ストリームに対して一定の精度を保ちながら連続的に k-匿名化する手法と，センシティブ属性間の値の提案手法：関係ノイズ比を抑制した関係多様化

特定の回避を属性値や属性間の関係を維持して実現する関係

関係多様化データの有用性を高くするために，関係ノイズ比多様化を提案した．これらの研究成果によって，系列データのを抑制した関係多様化を実現したい．提案手法では，ノイズレ

第三者提供や二次活用における有用性を維持しながらプライスクラスを多数生成することで関係ノイズ比を抑制する．

バシ侵害の懸念を軽減できたと考えられる．

Sj に同じ値を持ち，Si に異なる値を持つ ℓ1 個のタプルからは (ℓ1 ,1)-関係多様なノイズレスクラスを生成できる．さらに，Si の集合が同一かつ，Sj の値が異なる (ℓ1 ,1)-関係多様なノイズレスクラスの集合から，(ℓ1 ,ℓ2 )-関係多様なノイズレスクラ
スが生成できる．ここで，Si の値が同じタプル群毎に Sj の出
現パターンを考える．Sj の出現パターンが類似するこのタプル群からは，ノイズレスクラスが多数生成できる．
そこで，以下のステップでノイズレスクラスの生成を行う．

謝辞

3.3

1. 類似度の高いタプル群を選択
2. 前提部の多様化 ((ℓ1 , 1)-関係多様化)（図 3）
3. 結論部の多様化 ((ℓ1 , ℓ2 )-関係多様化)（図 4）
4. ノイズレスクラスが生成可能なら 1. へ
残りのタプルに対しては，RNR が小さくなるようにクラスタリングをすることで，関係多様性を充足させる．

3.4

評価

提案手法の有効性を評価するために関係ノイズ比と関係多様化の計算時間を評価した．提案手法を NLC とし，比較手法として関係ノイズ比を考慮したクラスタリングによる手法
DGRL と，関係ノイズ比を考慮しないナイーブな手法 DG を実装して比較した．データセットには，人工データを用いた．
評価尺度には，テーブル全体の関係ノイズ比 RN R を用いた．図 5 に (2, 2), (3,3)-関係多様化した 3 手法の RN R を示
す．提案手法は，(2,2)，(3,3)-関係多様化において，RN R が1 に近く，非常に小さい．
また，他の手法より 10 倍以上高速であることも確認できた．
以上より，提案手法は系列データの関係多様化を関係の曖昧化を抑止しながら効率よく実現できると言える．

筑波大学の北川博之教授を初めとする諸先生方やご指導くださった皆様に深く感謝致します．

[文献][1] L. Sweeney. k-anonymity: A model for protecting privacy. International Journal of Uncertainty, Fuzziness andKnowledge-Based Systems, Vol. 10, No. 5, pp. 557–570,
2002.
[2] A. Machanavajjhala, D. Kifer, J. Gehrke, and M.
Venkitasubramaniam. l-diversity: Privacy beyond kanonymity. TKDD, Vol. 1, No. 1, p. 3, 2007.
[3] O. Abul, F. Bonchi, and M. Nanni. Never walk alone:
Uncertainty for anonymity in moving objects databases.
ICDE 2008, pp. 376 ‒ 385, 2008.
[4] M. E. Nergiz, M. Atzori, Y. Saygin and B. Güç. Towards
Trajectory Anonymization: a Generalization-Based Approach. Transactions on Data Privacy, Vol. 2, No. 1, pp.
47–75, 2009.
[5] People Flow Project (pflow). http://pflow.csis.
u-tokyo.ac.jp/index.html

高橋 翼 Tsubasa TAKAHASHI
2010 年筑波大学大学院システム情報工学研究科博士前期課程修了．同年，日本電気株式会社入社．2014 年筑波大学大学院
システム情報工学研究科博士後期課程修了．博士（工学）．情報処理学会正会員．日本データベース学会正会員．

410-4

日本データベース学会