基于Spark的支持隱私保護(hù)的聚類(lèi)算法

高志強(qiáng)，李慶鵬，胡人遠(yuǎn)

（武警工程大學(xué)信息工程系，陜西 西安710086）

基于Spark的支持隱私保護(hù)的聚類(lèi)算法

高志強(qiáng)，李慶鵬，胡人遠(yuǎn)

（武警工程大學(xué)信息工程系，陜西 西安710086）

針對(duì)經(jīng)典聚類(lèi)方法無(wú)法應(yīng)對(duì)任意背景知識(shí)下惡意攻擊者在海量數(shù)據(jù)挖掘過(guò)程中的惡意攻擊問(wèn)題，結(jié)合差分隱私保護(hù)機(jī)制，提出一種適用于Spark內(nèi)存計(jì)算框架下滿足差分隱私保護(hù)的聚類(lèi)算法，并從理論上證明了改進(jìn)算法滿足在Spark并行計(jì)算框架下的ε-差分隱私。實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法在保證聚類(lèi)結(jié)果可用性前提下，具有良好的隱私保護(hù)性和滿意的運(yùn)行效率，在海量數(shù)據(jù)聚類(lèi)分析的隱私保護(hù)挖掘中，具有很好的應(yīng)用前景和價(jià)值。

Spark；差分隱私；聚類(lèi)算法；數(shù)據(jù)挖掘；大數(shù)據(jù)分析

1 引言

在大數(shù)據(jù)時(shí)代，海量數(shù)據(jù)的分析和處理技術(shù)受到了越來(lái)越廣泛的關(guān)注，尤其是大型互聯(lián)網(wǎng)公司，數(shù)據(jù)就是商機(jī)，數(shù)據(jù)就是價(jià)值。然而，在開(kāi)放系統(tǒng)環(huán)境下，信息資源的共享在給用戶帶來(lái)極大便利的同時(shí)，數(shù)據(jù)的隱私與敏感信息的保護(hù)問(wèn)題也不斷凸顯。用戶的原始數(shù)據(jù)信息可能在數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)的某個(gè)過(guò)程中被惡意攻擊者破壞、篡改、截獲，用戶數(shù)據(jù)信息的隱私安全正面臨著前所未有的威脅[1]。因此，支持任意背景知識(shí)下可以保護(hù)用戶隱私信息的海量數(shù)據(jù)挖掘算法

已成為研究熱點(diǎn)[2]。

國(guó)內(nèi)外學(xué)者做了許多卓有成效的研究工作。文獻(xiàn)[3]提出了一種基于 Haar小波和Daub-4小波分析的數(shù)據(jù)變換方式，使經(jīng)典的分類(lèi)挖掘算法滿足隱私保護(hù)的要求。文獻(xiàn)[4]在樸素貝葉斯分類(lèi)器的基礎(chǔ)上，提出一種滿足隱私保護(hù)的高效分布式推薦算法。文獻(xiàn)[5]將隱私保護(hù)機(jī)制融入 Hadoop平臺(tái)下的MapReduce分布式計(jì)算框架，實(shí)現(xiàn)了海量分布式數(shù)據(jù)的隱私保護(hù)算法。

文獻(xiàn)[6,7]均實(shí)現(xiàn)了MapReduce大數(shù)據(jù)并行計(jì)算框架與經(jīng)典聚類(lèi)算法的結(jié)合，其中，文獻(xiàn)[6]主要針對(duì)聚類(lèi)算法應(yīng)對(duì)最大背景知識(shí)攻擊的問(wèn)題，保證了改進(jìn)算法在挖掘過(guò)程中的隱私保護(hù)特性。文獻(xiàn)[7]在MapReduce框架基礎(chǔ)上，實(shí)現(xiàn)了支持差分隱私保護(hù)的 k-means聚類(lèi)算法，該算法在Reduce階段為數(shù)值型變量 num和 sum添加Laplace噪聲，實(shí)現(xiàn)了差分隱私保護(hù)。但是MapReduce框架在算法迭代過(guò)程中，需多次讀寫(xiě)存儲(chǔ)在外部硬盤(pán)的數(shù)據(jù)，消耗大量與 HDFS的I/O通信資源，并且過(guò)多的噪聲擾動(dòng)也會(huì)增加隱私保護(hù)算法的復(fù)雜度開(kāi)銷(xiāo)。因此，為了提高對(duì)隱私數(shù)據(jù)的保護(hù)程度和挖掘結(jié)果的可用性，本文以海量數(shù)據(jù)的數(shù)理統(tǒng)計(jì)特性為出發(fā)點(diǎn)，提出一種Spark框架下能有效支持差分隱私保護(hù)的k-means聚類(lèi)方法，使惡意攻擊者即使在獲取最大數(shù)據(jù)背景知識(shí)情況下，仍無(wú)法得到用戶數(shù)據(jù)的敏感信息。

