基于差分隱私保護的Stacking集成聚類算法研究*

李 帥，常錦才，李呂牧之，蔡昆杰

(1.華北理工大學理學院,河北 唐山 063210;2.河北省數據科學與應用重點實驗室，河北 唐山 063210)

1 引言

在萬物智能、萬物互聯的算力經濟時代，對大數據的聚合與挖掘技術發展迅速。依靠數據挖掘技術獲取各數據項之間的內在關聯是人工智能技術的核心工作[1]。已有的數據挖掘技術包括聚類、分類、回歸、關聯、序列和偏差[2]。聚類[3]作為一種典型的無監督算法，將樣本數據劃分為若干簇，實現“簇內相近、簇外相遠”的目的。與分類不同，聚類不要求數據集中含有預先定義的類別標簽，無需了解數據集的背景知識，僅通過對數據的數值特征進行計算實現集合劃分，分析其關聯規則。由于對數據進行聚類時容易造成用戶的隱私泄露，研究人員開始探索如何在聚類過程中有效保證數據安全，隱私保護數據挖掘[4]已成為近年來的熱門研究方向。

目前隱私保護技術主要分為分組保護、加密保護和失真保護。分組保護是對數據集中包含用戶隱私信息的特征進行刪除或修改，其代表性成果有：Sweeney等[5]提出了基于準標識符處理的k-Anonymity方法，但該方法在攻擊者掌握背景知識或敏感特征取值單一時易泄露隱私；Machanavajjhala等[6]提出了利用等價類替代敏感特征的l-Diversity方法，但特征值相近時可能受到相似性攻擊；Li等[7]提出了t-Closeness方法，通過設置等價類和數據集中敏感屬性分布距離的上限保護隱私，但數據損失較大且難以保護身份信息。加密保護通過對稱加密、非對稱加密和同態加密等技術對原始數據進行加密，雖然保證了傳輸過程中數據的安全性，但難以尋找可信第三方，且加解密過程易產生較大的算力開銷。

以上隱私保護方法在解決部分隱私問題的同時未對模型做出合理假設，在攻擊者掌握數據背景時仍有可能失效。失真保護通過擾亂原始數據來保障隱私安全，克服了上述方法的缺點，但如何達到數據可用性和安全性的平衡成為了難點。基于此，Dwork[8]提出了差分隱私DP(Differential Privacy)，通過嚴格的數學推導和定量的隨機噪聲實現可度量的隱私保護，與攻擊者擁有的數據背景無關，迅速成為研究熱點。

Blum等[9]首先將差分隱私引入K-means聚類算法，但查詢函數敏感度大，且未明確隱私保護預算ε的分配方式。Dwork[10]完善了DPK-means算法中ε的分配方式。Dishabi等[11]將差分隱私應用到基于小波變換的聚類算法中，通過降低數據維度來減小噪聲。Ni等[12]實現了多核密度聚類算法的隱私安全，并使用網絡用戶數據驗證了其可行性。Zhang等[13]改進了DPK-means算法，使用輪廓系數對其性能進行評價。Sun等[14]提出了基于密度的峰值聚類，并將滿足差分隱私的噪聲添加到局部密度和歐氏距離矩陣中，在保護用戶隱私的同時提高了聚類性能。Zhang等[15]通過改進模糊C均值算法中隱私預算的分配比例，依據聚類中心的高斯分布為隸屬度矩陣添加更均衡的噪聲，提高了分簇準確性。可以看出，通過改進聚類思想、優化噪聲的添加機制可同時提高聚類準確性和數據安全性，然而上述研究均使用單一算法聚類，在提升差分隱私聚類的準確性時具有局限性。

為更好地平衡數據可用性與隱私性，本文提出了基于差分隱私保護的Stacking集成聚類DPC-Stacking(Differential Privacy protected Clustering of Stacking)算法。集成多種異質聚類算法，結合輪廓系數對初級聚類算法的輸出進行加權，然后插入原始數據中進行學習，從而大幅提高聚類算法精度，同時針對原始數據和初級聚類算法輸出分別提出了自適應的ε函數p(x)，為數據添加更符合其敏感度的Laplace噪聲。實驗表明,DPC-Stacking算法有效提升了差分隱私保護下對數據集聚類的準確性，減少了噪聲對聚類結果的影響，優于現有差分隱私保護下單一聚類算法的聚類效果。

