一種改進的基于差分隱私的k-means聚類算法

初廣輝 王曉利

摘 要：聚類分析是數據挖掘和機器學習的一個重要分支，應用范圍廣，但在聚類分析過程中大量敏感信息的泄露對用戶構成威脅。因此，在聚類分析過程中實現隱私保護至關重要。傳統基于差分隱私（DP）的k-means聚類算法由于存在盲目選擇初始中心點、對異常點敏感度較高等問題，導致在保護數據隱私時，出現聚類可用性較低的情況。針對該問題提出一種改進的基于差分隱私保護的（IDP）k-means聚類算法以提高聚類可用性，并進行理論分析和對比實驗。理論分析表明，該算法滿足ε-差分隱私;仿真實驗結果表明，在同一隱私預算下，k-means算法改進后在聚類可用性上優于其它差分隱私k-means聚類算法，在同一數據集與同一隱私參數下，改進k-means算法在數據可用性方面比傳統算法提高了將近5個百分點。

關鍵詞：差分隱私 ;k-means聚類; 隱私保護

DOI：10. 11907/rjdk. 191756 開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP312 文獻標識碼：A 文章編號：1672-7800（2019）008-0071-04

An Improved k-means Clustering Algorithm Based on Differential Privacy

CHU Guang-hui， WANG Xiao-li

（College of Computer Science and Engineering， Shandong University of Science and Technology， Qingdao 266590， China）

Abstract： Clustering analysis is a outstanding branch in data mining and machine learning， which has a wide range of applications， but it is scary to users against an ocean of sensitive information leakage in the process of clustering analysis. Therefore， how to achieve clustering analysis privacy protection is crucial. Generally， the traditional k-means clustering algorithm based on differential privacy（DP） has the problem of high sensitivity to abnormal points due to the existence of initial center blind choice， resulting in data privacy protection and low the cluster availability. In order to solve above problems， this paper proposes an improved DPk-means clustering algorithm to improve the availability. Meanwhile， we have carried on the theoretical analysis and experiments. Theoretical analysis indicates that the improved k-means algorithm is superior to other clustering algorithms under the same privacy budget. Under the same privacy parameters of the same data set， in terms of data availability， the algorithm is nearly five percentage points higher than the traditional algorithm.

Key Words： differential privacy; k-means clustering; privacy protection

作者簡介：初廣輝（1994-），男，山東科技大學計算機科學與工程學院碩士研究生，研究方向為數據挖掘、隱私保護;王曉利（1994-），男，山東科技大學計算機科學與工程學院碩士研究生，研究方向為數據挖掘、圖像處理。

0 引言

隨著互聯網及信息技術的飛速發展，數據挖掘技術在一些深入的研究和應用中取得了長足進步。聚類分析作為數據挖掘中無監督學習算法的一個重要分支，在數據挖掘領域發揮著重要作用，但是在進行聚類分析過程中可能會導致用戶信息泄露。公眾對安全性日益重視，隱私保護已成為重要的焦點問題，如何在聚類分析的同時實現個人隱私保護是當前研究熱點。

傳統隱私保護技術大多基于k-匿名保護模型，但是該保護模型需要特殊的攻擊假設，如背景知識攻擊[1]和合成攻擊[2]，但是這些隱私保護算法的安全性在一定程度上存在問題。2006年，Dwork等[3-4]提出一種極其嚴格的新型隱私保護模型——差分隱私保護方法。該方法與傳統隱私保護算法不同，它不需要關心攻擊者的背景知識假設，可通過添加噪聲的方式實現隱私保護; 李楊等[5]提出DPk-means算法，通過改變初始中心點盲目選擇問題進行算法改進，提出改進的DPk-means聚類方法;傅彥銘等[6]也提出類似的DPk-means++聚類算法。以上算法只是對初始中心選擇的盲目性進行改進，但對k-means聚類算法對異常值比較敏感的問題沒有作相關處理，因此本文提出一種改進的基于差分隱私的（IDP）k-means聚類算法，該算法根據最遠距離規則選取中心點，然后通過區域密度避免異常值的干擾，在保護數據隱私的同時保證數據可用性。

3 實驗結果與分析

3.1 實驗環境與數據集

為了檢測本文算法有效性，必須從以下兩個方面考慮問題，第一方面是隱私保護程度，其可通過設置[ε]值進行調節;另一方面是聚類算法的高可用性，其可通過F-measure的值獲得。

本文使用Python3.6語言，在Pycharm應用平臺上，在具有4 GB RAM的Pentium（R）Dual-Core CPU 3.3 GHz上進行一系列實驗。操作系統為Windows 7。為了證明本文算法的有效性，使用DPk-menas、DPk-means++作為對比算法在3個數據集上運行，然后對結果進行評估，本文數據集可以在http：//archive.ics.uci.edu/ml/datasets.html上獲取，具體信息如表1所示。

表1 數據集信息

首先對數據進行預處理和規范化，數據規范化主要有3個方法：數據歸一化處理、數據標準化處理、數據中心化處理，本文采用歸一化方法[19]進行數據規范化，將3個數據集的所有數據均映射到（0，1）之間的小數中。

[x=x-minAmaxA-minA]? ? ? ?（6）

其中[x]表示數據集中的任意點，[maxA和minA]分別代表屬性A列中的最大值與最小值，最后結果[x∈（0，1）]。

3.2 評價指標

