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

馬哲 鹿方凱

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

關鍵詞：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 引言

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

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

1 隱私保護研究現狀

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

1.1 基于數據加密的隱私保護技術

1.1.1 對稱加密算法技術

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

1.1.2 非對稱加密算法技術

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

1.2 基于限制發布的隱私保護技術

1.2.1 K-匿名技術

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

1.2.2 L-diversity技術

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

1.3 基于數據失真的隱私保護技術

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

3 實現方法

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

4 實驗結果

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

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

5 結語

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

參考文獻：

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

[2] 閆蒲.互聯網社交大數據下行為研究的機遇與挑戰[J].中國統計，2016（3）：15-17.

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

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

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

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

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

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

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

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

[11] 周水庚，李豐，陶宇飛，等.面向數據庫應用的隱私保護研究綜述[J].計算機學報，2009，32（5）：847-861.

[12] SWEENEY L.k-anonymity：A model for protecting privacy[J].International Journal of Uncertainty，Fuzziness 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，Fuzziness 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.

（責任編輯：杜能鋼）