DEIM Forum 2014 E5-2

分類分析のための k -匿名化テーブル評価関数の提案
橋本 翔太†

上土井陽子††

若林 真一††† 広島市立大学情報科学部 〒 731–3194 広島県広島市安佐南区大塚東三丁目 4 番 1 号†† 広島市立大学大学院情報科学研究科 〒 731–3194 広島県広島市安佐南区大塚東三丁目 4 番 1 号
E-mail: †shotah@lcs.info.hiroshima-cu.ac.jp, ††{yoko,wakaba}@hiroshima-cu.ac.jp
あらまし 本研究では分類解析に適した k-匿名化テーブルを作成することを目的として k-匿名化テーブルを評価する関数を定義する．分類分析への入力となる k-匿名化テーブルを作成することを目的とした先行研究は存在するが，作成された表の評価方法は明確になっていなかった．我々は先行研究で導入されたエントロピーを利用した特殊化評価尺度を，テーブル全体を評価する関数に拡張する．
キーワード

階層的 k-匿名化，特殊化，分類1. は じ め に
近年，情報技術の発展により，企業は顧客の機密データを含む大量の情報を所有し，他の企業とも共有できる環境になってきている．企業は，蓄積した大量の情報を顧客に対するサービ

表 1 テーブル TIDClassSexJobSalary(K)1-30Y3N MaleJanitor

30

4-70Y4N MaleMover

32

8-12

2Y3N Male

Carpenter35

13-16 3Y1N Female Technician

37

ス等を考える際に有用に利用したい．しかし，大量の情報をそ

17-22 4Y2N Female Manager

42のまま利用しても，良質なサービスを提供できることにつなが23-25 3Y0N Female Manager

44

らない可能性がある．一方，顧客データを利用するにはプライ

26-28 3Y0N Male

バシ保護できるようデータを変換しなければならない．従来研

29-31 3Y0N Female Accountant 44

究 [1] では，第三者へ公開することを想定し，分類ルールを作

32-33 2Y0N Male

る際にできるだけ有用な情報へ加工する匿名化手法が提案され

34

Accountant 44
Lawyer44

1Y0N Female Lawyer

44ている．しかし，作成された情報に対する評価方法は明示さていなかった．本稿では，データマイニングの手法の 1 つである
分類分析 (Classification：図 1) に適した匿名化テーブル変換問
題を新たに定義し，階層的匿名化フレームワークで利用する評価関数を導出する．

2. 準備

本稿で扱うデータテーブル T は，ID を識別子の集合である識別子属性，D1 , ..., Dp を値の集合である準識別子属性，Class をタイプの集合である型属性としたとき，テーブル
T (ID, D1 , ..., Dp , Class) を各属性に属する値の p + 2 個の列(id, d1 , ..., dp , cls)(id ∈ ID, di ∈ Di (1 <= p), cls ∈ Class)=i<の集合とする．また，テーブル T に属する p + 2 個の値の列をレコードと呼ぶ．また，各属性に含まれる値をドメイン値と呼ぶ．テーブルの例を表 1 に示す．表 1 では 34 個のレコードを

図 2 分類木と森のカット

準識別子属性の値の組合せが同じものを集約し，1 つの行で表現している．例えば，表 1 の 3 行目は，⟨M ale, Carpenter, 35⟩
である 5 つのレコードをもち，そのうち型属性 Class が値 Yであるレコードが 2 つあり，型属性 Class が値 N であるレコー
ドが 3 つあることを表す．本稿では，表を表現する場合，表 1のような集約した形式を用いる．
テ ー ブ ル T (ID, D1 , ..., Dp , Class) の 属 性 の 列 の 部 分 列

A1 , A2 , ..., Al の属性が与えられたとき，T (A1 , A2 , ..., Al ) によって，テーブル T (ID, D1 , ..., Dp , Class) の属性列 A1 , A2 , ..., Alに関する射影を表すとする．

