MapReduce框架下支持差分隱私保護(hù)的k-means聚類方法

李洪成，吳曉平，陳燕

?

MapReduce框架下支持差分隱私保護(hù)的-means聚類方法

李洪成1，吳曉平1，陳燕2

（1. 海軍工程大學(xué)信息安全系，湖北武漢 430033；2. 解放軍61062部隊(duì)，北京 100091）

針對(duì)傳統(tǒng)隱私保護(hù)方法無(wú)法應(yīng)對(duì)任意背景知識(shí)下惡意分析的問題，提出了分布式環(huán)境下滿足差分隱私的-means算法。該算法利用MapReduce計(jì)算框架，由主任務(wù)控制-means迭代執(zhí)行；指派Mapper分任務(wù)獨(dú)立并行計(jì)算各數(shù)據(jù)片中每條記錄與聚類中心的距離并標(biāo)記其屬于的聚類；指派Reducer分任務(wù)計(jì)算同一聚類中的記錄數(shù)量和屬性向量之和，并利用Laplace機(jī)制產(chǎn)生的噪聲擾動(dòng)和，進(jìn)而實(shí)現(xiàn)隱私保護(hù)。根據(jù)差分隱私的組合特性，從理論角度證明整個(gè)算法滿足-差分隱私保護(hù)。實(shí)驗(yàn)結(jié)果證明了該方法在提高隱私性和時(shí)效性的情況下，保證了較好的可用性。

數(shù)據(jù)挖掘；-均值聚類；MapReduce；差分隱私保護(hù)；Laplace機(jī)制

1 引言

數(shù)據(jù)挖掘作為信息獲取的一種重要方法，可以從體量巨大、快速更新、類型多樣、價(jià)值量大的大數(shù)據(jù)中挖掘出有用的信息。聚類分析是一種典型的非指導(dǎo)學(xué)習(xí)數(shù)據(jù)挖掘方法，主要思想是將數(shù)據(jù)分為若干類，使各聚類中的數(shù)據(jù)差別最小、聚類之間的數(shù)據(jù)差別最大，該方法在網(wǎng)絡(luò)入侵異常檢測(cè)、大規(guī)模選址和市場(chǎng)細(xì)分等領(lǐng)域有重要應(yīng)用。

在大數(shù)據(jù)的背景下，聚類分析技術(shù)主要面臨以下2個(gè)問題。1) 隨著大數(shù)據(jù)時(shí)代的數(shù)據(jù)體量越來越巨大，單個(gè)計(jì)算機(jī)難以在可接受的時(shí)間內(nèi)對(duì)數(shù)據(jù)進(jìn)行有效的聚類分析。因此，如何利用并行分布式計(jì)算資源進(jìn)行快速聚類分析[1]是亟待解決的關(guān)鍵問題。2) 數(shù)據(jù)聚類分析的結(jié)果在提供有價(jià)值信息的同時(shí)，可能會(huì)泄露數(shù)據(jù)集中單個(gè)記錄的信息，對(duì)數(shù)據(jù)隱私安全造成威脅。在大數(shù)據(jù)時(shí)代，攻擊者所擁有的背景知識(shí)越來越多，使攻擊者竊取數(shù)據(jù)隱私更加便利[2]。因此，研究應(yīng)對(duì)任意背景知識(shí)的隱私保護(hù)聚類分析技術(shù)成為隱私保護(hù)領(lǐng)域的研究焦點(diǎn)。

