前回のお話（k-匿名性について電車で女子高生が喋っていた）に引き続き、愛知県の片田舎、とある町での出来事。この町にはいくつかの高校があり、下校の時間になると町の中心部にある駅は、いつも生徒の笑い声で賑わう。何せ町唯一の高校だから生徒も地元出身が多い。高校も大学も、就職先も、この町で満たされてしまう。全国展開する学習塾も、ショッピングモールもあり、案外なんでも揃ってしまう。

ほとんどのこの学校の高校生が、塾やアルバイトへと急ぐ中、目的が違う2人がいる。今回も、千種シャミアと本山アリスの、変な2人の会話を覗いてみようと思う。

（ちなみに、この記事執筆時点は冬に近づいているが、フィクションなので舞台は真夏である）（ちなみに愛知県の中心名古屋市の夏は、気だるく、暑い）

千種シャミア（ギャル）

性格：はしゃぐことが好きだがしっかりした面も持ち合わせている

趣味：バイク（原付）、カフェ巡り、ファッション

本山アリス（クールな変人）

性格：クールなオタク

趣味：論文を読む、Twitter廃人

本山アリス：「あつい…。なんてこんな暑い日に駅まで歩かないといけないの…。こういう時こそタクシーを使うべきでしょ、ねえシャミア」

千種シャミア：「たまには歩くのも悪くないじゃない？タクシーなんてここじゃあ高校生が乗っていたら変な目で見られるよ。ちょうどあそこに行きつけの喫茶店が見えたから、ホットコーヒーでも飲んで休憩しませんか？ねぇ、お嬢様？」

アリス：「……今日のシャミアちょっと変だね。喫茶店に立ち寄ることなんて提案して。こんなにのんびりしていて塾は大丈夫なの？」

シャミア（突然アリスの手を引っ張って走り出しながら）：「大丈夫だよ！今日講師の人が夏風邪で、休みになったから！」

気づけは目の前にはレトロな喫茶店。この町では、こういった類の、昭和から続くレトロな喫茶店が多くある。その中でも、目の前にある喫茶店「バーナム」は、カフェ巡りが趣味のシャミアにとってお気に入りのお店である。

一呼吸おいて、シャミアはバーナムのドアノブに手をかける。ぐいっと重いドアを押すと、乾いた風鈴の音がﾁﾘﾝﾁﾘﾝと鳴る。

「いらっしゃい」

店の中はクーラーが効いて外の暑さとは対照的だ。店主のおばあさんが空いている赤いソファー席に視線を向ける。2人がその席にトコトコ歩いていくと、おばあさんが「今日は何にするの」と尋ねてきた。シャミアが「ホットカフェオレ2つ」と言うと、おばあさんは一瞬、目をギョッと見開く。「ホットカフェオレふたつね」と呟いて、店の奥に消えていく。ホットを強調していたかのように思えたが、多分幻聴だろう。

ふぅと一呼吸。シャミアが口をひらく。

シャミア：「アリスは牛乳入れないとコーヒー飲めないのは知ってるよ。小学校からずっと一緒だからね。そして、新しい彼氏がその『k-匿名性』っていうのも知ってる」

アリス：「勝手に彼氏にしないで。まあ大体合っているけど」

シャミア：「うふふ。その彼氏くん（k-匿名性）のことをもっと教えてよ」

アリス：「いいよ。シャミアは私の偉大なる彼氏（k-匿名性）について何が知りたいの？」

シャミア：「うーん。データが彼氏、いやk-匿名性を満たさない時にそのデータを加工してk-匿名性を満たすようにするにはどうすればいいのかとか。例えば、特に目立つ記録を消したりするとか？」

アリス：「シャミアは時々鋭いね。それはトップコーディングと呼ばれる技術だよ。このトップコーティングは、閾値を設定して閾値を超えた値を閾値以上（もしくは以下）に置き換える技術を指すんだ[1]。例えば学校では不合格だった人の点数を公開しないことがあるよね。ただしこの手法そのものはk-匿名化する手法ではないよ」

シャミアの頭の上にはてなが浮かぶ。

アリス：「k-匿名性を満たすような匿名化処理は2ステップに分けられる。まずはテーブルのレコードをいくつかのグループに分ける。そしてどのグループもk個以上のレコードを含む。その後グループごとに準識別子（それ自体はユニーク識別子ではないものの、他の純識別子と組み合わされるとユニーク識別子になり得る識別子）を代表的な値に書き換えていく（注釈 1 ）」

ちょっと困惑しているシャミアを見たアリスが、ノートとペンを取り出す。バンっと広げたノートに大きく、名簿みたいなテーブルを書いた。

