一種基于差分隱私保護(hù)的數(shù)據(jù)挖據(jù)頻繁項(xiàng)集算法

武警工程大學(xué) 林煥楠 李慶鵬 耿新元

一種基于差分隱私保護(hù)的數(shù)據(jù)挖據(jù)頻繁項(xiàng)集算法

武警工程大學(xué) 林煥楠 李慶鵬 耿新元

差分隱私定義了一種比較嚴(yán)格和強(qiáng)健的隱私保護(hù)模型，通過添加噪音使數(shù)據(jù)失真達(dá)到隱私保護(hù)的目的。本文提出一種基于差分隱私的頻繁項(xiàng)集挖掘方法DPFM，該算法的挖掘策略結(jié)合Laplace機(jī)制，能夠在保證計(jì)算性能的前提下實(shí)現(xiàn)差分隱私保護(hù)。通過實(shí)驗(yàn)表明，本文提出的DPFM算法在誤差和拒真率以及兩種指標(biāo)的收斂速度上都優(yōu)于TF方法。

spark；Apriori

0.引言

頻繁模式挖掘是數(shù)據(jù)挖掘研究中的一個(gè)重要課題，其目的是找出頻繁出現(xiàn)在數(shù)據(jù)集中的模式，是關(guān)聯(lián)規(guī)則、相關(guān)性分析、分類、聚類和其他數(shù)據(jù)挖掘任務(wù)的基礎(chǔ)，也是數(shù)據(jù)分析的主要技術(shù)之一[1]。作為最簡單的FPM類型，頻繁項(xiàng)集挖掘最初應(yīng)用于事物數(shù)據(jù)庫中關(guān)聯(lián)規(guī)則的發(fā)現(xiàn)，同時(shí)也是其他模式挖掘的基礎(chǔ)。Apriori和FP-growth算法是發(fā)現(xiàn)頻繁項(xiàng)集的經(jīng)典算法[2]。

Apriori算法是最具影響力的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法，國內(nèi)外學(xué)者做了大量卓有成效的研究工作。其中，文獻(xiàn)[3]提出一種分組統(tǒng)計(jì)策略的Apriori并行算法，有效地減少了鍵/值對(duì)的產(chǎn)生，很大的提升了算法時(shí)間性能。文獻(xiàn)[4]提出一種基于矩陣的并行關(guān)聯(lián)規(guī)則算法Apriori_MMR，該算法結(jié)合了數(shù)據(jù)劃分的思想進(jìn)行并行化改進(jìn)，簡化了生成候選項(xiàng)的連接步驟，僅需對(duì)事務(wù)數(shù)據(jù)庫掃描兩次，同時(shí)在計(jì)算過程中還能對(duì)事務(wù)進(jìn)行壓縮從而進(jìn)一步提高了算法的性能[5]。

本文提出一種基于差分隱私的頻繁項(xiàng)集挖掘方法DPFM，該算法的挖掘策略結(jié)合Laplace機(jī)制和指數(shù)機(jī)制，能夠在保證計(jì)算性能的前提下實(shí)現(xiàn)差分隱私保護(hù)。

1.差分隱私保護(hù)

差分隱私保護(hù)技術(shù)被公認(rèn)為一種比較嚴(yán)格和強(qiáng)健的隱私保護(hù)模型，從本質(zhì)上來說，它是一種借助數(shù)據(jù)擾動(dòng)、加噪來保護(hù)數(shù)據(jù)敏感信息不被泄露的信息安全技術(shù)。

定義1 ε-差分隱私[6]（ε-differential privacy）對(duì)于給定的兩個(gè)臨近數(shù)據(jù)集D和D'，數(shù)據(jù)集間最多相差一條記錄，給定一個(gè)隱私算法A，R為A的輸出域，對(duì)任意子集，若算法A滿足：

則稱算法A提供ε-差分隱私保護(hù)，其中Pr[X]表示事件X發(fā)生的概率。

定義2 全局敏感度[7]設(shè)有函數(shù)，輸入為一數(shù)據(jù)集D，輸出為一d維實(shí)數(shù)向量。對(duì)于任意的鄰近數(shù)據(jù)集D和D'，函數(shù)f的全局敏感度為：

2.DPFM算法設(shè)計(jì)

Step1.獲取λ值，即支持度滿足閾值θ的項(xiàng)的個(gè)數(shù)。

Step2.構(gòu)建節(jié)點(diǎn)集F，F(xiàn)包含項(xiàng)集I中最頻繁的λ項(xiàng)，即所有支持度滿足閾值θ的頻繁項(xiàng)，F(xiàn)將包含top-k項(xiàng)集中出現(xiàn)的所有頻繁項(xiàng)。

