馬哲 鹿方凱

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

關鍵詞：k-means算法；差分隱私；隱私保護

DOIDOI：10.11907/rjdk.181386

中圖分類號：TP309

文獻標識碼：A 文章編號：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.

英文關鍵詞Key Words：k-means algorithm； differential privacy； privacy protect

0 引言

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

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

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

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

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

1.1.1 對稱加密算法技術

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

1.1.2 非對稱加密算法技術

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

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

1.2.1 K-匿名技術

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

1.2.2 L-diversity技術

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

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

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

3 實現(xiàn)方法

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

4 實驗結(jié)果

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

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

5 結(jié)語

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

參考文獻：

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

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

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

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

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

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

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

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

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

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

[11] 周水庚，李豐，陶宇飛，等.面向數(shù)據(jù)庫應用的隱私保護研究綜述[J].計算機學報，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] 李楊，溫雯，謝光強.差分隱私保護研究綜述[J].計算機應用研究，2012，29（9）：3201-3205，3211.

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

[21] 李楊，郝志峰，溫雯，謝光強.差分隱私保護k-means聚類方法研究[J].計算機科學，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.

（責任編輯：杜能鋼）