アリス：「名前単体では、特に何も意味をなさないデータだよね。なので、ここでの名前は準識別子になる。その上で、考えられるグループ分けの1つは名字が同じな人を1つのグループにする。グループ分けしたあとフルネームを名字に変える。（右のテーブルを指しながら）これで、2匿名性を満たすテーブルの出来上がりだ！」

「お待たせ」

おばあさんが湯気が立つカフェラテとクッキーを2人の前に置いた。 シャミアがスマホを取り出してSNSに投稿するための「映える」写真撮影タイムを繰り広げる。アリスはそんなシャミアの様子を呆れた様子で受け流しつつ、話を続ける。

アリス：「自動的にk-匿名化を行うためにいろんなモデルが提案されているんだ。モデルはグループの分け方で概ね分類できる。local recodingモデルとglobal recodingモデルや階層に基づくモデルと分割に基づくモデルなど違う側面から分類できるよ。[2]」

シャミア：「ちょっと待て！ろーかる・れこーでぃんぐって何？何をレコーディングするの？もっとちゃんと説明してよ、アリス」

アリス：「あっごめん。ちゃんと説明するべきだった。まずはね、レコーディングじゃなくてrecoding。このrecodingは「書き換え」という意味で、global recodingモデルは準識別子が同じ値を持つレコードを必ず同じグループに分けるというルールが存在するんだ。逆にlocal recodingはそんな制限がない。例えば……」

アリスは何かを考えているようでしばらく黙っていた。シャミアはカフェオレをずずずっとすすりながら考え込むアリスを見るのが好きだ。特に好きなのは、アリスが真剣に考えている時に目線が天井にいって白目を剥いてしまう時だ。

アリス：「global recodingを採用するなら(男, 28歳, 東京都)を準識別子とする2のレコードがグループ分けの段階で同じグループになるようにする。同じグループ内なら同じ準識別子になるように処理されるから、匿名処理した後のレコードは同じになる。その1つのレコードが(性別不明, 20代, 東京都)と処理されたならもうひとつも(性別不明, 20代, 東京都)でないといけない。local recodingならそのひとつのレコードが(男, 20代, 東京都)と変換されてもうひとつが（性別不明, 28歳, 東京都）でもOKだ」

アリスがカフェラテをちょっと飲んで続けた。「あちっ」と思わず声が漏れる。

アリス：「global recodingを採用した場合でもカラムごとにグループ分けを考える方針と準識別子全体で考える方針がある。それぞれsingle dimensionalとmulti-dimensionalと呼ばれる。single dimensionalではカラムごとに匿名処理を決める。multi-dimensionalの場合は準識別子の値の組み合わせで匿名化処理を決める。例として、東京在住25歳の田中(田中, 25歳, 東京都)と名古屋在住25歳の高橋(高橋, 25歳, 名古屋)が同じテーブルにいるとする。single-dimensionalモデルでは田中の年齢を「20代」にすると高橋の年齢も「20代」にしないといけない。multi-dimensionalモデルでは値の組み合わせで匿名化の結果を決めるのでこういった制約がない」

「うむ」と納得したような顔をするシャミアを見てアリスは続けた。

アリス：「local recoding とglobal recoding についてはこんなところかな。」

再びアリスはカフェオレに手をつけるが、「あちっ」と唸る。

アリス：「階層に基づくモデルと分割に基づくモデルの違いを説明するのはアルゴリズムを説明したほうが早いかもね」

シャミア：「アルゴリズム？」

アリス：「匿名化においてのアルゴリズムはモデルの制約のもとでグループ分けと匿名処理を行う手順のことだよ。先に言った分割に基づくモデルではMondrianというアルゴリズムが1番有名だ。Mondrianは準識別子の各属性の値には順序があると仮定する。年齢など数値属性はもちろん都道府県なども適切に順番付けできるものとする」

アリスは続ける。

アリス：「Mondrianはカラムごとにテーブルのレコードをその属性が中央値未満と中央値以上のグループに分けることを試みる。k-匿名化のためには、そのカラムで分けた時どのグループのサイズもk 以上であることが求められる。だから、例えばサイズが2k 未満なグループを分割することはできない。Mondrian では、分割ができなくなるまで、分割が許されるカラムの中で1番いいカラムを選択してレコードを2つのグループに分割することを繰り返す」

シャミア：「1番いいカラムって？」

アリス：「いい質問だね！実は明確な基準はないんだ。ただしMondrianの提唱者たちによるとカラムの値の範囲が広いカラムを選択するのが良いそうだ」

