基于差分隱私的RDPk—means聚類方法

馬哲 鹿方凱

摘要：為解決k-means聚類算法在聚類過程中隱私泄露風(fēng)險(xiǎn)，在滿足ε-差分隱私保護(hù)前提下，提出一種隱私保護(hù)的RDPk-means聚類方法。該方法與傳統(tǒng)隨機(jī)選取初始點(diǎn)方式不同，采取基于網(wǎng)格密度的方式選取初始聚類中心，并在UCI數(shù)據(jù)集中進(jìn)行有效性驗(yàn)證。采用543條數(shù)據(jù)生成2個(gè)聚類簇和19 020條數(shù)據(jù)生成3個(gè)聚類簇分別進(jìn)行實(shí)驗(yàn)。結(jié)果表明，該聚類方法在不同的數(shù)據(jù)規(guī)模和維數(shù)情況下可以很好地保護(hù)數(shù)據(jù)隱私，能保證聚類結(jié)果的可用性。

關(guān)鍵詞：k-means算法；差分隱私；隱私保護(hù)

DOIDOI：10.11907/rjdk.181386

中圖分類號(hào)：TP309

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2018）008-0205-03

英文摘要Abstract：In order to solve the risk of privacy leakage in the clustering process of k-means clustering algorithm，under the premise of satisfying ε-difference privacy protection，this paper proposes a privacy-preserving RDPk-means clustering method.This method is different from the traditional random selection of initial points and it is based on the grid density approach to select the initial poly Class Center to verify validity in UCI's real data set.Two experiments were performed using 543 data sets to generate 2 clusters and 19，020 data sets to generate 3 clusters.The experimental results show that the proposed clustering method can still protect data privacy with different data sizes and dimensions，and also guarantee the availability of clustering results.

英文關(guān)鍵詞Key Words：k-means algorithm； differential privacy； privacy protect

0 引言

大數(shù)據(jù)時(shí)代，隨著數(shù)據(jù)量的急劇增長(zhǎng)，全球范圍內(nèi)出現(xiàn)了對(duì)信息隱私的擔(dān)憂[1]。由于互聯(lián)網(wǎng)可以輕松地將數(shù)據(jù)自動(dòng)收集并添加到數(shù)據(jù)庫(kù)中，因此隱私問題進(jìn)一步惡化。對(duì)大量數(shù)據(jù)收集的擔(dān)憂已經(jīng)延伸到應(yīng)用于數(shù)據(jù)的分析工具。數(shù)據(jù)挖掘是當(dāng)前對(duì)數(shù)據(jù)進(jìn)行分析和處理的有效技術(shù)，可從大型數(shù)據(jù)庫(kù)中發(fā)現(xiàn)有潛在價(jià)值的信息。但與此同時(shí)，敏感信息的泄露也給用戶帶來了不可估量的損失[2-4]。因此，對(duì)聚類分析中的隱私數(shù)據(jù)進(jìn)行有效保護(hù)，成為數(shù)據(jù)隱私保護(hù)領(lǐng)域亟待解決的問題[5-6]。

針對(duì)上述問題已經(jīng)有許多隱私保護(hù)方法，如文獻(xiàn)[7-10]中描述的模型，但這些隱私保護(hù)模型需要不斷改進(jìn)以抵御新的攻擊，如背景知識(shí)攻擊[8]和合成攻擊[9]，其中一些并不能很好地解決數(shù)據(jù)可用性和隱私保護(hù)之間的平衡。因此，本文提出了一種在聚類分析中用于隱私數(shù)據(jù)保護(hù)的RDPk-means聚類算法。RDPk-means算法在k-means聚類算法的迭代過程中增加滿足特定分布的適當(dāng)隨機(jī)噪聲，使聚類結(jié)果在一定程度上失真，達(dá)到隱私保護(hù)目的，同時(shí)保證數(shù)據(jù)的可用性。

1 隱私保護(hù)研究現(xiàn)狀

當(dāng)前的隱私保護(hù)技術(shù)大致分為數(shù)據(jù)加密、限制發(fā)布和數(shù)據(jù)失真3類 [11]。數(shù)據(jù)加密是通過加密算法對(duì)數(shù)據(jù)加密，對(duì)數(shù)據(jù)進(jìn)行有效保護(hù)；限制發(fā)布主要是在發(fā)布數(shù)據(jù)前對(duì)數(shù)據(jù)提前加密；數(shù)據(jù)失真是對(duì)數(shù)據(jù)添加噪聲使數(shù)據(jù)失真，進(jìn)而對(duì)數(shù)據(jù)隱私進(jìn)行保護(hù)。

1.1 基于數(shù)據(jù)加密的隱私保護(hù)技術(shù)

1.1.1 對(duì)稱加密算法技術(shù)

對(duì)稱加密算法是最古老和使用最多的加密方法。在對(duì)稱加密算法中，解密密文的密鑰與加密明文密鑰相同。這種加密算法現(xiàn)在被廣泛使用，但是這種方法存在一定缺陷，即隨著密鑰數(shù)量的增加，用戶對(duì)密鑰的管理會(huì)變得很困難。