2. 1 k-匿 名 性
テ ー ブ ル T (ID, D1 , ..., Dp , Class) に お い て ，準 識 別子 属 性 の 集 合 を QID={D1 , ..., Dp } と し た と き ，QID の 並 び D1 , ..., Dp に お い て ，p 個 の ド メ イ ン 値の 各 列 (d1 , d2 , ..., dp )(di∈Di ) に 対 し て ，テ ー ブ ルT (ID, D1 , ..., Dp , Class) に属するレコードで，準識別子属

図 1 本研究で対象とする分類分析概要

性の列に対応する値の部分列が (d1 , d2 , ..., dp ) と一致するレ

しているドメイン値である木構造で，実行時に作成される．

コードの集合を S(d1 ,d2 ,...,dp ) とする．準識別子集合 QID の列

また，分類木 T reei における根から葉までの各パス上のノー

D1 , ..., Dp において，定義される全ての p 個のドメイン値のドを正確に 1 つ含むノードの集合をカットといい，属性 Di の

列 (d1 , d2 , ..., dp ) の中で，S(d1 ,d2 ,...,dp ) が空集合ではなく，サ

分類木 T reei におけるカットを cuti で表す．また，各分類木イズが最も小さいという条件を満たす列を (d′1 , d′2 , ..., d′p ) とすのカットを含む集合を分類木の森のカットと呼ぶ (図 2)．

る．このとき，|S(d′1 ,d′2 ,...,d′p ) | を準識別子集合 QID の匿名度A(QID) とする．また，k をユーザ定義の匿名性の閾値とすると，A(QID) >= k ならば，匿名要求 ⟨QID, k⟩ を満たしているとする．
さらに，これを準識別子属性集合 QID の部分集合に対応するよう拡張し，部分集合の列 {QID1 , QID2 , ..., QIDj } におけるテーブル T (ID, D1 , ..., Dp , Class) での各 QIDi の匿名性を A(QID1 ), A(QID2 ), ..., A(QIDj ) とする．そのとき，A(QID1 ) >= k1 かつ,..., かつ A(QIDj ) >= kj ならば，匿名要求{⟨QID1 , k1 ⟩, ..., ⟨QIDj , kj ⟩} を満たしているという．
2. 2 分類木とカット

2. 3 一 般 化
テ ー ブ ル T (ID, D1 , ..., Dp , Class) の あ る レ コ ー ド(id, v1 , ..., vp , cls) ∈ T (ID, D1 , ..., Dp , Class) を 分 類 木 の森 の カット Cut = {cut1 , ..., cutp } を 使って 一 般 化 し ，作
成 さ れ た レ コ ー ド を (id, v1′ , ..., vp′ , cls) と す る ．テ ー ブ ル

T (ID, D1 , ..., Dp , Class) の全てのレコードを一般化することで，一般化テーブルを作成する．以下では，値の一般化についてまず定義し，レコード，テーブルの一般化の定義に拡張する．

2. 3. 1 分類木 cuti による値 vi の一般化
準識別子属性 Di の cuti に含まれる値 vi′ で値 vi を置き換

準識別子属性集合 QID = {D1 , D2 , ..., Dp } の各属性 Di (1 <=えることを general(cuti , vi ) = vi′ と表す．ここで，vi′ は i 番i<= p) に対して，分類木 T reei を次のように定義する．図 2 に目の準識別子属性 Di の分類木 T reei の値 vi から根ノード

分類木の例を示す．

までのパス上のノード集合を path vertex(i, vi ) とするとき，（ 1 ） 属性 Di が分類別的 (categorical) な属性の場合：葉| path vertex(i, vi ) ∩ cuti |= 1 となる分類木 T reei のカット

ノードはドメイン値，親ノードは子ノードよりも特定の度合い

cuti において vi′ ∈ (path vertex(i, vi ) ∩ cuti ) を満たす．値 viの低い値を表す木構造で，実行前に決定されている．と値 vi′ は図 4 に示されている関係にある．

（ 2 ） 属性 Di が連続的 (numerical) な属性の場合：各ノー2. 3. 2 分類木の森 Cut によるレコードの一般化

ドは間隔を表し，葉でない各ノードは型属性 Class における

