An integer programming approach for frequent itemset hiding

ABSTRACT

The rapid growth of transactional data brought, soon enough, into attention the need of its further exploitation. In this paper, we investigate the problem of securing sensitive knowledge from being exposed in patterns extracted during association rule mining. Instead of hiding the produced rules directly, we decide to hide the sensitive frequent itemsets that may lead to the production of these rules. As a first step, we introduce the notion of distance between two databases and a measure for quantifying it. By trying to minimize the distance between the original database and its sanitized version (that can safely be released), we propose a novel, exact algorithm for association rule hiding and evaluate it on real world datasets demonstrating its effectiveness towards solving the problem.

REFERENCES

• 1: ILOG CPLEX 9.0 User's Manual. ILOG Inc., Gentilly, France, 2003.
• 2: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 3: M. Atallah , A. Elmagarmid , M. Ibrahim , E. Bertino , V. Verykios, Disclosure Limitation of Sensitive Rules, Proceedings of the 1999 Workshop on Knowledge and Data Engineering Exchange, p.45, November 07-07, 1999
• 4: Roberto J. Bayardo, Jr., Efficiently mining long patterns from databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.85-93, June 01-04, 1998, Seattle, Washington, United States
• 5: C. Clifton, M. Kantarcioglu, and J. Vaidya. Defining privacy for data mining. WNGDM '02: National Science Foundation Workshop on Next Generation Data Mining, pages 126--133, 2002.
• 6: C. Clifton and D. Marks. Security and privacy implications of data mining. SIGMOD '96: Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, pages 15--20, 1996.
• 7: Csilla Farkas , Sushil Jajodia, The inference problem: a survey, ACM SIGKDD Explorations Newsletter, v.4 n.2, p.6-11, December 2002 [doi>10.1145/772862.772864]
• 8: Stephen E. Fienberg , Aleksandra B. Slavkovic, Preserving the Confidentiality of Categorical Statistical Data Bases When Releasing Information for Association Rules*, Data Mining and Knowledge Discovery, v.11 n.2, p.155-180, September 2005 [doi>10.1007/s10618-005-0010-x]
• 9: C. Gueret, C. Prins, and M. Sevaux. Applications of Optimization with Xpress-MP. Dash Optimization Ltd., 2002.
• 10: Ron Kohavi , Carla E. Brodley , Brian Frasca , Llew Mason , Zijian Zheng, KDD-Cup 2000 organizers' report: peeling the onion, ACM SIGKDD Explorations Newsletter, v.2 n.2, p.86-93, Dec. 2000 [doi>10.1145/380995.381033]
• 11: D. Luenberger. Introduction to Linear and Non-linear Programming. Addison-Wesley Publishing Company, 1973.
• 12: S. Menon, S. Sarkar, and S. Mukherjee. Maximizing accuracy of shared databases when concealing sensitive patterns. Information Systems Research, 16(3):256--270, 2005.
• 13: M. Morgenstern. Controlling logical inference in multilevel database and knowledge-base systems. IEEE '88: Proceedings of the 1988 IEEE Symposium on Security and Privacy, pages 245--255, 1988.
• 14: Stanley R. M. Oliveira , Osmar R. Zaïane, Privacy preserving frequent itemset mining, Proceedings of the IEEE international conference on Privacy, security and data mining, p.43-54, December 01, 2002, Maebashi City, Japan
• 15: Emmanuel D. Pontikakis , Yannis Theodoridis , Achilleas A. Tsitsonis , Liwu Chang , Vassilios S. Verykios, A quantitative and qualitative ANALYSIS of blocking in association rule hiding, Proceedings of the 2004 ACM workshop on Privacy in the electronic society, October 28-28, 2004, Washington DC, USA [doi>10.1145/1029179.1029187]
• 16: Stuart J. Russell , Peter Norvig, Artificial Intelligence: A Modern Approach, Pearson Education, 2003
• 17: Y. Saad. SPARSKIT: A basic toolkit for sparse matrix computations (version 2). Technical report, University of Minnesota, Minneapolis, MN, 1994. http://www-users.cs.umn.edu/~saad/software/SPARSKIT/sparskit.html.
• 18: Y. Saygin, V. Verykios, and C. Clifton. Using unknowns to prevent discovery of association rules. SIGMOD '01: Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data, pages 45--54, 2001.
• 19: Xingzhi Sun , Philip S. Yu, A Border-Based Approach for Hiding Sensitive Frequent Itemsets, Proceedings of the Fifth IEEE International Conference on Data Mining, p.426-433, November 27-30, 2005 [doi>10.1109/ICDM.2005.2]

INDEX TERMS

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

Additional Classification:
  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.1 Public Policy Issues
          Subjects: Privacy

General Terms:
Algorithms, Design

Keywords:
association rule mining, integer programming, optimization, rivacy preserving data mining, sensitive itemset hiding