Posted at

k-anonymity:データのリスクの定量評価手法


はじめに

最近はSociety5.0とかなんとかいってデータサイエンスがバズりまくってるこの頃です。

機械学習とか最近めちゃくちゃ流行ってますよね。

そんなご時世ですが、一方でセキュリティもめちゃくちゃ大切です。

てかセキュリティ無くしては多分何も始まりません。多分。

データのセキュリティ方面においてk-anonymity (k匿名性)というのは結構重要な手法なのですが、ググってみても日本語でスッキリ解説されている記事がないんですよね。(見つかるのはNECとかのプレスリリースとかばっかり)

そういう背景のもと今回の記事ではデータセキュリティについて、データからの特定リスクを定量的に評価するk-anonymity(k匿名性)について解説させていただきます。


データのリスクとは

はじめに、データのリスクというのを聞いてどんなものをイメージするでしょうか?

恐らく、プライバシーの侵害というのが答えが一般的なものかと思われます。

ではプライバシーの侵害とはどんなものでしょうか?

これは以下の5段階に大別されます。

段階
内容

特定
誰を指し示すかわからないデータを該当する個人に結びつけること

連結
ある個人のデータを別の個人のデータと結びつけること

属性推定
ある個人のデータが削除・抽象化されているときにそれを復元すること

連絡
個人のデータの保持者が該当する個人に対してコンタクトを取ること

直接被害
個人に関するデータの保持者が該当する個人に対して直接的に被害を与えること

日本の個人情報保護法において配慮が必要とされているのは特定と連絡、直接被害です。

実際、SNSでの事業者が研究目的で外部の研究所にデータを提供する際、データの特徴から上記のようなプライバシーの侵害が起こりうるわけです。


いくつかの用語

以下ではk-anonymityについて説明しておこうと思いますが、その前に色々な概念を導入しておきます。


識別情報

特定とは上述した通り、データと個人を結びつける行為です。ツイッターのアカウント保持者をツイート内容から誰なのか特定するといった感じです。ちなみにぼくのツイッターのアカウントは@komi_edtr_1230なので良かったらフォローしてください。

識別情報直接識別情報間接識別情報に分かれ、直接識別情報とはそれ単体で直接的に個人を特定することができるようになる情報のことです。

一方で、間接識別情報とは他の情報と組み合わせることで個人を特定することができるようになる情報です。


識別と特定

上記の識別情報の説明の通り、識別とは持っている情報が直接識別情報を含んでいないときにその情報がどの個人を指し示しているかはわからないがそれがどれか個人のものであるとわかるような状態にすることです。

一方で、特定とはそれらの情報から個人を結びつける行為です。

識別と特定は似ているが結構違うので注意してください。


データ特定のリスク:k-anonymity

さて、上記のようなデータから個人のプライバシーが侵害されうるわけですが、ここで気になるのがここで扱っているデータは実際のところどのくらいプライバシー侵害のリスクがあるのかということです。

このデータの特定リスクを定量的に評価する手法がk-anonymityです。


定義

データに該当する人が$n$人いるとして、各自に$1$から$n$まで番号が振られているとしましょう。

また、番号の$i$の人に関するデータを$x_i$とします。

ここで、データ$x_i$は$d$個の属性を持ちます。例えば名前とか住所とか年齢とか好きな女優とか。

ちなみにぼくは女優だと戸田恵梨香が好きです。

よってデータ$\bf{x_i}$は以下のように表されます。

\bf{x_i} = (x_{i,1}, x_{i,2},\dots ,x_{i,d})

これよりデータの集合$D$は以下の通りに表せます。

D = \{ \bf{x_1}, \bf{x_2},\dots , \bf{x_n} \}

イメージとしてデータ$D$は以下のような形をしていると思ってください。

わかりやすさのために行列で表記しましたが、あくまで$D$は集合であることに注意です。

さて、ここで$j$番目の属性の定義域を$\it{X_j}$とすると、個人のデータ$\bf{x_i}$の定義域は$\it{X_1}, \dots ,\it{X_d}$の直積集合です。

つまり以下の通りに表せます。

\bf{x_i} \in \it{X_1} \times \it{X_2} \times \dots \times \it{X_d}

ここでこの$d$個の属性のうち$d_{QI}$個が間接識別情報であるとしましょう。

そして残りの$d_{misc} = d - d_{QI}$個はその他の属性であるとします。

このとき個人の情報$\bf{x_i}$は

\bf{x_i} = (\bf{x_i}^{QI}, \bf{x_i}^{misc} ) 

として表せます。

このときk-anonymityは以下の通りに定義されます。


