差分隱私軟大間隔聚類

謝云軒

(南京航空航天大學，江蘇 南京 210000)

如今，AI技術(shù)幾乎在每個行業(yè)都顯示出其獨特的優(yōu)勢。優(yōu)勢之一便來自大數(shù)據(jù)驅(qū)動。雖然對大數(shù)據(jù)的挖掘用于研究與決策可極大地改善社會體系，但是數(shù)據(jù)的共享同時也伴隨隱私的泄露。因此必須保護那些提供個人身份信息等各種機密數(shù)據(jù)的用戶的隱私。比如當研究機構(gòu)使用這些信息進行模型訓練并將模型公開時，隱私信息可能會泄露。因此，有必要在模型訓練過程中增加隱私保護技術(shù)。

在數(shù)據(jù)挖掘的眾多方法中聚類(Clustering)是一種較流行的無監(jiān)督學習手段，其將數(shù)據(jù)集劃分為多個由相似示例組成的簇，使得同一簇內(nèi)的任何兩個示例的相似性大于不同一簇的任意兩個示例的相似性。然而，對于大規(guī)模數(shù)據(jù)或分布式存儲數(shù)據(jù)，一般的單機聚類算法無法滿足對其聚類的訓練需求，即使可行，訓練的時間代價也過于高昂。因此，對單機聚類算法進行分布式改造，減少對大規(guī)模數(shù)據(jù)或分布式存儲數(shù)據(jù)訓練的時間成本，是提高其伸縮性的有效途徑。

在分布式計算中，不同節(jié)點通過在迭代更新中解決本地子問題并上傳解，從而求得全局閉式解，達到整個模型的收斂。但是，不同節(jié)點的通信過程會帶來隱私泄露的風險。因此，在迭代通信中，需要引入隱私保護技術(shù)確保隱私?jīng)]有泄露的風險。

因而近年隱私保護理念持續(xù)受到人們的關(guān)注，其在數(shù)據(jù)挖掘、機器學習和深度學習等許多領(lǐng)域都得到廣泛的應(yīng)用。其中差分隱私通過混淆查詢響應(yīng)來防止對手獲得關(guān)于隱私數(shù)據(jù)的信息，可以為個體隱私提供嚴格的保證而得到廣泛研究。具體而言，差分隱私將隨機噪聲加入待通訊的數(shù)據(jù)，從而避免攻擊者執(zhí)行攻擊來推測數(shù)據(jù)集的若干敏感信息。

盡管學界已提出了極其豐碩的高性能聚類算法，比如DeepClustering等，但對大量現(xiàn)有聚類算法不做選擇地改造并不實際。因此本文將隱私保護改造局限于相對簡單但又有代表性的聚類算法，目的不是提出新的單機聚類算法，而是示范如何讓相對簡單但又有代表性的聚類算法適應(yīng)聯(lián)邦學習環(huán)境，使之發(fā)揮更大的潛能。

軟大間隔聚類(Soft Large Margin Clustering, SLMC)性能相對認可又簡單，直接將數(shù)據(jù)映射到預定的個輸出標記實現(xiàn)聚類。除了不同于FCM(Fuzzy C-Means)在數(shù)據(jù)空間內(nèi)的聚類之外，其作為判別型算法在標記空間進行聚類產(chǎn)生的良好性能和一定程度的可解釋性，并受到后續(xù)關(guān)注。因此本文選擇將其進行隱私保護優(yōu)化。當面對潛在的隱私泄露風險時，分布式軟大間隔聚類(Distributed Sparse SLMC, DS-SLMC)與其他分布式聚類算法一樣，遭遇了類似的瓶頸。因此引入隱私保護改造是一個自然選擇。然而，改造的挑戰(zhàn)是如何在保持原有聚類算法收斂速度和準確度的同時，降低隱私泄露的風險。需要對改造后的算法進行理論證明，看其是否符合差分隱私準則，并利用實驗進行驗證。

本文為了提高SLMC的隱私保護能力，發(fā)展出差分隱私軟大間隔聚類(Differentially Private SLMC, DP-SLMC)。具體來說，在DS-SLMC迭代的過程中加入隨機高斯噪聲，為個體隱私提供嚴格的保證。同時通過-zCDP給出嚴格的隱私分析，證明本文提出的模型滿足差分隱私準則。

本文的具體貢獻如下：

1)將軟大間隔聚類與聯(lián)邦學習進行結(jié)合，通過引入隨機高斯噪聲減少不同節(jié)點間通訊導致隱私泄露的風險，從而解決不同節(jié)點進行分布式機器學習中的隱私問題。

2) 我們通過(,)-DP與-zCDP之間的關(guān)系進行理論證明，得到DP-SLMC算法的隱私保證。確保DP-SLMC算法滿足差分隱私準則。

