一種改進(jìn)的基于差分隱私的k-means聚類算法

初廣輝 王曉利

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

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

DOI：10. 11907/rjdk. 191756 開(kāi)放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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

作者簡(jiǎn)介：初廣輝（1994-），男，山東科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院碩士研究生，研究方向?yàn)閿?shù)據(jù)挖掘、隱私保護(hù);王曉利（1994-），男，山東科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院碩士研究生，研究方向?yàn)閿?shù)據(jù)挖掘、圖像處理。

0 引言

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

3.2 評(píng)價(jià)指標(biāo)

F-measure[20]是對(duì)查準(zhǔn)率與查全率的綜合評(píng)價(jià)指標(biāo)，也是衡量聚類效果的標(biāo)準(zhǔn)，可對(duì)兩個(gè)聚類效果相似性進(jìn)行評(píng)價(jià)。 F-measure值取值范圍是[0，1]，取值越大，說(shuō)明兩個(gè)算法相似性越大，即差分隱私保護(hù)算法添加的噪聲對(duì)聚類可用性影響較小。

[Ci]表示利用OTPK-means算法進(jìn)行聚類的結(jié)果，[Cj]表示利用DP-OTPK-means算法進(jìn)行聚類的結(jié)果。其中[Xi]表示[Ci]的任意聚簇，[Yj]表示[Cj]的任意聚簇，[nij=Xi∩Xj]，[T]為數(shù)據(jù)集的樣本個(gè)數(shù)，按式（7）-式（9）計(jì)算[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 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

4 結(jié)語(yǔ)

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

參考文獻(xiàn)：

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

[2] 焦佳. 社會(huì)網(wǎng)絡(luò)數(shù)據(jù)中一種基于k-degree-l-diversity匿名的個(gè)性化隱私保護(hù)方法[J]. 現(xiàn)代計(jì)算機(jī)：專業(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] 李楊，郝志峰，溫雯，等. 差分隱私保護(hù)k-means聚類方法研究[J]. 計(jì)算機(jī)科學(xué)，2013，40（3）：287-290.

[6] 傅彥銘，李振鐸. 基于拉普拉斯機(jī)制的差分隱私保護(hù)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匿名位置隱私保護(hù)方案[J]. 計(jì)算機(jī)學(xué)報(bào)，2019（5）：942-960.

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

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

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

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

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

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

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

（責(zé)任編輯：江 艷）