一種差分隱私K-means聚類算法的隱私預(yù)算分配方案

黃保華 程琪 袁鴻 黃丕榮

摘 ? 要：差分隱私K-means聚類算法因其能很好地兼顧數(shù)據(jù)可用性和數(shù)據(jù)隱私安全，而得到了廣泛地關(guān)注和研究。目前，在許多對差分隱私K-means聚類算法的研究中，都從K-means聚類算法的初始中心點(diǎn)的選擇上做改進(jìn)來提高數(shù)據(jù)的可用性，而很少關(guān)注隱私預(yù)算的分配問題對聚類結(jié)果帶來的影響。傳統(tǒng)的隱私預(yù)算分配方法可能在K-means算法后期的迭代更新質(zhì)心的過程中引入大量的噪聲而造成數(shù)據(jù)聚類效果差的問題。為了解決這個問題，提出一種結(jié)合三分法和等差數(shù)列的隱私預(yù)算分配方案。該方法在差分隱私K-means聚類算法中，保證每次迭代更新質(zhì)心的過程中引入的噪聲不會引起質(zhì)心變形，且前期使用三分法分配較大的預(yù)算，而在后期使用等差遞減的方式，分配隱私預(yù)算使隱私預(yù)算能在設(shè)定的迭代次數(shù)中用盡。實(shí)驗(yàn)證明，該方法在相同條件下能提高差分隱私K-means聚類算法的可用性。

關(guān)鍵詞：差分隱私;K-means聚類;隱私預(yù)算;隱私保護(hù);數(shù)據(jù)挖掘

中圖分類號： TP391 ? ? ? ? ?文獻(xiàn)標(biāo)識碼：A

Abstract： Differential privacy K-means clustering algorithm has received extensive attention and research because it can balance data availability and data privacy security. At present， in many researches on the differential privacy K-means clustering algorithm， the improvement is made from the selection of the initial center point of the K-means clustering algorithm to improve the availability of data， but little attention is paid to the impact of the distribution of privacy budget on the clustering results. The traditional privacy budget allocation method may introduce a lot of noise in the later iteration of K-means algorithm， resulting in poor clustering effect. In order to solve this problem， a privacy budget allocation scheme is proposed， which combines the trisection method and the equal difference sequence. In the K-means clustering algorithm of differential privacy， this method ensures that the noise introduced in the process of updating the centroid of each iteration will not cause the deformation of the centroid. In the early stage， the three-dimensional method is used to allocate a larger budget， while in the later stage， the equal difference decreasing method is used to allocate the privacy budget so that the privacy budget can be exhausted in the set number of iterations. Experiments show that this method can improve the availability of differential privacy K-means clustering algorithm under the same conditions.

Key words： differential privacy; K-means clustering; privacy budget; privacy protection; data mining

1 引言

在大數(shù)據(jù)時代，數(shù)據(jù)挖掘成為備受人們關(guān)注的熱點(diǎn)，K-means聚類算法作為一種簡便易用的數(shù)據(jù)挖掘[1]技術(shù)，受到了廣泛地關(guān)注。然而，K-means聚類算法需要不斷更新質(zhì)心，使用K-means聚類算法可能會泄露數(shù)據(jù)擁有者的隱私。因此，很多學(xué)者將信息保護(hù)技術(shù)引入到K-means聚類算法中來。由于差分隱私具備一些傳統(tǒng)信息保護(hù)技術(shù)（k-匿名[2]、干擾[3]）沒有的特質(zhì)，如能抵御背景知識[4]攻擊和一致性[5]攻擊等，差分隱私結(jié)合K-means聚類算法成為研究的熱門。

