Privacy-Preserving Data Mining.
Data mining is under attack from privacy advocates because of a misunderstanding about what it actually is and a valid concern about how it's generally done. This article shows how technology from the security community can change data mining for the better, providing all its benefits while still maintaining privacy.
Introduction
Explosive progress in networking, storage, and processor
technologies has led to the creation of ultra large
databases that record unprecedented amount of transactional
information. In tandem with this dramatic
increase in digital data, concerns about informational
privacy have emerged globally [Tim97] [Eco99] [eu998]
[Off98]. Privacy issues are further exacerbated now that
the World Wide Web makes it easy for the new data
to be automatically collected and added to databases
The concerns over massive collection of data are naturally
extending to analytic tools applied to data. Data
mining, with its promise to efficiently discover valuable,
non-obvious information from large databases, is particularly
vulnerable to misuse [CM96] [The98] [Off98]
[ECB99].
A fruitful direction for future research in data mining
will be the development of techniques that incorporate
privacy concerns [Agr99]. 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?
The underlying assumption is that a person will be
willing to selectively divulge information in exchange of
value such models can provide [Wes99]. Example of the
value provided include filtering to weed out unwanted
information, better search results with less effort, and
automatic triggers [HS99]. A recent survey of web users
classified 17% of respondents as privacy fundamentalists
who will not provide data to a web site
even if privacy protection measures are in place. How-
ever, the concerns of 56% of respondents constituting
the pragmatic majority were significantly reduced by
the presence of privacy protection measures. The remaining
27% were marginally concerned and generally
willing to provide data to web sites, although they often
expressed a mild general concern about privacy. Another
recent survey of web users [Wes99] found that 86%
of respondents believe that participation in information-
for-benefits programs is a matter of individual privacy
choice. A resounding 82% said that having a privacy
policy would matter; only 14% said that was not important
as long as they got benefit. Furthermore, people
are not equally protective of every field in their data
records [Wes99] [CRA99a]. Specifically, a person
ffl may not divulge at all the values of certain fields;
ffl may not mind giving true values of certain fields;
ffl may be willing to give not true values but modified
values of certain fields.
Given a population that satisfies the above assump-
tions, we address the concrete problem of building
decision-tree classifiers [BFOS84] [Qui93] and show that
that it is possible to develop accurate models while respecting
users' privacy concerns. Classification is one
the most used tasks in data mining. Decision-tree classifiers
are relatively fast, yield comprehensible models,
and obtain similar and sometimes better accuracy than
other classification methods [MST94].
Related Work There has been extensive research in
the area of statistical databases motivated by the desire
to be able to provide statistical information (sum,
count, average, maximum, minimum, pth percentile,
etc.) without compromising sensitive information about
individuals (see excellent surveys in [AW89] [Sho82].)
The proposed techniques can be broadly classified into
query restriction and data perturbation. The query restriction
family includes restricting the size of query
result (e.g. [Fel72] [DDS79]), controlling the overlap
amongst successive queries (e.g. [DJL79]), keeping audit
trail of all answered queries and constantly checking
for possible compromise (e.g. [CO82]), suppression
of data cells of small size (e.g. [Cox80]), and clustering
entities into mutually exclusive atomic populations
(e.g. [YC77]). The perturbation family includes swapping
values between records (e.g. [Den82]), replacing the
original database by a sample from the same distribution
(e.g. [LST83] [LCL85] [Rei84]), adding noise to the
values in the database (e.g. [TYW84] [War65]), adding
noise to the results of a query (e.g. [Bec80]), and sampling
the result of a query (e.g. [Den80]). There are negative
results showing that the proposed techniques cannot
satisfy the conflicting objectives of providing high
quality statistics and at the same time prevent exact
or partial disclosure of individual information [AW89].
The statistical quality is measured in terms of bias, pre-
cision, and consistency. Bias represents the difference
between the unperturbed statistics and the expected
value of its perturbed estimate. Precision refers to the
variance of the estimators obtained by the users. Consistency
represents the lack of contradictions and para-
doxes. An exact disclosure occurs if by issuing one or
more queries, a user is able to determine the exact value
of a confidential attribute of an individual. A partial
disclosure occurs if a user is able to obtain an estimator
whose variance is below a given threshold.
While we share with the statistical database literature
the goal of preventing disclosure of confidential
information, obtaining high quality point estimates is
not our goal. As we will see, it is sufficient for us to
be able to reconstruct with sufficient accuracy the original
distributions of the values of the confidential at-
tributes. We adopt from the statistics literature two
methods that a person may use in our system to modify
the value of a field [CS76]:
ffl Value-Class Membership. Partition the values into
a set of disjoint, mutually-exhaustive classes and
return the class into which the true value x i falls.
ffl Value Distortion. Return a value x
of x i where r is a random value drawn from some
distribution.
We discuss further these methods and the level of
privacy they provide in the next section.
We do not use value dissociation, the third method
proposed in [CS76]. In this method, a value returned for
a field of a record is a true value, but from the same field
in some other record. Interestingly, a recent proposal
[ECB99] to construct perturbed training sets is based
on this method. Our hesitation with this approach is
that it is a global method and requires knowledge of
values in other records.
The problem of reconstructing original distribution
from a given distribution can be viewed in the general
framework of inverse problems [EHN96]. In [FJS97],
it was shown that for smooth enough distributions
(e.g. slowly varying time signals), it is possible to to
fully recover original distribution from non-overlapping,
contiguous partial sums. Such partial sums of true
values are not available to us. We cannot make a
priori assumptions about the original distribution; we
only know the distribution used in randomizing values
of an attribute. There is rich query optimization
literature on estimating attribute distributions from
partial information [BDF + 97]. In the OLAP literature,
there is work on approximating queries on sub-cubes
from higher-level aggregations (e.g. [BS97]). However,
these works did not have to cope with information that
has been intentionally distorted.
Closely related, but orthogonal to our work, is the
extensive literature on access control and security (e.g.
sensitive
information is exchanged, it must be transmitted over a
secure channel and stored securely. For the purposes of
this paper, we assume that appropriate access controls
and security procedures are in place and effective in
preventing unauthorized access to the system. Other
relevant work includes efforts to create tools and
standards that provide platform for implementing a
system such as ours (e.g. [Wor] [Ben99] [GWB97]
Paper Organization We discuss privacy-preserving
methods in Section 2. We also introduce a quantitative
measure to evaluate the amount of privacy offered
by a method and evaluate the proposed methods
against this measure. In Section 3, we present our re-construction
procedure for reconstructing the original
data distribution given a perturbed distribution. We
also present some empirical evidence of the efficacy of
the reconstruction procedure. Section 4 describes techniques
for building decision-tree classifiers from perturbed
training data using our reconstruction proce-
dure. We present an experimental evaluation of the
accuracy of these techniques in Section 5. We conclude
with a summary and directions for future work in Section
6.
We only consider numeric attributes; in Section 6, we
briefly describe how we propose to extend this work to
include categorical attributes. We focus on attributes
for which the users are willing to provide perturbed
values. If there is an attribute for which users are
not willing to provide even the perturbed value, we
simply ignore the attribute. If only some users do
not provide the value, the training data is treated
as containing records with missing values for which
effective techniques exist in the literature [BFOS84]
[Qui93].
Privacy-Preserving Methods
Our basic approach to preserving privacy is to let
users provide a modified value for sensitive attributes.
The modified value may be generated using custom
code, a browser plug-in, or extensions to products such
as Microsoft's Passport (http://www.passport.com) or
Novell's DigitalMe (http://www.digitalme.com). We
consider two methods for modifying values [CS76]:
Value-Class Membership In this method, the values
for an attribute are partitioned into a set of disjoint,
mutually-exclusive classes. We consider the special case
of discretization in which values for an attribute are
discretized into intervals. All intervals need not be of
equal width. For example, salary may be discretized
into 10K intervals for lower values and 50K intervals
for higher values. Instead of a true attribute value, the
user provides the interval in which the value lies. Discretization
is the method used most often for hiding
individual values.
Value Distortion Return a value x
of x i where r is a random value drawn from some
distribution. We consider two random distributions:
ffl Uniform: The random variable has a uniform
distribution, between [\Gammaff; ff]. The mean of the
random variable is 0.
ffl Gaussian: The random variable has a normal
distribution, with mean
deviation oe [Fis63].
We fix the perturbation of an entity. Thus, it is not
possible for snoopers to improve the estimates of the
value of a field in a record by repeating queries [AW89].
2.1 Quantifying Privacy
For quantifying privacy provided by a method, we use
a measure based on how closely the original values of
a modified attribute can be estimated. If it can be
Confidence
50% 95% 99.9%
Discretization 0:5 \Theta W 0:95 \Theta W 0:999 \Theta W
Uniform 0:5 \Theta 2ff 0:95 \Theta 2ff 0:999 \Theta 2ff
Gaussian 1:34 \Theta oe 3:92 \Theta oe 6:8 \Theta oe

Table

1: Privacy Metrics
estimated with c% confidence that a value x lies in
the interval [x 1 then the interval width
defines the amount of privacy at c% confidence level.

Table

1 shows the privacy offered by the different
methods using this metric. We have assumed that the
intervals are of equal width W in Discretization.
Clearly, for Discretization
provide the same amount of privacy. As ff increases,
privacy also increases. To keep up with Uniform,
Discretization will have to increase the interval width,
and hence reduce the number of intervals. Note that
we are interested in very high privacy. (We use 25%,
50%, 100% and 200% of range of values of an attribute
in our experiments.) Hence Discretization will lead
to poor model accuracy compared to Uniform since
all the values in a interval are modified to the same
value. Gaussian provides significantly more privacy
at higher confidence levels compared to the other
two methods. We, therefore, focus on the two value
distortion methods in the rest of the paper.
3 Reconstructing The Original
Distribution
For the concept of using value distortion to protect
privacy to be useful, we need to be able to reconstruct
the original data distribution from the randomized data.
Note that we reconstruct distributions, not values in
individual records.
We view the n original data values x of a
one-dimensional distribution as realizations of n independent
identically distributed (iid) random variables
each with the same distribution as the
random variable X. To hide these data values, n independent
random variables Y 1
used, each with the same distribution as a different random
variable Y . Given x 1
y i is the realization of Y i ) and the cumulative distribution
function FY for Y , we would like to estimate the
cumulative distribution function FX for X.
Reconstruction Problem Given a cumulative distribution
FY and the realizations of n iid random samples
estimate FX .
Let the value of
that we do not have the individual values x i and y i ,
only their sum. We can use Bayes' rule [Fis63] to
estimate the posterior distribution function F 0
(given
that assuming we know the density
functions fX and fY for X and Y respectively.
X1 (a)
Z a
Z a
(using Bayes' rule for density functions)
Z a
(expanding the denominator)
R a
(inner integral is independent of outer)
R a
independent of
R a
To estimate the posterior distribution function F 0
we average the
distribution functions for each of the X i .
R a
The corresponding posterior density function, f 0
X is
obtained by differentiating F 0
(1)
Given a sufficiently large number of samples, we expect
X in the above equation to be very close to the
real density function f X . However, although we know
we do not know fX . Hence we use the uniform
distribution as the initial estimate f 0
X , and iteratively
refine this estimate by applying Equation 1. This
algorithm is sketched out in Figure 1.
Using Partitioning to Speed Computation Assume
a partitioning of the domain (of the data values)
into intervals. We make two approximations:
1 For example, if Y is the standard normal, f Y
(2-))e \Gammaz 2 =2 .
repeat
until (stopping criterion met)

Figure

1: Reconstruction Algorithm
ffl We approximate the distance between z and w i (or
between a and w i ) with the distance between the
mid-points of the intervals in which they lie, and
ffl We approximate the density function f X (a) with the
average of the density function over the interval in
which a lies.
Let I(x) denote the interval in which x lies, m(I p )
the mid-point of interval I p , and m(x) the mid-point
of interval I(x). Let fX (I p ) be the average
value of the density function over the interval I p , i.e.
R
R
Ip dz. By applying these two
approximations to Equation 1, we get
Let I denote the k intervals, and L p the
width of interval I p . We can replace the integral in the
denominator with a sum, since m(z) and f X (I(z)) do
not change within an interval:
(2)
We now compute the average value of the posterior
density function over the interval I p .
Z
Ip
Z
Ipn
(substituting Equation 2)
Z
Ipn
(since
R
Gaussian
(a) Plateau (b) Triangles2006001000
Number
of
Records
Attribute Value
Original
Randomized
Number
of
Records
Attribute Value
Original
Randomized
Reconstructed
Uniform
(c) Plateau (d) Triangles2006001000
Number
of
Records
Attribute Value
Original
Randomized
Number
of
Records
Attribute Value
Original
Randomized
Reconstructed

Figure

2: Reconstructing the Original Distribution
Let N (I p ) be the number of points that lie in interval I p
(i.e. number of elements in the set fw i jw g. Since
is the same for points that lie within the same
Finally, let Pr 0 (X 2 I p ) be the posterior probability of
X belonging to interval I p , i.e. Pr 0 (X 2 I p
Multiplying both sides of the above equation by
using Pr(X 2 I p
We can now substitute Equation 3 in step 3 of the
algorithm (Figure 1), and compute step 3 in O(m 2 )
time. 2
naive implementation of Equation 3 will lead to O(m 3 )
time. However, since the denominator is independent of Ip , we
can re-use the results of that computation to get O(m 2 ) time.
Stopping Criterion With omniscience, we would
stop when the reconstructed distribution was statistically
the same as the original distribution (using, say,
the - 2 goodness-of-fit test [Cra46]). An alternative is to
compare the observed randomized distribution with the
result of randomizing the current estimate of the original
distribution, and stop when these two distributions
are statistically the same. The intuition is that if these
two distributions are close to each other, we expect our
estimate of the original distribution to also be close to
the real distribution. Unfortunately, we found empirically
that the difference between the two randomized
distributions is not a reliable indicator of the difference
between the original and reconstructed distributions.
Instead, we compare successive estimates of the
original distribution, and stop when the difference
between successive estimates becomes very small (1%
of the threshold of the - 2 test in our implementation).
Empirical Evaluation Two original distributions,
"plateau" and "triangles", are shown by the "Original"
line in Figures 2(a) and (b) respectively. We add a
Gaussian random variable with mean 0 and standard
rid Age Salary Credit Risk
43 40K High
(a) Training
Salary < 50K
High
High Low
Age < 25
(b) Decision Tree

Figure

3: Credit Risk Example
deviation of 0.25 to each point in the distribution.
Thus a point with value, say, 0.25 has a 95% chance
of being mapped to a value between -0.26 and 0.74, and
a 99.9% chance of being mapped to a value between -
0.6 and 1.1. The effect of this randomization is shown
by the "Randomized" line. We apply the algorithm
(with partitioning) in Figure 1, with a partition width
of 0.05. The results are shown by the "Reconstructed"
line. Notice that we are able to pick out the original
shape of the distribution even though the randomized
version looks nothing like the original.

Figures

2(c) and (d) show that adding an uniform,
discrete random variable between 0.5 and -0.5 to each
point gives similar results.
4 Decision-Tree Classification over
Randomized Data
4.1 Background
We begin with a brief review of decision tree classifi-
cation, adapted from [MAR96] [SAM96]. A decision
tree [BFOS84] [Qui93] is a class discriminator that recursively
partitions the training set until each partition
consists entirely or dominantly of examples from
the same class. Each non-leaf node of the tree contains
a split point which is a test on one or more attributes
and determines how the data is partitioned.

Figure

3(b) shows a sample decision-tree classifier based
on the training shown in Figure 3a. (Age ! 25) and
(Salary ! 50K) are two split points that partition the
records into High and Low credit risk classes. The decision
tree can be used to screen future applicants by
classifying them into the High or Low risk categories.
A decision tree classifier is developed in two phases:
a growth phase and a prune phase. In the growth
Partition(Data S)
begin
(1) if (most points in S are of the same class) then
(2) return;
(3) for each attribute A do
evaluate splits on attribute A;
Use best split to partition S into S 1 and
Initial call: Partition(TrainingData)

Figure

4: The tree-growth phase
phase, the tree is built by recursively partitioning the
data until each partition contains members belonging
to the same class. Once the tree has been fully grown,
it is pruned in the second phase to generalize the
tree by removing dependence on statistical noise or
variation that may be particular only to the training
data.

Figure

4 shows the algorithm for the growth
phase.
While growing the tree, the goal at each node is
to determine the split point that "best" divides the
training records belonging to that node. We use the gini
index [BFOS84] to determine the goodness of a split.
For a data set S containing examples from m classes,
is the relative frequency of
class j in S. If a split divides S into two subsets S 1 and
the index of the divided data gini split (S) is given
by gini split
calculating this index requires only the distribution of
the class values in each of the partitions.
4.2 Training Using Randomized Data
To induce decision trees using perturbed training data,
we need to modify two key operations in the tree-growth
phase (

Figure

ffl Determining a split point (step 4).
ffl Partitioning the data (step 5).
We also need to resolve choices with respect to reconstructing
original distribution:
ffl Should we do a global reconstruction using the whole
data or should we first partition the data by class
and reconstruct separately for each class?
ffl Should we do reconstruction once at the root node
or do reconstruction at every node?
We discuss below each of these issues.
For pruning phase based on the Minimum Description
Length principle [MAR96], no modification is needed.
Determining split points Since we partition the domain
into intervals while reconstructing the distribu-
tion, the candidate split points are the interval bound-
aries. (In the standard algorithm, every mid-point between
any two consecutive attribute values is a candidate
split point.) For each candidate split-point, we
use the statistics from the reconstructed distribution to
compute gini index.
Partitioning the Data The reconstruction procedure
gives us an estimate of the number of points in each
interval. Let I 1 be the m intervals, and N (I p ) be
the estimated number of points in interval I p . We associate
each data value with an interval by sorting the
values, and assigning the N lowest values to interval
I 1 , and so on. 3 If the split occurs at the boundary
of interval I p\Gamma1 and I p , then the points associated with
go to S 1 , and the points associated
with intervals I go to S 2 . We retain this
association between points and intervals in case there is
a split on the same attribute (at a different split-point)
lower in the tree.
Reconstructing the Original Distribution We
consider three different algorithms that differ in when
and how distributions are reconstructed:
ffl Global: Reconstruct the distribution for each
attribute once at the beginning using the complete
perturbed training data. Induce decision tree using
the reconstructed data.
ffl ByClass: For each attribute, first split the training
data by class, then reconstruct the distributions
separately for each class. Induce decision tree using
the reconstructed data.
ffl Local: As in ByClass, for each attribute, split the
training data by class and reconstruct distributions
separately for each class. However, instead of doing
reconstruction only once, reconstruction is done at
each node (i.e. just before step 4 in Figure 4). To
avoid over-fitting, reconstruction is stopped after the
number of records belonging to a node become small.
A final detail regarding reconstruction concerns the
number of intervals into which the domain of an
attribute is partitioned. We use a heuristic to determine
the number of intervals, m. We choose m such that
there are an average of 100 points per interval. We
then bound m to be between 10 and 100 intervals i.e.
is set to 10, etc.
Clearly, Local is the most expensive algorithm in
terms of execution time. Global is the cheapest
3 The interval associated with a data value should not be
considered an estimator of the original value of that data value.
algorithm. ByClass falls in between. However, it
is closer to Global than Local since reconstruction is
done in ByClass only at the root node, whereas it
is repeated at each node in Local. We empirically
evaluate the classification accuracy characteristics of
these algorithms in the next section.
4.3 Deployment
In many applications, the goal of building a classification
model is to develop an understanding of different
classes in the target population. The techniques
just described directly apply to such applications. In
other applications, a classification model is used for predicting
the class of a new object without a preassigned
class label. For this prediction to be accurate, although
we have been able to build an accurate model using
randomized data, the application needs access to non-
perturbed data which the user is not willing to disclose.
The solution to this dilemma is to structure the application
such that the classification model is shipped to the
user and applied there. For instance, if the classification
model is being used to filter information relevant to
a user, the classifier may be first applied on the client
side over the original data and the information to be
presented is filtered using the results of classification.
5 Experimental Results
5.1 Methodology
We compare the classification accuracy of Global,
ByClass, and Local algorithms against each other and
with respect to the following benchmarks:
ffl Original, the result of inducing the classifier on
unperturbed training data without randomization.
ffl Randomized, the result of inducing the classifier
on perturbed data but without making any corrections
for randomization.
Clearly, we want to come as close to Original in accuracy
as possible. The accuracy gain over Randomized reflects
the advantage of reconstruction.
We used the synthetic data generator from [AGI
for our experiments. We used a training set of
100,000 records and a test set of 5,000 records, equally
split between the two classes. Table 2 describes
the nine attributes, and Table 3 summarizes the
five classification functions. These functions vary
from having quite simple decision surface (Function
1) to complex non-linear surfaces (Functions 4 and
5). Functions 2 and 3 may look easy, but are quite
difficult. The distribution of values on age are identical
for both classes, unless the classifier first splits on salary.
Further, the classifier has to exactly find five split-points
on salary: 25, 50, 75, 100 and 125 to perfectly classify
the data. The width of each of these intervals is less
Group A Group B
Function
Function
Function
((elevel
Function 4 (0:67 \Theta (salary
Function 5 (0:67 \Theta (salary
hvalue \Theta max(hyears \Gamma 20;

Table

3: Description of Functions
Attribute Description
salary uniformly distributed from 20K to 150K
commission salary - 75K
uniformly distributed from 10K to 75K
age uniformly distributed from 20 to 80
elevel uniformly chosen from 0 to 4
car uniformly chosen from 1 to 20
zipcode uniformly chosen from 9 zipcodes
hvalue uniformly distributed from k \Theta 50K
to k \Theta 150K, where k 2 f0
depends on zipcode
hyears uniformly distributed from 1 to
loan uniformly distributed from 0 to 500K

Table

2: Attribute Descriptions
than 20% of the range of the attribute. Function 2
also contains embedded XORs which are known to be
troublesome for decision tree classifiers.
Perturbed training data is generated using both
Uniform and Gaussian methods (Section 2). All
accuracy results involving randomization were averaged
runs. We experimented with large values for the
amount of desired privacy: ranging from 25% to 200%
of the range of values of an attribute. The confidence
threshold for the privacy level is taken to be 95% in
all our experiments. Recall that if it can be estimated
with 95% confidence that a value x lies in the interval
then the interval width
the amount of privacy at 95% confidence level. For
example, at 50% privacy, Salary cannot be estimated
(with 95% confidence) any closer than an interval of
width 65K, which is half the entire range for Salary.
Similarly, at 100% privacy, Age cannot be estimated
(with 95% confidence) any closer than an interval of
width 60, which is the entire range for Age.
5.2 Comparing the Classification
Algorithms

Figure

5 shows the accuracy of the algorithms for
Uniform and Gaussian perturbations, for privacy levels
of 25% and 100%. The x-axis shows the five functions
from

Table

3, and the y-axis the accuracy.
Overall, the ByClass and Local algorithms do remarkably
well at 25% and 50% privacy, with accuracy
numbers very close to those on the original data. Even
at as high as 100% privacy, the algorithms are within
5% (absolute) of the original accuracy for Functions 1, 4
and 5 and within 15% for Functions 2 and 3. The advantage
of reconstruction can be seen from these graphs by
comparing the accuracy of these algorithms with Randomized

Overall, the Global algorithm performs worse than
ByClass and Local algorithms. The deficiency of
Global is that it uses the same merged distribution
for all the classes during reconstruction of the original
distribution. It fares well on Functions 4 and 5, but
the performance of even Randomized is quite close to
Original on these functions. These functions have a
diagonal decision surface, with equal number of points
on each side of the diagonal surface. Hence addition
of noise does not significantly affect the ability of
the classifier to approximate this surface by hyper-rectangles

As we stated in the beginning of this section, though
they might look easy, Functions 2 and 3 are quite
difficult. The classifier has to find five split-points on
salary and the width of each interval is 25K. Observe
that the range over which the randomizing function
spreads 95% of the values is more than 5 times the width
of the splits at 100% privacy. Hence even small errors
in reconstruction result in the split points being a little
off, and accuracy drops.
The poor accuracy of Original for Function 2 at 25%
privacy may appear anomalous. The explanation lies in
Privacy
Gaussian Uniform8090100
Accuracy
Original
ByClass
Global
Accuracy
Original
ByClass
Global
Randomized
Privacy
Gaussian Uniform6080100
Accuracy
Original
ByClass
Global
Accuracy
Original
ByClass
Global
Randomized

Figure

5: Classification Accuracy
there being a buried XOR in Function 2. When Original
reaches the corresponding node, it stops because it does
not find any split point that increases gini. However,
due to the perturbation of data with randomization, the
other algorithms find a "false" split point and proceed
further to find the real split.
5.3 Varying Privacy

Figure

6 shows the effect of varying the amount of
privacy for the ByClass algorithm. (We omitted the
graph for Function 4 since the results were almost
identical to those for Function 5.) Similar results were
obtained for the Local algorithm. The x-axis shows the
privacy level, ranging from 10% to 200%, and the y-axis
the accuracy of the algorithms. The legend ByClass(G)
refers to ByClass with Gaussian, Random(U) refers to
Randomized with Uniform, etc.
Two important conclusions can be drawn from these
graphs:
ffl Although Uniform perturbation of original data
results in a much large degradation of accuracy
before correction compared to Gaussian, the effect
of both distributions is quite comparable after
correction.
ffl The accuracy of the classifier developed using
perturbed data, although not identical, comes fairly
close to Original (i.e. accuracy obtained from using
unperturbed data).
6 Conclusions and Future Work
In this paper, we studied the technical feasibility of
realizing privacy-preserving data mining. The basic
premise was that the sensitive values in a user's record
will be perturbed using a randomizing function so
that they cannot be estimated with sufficient precision.
Randomization can be done using Gaussian or Uniform
perturbations. The question we addressed was whether,
given a large number of users who do this perturbation,
Function 1 Function 26080100
Accuracy
Privacy Level (%)
Original
Accuracy
Privacy Level (%)
Original
Function 3 Function 56080100
Accuracy
Privacy Level (%)
Original
Accuracy
Privacy Level (%)
Original

Figure

Change in Accuracy with Privacy
can we still construct sufficiently accurate predictive
models.
For the specific case of decision-tree classification,
we found two effective algorithms, ByClass and Local.
The algorithms rely on a Bayesian procedure for
correcting perturbed distributions. We emphasize that
we reconstruct distributions, not individual records,
thus preserving privacy of individual records. As a
matter of fact, if the user perturbs a sensitive value
once and always return the same perturbed value,
the estimate of the true value cannot be improved by
successive queries. We found in our empirical evaluation
ffl ByClass and Local are both effective in correcting
for the effects of perturbation. At 25% and 50%
privacy levels, the accuracy numbers are close to
those on the original data. Even at 100% privacy,
the algorithms were within 5% to 15% (absolute) of
the original accuracy. Recall that if privacy were
to be measured with 95% confidence, 100% privacy
means that the true value cannot be estimated any
closer than an interval of width which is the entire
range for the corresponding attribute. We believe
that a small drop in accuracy is a desirable trade-off
for privacy in many situations.
ffl Local performed marginally better than ByClass,
but required considerably more computation. Investigation
of what characteristics might make Local a
winner over ByClass (if at all) is an open problem.
ffl For the same privacy level, Uniform perturbation
did significantly worse than Gaussian before correcting
for randomization, but only slightly worse after
correcting for randomization. Hence the choice between
applying the Uniform or Gaussian distributions
to preserve privacy should be based on other
considerations: Gaussian provides more privacy at
higher confidence thresholds, but Uniform may be
easier to explain to users.
Future Work We plan to investigate the effectiveness
of randomization with reconstruction for categorical at-
tributes. The basic idea is to randomize each categorical
value as follows: retain the value with probability p, and
choose one of the other values at random with probability
may then derive an equation similar
to Equation 1, and iteratively reconstruct the original
distribution of values. Alternately, we may be able to
extend the analytical approach presented in [War65] for
boolean attributes to derive an equation that directly
gives estimates of the original distribution.

Acknowledgments

A hallway conversation with
Robert Morris provided initial impetus for this work.
Peter Haas diligently checked the soundness of the
reconstruction procedure.



--R

Privacy critics: UI components to safeguard users' privacy.
Tomasz Imielin- ski
Data Mining: Crossing the Chasm.


A security mechanism for statistical databases.
Truste: an online privacy seal program.

Quasi cubes: Exploiting approximations in multidimensional databases.
Security and privacy implications of data mining.
Auditing and infrence control in statistical databases.
Suppression methodology and statistical disclosure control.
Mathematical Methods of Statistics.
Beyond concern: Understanding net users' attitudes about online privacy.
Cranor, editor. Special Issue on Internet Privacy.
Selective partial access to a database.
The tracker: A threat to statistical database security.
Secure statistical databases with random sample queries.
Cryptography and Data Security.
Computers and Security.
Secure databases: Protection against user influence.
Data swapping: Balancing privacy against precision in mining for logic rules.
The Economist.
Regularization of Inverse Problems.
The European Union's Directive on Privacy Protection
On the question of statistical confidentiality.
Probability Theory and Mathematical Statistics.
Recovering information from summary data.

Privacy in the marketplace.
Net Worth.
A data distortion by probability distribu- tion
Privacy interfaces for information management.
Method and system for client/server communications with user information revealed as a function of willingness to reveal and whether the information is required.
An analytic approach to statistical databases.
Jorma Ris- sanen
Machine Learning
Office of the Information and Privacy Com- missioner
Internet security: Firewalls and beyond.

Practical data-swapping: The first steps
A survey of the world wide web security.
SPRINT: A scalable parallel classifier for data mining.
Statistical databases: Characteris- tics
Design of LDV: A multilevel secure relational database management system.
Data mining and privacy: A conflict in making.

The statistical security of a statistical database.
Randomized response: A survey technique for eliminating evasive answer bias.

Privacy concerns
Freebies and privacy: What net users think.
The World Wide Web Consortium.
A study on the protection of statistical databases.
--TR

--CTR
Xun Yi , Yanchun Zhang, Privacy-preserving distributed association rule mining via semi-trusted mixer, Data & Knowledge Engineering, v.63 n.2, p.550-567, November, 2007
privacy;data mining