シャミア：「つまり分割に基づくモデルはレコードの値を基準にテーブルを細かく分割する感じか。うん…さっき言ったglobal recodingとlocal recodingだとMondrianはどっちになるの？」

アリス：「どっちもあるよ。先のアルゴリズムはStrict Mondrianと呼ばれる。Strict Mondrianはmulti-dimensionalでglobal recodingを採用したアルゴリズムになる。その他にもRelaxed Mondrianというlocal recodingを採用したアルゴリズムがある。Relaxed Mondrianでは、カラムを選んで分割する時にレコードを均等に2つのグループに分ける。だから準識別子の値が同じレコードでも違うグループになる可能性があるんだ（注釈 2 ）」

喋りすぎたのせいなのかアリスが軽く咳き込んだ。それを見たシャミアがおばあさんに水をもらう。

シャミア：「大丈夫？」

「大丈夫、だとおもう」と説明を続けようアリスだか、シャミアがとたんに「きゃー」と叫ぶ。アリスはギョッと目を見開いて、思わず言葉を飲み込んだ。

シャミア：「あっ、もうこんな時間だ！店を出なきゃ！」

2人慌てて鞄を持って会計を済まして店を出た。ここは駅まで遠くないがもうすぐ電車の発車時間だ。先までキンキンに冷えた喫茶店とは違って外はまだ真夏だ。急いで駅に駆け込む2人は汗でびしょびしょになっていた。そして「さっきの話はまだ終わってないよね」「階層に基づくモデルの話は次回にお預けだね」とふざけながら2人が電車に乗った。

注釈

1. k-匿名化の一般的なプロセスを2ステップに分ける正当性について：k-匿名化処理でレコードをテーブルに追加しないと仮定する。元のテーブルを$T_1$として匿名処理したテーブルを$T_2$とする。$T_2$に準識別子の値の組み合わせが同じなレコードを同じグループにまとめる。$T_2$にて同じグループに所属したレコードを$T_1$にでも同じグループに分けて$T_2$で行った処理を行うと$T_2$になることがわかる（$T_2$で削除された項がある場合その項を*とする）。そのためここでの定式化はk-匿名化のもっとも一般的なフレームワークと考えてもいいだろう。
2. Strict MondrianとRelaxed Mondrianの違い：Strict Mondrianは値を基準にグループ分けするため違うグループのレコードの準識別子の値は必ず違う。Relaxed Mondrianは均等に分割するため準識別子の値が全く同じでも違うグループになる可能性がある。

まとめ

k-匿名性を満たしていないテーブルをk-匿名性を満たすテーブルに変換することをk-匿名化と言う。k-匿名化をする上でモデルが重要である。モデルは概ねglobal recodingとlocal recoding、分割に基づくモデルと階層に基づくモデルなどに分類できる。分割を採用した手法の代表Mondrianをここで取り上げる。Mondrianはすべての準識別子に中央値で分割することを試す。分割した後のどのグループのサイズもk以上の準識別子のなか値の範囲が1番広いカラムを選ぶ。選んだカラムを基準にテーブルを2つのグループに分けてそれぞれ再帰的に分割を続ける。

参考文献（APA形式）

・小池正修, パキンオソトクラパヌン, 伊藤秀将. プライバシーを保護する匿名化技術. 東芝レビュー Vol.70 No.12（2015）.
https://www.global.toshiba/content/dam/toshiba/migration/corp/techReviewAssets/tech/review/2015/12/70_12pdf/f06.pdf

・LeFevre, K., DeWitt, D. J., & Ramakrishnan, R. (2005, June). Incognito: Efficient full-domain k-anonymity. In Proceedings of the 2005 ACM SIGMOD internation

・Samarati, P., & Sweeney, L. (1998). Protecting privacy when disclosing information: k-anonymity and its enforcement through generalization and suppression.

・Domingo-Ferrer, J., Martínez-Ballesté, A., Mateo-Sanz, J. M., & Sebé, F. (2006). Efficient multivariate data-oriented microaggregation. The VLDB Journal, 15(4), 355-369.

・DOMINGO-FERRER, J. O. S. E. P., & TORRA, V. (2005). Ordinal, Continuous and Heterogeneous k-Anonymity Through Microaggregation. Data Mining and Knowledge Discovery, 11, 195-212.

・LeFevre, K., DeWitt, D. J., & Ramakrishnan, R. (2006, April). Mondrian multidimensional k-anonymity. In 22nd International conference on data engineering (ICDE’06)  (pp. 25-25). IEEE.