眾多學(xué)者對差分隱私K-means（DPK-means）聚類算法進(jìn)行了研究。Blum等人[6]在2005年首次提出了差分隱私K-means算法，并部署在SuLQ平臺將其實(shí)現(xiàn)。但是，該方法存在查詢函數(shù)敏感、聚類效果不佳等問題。Nissim等人[7]從DPK-means算法的初始中心點(diǎn)選擇上進(jìn)行優(yōu)化，在一定程度上提升了聚類效果。李楊等人[8]將原始數(shù)據(jù)集分成k個子集，再從子集中選擇中心點(diǎn)進(jìn)行聚類，增強(qiáng)了數(shù)據(jù)的可用性。Yu等人[9]考慮了數(shù)據(jù)集中異常值的影響，采用計(jì)算數(shù)據(jù)點(diǎn)密度的方法剔除異常值再進(jìn)行DPK-means聚類。Ren等人[10]通過重復(fù)執(zhí)行DPK-means算法得到優(yōu)質(zhì)的初始中心點(diǎn)來提升聚類效果。許多研究都從DPK-means算法的初始中心點(diǎn)選取上改進(jìn)來提升聚類效果，但是隱私預(yù)算是否合理分配也對聚類結(jié)果有著重要的影響。Dwork[11]在文獻(xiàn)[6]的基礎(chǔ)上，對DPK-means算法進(jìn)行了詳盡地分析，并提出了兩種差分隱私預(yù)算因子的分配方式。Su等人[12]在對差分隱私聚類算法的研究中，使用均方差的方法，得到了聚類算法每次迭代需要分配隱私預(yù)算的最小值，保證質(zhì)心不會因?yàn)榧尤朐肼暥冃?。Fan等人[13]利用DPK-means算法中隱私預(yù)算分配的最小值，提出了一個等差遞減序列作為隱私預(yù)算分配序列，保證質(zhì)心不會因?yàn)樵肼暭尤攵冃?。但通過觀察，在DPK-means算法的前期迭代中，分配到的隱私預(yù)算并不太大，會一定程度影響算法前期迭代的效果。

為了解決DPK-means聚類算法中隱私預(yù)算的分配方法不好而導(dǎo)致聚類效果不佳的問題，提出一種新的DPK-means隱私預(yù)算分配方案。該方案在DPK-means聚類算法中，先給每一次迭代分配需要的最小隱私預(yù)算值，保證每次迭代質(zhì)心不變形;在剩余的預(yù)算中，前期迭代使用三分法分配隱私預(yù)算，使得前期的迭代更新能更快地收斂;在后期使用等差數(shù)列方法分配，使隱私預(yù)算能在設(shè)定的迭代次數(shù)中用盡。實(shí)驗(yàn)證明，該方案能在一定程度上提高聚類效果。

2 相關(guān)定義與理論基礎(chǔ)

2.1 差分隱私

差分隱私[14～17]是針對統(tǒng)計(jì)數(shù)據(jù)庫中可能造成隱私信息泄露[18]而提出一種隱私模型。差分隱私模型并不會使數(shù)據(jù)完全加密，而是通過在敏感數(shù)據(jù)加入符合某種特定分布的噪聲，使數(shù)據(jù)在一定程度上失真但卻不丟失數(shù)據(jù)的某些統(tǒng)計(jì)特性。在差分隱私模型的模型中，對統(tǒng)計(jì)數(shù)據(jù)集的查詢結(jié)果不會因?yàn)槠渲幸粭l數(shù)據(jù)的增加或刪除發(fā)生明顯的變化，因此即使在最大化攻擊者背景知識的情況下，攻擊者也無法根據(jù)已知信息推斷出數(shù)據(jù)集中的敏感信息。

定義1[14] 假設(shè)有隨機(jī)算法M，Pm是算法M所有的可能輸出的值的集合。對于任意的數(shù)據(jù)集D和D'（D和D'之間最多只相差一條信息），Sm為Pm的任意子集，如果算法M滿足：

其中，Lap（△f/ε）為服從參數(shù)為△f/ε的拉普拉斯分布的噪聲，ε的值越小，其概率密度越平均，數(shù)據(jù)所添加的噪聲量就越大，對數(shù)據(jù)的隱私保護(hù)更強(qiáng)。

2.2 DPK-means聚類算法