レ コ ー ド (id, v1 , ..., vp , cls)，分 類 木 の 森 の カット Cut =情報利得 (Inf oGain [1]) を最大にする親の間隔のある最適な 2{cut1 , ..., cutp } が与えられたとき，Cut によって一般化して作分割を表す 2 つの子ノードをもち，葉ノードはテーブルに出現成された一般化レコード (id, v1′ , ..., vp′ , cls) を次の関数により

図 4 特殊化の例
図 3 分類木 T reei における値 vi と値 vi′ の関係問題は，テーブル T ，匿名要求 {⟨QID1 , k1 ⟩, …, ⟨QIDl , kl ⟩}，定義する．

準識別子属性集合 QID のそれぞれの属性に対する分類木を与えたとき，以下の制約条件を満たす匿名化テーブル Tg を作る

General(Cut, (id, v1 , ..., vp , cls)) = (id, v1′ , ..., vp′ , cls)
| vi′ = general(cuti , vi )(1 <=i<= p) (1)ことである．
（ 1 ） 匿名化テーブル Tg は，匿名要求を満たしている．

2. 3. 3 分類木の森 Cut によるテーブルの一般化（ 2 ） 匿名化テーブル Tg は，分類分析のためにできるだけ

テ ー ブ ル T (ID, D1 , ..., Dp , Class)，分 類 木 の 森 の カッ

多くの情報を含む．

ト Cut = {cut1 , ..., cutp } が 与 え ら れ た と き ，テ ー ブ ル3. 1 階層的トップダウンフレームワーク

T (ID, D1 , ..., Dp , Class) を一般化する関数 GeneralT able を

従来研究では，分類分析のための匿名化テーブル変換問題を以下の式を満たす関数と定義する．またこの関数を適用し，得解くためのフレームワークとして，Fung らが TDS(Top-Downられたテーブルを匿名化テーブルという．以降の記述では，表Specialization) フレームワーク [3] を提案している．この TDS

T の匿名化テーブルを Tg と表記する．

フレームワークのフローチャートを図 5 に示す．なお，図中の特殊化のよさを表す関数 Score の引数は省略しているが，型属GeneralT able(Cut, T ) = {(id, v1′ , v2′ , ..., vp′ , cls)

性 Class に関してなるべくまとまったグループに分割できる特| (id, v1 , ..., vp , cls) ∈ T ∧ (id, v1′ , v2′ , ..., vp′ , cls)
= General(Cut, (id, v1 , ..., vp , cls))}

殊化を評価するための関数である．このフレームワークは，最(2)

初にテーブル Tg を分類木で各属性の根となる値で一般化してから，順々に特殊化を行い，匿名化テーブルを作成する．

2. 4 特 殊 化

3. 2 特殊化の指標 Score(v)

元 の テ ー ブ ル T (ID, D1 , ..., Dp , Class) と 準 識 別 子 属 性

D1 , D2 , ..., Dp の分類木 T ree1 , T ree2 , ..., T reep と，それら分類木によって構成される森に対するソリューションカット Cutと Cut に対応する匿名化テーブル Tg (Cut) が与えられているとき，Cut に含まれているノード v をその子ノードの集合child(v) に置き換え，Cut を Cut′ に更新することを特殊化と呼ぶ．つまり，Cut′ = (Cut − {v}) ∪ child(v) である．このと′特殊化 v → child(v) の前後における利得比を表す Score(v)がある．Score(v) は，値 v の上で特殊化の”よさ”を計ることができる．Score(v) の計算式は式 (3) であり，Score(v) を計算する際に必要とする Inf oGain(v) と SplitInf o(v) の計算式について，順に示していく．

Score(v) = GainRatio(v) =′Inf oGain(v)SplitInf o(v)(3)

き，Cut に対応する匿名化テーブル Tg (Cut )，Cut に対応する匿名化テーブル Tg (Cut) を特殊化したテーブルと呼ぶ．ま3. 2. 1 特 殊 化 v′→child(v) に お け る 情 報 利 得Inf oGain(v)た，Cut から Cut への特殊化を v → child(v) と表す．
もし特殊化が特殊化のあとに匿名要求を満たすテーブルを結値 x に一般化された T のレコードの集合を T [x] とする．