國(guó)內(nèi)外學(xué)者做了許多卓有成效的研究工作。其中，文獻(xiàn)[3]在云計(jì)算平臺(tái)上采用高效的MapReduce并行計(jì)算模型實(shí)現(xiàn)了-means聚類算法?該算法首先利用MapReduce的映射函數(shù)計(jì)算各條記錄到聚類中心的距離，并標(biāo)記其屬于的聚類中心，然后利用規(guī)約函數(shù)計(jì)算出新的聚類中心，最后啟用新的MapReduce Job來進(jìn)行-means算法的下一輪迭代，進(jìn)而將-means算法每輪迭代中時(shí)間復(fù)雜度最高的步驟交由分布式計(jì)算資源處理，有效提高了-means算法的運(yùn)行效率。在提高聚類分析時(shí)效性的同時(shí)，云平臺(tái)的開放性使攻擊者擁有大量的攻擊背景知識(shí)[4]，攻擊者可以通過關(guān)聯(lián)背景知識(shí)和聚類結(jié)果來竊取數(shù)據(jù)隱私[5,6]。然而，傳統(tǒng)的隱私保護(hù)方法只能應(yīng)對(duì)特定背景知識(shí)下的攻擊，針對(duì)此問題，文獻(xiàn)[7]利用差分隱私保護(hù)的嚴(yán)格定義，提出了可以應(yīng)對(duì)任意背景知識(shí)下攻擊的-means聚類方法DP-means（differential private-means），該方法通過對(duì)-means算法每輪迭代中各聚類內(nèi)記錄之和和記錄數(shù)等中間變量加入適量隨機(jī)噪聲來實(shí)現(xiàn)隱私保護(hù)。此外，文獻(xiàn)[8,9]針對(duì)DP-means中初始聚類中心受隨機(jī)噪聲影響較大的問題，對(duì)DP-means算法的初始中心點(diǎn)選擇方法進(jìn)行了改進(jìn)，有效提高了聚類分析的可用性。以上文獻(xiàn)并沒有研究將DP-means部署于分布式環(huán)境的具體方法，也就沒有解決分布式環(huán)境下應(yīng)對(duì)任意背景知識(shí)的數(shù)據(jù)隱私保護(hù)問題。

基于此，本文提出了一種MapReduce框架[10]下支持差分隱私保護(hù)的-means聚類方法，利用MapReduce框架提供的分布式計(jì)算功能來提高聚類分析的效率，并通過隨機(jī)噪聲添加使聚類的輸出結(jié)果滿足差分隱私。

2 差分隱私保護(hù)

差分隱私保護(hù)是一種基于部分信息隱藏的隱私保護(hù)技術(shù)，該技術(shù)通過隨機(jī)響應(yīng)或隨機(jī)噪聲添加來實(shí)現(xiàn)信息干擾，同時(shí)使干擾后的輸出信息在一定程度上保持原有的統(tǒng)計(jì)特性，進(jìn)而使數(shù)據(jù)挖掘結(jié)果的可用性保持在可接受的范圍內(nèi)。

差分隱私技術(shù)給出了一個(gè)嚴(yán)格且可證明的隱私保護(hù)定義，保證在數(shù)據(jù)集中改變?nèi)我粭l記錄時(shí)，查詢結(jié)果的變化量極小，攻擊者在已知除目標(biāo)記錄外所有其他記錄信息的條件下，仍然無(wú)法分析出這條記錄的任何信息，因此該方法可以應(yīng)對(duì)任意背景知識(shí)下的惡意分析[11]。差分隱私保護(hù)的基本原理如下。

用戶從數(shù)據(jù)集中提取信息的操作被定義為查詢，算法對(duì)查詢的輸出進(jìn)行隨機(jī)化處理，使之滿足差分隱私保護(hù)的條件[12]。

定理1 假設(shè)數(shù)據(jù)集和完全相同或只相差一條記錄，()為一個(gè)隨機(jī)算法輸出的值域，[]為事件發(fā)生的可能性，如果對(duì)于任意∈()，有

則隨機(jī)算法提供-差分隱私保護(hù)，其中，參數(shù)稱為隱私保護(hù)預(yù)算。

全局敏感度是查詢函數(shù)的一條重要固有屬性，反映單個(gè)記錄變化對(duì)查詢函數(shù)輸出的影響。全局敏感度的定義如下。

定義1查詢的全局敏感度為

差分隱私保護(hù)的實(shí)現(xiàn)機(jī)制主要有Laplace機(jī)制與指數(shù)機(jī)制2種，分別利用隨機(jī)噪聲添加和隨機(jī)響應(yīng)的方式實(shí)現(xiàn)隱私保護(hù)。其中，Laplace機(jī)制適用于對(duì)數(shù)值型結(jié)果的保護(hù)[13]，是聚類分析中最常用的差分隱私保護(hù)機(jī)制，其原理如下。