在K-means聚類算法中，更新質(zhì)心的過程有可能會造成隱私泄露。在更新一個簇的質(zhì)心時，需要用簇中點(diǎn)的坐標(biāo)和除以數(shù)據(jù)的個數(shù)，這等效于在數(shù)據(jù)集中查詢計(jì)數(shù)，如果直接發(fā)布更新的質(zhì)心，攻擊者則可以通過背景知識來獲取數(shù)據(jù)集中的信息。

DPK-means聚類算法通過引入噪聲的方法解決K-means算法中存在的隱私安全問題。通過在更新簇質(zhì)點(diǎn)時，向簇中的數(shù)據(jù)點(diǎn)的坐標(biāo)和和數(shù)據(jù)點(diǎn)個數(shù)加入一定量的噪聲達(dá)到隱私保護(hù)目的。差分隱私DPK-means聚類算法步驟分為四步。

（1）從待聚類的數(shù)據(jù)集中隨機(jī)選取k個點(diǎn)作為初始中心點(diǎn)。

（2）計(jì)算數(shù)據(jù)集中的點(diǎn)與k個中心點(diǎn)的歐氏距離，并將數(shù)據(jù)點(diǎn)歸類到距離最近的初始中心點(diǎn)的簇中。

（3）計(jì)算每一個簇中數(shù)據(jù)點(diǎn)到中心點(diǎn)的距離之和sum，并計(jì)算簇中的數(shù)據(jù)點(diǎn)個數(shù)num，分別向sum和num添加滿足Lap（△f/ε）分布的拉普拉斯噪聲得到sum和num，然后更新簇的中心點(diǎn)sum/num。

（4）重復(fù)步驟（2）和（3）直到誤差平方和不再發(fā)生變化或者迭代次數(shù)達(dá)到上限。

3 差分隱私預(yù)算分配方案

在差分隱私K-means算法中，尋找k個中心點(diǎn)相當(dāng)于在空間[0，1]d上進(jìn)行直方圖查詢[19]，刪除或增加一個空間中的點(diǎn)最多影響一個簇中的坐標(biāo)和，這個坐標(biāo)最多只能在d維空間中的每一維改變1，總的靈敏度改變d，對于計(jì)算數(shù)據(jù)點(diǎn)的個數(shù)，靈敏度的改變?yōu)?，因此總的靈敏度為d+1。在基于拉普拉斯機(jī)制的DPK-means算法中，加入的噪聲為Lap（d+1/ε）。如何避免ε過早用盡以及如何控制引入噪聲量的大小也是影響算法聚類效果的重要因素。

Dwork[11]針對DPK-means的隱私預(yù)算問題提出了兩種方法：（1）當(dāng)?shù)拇螖?shù)N確定時，每次迭代加入的噪聲為Lap（（d+1）N/ε）;（2）當(dāng)?shù)拇螖?shù)不確定時，采用二分法，即每次迭代時使用當(dāng)前剩余預(yù)算的一半，如第一次為Lap（2（d+1）N/ε），第二次為Lap（4（d+1）N/ε）。文獻(xiàn)[12]通過計(jì)算原始K-means算法中質(zhì)心與DPK-means算法中質(zhì)心的均方差，得到了一個數(shù)據(jù)集在差分隱私聚類算法中每一次迭代需要的隱私預(yù)算的最小值：

例如，如果一個數(shù)據(jù)集的樣本個數(shù)為N，簇的個數(shù)k為5，維度d為5，取p=0.3，設(shè)DPK-means算法的最大迭代數(shù)為10，ε為10。則該數(shù)據(jù)集的εm約為0.077，將上述均分法、二分法、等差法作比較，如圖1所示。

在二分法中，隱私預(yù)算消耗過快，當(dāng)?shù)螖?shù)到第八次時，分配的隱私預(yù)算約為0.039，已經(jīng)遠(yuǎn)小于保持質(zhì)心不變形的隱私預(yù)算最小值;而均分算法在迭代的過程都保持同一個隱私預(yù)算，并不能得到很好的聚類效果;差分序列方法是針對上述兩種傳統(tǒng)的隱私預(yù)算分配方法提出的一種方案，該方法以數(shù)據(jù)集的最小隱私預(yù)算作為等差序列的最后一項(xiàng)，保證數(shù)據(jù)集在聚類過程中添加的噪聲不會引起質(zhì)心變形，并且在聚類算法的前期迭代中也得到了相對較多的隱私預(yù)算。