2 差分隱私保護(hù)

大數(shù)據(jù)時(shí)代，攻擊者可以通過(guò)網(wǎng)絡(luò)資源，利用多種黑客技術(shù)獲取關(guān)于用戶隱私數(shù)據(jù)的背景知識(shí)，從而導(dǎo)致了用戶隱私的泄露，甚至引發(fā)犯罪和一系列更為嚴(yán)重的后果。而差分隱私保護(hù)技術(shù)（DP, differential privacy）[8]通過(guò)向數(shù)據(jù)集加入與數(shù)據(jù)集大小無(wú)關(guān)的擾動(dòng)噪聲（DN, disturbance noise），降低原始用戶數(shù)據(jù)在查詢或結(jié)果分析中泄露的風(fēng)險(xiǎn)，以達(dá)到保護(hù)隱私的效果，其形式化定義如下。

定理1 假設(shè)數(shù)據(jù)集D0或D1完全相同或只相差一條記錄（D0和D1被稱(chēng)為兄弟數(shù)據(jù)集），定義F為查詢操作，F(xiàn)(A)為隨機(jī)算法的查詢輸出，Pr[X]為事件X發(fā)生的概率測(cè)度，如果對(duì)任意輸出S∈F(A)，有則隨機(jī)算法A為隱私預(yù)算ε提供ε-差分隱私保護(hù)[9]。

圖1給出差分隱私算法的輸出結(jié)果所對(duì)應(yīng)的概率密度函數(shù)。

圖1 差分隱私算法輸出的概率密度函數(shù)

由圖1可知，單條記錄r是否在兄弟數(shù)據(jù)集中，對(duì)滿足差分隱私保護(hù)的隨機(jī)算法的輸出結(jié)果所對(duì)應(yīng)的概率密度函數(shù)變化影響不大，也就是說(shuō)，差分隱私保護(hù)算法所對(duì)應(yīng)的輸出函數(shù)值對(duì)于輸入數(shù)據(jù)集的微小差異是不敏感的，攻擊者無(wú)法輕易判斷某條數(shù)據(jù)記錄是否在數(shù)據(jù)集中。

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

定義1 查詢函數(shù)F所對(duì)應(yīng)的全局敏感度[10]為

其中，數(shù)據(jù)集D0與D1只相差一條記錄，|| ||1為向量的一范式。

本文采用了可以較好地保持原有數(shù)據(jù)統(tǒng)計(jì)特性的 Laplace機(jī)制，使改進(jìn)算法更適用于數(shù)值型聚類(lèi)分析，其原理如圖2所示。

圖2 Laplace機(jī)制

Laplace機(jī)制通過(guò)向數(shù)值型數(shù)據(jù)中添加Laplace噪聲實(shí)現(xiàn)差分隱私保護(hù)，其具體實(shí)現(xiàn)如定理2。

定理2 對(duì)于查詢函數(shù)F，數(shù)據(jù)集D0，設(shè)查詢輸出為F(D0)，F(xiàn)的全局敏感度為 ΔF ，如果噪聲 Y服從尺度為ΔF的 Laplace分布，則算法ε A(D0)=F(D0)+Y滿足ε-差分隱私[11]。

此外，差分隱私保護(hù)具有序列組合性和并行組合性[12]。

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

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

基于性質(zhì)1和性質(zhì)2，本文證明了改進(jìn)算法DP HK-means滿足差分隱私并指導(dǎo)隱私預(yù)算分配過(guò)程。

3 Spark框架下的DP HK-means算法

本文算法基于Spark內(nèi)存計(jì)算框架，實(shí)現(xiàn)了海量數(shù)據(jù)在聚類(lèi)分析時(shí)，在數(shù)據(jù)集的統(tǒng)計(jì)信息改變?nèi)我粭l記錄時(shí)，具有最大背景知識(shí)的攻擊者在整個(gè)聚類(lèi)過(guò)程中仍無(wú)法獲得數(shù)據(jù)隱私的功能，其對(duì)應(yīng)的攻擊模型如圖3所示。