定理2 對(duì)于查詢，數(shù)據(jù)集，設(shè)查詢輸出為()，的全局敏感度為Δ，如果噪聲服從尺度為的拉普拉斯分布，則算法滿足-差分隱私[13]。

此外，差分隱私保護(hù)具有序列組合性和并行組合性2種組合特性，這些特性在證明算法是否滿足差分隱私以及在隱私預(yù)算分配過程中起著重要作用[14]。

性質(zhì)1 設(shè)有個(gè)隨機(jī)算法1,…,A，算法A(1≤≤)提供ε-差分隱私保護(hù)，則對(duì)于同一數(shù)據(jù)集，{1,…,A}在上的序列組合算法提供-差分隱私保護(hù)，其中，。

性質(zhì)2 設(shè)有隨機(jī)算法和數(shù)據(jù)集，將分為不相交的子集1,…,D，若算法提供-差分隱私保護(hù)，則在{1,…,D}上的組合運(yùn)算所構(gòu)成的算法提供-差分隱私保護(hù)。

3 MapReduce框架下的DP k-means算法

本文算法的功能是在MapReduce分布式環(huán)境下，保證在數(shù)據(jù)集中改變?nèi)我挥涗洉r(shí)，每個(gè)聚類的質(zhì)心以及記錄數(shù)量所發(fā)生的變化不泄露隱私信息，即惡意分析者無(wú)法利用其擁有的與原數(shù)據(jù)集相似的數(shù)據(jù)集，通過挖掘得到原數(shù)據(jù)集中單個(gè)記錄的隱私信息。算法應(yīng)對(duì)的攻擊模型如圖1所示。

算法的基本思路是利用分布式計(jì)算節(jié)點(diǎn)上的Map分任務(wù)判斷出各記錄屬于的聚類類別，利用Reduce分任務(wù)計(jì)算出聚類中的記錄數(shù)量和對(duì)應(yīng)屬性之和，并加入適量Laplace噪聲，使聚類分析的結(jié)果滿足-差分隱私。

傳統(tǒng)的差分隱私保護(hù)-means算法[7]存在聚類準(zhǔn)確性較低的問題，其主要原因是隨機(jī)選擇的初始中心點(diǎn)導(dǎo)致算法收斂速度較慢，而算法迭代次數(shù)的增多導(dǎo)致了每輪添加的噪聲增多，而且添加了噪聲的初始中心點(diǎn)往往與原中心點(diǎn)偏離較遠(yuǎn)[9]，這些問題均導(dǎo)致了算法的聚類準(zhǔn)確性較低，所以本算法在對(duì)差分隱私保護(hù)-means算法進(jìn)行MapReduce并行化設(shè)計(jì)時(shí)，采用改進(jìn)的初始中心點(diǎn)選擇和加噪方法。

3.1 算法設(shè)計(jì)

設(shè)數(shù)據(jù)集中的記錄總數(shù)為，各條記錄記為a(1≤≤)，各記錄的維數(shù)為；將這些記錄分為個(gè)數(shù)據(jù)片，各數(shù)據(jù)片記為D(1≤≤)；算法要求的聚類數(shù)目為，各聚類中心記為u(1≤≤)。算法的步驟如下。

Step1 主任務(wù)Driver首先將各記錄歸一化到[0, 1]空間中。將條記錄1,…,a平均分成個(gè)子集1,…,C，集合C中的記錄數(shù)|C|≤，()為向上取整函數(shù)[8]。計(jì)算C中記錄的數(shù)量和C中各記錄的屬性向量之和，分別對(duì)和加入隨機(jī)噪聲得到和，計(jì)算0，即為初始聚類中心點(diǎn)。

Step2 主任務(wù)將所有數(shù)據(jù)記錄平均分為個(gè)數(shù)據(jù)片，并指派個(gè)分任務(wù)執(zhí)行Map操作，指派個(gè)分任務(wù)執(zhí)行Reduce操作。