3.1 DPK-means聚類算法隱私預(yù)算分配方案

K-means算法的目標(biāo)函數(shù)在前期的迭代中下降更快，對聚類影響更大，需要分配更多的隱私預(yù)算來獲得較小的噪聲。而差分序列方法中，前期分配的預(yù)算要比二分法少得多，并且聚類過程并不一定會將最大迭代次數(shù)用完，該方法在后期分配較多的隱私預(yù)算可能會造成預(yù)算浪費(fèi)。

針對以上不足，本文提出一種新的DPK-means隱私預(yù)算分配方案，保證每次隱私分配均滿足最小的隱私預(yù)算要求，同時也讓算法前期的迭代中獲得更多的隱私預(yù)算。假設(shè)一個數(shù)據(jù)集樣本為N，簇的個數(shù)為k，維度為d，DPK-means算法的最大迭代次數(shù)為Tmax，隱私預(yù)算為ε，方案的步驟分為四步。

（1）計(jì)算該樣本在DPK-means算法下的最小隱私預(yù)算εm，如果εm×Tmax>ε，則使用均分法分配預(yù)算，如果εm×Tmax<ε，則進(jìn)入步驟（2）。

（2）先給每一次迭代分配εm，保證每一次迭代質(zhì)心不變形。

（3）將剩余的預(yù)算εremain=ε-εm×Tmax，進(jìn)行Tmax/2次三分法，即每次取剩余預(yù)算的三分之一，加入到前Tmax/2項(xiàng)中。

（4）將步驟（3）中剩余的隱私預(yù)算εremain加入到后Tmax/2項(xiàng)中，并使后Tmax/2項(xiàng)為等差遞減數(shù)列，其最后一項(xiàng)為εm。通過公式（10）得到等差數(shù)列的公差d，并得到后Tmax/2項(xiàng)的預(yù)算分配序列，再結(jié)合前Tmax/2項(xiàng)，就可得到整個DPK-means差分隱私預(yù)算分配序列。

本方案的具體細(xì)節(jié)詳見算法1。

Algorithm 1 Privacy budget allocation scheme

Input： Dataset D with N tuples and d dimensions， k clusters， the privacy ε，

the maximum number of iterations T

Output： Clustering reslut C={C1，C2，...Ck}

1： Computer the minimum privacy budget εm with（6）;

2： if ε≤T×εm then

3： ?privacy budget of each iteration ← ε/T;

4： else

5： ? εrem=ε-T×εm ;

6： ? for i=1 to T/2 do

7： ? ? ?εi=1/3×εrem+εm;

8： ? ? ?εrem= εrem-1/3×εrem;

9： ? end for

10： ?Computer d with （10）;

11： ?for j =1 to T/2 do

12： ? ?εT+1-j=εm+（j-1）×d;

13： ?end for

14： ?sequence ε ={ε1，ε2，...εT}

15： end if

16： Ramdomly select k points from D;

17： t=0;

18： while The SSE not converges and t

19： ? t=t+1;

20： ? for i=1 to N do

21： ? ? ?Computer distance dij between xi and uj（1≤j≤k）;

22： ? ? ?Put xi to the nearest cluster Cj（1≤j≤k）;

23： ? end for

24： ? for j=1 to k do

25： ? ? ? ?sum=∑x∈Cjx;

26： ? ? ? ?num=|Cj|;

27： ? ? ? ?sum'=sum+Lap（（d+1）/ε）;

28： ? ? ? ?num'=num+lap（（d+1）/ε）;

29： ? ? ? ?uj'=sum'/num';

30： ? ? ? ?if uj'≠uj then

31： ? ? ? ? ? uj=uj';

32： ? ? ? ?else

