On the design and quantification of privacy preserving data mining algorithms

ABSTRACT

The increasing ability to track and collect large amounts of data with the use of current hardware technology has lead to an interest in the development of data mining algorithms which preserve user privacy. A recently proposed technique addresses the issue of privacy preservation by perturbing the data and reconstructing distributions at an aggregate level in order to perform the mining. This method is able to retain privacy while accessing the information implicit in the original attributes. The distribution reconstruction process naturally leads to some loss of information which is acceptable in many practical situations. This paper discusses an Expectation Maximization (EM) algorithm for distribution reconstruction which is more effective than the currently available method in terms of the level of information loss. Specifically, we prove that the EM algorithm converges to the maximum likelihood estimate of the original distribution based on the perturbed data. We show that when a large amount of data is available, the EM algorithm provides robust estimates of the original distribution. We propose metrics for quantification and measurement of privacy-preserving data mining algorithms. Thus, this paper provides the foundations for measurement of the effectiveness of privacy preserving data mining algorithms. Our privacy metrics illustrate some interesting results on the relative effectiveness of different perturbing distributions.

REFERENCES

• 1: 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
• 2: D. P. Bertsekas. Nonlinear Programming. Athena Scientific, Belmont, Massachusetts, 1995.
• 3: C. Clifton and D. Marks. Security and privacy implications of data mining. In ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, pages 15-19, May 1996.
• 4: H. Cramer. Mathematical Models of Statistics. Princeton University press, 1946.
• 5: Lorrie Faith Cranor, Internet privacy, Communications of the ACM, v.42 n.2, p.28-38, Feb. 1999 [doi>10.1145/293411.293440]
• 6: Vladimir Estivill-Castro , Ljiljana Brankovic, Data Swapping: Balancing Privacy against Precision in Mining for Logic Rules, Proceedings of the First International Conference on Data Warehousing and Knowledge Discovery, p.389-398, September 01, 1999
• 7: Tessa Lau , Oren Etzioni , Daniel S. Weld, Privacy interfaces for information management, Communications of the ACM, v.42 n.10, p.88-94, Oct. 1999 [doi>10.1145/317665.317680]
• 8: Chong K. Liew , Uinam J. Choi , Chung J. Liew, A data distortion by probability distribution, ACM Transactions on Database Systems (TODS), v.10 n.3, p.395-411, Sept. 1985 [doi>10.1145/3979.4017]
• 9: Claude E. Shannon , Warren Weaver, A Mathematical Theory of Communication, University of Illinois Press, Champaign, IL, 1963
• 10: The Economist. The end of privacy, May 1999.
• 11: The World Wide Web Consortium. The platform for privacy preference (P3P). Available from http://www.w3.org/P3P/P3FAQ.html.
• 12: K. Thearling. Data mining and privacy: A conflict in making. DS, Mar. 1998.
• 13: Time. The death of privacy, Aug. 1997.
• 14: Harry L. Van Trees, Detection, Estimation, and Modulation Theory: Radar-Sonar Signal Processing and Gaussian Signals in Noise, Krieger Publishing Co., Inc., Melbourne, FL, 1992
• 15: Paola Benassi, TRUSTe: an online privacy seal program, Communications of the ACM, v.42 n.2, p.56-59, Feb. 1999 [doi>10.1145/293411.293461]
• 16: J. Wu. On the convergence properties of the EM algorithm. Annals of Statistics, 11(1):95-103, 1983.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

General Terms:
Experimentation, Management, Theory