Genetic algorithm-based clustering approach for k-anonymization

Abstract

k-Anonymity has been widely adopted as a model for protecting public released microdata from individual identification. This model requires that each record must be identical to at least $k-1$ other records in the anonymized dataset with respect to a set of privacy-related attributes. Although anonymizing the original dataset to satisfy the requirement of k-anonymity is easy, the anonymized dataset must preserve as much information as possible of the original dataset. Clustering techniques have recently been successfully adapted for k-anonymization. This work proposes a novel genetic algorithm-based clustering approach for k-anonymization. The proposed approach adopts various heuristics to select genes for crossover operations. Experimental results show that this approach can further reduce the information loss caused by traditional clustering-based k-anonymization techniques.

Introduction

Privacy protection is an important societal concern. Protection of public released microdata from individual identification becomes increasingly important as the public becomes increasingly concerned with privacy. Most privacy protection techniques work by randomizing (Agrawal and Srikant, 2000, Lin and Cheng, 2009) or generalizing Samarati, 2001 the original data, but can also degrade the quality of the data. Therefore, a dilemma exists between data quality and data privacy.

As a privacy-preserving approach, has been extensively studied in recent years, the k-anonymity model (Samarati, 2001, Sweeney, 2002) works by ensuring that each record of a table is identical to at least $k-1$ other records with respect to a set of privacy-related attributes, called quasi-identifiers, that could be used to identify individuals by linking these attributes to external datasets. For instance, consider the hospital data in Table 1, where the attributes ZipCode, Gender and Age are considered as quasi-identifiers. Table 2 shows a 3-anonymization version of Table 1, where anonymization is achieved via generalization at the attribute level (Ciriani, di Vimercati, Foresti, & Samarati, 2007), i.e., if two records contain the same value at a quasi-identifier before anonymization, then they are generalized to the same value at the quasi-identifier by the anonymization process. Table 3 shows another 3-anonymization version of Table 1, where anonymization is achieved via generalization at the cell-level (Ciriani et al., 2007), i.e., two cells with same value could be generalized to different values (e.g., value “75275” in the ZipCode column and value “Male” in the Gender column). Because anonymization via generalization at the cell-level generates data containing different generalization levels within a column (e.g., values “7527^∗” and “75275” in the ZipCode column and values “Male” and “Person” in the Gender column of Table 3), utilizing such data becomes more complex than utilizing the data generated via generalization at the attribute level. However, in terms of data quality, generalization at the cell-level causes less information loss than generalization at the attribute level, and therefore is adopted in this study.

Anonymization via generalization at the cell-level can proceed in two steps, partitioning and anonymizing. In the partitioning step, the dataset to be anonymized is partitioned into several groups such that each group contains at least k records. Then, in the anonymizing step, records in the same group are generalized such that their values at each quasi-identifier are identical. Minimizing the information loss incurred by the anonymizing step requires that the partitioning step places similar records (with respect to the quasi-identifiers) in the same group. In data mining, clustering is an effective means of partitioning records into clusters such that records within a cluster resemble each other, while records in different clusters are clearly distinct from each other. Hence, clustering techniques have been successfully adapted for k-anonymization (Byun et al., 2007, Chiu and Tsai, 2007, Lin and Wei, 2008, Lin et al., 2008, Loukides and Shao, 2007).

Genetic algorithms (GA) are well known for their global search capabilities. The constraint of k-anonymity means that traditional GA-based clustering techniques cannot be easily adapted for the k-anonymization problem without causing much overhead. Section 2.3 provides details. This work proposes a GA-based clustering approach for k-anonymization. This approach starts with a dataset that has been partitioned using a traditional clustering-based k-anonymization technique, called the Hybrid method (Lin et al., 2008). The output of the Hybrid method is encoded as a population of chromosomes. Various heuristics are then adopted to select genes to undergo the crossover operations to reduce the information loss of the dataset. This approach is, to our knowledge, the first GA-based clustering method proposed for k-anonymization at the cell-level. Experimental results demonstrate that the proposed approach further reduces the information loss caused by the Hybrid method.

The rest of this paper is organized as follows. Section 2 reviews basic concepts on k-anonymization with a focus on clustering-based methods for k-anonymization and GA-based clustering techniques. Section 3 describes the proposed GA-based approach for k-anonymization. Section 4 presents a performance analysis of the proposed approach. Conclusions are finally drawn in Section 5, along with recommendations for further research.