2 預備知識

2.1 差分隱私模型

差分隱私模型無需考慮已獲取的最大背景知識，通過向數據集或迭代結果中添加定量Laplace噪聲使數據失真，實現嚴格的隱私保護，同時最大程度保證查詢函數的準確性。

定義1(ε-差分隱私) 若有算法M，數據集D和D′僅相差一條記錄,算法M以數據集D和D′為輸入，以M(D)和M(D′)為輸出，M所有可能輸出的子集S(S∈range(M))滿足式(1):

Pr[M(D)∈S]≤eεPr[M(D′)∈S]

(1)

則稱M滿足ε-差分隱私，其中ε表示隱私保護預算，其大小與算法安全性成反比。

定義2(全局敏感度) 函數f的全局敏感度定義如式(2)所示：

(2)

差分隱私為數據集添加Laplace噪聲，設有查詢函數f:D→Rd，其敏感度為Δq，若M滿足式(3):

M(D)=f(D)+[Lap(Δq/ε)]

(3)

則稱M提供ε-差分隱私保護，其中Lap(Δq/ε)表示服從尺度參數為Δq/ε的Laplace分布的隨機噪聲。

定義3(組合差分隱私[16]) 已知數據集D1={s1,s2,…,spnum}包含原始數據中的列向量；D2={sc1,sc2,sc3,sc4}為初級聚類算法產生的一級聚類結果，全數據集D=D1∪D2={s1,s2,…,spnum,sc1,sc2,sc3,sc4},D1和D2的ε值不同。D的相鄰數據集D′={s′1,s′2,…,s′pnum,s′c1,s′c2,s′c3,s′c4},D和D′中均包含pnum+4個列向量，相對應的列向量s和s′僅相差1個樣本。clui為D中任意一列數據，clu′i為D′中對應列，若算法M在clui和clu′i上的輸出Si滿足Pr[M(clui)∈Si]≤eεiPr[M(clu′i)∈Si]，則M滿足組合差分隱私，如式(4)所示:

(4)

其中，ε1和ε2分別表示D1和D2對應的隱私保護預算，Lap(△qi/εi)(i=1,2)表示為Di生成的Laplace噪聲。

2.2 Stacking集成學習算法

Stacking是由Woplert[17]提出的一種可用于異質學習器的串行集成學習框架，該框架采用多個初級學習器對數據集進行訓練，然后利用次級學習器對初級學習器的輸出進行學習，實現多個異質學習算法的融合，提升整體算法的泛化性能。

對于數據集DS={(xn,yn),n=1,2,…,N}，其中,xn為特征向量，yn為預測值，將DS劃分為訓練集DS1和測試集DS2。Stacking集成學習算法的流程如下所示：

步驟1選擇t個初級學習器Hi(i=1,2,…,t)對訓練集DS1進行訓練，然后分別得到初級學習器在訓練集DS1上的輸出DS′1以及在測試集DS2上的輸出DS′2。

步驟2使用次級學習器H′對初級學習器的輸出DS′1進行訓練。

步驟3使用訓練好的次級學習器H′對DS′2進行預測，得到最終對測試集DS2的預測結果。

3 基于差分隱私保護的Stacking集成聚類算法

3.1 初級聚類算法的選擇

在選擇初級聚類算法時，算法的差異性決定著集成算法的性能，因此在選擇初級聚類算法時需要綜合考慮各種聚類算法間的差異，以期取得更優的聚類效果。通過對常用算法分析，本文選用以下4種聚類算法：

(1)K-means經典算法以歐氏距離作為相似度值，迭代尋找新的簇中心，預測性能較好，適用于大規模數據集。

(2)Spectral算法將數據視為無向圖的鄰接矩陣，通過多路劃分實現聚類，但算法復雜度較高，適合小規模應用。

