Optimal randomization for privacy preserving data mining

ABSTRACT

Randomization is an economical and efficient approach for privacy preserving data mining (PPDM). In order to guarantee the performance of data mining and the protection of individual privacy, optimal randomization schemes need to be employed. This paper demonstrates the construction of optimal randomization schemes for privacy preserving density estimation. We propose a general framework for randomization using mixture models. The impact of randomization on data mining is quantified by performance degradation and mutual information loss, while privacy and privacy loss are quantified by interval-based metrics. Two different types of problems are defined to identify optimal randomization for PPDM. Illustrative examples and simulation results are reported.

REFERENCES

• 1: Dakshi Agrawal , Charu C. Aggarwal, On the design and quantification of privacy preserving data mining algorithms, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.247-255, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375602]
• 2: Rakesh Agrawal , Ramakrishnan Srikant, Privacy-preserving data mining, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.439-450, May 15-18, 2000, Dallas, Texas, United States
• 3: D. Bohning. A review of reliable maximum likelihood algorithms for semiparametric mixture models. J. Statist. Plann. Inference, 47:5--28, 1995.
• 4: The Economist. The end of Privacy. May, 1999.
• 5: Alexandre Evfimievski , Johannes Gehrke , Ramakrishnan Srikant, Limiting privacy breaches in privacy preserving data mining, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.211-222, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773174]
• 6: Alexandre Evfimievski , Ramakrishnan Srikant , Rakesh Agrawal , Johannes Gehrke, Privacy preserving mining of association rules, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775080]
• 7: J. Fan. Global behavior of deconvolution kernel estimates. Statistica Sinica, 1:541--551, 1991.
• 8: J. Fan. On the optimal rates of convergence for nonparametric deconvolution problem. Annals of Statistics, pages 1257--1272, 1991.
• 9: Hillol Kargupta , Souptik Datta , Qi Wang , Krishnamoorthy Sivakumar, On the Privacy Preserving Properties of Random Data Perturbation Techniques, Proceedings of the Third IEEE International Conference on Data Mining, p.99, November 19-22, 2003
• 10: Yehuda Lindell , Benny Pinkas, Privacy Preserving Data Mining, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.36-54, August 20-24, 2000
• 11: B.G. Lindsay. Mixture Models: Theory, Geometry and Applications, NSF-CBMS Regional Conference Series in Probability and Statistics, Vol. 5. Alexandria, Virginia: Institute of Mathematical Statistics and the American Statistical Association, 1995.
• 12: R. A. Redner and H. F. Walker. Mixture densities, maximum likelihood and the EM algorithm. SIAM Review, 26(2):195--239, 1984.
• 13: K. Thearling. Data mining and privacy: a conflict in making. DS, November 1998.
• 14: Jaideep Vaidya , Chris Clifton, Privacy preserving association rule mining in vertically partitioned data, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775142]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.0 General
          Subjects: Security, integrity, and protection**

General Terms:
Algorithms, Security, Theory

Keywords:
individual privacy, mixture model, randomization operator