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.

状況設定
Successful
Linking Attack
Tuple Age Gender

Unsuccessful
Linking Attack
Gender ZIP

Disease22915

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

DiseaseNameAgeGenderZIPHIV

Mia

35Female

Tuple

Aget125Female 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• The disease of Anna is disclosed andher privacy is violated.
• High Data Utility but NO Privacy inOriginal dataset

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 data in original dataset

Clustering + Generalization= k-anonymity

研究内容
SD algorithm suggests to cluster the tuples for generalization through local recoding based on distancecalculation to Enhance the Utility of Data in k-anonymization.

Total Distance (ti, tj) = D(Numerical(ti, tj) ) + D(Categorical(ti, tj) )xi  x jDistance(t1,t2)• Numerical Attribute: D(ti , t j ) Att R(Att)x• Categorical Attribute:x

MaleFemaleCardinality (Attx) = 1 then Distance (a, a) = 0
Distance(t1,t4)
Cardinality(Attx) = 2 then Distance (a, b) = 1
Cardinality(Attx) > 2
Privacy(Kvalue)
VersusUtilityofData
1. Measuring similarity based on observation probability
1
2. Defining distance based on measured similarities
JapanUSAChina

535016Utility•••

Distance(t1,t3)

Patient Data Released by Hospital
Tuples Age Gender ZIP Diseaset125 Female 22370
HIVt2
40 Male 55490 Malaria
t335 Female 22410 Asthma
t4
45 Male 55410 Influenza• Assuming, values in tuple 1 are Male (Gender), Japan (Nationality)• Japan is closer to USA than China based on the contingency table• Because the probability of being Male from Japan is closer
to Male from USA

0.80.60.4
2Datafly

102030K Value (n=5000)
Incognito
Mondrian

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

4050SD