Privacy-preserving SVM using nonlinear kernels on horizontally partitioned data

ABSTRACT

Traditional Data Mining and Knowledge Discovery algorithms assume free access to data, either at a centralized location or in federated form. Increasingly, privacy and security concerns restrict this access, thus derailing data mining projects. What we need is distributed knowledge discovery that is sensitive to this problem. The key is to obtain valid results, while providing guarantees on the non-disclosure of data. Support vector machine classification is one of the most widely used classification methodologies in data mining and machine learning. It is based on solid theoretical foundations and has wide practical application. This paper proposes a privacy-preserving solution for support vector machine (SVM) classification, PP-SVM for short. Our solution constructs the global SVM classification model from the data distributed at multiple parties, without disclosing the data of each party to others. We assume that data is horizontally partitioned -- each party collects the same features of information for different data objects. We quantify the security and efficiency of the proposed method, and highlight future challenges.

REFERENCES

• 1: SPECT dataset. ftp://ftp/ics.uci.edu/pub/machine-learning-databases/spect/.
• 2: 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]
• 3: 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
• 4: Christopher J. C. Burges, A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery, v.2 n.2, p.121-167, June 1998 [doi>10.1023/A:1009715923555]
• 5: Nello Cristianini , John Shawe-Taylor, An introduction to support Vector Machines: and other kernel-based learning methods, Cambridge University Press, New York, NY, 1999
• 6: W. Du , M. Atallah, Privacy-Preserving Cooperative Statistical Analysis, Proceedings of the 17th Annual Computer Security Applications Conference, p.102, December 10-14, 2001
• 7: Wenliang Du , Zhijun Zhan, Building decision tree classifier on private data, Proceedings of the IEEE international conference on Privacy, security and data mining, p.1-8, December 01, 2002, Maebashi City, Japan
• 8: Directive 95/46/EC of the european parliament and of the council of 24 october 1995 on the protection of individuals with regard to the processing of personal data and on the free movement of such data. Official Journal of the European Communities, No I.(281):31--50, Oct. 24 1995.
• 9: 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]
• 10: Glenn Fung , Olvi L. Mangasarian, Proximal support vector machine classifiers, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.77-86, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502527]
• 11: X. Ge. C++ code: SMO training of SVM. http://www.datalab.uci.edu/people/xge/svm/, 2001.
• 12: B. Goethals, S. Laur, H. Lipmaa, and T. Mielikäinen. On Secure Scalar Product Computation for Privacy-Preserving Data Mining. In C. Park and S. Chee, editors, The 7th Annual International Conference in Information Security and Cryptology (ICISC 2004), volume 3506, pages 104--120, December 2--3, 2004.
• 13: Standard for privacy of individually identifiable health information. Federal Register, 66(40), Feb. 28 2001.
• 14: Ioannis Ioannidis , Ananth Grama , Mikhail Atallah, A Secure Protocol for Computing Dot-Products in Clustered and Distributed Environments, Proceedings of the 2002 International Conference on Parallel Processing (ICPP'02), p.379, August 18-21, 2002
• 15: X. Jiang and H. Yu. SVM-JAVA: A Java implementation of the SMO (sequential minimal optimization) for training SVM. Computer Science Department, University of Iowa, http://hwanjoyu.org/svm-java, 2005.
• 16: Murat Kantarcioglu , Chris Clifton, Privacy-Preserving Distributed Mining of Association Rules on Horizontally Partitioned Data, IEEE Transactions on Knowledge and Data Engineering, v.16 n.9, p.1026-1037, September 2004 [doi>10.1109/TKDE.2004.45]
• 17: 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
• 18: L. A. Kurgan, K. J. Cios, R. Tadeusiewicz, M. Ogiela, and L. S. Goodenday. Knowledge discovery approach to automated cardiac spect diagnosis. Artificial Intelligence in Medicine, 23:2:149--169, 2001.
• 19: 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]
• 20: 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
• 21: Y. Lindell and B. Pinkas. Privacy preserving data mining. Journal of Cryptology, 15(3):177--206, 2002.
• 22: Alfred J. Menezes , Scott A. Vanstone , Paul C. Van Oorschot, Handbook of Applied Cryptography, CRC Press, Inc., Boca Raton, FL, 1996
• 23: John C. Platt, Fast training of support vector machines using sequential minimal optimization, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 24: P. Ravikumar, W. W. Cohen, and S. E. Fienberg. A secure protocol for computing string distance metrics. In Proc. the Workshop on Privacy and Security Aspects of Data Mining at the Int. Conf. on Data Mining, 2004.
• 25: 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.
• 26: Jaideep Shrikant Vaidya , Chris Clifton, Privacy preserving data mining over vertically partitioned data, Purdue University, West Lafayette, IN, 2004
• 27: 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]
• 28: Jaideep Vaidya , Chris Clifton, Privacy-preserving k-means clustering over vertically partitioned data, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956776]
• 29: J. Vaidya and C. Clifton. Privacy preserving naïve bayes classifier for vertically partitioned data. In 2004 SIAM International Conference on Data Mining, pages 522--526, 2004.
• 30: J. Vaidya and C. Clifton. Secure set intersection cardinality with application to association rule mining. Journal of Computer Security, 2005.
• 31: J. Vaidya and C. Clifton. Secure set intersection cardinality with application to association rule mining. Journal of Computer Security, 13(4), Nov. 2005.
• 32: V. N. Vapnik. Statistical Learning Theory. John Wiley and Sons, 1998.
• 33: Rebecca Wright , Zhiqiang Yang, Privacy-preserving Bayesian network structure computation on distributed heterogeneous data, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014145]
• 34: Xifeng Yan , Jiawei Han, CloseGraph: mining closed frequent graph patterns, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956784]
• 35: H. Yu, K. C. Chang, and J. Han. Heterogeneous learner for Web page classification. In Int. Conf. Data Mining (ICDM'2), 2002.
• 36: H. Yu and J. Vaidya. Privacy-preserving linear SVM classification. Submitted for publication, 2005.
• 37: H. Yu, J. Vaidya, and X. Jiang. Privacy preserving svm classification on vertically partitioned data. Submitted for publication, 2005.

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:
Algorithms, Security

Keywords:
privacy-preserving data mining, support vector machine