一種并行差分隱私關(guān)聯(lián)規(guī)則挖掘算法

申澤宇　袁健

摘 要：針對(duì)傳統(tǒng)基于ε-差分隱私模型的top-k關(guān)聯(lián)規(guī)則挖掘算法在大規(guī)模數(shù)據(jù)環(huán)境下挖掘效率低下的問題，提出了一種并行差分隱私關(guān)聯(lián)規(guī)則挖掘算法。算法利用Hadoop框架實(shí)現(xiàn)并行計(jì)算，利用負(fù)載均衡策略，使每一個(gè)節(jié)點(diǎn)分配到的數(shù)據(jù)量相當(dāng)，利用指數(shù)機(jī)制挑選出k個(gè)頻繁模式，采用拉普拉斯機(jī)制對(duì)這k個(gè)頻繁模式添加噪音。通過實(shí)驗(yàn)對(duì)算法的頻繁模式挖掘結(jié)果與同類算法進(jìn)行比較分析，結(jié)果表明，該算法在保證挖掘結(jié)果具有可用性的前提下，在效率上較傳統(tǒng)算法有所提升。

關(guān)鍵詞：頻繁模式挖掘；差分隱私；指數(shù)機(jī)制；并行計(jì)算

DOI：10.11907/rjdk.171559

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2017）009-0065-03

Abstract：In order to solve the problem of low efficiency of mining Top-k Association Rules Mining Algorithm Based on the differential privacy model in large scale data environment， a parallel algorithm for mining association rules based on differential privacy is proposed. The algorithm using Hadoop framework to realize parallel computing using the load balancing strategy， the amount of data so that each node is assigned to a selected K， using the index mechanism of frequent pattern， using the Laplasse mechanism add noise to these K frequent pattern. The results of the algorithm are compared with other algorithms. The experimental results show that the proposed algorithm can improve the efficiency of the mining algorithm than the traditional algorithm.

Key Words：frequent pattern mining； differential privacy； exponential mechanism； parallel computing

0 引言

隨著大數(shù)據(jù)時(shí)代的到來，數(shù)據(jù)挖掘成為研究熱點(diǎn)。而關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘中的一個(gè)重要研究課題。關(guān)聯(lián)規(guī)則挖掘能夠從數(shù)據(jù)中挖掘出潛在的項(xiàng)目之間的隱藏關(guān)系，如應(yīng)用醫(yī)療數(shù)據(jù)挖掘疾病之間的關(guān)聯(lián)，利用用戶交易數(shù)據(jù)挖掘用戶購(gòu)買行為之間的關(guān)聯(lián)等。然而對(duì)原始數(shù)據(jù)的發(fā)布會(huì)造成個(gè)人隱私泄漏，頻繁模式挖掘是關(guān)聯(lián)規(guī)則挖掘的核心，傳統(tǒng)的頻繁模式挖掘算法在面對(duì)海量數(shù)據(jù)時(shí)占用內(nèi)存大、效率低。如何提高算法效率和數(shù)據(jù)的可用性，同時(shí)解決隱私保護(hù)問題成為關(guān)聯(lián)規(guī)則分析的一個(gè)熱點(diǎn)。鑒于此，提出一種并行差分隱私頻繁模式挖掘算法。

1 相關(guān)工作

目前，在差分隱私模型下對(duì)頻繁模式挖掘進(jìn)行研究并取得了一定的研究成果。文獻(xiàn)[1]利用指數(shù)機(jī)制選取支持度最大的k個(gè)模式，對(duì)其添加噪聲得到top-k頻繁模式。文獻(xiàn)[2]利用θ-基以及映射技術(shù)提出了PrivBasis算法，首先由θ-頻繁對(duì)構(gòu)建出候選集合，接著對(duì)候選集合的頻度添加噪聲，最后選取k個(gè)作為top-k頻繁模式。文獻(xiàn)[3]考慮事務(wù)長(zhǎng)度對(duì)全局敏感度的影響，提出智能截?cái)嗪碗p重標(biāo)準(zhǔn)，有效提升了結(jié)果的可用性，但該方法只限于短事務(wù)居多的事務(wù)數(shù)據(jù)集。文獻(xiàn)[4]利用指數(shù)機(jī)制從候選集中選取top-k頻繁模式，并對(duì)選取的頻繁模式進(jìn)行噪音擾動(dòng)，而后通過對(duì)結(jié)果進(jìn)行二次規(guī)劃，提升數(shù)據(jù)的可用性。目前，關(guān)于差分隱私頻繁模式挖掘的研究雖已取得一定成果，但相關(guān)算法仍存在著消耗內(nèi)存大、效率低的問題。文獻(xiàn)[5-13]提出了并行頻繁模式挖掘算法，利用Hadoop平臺(tái)的多個(gè)節(jié)點(diǎn)并行運(yùn)算算法，可以有效地實(shí)施并行化，但仍會(huì)產(chǎn)生大量候選項(xiàng)集，且當(dāng)數(shù)據(jù)量大于數(shù)十萬數(shù)量級(jí)時(shí)算法無法高效率運(yùn)行。針對(duì)這一問題，本文提出基于指數(shù)機(jī)制和帶負(fù)載均衡的分布式FP-growth算法的分布式差分隱私頻繁模式挖掘算法（Parallel Differential Privacy Frequent Pattern Mining Algorithm，PDPFPM），擬在保證挖掘結(jié)果可用的前提下提升頻繁模式挖掘效率，滿足大數(shù)據(jù)的需求。通過與同類算法進(jìn)行比較，驗(yàn)證了PDPFPM算法的可行性和有效性。