F-measure[20]是對查準率與查全率的綜合評價指標，也是衡量聚類效果的標準，可對兩個聚類效果相似性進行評價。 F-measure值取值范圍是[0，1]，取值越大，說明兩個算法相似性越大，即差分隱私保護算法添加的噪聲對聚類可用性影響較小。

[Ci]表示利用OTPK-means算法進行聚類的結果，[Cj]表示利用DP-OTPK-means算法進行聚類的結果。其中[Xi]表示[Ci]的任意聚簇，[Yj]表示[Cj]的任意聚簇，[nij=Xi∩Xj]，[T]為數據集的樣本個數，按式（7）-式（9）計算[F（Cj）]既可得到F-measure的結果。

[Recall（Xi，Yj）=nijXi]? ? ? （7）

[Precision（Xi，Yj）=nijYi]? ?（8）

[F（Xi，Yj）=2×Recall（Xi，Yj）×Precision（Xi，Yj）Recall（Xi，Yj）+Precision（Xi，Yj）]? （8）

[F（Cj）=Xi∈cXiTmaxYj∈CjF（Xi，Yj）]? ? （9）

3.3 實驗結果分析

對3個數據集分別用DPk-means算法、DPk-means++算法、本文算法進行實驗，求取F-measure，為了避免實驗結果的偶然性，本文分別進行20次實驗，求取20次實驗結果的平均值作為實驗總結果。

從圖1-圖3可以看出，在同一隱私參數[ε]下，本文算法具有更高的可用性，在同一數據集下，伴隨著隱私參數[ε]的不斷增大，F-measure也在不斷增大，說明當[ε]增大，加入的Laplace噪聲隨之減少，聚類可用性便增大。

圖1 Iris數據集實驗結果

圖2 Wine數據集實驗結果

圖3 Gamma數據集實驗結果

4 結語

本文首先描述了k-means聚類算法在差分隱私中的應用，然后在DPk-means算法基礎上加以改進，解決了DPk-means算法對異常值敏感和初始化中心隨機選擇的問題。首先本文算法根據最遠歐式距離選取初始中心點，由于異常點往往分布在數據點邊緣地帶，為了避免選取到異常值，本文采用區域密度進行篩選，以此提高聚類可用性，并在仿真試驗上與DPk-means算法和DPk-means++算法進行比較，結果顯示，本文算法在可用性方面優于以上兩種算法。在未來研究中，可使用不同的策略進行異常點檢測，對本文算法作進一步優化，以便在更多領域進行探索。

參考文獻：

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

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

[3] BLUM A，DWORK C，MCSHERRY F，et al. Practical privacy： the SULQ framework[C].? Twenty-fourth ACM Sigmod-sigact-sigart Symposium on Principles of Database Systems， 2005.

[4] DWORK C. Differential privacy[C]. Venice： International Colloquium on Automata， Languages & Programming，2006.

[5] 李楊，郝志峰，溫雯，等. 差分隱私保護k-means聚類方法研究[J]. 計算機科學，2013，40（3）：287-290.

[6] 傅彥銘，李振鐸. 基于拉普拉斯機制的差分隱私保護k-means++聚類算法研究[J]. 信息網絡安全，2019（2）：43-52.

[7] SWEENEY L. k-ANONYMITY[J]. International Journal of Uncertainty，Fuzziness and Knowledge-Based Systems，2008，10（5）：557-570.

[8] 劉海，李興華，雒彬，等. 基于區塊鏈的分布式K匿名位置隱私保護方案[J]. 計算機學報，2019（5）：942-960.

[9] 曹敏姿，張琳琳，畢雪華，等. 個性化（α，l）-多樣性k-匿名隱私保護模型[J]. 計算機科學，2018，45（11）：180-186.

[10] 王濤春，劉盈，金鑫，等. 群智感知中基于k-匿名的位置及數據隱私保護方法研究[J]. 通信學報，2018，39（S1）：170-178.

[11] 楊升森. 基于空間位置的K-匿名隱私保護機制研究[J]. 現代信息科技，2018，2（8）：160-161.

[12] 陳家明，王麗，肖亞飛，等.? k-匿名機制下查詢隱私的一種度量方法[J]. 中國科學技術大學學報，2018，48（6）：512-518.

[13] 汪小寒，羅永龍，江葉峰，等. 基于KD樹最優投影劃分的k匿名算法[J]. 南京大學學報：自然科學，2016，52（6）：1050-1064.

[14] 吳偉民，黃煥坤. 基于差分隱私保護的DP-DBScan聚類算法研究[J]. 計算機工程與科學，2015，37（4）：830-834.

[15] 王紅，葛麗娜，王蘇青，等. 基于OPTICS聚類的差分隱私保護算法的改進[J]. 計算機應用，2018，38（1）：73-78.

[16] DWORK C. Differential privacy： a survey of results[C]. Berlin： International Conference on Theory and Applications of Models of Computation， 2008.

[17] DWORK C，MCSHERRY F，NISSIM K，et al. Calibrating noise to sensitivity in private data analysis[C]. Proceedings of the 3rd Theory Cryptograph Conference， 2006：265-284.

[18] AGGARWAL C C. Outlier analysis[M]. New York： Springer Publishing， 2013.

[19] VISALAKSHI N K， THANGAVEL K. Impact of normalization in distributed k-means clustering[J]. International Journal of Soft Computing， 4（4）：168-172.

[20] JIANG H， YI S， LI J， et al. Ant clustering algorithm with k-harmonic means clustering[J]. Expert Systems with Applications， 2010，37（12）：8679-8684.

（責任編輯：江 艷）