Association rule hiding based on evolutionary multi-objective optimization

Abstract

When data mining techniques are applied to discover useful knowledge behind a large data collection, they are often required to preserve some confidential information, such as sensitive frequent itemsets, rules and so on. A feasible way to ensure the confidentiality is to sanitize the database and conceal sensitive information. However, the sanitization process often produces side effects, thus minimizing these side effects is an important task. An important but ignored fact is that a tradeoff exists within different side effects. When attempting to improve the performance on one dimension, the performance on other dimensions often will be degraded. In this paper, we focus on privacy preserving in association rule mining. Since there is a tradeoff within different side effects, we tried to minimize them from the view of multi-objective optimization. A rule hiding approach based on evolutionary multi-objective optimization (EMO) is proposed. It hides sensitive rules through removing identified items. The side effects on missing non-sensitive rules, ghost rules and data loss are formulated as optimization objectives. EMO is utilized to find a suitable subset of transactions for modification so that side effects can be minimized. Experimental results on real datasets illustrate that the proposed approach can achieve satisfactory results with fewer side effects. In addition, the EMO-based approach can produce multiple hiding solutions in a single run. It provides the opportunity for a user to choose freely the preferred one by preference or experience.

Keywords

Privacy preserving data mining association rule hiding evolutionary multi-objective optimization EMO

References

Menon

, Sarkar

and Mukherjee

, Maximizing accuracy of shared databases when concealing sensitive patterns, Information Systems Research 16(3) (2005), 256-270.

Verykios

V.S.

, Elmagarmid

A.K.

, Bertino

, Saygin

and Dasseni

, Association rule hiding, IEEE Transactions on Knowledge and Data Engineering 16(4) (2004), 434-447.

Bertino

, Fovino

I.N.

and Provenza

L.P.

, A framework for evaluating privacy preserving data mining algorithms, Data Mining and Knowledge Discovery 11(2) (2005), 121-154.

Amiri

, Dare to share: Protecting sensitive knowledge with data sanitization, Decision Support Systems 43(1) (2007), 181-191.

Gkoulalas-Divanis

and Verykios

V.S.

, Exact knowledge hiding through database extension, IEEE Transactions on Knowledge and Data Engineering 21(5) (2009), 699-713.

Cheng

, Pan

J.-S.

and Lin

C.-W.

, Privacy preserving association rule mining using binary encoded NSGA-II, in: Proceedings of the 18th Pacific-Asia Conference on Knowledge Discovery and Data Mining Workshop (2014), 87-99.

Verykios

V.S.

, Association rule hiding methods, Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery 3(1) (2013), 28-36.

Atallah

, Bertino

, Elmagarmid

, Ibrahim

and Verykios

, Disclosure limitation of sensitive rules, in: Proceedings of Knowledge and Data Engineering Exchange Workshop (1999), 45-52.

Dasseni

, Verykios

V.S.

, Elmagarmid

A.K.

and Bertino

, Hiding association rules by using confidence and support, in: Proceedings of the 4th Information Hiding Workshop (2001), 369-383.

10.

Y.H.

, Chiang

C.M.

and Chen

A.L.P.

, Hiding sensitive association rules with limited side effects, IEEE Transactions on Knowledge and Data Engineering 19(1) (Jan 2007), 29-42.

11.

Hong

T.-P.

, Lin

C.-W.

, Yang

K.-T.

and Wang

S.-L.

, Using TF-IDF to hide sensitive itemsets, Applied Intelligence 38(4) (2013), 502-510.

12.

Menon

and Sarkar

, Minimizing information loss and preserving privacy, Management Science 53(1) (2007), 101-116.

13.

Sun

and Yu

P.S.

, A border-based approach for hiding sensitive frequent itemsets, in: Proceedings of the Fifth IEEE International Conference on Data Mining (ICDM) (2005), 426-433.

14.

Verykios

V.S.

, Pontikakis

E.D.

, Theodoridis

and Chang

