Masking and Re-identification Methods for Public-Use Microdata: Overview and Research Problems <s> Discussion of Information Loss Metrics <s> A fruitful direction for future data mining research will be the development of techniques that incorporate privacy concerns. Specifically, we address the following question. Since the primary task in data mining is the development of models about aggregated data, can we develop accurate models without access to precise information in individual data records? We consider the concrete case of building a decision-tree classifier from training data in which the values of individual records have been perturbed. The resulting data records look very different from the original records and the distribution of data values is also very different from the original distribution. While it is not possible to accurately estimate original values in individual data records, we propose a novel reconstruction procedure to accurately estimate the distribution of original data values. By using these reconstructed distributions, we are able to build classifiers whose accuracy is comparable to the accuracy of classifiers built with the original data. <s> BIB001 </s> Masking and Re-identification Methods for Public-Use Microdata: Overview and Research Problems <s> Discussion of Information Loss Metrics <s> Often a data holder, such as a hospital or bank, needs to share person-specific records in such a way that the identities of the individuals who are the subjects of the data cannot be determined. One way to achieve this is to have the released records adhere to k- anonymity, which means each released record has at least (k-1) other records in the release whose values are indistinct over those fields that appear in external data. So, k- anonymity provides privacy protection by guaranteeing that each released record will relate to at least k individuals even if the records are directly linked to external information. This paper provides a formal presentation of combining generalization and suppression to achieve k-anonymity. Generalization involves replacing (or recoding) a value with a less specific but semantically consistent value. Suppression involves not releasing a value at all. The Preferred Minimal Generalization Algorithm (MinGen), which is a theoretical algorithm presented herein, combines these techniques to provide k-anonymity protection with minimal distortion. The real-world algorithms Datafly and µ-Argus are compared to MinGen. Both Datafly and µ-Argus use heuristics to make approximations, and so, they do not always yield optimal results. It is shown that Datafly can over distort data and µ-Argus can additionally fail to provide adequate protection. <s> BIB002 </s> Masking and Re-identification Methods for Public-Use Microdata: Overview and Research Problems <s> Discussion of Information Loss Metrics <s> In this paper we show how a simple model that captures user uncertainty can be used to define suitable measures of disclosure risk and data utility. The model generalizes previous results of Duncan and Lambert. We present several examples to illustrate how the new measures can be used to implement existing optimality criteria for the choice of the best form of data release. <s> BIB003
The best situation for the producer of public-use microdata is when there is one set of users of the microdata with explicitly stated analytic needs. The key point is that, if there is a set of clearly defined users, the data provider can use ad hoc procedures that are specific to a small set of required types of analyses. Generally, individuals have desired more objective information loss metrics that allow comparison of results across several types of analyses or types of files. Before describing some of the attempts at objective information-loss metrics, we describe the situation with clearly user-defined needs. Kim and Winkler  needed to produce masked data that preserved analyses in a clearly defined set of subdomains determined by age, race, sex, and one other variable. In their situations, they, as producers of the data, were able to iteratively negotiate the potential analytic uses. Because some of the initial domains were too small, they were able to get users to agree to some collapsing of ages into age ranges and some of the subdomains determined race-age-sex categories. Based on the consultation with users, they initially created subdomains that had a sufficient number of records. They then applied additive noise with various levels of noise to determine the analytic degradations due to increased noise and determined a noise-level at the userspecified level of accuracy. Finally, they applied a swapping strategy for the most easily re-identified records. The swapping strategy was designed to preserve regression properties in the user-specified subdomains. After completion of the masking procedures, they provided information about analytic degradations in some subdomains that were not considered as important as the main set of subdomains and described specifics of the testing to determine that disclosure was avoided. Willenborg and De Waal  have suggested using entropy with discrete data. The possible intuition is that the masked data may have decreased entropy and be less useful. We observe, however, if X = (x 1 , …., x n ) is discrete data, then a collapsing strategy may produce masked data Y = (y 1 , …, y m ) where the sum of the counts in the y-cells exceeds a lower bound (say 3) and where the sum of the counts agrees the sum of the counts of the x-cells. Each of the y-variables is obtained by aggregating xvariables. Although entropy clearly decreases, it is not clear how a loglinear analysis might be affected. In the best situation, the collapsing may account for the sufficient statistics in original x-variables and the y-variables allow reproduction of an analysis. Domingo-Ferrer and Torra  have observed additional difficulties with the use of entropy. In other situations, a loglinear analysis that is possible on the x-variables is impossible on the y-variables. In other words, entropy is unlikely to provide useful information about possible degradations in analyses. Iyengar  provides an example of a collapsing strategy that allows a classification problem to be (approximately and accurately) reproduced. Sweeney  , BIB002 provides additional details on collapsing methods and strategies for producing k-anonymity. A file is k-anonymous if the identifiers agree exactly with the identifiers in at least k-1 other records. Willenborg and De Waal  have suggested using as an information loss metric a statistic that they refer to as the variance inflation statistic  are intended to cover both information loss and disclosure risk for a file containing one variable. Trotini and Fienberg BIB003 have shown how to extend their ideas to a few two-dimensional situations with multivariate normal data. Agrawal and Aggarwal  provide a measure of information loss that may be suitable for further research. Let ) ( x f X be the density estimated from the masked data be the density from the original data X. Agrawal and Aggarwal  estimate ) ( x f X in the one-dimensional privacy-preserving situation of Agrawal and Srikant BIB001 in which a simple type additive noise used for masking. In more general situations, the densities could be associated with multivariate data that has been masked via other methods. Then the information loss in the masked data is given by than to do a direct comparison, say, of two regression analyses using the masked and original data. This concern applies to all of the information-loss situations involving synthetic data (given below). Gomatam and Karr  provide a review and empirical comparison of six information-loss metrics for discrete data from the statistical and other literature. In the following f and g are two discrete distributions where the first might be associated with the unmasked data X and the second with the masked data Y. They use Hellinger distance whose definition is They use the discrete analog of the distance metric of Agarawal and Aggarwal  that they refer to as total variation. They use change in entropy that has been used by Willenborg and De Waal  and Domingo-Ferrer and Mateo-Sanz  . They use In the empirical work, Gomatam and Karr  apply the information loss metrics to data in which swapping has been performed (Dalenius and Reiss  ). Willenborg and De Waal  define a data swap of 2k elements in terms of k elementary swaps. In an elementary swap we first make a random selection of two records i and j from and then interchange of the values of the variables being swapped for these two records. The swap proportion or rate is defined as 2k/N where N is the number of records. Gomatam and Karr observe that each of the metrics generally increases with the increase in the swap rate and that they are quite correlated. Within the multiple-imputation framework of Raghunathan et al.  , Little and Liu  ,  have also considered an information loss metric for univariate statistics. Before giving the statistic, we need to define some terms. We are interested in the scalar parameter φ . For any completed data set likely to be bounded, the information loss γ goes to zero as the number of replicates D increases. The metric γ is appealing. If the analysis is based on a highly accurate model M, then the model M provides estimates of scalars for which information loss can go to zero. As MI is a general framework, it would be useful to extend the information loss to multivariate situations and provide a number of examples. Because of the difficulties in creating detailed models M, Little and Liu  and Reiter  only develop partial models that are applied to a subset of the variables in a data file. Alternatively, Kennickell  creates a MI model for data and iteratively blanks and fills values of variables to create a file of synthetic data. The iterative cycling between blanking data and filling in data stops when the data are believed to have converged or sufficient cycles have taken place. The ideas of Kennickell have been adapted and extended by Abowd and Woodcock  . The research questions for information loss are particularly difficult? Is it possible to create models that represent data in a form that allows or account for several analyses? With different models, is it possible to have metrics for information loss that relate to several analyses? How does a statistical agency create public-use files that preserve analytic properties and provide statistical justifications of the limitations of the public-use data?