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

1.南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，南京210023

2.東南大學(xué) 計(jì)算機(jī)網(wǎng)絡(luò)和信息集成教育部重點(diǎn)實(shí)驗(yàn)室，南京211189

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

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

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

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

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

1 相關(guān)概念

1.1 差分隱私的基本概念

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

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

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

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

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

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

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

其中b=Δf/ε。

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

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

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

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

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

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

2 DPQTk-means聚類算法

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

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

2.1 四分樹的結(jié)構(gòu)

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

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

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

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

2.2 算法設(shè)計(jì)

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

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

算法1 DPQTk-means算法

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

輸出：差分隱私聚類結(jié)果。

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)建存儲(chǔ)桶，桶的個(gè)數(shù)為葉結(jié)點(diǎn)的個(gè)數(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./*設(shè)置存儲(chǔ)桶的中心位置坐標(biāo)*/

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

差分隱私四分樹的構(gòu)建方式見算法2。

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

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

輸出：差分隱私四分樹。

2.noise ←Lap(1/budget)

3.count ←node.n /*計(jì)算當(dāng)前結(jié)點(diǎn)的計(jì)數(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ù)組，用來存儲(chǔ)孩子結(jié)點(diǎn)的序號(hào)*/

11.computePivot() /*計(jì)算中心點(diǎn)*/

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

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

14./*把數(shù)據(jù)劃分到四個(gè)結(jié)點(diǎn)中*/

15.add i to splits[pid]

16.end for

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

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

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

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

輸出：孩子結(jié)點(diǎn)。

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ù)孩子結(jié)點(diǎn)序號(hào)計(jì)算當(dāng)前孩子結(jié)點(diǎn)存儲(chǔ)桶（分裂后的存儲(chǔ)桶）的數(shù)據(jù)邊界，接著遞歸調(diào)用buildDPQuadTree函數(shù)，生成下一層孩子結(jié)點(diǎn)。

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

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

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

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

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

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

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

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

實(shí)驗(yàn)中使用的數(shù)據(jù)集見表1 所示。由于四分樹的結(jié)構(gòu)限制，本文算法適用于二維平面數(shù)據(jù)。Pytest 數(shù)據(jù)集為使用python 生成的隨機(jī)數(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 個(gè)向量和8 個(gè)高級(jí)聚類合成的數(shù)據(jù)集。birch3數(shù)據(jù)集[22]由隨機(jī)位置和隨機(jī)大小組成的二維數(shù)據(jù)集。

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

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

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

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

3.2 評(píng)價(jià)標(biāo)準(zhǔn)

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

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

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

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

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

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

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

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

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

圖2 D1上運(yùn)行的結(jié)果

圖3 D2上運(yùn)行的結(jié)果

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

圖4 D3上運(yùn)行的結(jié)果

圖5 D4上運(yùn)行的結(jié)果

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

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

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

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

表2 列出了ε 為0.1 時(shí)幾種算法在4 個(gè)數(shù)據(jù)集上的運(yùn)行時(shí)間?？梢钥闯觯惴ㄟ\(yùn)行時(shí)間與數(shù)據(jù)集的大小呈正相關(guān)。通過對(duì)比在相同數(shù)據(jù)集上的運(yùn)行時(shí)間可以對(duì)比分析各算法的運(yùn)行效率。

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

在相同的數(shù)據(jù)集下，DPk -means、DPk -means++、IDPk-means算法運(yùn)行時(shí)間較長(zhǎng)，這是因?yàn)檫@3個(gè)算法需要對(duì)數(shù)據(jù)進(jìn)行逐一遍歷，效率低下。

EUGk -means 算法和DPQTk -means 算法運(yùn)行時(shí)間較短，這是因?yàn)檫@兩個(gè)算法對(duì)存儲(chǔ)桶進(jìn)行聚類，提高了效率。DPQTk-means算法的運(yùn)行效率比EUGk-means算法略低，這是因?yàn)镈PQTk-means算法需要先對(duì)點(diǎn)進(jìn)行動(dòng)態(tài)劃分，消耗了一些時(shí)間，但其聚類性能更好。

4 結(jié)束語(yǔ)

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