DEIM Forum 2014 E5-5

Pk-匿名化手法の一改良法の検討
柿澤 美穂†

渡辺知恵美††

古川諒†††

高橋翼†††† お茶の水女子大学大学院人間文化創成科学研究科 〒 112–8610 東京都文京区大塚 2–1–1†† 筑波大学システム情報工学研究科 〒 305–8573 茨城県つくば市天王台 1–1–1††† NEC クラウドシステム研究所 〒 211–8666 神奈川県川崎市中原区下沼部 1753
E-mail: †kakizawa.miho@is.ocha.ac.jp, ††chiemi@cs.tsukuba.ac.jp,†††r-furukawa@cb.jp.nec.com, †††t-takahashi@nk.jp.nec.com
あらましランダム化を用いた匿名化手法の一つに Pk-匿名化 [1] [2] [3] がある. Pk-匿名化の既存手法は, k-匿名性を確率的指標に拡張した Pk-匿名性を保証するために, データ主体を 1/k 以上の確信度に絞り込めないように属性値にノイズを付与する. 既存手法は, 元の属性値にラプラス分布に従ったノイズを付与することで Pk-匿名化を実現し, 所望の k の下で Pk-匿名性を満たすようにラプラス分布の分散を決定している. 本稿では, より小さい分散で Pk-匿名化を実現するよう改良したアルゴリズムを提案する. 提案手法を既存手法と比較, 評価することで提案手法の優位性を示す.
キーワード

データベース, プライバシ保護, 匿名化

1. は じ め に化前のデータの類似性を考慮していくつかのグループに分割し,各グループの属性値集合に対して Pk-匿名化を適用する. 上記

近年, データベースサービスの普及に伴い, 個人情報等の機密のような例の場合, 各グループに Pk-匿名化を適用した際のラ情報をデータベースに格納する際にプライバシ保護が要求されプラス分布に従うノイズの分散が, 既存手法に比べて小さく抑ている. 特に, データベースに格納された機密情報を公開するえられる.

際, データ公開者はデータベースのレコード所持者をデータ利用

本稿では, 第 2 章にて Pk-匿名化について例を用いて説明し,者に特定させずに公開したいと望む. そのような場合にレコー

第 3 章でラプラス分布に従うノイズを適用した Pk-匿名化手法

ド所持者を隠すため, データを匿名化する手法が研究されていが持つ問題点を指摘する. 第 4 章で提案手法について述べ, 第 5

る. データ匿名化の一手法として, k-匿名化 [7] [5] がある. k-匿章でラプラス分布に従うノイズの分散を抑制するためのデータ名化とは, 属性値の抽象化, 削除等を行うことによって, レコー分割法に関しての考察を行う. 第 6 章で, 属性値の分布が二つド所持者を k 人未満に絞れないようにする手法である. この k-のグループに明確に分けられる属性値集合を例に提案手法を適匿名化を確率的指標に拡張した手法として, Pk-匿名化 [1] [2] [3]

用し, 既存手法に比べてラプラス分布に従うノイズの分散が抑がある. Pk-匿名化は, 属性値の置換やノイズ付与といった確率制されることを示す.

的な操作を用いて, レコード所持者を 1/k 以上の確信度で絞り込めないようにする. 既存研究では, 数値属性に対してラプラス分布に従うノイズを付与することで Pk-匿名化を実現する方法が提案されている.
既存の Pk-匿名化では, ラプラス分布の分散値を決定する際

2. Pk-匿名化
Pk-匿名性は, k-匿名性の データの持ち主を k 人未満に絞り込めないという直感的な指標を確率的に拡張し,データの持ち主を 1/k 以上の確信度に絞り込むことができない

こに, 属性値間の最大距離とレコード数を用いる. しかし, 属性値とを保証する. k-匿名性はランダム化を用いた匿名化手法に適の分布によっては, この方法では過剰にノイズが付与され匿名用できなかったが, Pk-匿名性はランダム化に対応した手法であ化が過剰になされる場合がある. 例えば, レコードの属性値のり, ランダム化の一手法である維持-置換攪乱 [8] において Pk-分布に特徴があり, いくつかのグループに明確に分類できるよ匿名性が実現可能であることが証明されている. [1]うな場合を考える. つまり各グループ内のレコード間の類似度

