k-匿名化の手法

ウィキペディア小見出し辞書

k-匿名化の手法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/03/10 08:48 UTC 版)

「k-匿名性」の記事における「k-匿名化の手法」の解説

k-匿名化問題において、データベースはn行m列の表形式である。それぞれの行はデータベースに収載された、ある特定の個人を表している。なお、それぞれの値が全て異なった値である必要はない。各列の値はその行の人の属性値である。「名前」「識別番号(ID)」など個人をはっきり指し示す属性を識別子と呼ぶのに対し、「年齢」「性別」「居住地」など単体では特定できないが、組み合わせることによって個人の特定が可能になる属性を「準識別子（quasi-identifier）」と呼ぶ。また、「年収」や「持病」など人に知られたくない属性を「センシティブ属性」（もしくは「要配慮属性」）と呼ぶ。 下の表は匿名化されていない日本の愛知県名古屋市にある架空の病院の患者の一覧である。 識別子 準識別子 センシティブ属性 名前年齢性別居住地宗教病気伊藤 29 女 静岡県浜松市 神道 ガン 黒田 24 女 愛知県豊田市 無宗教 ウイルス感染症 山本 28 女 静岡県浜松市 仏教 ガン 高橋 27 男 岐阜県各務原市 仏教 結核 加藤 24 女 愛知県名古屋市 キリスト教 心血管疾患 田中 23 男 岐阜県大垣市 仏教 結核 斎藤 19 男 愛知県春日井市 無宗教 ガン 岡田 29 男 岐阜県岐阜市 無宗教 心血管疾患 林 17 男 愛知県名古屋市 無宗教 心血管疾患 鈴木 19 男 愛知県名古屋市 仏教 ウイルス感染症 このデータには6つの属性と10人分のデータが含まれている。あるkの値に対してk-匿名性を達成するための処理は主に2つある。 抑制: この処理では、ある属性の一定の値をアスタリスク「*」で置換する。その列の全てないし一部の値が「*」に置換される。下の匿名化した表においては、「名前」のすべての値と「宗教」のすべての値を「*」で置換した。 一般化: この処理では、個々の属性値を広い範囲に置換する。たとえば、年齢の「19歳」は「10代」に、「23歳」は「20代」にといった具合である。 以下に匿名化した表を示す。 識別子 準識別子 センシティブ属性 名前年齢性別居住県宗教病気* 20代 女 静岡県 * ガン * 20代 女 愛知県 * ウイルス感染症 * 20代 女 静岡県 * ガン * 20代 男 岐阜県 * 結核 * 20代 女 愛知県 * 心血管疾患 * 20代 男 岐阜県 * 結核 * 10代 男 愛知県 * ガン * 20代 男 岐阜県 * 心血管疾患 * 10代 男 愛知県 * 心血管疾患 * 10代 男 愛知県 * ウイルス感染症 同一の準識別子の組み合わせをもつ同値類は4つある。 識別子 準識別子 センシティブ属性 同値類名前年齢性別居住県宗教病気A * 20代 女 静岡県 * ガン * 20代 女 静岡県 * ガン B * 20代 女 愛知県 * ウイルス感染症 * 20代 女 愛知県 * 心血管疾患 C * 20代 男 岐阜県 * 結核 * 20代 男 岐阜県 * 結核 * 20代 男 岐阜県 * 心血管疾患 D * 10代 男 愛知県 * ガン * 10代 男 愛知県 * 心血管疾患 * 10代 男 愛知県 * ウイルス感染症 このデータは「年齢」「性別」「居住県」において2−匿名性を達成している。なぜならば、これらの属性の組み合わせではどの組み合わせにおいても2人以上になるためである。どの準識別子の組み合わせでも、k-匿名性を満たすデータセットにおいてはk人以上のレコードが該当する。 MeyersonとWilliamsは2004年に最適なk-匿名化はNP困難な問題であることを示したが、2005年にBayardo、Agrawalにより示されたk-最適化のようなヒューリスティックな解法はしばしば良い結果を生み出す。概ねO(log k)の計算量であるという証明のある、k-匿名化問題を解くことができる実用的な近似アルゴリズムがKenigとTassaによって示された。