DEIM Forum 2016 F8-3

Clustering-based approach for achieving 𝑘-anonymization
Xiaoshuang Xu†

Masayuki Numao‡†The University of Electro-Communications, 1-5-1 Chofugaoka, Chofu, Tokyo 182-8585‡The University of Electro-Communications, 1-5-1 Chofugaoka, Chofu, Tokyo 182-8585

E-mail: †xuxiaoshuang1988@gmail.com,‡numao@cs.uec.ac.jp

Abstract This paper proposed an efficient generalized clustering method which derives from the 𝒌-means algorithm for achieving 𝒌anonymization with good data quality and minimum information loss. We defined the distance function for the three major attribute types:
numerical type, categorical type, and structural type. Then we proceeded the method in two stages: preprocessing stage and postprocessing𝒏stage. The preprocessing stage is to partitions all records into⌊ ⌋ groups, and then add the records that are naturally similar to each other into𝒌every group. The postprocessing stage is to add each remaining record into a cluster with respect to which the increment of the information
loss is minimal. We experimentally compared our method with other two clustering-based 𝒌-anonymization methods. The experiment showedthat our method outperforms their method and also ensures the anonymization of data.

Keyword 𝒌-anonymization, 𝒌-means, distance function, information loss

1. Introduction

anonymization [1, 2, 3] was proposed. It requires that each

In recent years, the privacy leakage has now become one

record in a table is indistinguishable from at least 𝑘 − 1of the important major concerns. Many companies andother records [1]. Therefore, privacy related information

organizations have collected and stored a large amount ofcannot be revealed from 𝑘-anonymity protected table. For

information and operational data. The data normallythe past years 𝑘 -anonymization has been extensively

contains a lot of personal details and sensitive information

studied especially one of approaches called generalizationsuch as name, birthdate, address, e -mail and disease etc. In[2, 5, 6, 10] which have successful achieved the privacy

general, companies and organizations need to do some

protection [9, 10, 11]. Table Ⅱ is a 3-anonymization version

privacy-preserving techniques when publishing data. For

by using generalization approach. In table Ⅱ , the data

example, a set of records with person’s basic information

values of TableⅠ in attributes Gender, Region and Age

may be released by an organization to facilitate useful data

has been generalized as common values(for instance, theanalysis or research. Records in TableⅠ is an example ofage of the person ID A0002 has been generalized toperson’s basic information records collected by a company.

[30,40] ) and the number of records in its two equivalence

The company must ensure that no other organization canclasses are both equal to three. As a result, give n TableⅡ ,infer the personal information or even identify aneven if an organization has the quasi -identifier values

individual since it will cause very serious impact o n society.

about the person of ID A0002, they cannot exactly identify

The process of protecting such a table is to remove all thethe record of ID A0002 from the first equivalence classes.

explicit identifiers, such as name from the table. However,

The purpose of data privacy preservation is then achieved.

even though a table is free of explicit identifiers, some of
TABLE I. P ERSON AL INFORM AT ION IN A COMPANY

the remaining attributes in combination could be specificenoughtoidentify

individuals.

For