圖3 本文算法對(duì)應(yīng)的攻擊模型

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

為解決k-means算法在聚類(lèi)挖掘過(guò)程中不適合海量數(shù)據(jù)分布式挖掘、缺乏隱私保護(hù)功能等問(wèn)題，本文提出一種適合于 Spark內(nèi)存迭代框架的DP HK-means算法，該算法主要執(zhí)行步驟如下。

Step1 將從 HDFS中讀取的初始數(shù)據(jù)集轉(zhuǎn)換為Spark框架下的RDD數(shù)據(jù)集，并對(duì)初始聚類(lèi)中心點(diǎn)編碼。

Step2 Map操作。訓(xùn)練初始聚類(lèi)中心，獲得初始聚類(lèi)中心，構(gòu)成（Key，Value）鍵值對(duì)，并選擇距離最小的聚類(lèi)中心，判斷記錄的聚類(lèi)歸屬。

Step3 Reduce及隱私保護(hù)操作。計(jì)算各個(gè)聚類(lèi)中記錄數(shù)量num及其向量和sum，并對(duì)變量sum加入Laplace噪聲擾動(dòng)，重新計(jì)算相應(yīng)聚類(lèi)中心。

Step4 根據(jù)Key值，進(jìn)行Join操作，產(chǎn)生新的 RDD數(shù)據(jù)集，如果本輪和上輪聚類(lèi)中心向量差小于預(yù)設(shè)值，則通過(guò)SaveAsTextFile方法保存聚類(lèi)結(jié)果，結(jié)束迭代；否則循環(huán)Step 2～Step 4，并將中間計(jì)算結(jié)果緩存至Cache中，進(jìn)行下一輪操作。

Step5 輸出聚類(lèi)結(jié)果。

在Step1和Step2中，本文改進(jìn)算法利用初始聚類(lèi)中心改進(jìn)初始中心的選擇方式，加快聚類(lèi)速率；在Step3中，由于變量num屬于攻擊者背景知識(shí)，為減少多余噪聲對(duì)聚類(lèi)中心的影響，只需對(duì)聚類(lèi)內(nèi)記錄的向量和sum進(jìn)行差分隱私處理以提高保護(hù)效率及聚類(lèi)準(zhǔn)確性；在Step4中，利用Spark框架的核心技術(shù)，將RDD緩存至Cache，避免與HDFS的多次I/O通信，提高了算法執(zhí)行效率。

3.2 隱私性分析

中間變量加入噪聲擾動(dòng)，降低了隱私保護(hù)預(yù)算，提高了迭代效率，減少了過(guò)多噪聲對(duì)聚類(lèi)效果的影響。

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

實(shí)驗(yàn)平臺(tái)搭建5個(gè)分布式節(jié)點(diǎn)，相關(guān)配置如下：操作系統(tǒng)為CentOS 6.4，CPU為3.30 GHz，內(nèi)存為16 GB，320 GB硬盤(pán)，1 000 Mbit/s以太網(wǎng)，用Hadoop 2.6.4和Spark 2.0塔建Spark on Yarn的集群環(huán)境[13]，算法由Python實(shí)現(xiàn)。實(shí)驗(yàn)所選擇的數(shù)據(jù)集為UC Irvine Machine Learning Repository中的Adult Data Set 數(shù)據(jù)集（記錄數(shù)為48 842，屬性數(shù)為14），根據(jù)數(shù)據(jù)集的已知分類(lèi)結(jié)果，實(shí)驗(yàn)中聚類(lèi)中心數(shù)優(yōu)化為6，迭代閾值設(shè)置為1。實(shí)驗(yàn)部分從運(yùn)行效率及隱私保護(hù)處理后輸出結(jié)果可用性方面與基于 MapReduce的 DP k-means算法[7]進(jìn)行對(duì)比測(cè)試。

4.1 算法效率分析

本文采用加速比（speedup）來(lái)測(cè)試算法的并行效率，其中，Ts為單機(jī)運(yùn)行時(shí)間，Tc為算法的集群執(zhí)行耗時(shí)。

本文算法與對(duì)比算法的加速比結(jié)果如表1所示。