33： ? ? ? ? ? keep uj unchange;

34： ? ? ? ?end if

35： ? end for

36： end while

本文再使用上述的例子來觀察本方案和等差序列方法，如圖2所示。Jain等人[20]對大數(shù)據(jù)進(jìn)行K-means聚類指出，K-means算法中給定的迭代次數(shù)的設(shè)置要隨著數(shù)據(jù)的增大，數(shù)據(jù)維度的增加而增加。因此，通過對圖2示例的數(shù)據(jù)維度增加1倍，迭代次數(shù)也相應(yīng)增加1倍，再計(jì)算隱私預(yù)算分配序列，如圖3所示。

對比圖2和圖3的隱私分配曲線，可以看出，隨著迭代次數(shù)的增加，等差序列方法的曲線會逐漸趨于平緩，而本文的方法在多維度大數(shù)據(jù)中，前期依然能提高較大的隱私預(yù)算而后期保證滿足數(shù)據(jù)隱私預(yù)算的最小值。

3.2 安全性分析

假設(shè)有數(shù)據(jù)集D1和D2，它們最多只相差一條數(shù)據(jù)，M（D1）和M（D2）表示使用本文算法的兩個輸出結(jié)果，S表示任意一種劃分聚類。假設(shè)算法滿足ε-差分隱私，則：

4 實(shí)驗(yàn)及分析

本文實(shí)驗(yàn)中，使用Python來做本文算法與二分法的DPK-means和等差數(shù)列法的DPK-means做比較。實(shí)驗(yàn)環(huán)境CPU：Intel（R） Core（TM） i5-4200U 1.60GHz;RAM：10.0GB;操作系統(tǒng)：Windows 10。實(shí)驗(yàn)的數(shù)據(jù)樣本來UCI Machine Learning Repository（http：//archive.ics.uci.edu/ml/index.php），數(shù)據(jù)集信息如表1所示。

4.1實(shí)驗(yàn)評價標(biāo)準(zhǔn)

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

本文對三個已有分類標(biāo)簽的數(shù)據(jù)集分別運(yùn)行二分法、等差法以及本文方案的DPK-means算法。首先對數(shù)據(jù)集D1-D3作數(shù)據(jù)預(yù)處理，使數(shù)據(jù)集每一維的值標(biāo)準(zhǔn)化為[0，1]，并且算出每一個數(shù)據(jù)集的最小隱私預(yù)算值，然后選擇合適的ε值，并逐步調(diào)高ε，進(jìn)行三組算法的實(shí)驗(yàn)對比，觀察不同算法的F-measure值，結(jié)果如圖4～6所示。

通過實(shí)驗(yàn)發(fā)現(xiàn)，隨著隱私預(yù)算ε的提高，F(xiàn)-measure值逐漸增大。通過分析發(fā)現(xiàn)：（1）隨著數(shù)據(jù)集的樣本數(shù)和屬性數(shù)的增大，二分法的聚類效果與另外兩種方法的差距越來越大，本文方法也在一定程度上優(yōu)于差分法;（2）在數(shù)據(jù)集樣本數(shù)和屬性數(shù)越來越多的情況下，本文方法聚類效果均比差分法聚類效果好，主要的原因是在數(shù)據(jù)樣本和維數(shù)增加的情況下，最大的迭代次數(shù)也要相應(yīng)的增大，差分法分配的預(yù)算曲線會趨于平緩，導(dǎo)致DPK-means算法前期得到的隱私預(yù)算不多，而后期可能造成隱私預(yù)算浪費(fèi)。

因此，本文的方法與其他兩種方法相比具有更好的可用性和聚類效果。

5 結(jié)束語

