李洪成，吳曉平，陳燕

?

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

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

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

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

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

1 引言

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

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

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

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

2 差分隱私保護

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 算法設(shè)計

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

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

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

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

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

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

3.2 隱私性分析

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

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

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

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

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

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

4 算法效率及可用性實驗

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

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

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

4.1 算法運行效率實驗

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

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

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

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

4.2 聚類結(jié)果可用性實驗

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

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

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

(6)

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

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

(8)

將本文算法的聚類結(jié)果與數(shù)據(jù)集中標準分類結(jié)果的相似程度記為F-measure1，并將本文算法的聚類結(jié)果與文獻[3]算法聚類結(jié)果的相似程度記為F-measure2。由于算法每次運行時噪聲的添加量服從Laplace隨機分布，所以聚類結(jié)果具有一定的隨機性，因此實驗中的結(jié)果取10次運算的平均值。對于“Blood”和“gamma”數(shù)據(jù)集，當隱私保護預(yù)算變化時，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可以看出，當隱私保護預(yù)算大于3時，本文算法的聚類結(jié)果可用性達到較高水平，因此本文算法可以在實現(xiàn)隱私性的情況下，保證聚類結(jié)果具有較好的可用性?另外，圖4中當隱私保護預(yù)算較小時，聚類結(jié)果的可用性隨著隱私保護預(yù)算的增加而顯著增加，當增大到一定值時，聚類結(jié)果可用性的增加速度趨于平緩，而考慮到隱私保護預(yù)算與添加噪聲的尺度參數(shù)成反比，因此用本文算法處理“Blood”和“gamma”數(shù)據(jù)集時，隱私保護預(yù)算取3~4有利于實現(xiàn)算法隱私性和可用性的平衡。

5 結(jié)束語

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

[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]. 計算機研究與發(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并行化實現(xiàn)[J]. 華中科技大學學報（自然科學版）, 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] 肖人毅. 云計算中數(shù)據(jù)隱私保護研究進展[J]. 通信學報, 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]. 小型微型計算機系統(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] 李楊, 郝志峰, 溫雯, 等. 差分隱私保護-means聚類方法研究[J]. 計算機科學, 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: 基于云計算的并行分布式數(shù)據(jù)挖掘工具平臺[J]. 中國科學: 信息科學, 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] 熊平, 朱天清, 王曉峰. 差分隱私保護及其應(yīng)用[J]. 計算機學報, 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] 丁麗萍, 盧國慶. 面向頻繁模式挖掘的差分隱私保護研究綜述[J]. 通信學報, 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ā)布和分析的差分隱私保護[J]. 計算機學報, 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

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

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

李洪成（1991-），男，河南商丘人，海軍工程大學博士生，主要研究方向為信息安全、數(shù)據(jù)挖掘。

吳曉平（1961-），男，山西新絳人，海軍工程大學教授、博士生導(dǎo)師，主要研究方向為信息安全、密碼學。

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