2 相關(guān)定義

2.1 差分隱私

定義1（鄰近數(shù)據(jù)集）：若數(shù)據(jù)集D1和D2有且僅有一條數(shù)據(jù)項(xiàng)的值不同，則稱D1和D2為鄰近數(shù)據(jù)集。

定義2（差分隱私）：給定隱私保護(hù)算法f，若f對(duì)鄰近數(shù)據(jù)集D1和D2的輸出結(jié)果O∈Range（f）均滿足下列不等式，則稱算法f滿足ε-差分隱私。Pr[f（T1∈0）]≤eε×Pr[f（T2∈0）]

（1） 其中，ε為隱私預(yù)算，衡量差分隱私保護(hù)的水平。由式（1）可知ε越小，隱私保護(hù)的水平越強(qiáng)。f是一個(gè)隨機(jī)的算法，Range（f）表示算法f的取值范圍。Pr[f（T∈0）]表示輸出f（T）結(jié)果為O的概率。

定義3（全局敏感度）：對(duì)于任意的查詢函數(shù)q：D→Rd，函數(shù)q的全局敏感度為：Sq=max‖q（D1）·q（D2）‖endprint

（2） 其中，D1和D2是兄弟數(shù)據(jù)集，R表示所對(duì)應(yīng)的實(shí)數(shù)空間，d表示查詢q的查詢維度，q（Di）表示查詢函數(shù)q在數(shù)據(jù)集Di上的查詢結(jié)果。

定理1（串行組合定理）：給定一組隨機(jī)算法f={f1，f2，…，fn}，每個(gè)算法fi均在數(shù)據(jù)集T上實(shí)現(xiàn)了εi-差分隱私，其中i=1，2，…，n，則該組隨機(jī)算法f在數(shù)據(jù)集T上實(shí)現(xiàn)了∑ni=1εi-差分隱私。

2.2 噪聲機(jī)制

定義4（拉普拉斯機(jī)制）：通過對(duì)數(shù)據(jù)添加服從拉普拉斯分布的噪聲，實(shí)現(xiàn)差分隱私保護(hù)。其基本思想是對(duì)數(shù)據(jù)集D進(jìn)行查詢q，查詢結(jié)果為q（D）。向q（D）添加噪聲χ，其中χ是一個(gè)滿足拉普拉斯分布的連續(xù)型隨機(jī)變量，其概率密度函數(shù)為：Pr[χ]=12be|x-μ|b

（3） μ為期望，在差分隱私算法中一般μ取0，方差為2b2，b用來衡量添加噪聲的大小。對(duì)于給定的查詢函數(shù)q：D→Rd，若算法f的輸出結(jié)果滿足式（3），則算法f滿足ε-差分隱私。f（D）=q（D）+〈Lap1（sqε），…，Lapd（sqε）〉

（4） 其中，Lapd（sqε）是相互獨(dú)立的拉普拉斯噪聲，拉普拉斯參數(shù)b=Sq/ε。

2.3 指數(shù)機(jī)制

定義5（指數(shù)機(jī)制[15]）：對(duì)于給定的一個(gè)評(píng)價(jià)函數(shù)u：（D×0）→R，若算法f滿足等式（5），則算法f滿足ε-差分隱私。f（D，u）={r：Pr[r∈0]}∝exp（εu（D，r）Δu）

（5） 其中，r表示輸出項(xiàng)，Pr（r∈0）表示r輸出的概率，Δu為評(píng)價(jià)函數(shù)u的全局敏感度。其關(guān)鍵在于設(shè)計(jì)一個(gè)評(píng)價(jià)函數(shù)u，通過u得到輸出結(jié)果集O中r的指數(shù)分布，r被選擇輸出的概率服從式（5）的概率分布。

3 并行差分隱私頻繁模式挖掘算法

