【技術】k-匿名化についてMIRAIタワーで女子高生が喋っていた【第三回】
前回の話からしばらくの間、アリスとシャミアは普通の学校生活を送っていた。階層に基づくモデルの話はずっと話せないまま、とうとう2人は夏休みを迎えた。夏休みといえば、山のように積まれた宿題と旅行だ。シャミアはもちろん、優等生のアリスも例外ではない。そんな2人が宿題そっちのけで都会の「名古屋」に出かける奇想天外な話を今回はのぞいてみたいと思う。
シャミア：「展望台が楽しみだね！恋人の聖地なんだって！アリスも興味あるよね？」
アリス：「あっ、そう？別に興味ないよ」
シャミア：「つまんないね！あたしはめっちゃ興味あるよ！」
「今日なんかツンツンしているね」と心の中で思うアリス。そんなこんなでエレベータの扉が開いた。辺り一面に名古屋の夜景が広がる。2人はすべての窓という窓をぐるっと回った。それから、階段を上って露天展望台に躍り出た。
シャミア：「真夏なのにちょっと寒いかも」
アリス：「ここは地上から百メートル以上だからね。風が強いんだよ」
シャミア：「アリスはなんでも知っているね。そう言えば前預けた話の続きをしようよ！」
アリス：「階層に基づくモデルの話ね。いいよ。ただしその前に一般化階層の説明をしないといけないね。そうだ、この間説明がかなり丁寧なページを見つけたよ」
アリスがスマホを取り出して検索し始めた。シャミアがアリスのスマホ画面を覗き込むと次の説明が載っている。
一般化階層（generalization hierarchy）とは値がどのように一般化されるかを表す木構造である。親ノードはノードと対応する値を一般化した時の値を表す。ただし一般の木とは違ってどの葉ノードから根ノードまでの距離も同じである。そのため一般化階層のノードをレベルに分けることができる。レベルが低いほど元のデータに近いとされる。特に最下層（レベル０）はカラムに出現している値と対応していて最上層はもっとも一般的な値と対応している。一つのレベルの値全体は領域（domain）と呼ばれる。
例として住所を匿名化する時を想像してください。最下層はそのままテーブルに出てくる住所のままである（例: 愛知県名古屋市千種区xx町 x-x）。その上の一層は住所の市町村までの部分(例: 愛知県名古屋市千種区xx町→愛知県名古屋市千種区→愛知県名古屋市)でそのさらに上の階層は県までの部分(例: 愛知県)にあたる。一番上は住所の全削除に相当する。次のテーブルと一般化階層を考える。
| 生年月日 | 性別 | 郵便番号 | 症状 |
| 1/21/76 | 男 | 53715 | 流感 |
| 4/13/86 | 女 | 53715 | 肝炎 |
| 2/28/76 | 男 | 53703 | 気管支炎 |
| 1/21/76 | 男 | 53703 | 腕打撲 |
| 4/13/86 | 女 | 53706 | 足首捻挫 |
| 2/28/76 | 女 | 53706 | ささくれ |
![郵便番号の一般化階層[1]](https://s3.ap-northeast-1.amazonaws.com/wraptas-prod/acompany-engineer/992e05f4-9f0b-4462-86f1-d7db9f5c1186/7ad8d6013eb024f9151b8a732bafbf05.png)
アリス：「わかりやすく例えると一般化階層はパソコンのフォルダー構造だね。元のテーブルに出現する値はファイルで匿名化した値はフォルダに相当する。匿名した値は匿名レベルの違いによって階層構造をなすこともまたフォルダと似ているね」
シャミアが理解したような顔したのを見て、アリスは続ける。
アリス：「階層に基づくアルゴリズムの代表はIncognitoが挙げられる[1]んだ。その他にもFlashというアルゴリズムがある[2]。この2つのアルゴリズムは問題設定が同じだからIncognitoだけ解説するね」
アリス：「Incognitoはfull-domain generalizationモデルという特別なglobal recodingモデルに従う。このモデルでは準識別子のカラムごとにそのカラムの値を一般化階層の同じレベルの値に置き換える。これだけだとちょっと抽象的すぎたかもね…例で考えましょう！仮に名古屋在住と神戸在住の2人の記録が同じテーブルにある。そのテーブルでは住所が準識別子の一部とされて「名古屋」を「愛知」に書き換えるなら「神戸」を「兵庫」に書き換えないといけない。これは匿名化した後の値が一般化階層の同じレベルにあるという制約があるから。この制約を利用して、どうやってテーブルを匿名処理するかを準識別子（筆者より補足：これ以降準識別子を準識別子の要素という意味合いで使うことがある）として別の匿名レベルの組み合わせにかける。Incognitoは準識別子とそれぞれの一般化階層を入力としてk匿名性を満たす匿名レベルの組み合わせを全部見つける」
アリス：「Incognitoの処理はラウンドに分けることができる。各ラウンドでは準識別子のサイズが固定された部分集合に注目して、その部分集合を準識別子とみなして各カラムの匿名化レベルを求める。1ラウンド目は準識別子のカラムそれぞれを取り出して匿名化レベルを求める。２ラウンド目は準識別子のなか2つカラムの組み合わせについて匿名化レベルの組み合わせを求める。こうやってラウンドごとに注目している部分集合のサイズを増やすことで最終的に準識別子全体の匿名化レベルの組み合わせを求められる。例えば準識別子が名前、住所と生年月日の時にラウンド1は名前、住所と生年月日それぞれのk匿名性を満たすに必要な匿名レベルを計算して、ラウンド2は(名前, 住所)、（住所, 生年月日）と（名前, 生年月日）の３つの部分集合に対して必要な匿名レベルの組み合わせを計算して、そしてラウンド3（最終ラウンド）は準識別子全体に対して匿名レベルの組み合わせを計算する」
シャミア：「うーん、なんだかめっちゃ遠回りしているような気がするね」
アリス：「Incognitoは前のラウンドの情報を利用して後のラウンドの計算時間を削減している。それはrollupと枝刈りというんだよ[1]」
シャミア：「ロール・アップ?枝刈り？」
アリス：「まずはrollup から説明するね。長くて言いにくいからこれからある匿名化レベルのもとでの値の組み合わせごとの出現回数をその匿名化レベルの頻度表と言うことにしよう。仮に匿名化レベルAと匿名化レベルBがあるとする。このBはAと比べて一つのカラムの匿名化レベルが1低くて、他のカラムの匿名化レベルは全て同じだとする。するとBの頻度表を基にAの頻度表を計算できる」
少し考えた様子を示したあとアリスはリュックからノートを取り出して膝に広げた。そしてノートにテーブルを2つ書いた。
| 名字 | 住所 | 出現回数 |
| 佐藤 | 名古屋 | 10 |
| 山川 | 三河 | 3 |
| 佐藤 | 安城 | 15 |
| 松下 | 米原 | 3 |
| 名字 | 住所 | 出現回数 |
| 佐藤 | 愛知 | 25 |
| 山川 | 愛知 | 3 |
| 松下 | 滋賀 | 3 |
アリス：「例えば上のテーブルがBの頻度表で下のテーブルの出現回数を計算できる。愛知県の佐藤（佐藤, 愛知）の出現回数は名古屋の佐藤（佐藤, 名古屋）の出現回数と安城の佐藤の出現回数の総和になる。愛知の山川の出現回数は三河の山川の出現回数と同じだ。このようにして低い匿名化レベルの頻度表の結果を利用して高い匿名化レベルの頻度表を作ることがrollupと呼ばれる。rollupを使えば、頻度表を計算する時毎回元のテーブルを参照しなくて済むんだ」
シャミア：「なるほど、確かに効率よくなりそう」
アリス：「次に枝刈りについて説明するね。枝刈りとは事前に絶対にk匿名性を満たさない匿名レベルの組み合わせや絶対にk匿名性を満たしている組み合わせを除外していくことだ。前者を除外することで探索が必要な組み合わせ数を抑えている。そして後者を除外していくことで頻度表を計算する回数の低減を図る」
シャミア：「うーん、でも頻度表を計算せずに匿名レベルの組み合わせがk匿名性を満たしているかを判別できるの？」
アリス：「できるよ。匿名レベルの組み合わせには「上位互換」のような関係が存在する。仮に匿名レベルの組み合わせAとBがあるとする。もしBが全ての属性においてAより匿名性レベルが高ければ、Aを採用してk匿名性が満たされるならBを採用してもk匿名性は満たされるはずなんだ。これはBを採用して匿名化することは、まずAで匿名化してからさらに匿名化することと同じだから。すでにk匿名性を満たすテーブルをさらに加工してもまたk匿名性を満たす。サイズを固定して準識別子の部分集合の匿名化レベルを探索する時にk匿名性を満たす組み合わせを一つでも見つけたら「上位互換」全てに「k匿名性を満たしている」というタグを付けて頻度表を計算しなくてもいいんだよ。例えば名前、住所と年齢の３つの準識別子に対して匿名レベルの組み合わせ（2, 0, 3）は組み合わせ（1, 0, 3）の上位互換になる。したがって組み合わせ（1, 0, 3）がk匿名性を満たすとわかったら(2, 0, 3)をチェックする必要がなくなるということなんだ」
アリスがさらにテーブルを2つ書き足して話を続けた。
| 名字 | 住所 | 年齢 | 出現回数 |
| 佐藤 | 名古屋 | 20代 | 2 |
| 山川 | 三河 | 20代 | 3 |
| 佐藤 | 安城 | 20代 | 4 |
| 松下 | 米原 | 20代 | 3 |
| 田中 | 東京 | 20代 | 5 |
| 名字 | 住所 | 年齢 | 出現回数 |
| 佐藤 | 愛知 | 20代 | 6 |
| 山川 | 愛知 | 20代 | 3 |
| 松下 | 滋賀 | 20代 | 3 |
| 田中 | 東京都 | 20代 | 5 |
アリス：「上の頻度表より下の頻度表の方が住所だけ匿名レベルが一段階高いからテーブルにある一番少ない値の組み合わせの出現回数は下のテーブル以上になっている。もし上の頻度表を計算してk匿名性が満たされたら下の頻度表を計算する必要がないわけだ」
（名古屋特有の生暖かい風が展望室を吹き抜ける）
アリス：「そしてk匿名性を満たす匿名レベルの組み合わせにも特徴がある。それはその中の一つのカラムを除外してそのほかのカラムの匿名レベルをそのままにして得られた匿名化レベルもまたk匿名性を満たしているということだ。逆に言えば、カラムを一つ除去して得られる組み合わせの中の一つでもk匿名性を満たしていないなら、元の組み合わせもk匿名性を満たしていない。この性質を利用して前のラウンドの計算結果を利用して、カラムを一つ除去したらk匿名性を満たさないような組み合わせをあらかじめ除外することができる」（注釈1）
シャミア：「Incognitoが小さい順に準識別子の部分集合をチェックしたのは後の計算に前の計算結果を利用するためだったのね！」
アリス：「シャミアは飲み込みが早いね。Incognitoはこうやって準識別子の小さい部分集合からk匿名性を満たす匿名レベルの組み合わせを探し出して最終的に準識別子全体に対してk匿名性を満たすような組み合わせを全部見つけることができる」
「アリスはあたしの師匠みたいだね」とシャミアが笑いながら言う。それを聞いたアリスの顔が赤くなって「そんなことないよ」と頭を左右に振りながら全力でシャミアの言うことを否定しようとする。シャミアはそんなアリスを気にせず話を続けた。
シャミア：「そろそろ下りてホテルに戻ろう！明日も早いから！」
シャミアは話ながらベンチから立ち上がって、アリスはただ静かに従う。さっきまで2人の構図とは大違いだ。MIRAIタワーから降りた2人が賑やかな栄を抜けてビジネスホテルの客室まで戻った。地上100メートルで繰り広げられた非日常な対話とはうってかわって客室は至ってシンプルだ。そして名古屋旅の1日目はこの客室にて幕を閉じた。
注釈
- 匿名レベルの組み合わせ（元の組み合わせと呼ぶ）から一つのカラムを除去することはそのカラムの匿名レベルをMAXにすることと同じである。つまり得られた頻度表は元の頻度表と比較して一番少ない値の組み合わせの出現回数がより多くなる。上位互換を採用してもk匿名性を満たせないなら元の組み合わせではk匿名性を満たすことはない。
参考文献
- LeFevre, K., DeWitt, D. J., & Ramakrishnan, R. (2005, June). Incognito: Efficient full-domain k-anonymity. In Proceedings of the 2005 ACM SIGMOD international conference on Management of data (pp. 49-60).
- Kohlmayer, F., Prasser, F., Eckert, C., Kemper, A., & Kuhn, K. A. (2012, September). Flash: efficient, stable and optimal k-anonymity. In 2012 International Conference on Privacy, Security, Risk and Trust and 2012 International Confernece on Social Computing (pp. 708-717). IEEE.