表1 加速比實(shí)驗(yàn)結(jié)果

由表1可知，本文算法加速比明顯優(yōu)于對(duì)比算法[7]，而且隨著節(jié)點(diǎn)數(shù)量增大而增大，雖然算法的加速比并沒(méi)有按線性遞增，但也驗(yàn)證了Spark內(nèi)存計(jì)算模式在迭代運(yùn)算效率方面高于MapReduce框架。

4.2 算法聚類(lèi)結(jié)果可用性分析

本文采用的聚類(lèi)可行性指標(biāo)為準(zhǔn)確率與召回率的加權(quán)綜合，表達(dá)式為

其中，F(xiàn)i為準(zhǔn)確率和召回率的加權(quán)調(diào)和平均值，|Ui|為第i個(gè)參考標(biāo)準(zhǔn)的聚類(lèi)集合，N為記錄集記錄的總量。本文用 Favailable來(lái)衡量聚類(lèi)結(jié)果可用性，衡量算法得到的聚類(lèi)結(jié)果與參考結(jié)果的相似程度。當(dāng)隱私預(yù)算改變時(shí)，實(shí)驗(yàn)聚類(lèi)結(jié)果可用性情況如圖4所示。

由圖4可知，當(dāng)隱私預(yù)算ε在0～15之間取值時(shí)，聚類(lèi)結(jié)果可用性屬于[0.3,1.0]。當(dāng)隱私預(yù)算水平較低時(shí)，聚類(lèi)結(jié)果可用性與其成很強(qiáng)的正相關(guān)，當(dāng)ε達(dá)到一定程度時(shí)，可用性趨于平緩，這也間接驗(yàn)證了ε對(duì)隱私性和可用性的平衡作用。

圖4 聚類(lèi)可用性隨ε變化情況

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

本文利用Spark并行內(nèi)存計(jì)算技術(shù)實(shí)現(xiàn)了支持差分隱私的改進(jìn)k-means算法，改進(jìn)算法優(yōu)化算法優(yōu)化初始聚類(lèi)中心，結(jié)合 Laplace機(jī)制對(duì)聚類(lèi)過(guò)程中最關(guān)鍵的隱私信息進(jìn)行噪聲擾動(dòng)，實(shí)現(xiàn)了ε-差分隱私。同時(shí)，在運(yùn)行效率和聚類(lèi)結(jié)果可用性方面，改進(jìn)算法性能明顯優(yōu)于傳統(tǒng)基于MapReduce框架的聚類(lèi)算法。今后研究工作將主要集中在保證隱私保護(hù)水平的前提下，通過(guò)高效的保護(hù)機(jī)制來(lái)減少噪聲的添加以降低算法復(fù)雜度。另外，將群體智能優(yōu)化算法融入Spark大數(shù)據(jù)計(jì)算框架，也具有廣闊的研究空間。

[1] 方濱興. 從層次角度看網(wǎng)絡(luò)空間安全技術(shù)的覆蓋領(lǐng)域[J]. 網(wǎng)絡(luò)與信息安全學(xué)報(bào)，2015, 1(1):1-6. FANG B X. A hierarchy model on the research fields of cyberspace security technology[J]. Chinese Journal of Network and Information Security, 2015, 1(1):1-6.

[2] 方濱興, 賈焰, 李?lèi)?ài)平, 等. 大數(shù)據(jù)隱私保護(hù)技術(shù)綜述[J]. 大數(shù)據(jù), 2016(1): 1-18. FANG B X, JIA Y, LI A P, et al. A survey of large data privacy pro-

tection technology [J]. Big Data, 2016, (1):1-18.

[3] SANJAY B, ARYYA G. A Wavelet-based approach to preserve privacy for classification mining[J]. Decision Sciences, 2006, 37(4): 623-643.

[4] CIHAN K, HUSEYIN P. Privacy-preserving naive Bayesian classifier-based recommendations on distributed data[J]. Computational Intelligence, 2015, 31 (1): 47-69.

[5] 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. 2010:297-312.

[6] 楊紹禹, 王世卿. MapReduce模型下數(shù)據(jù)隱私保護(hù)機(jī)制研究[J].計(jì)算機(jī)科學(xué), 2012, 39(12): 153-157. YANG S Y, WANG S Q. Research on the mechanism of data privacy protection in the MapReduce model[J]. Computer Science, 2012, 39 (12): 153-157.