例として, ある病院の患者の氏名, 住所の緯度, 経度, 病名が格が高く, グループ間の距離が大きく離れている場合である. こ

納されているデータセットがあり, これを Pk-匿名化し, 年齢,のようなデータに対して Pk-匿名化を適用する際, レコード全体重と病気の関係について第三者に分析を依頼することを想定

体に対してラプラス分布に従うノイズを適用すると, ラプラスする. 攻撃者はある人物の病名の特定を目的とし, 匿名化後の分布の分散が大きくなり匿名化前に見られていたデータの特徴データを何らかの手段で入手したとする. この時攻撃者は, 背景が失われてしまう場合がある.

知識として対象者の体重と年齢を知っており, このデータをもそこで我々は, ラプラス分布に基づくノイズ適用による Pk-とに対象者のレコードを特定して, 病名を突き止めようとする.

匿名化手法において, 匿名化前のデータの特徴をできるだけ維

Pk-匿名化は, レコードの属性値に確率的なノイズを加算して攪持するための改良法を提案する. 基本的なアイデアとして, 匿名乱させることによって, 対象者のデータ特定の確信度を 1/k 以

図 1: Pk-匿名化下にする. 匿名化後のデータセットは図 1 の右に示すような値となり, 攻撃者が対象者の体重と年齢をあらかじめ知っていたとしても, それが匿名化後の値のどれと対応するのかを 1/k 以
図 2: 相関係数 0.5 のデータを各匿名化処理した時の相関係数上の確信度で突き止めることができない.
さらに, この Pk-匿名性を保証する処理を Pk-匿名化と呼ぶ.の推移

文献 [2] では, 数値属性において Pk-匿名化を実現する手法として, レコードに対しラプラス分布に従うノイズを付与する手法を提案している. ラプラス分布に従うノイズを付与すると, 匿名化後の属性値が確率的に存在するようになる. これより, ある属性値 A を Pk-匿名化した値を A′ とすると,「 A を Pk-匿名化した値が A′ である」と確信する確率を 1/k 以下に抑えることができる. ここでは, k を下記の式で与えられる値として Pk匿名化であると証明している.

k = 1 + (|R| − 1)∏exp(−2V :属性

supu,v∈V ||u − v||1)σ(1)σ は ラ プ ラ ス 分 布 の 分 散, |R| は レ コ ー ド 数 を 表 す.
supu,v∈V ||u − v||1 は, 各属性値の絶対値の総和, すなわち属性値間の最大距離を表す. 所望の k の値の下で, σ の値を式 (1)図 3: 相関係数 1.0 のデータを各匿名化処理した時の相関係数の推移で決定する.
複数属性の場合は, まず各属性の値域を, 属性毎に [0,1] の範図 2,3 から読み取れるように, Pk-匿名化した場合の相関係数囲に正規化する. これは, ラプラス分布の分散の値域を属性間では, 元の相関係数から大きく離れてしまっている. k-匿名化した揃え, 属性間でノイズの強度が異なるのを防ぐためである. 正場合の相関係数は元の相関係数と大きく変わっていないことか

規化した後, 式 (1) で σ の値を算出し, σ の値に基づいたラン

ら, k-匿名化は元の属性値の特徴をある程度保持して匿名化でダムなノイズを各属性値に付与する. 最後に, 正規化の逆変換きる手法であることが言える. それに比べて Pk-匿名化をしたで値のスケールを元に戻す.

場合は, 元の相関係数から大きく離れることから, 匿名化後の値

3. 既存手法の課題が元の属性値から大きく広がって分布する可能性が考えられる.
これを確認するため, 上記の疑似データを匿名化した場合の3. 1 予備実験による分析

属性値の分布を可視化する. 各データの Pk-匿名化前の属性値

Pk-匿名化はラプラス分布に従うノイズを付与することで実の分布を示したものが図 4 と図 6, この疑似データを k = 10現される. そこで我々は, ノイズ付与による属性値の分布の広がとして Pk-匿名化した結果の分布を示したものが図 5 と図 7 でり方を調べるため, 疑似データを用いて予備実験を行った.

ある.

