面向频繁模式挖掘的差分隐私保护研究综述.pdf

《面向频繁模式挖掘的差分隐私保护研究综述.pdf》由会员分享，可在线阅读，更多相关《面向频繁模式挖掘的差分隐私保护研究综述.pdf（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2014?10?Journal on Communications October 2014?35?10?Vol.35 No.10?1?1,2(1.?100190?2.?100190)?3?TP309.2;TP392?A?1000-436X(2014)10-0200-10 Survey of differential privacy in frequent pattern mining DING Li-ping1,LU Guo-qing1,2(1.National Engineering Research Center of Fundamental Software,Institute of

2、Software,Chinese Academy of Sciences,Beijing 100190,China;2.University of Chinese Academy of Sciences,Beijing 100190,China)Abstract:Frequent pattern mining is an exploratory problem in the field of data mining.However,directly releasing the discovered frequent patterns and the corresponding true sup

3、ports may reveal the individuals privacy.The state-of-the-art solution for this problem is differential privacy,which offers a strong degree of privacy protection by adding noise.Firstly,the theoretical basis of differential privacy was introduced.Then,three representative frequent pattern mining me

4、thods under differential privacy were summarized and compared in detail.Finally,some future research directions were discussed.Key words:differential privacy;privacy protection;frequent pattern;data mining 1?(FPM,frequent pattern mining)1?(?)?k-?2?1)?2)?(DP,differential privacy)?Dwork?2006?2?2?3?1)?

5、(?)?2)?2?4?1)?2014-03-03?2014-04-20?(2012ZX01039-004)?(XDA06010600)Foundation Items:The National Science and Technology Major Program of China(2012ZX01039-004);The Strategic Technology Pilot Program of the Chinese Academy of Sciences(XDA06010600)doi:10.3969/j.issn.1000-436x.2014.10.023?10?201?2)?(FI

6、M,frequent itemset mining)?(FSM,frequent sequence mining)?(FGM,frequent subgraph mining)3?3?2?2.1?2,58?1 (-?2)?2?1D?2D?K?Range()K?K?K?-?Range()SK?12Pr()exp()Pr()K DSK DS?(1)?PrEs?Es?K?0.01,0.1,ln2,ln3?2.2?(global sensitivity)?2 (?9)?:f dDR,f?12,121max()()D Dff Df D=(2)?1D?2D?d?f?R?f?D?(Laplace mecha

7、nism)9?(exponential mechanism)10?11?12?13?14?1 (?9)?:f dDR?K?(3)?K?-?1()()(/),(/)dK Df DLapfLapf=+?(3)?(/)(1)iLapfid?f?f?(3)?()K D?(1)iid?2E(/)iferrorLapf=(4)?3 (?10)?:u()DOR?K?(5)?K?-?(,)(,)|Prexp()2u D rK D urrOu=(5)?u?(,)u D r?(,)()u D r rO?r?O?(5)?2.3?2?15?(sequential composition)?(parallel comp

8、osition)?1 (?15)?D?iK?(1)in?-i?iK?D?-i?2 (?15)?D?iK?(1)in?-i?iK?D?max()-i?2?1)?-?1?1?2?-?2)?-?202?35?1?2?2.4?2?1)?(,)userfullness 16?4 (,)userfullness 16)?K?Q?D?()DK D=?(6)?K?(,)userfullness?Pr|()()|1Q DQ Da?(6)2)?F-measure?top-k?F1-score?3?4?2?1)?2)?2?1?3?3.1?17?Apriori17?FP-growth18?TF19?FIM?(trun

9、cated frequency)?2?top-k?TF?2?1)?l?C?top-k?2)?k?2?(?PT-Exp)?(?PT-Lap)?1?2?1?TF?2?k?(2/)Lapkn?1?10?203?1?C?top-k?C?|lCI?|I?C?TF?C?p?ma()x(),kpf pff=?kf?C?k?C?01,=,kkSffCSff?(7)?C?0S?1S?1S?(1|1S=)?0S?(0|S?0|SC?)?C?0|1|CS+?TF?2?1 TF?2?PT-Exp?PT-Lap?1?Pr exp()4npf pk?C?k?top-k?C?)(4/Lapkn?top-k?2?k?)(2/

10、Lapkn?k?)(2/Lapkn?2(c)?TF?PT-Exp?l=2?top-3?TF?C?ln(|)4|/Iknl?k?l?0kf?()f p=max(),)kf pf?2 TF?PT-Exp?TF?PrivBasis20?-?top-k?1)?D?F?D?F?2)?F?-?P?F?P?-?B?3)?B?C B?C B?PrivBasis?-?B?(maximal clique)?F?P?B?F?P?,)G F P?,)G F P?-?-?-?B?3?-?B?D?-?341,I I I?B?top-k?l=2?top-3?13,I I?14,I I?34,I I?3 -?TF?top-k