, Efficient algorithms for distortion and blocking techniques in association rule hiding, Distributed and Parallel Databases 22(1) (2007), 85-104.

15.

Saygin

, Verykios

V.S.

and Clifton

, Using unknowns to prevent discovery of association rules, ACM SIGMOD Record 30(4) (2001), 45-54.

16.

Gkoulalas-Divanis

and Verykios

V.S.

, Association rule hiding for data mining, Springer, 2010.

17.

Deb

, Multi-objective optimization using evolutionary algorithms, John Wiley and Sons, 2001.

18.

Coello

C.C.

, Lamont

G.B.

and Van Veldhuizen

D.A.

, Evolutionary algorithms for solving multi-objective problems, Springer, 2007.

19.

Bleuler

, Laumanns

, Thiele

and Zitzler

, PISA - A platform and programming language independent interface for search algorithms, in: Conference on Evolutionary Multi-criterion Optimization (EMO 2003), Faro, Portugal, (2003), 494-508.

20.

Deb

, Pratap

, Agarwal

and Meyarivan

, A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Transactions on Evolutionary Computation 6(2) (2002), 182-197.

21.

Künzli

E.Z.A.S.

, Indicator-based selection in multiobjective search, in: Parallel Problem Solving From Nature-PPSN VIII (2004), 832-842.

22.

Beume

, Naujoks

and Emmerich

, SMS-EMOA: Multiobjective selection based on dominated hypervolume, European Journal of Operational Research 181(3) (2007), 1653-1669.

23.

Bader

and Zitzler

, HypE: An algorithm for fast hypervolume-based many-objective optimization, Evolutionary Computation 19(1) (2011), 45-76.

24.

Davis

, Job shop scheduling with genetic algorithms, in: Proceedings of An International Conference on Genetic Algorithms and Their Applications, Hillsdale, NJ, USA, (1985), 136-140.

25.

Agrawal

and Srikant

, Fast algorithms for mining association rules, in: Proceedings of the 20th International Conference of Very Large Data Bases VLDB (1994), 487-499.

26.

Bodon

, A fast apriori implementation, in: Proceedings of the IEEE ICDM Workshop on Frequent Itemset Mining Implementations (FIMI'03), Melbourne, Florida, USA, (2003).

27.

Bodon

, A trie-based APRIORI implementation for mining frequent item sequences, in: Proceedings of the 1st International Workshop on Open Source Data Mining: Frequent Pattern Mining Implementations (2005), 56-65.

28.

Branke

, Deb

, Dierolf

and Osswald

, Finding knees in multi-objective optimization, in: Parallel Problem Solving From Nature-PPSN VIII (2004), 722-731.

29.

Bechikh

, Said

L.B.

and Ghédira

, Searching for knee regions in multi-objective optimization using mobile reference points, in: Proceedings of the 2010 ACM Symposium on Applied Computing (2010), 1118-1125.

30.

Kim

J.-H.

, Han

J.-H.

, Kim

Y.-H.

, Choi

S.-H.

and Kim

E.-S.

, Preference-based solution selection algorithm for evolutionary multiobjective optimization, IEEE Transactions on Evolutionary Computation 16(1) (2012), 20-34.

31.

Shukla

P.K.

, Braun

M.A.

and Schmeck

, Theory and algorithms for finding knees, in: Evolutionary Multi-Criterion Optimization (2013), 156-170.

32.

Deb

, Current trends in evolutionary multi-objective optimization, International Journal for Simulation and Multidisciplinary Design Optimization 1(1) (2007), 1-8.

33.

Bayardo Jr

R.J.

, Efficiently mining long patterns from databases, ACM Sigmod Record 27(2) (1998), 85-93.

34.

Kohavi

, Brodley

C.E.

, Frasca

, Mason

and Zheng

, KDD-Cup 2000 organizers' report: Peeling the onion, ACM SIGKDD Explorations Newsletter 2(2) (2000), 86-93.

35.

Brijs

, Swinnen

, Vanhoof

and Wets

, Using association rules for product assortment decisions: A case study, in: Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (1999), 254-260.