PDPFPM可以有效解決在海量數(shù)據(jù)下，運(yùn)用FP-Growth算法進(jìn)行頻繁模式挖掘時(shí)，占用內(nèi)存過多、效率低的不足，克服了MPI并行編程模型存在的節(jié)點(diǎn)失效、網(wǎng)絡(luò)通信故障等缺點(diǎn)，同時(shí)在挖掘出頻繁模式時(shí)，可以保護(hù)其支持度計(jì)數(shù)不被泄漏。

3.1 基本思想

首先，統(tǒng)計(jì)事務(wù)數(shù)據(jù)庫(kù)中每一個(gè)項(xiàng)的支持度并找出所有頻繁項(xiàng)，得到頻繁F1項(xiàng)集（FList）；其次進(jìn)行計(jì)算量估計(jì)，Map 過程采用根據(jù)計(jì)算量估計(jì)的分割方式讀入事務(wù)項(xiàng)，分發(fā)到不同的Reduce 節(jié)點(diǎn)。Reduce 過程對(duì)構(gòu)造的FP-Tree 進(jìn)行FP-Growth 挖掘得到局部頻繁項(xiàng)集，再由指數(shù)機(jī)制Pr[c]=exp（ε1×c×r2×n）∑ni=0exp（ε1×ci×r2×n）選出n個(gè)頻繁模式，對(duì)所選出的支持度計(jì)數(shù)添加拉普拉斯噪音，最后由局部頻繁項(xiàng)集合并成全局頻繁項(xiàng)集，選取支持度最高的n個(gè)。

3.2 基于計(jì)算量估計(jì)的分組策略

整個(gè)并行FP-Growth的計(jì)算量主要在于各節(jié)點(diǎn)的頻繁模式的數(shù)量，而一般支持度高的項(xiàng)，其計(jì)算量較大。SSCE設(shè)定每項(xiàng)的估計(jì)計(jì)算量為C=∑ri=0Ci，其中r為每條數(shù)據(jù)的含有項(xiàng)集。將傳入數(shù)據(jù)集前P個(gè)數(shù)據(jù)r的每一項(xiàng)作為一組，P為節(jié)點(diǎn)數(shù)，計(jì)算每一組的計(jì)算量，將下一條數(shù)據(jù)加入到最小的一組，重復(fù)計(jì)算直到整個(gè)數(shù)據(jù)集遍歷完畢。

3.3 算法描述及流程

PDPFPM算法流程如圖1所示。

步驟1：掃描數(shù)據(jù)集，統(tǒng)計(jì)頻繁F1項(xiàng)集（FList）。Map過程：第一次全量掃描數(shù)據(jù)，計(jì)算出各自候選F1項(xiàng)集。Reduce過程：收集Map 階段輸出的中間結(jié)果，進(jìn)行求和，統(tǒng)計(jì)每項(xiàng)在整個(gè)數(shù)據(jù)源中的支持度，舍棄小于最小支持度的項(xiàng)，得到FList并按支持度降序排列。

步驟2：計(jì)算量估計(jì)，進(jìn)行數(shù)據(jù)劃分。Map過程：第二次全量地訪問數(shù)據(jù)集，遍歷每條數(shù)據(jù)中的項(xiàng)，按SSCE分成P個(gè)組輸出的key值為分組號(hào)p，value為去除小于最小支持度的子項(xiàng)集。Combiner過程：聚合每組中的數(shù)據(jù)，形成待處理的數(shù)據(jù)。

步驟3：添加噪音，進(jìn)行隱私保護(hù)。此為加噪以及挖掘的一步，整個(gè)步驟為一個(gè)Reduce過程。建立FP-Tree，然后通過FP-Growth挖掘算法得到頻繁項(xiàng)集，采用指數(shù)機(jī)制選出n個(gè)頻繁模式，對(duì)其支持度添加Lap（kε2）噪音。

步驟4：局部頻繁項(xiàng)集合并成全局頻繁項(xiàng)集。讀取HDFS 文件中的結(jié)果，相同局部頻繁項(xiàng)集的支持度求和，得到全局支持度。按支持度降序排列，選擇前n個(gè)保存，作為最后的全局頻繁項(xiàng)集。

4 實(shí)驗(yàn)設(shè)計(jì)與分析

本文從數(shù)據(jù)可用性和算法性能的角度對(duì)PDPFPM算法進(jìn)行分析，并與傳統(tǒng)的頻繁模式隱私保護(hù)算法進(jìn)行比較。采用算法耗時(shí)來對(duì)算法性能進(jìn)行衡量，采用準(zhǔn)確率和召回率的調(diào)和平均值（F-score）對(duì)數(shù)據(jù)的可用性進(jìn)行衡量，由于算法添加噪音具有隨機(jī)性，取10次實(shí)驗(yàn)的平均值。

