武警工程大學 林煥楠 李慶鵬 耿新元

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

武警工程大學 林煥楠 李慶鵬 耿新元

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

spark；Apriori

0.引言

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

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

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

1.差分隱私保護

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

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

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

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

2.DPFM算法設(shè)計

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

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

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

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

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

3.實驗與分析

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

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

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

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

4.結(jié)束語

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

[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.