初めに, あるデータに k-匿名化を施した場合と Pk-匿名化を匿名化後のデータはラプラス分布に従って分散していること施した場合の属性間の相関係数を比較する. 相関係数を用いてが見て取れる. また, 匿名化後の値の分布は元の属性値の分布比較するのは, 匿名化後の値が元の値の特徴をどれだけ保持しとは大きく異なっていることが分かる. 匿名化前後で値の分布て匿名化を実現できているかを確かめるためである.

が大きく異なるという結果から, ラプラス分布の分散が大きい

ここで, 2 属性間の相関係数が 0.5 と 1.0 である疑似データをために過剰なノイズが付与されている可能性が考えられる.

準備する. k-匿名化後のデータは, 各データに Mondrian [9] を3. 2 解析的考察ベースにした k-匿名化を施し, 匿名化後の値の範囲の中で一様

第 3. 1 節で, 既存の Pk-匿名化の問題点を実験を用いて示し分布に従って値を決めたものとする. 結果は以下の図のようにた. そこで今度は, Pk-匿名化の問題点を数式で解析的に考察すなった. 相関係数 0.5 を持つデータを各匿名化処理した場合のる. 既存手法で提案されているラプラス分布の分散決定手順で相関係数の推移を表したものが図 2, 同様に相関係数 1.0 のデー

は, まず各属性の値域が [0, 1] になるように正規化を行った後,タの場合が図 3 である.

ノイズを付与し正規化した値を元のスケールに戻す. この過程

を保持して Pk-匿名化するには, ラプラス分布の分散を小さくすることが望まれる.
そこで本研究では, ラプラス分布の分散を小さくし, ノイズの過剰付与を防ぐ手法を提案する.
まず, 第 2 章の既存の k の算出式 (1) を変形すると, レコー
図 4: 相関係数 0.5：匿名化前 図 5: 相関係数 0.5：匿名化後

ド数と所望の k の値を固定した際, σ の値は属性値間の最大距
離 supu,v∈V ||u − v||1 に比例して大きくなることが分かる.

σ=2supu,v∈V ||u − v||1log(|R| − 1) − log(k − 1)

(3)

元の属性値がある程度均等に分布している場合には, 全ての属性値間の最大距離を用いて σ の値を決定する. また, 例えば
元の属性値が大きく二つに分類された分布を持つ場合も, 値が
図 6: 相関係数 1.0：匿名化前 図 7: 相関係数 1.0：匿名化後分布していない空間を含んでいるにも関わらず, 全ての属性値間の最大距離を用いて σ の値を決定する.

において, ノイズを付与する場合に Pk-匿名化を満たすためのラプラス分布の分散 σ を求める.
まず, 第 2 章で説明した Pk-匿名化の k の算出式を再掲する.

k = 1 + (|R| − 1)∏

図 8 のようにデータがいくつかのまとまりとなって分布している場合, 全ての属性値をまとめて Pk-匿名化を行うより, 纏exp(−2V :属性まって分布しているグループ毎に Pk-匿名化する方が分散を小さくでき, かつ過度のノイズを付与することがないと考えられ

supu,v∈V ||u − v||1)
σる. そこで我々は, 属性値の分布に関わらず属性値をいくつかのグループにあらかじめ分割し, グループ毎に Pk-匿名化を行う

正規化後の属性値に対する σ の値を σ ′ とし, 属性数を n とという改良法を提案する (図 8).

おく. 正規化を適用すると各属性の値域は [0, 1] になるので,supu,v∈V ||u − v||1 は必ず 1 となる. したがって, 正規化した属性値における k の算出式は,

k = 1 + (|R| − 1)exp(−2n)σ′(2)となり, この式から σ ′ は下記の式で導出できる.

σ′ = 2nlog |R|−1k−1

また, 各属性の元の値域を di とすると, 正規化された状態からスケールを元に戻すには σ ′ に di 倍することになる. したがって, 各属性に適用するラプラス分布に従うノイズの分散をσi とすると,
σi = 2

図 8: 提案手法：全体の属性値をグループに分割

Pk-匿名化は, 所望の k の値から匿名化後の値の存在を確率di n的に与えるため, ラプラス分布の分散が属性値毎に異なっても klog |R|−1k−1の値は保たれる. したがって, 全体の属性値を分割して Pk-匿名化することが可能である. 全体の属性値をグループに分割してとなる．
ここで例として |R| = 14842, k = 101, n = 2 を代入し, ノイズを加えた属性値がどの程度分散するか計算してみる.