11、?1)k?2)?21?DP-topkP?22?SmartTrunc?(?)?23?DiffPart?204?35?1)?2)?3)?D%?4?4?1,2,7,8T TTT?1v?4?DiffPart?1v?14vN=+1(1/)vLap?1v?1v?DiffPart?iv?)(ic v?22C ()/ih v?2C?()ih v?iv?iv?iv?)(ic v?12/(/2)C+?121,CC?DiffPart?/2?/2?4 DiffPart?2?TF?k?l?2?(|)O kD PrivBasis-?TF?(|)O w D DP-topkP?k?l?2?(|)O kD SmartTrunc

12、?(|)DOL DiffPart?2?(|)DOL DiffMR?MapReduce?k?l?(|)O kD?10?205?1111211111+1+1+2222mmiinnnnn=?(8)?m?in?i?1(,1)iimnnn+=?21924?3.2?25?(?)?(?Web?)?(?DNA?)?FSM?FIM?26?DiffPart23?(prefix tree)?STM-Full?1)?PT?2)?D%?1)?p?,ivp 1|)|tr(tr()|iivv+?tr()iv?iv?iv?1iv+?2)tr(|),|vv?children()|tr()|uvu?STM-basic?STM-F

13、ull?(?)?0?STM-Full?k?m?k?,()B m p?p=exp()/2?exp0,0()=1(),0 xp xxx?(9)?2 2/=?2?STM-Full?STM-Full?27?n-gram?N-gram?1)?D?maxgramn(maxn?n-gram?)?T?2)?T?n-gram?3)?(Markov assumption)?n-gram?n-gram?T?D%?3)?T?D%?1)?T?T?nmax?(?N-gram-uniform)?5?3?max5n=?2/5?N-gram?v?(10)?maxP?v?()c v?v?maxmaxmin(log),()vPni

14、c v=(10)?206?35?5?/5?1v?1max100.4314 109vPh=+?/54/51v=?N-gram?maxn-gram?T?3?1)?maxn?2)?3)?5?T?max=5=3n?1v?2v?3v?2830?(,)userfullness?STM-Full26?PT?1v?lo(g1/1/)iO?1v?210log1(1/)niiO=?i?1v?29?PT-Sample29?6?1)?PT?2)?top-k?6 PT-Sample?PT-Sample?2?PT?top-k?top-k?326,27,29,31?3.3?32?5 N-gram?3?STM-Full?(|

15、)DOL Prefix-Hybrid?(|)DOL N-gram?N-gram?(|)DOL PT-Sample?1(|)maxhLO D+?10?207?,)(GV E=?,()sssGV E=?sVV?sEE?sG?G?2?111)(,VGE=?222)(,VGE=?2?1V?2V?1E?2E?1G?2G?2G?1G?NPC?33?TF19?PT-Exp?(MCMC)?top-k?Diff-FPM?1)MCMC?k?top-k?2)?k?Diff-FPM?MCMC?top-k?MCMC?()x?MH(metropolis-hastings)?1)?(POFG)?POFG?2)?()()11

16、()/2()()/expexp2x Xu xuxu xu=(11)?x?()u x?3)?Diff-FPM?xyq?x?y?()()11expmin,1ex()/2(p)/2yxxyxyyqxuuqauu=(12)?A-A-D?=1/()xyqN x?()N x?x?A-D?()=5()10N xN y=?exp(3/2)(1/10)min0.82exp(2/2)(1/5)xya=?A-A-D?82%?A-D?Diff-FPM?MCMC?()x?(,)?34?4?4.1?1)?SuLQ-based ID35?DiffP-C4.535?DiffGen36?(information gain)?2

