An Efficient Local Recoding Anonymization in Data without
Hierarchical Taxonomies
階層的分類を伴わない効果的な匿名化のためのローカルリコーディング
Mohammad Rasool Sarrafi Aghdam

Professor Noboru Sonehara

どんな研究？

Abstract

個人情報を保護するために，データを公開する際にプライバシー保護のために広く用いられているモデルとしてk-匿名性（k-anonymity）がある。
k-匿名性とは，個人情報から個人を特定することを難しくするための技術である。しかしながら，k-匿名性を用いたデータは情報が喪失されるため正確さに欠ける。現存するk-匿名化アプローチは大規模な情報喪失という点において問題がある。
そこで我々はattributes hierarchical taxonomies から独立した数値属性とカテゴリー属性を含むデータ間の距離の計算にもとづく新しいモデルとSpatialDistance (SD) ヒューリスティックアルゴリズムを提唱する。我々の研究では，SDは既存のよく知られているアルゴリズムに比べて有意に情報喪失を減少させることが示されている。

To protect the privacy of individuals, a model that is widelyused for privacy preservation in publishing micro-data, is kanonymity. It reduces the linking confidence between sensitive
information and specific individual. However, k-anonymous
dataset loses its accuracy due to the information loss. Most of
the existing k-anonymization approaches suffer from huge
information loss. We propose a new model and SpatialDistance(SD) heuristic algorithm based on distance calculation
between tuples including numerical and categorical attributes
which is independent of attributes hierarchical taxonomies andenhances the data utility significantly.

状況設定
Unsuccessful
Linking Attack

Successful
Linking Attack
Tuple Age Gender

Gender ZIP

Disease22915

t1 = t1&t3 25 ~ 35 Female 22***HIVZIP

DiseaseNameAgeGenderZIPHIV

Mia

35Female

Tuple

Age

t125Female 22370

t240

Male55490 Malaria

Jack40

Male75942

t2 = t2&t4 40 ~ 45 Male 554** Malaria

t335Female 22410 Asthma

Anna

25Female

22370

t3 = t1&t3 25 ~ 35 Female 22*** Asthma

t445MaleSara35Female

65784

t4 = t2&t4 40 ~ 45 Male 554** Influenza

55410 Influenza

External Data

Patient Data Released by Hospital

2-Anonymous Patient Dataset• Linking confidence is reduced by 1/k ratio• The privacy of individuals is protected tosome extent. However, the data is NOT as
accurate as the original Patient Data

• The disease of Anna is disclosed andClustering the tuples and thenher privacy is violated.
Generalization to achieve k-anonymity• High Data Utility but NO Privacy

研究内容
SD algorithm uses distance calculation for clustering the tuples for generalization through local recodingto Enhance the Utility of Data in k-anonymization.
Total Distance (ti, tj) = D(Numerical(ti, tj) ) + D(Categorical(ti, tj) )x j − xk

Distance(t1,t2)• Numerical Attribute: D (t j , t k ) Att =iR( Atti )• Categorical Attribute:

Distance(t1,t3)

Cardinality (Atti) = 1 then Distance (a,a) = 0
Cardinality(Atti) = 2 then Distance (a,b) = 1
Cardinality(Atti) > 2
1. Measuring similarity based on observation probability
2. Defining distanceJapan USA ChinaFemale

535016• Assuming, values in tuple 1 are Male (Gender), Japan(Nationality)• Japan is closer to USA than China• Because the probability of being Male from Japanand Male from USA is closer

Distance(t1,t4)

1Utility•••

MaleTuples Age Gender ZIP Diseaset125 Female 22370
HIV
t2
40 Male 55490 Malaria
t3
35 Female 22410 Asthma
t4
45 Male 55410 Influenza
Patient Data Released by Hospital

Privacy Level (K value) VS Utility of Data

0.8
0.6
0.4
2Datafly

102030K Value (n=5000)

Incognito

Mondrian

連絡先： Mohammad Rasool Sarrafi Aghdam ／ 総合研究大学院大学 複合科学研究科情報学専攻
Email : rasool@nii.ac.jp

4050

SD