(3)Birch算法通過對構造出的聚類特征 CF(Clustering Feature)樹進行掃描讀取特征元組，分析CF樹結構中的最大子樹和最大距離實現聚類，時間復雜度較低。

(4)GaussianMixture算法通過計算樣本滿足高斯分布的概率為其分配相似度，然后對概率進行修正從而劃分簇。

這4種算法的時間復雜度、可伸縮性、對噪聲的敏感度以及處理較大樣本集的能力均有較大差異，滿足集成算法對基聚類器的要求。

3.2 基本思想

基于差分隱私保護的Stacking集成聚類(DPC-Stacking)算法將K-means、Spectral、Birch和GaussianMixture作為異質聚類算法，對原始數據集D1添加自適應的Laplace噪聲得到脫敏數據集D′1，采用k折交叉驗證學習D′1，合并k折預測結果，作為初級聚類算法輸出。結合輪廓系數對預測集加權得到D2，為D2分配自適應噪聲，得到加噪后的預測集D′2。以K-means算法為次級聚類算法，輸入數據集Dtotal(Dtotal=D′1∪D′2)，產生最終聚類簇。

3.3 自適應ε函數p(x)

ε決定隱私保護程度，不同類型數據對隱私保護程度具有不同要求，因而需要添加不同大小的噪聲。本文定義了DPC-Stacking算法工作過程中的自適應ε函數p(x)，驗證了在集成聚類算法中分配自適應噪聲的可行性。

在為原始數據集D1和初級聚類算法產生的預測集D2選擇ε函數p(x)時需要注意到，原始數據集中含有較多離群點和非私密信息，且數據量較大，并無過高的隱私保護需求。而初級聚類算法產生的預測集由初級聚類算法對整個原始數據集分析得出，當聚類簇數差異較大時，易泄露用戶隱私，且其風險等級依賴聚類的準確性。本文定義D1和D2上的自適應ε函數pi(x)如式(5)所示：

(5)

式(5)綜合了樣本規模和初級聚類算法的輪廓系數，當樣本較多時不易泄露隱私，分配較大的ε。而初級聚類算法的輸出中若各簇節點數相差較大，則有較高安全風險，因而分配較小的ε，添加更大的Laplace噪聲。

3.4 算法流程

DPC-Stacking集成聚類算法的基本流程如下所示：

輸入：數據集Da={s1,s2,…,spnum}，聚類數K，隱私預算ε，初級聚類算法φi(i=1,2,…,T)，次級聚類算法φ。

輸出：經ε-差分隱私保護的聚類簇。

步驟1計算Da的隱私預算ε1=p1(x),生成Laplace噪聲noise1=Lap(Δq1/ε1)；

步驟2向Da中添加噪聲得到脫敏的數據集D′a,D′a=Da+noise1；

步驟3將D′a分為k個子集D′a1,D′a2,…,D′ak；

步驟4 for1≤i≤Tdo:

步驟5for1≤j≤kdo:

步驟6將D′a-D′aj輸入到初級聚類算法φi,得到預測子集S′ij;

步驟7endfor

步驟8合并k個預測子集S′ik得到預測子集Si,Si=S′i1∪S′i2∪…∪S′ik;

步驟9 endfor

步驟10計算各初級聚類算法的輪廓系數λi(i=1,2,…,T)，分別對每個預測子集Si中的每個元素乘以權重系數100×λi;

步驟11合并T個預測子集Si,得到基聚類器的預測集S=S1∪S2∪…∪ST；

步驟12計算預測集S的隱私預算ε2=p2(x),生成滿足ε2-差分隱私的Laplace噪聲noise2=Lap(Δq2/ε2)；

步驟13向S中添加噪聲得到數據集S′,S′=S+noise2；

步驟14合并數據集D′a和S得到D′，將其作為次級聚類算法φ的輸入,得到最終聚類結果。

3.5 隱私性分析

由于原始數據與初級聚類算法的輸出所執行的隱私預算不同，因此對于次級聚類算法所執行的聚類數據無法分析其整體隱私性。本節通過組合差分隱私間接分析DPC-Stacking算法隱私性，若所有數據塊均滿足ε-差分隱私保護，則算法全局滿足ε-差分隱私保護。

