基于空間動態(tài)劃分的差分隱私聚類算法

張可鏵，成衛(wèi)青

1.南京郵電大學 計算機學院，南京210023

2.東南大學 計算機網(wǎng)絡和信息集成教育部重點實驗室，南京211189

隨著計算機信息技術的不斷發(fā)展，數(shù)據(jù)庫系統(tǒng)性能日趨強大、數(shù)據(jù)存儲成本日趨降低，人們能從越來越多的途徑獲取各種信息。數(shù)據(jù)挖掘[1]是從大量信息中獲取有用知識的關鍵途徑，然而在挖掘有價值資料的過程中，個人隱私資料可能受到損害。數(shù)據(jù)發(fā)布是數(shù)據(jù)挖掘的重要應用方向，在現(xiàn)實生活中，有許多場所需要定期對外發(fā)布數(shù)據(jù)。比如，一些公司定期公布季度財務報表，醫(yī)院對外發(fā)布醫(yī)療統(tǒng)計數(shù)據(jù)等。隨著發(fā)布的數(shù)據(jù)量的增多，攻擊者可以通過多個數(shù)據(jù)表鎖定某個個體的隱私信息，導致隱私的泄漏，因此隱私保護已經(jīng)成為一個重要的問題。

目前，傳統(tǒng)匿名隱私保護模型已經(jīng)被廣泛研究。Sweeney[2]提出的k-匿名模型可以使數(shù)據(jù)表中的每一條記錄不能與其他k-1 條記錄區(qū)分開，從而使得攻擊者無法辨別隱私信息的所屬個體，保護了個人的隱私。l-多樣性（l-diversity）模型可以保證攻擊者識別出某一條隱私記錄的概率低于1/l。然而，這類隱私保護的模型并沒有一個衡量隱私水平的方法，需要不停地改進來防御新的攻擊，例如背景知識攻擊[3]和合成攻擊[4]。為了解決上述問題，2006年Dwork等人[5]提出了差分隱私模型，引起了研究熱潮。差分隱私保護技術通過添加拉普拉斯噪聲的方式保護數(shù)據(jù)，使受差分隱私保護的數(shù)據(jù)集的隱私泄漏風險控制在一個可接受的范圍內(nèi)。

差分隱私保護作為一個新興的研究熱點，它在理論和實際應用中都有很重要的價值。自Dwork 提出差分隱私保護的模型之后，又在一系列文章中不斷地完善補充差分隱私理論[6-8]。聚類算法是機器學習中的一個熱門研究方向，也是數(shù)據(jù)挖掘的重要方法。 K-Means 算法是常用的聚類方法之一，算法比較簡單并且能夠提供高速聚類，聚類效果較好。在差分隱私模型中運用聚類算法也是當下研究較多的方向[9]。差分隱私保護聚類算法的研究動機在于保持良好的聚類效果的同時能夠保護個體的隱私信息，這在現(xiàn)實生活中很常見。比如，醫(yī)院定期發(fā)布醫(yī)療統(tǒng)計數(shù)據(jù)，要求對病人的生病類型進行聚類分析，同時又不能暴露具體病人所生的疾病。