σi =4
di5

この結果より, あるレコードにラプラス分布に従うノイズを加えた場合, データ全体の値域の半分以上の広さで分散することがわかる．

4. 提 案 手 法
既存の Pk-匿名化手法の問題点として, 匿名化後の属性値が大きく広がって分布し, データの有用性が維持できない可能性を示した. 過剰なノイズが付与されると, 元のデータの特徴が失われデータの有用性が低くなるため, できるだけ高い有用性グループ毎に匿名化を行うことで, ラプラス分布に従うノイズが過度に付与されることを抑えられ, それに伴い匿名化後の値が元の属性値の特徴を維持することが可能になると期待できる.
我々の提案手法は, ある一つの属性値とその周辺に分布している属性値をまとめて一つのグループとし, そのグループ毎にσ の値を算出してノイズを付与するという手法である. これにより, 過剰のノイズが付与されることを防ぐ.

5. ラプラス分布の分散と属性値のグループ分割の最適化
全体の属性値をあらかじめ分割してから Pk-匿名化を施すことによって, ラプラス分布の分散を小さくして過剰なノイズ付与を防ぐことができる. そこで, グループ分割方法の有用性, ラプラス分布の分散と属性値のグループ分割の最適化の方法を考える.

つまり, 全体属性値集合から部分属性値集合を抽出して Pk匿名化を適用したとき, 全体属性値集合に対して小さな値域の5. 1 属性値のグループに対して Pk-匿名化を満たすラプラス分布の分散の考察

部分属性値集合を選ぶことができれば, それによって要素数が減ったとしてもその影響は少なく, 部分属性値集合の値域分だ

全体の属性値集合 R （以下, 全体属性値集合と呼ぶ）に対して, 一部分の属性値集合 C （以下, 部分属性値集合と呼ぶ）だけを対象に Pk-匿名化をすることを考える．この時 Pk-匿名化を満たすためのノイズのラプラス分布の σ の値を求める.
データ全体にラプラス分布に従うノイズを付与する場合の σの値は, 第 3. 2 節よりけ σ の値を抑えることができる.

6. 予備実験と評価
元の属性値をあらかじめ分割して Pk-匿名化を施すことで,より小さい σ の値でのノイズ付与を実現することが期待できる. これを確認するため, サンプルデータを用いて全体の属性

σiR = 2di n

値を二つのグループにあらかじめ分割して Pk-匿名化を施す予

log |R|−1k−1

備実験を行う. サンプルデータには, 東京と大阪の全国地方公共団体コードと郵便番号が格納されたレコードを用いる. 東京である.と大阪のレコードの分布は, 図 9 のようにはっきりと分かれて同様に部分属性値集合に対する σi の値は,σiC = 2いる. これを東京グループと大阪グループとする.

di βlog |C|−1k−1

ただし, β = Σnj=1

cjdjとなる．ここで |C| は部分属性値集合の要素数, di は全体属性値集合がとりうる値域, ci は i 番目（以下, i 次元と呼ぶ）の属性値の値域とする．
まず, σiR に対する σiC の比率を求める.
cjΣj=1 dj log |R|−1σCk−1=σRnlog |C|−1n(4)図 9: 東京グループと大阪グループの分布k−1

以降これをパラメタ比率と呼ぶことにする. 式 (4) で比率を東京と大阪をまとめたレコードを東京 大阪グループと呼ぶ.

求めた時点で次元に依存しなくなるため, 次元にかかわらず同

この東京 大阪グループに対して σ の値を求めた場合と, 東京グ

じパラメタ比率となる.

ループ, 大阪グループで別々に σ の値を求めた場合との σ の値

5. 2 全体属性値集合に対する割合を用いた指標の導入を比較する. 図 10 が, σ の値を比較したグラフである. 東京グ

この節で定義するそれぞれの指標では, 実際の値ではなく全ループもしくは大阪グループだけで σ の値を求めた場合に比体の属性値集合に対する割合で考える．部分属性値集合 C の要

べて, 東京 大阪グループで σ の値を求めた場合の σ の値の方素数, 全体属性値集合の値域に対する C の値域の比率をそれぞが 6〜7 倍大きくなっていることが分かる.

れ要素数比率, 幅比率と呼び, f raccard (R, C), f racwidth (R, C)と表す．これらの定義は以下のとおりである.

