The post randomisation method for protecting microdata

Q¨ UESTII ´ O,vol. 22, 1, p. 145-156, 1998 THE POST RANDOMISATION METHOD FOR PROTECTING MICRODATA JOS´ E GOUWELEEUW PETER KOOIMAN LEON WILLENBORG PETER-PAUL DE WOLF Statistics Netherlands This paper describes the Post RandomisationMethod (PRAM) as a method for disclosure protection of microdata. Applying PRAM means that for each record in the data file according to a specified probability mechanism the score on a number of variables is changed. Since this probability mechanismis known, the characteristicsof the latent true data can unbiasedly be estimated from the observed data moments in the perturbed file. Hola PRAM is applied to categorical variables. It is shown that both crosstabulation and standard multivariate analysis techniques can easily be adapted to account for PRAM. It only requires pre-multiplication by the transpose of the inverted Markov transition matrix, specifying the randomisation process. Also, estimates for the additional variance introduced by PRAM are given. By a proper choice of the transition probabilities, PRAM can be applied in such a way that certain chosen marginal distributions in the original data file are left invariant in expectation. In that case the perturbed data can be used as if it were the original data. We describe how to obtain such an invariant PRAM process. Finally, some consequences of using PRAM in practice are discussed. The present paper is a shortened version of Kooiman et al. (1997). Keywords: Post RAndomisation Method (PRAM), disclosure, randomised response, Markov matrix, invariant matrix, perturbed data, data swapping. *Jos´e Gouweleeuw, Peter Kooiman, Leon Willenborg and Peter-Paul de Wolf. Statistics Netherlands. Division Research and Development. Department of Statistical Methods. The Netherlands. –Received July 1997. –Accepted October 1997. 145 1. INTRODUCTION This paper investigates a suggestion by S¨arndal et al.. (1992), pp. 572-3, to protect microdata files against disclosure by randomisation of individual record data, using the methodology of randomised response techniques due to Warner (1965). This methodology is employed when interviewers have to deal with highly sensitive questions, on which the respondent is not likely to report true values in a face-to-face interview setting. By embedding the question in a pure chance experiment the true value of the respondent is never revealed to the interviewer. By knowing the probabilities involved in the chance experiment, the analyst can nevertheless make inferences about the population frequencies of the characteristic investigated, be it with some loss in precision. The suggestion of S¨arndal et al. amounts to applying the same randomisation technique to reported individual scores, prior to their release as microdata files. Thus, true individual scores will not be revealed, whereas an analyst, by taking the (known) randomisation model into account, can still make valid inferences from the data set as a whole. The methodology advocated in this paper represents an alternative to data swapping as a technique for disclosure protection of microdata (see Dalenius and Reiss, 1982). In data swapping individual scores on certain variables are interchanged between records in such a way that second order moments are kept more or less intact (first order moments are unchanged automatically). In this paper we take another approach. We no longer require the perturbed file to mimic the original one. Instead we require that data moments of the original file can unbiasedly be estimated from the perturbed file. This is achieved as follows. For each record in the original microdata file, the score on one or more variables is replaced by an other score according to some probability mechanism. Because of this the moments of the data will change, the true data moments of the original file become latent. Since the probability mechanism that is used for perturbing the scores is completely known to the data protector, it can be shipped to the analyst jointly with the perturbed file. This allows the analyst to reconstruct the latent true data moments to the extent that these moments can unbiasedly be estimated from the observed data moments in the perturbed file. This method for disclosure protection of microdata will be called the Post Randomisation Method (PRAM). In order to make valid inferences from the perturbed file the analyst has to account for the fact that the true data patterns are hidden behind a veil of errors deliberately introduced to protect the individual records. Thus, he has to apply somewhat more complicated types of statistical analyses, which is a drawback of the method in comparison with other disclosure control techniques as for example recoding or suppression of values. However, in this paper we show that this drawback is minor when PRAM is applied to categorical variables. Most disclosure protection analysis 146 of microdata involves categorical variables. Due to the fact that the analyst knows the complete distribution of the errors, simple corrections that can be routinely applied using standard statistical software are sufficient. As compared to data swapping, the method has the important advantage that it is soundly statistical, not mechanical. This allows us to invoke the complete apparatus of statistical modelling and inference, both to make probability statements about disclosure risks at the individual record level and to calculate the loss in precision of aggregate statistics, due to PRAM. The remainder of this paper is organised as follows. In Section 2, PRAM is introduced by an example. In Section 3, the technique is worked out for the most elementary type of analysis: cross-tabulation of categorical variables. The probability mechanism used for PRAM can be chosen in such a way that the distribution of the variables in the perturbed file equals that in the original file, in which case the perturbed file can be used directly for analysis. Section 4 describes how to construct such a probability mechanism. In Section 5 the consequences of using PRAM in practice are discussed and finally Section 6 contains some conclusions and topics for further research. 2. DISCLOSURE PROTECTION BY RANDOMISATION Consider a f 0 ; 1 g? variable, e.g. gender with 0 = male, 1 = female. Scores are randomised, independently for each record, by using the following (known) probability matrix Px = f pkl g : Px = θ01 ? θ0 1 ? θ1θ1 ! ; where pkl represents the probability that the reported randomised score equals lgiven that the latent true score equals k. In the sequel we denote the true score with ξ, and the randomised score with x. Assume that a data file representing a simple random sample of nrecords is available. We want to estimate the true population fractions of both categories. From the original file this would be achieved by calculating Tξ = n, Tξbeing the total of ξin the data file. From the perturbed file we can similarly calculate Tx. The relation between both totals can be computed as: E ( Tx j ξ ) = Tξθ1 + ? n ? Tξ  ( 1 ? θ0 ) ; where E ( : j : ) denotes the conditional expectation. An unbiased estimator for Tξis directly obtained as ˆ Tξ = Tx ? n ( 1 ? θ0 ) θ1 + θ0 ? 1 : (2.1) 147 Clearly V ? ˆ Tξ j ξ  = V ( Tx j ξ ) ( θ1 + θ0 ? 1 ) 2 ; (2.2) where V ( : j : ) indicates the conditional variance. Note that we have to assume that θ1 6 = 1 ? θ0, since otherwise the denominator in (2.1) as well as (2.2) becomes 0. In practice, it is desirable that θ1is not too close to 1 ? θ0, since a value of θ1close to 1 ? θ0would lead to a large variance as can be seen from formula (2.2). Formula (2.2) can be rewritten as follows. Note that Tx j ξis distributed as the sum of two independent binomially distributed random variables with parameters ( Tξ ; θ1 ) and ( n ? Tξθ0 ) respectively. Consequently V ( Tx j ξ ) = Tξθ1 ( 1 ? θ1 ) + ( n ? Tξ ) θ0 ( 1 ? θ0 ) , so that V ? ˆ Tξ j ξ  = Tξθ1 ( 1 ? θ1 ) + ? n ? Tξ  θ0 ( 1 ? θ0 ) ( θ1 + θ0 ? 1 ) 2 ; which for θ0 = θ1 (= θ ) reduces to V ? ˆ Tξ j ξ  = nθ ( 1 ? θ ) ( 2θ ? 1 ) 2 : This demonstrates that under the assumptions stated the standard deviation does not depend on the true proportion Tξ = n. Consequently the coefficient of variation V ? ˆ tξ j ξ  1 = 2 = Tξis inversely proportional with Tξ. Thus, the distortion is relatively large when the true score Tξ(or n ? Tξ) is (very) low. This fits nicely into our general purpose to protect rare scores, since these are the most vulnerable to disclosure. We conclude this section with an example indicating the effect of PRAM on protecting the individual scores. Consider a microdata file of n records, representing a simple random sample of a population of size N. The data set contains exactly one surgeon, whose gender is given as female. PRAM has been applied to the gender variable, though. Independently for each record, the gender score has been kept intact with probability 0.9, and has been changed to the opposite score with probability 0.1. Other variables in the file are not perturbed. Suppose an intruder knows that the population contains 1 female surgeon and 99 male surgeons. He can derive that the (posterior) odds are 11:1 in favour of a perturbed male surgeon in the data file. When the population contains 9 male surgeons besides the one female surgeon, the odds are 1:1. So without additional information, the intruder can not conclude that he has identified the female surgeon. 148 3. CROSS-TABULATION We now turn to the problem of deriving valid cross-tabulations from a perturbed data file with categorical variables. The example of Section 2, which refers to the simplest non-trivial tabulation possible, i.e. a ( 2  1 ) table, will be generalised step by step. First consider a categorical variable ξ, with categories ξ ( k ) ; k = 1 ;::: ; K. To protect a data file containing ξ, we perturb the scores ξ ( k ) . In particular, ξ ( k ) is transformed into a score x ( k ) = ξ ( l ) with probability pkl, for k ; l = 1 ;::: ; K. The matrix Px = f pkl g is a Markov matrix, i.e. Pxι = ι ; ιbeing a ( K  1 ) vector of ones. Since in practical situations we only want to change a small minority of the true values the diagonal elements of Pxdominate strongly (these will in general be in the range of 0 : 9 ? 1 : 0), so that Pxcertainly has full rank. Now let Tξbe the ( K  1 ) vector of frequencies of the Kcategories of ξ, observed in the original data file, and similarly, let Txbe the vector of frequencies in the perturbed file. It is easy to verify that E ( Tx j ξ ) = PT xTξ ; (3.1) where the superscript 0 T 0 indicates transposition. Thus Tξcan unbiasedly be estimated by ˆ Tξ = ? P ? 1 x  TTx : Note that the matrix Pxhas to be non-singular in order for ˆ Tξto be well defined. This implies that the matrix Pxcan not contain two equal rows, which means that each value of ξcorresponds uniquely with a distribution of the perturbed variable over the categories, as determined by the rows of Px. The conditional variance of ˆ Tξis given by V ? ˆ Tξ j ξ  = ? P ? 1 x  TV ( Tx j ξ ) P ? 1 x : Due to the recordwise independence of the multinomial transition process we obtain the covariance matrix of Txas V ( Tx j ξ ) = K ∑ k = 1 Tξ ( k ) Vk ; where, for k = 1 ; : : : ; K,Vkis the ( K  K ) covariance matrix of the outcomes x ( l ) , l = 1 ;::: ; K, of the multinomial transition process of an element with true score ξ ( k ) : Vk ( l ; j ) = ( Px ; kl ( 1 ? Px ; kl ) if l = j ? Px ; kl Px ; kj if l 6 = j ; for l ; j = 1 ;::: ; K : (3.2) Substituting the estimator ˆ tξfor the unknown true frequencies Tξwe obtain an estimator for the uncertainty introduced by the noise process: ˆ V ( Tx j ξ ) = K ∑ k = 1 ˆ Tξ ( k ) Vk : (3.3) 149 The derivations show that univariate frequencies can straightforwardly be corrected for the noise added to the file. It just requires pre-multiplication with the transpose of the inverted transition probability matrix. This matrix can be supplied with the (perturbed) data file so that analysis only requires a matrix multiplication as an extra step in the tabulation. Using the same information it is also possible to estimate covariances of the estimated true frequencies. This result generalises to multivariate distributions (see Kooiman et al., 1997). A problem related to cross-tabulation that is of practical importance is the following. Some users of statistical microdata sets want to match extra variables to the data set supplied. We give a simplified example. Suppose the data set supplied to a client contains the dichotomous variable car ownership C (0: does not possess a car; 1: does possess a car) and the highly detailed geographical classification indicating place of living G (say, 1000 localities). The client wants to analyse the relationship between car ownership and the presence of a railway station in the place of living. For each of the 1000 localities of the geographical classification the client knows whether there is a railway station or not. When the file is not perturbed it is easy to match this data to the file and add a third variable railway station R (0: has no direct access to railway facilities; 1: does have direct access to railway facilities). Then, the analysis could be done by studying the 2 ( 2 cross classification of the variables C and R. The variable G is only used as an intermediate variable; it does not play a role in the subsequent analysis. The question arises whether this process, which occurs frequently in practice, is still feasible when the microdata file supplied to the client has been perturbed. The answer is: yes, it is still possible, but not by matching the new variable to the (perturbed) microdata file itself. What can be done is the following. First estimate the ( 2  1000 ) table TCG. Then an unbiased estimate of the true table is ˆ TCR = ? P ? 1 C  T˜ TCG P ? 1 GTGR ; where ˆ TCG = ? P ? 1 C  t˜ TCG P ? 1 Gis the estimated C  Gtable. In fact the TGR table acts as an aggregator of the rows of TCG. The process of matching additional variables as indicated above, therefore amounts to the addition of specific aggregation keys for detailed classificatory variables present in the data set. A similar example is occupation, which could for instance be aggregated according to the distinction between white collar and blue collar work. So far we have demonstrated that tabular analysis of perturbed microdata sets consisting of categorical variables poses no fundamental problems. The frequency tables summarise all available information in the data set. Multivariate analysis for categorical data, like loglinear modelling or correspondence analysis, can therefore proceed from the estimates of the latent true tables. The presence of a small bit of extra va- 150 riance in these estimates will generally pose no problems to the analyst, as the extra variance just adds to the sampling variance that is present in the data anyhow. A somewhat more serious problem might be that for small frequencies in the original table the estimated frequencies can turn out to be negative. Indeed, when a true frequency is zero and its estimate is unbiased, positive and negative estimates are equally likely to occur. When the analyst is interested in the cross-tabulation per se, he might truncate estimated frequencies at zero: although a biased estimate results, the mean squared error of the cells involved decreases by the truncation. However, this procedure introduces an upward bias in the row and column totals associated with these cells. A final problem is that subdomain analysis can not proceed as usual, as subdomains can no longer be properly identified when the domain indicator involved has been affected by PRAM. The solution is simple, though. We add the domain indicator to the set of variables under analysis, and (re)construct the relevant tables, including the domain indicator as an extra variable in the tabulations. The table entries pertaining to the subdomain of interest give unbiased estimates of the original subdomain tabulations. 4. INVARIANT PRAM So far, it was seen that applying PRAM implies that the perturbed tables have to be pre-multiplied by ( P ? 1 x ) t. In this section, it will be demonstrated that the analysis of the perturbed data file can be simplified if Pxis chosen to be invariant with respect to the distribution of the variable that is to be perturbed. Here distribution can refer to the distribution in the data file (the sample) as well as the distribution in the population. The consequence of this choice of Pxwill be discussed in this section. First consider the case where the data file contains one categorical variable ξwith categories ξ ( k ) ,k = 1 ;::: ; K. As before, ξ ( k ) is transformed into a score x ( k ) = ξ ( l ) with probability pkl for k ; l = 1 ;::: ; K. The matrix Px = f pkl g now should be chosen in such a way that the distribution of ξover the different categories in the original data file is invariant with respect to Px, i.e. Pxshould satisfy . PT xTξ = Tξ : (4.1) The K  Kidentity matrix Ialways satisfies this equation, but this is not very interesting, since the perturbed data file will be the same as the unperturbed data file. In general, there will be at least one other solution Pxfor this set of equations (since there are K ( K ? 1 ) unknowns and Kequations). For example, Pxcan be chosen as follows. Assume without loss of generality that the categories are ordered in such a 151 way that Tξ ( k ) > Tξ ( K ) > 0 for k = 1 ;::: ; K pkl = 8 > > < > > : 1 ? ? 0 : 1Tξ ( K ) = Tξ ( k )  if l = k 0 : 1Tξ ( K ) = Tξ ( k ) if l = ( k + 1 ) modK 0 otherwise (4.2) Then a simple computation shows that this matrix Pxsatisfies PT xι = ιand PT xTξ = Tξ : There are other choices of Pxpossible. Now suppose that Pxis chosen such that (4.1) is satisfied. In that case E ( Tx j ξ ) = PT xTξ = Tξ : Here the first equality follows from formula (3.1) and the second equality follows from the choice of Px. This means that Tξcan unbiasedly be estimated by ˆ Tξ = Tx : Note that a transformation satisfying (4.1) is indeed invariant with respect to the (sample) distribution of ξ. However this invariance does not entail that the transformation is invariant with respect to crossings of ξwith other variables in the file. 5. APPLICATION OF PRAM Now that we have introduced PRAM, the question that remains to be considered is how to apply this technique in practice. This essentially means that a choice should be made for the Markov matrices to be applied. This involves several aspects that are discussed in separate subsections. 5.1. Markov Matrix Classes For practical purposes it is important to study a few special classes of Markov matrices that might be considered for use in PRAM. Below we study three types of such matrices. Other choices are also possible, however. What type of Markov matrix to choose for a variable or set of variables in a particular application of PRAM depends on such things as the initial distribution to be left invariant (if any) and requirements implied by the acceptability of certain combinations of values (only if combinations 152 of variables have to be considered in the light of integrity checks). In fact it takes some further study into the structure of these matrices so as to inform the practitioner who wants to make a motivated choice among the various possibilities. 5.1.1. Type I: two different non-zero values per row Suppose that the number of categories for a variable on which PRAM is applied, is K. A type I Markov matrix Pis one that has nonzero values on the main diagonal and for each row there is at least one other nonzero entry. Nonzero entries outside the main diagonal are all the same within a row (they may differ among rows) and they will in general not be equal to the entry on the diagonal in the same row. In fact if in row ithere are ki ? 1 nonzero off-diagonal elements, they are all equal to ( 1 ? pii ) = ( ki ? 1 ) , where pii is the i ? th diagonal element. Furthermore we require that Pis non-singular, so that the inverse of Pexists. Note that each row in Phas two unknowns, implying that, because the row entries should add to 1, there are K unknowns. Note that the matrix that is defined in formula (4.2) is a type Imatrix. In this case ki = 2 for all i. Special cases of Type I matrices are given in (5.1) below. In both cases kidoes not depend on i. In the first case ki = 2, and in the second case ki = K. 0 B B B B B B B B @ p1p10 ::: ::: 0 0p2p20 ::: 0 . . .............. . . . . .............0 0 : : : : : : 0pk ? 1pk ? 1 pk0 ::: ::: 0pk 1 C C C C C C C C A 0 B B B B B @ p1˜p1 ::: ::: ˜p1 ˜p2p2˜p2 ::: ˜p2 . . ........... . . ˜pk ? 1 ::: ˜pk ? 1pk ? 1˜pk ? 1 ˜pk ::: ::: ˜pkpk 1 C C C C C A (4.3) where pi = ( 1 ? pi ) , in the first matrix, and ˜pi = ( 1 ? pi ) = ( K ? 1 ) in the second matrix, for i = 1 ;::: ; K : 5.1.2. Type II: more than two different non-zero values per row In this case we assume well-defined functional relationships between diagonal elements and the nonzero off-diagonal elements in the same row as the respective diagonal element. In this light the Type I matrices are a subclass of the Type II matrices: each off-diagonal element is a linear function of the corresponding diagonal element, and besides these linear relationships are the same for the off-diagonal elements in the same row. This removes the tight constraint for the Type I Markov matrices namely that of the equality of the nonzero off-diagonal elements in the same row. 153