基于空間動態劃分的差分隱私聚類算法

張可鏵，成衛青

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

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

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

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

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

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

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

1 相關概念

1.1 差分隱私的基本概念

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

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

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

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

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

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

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

其中b=Δf/ε。

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

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

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

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

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

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

2 DPQTk-means聚類算法

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

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

2.1 四分樹的結構

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

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

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

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

2.2 算法設計

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

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

算法1 DPQTk-means算法

輸入：數據集D，初始化中心{o1,o2,…,ok}，差分隱私預算ε，四分樹的高度maxH ，分裂閾值參數T ，比率γ，中心個數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 ←? /*創建存儲桶，桶的個數為葉結點的個數*/

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

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

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

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

輸出：差分隱私四分樹。

2.noise ←Lap(1/budget)

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

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 ←? /*二維數組，用來存儲孩子結點的序號*/

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

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

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

14./*把數據劃分到四個結點中*/

15.add i to splits[pid]

16.end for

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

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

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

輸入：記錄四個分裂存儲桶中數據的數組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 函數根據孩子結點序號計算當前孩子結點存儲桶（分裂后的存儲桶）的數據邊界，接著遞歸調用buildDPQuadTree函數，生成下一層孩子結點。

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

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

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

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

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

3 實驗與結果分析

3.1 實驗參數設置與實驗環境

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

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

表1 數據集信息

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

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

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

3.2 評價標準

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

其中，Ci為第i 個聚類質心，N 為數據集的樣本數，x為樣本數據。

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

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

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

其中β 設置為1。對于整個數據集來說，F-measure為：

3.3 實驗結果與分析

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

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

圖2 D1上運行的結果

圖3 D2上運行的結果

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

圖4 D3上運行的結果

圖5 D4上運行的結果

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

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

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

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

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

表2 各算法在各數據集下的運行時間 ms

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

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

4 結束語

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