基于Spark的支持隱私保護的聚類算法

高志強，李慶鵬，胡人遠

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

基于Spark的支持隱私保護的聚類算法

高志強，李慶鵬，胡人遠

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

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

Spark；差分隱私；聚類算法；數據挖掘；大數據分析

1 引言

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

已成為研究熱點[2]。

國內外學者做了許多卓有成效的研究工作。文獻[3]提出了一種基于 Haar小波和Daub-4小波分析的數據變換方式，使經典的分類挖掘算法滿足隱私保護的要求。文獻[4]在樸素貝葉斯分類器的基礎上，提出一種滿足隱私保護的高效分布式推薦算法。文獻[5]將隱私保護機制融入 Hadoop平臺下的MapReduce分布式計算框架，實現了海量分布式數據的隱私保護算法。

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

2 差分隱私保護

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

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

圖1給出差分隱私算法的輸出結果所對應的概率密度函數。

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

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

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

定義1 查詢函數F所對應的全局敏感度[10]為

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

本文采用了可以較好地保持原有數據統計特性的 Laplace機制，使改進算法更適用于數值型聚類分析，其原理如圖2所示。

圖2 Laplace機制

Laplace機制通過向數值型數據中添加Laplace噪聲實現差分隱私保護，其具體實現如定理2。

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

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

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

性質2 設有隨機算法A和數據集D，將D分為不相交的子集D1,…,Dn，若算法A提供ε-差分隱私保護，則A在{D1,…,Dn}上的組合算法所構成的算法提供ε-差分隱私保護。

基于性質1和性質2，本文證明了改進算法DP HK-means滿足差分隱私并指導隱私預算分配過程。

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

本文算法基于Spark內存計算框架，實現了海量數據在聚類分析時，在數據集的統計信息改變任一條記錄時，具有最大背景知識的攻擊者在整個聚類過程中仍無法獲得數據隱私的功能，其對應的攻擊模型如圖3所示。

圖3 本文算法對應的攻擊模型

3.1 算法設計

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

Step1 將從 HDFS中讀取的初始數據集轉換為Spark框架下的RDD數據集，并對初始聚類中心點編碼。

Step2 Map操作。訓練初始聚類中心，獲得初始聚類中心，構成（Key，Value）鍵值對，并選擇距離最小的聚類中心，判斷記錄的聚類歸屬。

Step3 Reduce及隱私保護操作。計算各個聚類中記錄數量num及其向量和sum，并對變量sum加入Laplace噪聲擾動，重新計算相應聚類中心。

Step4 根據Key值，進行Join操作，產生新的 RDD數據集，如果本輪和上輪聚類中心向量差小于預設值，則通過SaveAsTextFile方法保存聚類結果，結束迭代；否則循環Step 2～Step 4，并將中間計算結果緩存至Cache中，進行下一輪操作。

Step5 輸出聚類結果。

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

3.2 隱私性分析

中間變量加入噪聲擾動，降低了隱私保護預算，提高了迭代效率，減少了過多噪聲對聚類效果的影響。

4 實驗與分析

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

4.1 算法效率分析

本文采用加速比（speedup）來測試算法的并行效率，其中，Ts為單機運行時間，Tc為算法的集群執行耗時。

本文算法與對比算法的加速比結果如表1所示。

表1 加速比實驗結果

由表1可知，本文算法加速比明顯優于對比算法[7]，而且隨著節點數量增大而增大，雖然算法的加速比并沒有按線性遞增，但也驗證了Spark內存計算模式在迭代運算效率方面高于MapReduce框架。

4.2 算法聚類結果可用性分析

本文采用的聚類可行性指標為準確率與召回率的加權綜合，表達式為

其中，Fi為準確率和召回率的加權調和平均值，|Ui|為第i個參考標準的聚類集合，N為記錄集記錄的總量。本文用 Favailable來衡量聚類結果可用性，衡量算法得到的聚類結果與參考結果的相似程度。當隱私預算改變時，實驗聚類結果可用性情況如圖4所示。

由圖4可知，當隱私預算ε在0～15之間取值時，聚類結果可用性屬于[0.3,1.0]。當隱私預算水平較低時，聚類結果可用性與其成很強的正相關，當ε達到一定程度時，可用性趨于平緩，這也間接驗證了ε對隱私性和可用性的平衡作用。

圖4 聚類可用性隨ε變化情況

5 結束語

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

[1] 方濱興. 從層次角度看網絡空間安全技術的覆蓋領域[J]. 網絡與信息安全學報，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] 方濱興, 賈焰, 李愛平, 等. 大數據隱私保護技術綜述[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模型下數據隱私保護機制研究[J].計算機科學, 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框架下支持差分隱私保護的k-means聚類方法[J]. 通信學報, 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] 熊平, 朱天清, 王曉峰. 差分隱私保護及其應用[J]. 計算機學報, 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] 丁麗萍, 盧國慶. 面向頻繁模式挖掘的差分隱私保護研究綜述[J]. 通信學報, 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] 張嘯劍, 孟小峰. 面向數據發布和分析的差分隱私保護[J]. 計算機學報, 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] 王保義, 王冬陽, 張少敏. 基于Spark和IPPSO_LSSVM的短期分布式電力負荷預測算法[J]. 電力自動化設備, 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.

高志強（1989-），男，河北故城人，武警工程大學博士生，主要研究方向為大數據隱私保護、群體智能優化算法。

李慶鵬（1992-），男，山東濟南人，武警工程大學碩士生，主要研究方向為大數據隱私保護、數據挖掘與機器學習。

胡人遠（1992-），男，浙江臺州人，武警工程大學碩士生，主要研究方向為云計算數據存儲、元數據管理、同態加密算法。

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。通信作者：高志強，1090398464@qq.com

國家自然科學基金資助項目（No.61309008）；陜西省自然科學基金資助項目（No.2014JQ8049）

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