The Open University of Israel Department of Mathematics and Computer Science Practical Approximation Algorithms for Optimal k-Anonymity Thesis submitted as partial fulfillment of the requirements towards an M.Sc. degree in Computer Science The Open University of Israel Department of Mathematics and Computer Science By Batya Kenig Prepared under the supervision of Dr. Tamir Tassa June 2009 I I wish to express my gratitude to Dr. Tamir Tassa for his devoted counsel, guidance and patience. A special thanks to my husband Tal - for his love and encouragement. I Contents 1 Introduction 1 1.1 Overview of the thesis . . . . . . . . . . . . . . . . . . . . . . 3 2 k−Anonymization 4 2.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Generalization . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2.1 Generalization types . . . . . . . . . . . . . . . . . . . 5 2.3 The k-anonymization problem . . . . . . . . . . . . . . . . . . 7 3 Measures of Information Loss 9 3.1 Basic measures . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.2 Entropy based measures . . . . . . . . . . . . . . . . . . . . . 11 3.3 Monotonicity of cost measures. . . . . . . . . . . . . . . . . . 13 4 Approximation Algorithms for k-Anonymization 14 4.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.2 k-anonymization using set cover . . . . . . . . . . . . . . . . . 16 4.2.1 k-anonymity using frequent itemsets . . . . . . . . . . 20 4.3 k−anonymization via the forest algorithm . . . . . . . . . . . 22 4.3.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . 22 4.3.2 Phase 1: Creating the initial forest . . . . . . . . . . . 24 4.3.3 Phase 2: Decomposing large trees. . . . . . . . . . . . 25 5 Heuristic Algorithms for k−Anonymization 28 6 Frequent Itemset Mining Algorithms 31 6.1 The frequent itemset mining problem . . . . . . . . . . . . . . 31 6.2 The FP-growth algorithm . . . . . . . . . . . . . . . . . . . . 33 6.2.1 FP-tree construction . . . . . . . . . . . . . . . . . . . 33 6.2.2 FP-Growth, mining FIs from the FP-tree . . . . . . . 34 II CONTENTS III 6.3 Mining closed frequent itemsets . . . . . . . . . . . . . . . . . 37 6.3.1 Theoretic foundations for mining CFIs from FP-trees 38 6.3.2 The Charm algorithm . . . . . . . . . . . . . . . . . . 43 7 Generalized Frequent Itemset Mining Algorithms 50 7.1 Problem definition . . . . . . . . . . . . . . . . . . . . . . . . 50 7.2 The basic algorithm . . . . . . . . . . . . . . . . . . . . . . . 51 7.3 The Cumulate algorithm . . . . . . . . . . . . . . . . . . . . . 51 7.4 Proposed generalized itemset mining algorithm . . . . . . . . 53 7.4.1 The setting . . . . . . . . . . . . . . . . . . . . . . . . 53 7.4.2 Overview of the algorithm . . . . . . . . . . . . . . . . 55 7.4.3 Data structures used for counting itemset support . . 57 7.4.4 The algorithm . . . . . . . . . . . . . . . . . . . . . . 58 7.4.5 Implementation notes . . . . . . . . . . . . . . . . . . 61 8 An Improved Approximation Algorithm for k-Anonymity 64 9 Experiments 69 9.1 Adult dataset experiments . . . . . . . . . . . . . . . . . . . . 70 9.2 Nursery dataset experiments . . . . . . . . . . . . . . . . . . 75 9.3 Coil2000 dataset experiments . . . . . . . . . . . . . . . . . . 77 9.4 Scalability of the proposed mining algorithm . . . . . . . . . 79 10 Conclusion 81 III Abstract k-Anonymity is a privacy preserving method for limiting disclosure of pri- vate information in data mining. In a k-anonymized table, every record is indistinguishablefromatleastk−1otherrecords, whenceanadversarywho attemptstoextractpersonalinformationonanindividualwhoisrepresented in the released table cannot link that individual to less than k records in the table. The process of anonymizing a database table involves generaliz- ing table entries and, consequently, loss of relevant information for the data miner. This motivates the search for anonymization algorithms that achieve the required level of anonymization while incurring a minimal loss of infor- mation. The problem of k-anonymity with minimal loss of information is NP-hard. In this study wepresent severalknownapproximation and heuris- tic algorithms for the k-anonymization problem. Our main contribution is a practical algorithm that enables solving the k-anonymization problem with an approximation guarantee of O(lnk). This algorithm improves an algo- rithm due to Aggarwal et al. [1] that offers an approximation guarantee of O(k), and generalizes that of Park and Shim [15] that was limited to the case of generalization by suppression. Our algorithm uses techniques that we introduce herein for mining generalized frequent itemsets. Experi- ments show that the new algorithm provides better results than the leading approximation algorithm, as well as known heuristic algorithms. Chapter 1 Introduction Inrecentyears,therehasbeentremendousgrowthintheamountofpersonal data that can be collected and analyzed. Data mining tools are increasingly being used to infer trends and patterns. Of particular interest are data containing structured information on individuals. However, the use of data containingpersonalinformationhastoberestrictedinordertoprotectindi- vidual privacy. Although identifying attributes like ID numbers and names are never released for data mining purposes, sensitive information might still leak due to linking attacks that are based on the public attributes, a.k.a quasi-identifiers. Such attacks may join the quasi-identifiers of a published table with a publicly accessible table like the voters registry, and thus dis- close private information of specific individuals. In fact, it was shown in [20] that 87% of the U.S. population may be uniquely identified via the combination of the three quasi-identifiers: birthdate, gender and zipcode. Privacy-preserving data mining [2] has been proposed as a paradigm of ex- ercising data mining while protecting the privacy of individuals. One of the most well-studied methods of privacy preserving data mining is called k-anonymization, proposed by Samarati and Sweeney [17, 18, 21]. This method suggests to generalize the values of the public attributes, so that each of the released records becomes indistinguishable from at least k−1 other records, when projected on the subset of public attributes. The privatedataisthenassociatedtosetsofrecordsofsizeatleastk. Thevalues of the table are modified via the operation of generalization, while keeping them consistent with the original ones. A cost function is used to measure the amount of information lost by the generalization process. The objective is to modify the table entries so that the table becomes k−anonymized and theinformationloss(orcostfunction)isminimized. MeyersonandWilliams 1 2 [13] introduced this problem and studied it under the assumption that the table entries may be either left unchanged or totally suppressed. In that setting, the cost function to be minimized is the total number of suppressed entriesinthe table. They showedthatthe problem is NP-hardbyshowinga reduction from the k-dimensional perfect matching problem. They devised two approximation algorithms; one that runs in time O(n2k) and achieves anapproximationratioofO(klnk); andanotherthathasafullypolynomial running time (namely, it depends polynomially on both n and k) and guar- antees an approximation ratio of O(klnn). Aggarwal et al. [1] extended the setting of suppressions-only to generalizations by hierarchical clustering trees, and devised an approximation algorithm with an approximation ratio of O(k). Gionis and Tassa [7] improved the first algorithm of [13] by offer- ing an approximation ratio of O(lnk), rather than O(klnk), and applying it to a wider class of generalization operators (the generalizations in that class are called “proper” and they include generalization by suppression as well as generalizations by hierarchical clustering trees), and a wider class of measures of loss of information. However, the runtime of their algorithm re- mains O(n2k). Finally, Park and Shim [15] devised, independently of [7], an improved and practical version of the algorithm in [7] that also provides an approximation ratio of O(lnk). However, it applies only to generalizations by suppression. Another approach to the problem is using heuristical algorithms. The algorithm of choice is called the agglomerative algorithm [6] and it outper- forms the approximation algorithm of [1] which is the currently best prac- tical algorithm with a proven approximation guarantee (for the setting of generalization, and not just suppressions). The main contribution of this thesis is a practical anonymization algo- rithm that guarantees an approximation ratio of O(lnk) and applies to all proper generalizations and to a wide class of measures of loss of informa- tion. Our algorithm is based on the algorithm of Park and Shim which was restricted to suppressions only. It is also based on techniques that we de- vise herein for mining generalized frequent itemsets. When comparing the proposed algorithm to the currently best known approximation algorithm (the algorithm of [1]) and to the currently best known heuristical algorithm (the Agglomerative algorithm of [6]) it outperforms both of them in terms of information loss. In terms of runtime, it is a practical algorithm, and in some cases it is even faster than the above mentioned algorithms. 2 1.1. OVERVIEW OF THE THESIS 3 1.1 Overview of the thesis In Chapter 2 we present the fundamentals of k-anonymization. Then, in Chapter 3 we provide an overview of the common measures of information loss. In Chapter 4 we present k-anonymization algorithms that have a known approximationguarantee. Thefirstone(Section4.2)istheO(lnk)-approximation algorithm of [7]. Then we review the closely-related approximation algo- rithm of [15] that offers the same approximation ratio of O(lnk), but has better runtime performance, although it is restricted to generalization by suppression (Section 4.2.1). Finally, we discuss in Section 4.3 the O(k)- approximation algorithm of [1] which is the best practical and general ap- proximation algorithm for the problem of k-anonymity with minimal loss of information. In Chapter 5 we turn our attention from approximation algorithms with a known approximation guarantee to heuristic algorithms. We focus on the agglomerative algorithms of [6]. Asthemaincontributionofthisthesisborrowsideasfromalgorithmsfor mining generalized frequent itemsets, we proceed to discuss algorithms for mining frequent itemsets. In Chapter 6 we give an overview of the known frequent itemset mining algorithms in the standard setting (where all items in the itemset are single-valued, as opposed to generalized values). Then, in Chapter 7, we present the problem of mining generalized frequent itemsets and introduce our novel frequent generalized itemset mining algorithm. In Chapter 8 we present our practical O(lnk)-approximation algorithm for the problem of k-anonymization with minimal loss of information. That algorithm is based on the algorithms that were presented in Section 4.2 and onthealgorithmformininggeneralizedfrequentitemsetsthatwaspresented in Chapter 7. Finally, in Chapter 9 we compare the performance of our proposed algo- rithm to the performance of the best available approximation and heuristic algorithms. The comparison of the best known approximation algorithm (the algorithm that we devise in Chapter 8) to the best known heuristic (Chapter 5) reveals the following conclusion: The approximation algorithm is preferable not only from a theoretical point of view (as it provides an approximation guarantee) but also from a practical point of view, as it out- performs the heuristic algorithm in terms of the corresponding information loss. The thesis is concluded in Chapter 10. 3 Chapter 2 k−Anonymization Hereweprovidethebasicdefinitionsandlemmasrelatedtothek-anonymization problem. These will be used in subsequent chapters of this study. 2.1 Preliminaries A database table holds information on individuals in some population U = {u ,...,u }. Each individual is described by a set of r public attributes 1 n (a.k.a quasi-identifiers), A ,...,A , and s private attributes, Z ,...,Z . 1 r 1 s Each of the attributes consists of several possible values: A = {a : 1 ≤ l ≤ m }, 1 ≤ j ≤ r, j j,l j and Z = {z : 1 ≤ l ≤ n }, 1 ≤ j ≤ s. j j,l j We use the same notation, namely A or Z , to denote both the attribute j j name and the domain in which it takes values. For example, if A is gender, j then A = {M,F}, while if it is the age of the individual, it is a bounded j non-negative natural number. The public table holds all publicly available information on the individuals in U; it takes the form D = {R ,...,R }, (2.1) 1 n where R ∈ A ×···×A , 1 ≤ i ≤ n. The corresponding private table holds i 1 r the private information D(cid:48) = {S ,...,S }, (2.2) 1 n 4 2.2. GENERALIZATION 5 whereS ∈ Z ×···×Z , 1 ≤ i ≤ n. Thecompletetableistheconcatenation i 1 s of those two tables, D||D(cid:48) = {R ||S ,...R ||S }. We refer to the records 1 1 n n of R and S , 1 ≤ i ≤ n, as public and private records, respectively. Each i i cell in the table will be referred to as a table entry. The jth component of the record R (the (i,j)th entry in the table D) will be denoted by R (j). i i It should be noted that the sets in (2.1) and (2.2) may be multisets, that is they may include repeated records. 2.2 Generalization Generalization is the act of replacing the values that appear in the table with subsets of values, so that an entry R (j) ∈ A , 1 ≤ i ≤ n, 1 ≤ j ≤ r, is i j replaced by a subset of A that includes the value of this entry. j Definition 2.2.1. Let A , 1 ≤ j ≤ r, be finite sets and let A ⊆ P(A ) be j j j a collection of subsets of A . A mapping g : A ×···×A → A ×···× j 1 r 1 A is called a generalization if for every (b ,··· ,b ) ∈ A ×···×A and r 1 r 1 r g(b ,··· ,b ) = (B ,···B ), it holds that b ∈ B , 1 ≤ j ≤ r. 1 r 1 r j j 2.2.1 Generalization types In Definition 2.2.1, each attribute A , 1 ≤ j ≤ r, is assigned a collection of j subsets A ⊆ P(A ). According to the choice of A we get different types of j j j generalizations. Let us consider three examples: • Generalization by suppression. This refers to a mapping g that ei- ther leaves entries unchanged or replaces them by the entire set of attribute values. That is, A = A ∪{A } for all 1 ≤ j ≤ r. Namely, j j j g(b ,...,b ) = (b ,...,b ) where b ∈ {b ,A }, 1 ≤ j ≤ r. 1 r 1 r j j j • Generalization by hierarchical clustering trees. In [1], Aggarwal et al. considered a setting in which for every attribute A there is a corre- j spondingbalancedtree, T(A ), thatdescribesahierarchicalclustering j of A . Each node of T(A ) represents a subset of A , the root of the j j j tree is the entire set A , the descendants of each node represent a par- j titionof the subset that corresponds to the father node, and the leaves are all singleton subsets. Given such a balanced tree, the generaliza- tion operators may replace an entry R (j) with any of its ancestors in i T(A ). Generalizationbysuppressionisaspecialcaseofgeneralization j by clustering trees where all trees are of height 2. 5