果として出力するならば，valid(妥当) である．特殊化は，v に

各 レ コ ー ド は 分 類 ク ラ ス 集 合 CLS に 属 す る ク ラ ス cls を一般化されていたレコード全てが同じクラスをもっていないなもっているとする．クラス cls をもっている T [x] のレコーら，beneficial(有益) である．もしそうでないならば，そのときドの個数を f req(T [x], cls) とする．c ∈ child(v) であるとき，∑c∈child(v) |T [c]| である．I(T [x]) が T [x] のエントロ

特殊化は分類分析にとって役に立つ情報を導かない．よって特|T [v]| =殊化は，妥当かつ有益である場合に限り，実行する．

ピーであるとき，3. 従来研究での匿名化テーブル変換問題

I(T [x]) = −∑cls∈CLS

従来研究で対象とする分類分析のための匿名化テーブル変換

f req(T [x], cls)
f req(T [x], cls)
× log2．
|T [x]||T [x]|(4)•

匿名化テーブル Tg は，匿名要求を満たしている．

目的関数
テ ー ブ ル T (ID, D1 , ..., Dp , Class) の 型 属 性 Class に 関
す る 乱 雑 さ を 計 算 す る 関 数 T ableInf o(T, Cut) の 計 算式 は 式 (7) で あ る ．w は ユ ー ザ が 指 定 す る 重 み 係 数
で あ る ．T ableInf o(Cut, v) を 計 算 す る 際 に 必 要 と す るClassInf o(T, Cut) と SplitInf o(T, Cut) の計算式について，次節より順に示していく．

T ableInf o(T, Cut) = w × ClassInf o(T, Cut)+(1 − w) × SplitInf o(T, Cut)

(7)

4. 2 種々の関数
4. 2. 1 属性値によるテーブルのグループ化
テーブル T と分類木の森のカット Cut = {cut1 , ..., cutp } が与えられたとき，p 個の準識別子属性 D1 , D2 , ..., Dp のカット

cut1 , cut2 , ..., cutp の積集合 cut1 × cut2 × ... × cutp に含まれている p 個の値の組 (v1′ , v2′ , ..., vp′ ) において，テーブル T に含まれているレコード (id, v1 , v2 , ..., vp , cls) の匿名化レコードでその準識別子属性の値の列が (v1′ , v2′ ..., vp′ ) と一致する匿名化レ
コードの集合をグループと呼ぶ．以下にグループの定義を示す．

group((v1′ , v2′ , ..., vp′ ), T, Cut) = {(id, v1′ , v2′ , ..., vp′ , cls)

図 5 TDS フレームワーク| (id, v1 , v2 , ..., vp , cls) ∈ T ∧ (id, v1′ , v2′ ..., vp′ , cls)
= General(Cut, (id, v1 , v2 , ..., vp , cls))}であるので，∑Inf oGain(v) = I(T [v]) −c∈child(v)|T [c]|I(T [c])．
|T [v]|(8)(5)

ま た ，テ ー ブ ル T の 匿 名 化 テ ー ブ ル が n 種 類 の p

3. 2. 2 特 殊 化 v→ child(v) に お け る 分 割 情 報 量SplitInf o(v)

個 の 準 識 別 子 属 性 の 一 般 化 値 の 組 合 せ (v1′ , v2′ , ..., vp′ )′′′′′′の 組 合 せ (v11, v21, ..., vp1), ..., (v1n, v2n, ..., vpn) を持つとInf oGain(v) の値は，多数の子の値をもつ属性の特殊化では

き ，そ れ ぞ れ の p 個 の 値 の 組 合 せ に 関 す る グ ル ー

偏りができ，他の属性よりも高い値をもつ．しかし，多数の子をプ を group1 , ..., groupn と し ，こ の グ ル ー プ の 集 合 をもつ属性を特殊化することは，分類分析にとって有益ではないか

Group(T, Cut) = {group1 , group2 , ..., groupn }⊂=cut1 ×cut2 ×もしれない．これは，分割情報 SplitInf o(v) で Inf oGain(v)· · · × cutp とすると，集合 Group(T, Cut) に属するグループのを割ることにより避けうる．
∑|T [c]||T [c]|SplitInf o(v) = −× log2．
|T [v]||T [v]|は必ず等しい．