定義5（F-score） 設(shè)Rp為隱私保護(hù)后的挖掘結(jié)果，Ra為準(zhǔn)確的挖掘結(jié)果。準(zhǔn)確率（Precision）表示挖掘出的準(zhǔn)確結(jié)果，召回率（Recall）表示準(zhǔn)確結(jié)果被挖掘出的概率，由定義可以看出，準(zhǔn)確率和召回率是一對(duì)互斥的標(biāo)準(zhǔn)，采用F-score將兩者結(jié)合，F(xiàn)-score值越大，數(shù)據(jù)的可用性越高。Precision=Rp∩RaRp

（5）

recall=Rp∩RaRa

（6）

F-score=2×precision×recallprecision+recall

（7）4.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)采用IBM研究團(tuán)隊(duì)開發(fā)的數(shù)據(jù)生成器生成T10I4D100K數(shù)據(jù)集，對(duì)PDPFPM算法的數(shù)據(jù)可用性和算法性能進(jìn)行分析。

4.2 實(shí)驗(yàn)結(jié)果分析

隱私預(yù)算ε1和ε2各取0.5，計(jì)算F-score的取值，與DP-topkP[4]相比發(fā)現(xiàn)PDPFPM算法F-score的值比DP-topkP有所下降，這主要是由于分布式處理時(shí)，各單節(jié)點(diǎn)添加的噪音造成噪音積累，因此造成了F-score的下降，實(shí)驗(yàn)結(jié)果如表2所示。endprint

通過實(shí)驗(yàn)驗(yàn)證算法的性能，實(shí)驗(yàn)結(jié)果如表3所示（時(shí)間單位：s）?？梢园l(fā)現(xiàn)，PDPFPM算法處理時(shí)間提升同時(shí)隱私保護(hù)水平相當(dāng)。

頻繁模式挖掘的隱私保護(hù)日益成為大數(shù)據(jù)分析的基礎(chǔ)之一，頻繁模式挖掘受到了大量數(shù)據(jù)分析者的青睞，針對(duì)傳統(tǒng)基于ε-差分隱私模型的top-k關(guān)聯(lián)規(guī)則挖掘算法在大規(guī)模數(shù)據(jù)環(huán)境下挖掘效率低下的問題，提出PDPFPM算法，實(shí)驗(yàn)表明其可以有效解決算法的性能問題。

參考文獻(xiàn)：

[1] BHASKAR R， LAXMAN S， SMITH A， et al. Discovering frequent patterns in sensitive data[C].Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，ACM，2010：503-512.

[2] LI N， QARDAJI W， SU D， et al. PrivBasis：frequent itemset mining with differential privacy[J].Proceedings of the Vldb Endowment，2012，5（11）：1340-1351.

[3] ZENG C， NAUGHTON J F， CAI J Y. On differentially private frequent itemset mining[J]. Proceedings of the Vldb Endowment，2012，6（1）：25-36.

[4] ZHANG X， WANG M， MENG X.An accurate method for mining top-k frequent pattern under differential privacy[J]. Journal of Computer Research & Development，2014，51（1）：104-114.

[5] FANG M，SHIVAKUMAR N，GARCIA-MOLINA H，et al.Computing iceberg queries efficiently[C].Proceedings of the 24rd International Conference on Very Large Data Bases. Morgan Kaufmann Publishers Inc.，2000：299-310.

[6] QURESHI Z，BANSAL J，BANSAL S.A survey on association rule mining in cloud computing[J]. International Journal of Emerging Technology and Advanced Engineering，2013，3（4）：2250-2459.

[7] ASHRAFI M Z， TANIAR D， SMITH K.ODAM： An optimized distributed association rule mining algorithm[J]. Distributed Systems Online IEEE，2004，5（3）：1.

[8] LI L，ZHANG M.The Strategy of mining association rule based on cloud computing[C].International Conference on Business Computing and Global Informatization.IEEE Computer Society，2011：475-478.

[9] SANJEEV R， GUPTA P. Implementing improved algorithm over apriori data mining association rule algorithm[J]. IJCST，2012，3（1）：2250-2459.

[10] CHEN S Y， LI J H， LIN K C， et al.Using MapReduce framework for mining association rules[M]. Information Technology Convergence. Springer Netherlands，2013：723-731.

[11] RIONDATO M， DEBRABANT J A， FONSECA R， et al. PARMA：a parallel randomized algorithm for approximate association rules mining in MapReduce[C].ACM International Conference on Information and Knowledge Management，2012：85-94.

[12] YANG X Y， LIU Z， FU Y. MapReduce as a programming model for association rules algorithm on Hadoop[C]. International Conference on Information Sciences and Interaction Sciences，2010：99-102.

[13] LI N， ZENG L， HE Q， et al. Parallel implementation of apriori algorithm based on MapReduce[C]. Acis International Conference on Software Engineering， Artificial Intelligence，NETWORKING and Parallel & Distributed Computing，2012：236-241.

（責(zé)任編輯：孫 娟）endprint