設相鄰數據集D與D′僅相差1個樣本，M(D)和M(D′)分別表示DPC-Stacking算法在D與D′上的輸出，S是任意一種聚類的劃分結果。若M(D)和M(D′)均滿足Pr[M(D)∈S]≤eεiPr[M(D′)∈S]，則DPC-Stacking算法滿足ε-差分隱私保護。

證明由條件概率知

其中，σi為尺度參數，服從Laplace分布;Pr[·]為輸出概率。由σi=Δqi/εi得

由f(D)-f(D′)≤Δqi得

故Pr[M(D)∈S]≤eεiPr[M(D′)∈S]，由定義3,M滿足ε-差分隱私。

□

3.6 時間復雜度分析

在3.4節所述DPC-Stacking算法步驟中，步驟1和步驟2用于生成原始數據并添加噪聲，其時間復雜度為O(Nd)；步驟3～步驟8中各初級聚類算法生成預測子集的時間復雜度為O(NdKI)+O(N2)+O(N2logN)+O(N2)；步驟9和步驟10對初級聚類算法的輸出加權并合并至原始數據集中，其時間復雜度為O(NT)；步驟11和步驟12向預測集中添加噪聲的時間復雜度為O(NT)；步驟13和步驟14使用K-means算法對擴展數據集進行聚類的時間復雜度為O(NdKI)。其中,N為樣本數，d為樣本維度，K為聚類個數，I為K-means算法中的迭代次數，T為初級聚類算法個數。

上述5個計算過程無嵌套關系，因而DPC-Stacking算法的總時間復雜度為5個過程中最大的時間復雜度，即O(max(N2,NT,NdKI))。由此可知，算法精度的提升雖然導致計算量略有提升，但與初級聚類算法相比，其時間復雜度仍為一個數量級，不會對算法運行時長產生較大影響。

4 實驗及結果分析

4.1 實驗環境及數據

實驗所用計算機配置為：Intel?CoreTMi5-7200U CPU @ 2.50 GHz、8 GB內存，使用Python編程。所用數據如表1所示，DB1～DB3數據集均來自UCI數據庫，DB4數據集來自DRYAD數據庫。DB1為丙型肝炎血液檢測數據，包含正常血液、丙型肝炎及發展至纖維化、肝硬化時期患者血液。DB2為宮頸癌行為風險數據集，包含正常受訪者和宮頸癌患者的行為特征。DB3為正常受訪者和肥胖癥患者的飲食習慣和身體狀況數據。DB4為2010年Nordsj?lland 大學醫院急診科連續入院患者的常規血液檢查及其死亡風險預測。

Table 1 Experimental data information表1 實驗數據信息

4.2 聚類效果的評價指標

(1)Calinski-Harabasz系數。

Calinski-Harabasz(CH)系數是一種聚類的評估標準，通過簇間距離差與簇內距離差之間跡的比值，判斷聚類結果集中簇內的密合程度以及各簇間的分離程度。CH系數的計算如式(6)所示：

(6)

其中，tr(·)表示矩陣的跡，Bk表示各個簇的協方差矩陣，Wk表示簇內的協方差矩陣，n表示樣本個數，k表示聚類個數，CH(k)∈[-1,1]。

CH系數的值越大，代表聚類效果越好，各個簇間距離更遠且簇內元素在空間中分布越緊密。

(2)輪廓系數。

輪廓系數(Silhouette Coefficient)綜合考慮了內聚度和分離度，通過計算簇內和簇間的不相似度，給出聚類效果的評價。樣本spl的輪廓系數定義如式(7)所示：

(7)

其中，a(spl)表示數據集的簇內不相似度，即樣本spl到該簇內異于該點樣本的平均距離；b(spl)為簇間不相似度，即樣本spl到其他簇內樣本點的平均距離。

綜上，數據集的輪廓系數定義如式(8)所示：

(8)

其中，Nspl為樣本個數，S∈[-1,1]。