[7] 李洪成, 吳曉平, 陳燕. MapReduce框架下支持差分隱私保護(hù)的k-means聚類(lèi)方法[J]. 通信學(xué)報(bào), 2016, 37(2): 124-130. LI H C, WU X P, CHEN Y. K-means clustering method for differential privacy protection under the framework of MapReduce[J]. Journal on Communications, 2016, 37 (2): 124-130.

[8] DWORK C. A firm foundation for private data analysis[J]. Communications of the ACM, 2011, 54(1):86-95.

[9] DWORK C. Differential privacy[C]//The 33rd International Colloquium on Automata, Languages and Programming. 2006: 1-12.

[10] 熊平, 朱天清, 王曉峰. 差分隱私保護(hù)及其應(yīng)用[J]. 計(jì)算機(jī)學(xué)報(bào), 2014, 37(1): 101-122. XIONG P, ZHU T Q, WANG X F. Differential privacy protection and its application [J]. Journal of Computer Science, 2014, 37(1): 101-122.

[11] 丁麗萍, 盧國(guó)慶. 面向頻繁模式挖掘的差分隱私保護(hù)研究綜述[J]. 通信學(xué)報(bào), 2014, 35(10): 200-209. DING L P, LU G Q. A survey of differential privacy protection for frequent pattern mining[J]. Journal on Communications, 2014, 35 (10): 200-209.

[12] 張嘯劍, 孟小峰. 面向數(shù)據(jù)發(fā)布和分析的差分隱私保護(hù)[J]. 計(jì)算機(jī)學(xué)報(bào), 2014, 37(4): 927-949. MENG X F, ZHANG X J. Differential privacy preserving data publishing and analysis[J]. Journal of Computers, 2014, 37(4): 927-949.

[13] 王保義, 王冬陽(yáng), 張少敏. 基于Spark和IPPSO_LSSVM的短期分布式電力負(fù)荷預(yù)測(cè)算法[J]. 電力自動(dòng)化設(shè)備, 2016, 36(1): 117-122. WANG B Y, WANG D Y, ZHANG S M. Short term distributed load forecasting algorithm based on Spark and IPPSO_LSSVM[J]. Electric Power Automation Equipment, 2016, 36(1): 117-122.

高志強(qiáng)（1989-），男，河北故城人，武警工程大學(xué)博士生，主要研究方向?yàn)榇髷?shù)據(jù)隱私保護(hù)、群體智能優(yōu)化算法。

李慶鵬（1992-），男，山東濟(jì)南人，武警工程大學(xué)碩士生，主要研究方向?yàn)榇髷?shù)據(jù)隱私保護(hù)、數(shù)據(jù)挖掘與機(jī)器學(xué)習(xí)。

胡人遠(yuǎn)（1992-），男，浙江臺(tái)州人，武警工程大學(xué)碩士生，主要研究方向?yàn)樵朴?jì)算數(shù)據(jù)存儲(chǔ)、元數(shù)據(jù)管理、同態(tài)加密算法。

Clustering algorithm preserving differential privacy in the framework of Spark

GAO Zhi-qiang, LI Qing-peng, HU Ren-yuan
(Department of Information Engineering, University of PAP, Xi’an 710086, China)

Aimed at the problem that traditional methods fail to deal with malicious attacks with arbitrary background knowledge during the process of massive data clustering analysis, an improved clustering algorithm，especially designed for preserving differential privacy, under the framework of Spark was proposed. Furthermore, it’s theoretically proved to meet the standard of ε-differential privacy in the framework of Spark platform. Finally, experimental results show that guaranteeing the availability of proposed clustering algorithm, the improved algorithm has an advantage over privacy protection and satisfaction in the aspect of time as well as efficiency. Most importantly, the proposed algorithm shows a good application prospect in the analysis of data clustering preserving privacy protection and data security.

Spark, differential privacy, clustering algorithm, data mining, big data analysis

TP301

A

10.11959/j.issn.2096-109x.2016.00087

2016-05-17；

2016-06-26。通信作者：高志強(qiáng)，1090398464@qq.com

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61309008）；陜西省自然科學(xué)基金資助項(xiàng)目（No.2014JQ8049）

Foundation Items: The National Natural Science Foundation of China (No.61309008), The Natural Science Foundation of Shaanxi Province (No.2014JQ8049)