針對以上需求，Blum 等人[10]提出了差分隱私k -means 算法，做到在獲取聚類結果的同時保護數(shù)據(jù)隱私，但是聚類可用性受噪聲影響較大，并且數(shù)據(jù)分布會對聚類效果造成很大影響，結果不穩(wěn)健。李楊等人[11]提出了另一種IDPk-means 算法，改進了聚類初始中心點的選擇，使聚類效果更好，但是他們忽視了聚類過程中異常值的負面影響。Yu 等人[12]提出了一種異常檢測方法來選擇初始聚類中心，并且使用OEPT算法消除數(shù)據(jù)集中的異常值，用來預處理數(shù)據(jù)集提高聚類的效果以及可用性。但是，OEPT 算法選擇初始聚類中心的方法復雜，且在某些數(shù)據(jù)分布的情況下會使迭代收斂速度更慢，產(chǎn)生劣化。Su 等人[13]以k 均值聚類算法為例，研究了交互式方法以及非交互式方法的優(yōu)缺點，提出了一種將交互式方法和非交互式方法相結合的混合方法并應用到差分隱私中，發(fā)表了EUGk-means方法。但是該方法在數(shù)據(jù)量較為龐大的情況下，存儲桶的個數(shù)會急劇增加，導致添加的噪聲量加大，影響最終結果。在文獻[13]的研究中，無論數(shù)據(jù)分布如何，對數(shù)據(jù)進行均等間隔的分割，并創(chuàng)建存儲桶表示這些數(shù)據(jù)。然而有些不存在數(shù)據(jù)的區(qū)域也被包含進去并且添加了噪聲，這樣做無形中增加了總噪聲量，減少存儲桶的數(shù)量可以減少噪聲插入的數(shù)量但是卻不能充分表示數(shù)據(jù)的分布。Ren等人[14]將數(shù)據(jù)集隨機劃分為多個子集來獲取初始中心，但是結果受數(shù)據(jù)分布影響較大。胡闖等人[15]在傳統(tǒng)的DPk-means算法基礎上對初始中心點的選擇進行改進，將k-means++算法應用到差分隱私上。但是該方法在數(shù)據(jù)集分布不規(guī)則的情況下產(chǎn)生較差的效果。

由于以往的算法受數(shù)據(jù)分布影響較大，本文提出一種基于空間動態(tài)劃分的差分隱私聚類算法，使用四分樹詳細表示數(shù)據(jù)分布，在數(shù)據(jù)分布較密集的區(qū)域用較小的存儲桶表示，數(shù)據(jù)分布比較少的區(qū)域用較大的存儲桶表示，動態(tài)劃分數(shù)據(jù)空間，以此來創(chuàng)建一個直方圖有效表示數(shù)據(jù)分布，做到盡量減少存儲桶的同時充分表示數(shù)據(jù)的分布情況，減少插入的噪聲。使用處理過的存儲桶的數(shù)據(jù)運行k-means聚類算法，可以有效提高聚類可用性以及準確度，實驗結果表明所提算法優(yōu)于現(xiàn)有算法。

1 相關概念

1.1 差分隱私的基本概念

差分隱私保護模型被公認為是一個嚴格強大的保護模型。它不依賴于對手的背景知識或者計算能力，通過添加噪聲使數(shù)據(jù)失真，同時保證數(shù)據(jù)整體的某些屬性在統(tǒng)計時保持性質(zhì)不變。差分隱私的定義如下：

定義1[5]設K 是一隨機算法，T1和T2為只存在一條記錄不同的兄弟數(shù)據(jù)表，若K 對任意一對兄弟數(shù)據(jù)表T1和T2以及任意輸出S ?Range(K)都滿足：