1.1.2 非對(duì)稱加密算法技術(shù)

與對(duì)稱加密算法不同，非對(duì)稱加密算法使用兩個(gè)密鑰：一個(gè)密鑰即私鑰，只有一個(gè)人知道，另一個(gè)密鑰即公鑰，每個(gè)人都可以使用。這兩個(gè)值在數(shù)學(xué)上相互關(guān)聯(lián)，但從一個(gè)值得出另一個(gè)值是不可能的。該方法在數(shù)字簽名和身份認(rèn)證領(lǐng)域應(yīng)用較廣，但它的缺點(diǎn)是算法復(fù)雜，數(shù)據(jù)加密效率較低。

1.2 基于限制發(fā)布的隱私保護(hù)技術(shù)

1.2.1 K-匿名技術(shù)

K-匿名[12]是一種經(jīng)典的匿名化方法，這種方法首先將所要發(fā)布的關(guān)系數(shù)據(jù)劃分為多個(gè)等價(jià)類，每個(gè)等價(jià)類必須包含不少于K條相似數(shù)據(jù)，也就是說，在等價(jià)類中，任意一條數(shù)據(jù)都無(wú)法和其它K-1條數(shù)據(jù)區(qū)分[13]，這使得滿足k-匿名的數(shù)據(jù)具有較好的隱私保護(hù)能力。但是K匿名的缺陷也很明顯，敏感屬性是等價(jià)類中的重要因素[14]，因?yàn)镵-匿名并沒有對(duì)此進(jìn)行限制，所以當(dāng)某個(gè)等價(jià)類的敏感屬性取值相同時(shí)這種技術(shù)便會(huì)失效。

1.2.2 L-diversity技術(shù)

L-diversity[15]是基于K-匿名改進(jìn)的技術(shù)，因?yàn)樵趉-匿名中雖然攻擊者無(wú)法確定某個(gè)人到底是等價(jià)類中的哪條數(shù)據(jù)，但如果等價(jià)類中某項(xiàng)敏感屬性值出現(xiàn)的頻率過高，那么攻擊者很有可能將這個(gè)人和這個(gè)屬性值聯(lián)系起來。所以L-diversity要求在同一個(gè)等價(jià)類中，某一項(xiàng)屬性值的出現(xiàn)概率不能超過1/L，這樣攻擊者就不太可能將某個(gè)人和某個(gè)敏感屬性值聯(lián)系起來。但如果數(shù)據(jù)中敏感屬性值比例過大，攻擊者仍然有可能獲得個(gè)人隱私。

1.3 基于數(shù)據(jù)失真的隱私保護(hù)技術(shù)

差分隱私[16-18]近年來被引入數(shù)據(jù)發(fā)布中的隱私保護(hù)，隱私保護(hù)模型旨在確保所有幾乎相同的輸入數(shù)據(jù)集之間的任何已發(fā)布數(shù)據(jù)具有相等概率，它保證了所有輸出對(duì)個(gè)體不敏感。除此之外，即使攻擊者擁有一定的背景知識(shí)，該模型也能使記錄的隱私性得到有效保護(hù)[19]。

3 實(shí)現(xiàn)方法

通過數(shù)據(jù)實(shí)驗(yàn)對(duì)RDPk-means算法的可用性進(jìn)行分析和說明。實(shí)驗(yàn)環(huán)境為：Inter（R） Core（TM） i3-2328M CPU@2.20GHz，8G內(nèi)存，Windows7 64位操作系統(tǒng)，實(shí)驗(yàn)使用Java語(yǔ)言實(shí)現(xiàn)，采用的IDE開發(fā)工具為Eclipse，版本為Mars.2 Release （4.5.2）。算法中用到的數(shù)據(jù)來自于UCI Knowledge Discovery Archive database，具體信息如表1所示。

4 實(shí)驗(yàn)結(jié)果

本實(shí)驗(yàn)用RDPk-means和DPk-means對(duì)每個(gè)數(shù)據(jù)集進(jìn)行聚類分析。由于添加的拉普拉斯噪聲是隨機(jī)的，所以實(shí)驗(yàn)可能會(huì)產(chǎn)生一定誤差。為減少誤差，在不同的數(shù)據(jù)集上調(diào)用RDPk-means算法30次后取CH值的平均值。CH比率越接近1，說明兩種算法聚類后的有效性越接近，結(jié)果如圖1、圖2所示。

從圖1、圖2可知，隨著ε值的不斷增大，CH的值最后也大大提高。這是因?yàn)橥ㄟ^改變初始點(diǎn)選擇，提升了聚類中心精度，從而使聚類結(jié)果的偏差變小。尤其是當(dāng)ε值較小、噪聲較大時(shí)，RDPk-means算法聚類可用性提高；當(dāng)ε值較大、添加噪聲減少時(shí)，顯示數(shù)據(jù)可用性逐漸接近原始K均值算法的聚類，這表明了RDPk-means算法的優(yōu)越性。

5 結(jié)語(yǔ)