為解決DPK-means聚類算法中隱私預(yù)算的分配方法不好而導(dǎo)致聚類效果不佳的問題，提出一種新的DPK-means隱私預(yù)算分配方案。該方案在DPK-means聚類算法中，先給每一次迭代分配不會引起質(zhì)心變形的最小隱私預(yù)算值;在剩余的預(yù)算中，前期迭代使用三分法分配隱私預(yù)算，使得前期的迭代更新能更快地收斂;在后期使用等差數(shù)列方法分配，使隱私預(yù)算能在設(shè)定的迭代次數(shù)中用盡。實(shí)驗(yàn)證明，該方案能在一定程度上提高聚類效果。在未來的工作中，希望從DPK-means聚類算法的初始中心點(diǎn)選擇上進(jìn)行研究，進(jìn)一步提高本方案的聚類效果。

基金項(xiàng)目：

國家自然科學(xué)基金項(xiàng)目（項(xiàng)目編號：61962005）。

參考文獻(xiàn)

[1] Hand D J， Adams N M. Data Mining[J]. Wiley StatsRef： Statistics Reference Online， 2014： 1-7.

[2] Sweeney. k-anonymity： a model for protecting privacy[J]. International Journal of Uncertainty， Fuzziness and Knowledge-Based Systems， 2002， 10（05）：557-570.

[3] Lindell Y， Pinkas B. Privacy Preserving Data Mining[C]// Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology. Springer， Berlin， Heidelberg， 2000.

[4] Machanavajjhala A， Kifer D， Gehrke J， et al. L-diversity： Privacy beyond kanonymity[J].ACM Transactions on Knowledge Discovery from Data， 2006， 1（1）：3.

[5] Ganta S R， Kasiviswanathan S P， Smith A. Composition attacks and auxiliary information in data privacy[C]//Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. 2008： 265-273.

[6] Blum A， Dwork C， McSherry F， et al. Practical privacy： the SuLQ framework[C]//Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. 2005： 128-138.

[7] Nissim K， Raskhodnikova S， Smith A. Smooth sensitivity and sampling in private data analysis[C]//Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. 2007： 75-84.

[8] 李楊，郝志峰，溫雯，等.差分隱私保護(hù)K-means聚類方法研究[J].計(jì)算機(jī)科學(xué)， 2013（03）：293-296.

[9] Yu Q， Luo Y， Chen C， et al. Outlier-eliminated k-means clustering algorithm based on differential privacy preservation[J]. Applied Intelligence， 2016， 45（4）： 1179-1191.

[10] Ren J， Xiong J， Yao Z， et al. DPLK-means： A novel Differential Privacy K-means Mechanism[C]//2017 IEEE Second International Conference on Data Science in Cyberspace （DSC）. IEEE， 2017： 133-139.

[11] Dwork C. A firm foundation for private data analysis[J]. Communications of the ACM， 2011， 54（1）： 86-95.

[12] Su D， Cao J， Li N， et al. Differentially private k-means clustering[C]//Proceedings of the sixth ACM conference on data and application security and privacy. 2016： 26-37.

[13] Fan Z， Xu X. Apdpk-means： A new differential privacy clustering algorithm based on arithmetic progression privacy budget allocation[C]//2019 IEEE 21st International Conference on High Performance Computing and Communications; IEEE 17th International Conference on Smart City; IEEE 5th International Conference on Data Science and Systems （HPCC/SmartCity/DSS）. IEEE， 2019： 1737-1742.

[14] DWORK C. Differential privacy[C]//Proceedings of the 33rd International Conference on Automata，Languages and Programming-Volume Part II.Springer，Berlin，Heidelberg，2006：1-19.

[15] 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.

[16] Dwork C. The differential privacy frontier[C]//Theory of Cryptography Conference. Springer， Berlin， Heidelberg， 2009： 496-502.

[17] Dwork C. Differential privacy in new settings[C]//Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics， 2010： 174-183.

[18] DALENIUS T. Towards a methodology for statistical disclosure control[J].Statistik Tidskrift，1977，15（2）：429-444.

[19] VISWANATH P. Histogranm-based Estimation Techniques in Databases[D].Madison： University of Wisconsirr-Madison， 1997.

[20] Jain， Mugdha， Verma， Chakradhar. Adapting k-means for Clustering in Big Data[J].International Journal of Computer Applications， 2014， 101（1）：19-24.