則稱算法K 滿足ε-差分隱私，其中ε 為差分隱私預算。Pr[K(T1)∈S] 和Pr[K(T2)∈S] 分別表示輸出K(T1) 和K(T2)為S 的概率。差分隱私預算ε 一般設定在[0.01，1）的范圍之內(nèi)，較低的ε 能夠提供更強的隱私保護。

從定義1可以看出，噪聲機制是實現(xiàn)差分隱私保護的主要方法。拉普拉斯機制和指數(shù)機制是實現(xiàn)差分隱私的兩種常用方法。本文使用拉普拉斯機制實現(xiàn)差分隱私，使用拉普拉斯機制時的噪聲大小取決于以下函數(shù)的敏感度。

定義2[5，8]設查詢函數(shù)為f:T →Rd，輸入為任意一對兄弟數(shù)據(jù)表T1和T2，函數(shù)f 的敏感度為：

‖ f(T1)-f(T2) ‖1表示f(T1) 和f(T2) 的一階范數(shù)距離。拉普拉斯機制的定義如下：

定義3[16（]Laplace機制）拉普拉斯機制是通過向數(shù)值型數(shù)據(jù)添加Laplace噪聲實現(xiàn)差分隱私機制的。現(xiàn)有一數(shù)據(jù)表T ，設函數(shù)f:T →Rd，函數(shù)敏感度為Δf ，那么：滿足ε-差分隱私保護。噪聲函數(shù)的概率密度為：

其中b=Δf/ε。

1.2 差分隱私k 均值聚類算法（DPk-means）

設計差分隱私聚類算法是為了在對數(shù)據(jù)表進行刪除數(shù)據(jù)操作時，簇質(zhì)心的變化不會導致隱私數(shù)據(jù)的泄漏。DPk-means[10]的主要思想是：

（1）首先輸入數(shù)據(jù)集D 以及簇的數(shù)量k，隨機選取k 個點{o1,o2,…,ok}作為初始中心點。

（2）將數(shù)據(jù)集中的每個點劃分到距離它最近的中心簇處，形成新的聚類簇，對于每個聚類簇，計算簇內(nèi)的數(shù)據(jù)點各位坐標之和得到，簇內(nèi)數(shù)據(jù)個數(shù)為num。分別對sum 和num 添加滿足差分隱私模型的Laplace 噪聲，得到，以及，計 算 新 的 聚 類 中 心 為num′ 。不停重復上述步驟直到達到迭代次數(shù)或者中心簇不再變化，返回聚類結果中心C。

隱私預算的分配采用逐步增加的分配方式，第一輪迭代分配的隱私預算為ε/2，之后每次迭代分配的預算為前一次的一半。

在實驗過程中發(fā)現(xiàn)隨機選取初始點會導致算法陷入局部最優(yōu)解，實驗結果不穩(wěn)定，并且添加噪聲之后計算得到的新初始中心點往往會大大偏離原來中心點，從而導致后續(xù)聚類結果較差的問題。

2 DPQTk-means聚類算法

傳統(tǒng)差分隱私聚類算法對初始中心選擇敏感，聚類結果較差，并且盲目遍歷所有數(shù)據(jù)，導致算法效率低下。本文提出一種新的差分隱私聚類算法DPQTk -means 算法（Differentially Private Quad Tree k -means algorithm）。所提算法采用四分樹的結構對數(shù)據(jù)集進行處理，用直方圖存儲桶的方式表示數(shù)據(jù)集中分布的數(shù)據(jù)，自適應地根據(jù)數(shù)據(jù)分布情況用大小不一的存儲桶，分布較為稀疏的區(qū)域用較大的存儲桶，分布密集的區(qū)域用較小的存儲桶，動態(tài)劃分空間，更少的存儲桶意味著插入的噪聲量少，能夠有效提高后續(xù)聚類效果。這種表示方式能夠很好解決EUGk-means 算法中對沒有數(shù)據(jù)的區(qū)域也無差別插入噪聲的問題，同時能夠適用于各種分布的數(shù)據(jù)。

由于采用構建差分隱私四分樹的方式進行表示數(shù)據(jù)集，因此本文算法對二維平面位置數(shù)據(jù)有較好的效果。下面介紹四分樹的基本結構。

2.1 四分樹的結構

四分樹（quad tree）是一種樹形數(shù)據(jù)結構，每個結點有四個孩子，因其特殊結構[17-18]可以用來處理二維數(shù)據(jù)。四分樹數(shù)據(jù)結構有一些共有的特性：（1）四分樹把空間分為自適應的區(qū)塊。（2）每個區(qū)塊有一個最大容量，達到最大容量，區(qū)塊會分裂出下一層結點。

圖1表示四分樹劃分平面空間的具體方式，通過判斷區(qū)塊內(nèi)的數(shù)據(jù)點的個數(shù)是否到達設定閾值來決定是否分裂。圖1 中的分裂閾值設定為3，若當前區(qū)塊內(nèi)包含的數(shù)據(jù)點個數(shù)小于等于3則不分裂；若個數(shù)大于3，則分裂成大小相同的四份。

圖1 四分樹劃分空間示意圖

觀察圖1發(fā)現(xiàn)，數(shù)據(jù)分布比較密集的區(qū)域分裂出的區(qū)塊比較多且小，這就是上文所說的較小的存儲桶；數(shù)據(jù)分布較為稀疏的區(qū)塊比較大，這就是較大的存儲桶。這種分裂方式可以根據(jù)點的密集度動態(tài)劃分空間。實際實驗中分裂閾值的設定跟數(shù)據(jù)集的大小有關，并且存儲桶的位置用該桶中心的位置進行代替。

2.2 算法設計

本文通過構造差分隱私四分樹，將數(shù)據(jù)集里的數(shù)據(jù)存儲在四分樹上，根據(jù)設定閾值使用上述區(qū)塊分裂策略構造直方圖存儲桶（也就是四分樹的葉結點），創(chuàng)建一個直方圖來有效表示數(shù)據(jù)的分布，接著提取四分樹上葉結點的數(shù)據(jù)以及計數(shù)值，初始化數(shù)據(jù)集，再運行k -means算法進行聚類，初始中心點采用k-means算法在數(shù)據(jù)集上運行所得到的結果。為了對直方圖進行聚類，用存儲桶的中心點的數(shù)值來表示當前存儲桶。

將差分隱私預算ε 分為兩份ε1=γε 和ε2=(1-γ)ε來進行分配，ε1采用文獻[18-20]中提出的統(tǒng)一分配方法對四分樹進行隱私預算分配。統(tǒng)一分配方法按照四分樹的高度平均分配每層隱私預算εi=ε1/max H ，這樣分配滿足從根結點到葉結點的路徑隱私預算之和小于等于總隱私預算ε1。ε2對直方圖創(chuàng)建完成后的計數(shù)值添加噪聲。算法1為DPQTk-means算法的主要步驟。

算法1 DPQTk-means算法

輸入：數(shù)據(jù)集D，初始化中心{o1,o2,…,ok}，差分隱私預算ε，四分樹的高度maxH ，分裂閾值參數(shù)T ，比率γ，中心個數(shù)k。

輸出：差分隱私聚類結果。

1.ε1←γε,ε2←(1-γ)ε

2.bound←calculate the range of the data

3.Tree ←buildDPQuadTree(D,ε1,bound,max H,T)

4.Leaves ←getQuadTreeLeaves()

5.Bucket ←? /*創(chuàng)建存儲桶，桶的個數(shù)為葉結點的個數(shù)*/

6.for each i in[0,Bucket.size-1]：

7.bound ←Leaves[i].bound

8.Bucket.p[i][0]←(bound[0][0]+bound[1][0])/2

9.Bucket.p[i][1]←(bound[0][1]+bound[1][1])/2

10./*設置存儲桶的中心位置坐標*/

11.Bucket.NoisyCount[i]←Leaves[i].count+Lap(1/ε2)

12.end for

13.{c1,c2,…,ck}←kmeans(Bucket,k)

14.return Cluster centroids{c1,c2,…,ck}

算法1中首先將差分隱私預算分為兩份，第一份用來生成差分隱私四分樹，第二份用來計算存儲桶的噪音計數(shù)值，接著使用一個函數(shù)buildDPQuadTree(D,ε1,bound,max H,T)來構建差分隱私四分樹，具體的構建方式見后文。構建完畢后數(shù)據(jù)集中的所有數(shù)據(jù)都被存儲在Bucket 中，Bucket.p[][0]和Bucket.p[][1]表示每個存儲桶代表的數(shù)據(jù)，計算每個Bucket代表的數(shù)據(jù)點（8和9行），如前文所說，使用存儲桶的中心點的數(shù)值代表當前存儲桶，接著對存儲桶的計數(shù)值添加差分隱私噪聲（第11 行），最后使用所有Bucket 的數(shù)據(jù)以及噪音計數(shù)值運行k-means 算法，返回差分隱私聚類結果。算法1中的bound 是一個二維數(shù)組，用于存儲一個區(qū)塊中數(shù)據(jù)（二維）的取值范圍，第二行將數(shù)據(jù)集中所有數(shù)據(jù)的第一維的最小值和最大值賦給bound[0][0]和bound[1][0]，第二維的最小值和最大值賦給bound[0][1]和bound[1][1]。

差分隱私四分樹的構建方式見算法2。

算法2 buildDPQuadTree(D,ε1,bound,maxH,T)

輸入：數(shù)據(jù)集D，數(shù)據(jù)集值域bound ，差分隱私預算ε1，四分樹的高度maxH ，閾值參數(shù)T 。

輸出：差分隱私四分樹。

2.noise ←Lap(1/budget)

3.count ←node.n /*計算當前結點的計數(shù)值*/

4.NoisyCount ←count+noise

5.if h ≥max H or NoisyCount ≤T then

6.nChildren←0

7.return；/*四分樹初始高度為0*/

8.end if

9.nChildren ←4

10.splits ←? /*二維數(shù)組，用來存儲孩子結點的序號*/

11.computePivot() /*計算中心點*/

12.for each i from 0 to count-1：

13.pid ←partid(pivot,data.points[i])

14./*把數(shù)據(jù)劃分到四個結點中*/

15.add i to splits[pid]

16.end for

17.makeChildren(splits,h+1,ε1-budget)

算法2 的主要思想為：第一次運行算法2 會建立根結點，并設置當前結點參數(shù)，分配每層的隱私預算，根據(jù)預算添加拉普拉斯噪聲。將數(shù)據(jù)集中的點根據(jù)與中心點的大小關系劃分為4 類，分別存儲在四個孩子結點上，并且計數(shù)。設置完畢之后生成孩子結點，其深度為h+1，分配剩余隱私預算。若四分樹深度達到maxH 或者噪音計數(shù)值小于等于預先設置的分裂閾值參數(shù)T ，則四分樹不再繼續(xù)分裂（if 語句也為遞歸返回出口）。makeChildren函數(shù)用來生成孩子結點，在函數(shù)體內(nèi)遞歸調(diào)用buildDPQuadTree 函數(shù)，不斷生成結點。具體實現(xiàn)方式見算法3。

算法3 makeChildren(splits,h,budget)函數(shù)

輸入：記錄四個分裂存儲桶中數(shù)據(jù)的數(shù)組splits，深度h，剩余隱私預算budget。

輸出：孩子結點。

1.create children nodes

2.for j from 0 to nChildren-1

3.for d from 0 to 1

4.if (j ＞＞d)%2==0 then

5.nBound[0][d]←bound[0][d]

6.nBound[1][d]←(bound[0][d]+bound[1][d])/2

7.else

8.nBound[0][d]←(bound[0][d]+bound[1][d])/2

9.nBound[1][d]←bound[1][d]

10.end if

11.end for

12.children[j]←bulidDPQuadTree (splits[j],budget,nBound)

13.end for

makeChildren 函數(shù)根據(jù)孩子結點序號計算當前孩子結點存儲桶（分裂后的存儲桶）的數(shù)據(jù)邊界，接著遞歸調(diào)用buildDPQuadTree函數(shù)，生成下一層孩子結點。

定義4[19]設有n 個隨機算法{ A1,A2,…,An} 和數(shù)據(jù)集D，任意的Ai滿足εi-差分隱私，則該序列組合在數(shù)據(jù)集D 上滿足-差分隱私。

根據(jù)定義4，算法2的差分隱私預算為：

由上式可得，算法2滿足ε1-差分隱私。

同理，算法1中ε1+ε2=ε，滿足ε-差分隱私。

綜上所述，所提算法滿足ε-差分隱私。

3 實驗與結果分析

3.1 實驗參數(shù)設置與實驗環(huán)境

本文使用C++語言進行編程仿真，實驗環(huán)境為Intel?Core i5-8259U @2.3 GHz，8 GB內(nèi)存，MacOS操作系統(tǒng)。

實驗中使用的數(shù)據(jù)集見表1 所示。由于四分樹的結構限制，本文算法適用于二維平面數(shù)據(jù)。Pytest 數(shù)據(jù)集為使用python 生成的隨機數(shù)據(jù)集，維度為2，數(shù)值為(-2,2)，屬性類型為數(shù)值型數(shù)據(jù)。Checkin 數(shù)據(jù)集[21]為社交網(wǎng)站Gowalla上用戶登記酒店的位置信息（經(jīng)度、緯度），維度為2，數(shù)值型數(shù)據(jù)，分布較稀疏。Unbalance 數(shù)據(jù)集[22]表示由6 500 個向量和8 個高級聚類合成的數(shù)據(jù)集。birch3數(shù)據(jù)集[22]由隨機位置和隨機大小組成的二維數(shù)據(jù)集。

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

DPQTk-means算法需要用到ε（差分隱私預算）、k（聚類的中心簇個數(shù)）、maxH（四分樹的高度）、T（分裂閾值參數(shù)）、γ（預算分配系數(shù)）。

通常ε 設置的范圍是[0.01，1]之間，一些情況下設置為ln2 或者ln3[23]。本文設置ε 在[0.01，1]之間呈線性分布，方便觀察算法聚類效果。

聚類簇的個數(shù)已由數(shù)據(jù)集給出。四分樹高度由數(shù)據(jù)集大小決定，具體計算公式為：maxH=(ln N)/d，其中N 為數(shù)據(jù)集的樣本數(shù)，d 為數(shù)據(jù)集的維度。閾值參數(shù)T的計算公式為樣本數(shù)除以1 000。預算分配系數(shù)γ 取0.3。

3.2 評價標準

由于前兩個數(shù)據(jù)集沒有分類標簽，因此采用規(guī)范化簇內(nèi)方差（Normalized Intracluster Variance，NICV）來衡量聚類效果，NICV的計算公式為：

其中，Ci為第i 個聚類質(zhì)心，N 為數(shù)據(jù)集的樣本數(shù)，x為樣本數(shù)據(jù)。

NICV的值越小，說明聚類簇與簇中數(shù)據(jù)越緊密，聚類效果越好；反之，說明聚類效果越差。

對于后兩個帶分類標簽的數(shù)據(jù)集，采用F-measure[24]和NICV相結合的方式評估。F-measure是一種基于精確率和召回率衡量聚類結果準確性（可用性）的度量方法，F(xiàn)-measure 的值越大，表示聚類前后結果相似度越大，即差分隱私算法添加噪聲對聚類結果可用性的影響越小。

設N 為數(shù)據(jù)集的樣本數(shù)，i 為數(shù)據(jù)集的類標簽，ni代表類i 中的點的數(shù)量，nj代表簇Cj中的點的數(shù)量，ni,j代表交集部分的點的數(shù)量。類i 數(shù)據(jù)的聚類精確率、召回率和F-measure定義如下：

其中β 設置為1。對于整個數(shù)據(jù)集來說，F(xiàn)-measure為：

3.3 實驗結果與分析

分別在4 個數(shù)據(jù)集上運行了DPk -means 算法[10]、DPk -means++算法[15]、IDPk -means 算法[11]、EUGk -means 算法[13]以及DPQTk -means 算法。實驗過程中，將差分隱私預算ε 從0.01逐步提高到1。實驗結果顯示的是對應每個差分隱私預算ε，運行30次5個算法之后得到的F-measure和NICV的平均值。

圖2和圖3分別展示了在數(shù)據(jù)集D1和D2上運行5種算法得到的NICV的結果。圖4（a）和圖5（a）為在數(shù)據(jù)集D3和D4上運行得到的NICV的結果。圖4（b）和圖5（b）為在D3和D4上運行得到的F-measure的結果。

圖2 D1上運行的結果

圖3 D2上運行的結果

圖2 ～圖5 中DPQTk -means 和EUGk -means 算法的NICV接近且難以區(qū)分，因此進一步采用相對聚類性能（Relative Clustering Performance，RCP）指標進行衡量。RCP定義為：

圖4 D3上運行的結果

圖5 D4上運行的結果

RCP 可以放大DPQTk -means 和EUGk -means 算法的NICV 的相對關系，RCP 大于0 說明本文所提算法優(yōu)于EUGk -means 算法，否則說明EUGk -means 算法更有優(yōu)勢。圖6展示了兩種算法的聚類性能的優(yōu)劣情況。

圖6 DPQTk-means和EUGk-means算法的RCP

對比圖2、圖3、圖4（a）和圖5（a）可以發(fā)現(xiàn)，在相同的差分隱私預算ε 下，DPQTk-means算法的規(guī)范化簇內(nèi)方差大幅低于DPk-means 算法、DPk-means++算法以及IDPk -means 算法的。觀察圖6 發(fā)現(xiàn)，DPQTk -means算法與EUGk-means算法的RCP值幾乎都大于0，在較低差分隱私預算的情況下，DPQTk-means算法的聚類性能優(yōu)勢明顯，RCP 值可以達到10%到25%，這說明本文算法采用構造差分隱私四分樹的方式初始化數(shù)據(jù)集的方式是有效的，通過四分樹自適應生成存儲桶，動態(tài)劃分平面空間，比EUGk-means算法插入更少的噪聲，提高了聚類效果。觀察到DPk-means 算法、DPkmeans++算法以及IDPk-means算法對于數(shù)據(jù)集的變化NICV值波動較大，而本文算法比較穩(wěn)定，這些結果都說明本文算法優(yōu)于其他四個算法。

對比圖4（b）以及圖5（b）發(fā)現(xiàn)，DPQTk-mans 算法優(yōu)于另外四種算法，因此本文所提算法的聚類結果較為接近原始類標簽標注的結果。并且隨著差分隱私預算的逐漸增加，F(xiàn)-measure 的值也慢慢增加，這是因為隱私水平降低之后，添加的噪聲量也會降低，聚類效果會得到提高。

表2 列出了ε 為0.1 時幾種算法在4 個數(shù)據(jù)集上的運行時間?？梢钥闯?，算法運行時間與數(shù)據(jù)集的大小呈正相關。通過對比在相同數(shù)據(jù)集上的運行時間可以對比分析各算法的運行效率。

表2 各算法在各數(shù)據(jù)集下的運行時間 ms

在相同的數(shù)據(jù)集下，DPk -means、DPk -means++、IDPk-means算法運行時間較長，這是因為這3個算法需要對數(shù)據(jù)進行逐一遍歷，效率低下。

EUGk -means 算法和DPQTk -means 算法運行時間較短，這是因為這兩個算法對存儲桶進行聚類，提高了效率。DPQTk-means算法的運行效率比EUGk-means算法略低，這是因為DPQTk-means算法需要先對點進行動態(tài)劃分，消耗了一些時間，但其聚類性能更好。

4 結束語

本文提出了一種基于空間動態(tài)劃分的差分隱私聚類算法，該算法通過構建差分隱私四分樹的方式初始化數(shù)據(jù)集，動態(tài)劃分平面空間成自適應存儲桶，與傳統(tǒng)DPk -means 算法、DPk -means++算法、IDPk -means 算法以及EUGk-means算法相比，有效提高了差分隱私聚類的可用性，并且能夠在較高差分隱私保護水平的情況下，保持聚類效果，更好地保護了數(shù)據(jù)隱私。然而受四分樹結構限制，本文算法只能處理二維數(shù)據(jù)，今后將研究多維數(shù)據(jù)的差分隱私保護。