和集合の大きさ | ∪g∈Group(T,Cut) g| とテーブル T の大きさ |T |(6)c∈child(v)4. 2. 2 テーブル T のクラスに関する乱雑さ ClassInf o(T, Cut)

4. 新しい分類分析のための匿名化テーブル変換問題

Group(T, Cut) とするとき，Group(T, Cut) に属する任意の従来研究にはなかった一般化テーブル Tg の同じ型属性 Class

group において，クラス cls をもっている group のレコードののラベルをもつレコードを集めてグループ化したいので，クラ個数を f req(group, cls) とする．このとき，各グループ groupスに関する乱雑さを目的関数とし，この目的関数値が最小であのクラスに関する乱雑さ E(group) を式 (9) で定義する．

る一般化テーブルを作成する問題を以下に明確に定義する．

4. 1 問 題 定 義
テーブル T ，匿名要求 {⟨QID1 , k1 ⟩, …, ⟨QIDl , kl ⟩}，準識別子属性集合 QID のそれぞれの属性に対する分類木を与えたとき，匿名化テーブル変換問題は，以下の制約条件を満たしながら，後に詳述する目的関数 T ableInf o(T, Cut) を最小にする匿
名化テーブル Tg を作る問題である．

制約条件カット Cut で匿名化されたテーブル T のグループの集合をE(group) =∑ f req(group, cls)
f req(group, cls)
−× log2|group||group|cls∈Class(9)また，テーブル T のクラスに関する乱雑さ ClassInf o(T, Cut)
は，各グループのクラスに関する乱雑さ E(group) に重み|group|をかけて足し合わせたものであり，以下に定義する．
|T |

表4

ClassInf o(T, Cut)∑|group|=・E(group)
|T |

Class

group∈Group(T,Cut)=−∑cls∈Class∧group∈Group(T,Cut)f req(group, cls)
f req(group, cls)
・log2
|T |
|group|Sex

テーブル T2

Job[1-37)

3Y1N[37-99)

ANY Blue-collar

16Y2N ANY White-collar [37-99)
表5(10)
4. 2. 3 テ ー ブ ル T の レ コ ー ド に 関 す る 乱 雑 さSplitInf o(T, Cut)
本小節では分類ルールを作成する上で，不必要な特殊化が行

Salary(K)

2Y10N ANY Blue-collar

テーブル T3ClassSex

Job

0Y7N

ANY Non-Technical [1-37)

Salary(K)

2Y3N

ANY Technical[1-37)

3Y1N

ANY Technical[37-99)

16Y2N ANY White-collar[37-99)

われていないかを評価する関数としてレコードに関する乱雑さ
表6を定義する．不必要な特殊化とは，表 8 の 6 行目のレコード⟨M ale, P rof essional, [37 − 99)⟩ を例にすると，準識別子属性

テーブル T4ClassSex

Job

0Y7N

ANY Non-Technical [1-35)

Salary(K)Salary の値 P rof essional で特殊化を行うと，レコードが細2Y3N

ANY Technical[1-37)

かく分類されてしまうような特殊化といい，分類ルールを作る

3Y1N

ANY Technical[37-99)という目的に反するので不必要な特殊化という．

16Y2N ANY White-collar[37-99)

カット Cut で匿名化されたテーブル T のレコードの個数を
表7|T |，テーブル T のグループの集合を Group(T, Cut) とする．
このとき，テーブル T のレコードの乱雑さ SplitInf o(T, Cut)
は式 (15) である．

SplitInf o(T, Cut)∑=−group∈Group(T,Cut)|group||group|× log2
|T |
|T |

(11)

Sex

Job

0Y7N

Male

Non-Technical [1-35)

2Y3N

Male

Technical

3Y1N

Traw , Tinit , T1 , T2 , T3 , T4 , T5 , Tf inal を例に計算してみる．テー

Salary(K)Female Technical[35-37)[37-99)

11Y2N Female White-collar[37-99)