17、)?(means)?(center)?(median)?Pk-means37,38?Pk-median?39?GUPT40?k?NP?k?2?k?208?35?4.2?PDBSCAN41,42?4.3?1)?30?2)?MapReduce?Diff-FPM24?MapReduce?Airavat43?NoSQL?5?1 HAN J,KAMBER M,PEI J.Data Mining:Concepts and Tech-niquesM.Morgan kaufmann,2006.2 DWORK C.Differential privacyA.Proc of the 33rd Internatio

18、nal Colloquium on Automata,Languages and ProgrammingC.Berlin:Spinger-Verlag,2006.3?,?,?.?J.?,2014,37(1):101:122.XIONG P,ZHU T Q,WANG X F.A survey on differential privacy and applicationsJ.Chinese Journal of Computers,2014,37(1):101-122.4?,?.?J.?,2014,37(4):927-949.ZHANG X J,MENG X F.Differential pri

19、vacy in data publication and analysisJ.Chinese Journal of Computers,2014,37(4):927-949.5 BLUM A,DWORK C,McSHERRY F,et al.Practical privacy:the SuLQ frameworkA.Proc of the 24th ACM SIGMOD International Conference on Management of Data/Principles of Database Sys-temsC.NewYork:ACM Press,2005.128-138.6

20、BLUM A,LIGETT K,ROTH A.A Learning theory approach to non-interactive database privacyA.Proc of the 40th Annual ACM Symposium on Theory of Computing(STOC)C.Victoria,British Columbia,Canada,2008.351-360.7 DWORK C.A firm foundation for private data analysisJ.Commu-nications of the ACM,2011,54(1):86-95.

21、8 NGUYEN H H,KIM J,KIM Y.Differential privacy in practiceJ.Journal of Computing Science and Engineering,2013,7(3):177-186.9 DWORK C,MCSHERRY F,NISSIM K,et al.Calibrating noise to sensitivity in private data analysisA.TCCC.2006.265-284.10 MCSHERRY F,TALWAR K.Mechanism design via differential privacyA

22、.FOCSC.2007.94-103.11 DWORK C,NAOR M,VADHAN S.The privacy of the analyst and the power of the stateA.2012 IEEE 53rd Annual Symposium on Foundations of Computer Science(FOCS)C.2012.400-409.12 GHOSH A,ROUGHGARDEN T,SUNDARARAJAN M.Universally utility-maximizing privacy mechanismsA.Proceedings of the 41

23、st Annual ACM Symposium on Theory of ComputingC.ACM,2009.351-360.13 LI C,HAY M,RASTOGI V,et al.Optimizing linear counting queries under differential privacyA.Proceedings of the 29th ACM SIG-MOD-SIGACT-SIGART Symposium on Principles of Database Sys-temsC.2010.123-134.14 ZHANG J,ZHANG Z,XIAO X,et al.F

24、unctional mechanism:regres-sion analysis under differential privacyJ.Proceedings of the VLDB Endowment,2012,5(11):1364-1375.15 MCSHERRY F.Privacy integrated queries:an extensible platform for privacy-preserving data analysis WWWA.SIGMOD ConferenceC.?10?209?2009.19-30.16 KIFER D,MACHANAVAJJHALA A.No

25、free lunch in data pri-vacyA.Proceedings of the 2011 ACM SIGMOD International Con-ference on Management of dataC.2011.193-204.17 AGRAWAL R,SRIKANT R.Fast algorithms for mining association rulesA.Proc 20th Int Conf Very Large Data BasesC.1994.487-499.18 HAN J,PEI J,YIN Y.Mining frequent patterns with

26、out candidate generationJ.ACM SIGMOD Record,2000,29(2):1-12.19 BHASKAR R,LAXMAN S,SIMTH A,et al.Discovering frequent patterns in sensitive dataA.Proceedings of the ACM SIGKDD In-ternational Conference on Knowledge Discovery and Data Mining(SIGKDD)C.Washington,DC,USA,2010.503-512.20 LI N,QARDAJI W,SU

27、 D,et al.Privbasis:frequent itemset mining with differential privacyA.Proceedings of the 38th Conference of Very Large Databases(VLDB)C.Istanbul,Turkey,2012.1340-1351.21?,?,?.?top-k?J.?,2014,51(1):104-114.ZHANG X J,WANG M,MENG X J.An accurate method for mining top-k frequent pattern under differenti

