高次元データに対するMicroaggregationに基づくk

DEIM Forum 2015 G1-4
高次元データに対する Microaggregation に基づく k -匿名化手法
田中
千紗†
上土井陽子††
若林 真一††
† 広島市立大学情報科学部 〒 731–3194 広島県広島市安佐南区大塚東三丁目 4 番 1 号
†† 広島市立大学大学院情報科学研究科 〒 731–3194 広島県広島市安佐南区大塚東三丁目 4 番 1 号
E-mail: †[email protected], ††{yoko,wakaba}@hiroshima-cu.ac.jp
あらまし 統計的開示制御の既存方法の一つである Microaggregation は，k-匿名性を満たし，かつ，情報損失の少な
いデータ変換を行う手法である．既存の手法として，データ要素を空間上の点とみなした上で，Microaggregation を
経路作成と最短経路探索によって実現する手法が知られている．低次元データに対しては効率よく解く手法が知られ
ているが，大規模で高次元なデータに対しては高速にデータ変換を行うことが困難と予測される．本研究では，距離
に基づくハッシングを用いた経路作成を取り入れた，高次元データに対する Microaggregation を利用した k-匿名化手
法を紹介する．
キーワード
Microaggregation，k-匿名化，距離に基づくハッシング
1. は じ め に
近年，情報システムの普及により情報化社会となっている．
そこで企業等に集められた情報は，統計的に解析することで新
できる可能性がある．準識別子の例は，年齢，性別，仕事，郵
便番号，などがある．このように，他の属性と組み合わせるこ
とでレコードの持ち主を特定する可能性のある属性を準識別子
という．
しい有用な情報を得るために利用できる可能性がある．企業
機密の出力属性 3 つ目は持ち主に関する機密情報を含む属性で
等に集められた情報を第三者が解析できるように提供するた
ある．機密の出力属性の例は，給料，宗教，政治的な提携，健
め，元の情報からの損失を減らしつつ，個人のプライバシーを
康状態，病名などがある．
保護するために情報を変換する必要がある．企業等の第三者は
できるだけ情報損失の少ないデータを求めるが，提供する側
本研究で k-匿名化を行うための変換の対象とする属性値は，
準識別子にあたる属性の値である．
はプライバシーを保護しなければならない．そこで統計およ
2. 2 k-匿 名 化
び管理データベースの統計的開示制御 (Statistical Disclosure
k-匿名化とは、匿名化の尺度となる安全性を表す．k はデー
Control：SDC) では，プライバシーに対する個人の権利と，知
タ管理者が前もってセットする定数であり、プライバシー保護
るための社会的権利のバランスを試みる．
の評価尺度である．
本稿では，SDC の既存方法の一つである microaggregation [2]
を利用した k-匿名化に注目し，従来手法のデータ変換の高速化
をめざし，高次元データに対応する k-匿名化手法について考察
する．
2. 3 標 準 化
データ等を変換し，単位系や数値の大きさによらない利用し
やすいデータにすることである．Microaggregation では多量な
属性の項目を持つデータのレコード集合を類似したレコード集
2. 準
備
2. 1 マイクロデータ
本研究で用いる入力データベースであるマイクロデータは，
合に分割しなければならない。このとき，単位系が異なってお
り，比較するのに適さない項目がある場合に用いる．表 1 に元
のマイクロデータ，表 2 に表 1 を標準化したデータを示す．
表1
表として表現されていると仮定する．このとき属性とはマイ
マイクロデータ
クロデータの列に対応する項目にあたる．また，表の各行をレ
会社名
コードと呼ぶ．入力である非保護のマイクロデータの属性は主
A&A Ltd
790
55
3212334
313250
に 3 つに分類することができる．以下に 3 つの属性を示す．
B&B SpA
710
44
2283340
299876
識別子 1 つ目は識別子である．識別子は，データの持ち主を明
C&C Inc
730
32
1989233
200213
D&D BV
810
17
984983
143211
E&E SL
950
3
194232
51233
F&F GmbH
510
25
119332
20333
するとき，レコードの持ち主が第三者に特定されるのを防がな
G&G AG
400
45
3012444
501233
ければならないので，この識別子は削除または暗号化される．
H&H SA
330
50
4233312
777882
I&I LLC
510
5
159999
60388
い 1 つだけでは持ち主を特定することはできない．しかし，ほ
J&J Co
760
52
5333442
1001233
かの複数の属性を組み合わせることでレコードの持ち主を特定
K&K Sarl
50
12
645223
333010
白に識別する属性である．識別子の例は，パスワード番号，社
会保障番号，フルネーム，などがある．データを第三者に公開
準識別子
2 つ目は準識別子である．準識別子は，識別子とは違
面積
[m2 ]
従業員数 取引高 [Euros] 利益 [Euros]
全ての点が経路に追加されるまで探索を繰り返す．
表 2 標準化したデータ
会社名
面積
[m2 ]
従業員数 取引高 [Euros] 利益 [Euros]
こ の ス テップ を 用 い て ，表 2 の レ コ ー ド を 上 か ら
0, 1, ..., 10) と し ，経 路 作 成 を 行 う と πT
A&A Ltd
0.778
1.297
3212334
313250
Xi (i
B&B SpA
0.458
0.705
2283340
299876
(X10 , X8 , X5 , X2 , X1 , X9 , X0 , X6 , X7 , X3 , X4 ) となる．これを
C&C Inc
0.538
0.059
1989233
200213
図 1 に示す．7
D&D BV
0.857
-0.749
984983
143211
51233
E&E SL
1.417
-1.502
194232
F&F GmbH
-0.342
-0.318
119332
20333
G&G AG
-0.781
0.758
3012444
501233
H&H SA
-1.061
1.028
4233312
777882
I&I LLC
-0.342
-1.395
159999
60388
J&J Co
0.658
1.135
5333442
1001233
-2.180
-1.018
645223
333010
K&K Sarl
=
=
2. 4 Microaggregation
SDC の既存方法の 1 つであり，連続数値データのために設
計されたデータ変換法である．公開前の元々のデータベースレ
図 1 NPN 探索で作成した経路
コード集合を分割し，類似した値の組み合わせを持つグループ
に分割する．全てのグループが k から 2k − 1 個のレコードを
持つ．また，各グループ内の全てのレコードの値を，グループ
内のレコードを数値ベクトルと見なしたときの重心で置き換え
る．最後に識別子を削除することで microaggregation を利用
した k-匿名化データとなる．Microaggregation は経路作成と，
有向グラフの作成と最短経路探索からなる MHM アルゴリズム
で構成されている．Microaggregation を利用して 3-匿名化し
3. 2 FDH [3] を利用した経路作成
経 路 作 成 と し て ，ハッシ ン グ ベ ー ス の 手 法 で あ る
FDH(Flexible Distance-Based Hashing) を用いる．FDH に
よるデータの分割では円を描いて空間を分割し，ビットマッ
プによってそれぞれに名前を割り当て領域を区別しデータ
を探索することで経路を作成する．以下にその手順を示す．
また，図 2 に A=3 のときの分割の例，図 3 に作成した経路
た例を表 3 に示す．
πT = (X10 , X5 , X2 , X1 , X6 , X7 , X9 , X0 , X3 , X4 , X8 ) を示す．
表 3 Microaggregation による 3-匿名化の例
面積 [m2 ]
従業員数 取引高 [Euros] 利益 [Euros]
(1) アンカーオブジェクト ai (i = 0, 1, ..., A − 1) として A 個
のランダムなオブジェクトを選択する．
747.5
46
3212334
313250
747.5
46
2283340
299876
747.5
46
1989233
200213
このとき，ri はアンカーオブジェクト ai からその他すべての
756.7
8
984983
143211
オブジェクへの距離の平均とする．
756.7
8
194232
51233
(3) 距離値 ri によって空間を分割し作成した領域にビット値
322.5
33
119332
20333
を持たせることで各領域を区別する．ビット値は，距離値 ri 内
322.5
33
3012444
501233
322.5
33
4233312
777882
756.7
8
159999
60388
747.5
46
5333442
1001233
322.5
33
645223
333010
(2) 各アンカーオブジェクトに対して，距離値 ri を求める．
は 0，ri 外であれば 1 を割り振る．
(4) 標準化したデータの重心から一番遠いデータを始点とし，
始点が含まれる領域から経路探索を行う．
(5) 同じ領域内で最も近い点を次の点とする動作を未通過の
点が無くなるまで繰り返す．
3. 経 路 作 成
3. 1 NPN 探索
NPN 探索 (最近傍点：Nearest Point Next) とは，1 つの点
に対して最も近い点を次の点として探す方法である．近くの点
を繋ぐことは，点に対応するレコードに近いレコードを順に並
べ経路を作成することになる．経路作成は以下のステップによ
り行われる．
(1) データセット内の全ての点の重心 X を計算する．
(2) X から最も遠い点を計算し、最初の点 r とする．
(3) 最初の点 r から最も近い点を 2 点目とする．1 番目と 2
番目を除いた点の中で，2 番目の点に最も近い点を 3 点目とし，
(6) 最も低いハミング距離の領域に移動し，(5) を実行する．
該当する領域が複数ある場合，各領域の重心が経路の終端から
近い方へ移動する．
以上の手順により，選択するアンカーの個数やアンカーとす
るデータの変更によって空間の分割数や分割された領域の大き
さを変更することにより高次元データへの良質な解探索と高速
化を図る．
3. 3 距離値 ri による領域範囲の変更
前節の FDH による手法では，アンカーオブジェクト ai に対
する距離値 ri はアンカーオブジェクト ai からその他すべての
オブジェクへの距離の平均としている．ここでは，その距離値
ri の変更による領域の範囲の変更を行う．距離値 ri が平均で
あったとき，扱うデータセットの要素が分散していれば各領域
にデータが分かれる．一方，データ要素に偏りがある場合はあ
る領域にデータが集中してしまい，データの無い領域が増える
ため空間の分割が上手くできていない．そこで，データ要素に
偏りがある場合には距離値 ri を小さくすることによって領域内
のデータ数を分散させることを目的に，各 ri を定数 m(1 < m)
図 4 有向枝の様子
で割る．
4. 1. 1 枝コストの計算
以下に 1 本の枝のコストを演算するための一般式を示す．こ
こで枝 (i, j) に対応するグループは Ci,j = {xi+1 , ..., xj−1 , xj }，
Li,j は枝 (i, j) のコスト，yi,j は Ci,j の重心である．
Li,j =
j
∑
(xn − yi,j )
n=i+1
= (xi+1 − yi,j )2 + · · · + (xi − yi,j )2
(1)
直前の枝を (i, j − 1) としたときも同様に，
図 2 FDH による空間の分割例
Li,j−1 =
j−1
∑
(xn − yi,j−1 )
n=i+1
= (xi+1 − yi,j−1 )2 + · · · + (xj−1 − yi,j−1 )2
(2)
と表せるので、Li,j−1 を利用して Li,j を表すと，
2
2
Li,j = Li,j−1 + (j − 1 − i)yi,j−1
+ x2j − (j − i)yi,j
(3)
次に、始点が隣に移ったときの枝を (i, j) と仮定すると，
Li,j =
j
∑
(xn − yi,j )
n=i+1
図 3 FDH を利用して作成した経路
= (xi+1 − yi,j )2 + · · · + (xi − yi,j )2
(4)
ノードが 1 つ前で終点が同じ枝 (i − 1, j) も同様に，
4. MHM アルゴリズム
MHM アルゴリズムは有向グラフの作成と最短経路探索で構
成されている．以下に MHM アルゴリズムの出力が満たす理論
的性質について記す．
[定義 1] 順列 πT に矛盾しない k-分割：p-次元点の順列 πT =
(X1 , ..., Xn ) が与えられたとき，k-分割中の任意のグループ
G と，i <
= j <
= k を満たす任意の 3 点 Xi , Xj , Xk において，
Xi , Xk ∈ G に含まれるなら，Xj も G に含まれるという条件
を満たすなら，k-分割は順列 πT に矛盾しないとする．
[定理 1] MHM アルゴリズムは，与えられた順列に矛盾しない
k-分割の中で最も情報損失の小さい k-分割を出力する．
4. 1 有向グラフの作成
以下に有向グラフの作成の手順を示す．また，有向枝の様子
を図 4 に示す．
Li−1,j =
j
∑
(xn − yi−1,j )
n=i
= (xi − yi−1,j )2 · · · + (xj − yi−1,j )2
(5)
Li−1,j を利用して Li,j を表すと，
2
2
Li,j = Li−1,j + x2i + (j − i + 1)yi−1,j
− (j − i)yi,j
(6)
上記の式 (3)，(6) を使用することで枝コストを求め情報損失を
算出し，レコードの SST (総平方和：total sum of squares) で
割ることで情報損失の尺度を表す．
4. 2 最短経路探索
対象とする最短経路問題の入力とそれに伴う出力を定義する．
入力 有向グラフ G = (V, E)，枝コスト関数 l : E → R+ ，有向
グラフ G のノード数 n + 1，ノードの順序 πT (順番にノードを
(1) 作成された経路の順列 πT 中の値 Xi に対して，ラベル
一対一に対応させる関数 πT : 0, ..., n → v)，ここで有向グラフ
i を作成し，ラベル 0 の追加ノードを作成する．
(2) i + k <
= j < i + 2k を満たすノードの各組 (i, j) に対し
G では，各枝 (i, j) において πT −1 (u) < πT −1 (v) が成り立つ
て，ノード i からノード j の有向枝 (i, j) を作成する．
(3) 各枝 (i, j) に対して，Li,j を枝 (i, j) の長さ (コスト) と
する．また，枝の長さは情報損失と等しい．
出力 接点 πT −1 (0) から接点 πT −1 (n) の最短経路 ST (逆順)
最短経路探索のアルゴリズムの概要を以下の通りである．ここ
での d は経路の長さを格納する場所であり，f はどのノードか
らの出力枝であるかを示すノード番号を格納する場所である．
ステップ 1 d(πT (0)) に 0 を代入，πT (0) ではない全ての頂点
v に対して d(v) に ∞ を代入．
表4
要素数
ステップ 2 f or(i = 0; i <= n; i + +) 以下のステップ 2.1 を繰
10000
り返す．
ステップ 2.1 頂点 πT (i) を選び，頂点 πT (i) を始点とする各
枝 (πT (i), v) に対してステップ 2.1.1 を実行．
ステップ 2.1.1 if (d(v) > d(πT (i))+l(πT (i), v)) then(d(v) ←
50000
d(πT (i)) + l(πT (i), v), f (v) ← πT (i))
ステップ 3 ST [0] ← πT (n)
ステップ 4 f or(i = 1; i <= n&&ST [i − 1]! = πT (0); i + +)
100000
以下のステップ 4.1 を繰り返す．
ステップ 4.1 ST [i] = f (ST [i − 1])
以上のステップより，枝コストの総計が一番小さくなる経路
を逆順に ST 配列に格納するため，ST 配列を参照することで
300000
逆順の MHM 出力を得ることができる．したがって図 3 の経
大規模データによる従来手法の実行結果
k の値 情報損失 [%] 経路作成時間 [s] 全体の実行時間 [s]
2
5.498
22.905
22.963
5
20.223
22.922
23.002
10
29.090
22.923
23.040
50
47.125
22.923
23.334
100
56.992
22.921
23.698
2
5.675
604.590
604.822
5
13.193
604.404
604.808
10
21.576
605.158
605.752
50
38.242
605.429
607.520
100
45.742
605.841
609.817
2
4.720
2472.264
2472.863
5
10.599
2471.603
2472.410
10
17.353
2468.407
2469.594
50
36.611
2492.928
2497.205
100
43.760
2497.543
2505.525
2
3.586
23673.747
23675.504
5
6.872
23524.346
23526.782
10
9.736
23483.956
23487.583
50
22.633
23497.457
23510.086
100
31.293
23543.402
23567.468
2
4.461
64145.747
64148.671
5
7.904
64049.700
64053.758
1 の NPN 探 索 に よ る 経 路 を 入 力 と し た 場 合 は ，グ ル ー プ
10
10.339
63645.501
63651.437
{X10 , X8 , X5 }, {X2 , X1 , X9 , X0 , X6 }, {X7 , X3 , X4 } が出力さ
50
18.552
63545.615
63566.687
100
23.565
63643.343
63683.491
路の最短経路を示す枝は図 4 で示されている枝で分けられる
グループ {X10 , X5 , X2 }, {X1 , X6 , X7 , X9 , X0 }, {X3 , X4 , X8 }
500000
と な る ．こ の と き の 情 報 損 失 は 43.74%と な る ．一 方 ，図
れる．このときの情報損失は 55.10%となり，FDH を利用した
探索の方がよい結果を導いている．
表 5 大規模データによる FDH を用いた手法の実行結果 (A=3)
要素数
5. 実 行 結 果
10000
k の値 情報損失 [%] 経路作成時間 [s] 全体の実行時間 [s]
2
5.820
11.453
11.633
5
21.940
11.774
11.985
10
31.126
11.477
11.720
gcc 4.2.1 コンパイラを用いてコンパイルし，CPU:2.93GHz
50
48.202
11.478
12.034
6-Core Intel Xeon の計算機上に実現しシミュレーション実験
100
59.377
11.374
12.618
2
6.448
332.546
335.866
従来手法の NPN 探索，提案手法を C 言語を用いて実装し，
50000
を行った．実験で用いたデータは，UCI KDD アーカイブの
5
14.821
334.265
337.705
Paralyzed Veterans of America のベンチマークデータ (デー
10
21.478
338.648
342.379
タ数 50 万，属性数 36) である．表 4 は，従来手法の NPN 探
50
37.455
334.407
339.637
100
44.756
337.376
344.601
2
3.112
1458.156
1470.821
索に関する実験結果である．表 5，6 は FDH を利用した手法を
100000
実装しアンカー数 A=3,10 でシミュレーション実験を行った結
果であり，提案手法１とする．表 5，表 6 より従来手法に比べ，
提案手法は平均 42%程度計算時間を削減した．また，情報損失
に関しても要素数，k の値が大きくなるにつれて提案手法は従
来手法よりもよい結果を得ている．しかし，一方で，アンカー
数を上げることによる高速化を実現できておらず，高速化が十
表6
9.907
1459.233
1472.467
17.162
1420.846
1434.303
50
34.872
1433.023
1449.728
100
42.908
1431.505
1452.073
大規模データによる FDH を用いた手法の実行結果 (A=10)
要素数
10000
分ではない．これは，データの分布に偏りがあったため，アン
カー数増加の効果がほとんどなかったことが原因と考えられる．
表 7，8，9 は距離値による領域範囲の変更を行いアンカー数
A=3,10 でシミュレーション実験を行った結果であり，提案手
5
10
50000
k の値 情報損失 [%] 経路作成時間 [s] 全体の実行時間 [s]
2
6.044
12.638
12.818
5
22.250
12.572
12.776
10
31.623
12.566
12.810
50
51.644
13.012
13.569
100
62.984
13.030
13.974
2
6.373
378.083
381.401
5
15.337
384.858
388.300
法２とする．実行結果より，従来手法や提案手法 1 に比べてさ
10
22.739
384.483
388.169
らに高速化していることがわかる．従来手法と比べて，距離値
50
38.386
392.002
397.224
100
46.762
397.577
404.775
2
3.130
1459.852
1472.535
ri /2 のとき平均 69.4%，ri /3 のとき平均 76.2%，ri /4 のとき
平均 68.4%計算時間を削減しており，距離値 ri /3 のとき最も
高速化できていた．また，大規模なデータの場合には，提案手
法は，従来手法の情報損失を改良することが分かった．これは，
データ要素が多く集まる場所を分割できていたためである．
100000
5
9.954
1521.097
1534.008
10
17.249
1437.655
1434.303
50
34.963
1510.375
1526.896
100
43.585
1545.704
1566.176
表 7 提案手法 2 の m=2,A=3,10 の実行結果の比較
情報損失 [%] N
10,000
50,000
100,000
300,000
500,000
k
経路作成時間 [s]
全体の実行時間 [s]
A=3
A=10
A=3
A=10
A=3
5 20.486
21.215
6.643
9.196
6.851
9.402
100 56.175
56.635
6.242
10.908
7.069
11.856
5 14.750
14.773
160.609
286.244
164.123
289.775
100 45.305
45.185
156.536
344.844
163.812
352.120
9.986
10.001
587.834
837.521
600.994
850.521
100 43.719
43.681
563.597
732.551
584.102
753.011
5
5
A=10
6.627
6.676
8442.361 13001.618
8557.267 13116.423
100 29.360
28.935
9048.466 11901.332
9184.657 12037.852
5
7.833
7.870 21391.330 29521.756 21707.667 29844.801
100 23.307
23.233 22207.880 29853.793 22564.095 30212.846
表 8 提案手法 2 の m=3,A=3,10 の実行結果の比較
情報損失 [%] N
10,000
50,000
100,000
300,000
500,000
k
経路作成時間 [s]
全体の実行時間 [s]
A=3
A=10
A=3
A=10
A=3
A=10
5 20.889
21.424
4.634
8.632
4.847
8.837
100 55.641
56.165
5.746
8.260
6.694
9.208
5 14.767
14.840
107.353
219.716
110.840
223.153
100 44.734
45.080
108.511
211.851
115.884
219.130
9.986
10.023
454.694
460.522
467.853
473.407
100 43.486
43.498
478.661
497.548
499.638
518.017
6.624
6.726
5341.544
8626.527
5456.408
8741.155
100 29.314
29.388
6464.059
6847.451
6600.288
6987.358
5
5
5
7.869
7.870 23640.305 20326.171 23956.505 19642.199
100 23.380
23.174 15121.500 23541.279 15476.538 23893.961
表 9 提案手法 2 の m=4,A=3,10 の実行結果の比較
情報損失 [%] N
10,000
50,000
100,000
300,000
500,000
k
経路作成時間 [s]
全体の実行時間 [s]
A=3
A=10
A=3
A=10
A=3
A=10
5 20.544
20.244
7.336
6.308
7.545
6.516
100 55.473
55.940
6.725
8.187
7.673
9.139
5 12.320
15.160
198.747
211.962
202.214
214.788
100 45.127
45.675
205.800
186.582
213.263
193.859
9.971
10.012
799.212
581.134
812.363
594.286
100 43.426
43.351
747.130
648.512
768.258
669.340
6.621
6.631
6725.216
5741.293
6839.852
5855.837
100 29.176
30.249
6405.530
7776.024
6542.696
7914.105
5
5
5
7.870
7.874 21563.175 17358.327 21879.243 17674.841
100 23.229
23.232 17281.175 19438.174 17633.782 19790.077
6. 今後の課題
高次元データの偏りによって経路作成時間が実行時間のほと
んどを占めている状況であるため，高次元データの偏りに依存
しないようアルゴリズムを改良することが今後の課題である．
文
献
[1] 須崎 亮, 上土井 陽子, 若林 真一, ”Microaggregation を利用し
た k-匿名化手法の高速化”, 第 5 回データ工学と情報マネージメ
ントに関する論文集 (DEIM2013), F8-3 (2013).
[2] J. Domingo-Ferrer, A. Martinez-Ballests, J.M. Mateo-Sanz
and F. Sebe, ”Efficient multivariate data-oriented microaggregation,” The VLDB Journal, Vol.15, pp. 355-369 (2006).
[3] Man Lung Yiu, Ira Assent, Christian S. Jensen, and Panos
Kalnis, ”Outsources Similarity Search on Metric Data Assets,” IEEE Transaction on Knowledge and Data Engineering, Vol.24, No.2, pp. 346-347 (2012).