5Y0N[37-99)

4. 3 匿名化テーブルの情報量比較
以上に定義した関数を表 1 から表 8 のテーブル

テーブル T5Class

MaleWhite-collar

表8テーブル Tf inal

ClassSex

Job

0Y7N

Male

Non-Technical [1-35)

Salary(K)

2Y3N

Male

Technical[35-37)

3Y1N Female Technical[37-99)

化されている初期テーブル，Ti (1 <=i<= 5) は i 回目の特殊化後

7Y2N Female Manager[37-99)のテーブル，Tf inal は最後に出力される匿名化テーブルである．

4Y0N Female Professional[37-99)

5Y0N[37-99)ブル Traw は生のデータテーブル，テーブル Tinit は最も一般

テーブル T のクラスに関する乱雑さ ClassInf o，テーブル

Male

Professional

T のレコードに関する乱雑さ SplitInf o，目的関数であるテー
表9

ブルの乱雑さ T ableInf o の計算結果を表 9 に示す．表 9 から，•特殊化が進むにつれて，関数 ClassInf o の値が減少，関テーブル

関数値の例 (重み係数 w = 98)

ClassInf o SplitInf o T ableInf o

Traw

0.40023.20100.4562Tinit

0.959600.9404

T1

0.60120.93660.6079

T20.5912

1.37920.6070テーブル Tf inal の乱雑さの差は，匿名要求による差である．

T30.5046

1.7251

0.5290といったことが分かる．

T40.5046

1.7251

0.5290

T50.4750

2.17630.5090Tf inal0.44052.51680.4820

数 SplitInf o の値が増加している．

•

特殊化が進むにつれて，関数 T ableInf o の値が減少する．

•生のデータテーブル Traw と最後に出力される一般化

表 2 テーブル Tinit

ClassSex

Job

Salary(K)21Y13N ANY ANY [1-99)

5. 組織的なトップダウン k-匿名化
表3ClassSex

テーブル T1

Job

Salary(K)5. 1 新しい特殊化の指標 Score(T, Cut, v)

2Y10N ANY ANY [1-37)

表 2 のテーブル Tinit と表 3 のテーブル T1 を例に評価関数

19Y3N ANY ANY [37-99)

値の比較を行い，特殊化によるスコアを導出する．表 9 のテー
ブル Tinit , T1 の関数 T ableInf o の関数値に注目する．特殊化[1 − 99) → {[1 − 37), [37 − 99)} を行うと，テーブル Tinit , T1

の関数値 T ableInf o は 0.9404 から 0.6079 に 0.3325 だけ減少

5. 1. 2 テーブル T のレコードに関する乱雑さの利得差関数していることが分かる．この関数値の差分は属性 Salary の値[1 − 99) の特殊化 [1 − 99) → {[1 − 37), [37 − 99)} による，テー

SplitInf oGain(T, Cut, vi )テーブル T のレコードに関する乱雑さの利得差関数をブルの目的関数値の最小化に関する貢献であると考えることがSplitInf oGain(T, Cut, vi ) とするとき，式は次のように定義でき，目的関数値の差分を値 [1 − 99) の Score とする．

される．

また，目的関数値の差分 Score は，T ableInf o(Tinit , Cut) −T ableInf o(T1 , Cut′ ) と表現できるが，関数 T ableInf o の引数に特殊化をする値 v が明示されていないため，値 v を引数にSplitInf oGain(T, Cut, vi ) =∑|group||group|=・log2|T ||T |group∈Group(T,Cut)∧V al(group,i)=vi含めた関数 Score(T, Cut, v) として次節で定義する．本研究において，テーブルの乱雑さの最小化を目的としているので，特殊化前後における目的関数値の差分が大きい，すなわち関数

Score(T, Cut, v) の値が最も大きい値 v で特殊化を行うことを，−∑group∈Group(T,Cut′ )∧V al(group,i)∈child(vi )|group||group|・log2|T ||T |(15)

制約条件を満たさなくなるまで繰り返すことにより，目的関数

5. 2 組織的なトップダウン k-匿名化アルゴリズム