example,thecombination of {Gender, Region, Age} can be used to
identify an individual and has been called a quasi -identifierin literatures. If an organization has the backgroundknowledge about the person of ID A0002, that is: Genderis Male, Age is 38, and Region is Tokyo, he can accurately
infer the person of ID A0002`s Disease, that is Bronchitis.
To prevent privacy leakage or against identifying
individuals, a simple and practical privacy-preserving 𝒌-

ID

A0001
A0002
A0003
A0004
A0005
A0006

GenderMale
Male
FemaleMale
FemaleFemaleRegionAge

DiseaseKanagawa
Tokyo
Chiba
Kyoto
Kobe
Nara

40
38
37
28
25
23

Flu
Bronchitis
Bronchitis
CancerFlu
CancerDEIM Forum 2016 F8-3

stages: preprocessing stage and postprocessing stage. The

TABLE II. 3- ANONYM IZ AT ION T AB LE
G-ID

1
1
1
2
2
2

Gender

Male
Male
Male
FemaleFemaleFemale𝑛RegionAge

DiseaseKantouKantouKantouKansaiKansaiKansai[30,40][30,40][30,40][20,30][20,30][20,30]Flu
Bronchitis
Bronchitis
CancerFlu
Cancerpreprocessing stage is to partitions a ll records into ⌊ ⌋𝑘groups, and then add the records in its nearest group. Afterthe preprocessing stage, a set of clusters are constructed,
but some of records might remain. The postprocessing
stage is to adjust the remaining records, which adds eachrecord into a cluster with respect to that the increment of

Although the generalization based 𝑘 -anonymization

the information loss is minimal.

have successfully achieved the privacy preservation, there

The rest of this paper is organized as follows. Section 2

is a serious issue on that it decreases data quality a lot after

reviews the basic concepts of 𝑘–anonymization. In section

anonymized. To ensure data mining performance, utility

3, we talked about the exiting technique on this f ield. Inshould be taken into account. One of the direct measuressection 4, we present the details of our generalizationof the utility of the generalized data is information loss

algorithm. In section 5, we experimentally evaluate the[4]. Generally speaking, the less the information loss in theefficiency and effectiveness of our algorithm. Finally, the𝑘 -anonymity protected table makes, the larger the table

paper is concluded in Section 6.

usability is. Clustering [11] is a method commonly used toautomatically partition a data set into many groups, which

2. Fundamental definitions

aims at grouping a set of records into clusters so thatIn this section, we give the definitions of basic concept

records in a cluster are similar to each other and areabout 𝑘-anonymization. Let 𝑇 denote a microdata tabledifferent from records in other clusters. In the clustering-

like Table Ⅰ that contains the private information of a set

based 𝑘-anonymity protected table, if the records that willof individuals and has privacy-related attributes.

be assembled as an equivalence class are more similar to

2.1. 𝒌-anonymization table
Definition 1 (Quasi-identifier Attribute Set). A quasi-

each other with respect to an attribute set, it reduces the
much

more

information

loss

for

generalizingtheequivalence class.
In this paper we proposed an efficient clustering based
𝑘 -anonymization to ensure good data quality withminimum information loss and to realize the good
performance. At the heart of every clustering problem are
the distance functions that measure the dissimilarities
among data points. The distance functions are us ually
determined by the type of data. As the data in the 𝑘 anonymity problem are always person -specific records thattypically consists of the three major types: numerical type(such as age), categorical type (such as nationality), we
need a distance function that can handle both types of dataat the same time. This motivated us to define the distancefunction for the three major type respectively irrespectiveof the background for attributes. The distance function
without regard to the background of data type is calculatedby the numbers of each attribute to be generalized and thenumbers of generalized attribute, which has a meaning ofgeneral purpose for any kind of data and makes theclustering calculate very easy and fast as well. Ourclustering approach was based on the 𝑘-means clustering
which will produce some clusters that do not satisfy the 𝑘size condition. Therefore, we proceed the partitions in two

identifier

attribute

set

QI

=

{𝐴1 , 𝐴2 , … , 𝐴𝑑 } ⊆{𝐴1 , 𝐴2 , … , 𝐴𝑛 } is a set of attributes in a table which canpossibly be joined with other tables in order to reveal the
personal identity of individual records. For example,
attribute set {Gender, Region, Age} in Table Ⅰ is a quasiidentifier set. If the table is joined with other tables, it may
reveal more information of personal information.
Definition 2 (equivalence class). An equivalence classof a table with respect to a quasi-identifier attribute set isthe set of all records in the table containing identical values
for the quasi-identifier attribute set. For example, records
1 and 2 in TableⅡ form an equivalence class with respecttoattribute

set{Gender,

Region,Age} .

Their

corresponding values are identical.
Definition 3 ( 𝒌-anonymity Property). A table is 𝑘 anonymous with respect to a quasi -identifier set if the sizeof every equivalence class is 𝑘 or more. 𝑘 -anonymity
requires that each record in a table with re spect to a quasiidentifier set is indistinguishable from at least 𝑘 − 1 otherrecords [3]. For example, Table Ⅱ satisfies 3-anonymity
property since equivalence class {Male, Kantou, [30, 40]}and {Female, Kansai, [20, 30]} occur three times.
Definition 4 (𝒌-anonymization). A table is said to be a𝑘-anonymization of the table if the table after anonymized

DEIM Forum 2016 F8-3

satisfies the 𝑘 -anonymity property with respect to thevalues (e.g., {Japan, China}) or a single value thatquasi-identifier set. For example, TableⅡ is a table of 𝑘-

represents such a set (e.g., Asia).

anonymization.

3.1. Generalization based 𝐤-anonymization
Recently, many generalization approaches have been

2.2. Information loss
𝑘 -anonymization by generalization or any other way

proposed. Mainly there are two ways to achieve k -usually causes information loss. The idea of information

anonymity,

loss is used to measure the amount of information loss due

generalization. The domain generalization happens at the

𝑘 -anonymization. There are various methods of

domain level. If a lower level domain needs to be

devoting information loss. The measurement in this paper

generalized to a higher level domain, all the values in theis based on the description given by Byun et al [4]. Please

lower domain are generalized to the higher domain. This

also refer to Byun et al. for more details.

restriction could be a significant drawback in that it may

to

Let 𝑇 denote a set of records with 𝑚 numeric quasiidentifiers

𝑁1 , 𝑁2 , … , 𝑁𝑚𝑠andcategorical

namelydomaingeneralization

and

local

lead to relatively high data distortion due to unnecessary

quasi-

generalization. A local generalization method generalizes

identifiers 𝐶1 , 𝐶2 , … , 𝐶𝑠 . Let 𝑃 = { 𝑃1 , 𝑃2 , … , 𝑃𝑝 } be a

attribute values at cell level. This method allows values𝑝⋃𝑖=1 𝑃𝑖 = T, andpartitioning of 𝑇, such that

𝑃𝑖 ∩ 𝑃𝑗 = ∅ forfrom different domain levels to be combined to represent a

any 𝑖 ≠ 𝑗 . To generalize the values of each categoricalgeneralization and hence may minimize the distortion of an

attribute 𝐶𝑖 (𝑖 = 1, 2,…,𝑆), let 𝑇𝑐𝑖 be the taxonomy tree

anonymousdefined for the domain of 𝐶𝑖 .

algorithm but it is impractical and another DataFly [2] is atable.

Sweeney

proposed

MinGen[1,2]Consider a cluster 𝑃 in 𝑇 which consists of someglobal recoding algorithm. A lot of papers con clude thatnumerical and categorical attributes. Let 𝑁𝑖𝑚𝑎𝑥 , 𝑁𝑖𝑚𝑖𝑛

optimal k-anonymization is NP -hard. The objectives of 𝒌-

devote the max and min values of the records in 𝑃 and
𝑇𝑁 𝑖 , 𝑇𝑁 𝑖 be the max and min values of the records inanonymization is to modify a table to satisfy the 𝒌 -𝑇 with respect to numeric attribute 𝑁𝑖 (𝑖 = 1, 2,..., 𝑚).

original table after anonymized.

Also let ⋃ 𝑐𝑖 devote the union set of values in 𝑃 with

3.2. Clustering based 𝒌-anonymization

𝑚𝑎𝑥

𝑚𝑖𝑛

anonymity property, and to minimize the distortion from its

respect to the categorical attribute 𝐶𝑖 (𝑖 = 1, 2,…,𝑆). Then

Clustering is the problem of partitioning a set of records

the amount of information loss due to generalizing 𝑃 ,into groups such that records in the same group are moredenoted by 𝐼𝐿(𝑝) is defined as:

similar to each other than records in other groups with

𝑰𝑳(𝒑) = |𝐞|.(∑𝒎𝐢=𝟏

𝑵𝒊𝒎𝒂𝒙 −𝑵𝒊𝒎𝒊𝒏
𝑻𝑵 𝒊

𝒎𝒂𝒙

−𝑻𝑵 𝒊

𝒎𝒊𝒏

𝒑

+ ∑𝐢=𝟏

𝑯(∧(⋃ 𝒄𝒊 ))𝑯(𝑻𝒄𝒊 )

respect to some defined similarity criteria. In the k -)anonymity protected table, if the records are more similar

where |e| is the number of records in cluster 𝑃. ∧ (⋃ 𝑐𝑖 )to each other with respect to an attribute set, it reduces theis the subtree rooted at the lowest common ancestor of

more information loss for generalizing the equivalence

every value in ⋃ 𝑐𝑖 . And 𝐻(𝑇𝑐𝑖 ) is the height of taxonomy

class. That is the reason why the k-anonymity model cantree 𝑇𝑐𝑖 .

be addressed from the viewpoint of clustering.

Consider that the total number of records in 𝑇 is

Byun et al. [4] proposed the greedy 𝑘-member clustering

partitioned into 𝑃 clusters, namely 𝑃 = { 𝑃1 , 𝑃2 , … , 𝑃𝑝 }.

algorithm.

The total information loss of 𝑇 is the sum of theselecting a record r as the seed to start building a cluster,

information loss of each 𝑃1 (𝑖 = 1, 2,…,p). Therefore theand subsequently selecting and adding more records to thetotal information loss will be:cluster such that the added records incur the least

𝑵𝒊𝒎𝒂𝒙 −𝑵𝒊𝒎𝒊𝒏𝐩

𝑰𝑳(𝑻) = ∑𝐢=𝟏 |𝐞|. (∑𝒎
𝐢=𝟏

𝑻𝑵 𝒊

𝒎𝒂𝒙

−𝑻𝑵 𝒊

𝒎𝒊𝒏

𝒑

+ ∑𝐢=𝟏

𝑯(∧(⋃ 𝒄𝒊 ))𝑯(𝑻𝒄𝒊 )

This

algorithm

works by first

randomly

information loss within the cluster. Once the number of)records in this cluster reaches 𝑘, this algorithm selects a
new record that is the furthest from r, and repeats the same

3. Existing Techniques

process to build the next cluster. When there are fewer thanIn the section of introduction, we talked about k -𝑘 records not assigned to any cluster yet, this algorithm

anonymization achieved by the generalization approach,then individually assigns these records to their closest

which

but

clusters. This algorithm has two drawbacks. First, it is slow.

semantically consistent values. Typically, numeric values

Second, it is sensitive to outliers. To build a new cluster,

are

and

this algorithm chooses a new record that is the furthest

categorical values are generalized into a set of distinct

from the first record selected for the previous cluster. If thereplaces

generalized

real
into

valueswithintervals

less(e.g.,

specific[30−40]),DEIM Forum 2016 F8-3

data contains outliers, it is likely that outliers have a great

numbers of generalized attribute. And then give them thechance of being selected. If a cluster contains outliers, theappropriate weight.

information

4.1. Distance function

loss

of

this

clusterincreases.

Theirexperimental results showed that the k-member algorithm

Definition 5 (numeric values) About the values ofcauses significantly less information loss than another k -numeric attribute type, we note that there are three kinds

anonymization technique called “Mondrian” proposed byof values in the data. First one is continuous value like age

LeFevre et al.

(such as 35, 36, 37,…, etc.). Second one is 2 -values typeTo reduce the information loss and execution time

like gender. If the male is set as 1, the female can only berecently Lin and Wei [8] proposed an efficient one -pass 𝑘

0. The last one is hierarchical data like education. The-meanvalue are of hierarchy such as grade of 1st-4th, 5th-6th,clustering

problem.

Theyshowed

that

their

algorithm performs better than the proposed algorithm of

7th-8th,9th,10th,11th,12th,...etc.

Byun et al. with respect to both execution time andhierarchical values into hierarchical numeric values: 0,Weconvertthese

information loss. Like Chiu and Tsai’s algorithm, this

1,2,3,4,5,6,7,…,etc.

algorithm forms all clusters at a time. According to their

Let 𝑆𝑁𝑖 be the standard deviation of the records in 𝑇

methods first sort all records by their quasi -identifiers,

with respect to numeric attribute 𝑁𝑖 (𝑖 = 1, 2,…, m). Then𝑛then determine approximate number of clusters, by ⌊ ⌋ ,𝑘where 𝑘 is the cluster size. Then randomly select 𝑃
records as seeds to build 𝑃 clusters. For each record 𝑟

the distance between numeric values 𝑁1 , 𝑁2 , devoted as:|𝑹𝑵 𝒊 |−𝟏

𝑵𝑵𝒊 (𝑵𝟏 , 𝑵𝟐 ) =|𝑵𝒊 |−𝟏.

𝑵𝟏 −𝑵𝟐(3)

𝑺 𝑵𝒊|𝑁𝑖 |is the numbers of numeric attribute to be

the algorithm finds the cluster that is closest to 𝑟, assigns 𝑟

generalized and |𝑅𝑁 𝑖 | is the numbers of generalized

to that cluster and subsequently updates the center point.

numeric attribute.

Finally, if some clusters contain more than 𝑘 records
remove excess records from tho se clusters that are

Definition 6 (categorical values). We specify thedissimilar to most of the records and then add these records

attribute such as nationality or occupation as theto other similar clusters (whose size is less than 𝑘 ).

categorical type. Let 𝐶𝑖 denotes 𝑆 categorical quasi-

Although this method has less execution time there is still

identifiers𝐶1 , 𝐶2 , … , 𝐶𝑠 . The normalized distance betweena chance of being affected by extreme values. Again if thi s

two categorical values 𝑣𝑖 , 𝑣𝑗 ∈ 𝑁 is defined as:algorithm first selects p records that come from the sameequivalent class then the total information loss will behigher.

𝑵𝑪𝒊 ( 𝒗𝟏 , 𝒗𝟐 )=|𝑹𝑪 𝒊 |−𝟏

(4)

|𝑪𝒊 |−𝟏|𝐶𝑖 |is the numbers of categorical attribute to begeneralized and |𝑅𝐶 𝑖 | is the numbers of generalized

4. Clustering based approach

categorical attribute.

In this section, we will present the details of our efficient
generalized clustering method based 𝑘 -anonymization.

Definition 7 (Distance between two records) Let 𝑇
denotecontains a variety of attribute types to satisfy the 𝑘 -identifiers

anonymity property, and to minimize the information loss

identifiers 𝐶1 , 𝐶2 , … , 𝐶𝑠 . We combine the accurate distancefrom its original table after anonymized. Considering thefor clustering: Euclidean distance. Hence, the distance ofdata in the 𝑘 -anonymity problem are always person -two records 𝑟1 , 𝑟2 ∈ 𝑇 is defined as:

specific records and the attribute type in the data are

a

set

of

recordsm

The objective of our algorithm is to modify a table which

𝑁1 , 𝑁2 , … , 𝑁𝑚

,

with
s

numeric

quasi-

ccategoricalquasi-△ ( 𝒓𝟏 , 𝒓𝟐 )=nothing more than three major types: numerical type (suchas age), categorical type (such as nationality, occupation).
To apple the clustering approach, it is n ecessary to define
the distance that measures the dissimilarities among data
points. In this paper we defined the distance function forthree major attribute irrespective of the background for
attributes. The key of our distance function is to consider
the numbers of each attribute to be generalized and the

𝒔
𝟐
𝟐
√∑𝒎
𝐢=𝟏(𝒓𝟏 [𝑵𝑵𝒊 ] − 𝒓𝟐 [𝑵𝑵𝒊 ]) + ∑𝐣=𝟏(𝒓𝟏 [𝑵𝑪𝒊 ] − 𝒓𝟐 [𝑵𝑪𝒊 ]) (5)DEIM Forum 2016 F8-3

Input: a set T of n records and the value k
Output: a set of clusters 𝑃 = {𝑃1 , 𝑃2 , … , 𝑃𝑝 }the distance between record 𝑟 and the centroid of the------------------The preprocessing stage----------1. if( | n | ≤ k )2.
return n;
3. end if;

are constructed, but some of records might remain. The

cluster [8]. After the preprocessing stage, a set of clusters

which adds each record into a cluster with respect to that𝑛the increment of the information loss is minimal. For those𝑘clusters with more than 𝑘 records, calculate the inner

4. Let 𝑃 = ⌊ ⌋;5. result = ∅;6. randomly select 𝑃 distinct records 𝑟1 , 𝑟2 , … , rp ;7. for i= 1 to 𝑃
8.
Let 𝑃𝑖 = {𝑟i } ;9.
T = T - {𝑟i };10. While (T ≠ ∅)11.
r =randomly picked record from T ;12.
Calculate the distance △ (r, 𝑃𝑖 ) ;13.
Add r to its closest 𝑃𝑖 ;14.
update centroid of 𝑃𝑖 ;15.
T = T - {r};16. End While----------------The postprocessing stage----------17. If there is 𝑃which the size is < 𝑘 then
18.
While (| 𝑃 | > 𝑘)19.
sort all clusters by the information
loss;
20.
find the cluster that information loss ismaximal21.
remove r which is farthest from
centroid ofthe cluster;
22. End while
23. Add the record into the cluster with respect towhichthe increment of the information loss is
minimal.
24. Else
25.
Return result;
26. End if
Fig. 1.

postprocessing stage is to adjust the remaining records,

cluster information loss. Then, sort all clusters by the
information loss. Remove the record from the cluster that
information loss is maximal. The records that are removed
from the cluster are those most distant from the centroid of
the cluster. Then add the record into a cluster with respect
to which the increment of the information loss is minimal.

5. Experimental results
The main purpose of the experiments was to investigate
the performance of our method in terms of Information Lossand Execution Time. To accurately evaluate our approach,
we also compared our implementation with another two
methods, greedy 𝑘 member clustering proposed by Byun
Ji-won [4] and one-pass 𝑘-means clustering proposed by
Jun-Lin Lin [8].

5.1. Experimental Setup
All of the experiments were performed on a on a desktop
PC with Intel Core2Duo 2.2 GHz CPU and 2GB of RAM
under

MS

Window

7

operatingsystem.

And

theimplementation was built and run in Java. For our
experiments, we used the Adult dataset from the UC Irvine
Machine Learning Repository, which is considered a defacto benchmark for evaluating the performance of 𝑘 anonymity

algorithms.

For𝑘 -anonymization,

weconsidered {age, work class, education, marital status,

Clustering based approachoccupation, race, gender, and native country} as the quasi identifier. Among these, age and education were treated as

4.2. Clustering based approach
Now we discuss our efficient generalized clustering

numeric attributes while the other six attributes werealgorithm based 𝑘-anonymization. This algorithm is based

treated as categorical attributes.

on the 𝑘 -means clustering, but it will produce some

5.2. Information time and Execution Timeclusters that do not satisfy the size condition. Therefore,

The two metric used to measure the data quality are

we proceed the partitions in two stages. We give the details

Information time and Execution Time. We experimentally
implemented the two clustering-based 𝑘 -anonymization𝑛of our algorithm. Let 𝑃 = ⌊ ⌋ , where 𝑛 is the number ofmethod, greedy 𝑘 member clustering proposed by Byunrecords and 𝑘 is the value for 𝑘 -anonymization. During

Ji-won [4] and one-pass 𝑘-means clustering proposed by

the preprocessing stage, the algorithm randomly picks 𝑃

Jun-Lin Lin [8].

𝑘records as the initial values to build 𝑃 clusters. Then, theFigure 2 shows the Execution Time of both three, addsalgorithms. We set 𝑘 from 50 to 500 and wrote down the𝑟 to this cluster and subsequently updates the centroid oftime respectively. According to Figure 2, our efficient

this cluster. The distance between a cluster and a record 𝑟

generalized clustering algorithm took much less time thanis devoted as the number of records in the clusters times

the two algorithms. Figure 3 recorded the Information Lossalgorithm finds the nearest cluster for each record

DEIM Forum 2016 F8-3

caused by partitioning a set of clustering. It showed that

Histogram of the number of cluseters
vs. Information loss

our algorithm caused less information loss than the twoclustering algorithm.
250

209

200

178
135

150
100

95
79
4353 3530
22 161424
21410
4 2 0 108 1 0 7 4 4 2

50
0

0 0.2 0.4 0.6 0.8 1

Fig. 2. Execution time by different 𝑘

3

5

7

9 11 13 15 17

k=5

Fig. 5. The histogram of the information loss when k=5

Histogram of the number of cluseters
vs. Information loss
100
Fig. 3. Information Loss by different 𝑘

80

5.3. Histogram of the number of cluseters vs.
Information loss

60

We also experimented on a dataset of 5000records
include the attributes of age, gender and region. We let
𝑘=5 and 𝑘=10 to implement our clustering based approach.
The final result was showed in the Fig4. Also we give the

86

36
35 31
33 37
26
25
23
20
17
14
14
13
11 8
11
11
20
7
3221001 7545
233000111200000
0
0 0.3 0.6 0.9 3 6 9 12 15 18 21 24 27 30 33
40

k=10

histogram of the number of Cluste rs VS. Information loss
when 𝑘=5 and 𝑘=10

Fig. 6. The histogram of the information loss when k=10

6. Conclusions
In this paper, we proposed an efficient generalized
clustering algorithm based 𝑘 -anonymization.We definedFig. 4. The final result by the dataset of 5000set

the distance function for the numerical type (such as age),
categorical type (such as nationality, occupation). We
proceeded our algorithm in two stages: preprocessing stage
and postprocessing stage. The preprocessing stage is topartitions

allrecords𝑛

into ⌊ ⌋𝑘clusters,

and

the

postprocessing stage is to adjust the remaining records inthe preprocessing stage, which adds each record into acluster with respect to that the increment of the information
loss is minimal. We experimentally compared our methodwith two other clustering-based 𝑘-anonymization method.
The experiment shows that our method outperforms theirDEIM Forum 2016 F8-3

method and also ensure the anonymization of data. Finally,[11] MacQueen, J.B.: Some methods for classification andmany variations of the 𝑘-anonymization model have been

analysis of multivariate observations, Berkeley, pp.

proposed to further protect the data from identification,

281–297 (1967)

e.g., l-diversity [12], t-closeness [7].We should extend ouralgorithm to these models.

[12] A. Machanavajjhala, J. Gehrke, D. Kifer, and M.

Venkitasubramaniam. l-diversity: Privacy beyond kanonymity.

References
privacy. Int. J. Uncertain. Fuzziness Knowl. -Based
Syst. 10(5), 557–570 (2002)
Sweeney.

protection

Achievingusing

k-anonymity

generalization

andprivacy

suppression.

International Journal on Uncertainty, Fuzziness andKnowledge-based Systems, 2002.
[3] P.

Samarati.

Protecting

respondent’s

privacyinmicrodata release. IEEE Transactions on Knowledge
and Data Engineering, 13, 2001.
[4] J.-W. Byun, A. Kamra, E. Bertino, and N. Li.: Efficientk-anonymizationusing

clustering

techniques.

In

International Conference on Database Systems for
Advanced Applications (DASFAA) (2007)[5] B. C. M. Fung, K. Wang, and P. S.: Top -down

specializationfor

information

andprivacypreservation. In ICDE ’05: Proceedings of the 21stInternational

Conference

on

Data

Engineering(ICDE’05) (2005)[6] V. Ciriani, S. D. C. di Vimercati, S. Foresti, and P.

Samarati. K-anonymity. Security in Decentralized
Data Management (to appear).
[7] N. Li and T. Li. t-closeness: Privacy beyond k-

anonymity and l-diversity. In International Conferenceon Data Engineering (ICDE) (2007)[8] Lin, J.L., Wei, M.C.: An efficient clustering method

for k-anonymization. In Proceedings of the 2008
International Workshop on Privacy and Anonymity inInformation Society (2008)[9] Shyam

BoriahSimilarity

Varun

Measures

Chandola
for

Vipin

Categorical

Kumar:
Data:

A

Comparative Evaluation. Conference: Proceedings of
the SIAM International Conference on Data Mining,
SDM 2008, April 24-26, 2008, Atlanta, Georgia, USA[10] G. Aggarwal, T. Feder, K. Kenthapadi, R. Motwani, R.

Panigrahy, D. Thomas, and A. Zhu. Anonymizing
tables. In International Conference on Database
Theory, pages 246–258, 2005.

Proceedings

of

the

22nd

IEEE

International Conference on Data Engineering (ICDE[1] Sweeney, L.: k-anonymity: a model for protecting[2] L.

In

2006), 2006.