Step3.基于F構(gòu)建邊集P，P由F中的所有長度為2且滿足閾值θ的子集構(gòu)成，即集合P將包含top-k項(xiàng)集中出現(xiàn)的所有頻繁對(duì)。

Step4.基于F和P生成圖G(F,P)，找出圖G上的所有極大團(tuán)M，構(gòu)成θ-基集合B，每個(gè)極大團(tuán)對(duì)應(yīng)一個(gè)θ-基，最終找到一個(gè)寬度和長度都盡可能小的θ-基集。

Step5.由B構(gòu)建候選集C(B)，計(jì)算C(B)中項(xiàng)集的支持度，并對(duì)支持度進(jìn)行差分隱私處理，最終從中獲得滿足隱私約束top-k頻繁項(xiàng)集的相關(guān)信息。

3.實(shí)驗(yàn)與分析

本文實(shí)驗(yàn)實(shí)施的硬件環(huán)境為：AMD Athlon Ⅱ X4 645 Processor 3.1GHz處理器，4GB內(nèi)存。軟件方面采用win7操作系統(tǒng)，使用Matlab實(shí)現(xiàn)和運(yùn)行相關(guān)算法。

由于本文提出的DPFM算法在不同值的情況下有著不同的處理策略，本實(shí)驗(yàn)通過將本文提出的DPFM算法與TF方法置于三種具有代表性的數(shù)據(jù)集上進(jìn)行測試，如表1所示：

表1　實(shí)驗(yàn)使用的真實(shí)數(shù)據(jù)集在確定

可以看出，隨著隱私預(yù)算的增加，算法結(jié)果的拒真率和相對(duì)誤差均呈現(xiàn)下降趨勢，并在隱私預(yù)算取到0.6以上時(shí)逐漸趨于穩(wěn)定，由于頻繁項(xiàng)集的挖掘范圍較小，兩種算法在誤差上的表現(xiàn)均比較優(yōu)秀，綜合來看，算法提供的結(jié)果的準(zhǔn)確率較高，但本文提出的DPFM算法在誤差和拒真率以及兩種指標(biāo)的收斂速度上都優(yōu)于TF方法。

4.結(jié)束語

針對(duì)長事務(wù)數(shù)據(jù)上的挖掘效率與準(zhǔn)確性較低等問題，提出了一種滿足差分隱私約束的頻繁項(xiàng)集挖掘算法DPFM，該算法從頻繁項(xiàng)集挖掘的先驗(yàn)規(guī)則出發(fā)，結(jié)合極大團(tuán)理論和-基映射技術(shù)，根據(jù)閾值將數(shù)據(jù)集中的大量事務(wù)壓縮除冗，挖掘事務(wù)集合中保留有效信息的閉頻繁項(xiàng)集來構(gòu)建候選集，并結(jié)合Laplace機(jī)制對(duì)頻繁項(xiàng)支持度隱私信息進(jìn)行噪聲擾動(dòng)，實(shí)現(xiàn)了ε-差分隱私隱私處理，最終由候選集重構(gòu)得到滿足隱私安全策略的top-k頻繁項(xiàng)集的支持度，由于算法有效的控制了候選集的規(guī)模，降低了添加的噪聲量和所消耗的隱私預(yù)算，從而在保證數(shù)據(jù)隱私的前提下，提升了算法在挖掘top-k頻繁項(xiàng)集時(shí)的性能和準(zhǔn)確性。

[1]Ding Li ping,Lu Guoqing Survey of differential privacy in frequent pattern mining [J].Journal on Communication2014,35(10):200-209.

[2]Inokuchi A, Washio T, Motoda H.An Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data[C].European Conference on Principles of Data Mining&Knowledge Discovery,2000:13-23.

[3]Huang Liqin, Liu Yanhuang,MapReduce based parallel Apriori algorithm improvement research[J].Journal of Fuzhou University (NATURAL SCIENCE EDITION),2011,39(5):34-39.

[4]Xie Zhiming, Wang Peng, a parallel matrix Apriori algorithm based on Reduce Map architecture[J].computer application research,34(1):17-21.

[5]Dwork C,Dwork C.The Differential Privacy Frontier[J]. Tcc, 2009:496--502.

[6]Xie Zhiming,Wang Peng, a parallel matrix Apriori algorithm based on Reduce Map architecture[J].computer application research,34(1):17-21.

[7]Wang Baoyi,Wang Dongyang,Zhang Shaomin. Short term distributed power load forecasting algorithm based on Spark and [J].IPPSO_ LSSVM electric power automation equipment,2016,36(1):117-122.