値を最小化する．
次節で，特殊化 v → child(v) の前後における利得差を表す関数 Score(T, Cut, v) を定義する．また関数 Score(T, Cut, v)
は ，分 類 分 析 に つ い て ，現 在 の Cut に お け る 値 v の 上 で特殊化の “よさ”を示す．関数 Score(T, Cut, v) の計算式は，式 (12) であり，Score(T, Cut, v) を計算する際に必要となる

Inf oGain(T, Cut, v) と SplitInf o(T, Cut, v) の計算式につい前節で定義した特殊化の指標 Score を用いたアルゴリズムのフローチャートを図 6 に示す．最初に分類木 T ree の最上の値でテーブル，森のカット Cut を初期化することにより，匿名化を行うトップダウンなアルゴリズムである．
このアルゴリズムと前述した図 5 の TDS フレームワークとの大きな違いは，Score の更新に関する部分である．従来は特殊化する値の子集合に対して Score を計算していたが，提案すて，順に示していく．

るアルゴリズムでは特殊化をするたびに Cut に属する全てのScore(T, Cut, vi )値に対して，新しい Cut を使って Score を更新する．これに= w × ClassInf oGain(T, Cut, vi )より，特殊化前後のテーブル全体がどれだけ分類分析に適して+(1 − w) × SplitInf oGain(T, Cut, vi )(12)

いるかを表す目的間数値 T ableInf o を活かした特殊化を選択することが可能となる．

5. 1. 1 テーブル T のクラスに関する乱雑さの利得差関数
ClassInf oGain(T, Cut, vi )現在のカット Cut から，第 i 番目の準識別子の分類木のカッ
ト cuti に属する値 vi で特殊化 vi → child(vi ) を行った後のカット Cut′ = (Cut − {vi }) ∪ child(vi ) とする．ここで，child(vi )は分類木における値 vi の子の集合である．テーブル T のクラスに関する乱雑さの利得差関数 ClassInf oGain(T, Cut, vi ) は，式 (13) になる．

ClassInf oGain(T, Cut, vi )= ClassInf o(T, Cut) − ClassInf o(T, Cut′ )(13)

値 vi や子の値 child(vi ) を用いて表すと式 (14) となる．式 (14)の関数 V al は，テーブル T (ID, D1 , ..., Dp , Class) の一般化
テーブルにおけるグループ group と整数 i(1 <= p) が与え=i<られたときに，group に属する全てのレコードが共通してもっている i 番目の準識別子属性に対応する値を返す関数とする．

ClassInf oGain(T, Cut, vi )∑|group|=・E(group)|T |group∈Group(T,Cut)∧V al(group,i)=vi−∑′

group∈Group(T,Cut )∧V al(group,i)∈child(vi )|group|・E(group)
|T |

(14)

図 6 組織的なトップダウン k-匿名化アルゴリズムのフローチャート6. まとめと今後の課題
本研究では，分類分析を目的として作成された k-匿名化テー
ブルを評価する関数を提案した．さらに，階層的匿名化フレームワークで利用する評価関数を導出した．
今後の課題としては，提案階層的 k-匿名化手法の実験的性能評価，および，集中的に管理されたテーブルのみならず，分散環境下にあるテーブルに対してもプライバシーを保護しながらk-匿名化テーブルを作成する手法の考案があげられる．
文献[1] Noman Mohammed, Benjamin C. M. Fung and Mourad
Debbabi “Anonymity meets game theory:secure data integration with malicious participants,” VLDB Journal, pp.
567-588, 2011.
[2] Jiawei Han and Micheline Kamber, “Data Mining : Concepts and Techniques,” Morgan Kaufman Pub., 2001.
[3] Benjamin C.M., Fung, Ke Wang, and Philip S. Yu, Fellow,
IEEE “Anonymizingclassificationdata for privacy preservation,” IEEE TKDE 19(5), 711725, 2007.
[4] Ke Wang, Benjamin C. M. Fung, and Guozhu Dong,“Integrating
Private Databases for Data Analysis,” Intelligence and Security Informatics Lecture Notes in Computer Science Volume 3495, pp171-182, 2005.