為解決現(xiàn)有DPk-means算法中聚類結(jié)果效率不高問題，本文提出一種新的RDPk-means算法。通過對(duì)原始數(shù)據(jù)集進(jìn)行基于網(wǎng)格密度的劃分，明顯減少了異常值對(duì)結(jié)果的影響。另外，該算法通過劃分每個(gè)維度的數(shù)據(jù)生成初始聚類中心，改善了初始聚類中心的選擇及聚類效果。

參考文獻(xiàn)：

[1] 賀瑤，王文慶，薛飛.基于云計(jì)算的海量數(shù)據(jù)挖掘研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2013，23（2）：69-72.

[2] 閆蒲.互聯(lián)網(wǎng)社交大數(shù)據(jù)下行為研究的機(jī)遇與挑戰(zhàn)[J].中國(guó)統(tǒng)計(jì)，2016（3）：15-17.

[3] 劉雅輝，張鐵贏，靳小龍，等.大數(shù)據(jù)時(shí)代的個(gè)人隱私保護(hù)[J].計(jì)算機(jī)研究與發(fā)展，2015，52（1）：229-247.

[4] 王璐，孟小峰.位置大數(shù)據(jù)隱私保護(hù)研究綜述[J].軟件學(xué)報(bào)，2014，25（4）：693-712.

[5] 王保義，胡恒，張少敏.差分隱私保護(hù)下面向海量用戶的用電數(shù)據(jù)聚類分析[J].電力系統(tǒng)自動(dòng)化，2018，42（2）：121-127.

[6] 李黎明.基于網(wǎng)格的隱私保護(hù)聚類挖掘算法研究[D].福州：福州大學(xué)，2010.

[7] 闞瑩瑩，曹天杰.一種增強(qiáng)的隱私保護(hù)K-匿名模型——（α，L）多樣化K-匿名[J].計(jì)算機(jī)工程與應(yīng)用，2010，46（21）：148-151，180.

[8] 谷汪峰，饒若楠.一種基于k-anonymity模型的數(shù)據(jù)隱私保護(hù)算法[J].計(jì)算機(jī)應(yīng)用與軟件，2008（8）：65-67.

[9] 焦佳.社會(huì)網(wǎng)絡(luò)數(shù)據(jù)中一種基于k-degree-l-diversity匿名的個(gè)性化隱私保護(hù)方法[J].現(xiàn)代計(jì)算機(jī)：專業(yè)版，2016（29）：45-47，60.

[10] 張健沛，謝靜，楊靜，等.基于敏感屬性值語(yǔ)義桶分組的t-closeness隱私模型[J].計(jì)算機(jī)研究與發(fā)展，2014，51（1）：126-137.

[11] 周水庚，李豐，陶宇飛，等.面向數(shù)據(jù)庫(kù)應(yīng)用的隱私保護(hù)研究綜述[J].計(jì)算機(jī)學(xué)報(bào)，2009，32（5）：847-861.

[12] SWEENEY L.k-anonymity：A model for protecting privacy[J].International Journal of Uncertainty，F(xiàn)uzziness and Knowledge-Based Systems，2002，10（5）：557-570.

[13] SWEENEY L.Achieving k-anonymity privacy protection using generalization and suppression[J].International Journal of Uncertainty，F(xiàn)uzziness and Knowledge-Based Systems，2002，10（5）：571-588.

[14] Li N，Li T，VENKATASUBRAMANIAN S.t-closeness：privacy beyond k-anonymity and l-diversity[C].Data Engineering，2007.ICDE2007.IEEE 23rd International Conference on.IEEE，2007：106-115.

[15] MACHANAVAJJHALA A. l-diversity： Privacy beyond k-anonymity [C].Data Engineering，2006.ICDE'06.Proceedings of the 22nd International Conference on.IEEE，2006：24-24.

[16] DWORK C.Differential privacy in the 40th international colloquium on automata.Languages and Programming，2006.Dwork C.Differential privacy：a survey of results[C].International Conference on Theory and Applications of Models of Computation.Springer，Berlin，Heidelberg，2008：1-19.

[17] DWORK C，NAOR M，PITASSI T，et al.Pan-private streaming algorithms[C].ICS.2010：66-80.

[18] DWORK C.Differential privacy under continual observation[C].Proceedings of the forty-second ACM symposium on Theory of computing.ACM，2010：715-724.

[19] 李楊，溫雯，謝光強(qiáng).差分隱私保護(hù)研究綜述[J].計(jì)算機(jī)應(yīng)用研究，2012，29（9）：3201-3205，3211.

[20] DWORK C.The differential privacy frontier[J].Tcc.2009（54 44）：496-502.

[21] 李楊，郝志峰，溫雯，謝光強(qiáng).差分隱私保護(hù)k-means聚類方法研究[J].計(jì)算機(jī)科學(xué)，2013，40（3）：287-290.

[22] CALISKI T，HARABASZ J.A dendrite method for cluster analysis[J].Communications in Statistics-theory and Methods，1974，3（1）：1-27.

（責(zé)任編輯：杜能鋼）