Step4 Reducer分任務(wù)接收所有同屬于一個(gè)聚類中心的<，>對(duì)，運(yùn)行Reduce函數(shù)：計(jì)算該聚類中記錄的數(shù)量和聚類內(nèi)各記錄的屬性向量之和，對(duì)和加入隨機(jī)噪聲，然后計(jì)算加噪后的聚類中心點(diǎn)。

Step5 主任務(wù)接收各個(gè)Reduce節(jié)點(diǎn)的輸出結(jié)果，計(jì)算本輪和上一輪中個(gè)聚類中心點(diǎn)的距離。若中心點(diǎn)屬性向量差的距離范數(shù)小于閾值，則算法終止，輸出各聚類中心和聚類內(nèi)記錄的數(shù)量；否則，重復(fù)Step3~Step5。

MapReduce框架下的DP-means算法流程如圖2所示。

3.2 隱私性分析

由圖2可以看出，MapReduce框架下DP-means算法的隱私性通過對(duì)每個(gè)Reduce操作中的num和sum加入Laplace噪聲來實(shí)現(xiàn)。由于-means算法的每輪迭代相當(dāng)于隨機(jī)算法的序列組合，所以根據(jù)性質(zhì)1可知，整個(gè)算法的隱私保護(hù)預(yù)算為

其中，為迭代的總次數(shù)，ε為第次迭代的隱私保護(hù)預(yù)算。在預(yù)算分配方面，本文采用文獻(xiàn)[7]的策略，每次迭代消耗剩余隱私預(yù)算的一半，即第次迭代的隱私預(yù)算為ε=。

圖2 MapReduce框架下的DP -means算法

在每輪迭代中，由于個(gè)Reducer分節(jié)點(diǎn)相互獨(dú)立地執(zhí)行操作，各輪迭代的結(jié)果相當(dāng)于Reduce操作的并行組合[15]，所以根據(jù)性質(zhì)2可知，要想第輪迭代滿足ε-差分隱私，需要使分布式環(huán)境下每個(gè)Reducer分任務(wù)的操作滿足ε-差分隱私。

由定義1可知，的全局敏感度Δnum=1，在維空間[0, 1]的點(diǎn)集中添加或刪除一個(gè)點(diǎn)，各個(gè)屬性和的最大變化量為1，由于點(diǎn)的維數(shù)為，則的全局敏感度Δsum=?所以根據(jù)性質(zhì)1可知，整個(gè)查詢序列的全局敏感度Δ=+1。

因此，由定理2可知，在初始中心點(diǎn)計(jì)算過程中的0和0上分別加入隨機(jī)噪聲(1)，并在算法第輪迭代的num和sum上分別加入隨機(jī)噪聲(1)，可以保證MapReduce框架下DP-means算法滿足-差分隱私保護(hù)。相比于傳統(tǒng)的差分隱私保護(hù)-means算法，改進(jìn)的初始中心點(diǎn)計(jì)算過程可以在相同的隱私保護(hù)預(yù)算下，減少算法的迭代次數(shù)，進(jìn)而減少隨機(jī)噪聲添加量。

4 算法效率及可用性實(shí)驗(yàn)

由于本文算法的主要功能是利用MapReduce分布式計(jì)算框架提高聚類效率，并利用Laplace機(jī)制保護(hù)數(shù)據(jù)隱私，而算法的隱私性已經(jīng)在上文中得到證明，因此本文的實(shí)驗(yàn)部分只考慮算法的運(yùn)行效率，以及隱私保護(hù)聚類算法的輸出結(jié)果可用性。

實(shí)驗(yàn)中云計(jì)算平臺(tái)由1臺(tái)主節(jié)點(diǎn)的計(jì)算機(jī)和3臺(tái)分節(jié)點(diǎn)的計(jì)算機(jī)組成，每臺(tái)計(jì)算機(jī)配置如下：操作系統(tǒng)為L(zhǎng)inux，CPU為3.30 GHz，內(nèi)存為2.99 GB。在集群上部署Hadoop0.20.2。聚類算法利用Java軟件進(jìn)行開發(fā)。

