Privacy-preserving k-means clustering over vertically partitioned data

ABSTRACT

Privacy and security concerns can prevent sharing of data, derailing data mining projects. Distributed knowledge discovery, if done correctly, can alleviate this problem. The key is to obtain valid results, while providing guarantees on the (non)disclosure of data. We present a method for k-means clustering when different sites contain different attributes for a common set of entities. Each site learns the cluster of each entity, but learns nothing about the attributes at other sites.

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: J. Benaloh. Dense probabilistic encryption. In Proceedings of the Workshop on Selected Areas of Cryptography, pages 120--128, Kingston, Ontario, May 1994.
• 4: Paul S. Bradley , Usama M. Fayyad, Refining Initial Points for K-Means Clustering, Proceedings of the Fifteenth International Conference on Machine Learning, p.91-99, July 24-27, 1998
• 5: A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the EM algorithm (with discussion). Journal of the Royal Statistical Society, B 39:1--38, 1977.
• 6: Inderjit S. Dhillon , Dharmendra S. Modha, A Data-Clustering Algorithm on Distributed Memory Multiprocessors, Revised Papers from Large-Scale Parallel Data Mining, Workshop on Large-Scale Parallel KDD Systems, SIGKDD, p.245-260, August 15, 1999
• 7: W. Du , M. Atallah, Privacy-Preserving Cooperative Statistical Analysis, Proceedings of the 17th Annual Computer Security Applications Conference, p.102, December 10-14, 2001
• 8: Wenliang Du , Mikhail J. Atallah, Secure multi-party computation problems and their applications: a review and open problems, Proceedings of the 2001 workshop on New security paradigms, September 10-13, 2001, Cloudcroft, New Mexico [doi>10.1145/508171.508174]
• 9: R. Duda and P. E. Hart. Pattern Classification and Scene. Analysis. John Wiley & Sons, 1973.
• 10: 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]
• 11: M. Feingold, M. Corzine, M. Wyden, and M. Nelson. Data-mining moratorium act of 2003. U.S. Senate Bill (proposed), Jan. 16 2003.
• 12: M. Franklin and M. Yung. Varieties of secure distributed computing. In Proc. Sequences II, Methods in Communications, Security and Computer Science, pages 392--417, Positano, Italy, June 1991.
• 13: Keinosuke Fukunaga, Introduction to statistical pattern recognition (2nd ed.), Academic Press Professional, Inc., San Diego, CA, 1990
• 14: O. Goldreich. Secure multi-party computation, Sept. 1998. (working draft).
• 15: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 16: M. Kantarcioglu and C. Clifton. Privacy-preserving distributed mining of association rules on horizontally partitioned data. In The ACM SIGMOD Workshop on Research Issues on Data Mining and Knowledge Discovery (DMKD'02), pages 24--31, Madison, Wisconsin, June 2 2002.
• 17: M. Kantarcioĝlu and C. Clifton. Privacy-preserving distributed mining of association rules on horizontally partitioned data. IEEE-TKDE, submitted.
• 18: Murat Kantarcioglu , Jaideep Vaidya, An architecture for privacy-preserving mining of client information, Proceedings of the IEEE international conference on Privacy, security and data mining, p.37-42, December 01, 2002, Maebashi City, Japan
• 19: Hillol Kargupta , Weiyun Huang , Krishnamoorthy Sivakumar , Erik Johnson, Distributed clustering using collective principal component analysis, Knowledge and Information Systems, v.3 n.4, p.422-448, November 2001 [doi>10.1007/PL00011677]
• 20: Edwin M. Knorr , Raymond T. Ng , Ruben H. Zamar, Robust space transformations for distance-based operations, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.126-135, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502532]
• 21: Xiaodong Lin , Chris Clifton , Michael Zhu, Privacy-preserving clustering with distributed EM mixture modeling, Knowledge and Information Systems, v.8 n.1, p.68-81, July 2005 [doi>10.1007/s10115-004-0148-7]
• 22: 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
• 23: G. J. McLachlan and T. Krishnan. The EM Algorithm and Extensions. John Wiley & Sons, 1997.
• 24: David Naccache , Jacques Stern, A new public key cryptosystem based on higher residues, Proceedings of the 5th ACM conference on Computer and communications security, p.59-66, November 02-05, 1998, San Francisco, California, United States [doi>10.1145/288090.288106]
• 25: T. Okamoto and S. Uchiyama. A new public-key cryptosystem as secure as factoring. In Advances in Cryptology - Eurocrypt '98, LNCS 1403, pages 308--318. Springer-Verlag, 1998.
• 26: P. Paillier. Public key cryptosystems based on composite degree residuosity classes. In Advances in Cryptology - Eurocrypt '99 Proceedings, LNCS 1592, pages 223--238. Springer-Verlag, 1999.
• 27: S. J. Rizvi and J. R. Haritsa. Maintaining data privacy in association rule mining. In Proceedings of 28th International Conference on Very Large Data Bases, pages 682--693, Hong Kong, Aug. 20--23 2002. VLDB.
• 28: 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]
• 29: A. C. Yao. How to generate and exchange secrets. In Proc. of the 27th IEEE Symposium on Foundations of Computer Science, pages 162--167. IEEE, 1986.

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.4 Systems
          Subjects: Distributed databases
      H.2.7 Database Administration
          Subjects: Security, integrity, and protection

General Terms:
Security

Keywords:
privacy