黃保華 程琪 袁鴻 黃丕榮

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

關鍵詞：差分隱私;K-means聚類;隱私預算;隱私保護;數據挖掘

中圖分類號： TP391 ? ? ? ? ?文獻標識碼：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 引言

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

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

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

2 相關定義與理論基礎

2.1 差分隱私

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

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

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

2.2 DPK-means聚類算法

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

DPK-means聚類算法通過引入噪聲的方法解決K-means算法中存在的隱私安全問題。通過在更新簇質點時，向簇中的數據點的坐標和和數據點個數加入一定量的噪聲達到隱私保護目的。差分隱私DPK-means聚類算法步驟分為四步。

（1）從待聚類的數據集中隨機選取k個點作為初始中心點。

（2）計算數據集中的點與k個中心點的歐氏距離，并將數據點歸類到距離最近的初始中心點的簇中。

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

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

3 差分隱私預算分配方案

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

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

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

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

3.1 DPK-means聚類算法隱私預算分配方案

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

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

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

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

（3）將剩余的預算εremain=ε-εm×Tmax，進行Tmax/2次三分法，即每次取剩余預算的三分之一，加入到前Tmax/2項中。

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

本方案的具體細節(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]對大數據進行K-means聚類指出，K-means算法中給定的迭代次數的設置要隨著數據的增大，數據維度的增加而增加。因此，通過對圖2示例的數據維度增加1倍，迭代次數也相應增加1倍，再計算隱私預算分配序列，如圖3所示。

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

3.2 安全性分析

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

4 實驗及分析

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

4.1實驗評價標準

4.2 實驗結果與分析

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

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

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

5 結束語

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

基金項目：

國家自然科學基金項目（項目編號：61962005）。

參考文獻

[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] 李楊，郝志峰，溫雯，等.差分隱私保護K-means聚類方法研究[J].計算機科學， 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.