實(shí)驗(yàn)所選擇的數(shù)據(jù)集為UCI Knowledge Discovery Archive database中的“Blood”數(shù)據(jù)集（記錄數(shù)為748，屬性數(shù)為5，數(shù)據(jù)類型為實(shí)值型）和“gamma”數(shù)據(jù)集（記錄數(shù)為19 020，屬性數(shù)為10，數(shù)據(jù)類型為實(shí)值型），這2個(gè)數(shù)據(jù)集中均給出了各記錄的分類信息，因此可以用來檢驗(yàn)聚類算法的性能。根據(jù)“Blood”和“gamma”數(shù)據(jù)集的標(biāo)準(zhǔn)分類結(jié)果，實(shí)驗(yàn)設(shè)定聚類中心數(shù)為2，相鄰2輪中心點(diǎn)屬性向量差的距離范數(shù)小于1時(shí)迭代終止。

4.1 算法運(yùn)行效率實(shí)驗(yàn)

為反映MapReduce框架下算法運(yùn)行效率受分布式計(jì)算節(jié)點(diǎn)數(shù)量的影響，本實(shí)驗(yàn)啟動(dòng)1個(gè)和3個(gè)分節(jié)點(diǎn)分別進(jìn)行運(yùn)算，并考察不同數(shù)據(jù)量情況下加速比的變化規(guī)律。首先，在“gamma”數(shù)據(jù)集上截取不同數(shù)量的記錄作為待處理文件，分別上傳至Hadoop的HDFS文件系統(tǒng)中。然后，將本文算法部署于MapReduce中，記錄5次運(yùn)行時(shí)間的平均值，得到1個(gè)和3個(gè)子節(jié)點(diǎn)分別參與運(yùn)算的情況下算法的運(yùn)行時(shí)間（如圖3所示）。

由圖3可以看出，系統(tǒng)啟動(dòng)3個(gè)子節(jié)點(diǎn)時(shí)算法的運(yùn)行時(shí)間較啟動(dòng)1個(gè)子節(jié)點(diǎn)時(shí)顯著減少，說明分布式集群可以有效提高本文聚類算法的運(yùn)行效率。然而，隨著數(shù)據(jù)集記錄數(shù)量的增多，運(yùn)行效率的提高比例逐漸降低。主要原因是記錄數(shù)量的增漲導(dǎo)致算法迭代次數(shù)增加，而每輪迭代中都有主節(jié)點(diǎn)與子節(jié)點(diǎn)之間的數(shù)據(jù)傳遞操作，以及主節(jié)點(diǎn)進(jìn)行的聚類中心距離比較操作，這些操作沒有利用分布式集群的資源，因此操作用時(shí)隨著迭代次數(shù)增加而增加，而不隨子節(jié)點(diǎn)數(shù)目增加而減少。

另外，為反映本文算法引入隱私保護(hù)后對(duì)算法效率的影響，將本文算法與分布式計(jì)算框架下的-means算法進(jìn)行比較。由于文獻(xiàn)[3]算法將-means算法部署于MapReduce環(huán)境中，而沒有引入隱私保護(hù)，所以選擇文獻(xiàn)[3]算法作為比較對(duì)象。首先，在包含1個(gè)主節(jié)點(diǎn)和3個(gè)分節(jié)點(diǎn)的分布式計(jì)算平臺(tái)上，分別利用本文算法和文獻(xiàn)[3]算法處理“gamma”數(shù)據(jù)集上截取的不同文件，記錄5次運(yùn)行時(shí)間的平均值，得到本文算法運(yùn)行時(shí)間減去文獻(xiàn)[3]算法運(yùn)行時(shí)間的差值（如圖4所示）。

通過比較圖3和圖4中數(shù)值的數(shù)量級(jí)，可以看出2種算法運(yùn)行時(shí)間的差值比算法運(yùn)行時(shí)間要小約4個(gè)數(shù)量級(jí)。因此，相比于文獻(xiàn)[3]算法，本文算法在提高隱私性的情況下，并沒有導(dǎo)致運(yùn)行效率的明顯降低。此外，由圖4可以看出，2種算法運(yùn)行時(shí)間的差值隨著數(shù)據(jù)集記錄數(shù)量的增漲而增大。主要原因是隨著記錄數(shù)量的增長(zhǎng)，算法的迭代次數(shù)逐漸增加，而本文算法的每輪迭代都要進(jìn)行Laplace隨機(jī)噪聲的產(chǎn)生和添加操作，每輪迭代中的這些操作直接導(dǎo)致了2種算法運(yùn)行時(shí)間的差別。