$D$がn人から集めたレコードの集合であるとし、$D$に含まれる間接識別情報の組み合わせの集合を$A \ ( = X_1 \times X_2 \times \dots \times X_{d_{QI}} )$とする。このとき全ての$\bf{x}^{QI} \rm{\in A}$について$\bf{x}^{QI}$を含むレコードが$D$に少なくとも$k$個存在するとき、$D$はk-anonymityを持つという。



わかりすさのために具体例として以下のようなデータを考えましょう。

名前
年齢
性別
都道府県
市区町村
職業

橋本環奈
19

東京都
港区
学生

ピカソ
78

島根県
松江市
教師

杉咲花
20

千葉県
船橋市
女優

安倍晋三
32

北海道
札幌市
小説家

田所浩二
24

東京都
世田谷区
学生

聖徳太子
30

京都府
京都市
無職

ドナルド・トランプ
59

大阪府
高槻市
会社員

戸田恵梨香
30

静岡県
焼津市
女優

こんな感じのデータをある会社が持っていたとします。

当然、研究のためにデータ提供する際にこのままだと色々まずいのでマスキングしたりします。

ID
年齢
性別
都道府県
市区町村
職業

748346
[-25]

東京都
N/A
N/A

682125
[50-]

島根県
N/A
N/A

184056
[-25]

千葉県
N/A
N/A

123023
[30-50]

北海道
N/A
N/A

114514
[-25]

東京都
N/A
N/A

361711
[30-50]

京都府
N/A
N/A

762391
[50-]

大阪府
N/A
N/A

543271
[30-50]

静岡県
N/A
N/A

そうしてこれを年齢でソートします。

ID
年齢
性別
都道府県
市区町村
職業

748346
[-25]

東京都
N/A
N/A

184056
[-25]

N/A
N/A
N/A

114514
[-25]

東京都
N/A
N/A

123023
[30-50]

N/A
N/A
N/A

361711
[30-50]

N/A
N/A
N/A

543271
[30-50]
N/A
N/A
N/A
N/A

682125
[50-]

N/A
N/A
N/A

762391
[50-]

N/A
N/A
N/A

こうしてみると都道府県や年齢から個人を特定することができません。

このデータは、攻撃者が特定をしようとするときデータがk-anonymityを持つならば特定の候補が少なくともk人存在し、特定候補をk人以下に絞り込めない、ということになります。

これがデータの特定リスクを定量的に評価する指標であるk-anonymityです。


アルゴリズム

先ほどk-anonymityの定義を述べましたが、以下ではk-anonymityを実現するようなデータの一般化アルゴリズムについて考察していきます。


一般化階層構造

先ほどの例でデータの匿名性を上げるためにデータの各セルをN/Aでマスキングをしました。

また、年齢を[-25]などにするなどデータの抽象度を上げたりもしました。

このようにデータの処理の仕方があるのですが、抽象度の上げ方についていくつかの段階を考えられます(以下の図を参照)。

このように属性値を一般化することで属性値のバリエーションは少なくなり、間接識別情報の組み合わせが同じ値を取りやすくなります。


匿名性と有用性のトレードオフ

匿名性を最優先するのであれば各属性を最高階層まで一般化してしまえば実現できます。

つまり年齢を全て[0-120]とし、性別を*、出身地域を惑星とすれば匿名性の高いデータとなります。

しかしこれは明らかにデータとして解析に役立たずで、データ解析において有用性がありません。

このように匿名性と有用性はトレードオフの関係性にあります。

では良い匿名化具合を考えるわけですが、この評価指標には色々あります。

以下では匿名化前のデータを$D=(\bf{x_1}, \bf{x_2}, \dots , \bf{x_n})$とし、匿名化後のデータを$D'=(\bf{x_1}', \bf{x_2}', \dots , \bf{x_n}')$としておきます。


データ変化量による有用性基準

これは単純にデータがそこまで変化していないことが良いと定義する手法です。

具体的にどうするかというと、属性値は数値情報ならユークリッド距離の最小化になります。

U_{Euclid}(D, D') = \sum_{i=1}^{n} \sum_{j=1}^{d} (x_{i,j} - x'_{i,j})^2

属性値が離散属性ならば、j番目の属性の確率質量分布のKLダイバージェンス(=分布の距離)を最小化になります。

