初廣輝 王曉利

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

關(guān)鍵詞：差分隱私 ;k-means聚類; 隱私保護

DOI：10. 11907/rjdk. 191756 開放科學(xué)（資源服務(wù)）標識碼（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-），男，山東科技大學(xué)計算機科學(xué)與工程學(xué)院碩士研究生，研究方向為數(shù)據(jù)挖掘、隱私保護;王曉利（1994-），男，山東科技大學(xué)計算機科學(xué)與工程學(xué)院碩士研究生，研究方向為數(shù)據(jù)挖掘、圖像處理。

0 引言

隨著互聯(lián)網(wǎng)及信息技術(shù)的飛速發(fā)展，數(shù)據(jù)挖掘技術(shù)在一些深入的研究和應(yīng)用中取得了長足進步。聚類分析作為數(shù)據(jù)挖掘中無監(jiān)督學(xué)習(xí)算法的一個重要分支，在數(shù)據(jù)挖掘領(lǐng)域發(fā)揮著重要作用，但是在進行聚類分析過程中可能會導(dǎo)致用戶信息泄露。公眾對安全性日益重視，隱私保護已成為重要的焦點問題，如何在聚類分析的同時實現(xiàn)個人隱私保護是當前研究熱點。

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

3 實驗結(jié)果與分析

3.1 實驗環(huán)境與數(shù)據(jù)集

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

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

表1 數(shù)據(jù)集信息

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

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

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

3.2 評價指標

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

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

[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 實驗結(jié)果分析

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

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

圖1 Iris數(shù)據(jù)集實驗結(jié)果

圖2 Wine數(shù)據(jù)集實驗結(jié)果

圖3 Gamma數(shù)據(jù)集實驗結(jié)果

4 結(jié)語

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

參考文獻：

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

[2] 焦佳. 社會網(wǎng)絡(luò)數(shù)據(jù)中一種基于k-degree-l-diversity匿名的個性化隱私保護方法[J]. 現(xiàn)代計算機：專業(yè)版，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]. 計算機科學(xué)，2013，40（3）：287-290.

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

[7] SWEENEY L. k-ANONYMITY[J]. International Journal of Uncertainty，F(xiàn)uzziness and Knowledge-Based Systems，2008，10（5）：557-570.

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

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

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

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

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

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

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

[15] 王紅，葛麗娜，王蘇青，等. 基于OPTICS聚類的差分隱私保護算法的改進[J]. 計算機應(yīng)用，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.

（責任編輯：江 艷）