4.2 聚類結(jié)果可用性實(shí)驗(yàn)

為衡量本文提出的MapReduce框架下差分隱私聚類算法的可用性，本實(shí)驗(yàn)選擇以下參考標(biāo)準(zhǔn)與本文算法聚類結(jié)果進(jìn)行比較：1)由于“Blood”和“gamma”數(shù)據(jù)集中的標(biāo)準(zhǔn)分類情況是在真實(shí)情況下調(diào)查得到的，因此選擇“Blood”和“gamma”數(shù)據(jù)集的標(biāo)準(zhǔn)分類結(jié)果作為比較對(duì)象之一；2) 為了分析本文算法引入隱私保護(hù)后對(duì)聚類結(jié)果可用性的影響，本實(shí)驗(yàn)選擇文獻(xiàn)[3]算法的聚類結(jié)果作為可用性比較的另一個(gè)參考對(duì)象。

衡量數(shù)據(jù)挖掘結(jié)果可用性的指標(biāo)主要有準(zhǔn)確率（precision）和召回率（recall）等，而F-measure可以對(duì)準(zhǔn)確率和召回率進(jìn)行綜合，因此本實(shí)驗(yàn)利用F-measure評(píng)價(jià)指標(biāo)來衡量聚類可用性?F-measure越大說明2個(gè)聚類結(jié)果的相似程度越強(qiáng)，即本文算法所添加的噪聲對(duì)聚類可用性影響越小?

F-measure的計(jì)算過程如下：用表示作為參考標(biāo)準(zhǔn)的聚類結(jié)果，表示本文聚類算法的聚類結(jié)果，聚類數(shù)為，U為中的第個(gè)聚類集合（1≤≤），V為中的第個(gè)聚類集合（設(shè)2次聚類的標(biāo)記統(tǒng)一），cover為U和V重合的記錄數(shù)目，|U|和|V|分別為U和V中的記錄數(shù)目，記第個(gè)聚類的準(zhǔn)確率為P，召回率為R，則

(6)

然后，計(jì)算P和R的加權(quán)調(diào)和平均，記為F，則

最后，對(duì)各聚類的F進(jìn)行加權(quán)平均。設(shè)TOTAL為數(shù)據(jù)集記錄總數(shù)，算得聚類結(jié)果的可用性度量

(8)

將本文算法的聚類結(jié)果與數(shù)據(jù)集中標(biāo)準(zhǔn)分類結(jié)果的相似程度記為F-measure1，并將本文算法的聚類結(jié)果與文獻(xiàn)[3]算法聚類結(jié)果的相似程度記為F-measure2。由于算法每次運(yùn)行時(shí)噪聲的添加量服從Laplace隨機(jī)分布，所以聚類結(jié)果具有一定的隨機(jī)性，因此實(shí)驗(yàn)中的結(jié)果取10次運(yùn)算的平均值。對(duì)于“Blood”和“gamma”數(shù)據(jù)集，當(dāng)隱私保護(hù)預(yù)算變化時(shí)，F(xiàn)-measure1和F-measure2的變化情況如圖5所示。

(a)“Blood”數(shù)據(jù)集聚類結(jié)果的F-measure變化情況

(b)“gamma”數(shù)據(jù)集聚類結(jié)果的F-measure變化情況

圖5 各數(shù)據(jù)集的F-measure1和F-measure2隨變化情況