U_{KL}(D, D') = \sum_{j=1}^d KL(p_j, p'_j) = \sum_{j=1}^d \sum_{x \in X_j} p_j(x) \log \frac{p_j(x)}{p'_j(x)}


匿名化操作数による有用性基準

データ$D$からデータ$D'$にするのになるべく少ない操作数で匿名化を達成するという評価指標です。

例えば一般化階層構造において性別を第一階層、年齢を第三階層、郵便番号を第二階層として考えたときに操作回数は0 + 2 + 1 = 3で3回です。


解析結果の変化量による有用性基準

これはあらかじめ解析に用いる手法が固定されている場合の評価指標で、なるべく匿名化してもデータの解析結果に影響を与えないことが良いと定義しているわけです。

この場合、データの解析関数をfとすればf(D) - f(D')が最小化対象となります。


アルゴリズム

以下ではこの間接識別情報の組み合わせがうまいことk-anonymityを実現するようなアルゴリズムを考えていきたいのですが、先に言っておくと最適なk-anonymization(k匿名化)はNP困難であることが知られています。

つまり多項式時間で匿名化を達成することはできません。

しかし以下で紹介するIncognitoというアルゴリズムは匿名化操作数に基づく有用性基準において効率的にk匿名化を達成することができます(多項式時間ではないが)。


背景

データ$D$がk-anonymityを持つとき、$D$に含まれる全ての間接識別情報の組み合わせの値を持つレコードは必ずk個以上存在します。

つまり、$D$がk-anonymityを持つならば$D$の部分集合もk-anonymityを持ちます。

この事実をk-anonymityの単調性といい、Incognitoではこの単調性を利用してk-anonymityを実現します。


アルゴリズムの動作

Incognitoでは単調性を利用すると言いました。

具体的にどうするかというと、元データの部分集合がk-anonymityを持つため、あらかじめ少数の属性値の組み合わせでk-anonymityを持っているかチェックし、そうしてだんだんと属性値の組み合わせを大きくしていきます。

要するに枝刈りです。遺伝アルゴリズムとかに近い感じ。

今回は動作例を表すために以下の状況で、(S0, Y0, A0)などのような一般化階層の組み合わせを考えていきます。

まず最初に、単独の間接識別情報において、最も少ない一般化の操作数でk-anonymityを考えます。

そのような集合を$S_1$とします。

次に$S_{i-1}$に含まれる$i$個の間接識別情報の一般化の組み合わせの集合を$C_i$とします。

そうして得られた$C_i$の各要素について、一般化の束(一般化の操作を+1したもの)を幅優先探索し、最も少ない一般化の操作数でk-anonymityを実現している一般化階層を求め、そうしてそれを$S_i$とします。

この操作を$i = 2, \dots, d$で行い、最終的に得られる$S_d$が欲しい出力となります。

これを図示すると以下の通りとなります。


他のデータの特定リスクの評価指標

本稿ではk-anonymityについて論じましたが、この話題はもう少し拡張することができます。


母集団一意性と標本一意性

データ提供者は全てのデータ(=母集団)を与えるわけではなく一部(=標本)を提供するわけです。

そこで考えられるのが、標本中での一意性(特定できること)が母集団での一意性に一致するわけではないという可能性です。

ここで「母集団一意性 → 標本一意性」は言えますが「標本一意性 → 母集団一意性」は必ずしも言えないことに注意してください。

k-anonymityでは提供データが母集団かどうかであるかに関わらず標本一意であれば特定リスクがあると考えていました。

しかし、実際のところ標本一意であっても母集団一意ではない場合もあり、標本中でk-anonymityを考えた際に特定リスクが高いと考えられても母集団を考えた際は意外と特定リスクが高くないかもしれないわけです。

そこで母集団一意性に基づくリスク評価指標が考えられるわけですが、これはk-anonymityよりも緩和的なリスク評価指標であり、k-anonymityの拡張とも見てとれます。

さて、実際のところどうするかというと、手元には標本しかない場合は母集団一意なレコード数(個人のデータ数)がわからないので、母集団のレコード数を統計的に推定することになります。

ここから先はポアソン分布やガンマ分布を仮定したりと統計的モデリングの話になってくるので踏み込みませんが、非常に面白い話題ですので興味がある人は勉強してみてください。


時系列データ

今回のk-anonymityではデータの母集団が時間的に変化しないことを仮定して話を進めてきました。

しかしこのデータ特定のリスク評価を時系列的に連続に処理しようとすると少し拡張が必要です。

離散時間でデータが変化するごとにk-anonymityを考えればいいやんという考え方もありますが、計算コストが大きいことや単位時間での変化率を考えると全て計算し直すのは少々効率が悪いわけです。

こんな感じの問題もあるのですが、またこれも今後検討していく話題となっていますので、興味がある人は勉強・研究してみるといいかもしれません。


まとめ

今回はk-anonymityについて紹介しました。

日本ではあまりデータ匿名化手法が話題になっていないせいか、k-anonymityについての日本語の記事がなかったのもあって本稿を執筆することにしました。

ぼく自身も未熟なのでひょっとしたら致命的な勘違いをやらかしてそうではありますが、間違いが発見された際はご指摘いただけると幸いです。

それではお疲れ様でした!


出典

論文:

k-ANONYMITY: A MODEL FOR PROTECTING PRIVACY

参考図書:

データ解析におけるプライバシー保護