3) 利用數(shù)據(jù)集進行了廣泛的實驗并對其非隱私版本進行比較，證明所提出算法的有效性。

1 相關(guān)工作

1.1 差分隱私

差分隱私定義如定義1-3所述。

(1)

其中Z()的上界為的可能性至少為1-。

(敏感度) 查詢函數(shù)()對輸入的敏感度為：

(2)

(高斯機制).對于函數(shù)而言, 高斯機制A定義為：

(,,)=()+

(3)

其中為從N(0,)的高斯分布中采樣的噪聲。高斯機制需要將其加入函數(shù)的輸出中。當滿足式(4)時，高斯機制A滿足(,)-DP。

(4)

零集中差分隱私(zero concentrated differential privacy,-zCDP)是一個差分隱私的松弛版本，利用Rényi散度來度量隨機函數(shù)在相鄰數(shù)據(jù)集上的分布差異。-zCDP 如定義4所述。

下文的引理1-3顯示了-zCDP 與(,)-DP 的關(guān)系以及-zCDP的合成定理.

1.2 ADMM方法

在現(xiàn)有的分布式優(yōu)化方式中，交替方向乘子法(Alternating Direction Method of Multipliers, ADMM)是一種比較流行的策略。ADMM將全局問題分解為多個局部子問題，通過協(xié)調(diào)子問題的解最終得到全局問題的最終解。ADMM對輸入不敏感，還具有方法簡單、可解釋性高與收斂性易證明的優(yōu)點。

s.t.+=

(5)

通過優(yōu)化這個目標函數(shù)，算法最終會收斂到某一個全局最優(yōu)化或近似最優(yōu)結(jié)果，從而解決了分布式中的一致性優(yōu)化問題。

然而，滿足差分隱私的ADMM算法大多數(shù)都是去中心化的。比如動態(tài)zCDP(dynamic zero concentrated differential privacy)在每次迭代中引入具有線性衰減方差的高斯噪聲，在加速訓練的同時保持隱私保護的效能。K-Fed算法將聯(lián)邦學習與one-shot學習結(jié)合，只需一輪通訊即可完成K-Means算法的訓練。L-FGADMM將節(jié)點分為頭尾兩組，以確保每個節(jié)點只與其相鄰的兩個節(jié)點進行通信。此外，通過對神經(jīng)網(wǎng)絡(luò)的每一層選擇不同的通信周期，L-FGADMM也減小了模型的通信負載。

1.3 分布式軟大間隔聚類

軟大間隔聚類(SLMC)由Chen于2013年提出。該模型將大間隔聚類(Maximum Margin Clustering, MMC)與軟聚類結(jié)合，在輸出空間進行聚類，而不是在數(shù)據(jù)空間中尋找一組聚類中心。具體來說，SLMC將簇中心錨定為個輸出標記的預定義編碼，計算決策函數(shù)和輸出空間中數(shù)據(jù)的軟隸屬度。它兼有大間隔聚類和軟聚類的優(yōu)點，一方面具有尋求簇間最大間隔的決策函數(shù)，另一方面通過引入軟學習原理，使每個實例都屬于具有相應(yīng)軟隸屬度的多個簇/聚類，并可通過軟隸屬度反映屬于單個簇的程度，從而具有較強的聚類能力。

對SLMC結(jié)合ADMM進行分布式改造之后，優(yōu)化問題表示如下。

‖+‖‖

0≤,≤1,?=1，…，,=1，…，,

=1，…，

(6)

其中決策函數(shù)為：

(7)

該算法通過引入RBF核的顯式特征映射近似，在不降低精度的前提下降低了時間復雜度。具體而言，該算法用傅立葉變換的蒙特卡羅逼近RBF核的特征映射。特征映射的方式如式(8)所述。

(8)

為RBF核對應(yīng)高斯分布中隨機抽樣的向量。顯然，這種近似的精度會隨著樣本數(shù)量的增加而增加。在訓練中，將會根據(jù)具體場景考慮精度與復雜度的權(quán)衡來選擇一個適當?shù)摹?/p>

對其增廣拉格朗日優(yōu)化格式實現(xiàn)采用交替迭代策略求解，可得迭代更新式：

)-1

(9)

(10)

(11)

(12)

為了防止分母為0，故在分母處添加非負小量數(shù)。

(13)

然而，目前還沒有關(guān)于差分隱私中心化SLMC算法的研究工作。因此，本文重點關(guān)注中心化差分隱私ADMM算法并提出了具有隱私保證的差分隱私軟大間隔聚類算法。

2 差分隱私軟大間隔聚類

2.1 差分隱私軟大間隔聚類

