Spark框架下保護數據差分隱私的遺傳聚類算法

張玉婷

摘要：針對分布式計算框架下海量數據聚類分析過程中的數據隱私泄露問題，提出了一種Spark下支持差分隱私保護的遺傳k-means聚類算法。首先利用遺傳算法實現對k-means聚類方案的全局尋優，提高算法的準確率；并采用種群遷移策略將遺傳k-means算法部署于Spark框架中，實現基于內存讀寫的分布式聚類；然后利用差分隱私保護的Laplace機制在Spark每輪迭代的mapvalues算子中，對各聚簇中記錄數量num和聚簇中各記錄之和sum上添加隨機噪聲。根據差分隱私保護的性質，通過理論分析證明了算法達到ε-差分隱私保護要求。最后實驗分析表明了算法在Spark框架下的時效性高于MapReduce框架，其運行時間主要受迭代次數的影響，并且得出了使算法隱私性和準確性達到平衡的最優隱私保護預算取值。

關鍵詞：數據分析；k-means聚類；Spark框架；差分隱私；遺傳算法

中圖分類號：TP309.7 文獻標識碼：A 文章編號：1009-3044（2019）04-0198-03

1 引言

在大數據時代，數據挖掘技術得到了廣泛的應用，聚類分析作為一種常用的無監督數據挖掘技術，可以將相近的數據劃分到同一個類簇中，在網絡入侵檢測、目標識別等領域應用十分廣泛。k-means算法由于運算速度較快，實現原理簡單，所以成為應用領域最廣泛的聚類分析算法之一[1]。

本文提出一種Spark框架下滿足差分隱私保護的遺傳k-means算法（IGKM，Improved Genetic K-Means），利用遺傳算法解決k-means算法容易陷入局部最優的問題，利用基于內存計算的Spark分布式框架，利用Laplace機制實現差分隱私保護，為應對任意背景知識惡意分析的高效聚類分析提供了一種解決方案。

2 差分隱私保護基礎

差分隱私方法能夠解決任意背景知識下非法分析的問題[2]。

3 Spark框架下的DP-IGKM算法

Spark下的DP-IGKM算法實現目的是在Spark分布式框架下，當數據中的某一條記錄改變時，聚簇的中心點和記錄總數的變化情況不會暴露數據隱私。

3.1 IGKM算法設計

Step1：種群初始化：用聚簇中心的特征取值對染色體編碼。具體方法如圖1。

NK為聚簇數量，vki為第k個聚簇中心點的第i個特征取值（k[∈][1， NK]）。隨機選擇樣本集中的樣本作為聚簇中心，重復M次，使用于進化的種群規模達到M。

Step2：k-means聚類

k-means聚類具體分為兩個步驟：①計算各條記錄與聚簇中心點間的距離關系，將各記錄分配到具體它最近的中心點所在的聚簇中；②對于新形成的聚簇，計算聚簇中各記錄中各維特征的平均值，形成新的聚簇中心。

Step3：遺傳操作

遺傳操作包括選擇操作、雜交操作和變異操作。

Step4：循環終止準則設定

當算法當前的循環次數為預先設定的最高次數時，循環終止。否則，重復Step1～Step3。

3.2 Spark框架下的IGKM算法設計

采用基于內存的分布式計算框架Spark。在基于Spark的IGKM算法中，本質是利用RDD中的各Partition存儲子種群，然后在子種群內進行染色體的更新。

Spark框架下的IGKM算法流程如圖2所示。

圖2中各算子所實現的具體操作如下。

（1）textFile算子：從分布式存儲框架HDFS中讀取編碼后的染色體數據文件，每個染色體代表一個聚類方案。

（2）partitionBy算子：將RDD中的數據重新分區成QS個新的Partition，每個Partition存放一個子種群中的染色體數據。

（3）mapValues算子：對各Partition中的染色體數據逐條進行操作。

（4）groupBy算子：用key作為染色體所屬于的子種群標識，形成P個新的Partition。

（5）mapPartitions算子：完成選擇、雜交和變異等遺傳操作。

（6）cache算子：將數據緩存到內存，供迭代運算使用。

（7）reduceByKeyLocally算子：選出適應度最高的染色體。

3.3 Spark框架下的DP-IGKM算法設計

Spark中的mapValues算子的操作如下：

（1）在第一輪迭代中，在染色體內部進行聚類中心初始化。

將NR條記錄u1，…，uNR平均分成NK個子集G1，…，GNK，集合Gk中的記錄數|Gk|≤ceil（NR/NK），ceil（）為向上取整函數。計算Gk中記錄的數量num0k和Gk中各記錄的特征向量之和sum0k，分別對num0k和sum0k加入隨機噪聲得到num0k' 和sum0k'，計算v0k'=sum0k' / num0k'，v0k'即為初始聚類中心點。

（2）在后續的迭代中，通過均值聚類完成聚類中心的更新。

3.4 算法隱私性分析

5 結語

本文在Spark分布式平臺上設計了滿足差分隱私保護的遺傳k-means算法，利用染色體表示一種聚類方案，將多條染色體劃分到Spark框架下的各個分布式資源中分別進行進化，并利用種群遷移策略實現遺傳聚類的全局優化，最后通過隨機噪聲添加使算法滿足差分隱私保護。

參考文獻：

[1] 唐成華，劉鵬程，湯申生，等.基于特征選擇的模糊聚類異常入侵行為檢測[J].計算機研究與發展，2015，52（3）：718-728.

[2] Sarat K C，Bhogeswar B.On analysis of time-series data with preserved privacy[J].Innovations in Systems and Software Engineering，2015，11（3）：155-165.

[3] 鄧詩卓，姚繼濤，王波濤，等.PCPIR-V：基于Spark的并行隱私保護近鄰查詢算法[J].網絡與信息安全學報，2016，2（5）：64-76.

[4] 宋健，許國艷，夭榮朋.基于差分隱私的數據匿名化隱私保護方法[J].計算機應用，2016，36（10）：2753-2757.

[5] 何賢芒，王曉陽，陳華輝，等.差分隱私保護參數ε的選取研究[J].通信學報，2015，36（12）：124-130.

【通聯編輯：代影】