28、al privacyJ.Journal of Com-puter Research and Develoment,2014,51(1):104-114.22 ZENG C,NAUGHTON J,CAI J Y:On differentially private frequent itemset miningJ.PVLDB,2012,6(1):25-36.23 CHEN R,MOHAMMED N,FUNG B C M,et al.Publishing set-valued data via differential privacyA.Proceedings of the 37th Confere

29、nce of Very Large Databases(VLDB)C.Seattle,Washington,USA,2011.1087-1098.24 HAN X,WANG M,ZHANG X,et al.Differentially private top-k query over MapReduceA.Proceedings of the 4th International Workshop on Cloud Data ManagementC.2012.25-32.25 AGRAWAL R,SRIKANT R.Mining sequential patternsA.Pro-ceedings

30、 of the 11th International Conference on Data Engineering IEEEC.1995.3-14.26 CHEN R,FUNG B,DESAI B C.Differentially private trajectory data publicationEB/OL.http:/arxiv.org/abs/1112.2020.27 CHEN R,CS G,CASTELLUCCIA C.Differentially private sequen-tial data publication via variable-length n-gramsA.CC

31、SC.2012.638-649.28 BONOMI L,XIONG L,CHEN R,et al.Frequent grams based em-bedding for privacy preserving record linkageA.CIKMC.2012.1597-1601.29 BONOMI L,XIONG L.A two-phase algorithm for mining sequential patterns with differential privacyA.CIKMC.2013.269-278.30 BONOMI L.Mining frequent patterns wit

32、h differential privacyJ.PVLDB,2013,6(12):1422-1427.31 CHEN R,FUNG B,DESAI B C,et al.Differentially private transit data publication:a case study on the montreal transportation sys-temA.Proceedings of the 18th ACM SIGKDD International Con-ference on Knowledge Discovery and Data MiningC.ACM,2012:213-2

33、21.32 HAN J,CHENG H,XIN D,et al.Frequent pattern mining:current status and future directionsJ.Data Mining and Knowledge Discovery,2007,15(1):55-86.33 SHEN ET,YU T.Mining frequent graph patterns with differential privacyA.KDDC.2013.545-553.34 DWORK C,KENTHAPADI K,MCSHERRY F,et al.Our Data,Ourselves:P

34、rivacy Via Distributed Noise GenerationM.Springer Berlin Heidelberg,2006.486-503.35 FRIEDMAN A,SCHUSTER A.Data mining with differential pri-vacyA.Proceedings of the 16th ACM SIGKDD International Con-ference on Knowledge Discovery and Data MiningC.ACM,2010.493-502.36 MOHAMMED N,CHEN R,FUNG B,et al.Di

35、fferentially private data release for data miningA.Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data MiningC.2011.493-501.37 NISSIM K,RASKHODNIKOVA S,SMITH A.Smooth sensitivity and sampling in private data analysisA.Proceedings of the 39th An-nual ACM Sympos

36、ium on Theory of ComputingC.2007.75-84.38?,?,?.?k-means?J.?,2013,40(3):287-290.LI Y,HAO ZF,WEN W.Research on differential privacy preserving k-means clusteringJ.Computer Science,2013,40(3):287-290.39 GUPTA A,LIGETT K,MCSHERRY F,et al.Differentially private combinatorial optimizationA.Proceedings of

37、the 21st Annual ACM-SIAM Symposium on Discrete Algorithms.Society for Indus-trial and Applied MathematicsC.2010.1106-1125.40 MOHAN P,THAKURTA A,SHI E,et al.GUPT:privacy preserving data analysis made easyA.Proceedings of the 2012 ACM SIGMOD International Conference on Management of DataC.2012.349-360

38、.41 HO S S,RUAN S.Differential privacy for location pattern miningA.Proceedings of the 4th ACM SIGSPATIAL International Workshop on Security and Privacy in GIS and LBS SPRINGL)C.Chicago,IL,USA,2011.17-24.42 HO S S.Preserving privacy for moving objects data miningA.2012 IEEE International Conference on Intelligence and Security Informat-ics(ISI)C.2012.135-137.43 ROY I,SETTY S T V,KILZER A,et al.Airavat:security and privacy for MapReduceA.Proceedings of the 7th USENIX Conference on Networked Systems Design and ImplementationC.USENIX Asso-ciation,2010.20-20.?1989-?1965-?