算法1 隱私保護軟大間隔聚類算法輸入:λ、ρ,停止參數(shù)εs、εr,,節(jié)點數(shù)M、映射特征維度D、輸入數(shù)據(jù)X;輸出:軟隸屬度矩陣Um;Each learner constructs random feature map Rm(x) with the same seed.Initialize Um by FCM,k=0.Upload Um+ξk+1mto the central server where ξk+1m～N(0,σ2Im+1D).Update Zk+1 in the central server by (11).Update θ^k+lm in parallel by (9).Update Uk+lm in parallel by (10).Update αk+lm in parallel by (13).k=k+1.If not obtaining convergence then go 3.10. Output Um at each learner.

2.2 隱私保護分析

證明：根據(jù)式(6)可得：

(14)

(15)

(16)

(17)

DP-SLMC的隱私保護效用如定理1所示。

(18)

(19)

可得：

(20)

由于在整個迭代過程中每一輪都在更新與上傳系數(shù)矩陣，因此需要計算迭代過程中隱私損失的總和。

(21)

對于所有節(jié)點, DP-SLMC被(,)-DP限制的總隱私損失為：

(22)

3 實驗部分

本節(jié)將會通過 UCI 數(shù)據(jù)集來對本文提出的算法進行實驗，探究其性能。第3.1節(jié)中說明實驗相關(guān)設(shè)置。第3.2節(jié)引入本次實驗的對比指標。最后進行實驗并對實驗結(jié)果進行分析，驗證該方法的有效性。

3.1 實驗設(shè)置

本節(jié)將與未做隱私保護的分布式SLMC進行對比分析，進行性能比較。

我們對待對比的算法執(zhí)行了20次獨立實驗，在每次實驗中使用最優(yōu)的核與參數(shù)設(shè)置，并最終記錄這些實驗結(jié)果的平均值。所有的實驗都是在一臺具有英特爾(R)核心(TM)四核處理器(i7CPU@3.6GHz)和16.0GB內(nèi)存的64位機器上進行的。表2描述了實驗數(shù)據(jù)集的屬性。

表2 數(shù)據(jù)集屬性

3.2 評估指標

雖然本文提出的是無監(jiān)督分布式聚類算法，但在訓練時可通過帶類別標簽的數(shù)據(jù)集進行訓練。具體來說，在訓練時將類別信息剔除，然后將聚類的結(jié)果與真實標簽相比較。因此可采用聚類準確度(Clustering Accuracy, CA)來對算法進行性能評價。

(23)

代表第聚類標簽，而代表真實標簽。(,)則代表屬于真實類別而被預測為類別的數(shù)據(jù)個數(shù)。我們通過比較預測聚類的標簽與真實標簽的方式，來確定聚類的準確度。顯然這個數(shù)值是越大越好。

此外，由于本文提出的是聯(lián)邦聚類算法，因此也將與未進行隱私保護的分布式軟大間隔聚類(DS-SLMC)進行收斂速度的對比。

3.3 實驗分析

圖1顯示了DP-SLMC算法與DS-SLMC算法目標函數(shù)值的對比。DP-SLMC與DS-SLMC的收斂曲線基本吻合，證明二者收斂速度并無太大差異。這個符合我們的直覺，即對交換變量加入符合差分隱私要求的噪聲對收斂過程與函數(shù)值影響較小。這個實驗證明即使加入噪聲，只要控制噪聲的大小，噪聲本身對模型的收斂無法造成較大的干擾。

(a) Dry Bean

DP-SLMC在不同隱私預算下的目標函數(shù)值與準確度對比如圖2所示。在隱私預算較小的情況下，由于加入的噪聲過多，DP-SLMC的目標函數(shù)值與準確度相比，DS-SLMC算法表現(xiàn)不佳。但隨著隱私預算的增加，加入的噪聲逐漸減少，DP-SLMC的目標函數(shù)值與準確度越來越接近DS-SLMC算法。這個實驗說明，保證差分隱私的前提下，只要給予足量的隱私預算，噪聲本身對算法的準確度無法造成較大的干擾。在實際應(yīng)用場景中，可通過準確率與隱私保護需求的權(quán)衡來決定隱私預算的大小，從而讓算法最大限度地滿足需求。

(a) Dry Bean

4 結(jié) 論

提出了一種聯(lián)邦軟大間隔聚類算法，將原聚類算法與隱私保護進行結(jié)合。為了實現(xiàn)這個目標，我們將原始的聚類問題中容易發(fā)生隱私泄露的通信環(huán)節(jié)加噪，使其滿足差分隱私準則，從而達到隱私保護效果。而實驗結(jié)果也表明本文提出的算法在降低隱私泄漏風險的前提下，依舊有貼近原聚類算法的性能與較快的收斂速度。此外，我們也通過實驗驗證DP-SLMC在不同數(shù)據(jù)集上都擁有良好的聚類性能。