f raccard (R, C) =|C| − 1
|R| − 1

f racwidth (R, C) = Σn
j=1

cj
dj

式 (4) に f raccard (R, C) と f racwidth (R, C) を代入して関係式を求めると

f racwidth (R, C)
σC=σR
1 + log |R−1| f raccard (R, C)(5)

k−1となる. 上式を読みとくと, σ R に対する σ C の比率が幅比率に

図 10: σ の値の変化グラフ比例する一方, 要素数比率に反比例するため, 要素数を小さくし過ぎるとパラメタ比率は逆に大きくなってしまい, 場合によっ

この結果より, あらかじめレコードをグループに分類をしてては 1 を超える可能性もある. しかしながら, 要素数比率は対からグループ毎に σ の値を決定し, その σ の値に従ってノイ数スケールで反比例するためその影響は要素数比率に対してはズを付与する方法が有用であると言える. また, k = 20 として小さいと考えられる.

東京 大阪グループで Pk-匿名化した場合と, 東京グループもしした場合, 図 12 を拡大すると以下の図 15 のようになり, 各属性値はグループとして分布していた元の属性値の周辺に分散していることが分かる.

図 11: 匿名化前

図 15: 分類してから匿名化した場合（図 12 の拡大）

この予備実験では属性値全体を単純に明確な二つのグループに分けたため, 第 5. 章で提案した比率を考慮して導出したグループの要素数で分割できれば, さらに σ の値を抑えた Pk-匿名化を行うことができると考える. 今後, それらの比率を考慮したグループの要素数の最適化にも取り組んでいきたい.
図 12: 分類してから匿名化した場合

7. ま と め
本稿では, ラプラス分布のパラメータを決める際に, 元の属性値をあらかじめいくつかのグループへ分類してからグループ毎に Pk-匿名化を施すという, 一改良法を示した. この手法により,過剰にノイズを付与することなく Pk-匿名化を実現することが可能になると考える. 今後の課題として, さらに複雑な分類を持つデータや実際の機密情報を用いた検証実験や, k の値と σ の値との関係の数式的定義の確立などが考えられる. また, 本稿で導出したデータ分割の条件の実験的な検証や, Randomization

図 13: 東京 大阪グループ匿名化後（東京）を用いた数値データ [6] に対する k-匿名化手法との比較もあげられる.
文

図 14: 東京 大阪グループ匿名化後（大阪）くは大阪グループで Pk-匿名化した場合の値の分布を比較する(図 10〜14).
この結果を見ると, あらかじめ分類をせずに東京 大阪グループとして匿名化を行うと, 元の属性値から大きく離れて分散することが分かる (図 13, 図 14). しかし, あらかじめ分類をしてから東京グループと大阪グループに分けてそれぞれ Pk-匿名化

献[1] 五十嵐 大, 千田 浩司, 高橋 克巳,”k-匿名化の確率的指標への拡張とその適用例”,CSS2009,2009[2] 五十嵐 大, 千田 浩司, 高橋 克巳,”数値属性における k 匿名化を満たすランダム化手法”,CSS2011,2011[3] 五十嵐 大, 千田 浩司, 高橋 克巳,”ランダム化データベース上のk-匿名性の一般的算出法”,CSS2011,2011[4] 五十嵐 大, 長谷川 聡, 納 竜也, 菊池 亮, 千田 浩司, 数値属性に適用可能なランダム化により k 匿名化を保証するプライバシクロ
ス集計,CSS2012[5] 千田 浩司, 木村 映善, 五十嵐 大, 濱田 浩気, 菊池 亮, 石原 謙,”
集合匿名化データの多変量解析評価”,CSS2012,2012[6] J. Li, ”Preservation of proximity privacy in publishing numerical sensitive data”, SIGMOD2008[7] L. Sweeney. ”k-anonymity: a model for protecting privacy”, International Journal on Uncertainty, Fuzziness andKnowledge-based Systems,10(5), pp.555-570, 2002.
[8] R. Agrawal and R. Srikant. Privacy-preserving data mining.
Proc. of the 2000 ACM SIGMOD Intl. Conf. on Management of Data, 2000.
[9] Kristen LeFevre, David J. DeWitt, Raghu Ramakrishnan,”Mondrian Multidimensional K-Anonymity”,ICDE,2006