4.3 實驗結果及分析

實驗對DB1～DB4進行預處理，將類別屬性轉換為實數，剔除含有缺失值的樣本。分別對K-means、Birch、Spectral和GaussianMixture 4種初級聚類算法進行測試，然后對C-Stacking (無噪聲的DPC-Stacking)算法進行測試，對比基于Stacking思想的集成聚類算法的CH系數和輪廓系數，結果如圖1所示。

由圖1可知，與單一聚類算法相比,C- Stacking算法經聚類計算產生的CH系數提升了43%～406%，輪廓系數提升了26.7%～83.9%。實驗的數據來源于不同領域，且樣本數和特征數有較大差別，但聚類性能均得到顯著增強，表明DPC-Stacking算法具有較高的可用性與魯棒性。因此可知，基于Stacking思想的集成聚類算法遠優于單一聚類算法。

然后，分別令ε=0.05,0.1,0.2,0.5,1,5,10，測試DPC-Stacking算法在不同隱私預算ε下對數據集DB1～DB4的聚類效果。考慮到算法所添加的Laplace噪聲具有隨機性，實驗結果可能存在差異，對不同ε的DPC-Stacking算法運行20次，取CH系數和輪廓系數的平均值作為結果，其對比圖如圖2所示。

由圖2可知，隨著ε的增大，為數據集分配的Laplace噪聲變小，數據的可用性得到提高，因而聚類結果的準確性也不斷提高。當ε<0.5時噪聲過大，加噪后數據集的空間特征難以準確體現樣本的實際特征，聚類結果較差。當ε≥0.5時，算法可以提供足夠的隱私保護，聚類的準確性提升較大，實現了數據安全性與可用性的平衡。因此，將差分隱私保護用于DPC-Stacking算法實現安全高效的聚類是可行的。

Figure 1 Comparison of performance between single clustering algorithm and DPC-Stacking(no noise) algorithm圖1 單一聚類算法與無噪聲DPC-Stacking算法性能對比

Figure 2 DPC-Stacking算法在不同ε下的聚類性能圖2 Clustering performance of DPC-Stacking algorithm with different ε values

為驗證3.3節提出的自適應ε函數p(x)，分別使用4種初級聚類算法對DB1～DB4進行聚類，計算原始數據集D1和初級聚類算法產生的預測集D2的ε函數p1(x)和p2(x)的值，其具體值如表2所示。將其分別代入DPC-Stacking算法，算法運行結果與圖2中近似的傳統ε的對比結果如圖3所示。

Table 2 ε function value of each dataset表2 各數據集的ε函數p(x)值

Figure 3 Comparison of adaptive ε and traditional ε clustering圖3 自適應ε與傳統ε聚類對比圖

由圖3可知，其他條件不變時，原始數據中添加的噪聲對聚類算法性能的影響大于對初級聚類算法的聚類結果所產生的影響。同時，采用自適應的ε函數p(x)確定隱私預算，其生成的噪聲更適合數據集的結構特點，在添加相近噪聲時可產生更優的聚類效果，實現同級別的隱私保護，在滿足ε-差分隱私保護的基礎上仍可提升模型聚類性能，保證了數據可用性。因此，本文提出的自適應ε函數p(x)相對于傳統的無差別ε具有一定的優越性。

5 結束語

數據挖掘中的隱私保護近年來備受關注，傳統聚類僅采用單一算法進行分析，此時引入差分隱私對算法性能影響較大，難以保證數據隱私性與可用性的平衡。本文提出了一種基于差分隱私保護的DPC-Stacking集成聚類算法。通過改進Stacking集成學習算法，并將其與聚類算法相結合，實現了高精度的Stacking聚類算法。考慮到聚類算法在實踐中易產生的隱私泄露問題，將差分隱私引入Stacking聚類算法，并提出適合該算法特性的自適應ε函數p(x)，為初級聚類算法在不同階段的輸入添加更合適的噪聲，在保證數據可用性的基礎上實現了可度量的隱私保護，大幅提高了聚類的準確性與安全性，為差分隱私在集成聚類中的應用開拓了新思路。