由圖5可以看出，當(dāng)隱私保護(hù)預(yù)算大于3時(shí)，本文算法的聚類結(jié)果可用性達(dá)到較高水平，因此本文算法可以在實(shí)現(xiàn)隱私性的情況下，保證聚類結(jié)果具有較好的可用性?另外，圖4中當(dāng)隱私保護(hù)預(yù)算較小時(shí)，聚類結(jié)果的可用性隨著隱私保護(hù)預(yù)算的增加而顯著增加，當(dāng)增大到一定值時(shí)，聚類結(jié)果可用性的增加速度趨于平緩，而考慮到隱私保護(hù)預(yù)算與添加噪聲的尺度參數(shù)成反比，因此用本文算法處理“Blood”和“gamma”數(shù)據(jù)集時(shí)，隱私保護(hù)預(yù)算取3~4有利于實(shí)現(xiàn)算法隱私性和可用性的平衡。

5 結(jié)束語(yǔ)

本文利用MapReduce計(jì)算框架實(shí)現(xiàn)了并行分布式-means聚類，并同時(shí)利用Laplace機(jī)制實(shí)現(xiàn)了算法的差分隱私保護(hù)，同時(shí)提高了-means算法的時(shí)效性和隱私性。下一步需要進(jìn)行的研究工作主要有以下2個(gè)方面：1) 針對(duì)算法迭代次數(shù)對(duì)運(yùn)行效率影響較大的問題，設(shè)計(jì)算法減少M(fèi)apReduce Job的運(yùn)行次數(shù)，并將-means中的迭代執(zhí)行判斷工作交由子節(jié)點(diǎn)執(zhí)行；2) 為緩解算法隱私性和可用性之間的矛盾，研究如何在保證隱私保護(hù)水平的前提下，通過綜合利用指數(shù)機(jī)制和Laplace機(jī)制，減少對(duì)每輪迭代實(shí)施的擾動(dòng)。

[1] FLAVIO C, NILESH D, RAVI K. Correlation clustering in MapReduce[C]//The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2014). New York, USA, c2014: 641-650.

[2] 孟小峰, 張嘯劍. 大數(shù)據(jù)隱私管理[J]. 計(jì)算機(jī)研究與發(fā)展, 2015, 52(2):265-281.

MENG X F, ZHANG X J. Big data privacy management[J]. Journal of Computer Research and Development, 2015, 52(2):265-281.

[3] 江小平, 李成華, 向文, 等.-means聚類算法的MapReduce并行化實(shí)現(xiàn)[J]. 華中科技大學(xué)學(xué)報(bào)（自然科學(xué)版）, 2011, 39(S1): 120-124.

JIANG X P, LI C H, XIANG W, et al. Parallel implementing-means clustering algorithm using MapReduce programming mode[J]. Journal of Huazhong Univ of Sci & Tech(Natural Science Edition), 2011, 39(S1):120-124.

[4] ROY I, SETTY S T V, KILZER A, et al. Airavat: security and privacy for MapReduce[C]//The 7th USENIX Symposium on Networked Systems Design and Implementation. San Jose, USA, c2010:297-312.

[5] 肖人毅. 云計(jì)算中數(shù)據(jù)隱私保護(hù)研究進(jìn)展[J]. 通信學(xué)報(bào), 2014, 35(12):168-177.

XIAO R Y. Survey of privacy preserving data queries in cloud computing[J]. Journal on Communications, 2014, 35(12):168-177.

[6] SHI E, CHAN T H, RIEFFEL E G,. Privacy-preserving aggregation of time-series data[C]//The Network and Distributed System Security Symposium. San Diego, USA, c2011.

[7] DWORK C. A Firm Foundation for Private Data Analysis[J]. Communications of the ACM, 2011, 54(1):86-95.

