張玉婷

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

關(guān)鍵詞：數(shù)據(jù)分析；k-means聚類；Spark框架；差分隱私；遺傳算法

中圖分類號(hào)：TP309.7 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2019）04-0198-03

1 引言

在大數(shù)據(jù)時(shí)代，數(shù)據(jù)挖掘技術(shù)得到了廣泛的應(yīng)用，聚類分析作為一種常用的無監(jiān)督數(shù)據(jù)挖掘技術(shù)，可以將相近的數(shù)據(jù)劃分到同一個(gè)類簇中，在網(wǎng)絡(luò)入侵檢測、目標(biāo)識(shí)別等領(lǐng)域應(yīng)用十分廣泛。k-means算法由于運(yùn)算速度較快，實(shí)現(xiàn)原理簡單，所以成為應(yīng)用領(lǐng)域最廣泛的聚類分析算法之一[1]。

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

2 差分隱私保護(hù)基礎(chǔ)

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

3 Spark框架下的DP-IGKM算法

Spark下的DP-IGKM算法實(shí)現(xiàn)目的是在Spark分布式框架下，當(dāng)數(shù)據(jù)中的某一條記錄改變時(shí)，聚簇的中心點(diǎn)和記錄總數(shù)的變化情況不會(huì)暴露數(shù)據(jù)隱私。

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

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

NK為聚簇?cái)?shù)量，vki為第k個(gè)聚簇中心點(diǎn)的第i個(gè)特征取值（k[∈][1， NK]）。隨機(jī)選擇樣本集中的樣本作為聚簇中心，重復(fù)M次，使用于進(jìn)化的種群規(guī)模達(dá)到M。

Step2：k-means聚類

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

Step3：遺傳操作

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

Step4：循環(huán)終止準(zhǔn)則設(shè)定

當(dāng)算法當(dāng)前的循環(huán)次數(shù)為預(yù)先設(shè)定的最高次數(shù)時(shí)，循環(huán)終止。否則，重復(fù)Step1～Step3。

3.2 Spark框架下的IGKM算法設(shè)計(jì)

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

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

圖2中各算子所實(shí)現(xiàn)的具體操作如下。

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

（2）partitionBy算子：將RDD中的數(shù)據(jù)重新分區(qū)成QS個(gè)新的Partition，每個(gè)Partition存放一個(gè)子種群中的染色體數(shù)據(jù)。

（3）mapValues算子：對(duì)各Partition中的染色體數(shù)據(jù)逐條進(jìn)行操作。

（4）groupBy算子：用key作為染色體所屬于的子種群標(biāo)識(shí)，形成P個(gè)新的Partition。

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

（6）cache算子：將數(shù)據(jù)緩存到內(nèi)存，供迭代運(yùn)算使用。

（7）reduceByKeyLocally算子：選出適應(yīng)度最高的染色體。

3.3 Spark框架下的DP-IGKM算法設(shè)計(jì)

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

（1）在第一輪迭代中，在染色體內(nèi)部進(jìn)行聚類中心初始化。

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

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

3.4 算法隱私性分析

5 結(jié)語

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

參考文獻(xiàn)：

[1] 唐成華，劉鵬程，湯申生，等.基于特征選擇的模糊聚類異常入侵行為檢測[J].計(jì)算機(jī)研究與發(fā)展，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的并行隱私保護(hù)近鄰查詢算法[J].網(wǎng)絡(luò)與信息安全學(xué)報(bào)，2016，2（5）：64-76.

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

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

【通聯(lián)編輯：代影】