k-匿名化

k-匿名化は、準識別子(同一属性)のデータがk件以上になるようにデータを変換。個人が特定される確率をk分の1以下に低減して特定を困難にする技術です。

似たデータをk+1個用意することで、1/k にする

識別子、準識別子は作成者が決める必要がある

kの最適値は2or3説、5or10説があるらしい

20だとデータが壊れるらしい

MeyersonとWilliamsは2004年に最適なk-匿名化はNP困難な問題であることを示したが、2005年にBayardo、Agrawalにより示されたk-最適化のようなヒューリスティックな解法はしばしば良い結果を生み出す。 概ねO(log k)の計算量であるという証明のある、k-匿名化問題を解くことができる実用的な近似アルゴリズムがKenigとTassaによって示された

意外と奥深くてウケる