[8] 李楊, 郝志峰, 肖燕珊, 等. 差分隱私DPE-means 數(shù)據(jù)聚合下的多維數(shù)據(jù)可視化[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2013, 34(7):1637-1640.

LI Y, HAO Z F, XIAO Y S, et al. Multidimensional data visualization using aggregation method of differential privacy equip partition k-means[J]. Journal of Chinese Computer Systems, 2013, 34(7): 1637-1640.

[9] 李楊, 郝志峰, 溫雯, 等. 差分隱私保護(hù)-means聚類方法研究[J]. 計(jì)算機(jī)科學(xué), 2013, 40(3):287-290.

LI Y, HAO Z F, WEN W, et al. Research on differential privacy preserving-means clustering[J]. Computer Science, 2013, 40(3): 287-290.

[10] 何清, 莊福振, 曾立, 等. PDMiner: 基于云計(jì)算的并行分布式數(shù)據(jù)挖掘工具平臺(tái)[J]. 中國(guó)科學(xué): 信息科學(xué), 2014, 44(7):871-885.

HE Q, ZHUANG F Z, ZENG L, et al. PDMiner: a cloud computing based parallel and distributed data mining toolkit platform[J]. Chinese Science: Information Science, 2014, 44(7):871-885.

[11] MCGREGOR A, MIRONOV I, PITASSI T, et al. The limits of two-party differential privacy[C]//The 51st IEEE Annual Symposium on Foundations of Computer Science. Las Vegas, USA, c2010:81-90.

[12] 熊平, 朱天清, 王曉峰. 差分隱私保護(hù)及其應(yīng)用[J]. 計(jì)算機(jī)學(xué)報(bào), 2014, 37(1):101-122.

XIONG P, ZHU T Q, WANG X F. A survey on differential privacy and applications[J]. Chinese Journal of Computers, 2014, 37(1):101-122.

[13] 丁麗萍, 盧國(guó)慶. 面向頻繁模式挖掘的差分隱私保護(hù)研究綜述[J]. 通信學(xué)報(bào), 2014, 35(10):200-209.

DING L P, LU G Q. Survey of differential privacy in frequent pattern mining[J]. Journal on Communications, 2014, 35(10):200-209.

[14] 張嘯劍, 孟小峰. 面向數(shù)據(jù)發(fā)布和分析的差分隱私保護(hù)[J]. 計(jì)算機(jī)學(xué)報(bào), 2014, 37(4):927-949.

ZHANG X J, MENG X F. Differential privacy in data publication and analysis[J]. Chinese Journal of Computers, 2014, 37(4):927-949.

[15] MCSHERRY F. Privacy integrated queries: an extensible platform for privacy-preserving data analysis[J]. Communication of the ACM, 2010, 53(9):89-97.

-means clustering method preserving differential privacy in MapReduce framework

LI Hong-cheng1, WU Xiao-ping1, CHEN Yan2

(1. Department of Information Security, Naval University of Engineering, Wuhan 430033, China; 2. No.61062 Troops of PLA, Beijing 100091, China)

Aiming at the problem that traditional privacy preserving methods were unable to deal with malign analysis with arbitrary background knowledge, a-means algorithm preserving differential privacy in distributed environment was proposed. This algorithm was under the computing framework of MapReduce. The host tasks were obligated to control the iterations of-means. The Mapper tasks were appointed to compute the distances between all the records and clustering centers and to mark the records with the clusters to which the records belong. The Reducer tasks were appointed to compute the numbers of records which belong to the same clusters and the sums of attributes vectors, and to disturb the numbers and the sums with noises made by Laplace mechanism, in order to achieve differential privacy preserving. Based on the combinatorial features of differential privacy, theoretically prove that this algorithm is able to fulfill-differentially private. The experimental results demonstrate that this method can remain available in the process of preserving privacy and improving efficiency.

data mining,-means clustering, MapReduce, differential privacy preserving, Laplace mechanism

TP301

A

10.11959/j.issn.1000-436x.2016038

2015-04-05；

2015-07-28

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61100042）；總后軍內(nèi)科研基金資助項(xiàng)目（No.AWS14R013）

The National Natural Science Foundation of China (No.61100042), The Military Scientific Research Project of the General Logistics Department (No.AWS14R013)

李洪成（1991-），男，河南商丘人，海軍工程大學(xué)博士生，主要研究方向?yàn)樾畔踩?、?shù)據(jù)挖掘。

吳曉平（1961-），男，山西新絳人，海軍工程大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)樾畔踩⒚艽a學(xué)。

陳燕（1975-），女，河北石家莊人，解放軍61062部隊(duì)高級(jí)工程師，主要研究方向?yàn)榫W(wǎng)絡(luò)應(yīng)用、信息系統(tǒng)。