基于概率主成分分析的差分隱私數(shù)據(jù)發(fā)布方法

顧貞， 張國印，，宋蕾

(1.哈爾濱工程大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001；2.黑龍江東方學(xué)院 基礎(chǔ)教學(xué)研究部，黑龍江 哈爾濱 150066；3.山東科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，山東 青島 266590)

隨著科學(xué)技術(shù)的發(fā)展，通過各種智能設(shè)備搜集和存儲(chǔ)數(shù)據(jù)的能力越來越強(qiáng)，對這些數(shù)據(jù)進(jìn)行分析挖掘可以很好的為人們的生活服務(wù)。但是這些數(shù)據(jù)往往包含敏感的個(gè)人信息，如果直接將數(shù)據(jù)發(fā)布出去，將會(huì)泄露個(gè)人隱私。平衡發(fā)布數(shù)據(jù)的可用性和隱私性的研究成為近些年研究的熱點(diǎn)，隱私保護(hù)的數(shù)據(jù)發(fā)布就是將原始數(shù)據(jù)進(jìn)行變換使得發(fā)布的數(shù)據(jù)能夠滿足人們用來分析挖掘的需求并且避免隱私泄露。

隱私保護(hù)技術(shù)有匿名方法、抑制方法等，但都容易遭受具有背景知識的攻擊，而差分隱私可以抵抗攻擊者具有任何背景知識的攻擊，差分隱私是將原始數(shù)據(jù)加入隨機(jī)噪聲，從概率意義上使得攻擊者無法區(qū)分原始輸入數(shù)據(jù)，因此，基于差分隱私的數(shù)據(jù)發(fā)布機(jī)制的研究成為近年來研究的熱點(diǎn)[1-5]。

大數(shù)據(jù)時(shí)代搜集到的數(shù)據(jù)具有量大，維度高且有相關(guān)性等特點(diǎn)，通常所用的主成分分析(principal component analysis,PCA)方法是利用降維的思想，研究如何通過少數(shù)幾個(gè)綜合隱變量來解釋原來變量的絕大多數(shù)信息的一種多元統(tǒng)計(jì)分析方法，是非概率的方法，其對應(yīng)的生成式方法叫做概率主成分分析(probabilistic PCA，PPCA)，可以構(gòu)建一個(gè)概率模型，得到原始高維變量和低維隱變量之間的關(guān)系式。Dwork[6]中提出差分隱私，其思想是將數(shù)據(jù)中加入隨機(jī)噪聲，由于差分隱私具有嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)形式，所以無論攻擊者有什么樣的背景知識都能提供強(qiáng)大的隱私保護(hù)，因此差分隱私成為近年的研究熱點(diǎn)，在隱私保護(hù)領(lǐng)域有著廣泛的應(yīng)用，目前對于數(shù)據(jù)隱私保護(hù)，差分隱私算法根據(jù)添加噪聲擾動(dòng)的方式分為輸入擾動(dòng)、目標(biāo)擾動(dòng)、算法擾動(dòng)和輸出擾動(dòng)。

高維數(shù)據(jù)之間具有相關(guān)性，如果數(shù)據(jù)之間存在相關(guān)性，則差分隱私可能無法保證針對任意對手的隱私[7]；如果對高維相關(guān)數(shù)據(jù)的每一維度特征都加入噪聲確保差分隱私，那么隨著隱私預(yù)算的減少，加入的噪聲變大，發(fā)布數(shù)據(jù)的效用將會(huì)明顯降低，甚至導(dǎo)致發(fā)布數(shù)據(jù)不可用[8]。因此，先對高維數(shù)據(jù)進(jìn)行降維處理，在低維的綜合隱變量中加入噪聲，這相當(dāng)于在不降低隱私保護(hù)級別的情況下，將噪聲添加到更少但最重要的部分?jǐn)?shù)據(jù)中，從而可以提高發(fā)布數(shù)據(jù)的效用。文獻(xiàn)[9-17]基于主成分分析的差分隱私數(shù)據(jù)發(fā)布方法已有一些研究成果。目前大多數(shù)方法都是基于輸入擾動(dòng)，基于輸出擾動(dòng)的研究比較少，但是隨著數(shù)據(jù)維數(shù)的增多，特征之間存在關(guān)聯(lián)性，直接對輸入進(jìn)行擾動(dòng)，會(huì)導(dǎo)致重復(fù)加噪和發(fā)布數(shù)據(jù)的效用過低等問題。

基于以上研究，本文提出2種隱私保護(hù)數(shù)據(jù)發(fā)布方法:

1)基于概率主成分分析(probabilistic principal component analysis，PPCA)模型的隱私數(shù)據(jù)發(fā)布方法，將原始高維變量降維為少數(shù)綜合隱變量，利用概率主成分分析模型生成新的數(shù)據(jù)集發(fā)布，發(fā)布的數(shù)據(jù)集保持原數(shù)據(jù)集的統(tǒng)計(jì)特性；

2)基于概率主成分分析的差分隱私(probability principal component analysis of differential privacy，PPCA-DP)數(shù)據(jù)發(fā)布方法，將原始變量降維，得到原始數(shù)據(jù)集的投影矩陣，在投影矩陣中加入拉普拉斯隨機(jī)噪聲，再利用概率主成分分析模型生成新的數(shù)據(jù)集發(fā)布，提高發(fā)布數(shù)據(jù)集的效用。

1 差分隱私及主成分分析

差分隱私為敏感信息提供了可用數(shù)學(xué)公式量化的、嚴(yán)格的隱私保護(hù)，差分隱私的本質(zhì)是隨機(jī)擾動(dòng)，有Laplace機(jī)制[18]和指數(shù)機(jī)制[19]，Laplace機(jī)制適用于數(shù)值型查詢，指數(shù)機(jī)制適用于非數(shù)值型查詢，本文采用Laplace機(jī)制。

定義1差分隱私[6]：給定2個(gè)數(shù)據(jù)集D和D′，兩者至多相差一條記錄，給定一個(gè)隱私算法A，Rang(A)為A的取值范圍，若算法A在2個(gè)相鄰數(shù)據(jù)集D和D′上的任意輸出結(jié)果O滿足：

Pr{A(D)=O}≤exp(ε)Pr{A(D′)=O}

(1)

稱算法A滿足ε差分隱私，ε為隱私預(yù)算，取值越小表示隱私保護(hù)度越高。

定義3拉普拉斯機(jī)制[20]：對于任意一個(gè)函數(shù)f:D→Rd，若算法A的輸出滿足等式：

(2)

式中算法A滿足ε差分隱私，其中Lap(Δf/ε)是拉普拉斯變量。

主成分分析[21]是一種簡化數(shù)據(jù)集的技術(shù)，其思想是對協(xié)方差矩陣Σ進(jìn)行特征分解得：

Σ=UTΛU

(3)

2 基于PPCA模型和PPCA-DP模型的隱私數(shù)據(jù)發(fā)布方法

主成分分析是非概率形式的方法，對應(yīng)的概率形式稱為概率主成分分析。圖1所示的隱變量模型中，將p維觀測向量x與相應(yīng)的k維隱變量s聯(lián)系起來。最常見的這種模型是因子分析模型：

圖1 因子分析圖模型Fig.1 Graphical model for factor analysis

x=Ws+μ+ξ

(4)

式中：x是p維觀測變量；s為k維隱變量，主成分分析可以看作是具有各向同性協(xié)方差矩陣的因子分析模型的最大似然解。

定理1[22]：由圖1和因子分析模型所定義的模型中，當(dāng)ξ～N(0，σ2I),s～N(0,Ik)時(shí)：

x|s～N(Ws+μ，σ2Ip),

(5)

式中：σ>0,W∈Rp×k；參數(shù)W、μ、σ2的最大似然估計(jì)為：

(6)

(7)

(8)

定理2[22]：由圖1和因子分析模型所定義的隱變量模型中在給定觀測變量x的情況下，s的條件分布為：

s|x～N(M-1WT(x-μ),σ2M-1)

(9)

其中s|x已知x的情況下σ的條件分布；M=WTW+σ2I，W,σ2的極大似然估計(jì)為：

(10)

(11)

基于此本節(jié)提出2種隱私數(shù)據(jù)發(fā)布方法，分別是基于概率主成分分析模型的隱私數(shù)據(jù)發(fā)布方法及基于概率主成分分析的差分隱私數(shù)據(jù)發(fā)布方法。

2.1 基于PPCA模型的隱私數(shù)據(jù)發(fā)布方法

基于PPCA模型的隱私數(shù)據(jù)發(fā)布方法其原理是利用主成分分析將原始高維變量降維為低維隱變量，再根據(jù)定理1和定理2中的模型，由低維隱變量得到原始高維變量的概率分布，然后依分布抽樣生成與原始數(shù)據(jù)集具有相同規(guī)模的合成數(shù)據(jù)集發(fā)布，發(fā)布的合成數(shù)據(jù)集與原始數(shù)據(jù)集具有相近的統(tǒng)計(jì)特征，所以該方法既保護(hù)了原始數(shù)據(jù)集的隱私又提高了發(fā)布數(shù)據(jù)集的效用。PPCA模型的算法如下：

算法1：基于PPCA模型的隱私數(shù)據(jù)發(fā)布方法。

輸入：原始數(shù)據(jù)集Xn×p為n行p列的矩陣，每一行是一個(gè)樣本，每個(gè)樣本具有p維特征。

輸出：與原始數(shù)據(jù)具有相近概率分布的數(shù)據(jù)集X′n×p。

算法過程為：

1)輸入數(shù)據(jù)集Xn×p；

2)數(shù)據(jù)規(guī)范化處理，將數(shù)據(jù)變換在[0,1]取值；

3)計(jì)算樣本均值和樣本協(xié)方差陣：

(12)

(13)

4)對Σ分解得Σ=UTΛU，U的各列由矩陣Σ的特征值λ1≥λ2≥…≥λp所對應(yīng)的特征向量構(gòu)成，選取U的前k列得到Uk；

5)計(jì)算Xn×p在k個(gè)主成分空間的主成分得分矩陣：

Sn×k=(X-E(X))Uk

(14)

6)由定理2求隱變量s的條件均值E(s|x)和方差Var(s|x)，從而得到條件分布P(s|x)；

7)依分布P(s|x)抽取樣本s；

8)依分布x|s～N(Ws+μ,σ2Ip)抽取樣本x；

9)生成新的數(shù)據(jù)集X′n×p。

基于PPCA模型的隱私數(shù)據(jù)發(fā)布方法沒有引入差分隱私，而是利用PPCA模型生成新的與原始數(shù)據(jù)集具有相近概率分布的數(shù)據(jù)集發(fā)布，從而使得原始數(shù)據(jù)的隱私信息得到保護(hù)。

2.2 基于PPCA-DP模型的隱私數(shù)據(jù)發(fā)布方法

差分隱私可以抵御具有任何背景知識的攻擊，由于數(shù)據(jù)的高維特性，直接在原始數(shù)據(jù)中加入噪聲或者在協(xié)方差矩陣中加入噪聲將會(huì)影響發(fā)布數(shù)據(jù)的效用，尤其當(dāng)高維數(shù)據(jù)之間存在相關(guān)性的時(shí)候，存在重復(fù)加噪的問題，導(dǎo)致發(fā)布數(shù)據(jù)效用過低，甚至不可用，因此本方案主要分2步:1)利用主成分分析將高維數(shù)據(jù)降維后得到低維隱變量，在低維隱變量中加入噪聲，這相當(dāng)于在比較重要的獨(dú)立的變量中加入噪聲，在同等隱私保護(hù)度下可以提高發(fā)布數(shù)據(jù)的效用；2)利用定理1和定理2生成與原始數(shù)據(jù)具有相近概率分布的合成數(shù)據(jù)集發(fā)布，既提高了發(fā)布數(shù)據(jù)的效用又保護(hù)了原始數(shù)據(jù)的隱私。具體PPCA-DP算法如下：

算法2：基于PPCA-DP的隱私數(shù)據(jù)發(fā)布方法。

輸入：原始數(shù)據(jù)集Xn×p。

輸出：加入拉普拉斯噪聲的與原始數(shù)據(jù)具有相近概率分布的數(shù)據(jù)集X′n×p。

1)輸入數(shù)據(jù)集Xn×p；

2)數(shù)據(jù)規(guī)范化處理，將數(shù)據(jù)變換在[0,1]取值；

3)計(jì)算樣本均值和樣本協(xié)方差陣；

4)對Σ分解得Σ=UTΛU，U的各列由矩陣Σ的特征值λ1≥λ2≥…≥λp所對應(yīng)的特征向量構(gòu)成，選取U的前k列得到Uk；

5)計(jì)算Xn×p在k個(gè)主成分空間的主成分得分矩陣：

K=(X-E(X))Uk

(15)

6)在主成分得分矩陣中加入拉普拉斯噪聲:

(16)

7)由定理2求隱變量s的條件均值E(s|x)和方差Var(s|x)，從而得到條件分布P(s|x)；

8)依分布P(s|x)抽取樣本s；

9)依分布x|s～N(Ws+μ,σ2Ip)抽取樣本；

10)生成新的數(shù)據(jù)集X′n×p；

在PPCA-DP算法中，加入了差分隱私，所以對原始數(shù)據(jù)集起到了更加嚴(yán)格的隱私保護(hù)作用，以下是PPCA-DP算法的隱私分析。

定理3：算法PPCA-DP滿足ε差分隱私。

由向量范數(shù)的定義知：

k‖(X(1)-X(2))Up×k‖2=k[(X(1)-X(2))Up×k]

(17)

故有：

‖(X(1)-X(2))Up×k‖1≤

(18)

因此PPCA-DP算法滿足ε差分隱私。

3 低秩近似誤差及SVM分類實(shí)驗(yàn)

實(shí)驗(yàn)的2個(gè)數(shù)據(jù)集分別為Adult數(shù)據(jù)集和Magic04數(shù)據(jù)集，均來自UCI數(shù)據(jù)集。利用Python實(shí)現(xiàn)本文算法，每組實(shí)驗(yàn)進(jìn)行5次，取5次實(shí)驗(yàn)結(jié)果的平均值。Adult數(shù)據(jù)集中每個(gè)數(shù)據(jù)具有15個(gè)特征維度，在本節(jié)實(shí)驗(yàn)中刪除Adult數(shù)據(jù)集的部分特征，保留其中的age、workclass、education-num、race、gender、capital-gain、capital-loss、hours-per-week、income 9個(gè)特征維度，其中有些是非數(shù)值特征，經(jīng)過特征轉(zhuǎn)換后得到具有21維特征的數(shù)據(jù)集，以income≤50k和income>50k為分類目標(biāo)。Magic04數(shù)據(jù)集中每個(gè)數(shù)據(jù)具有11個(gè)特征維度，數(shù)據(jù)屬于2個(gè)分類。

針對2種方法，本節(jié)與文獻(xiàn)[8]提出的PCA-based PPDP方法做了對比實(shí)驗(yàn)，從矩陣低秩近似誤差MSE值和SVM分類準(zhǔn)確率2方面分別比較這3種方法發(fā)布數(shù)據(jù)集的功效。

Adult和Magic04數(shù)據(jù)集的特征值占比如圖2所示，可看出Adult數(shù)據(jù)集的前9個(gè)主成分的累積貢獻(xiàn)率可以達(dá)到90%以上，Magic04數(shù)據(jù)集的前4個(gè)主成分的累積貢獻(xiàn)率可以達(dá)到90%以上。

圖2 特征值占比Fig.2 Proportion of eigenvalues

3.1 矩陣的低秩近似均方誤差MSE值的比較

本節(jié)利用發(fā)布數(shù)據(jù)集和原始數(shù)據(jù)集之間的矩陣低秩近似誤差MSE的值衡量本文提出的PPCA方法和PPCA-DP方法發(fā)布數(shù)據(jù)集的效用，并與PCA-based PPDP方法作比較。圖3和圖4分別表示2個(gè)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果，每個(gè)數(shù)據(jù)集分別在隱私預(yù)算ε取值為0.1、0.5、1下進(jìn)行實(shí)驗(yàn)，從圖3和圖4可以看出本文所提出的2種方法PPCA與PPCA-DP發(fā)布數(shù)據(jù)集的矩陣低秩近似誤差MSE的值均低于PCA-based PPDP方法發(fā)布數(shù)據(jù)集的矩陣低秩近似誤差MSE的值，這說明本文的PPCA與PPCA-DP方法發(fā)布數(shù)據(jù)集的效用均高于PCA-based PPDP方法發(fā)布數(shù)據(jù)集的效用。

從圖3和圖4中還可以看出對于PPCA數(shù)據(jù)發(fā)布方法，由于沒有引入差分隱私，所以其發(fā)布數(shù)據(jù)集與原始數(shù)據(jù)集的矩陣低秩近似誤差MSE值非常小，并與其余2種方法的MSE值不在一個(gè)數(shù)量級別，并且其MSE值隨著保留主成分個(gè)數(shù)k的增大而減小，這說明隨著保留主成分個(gè)數(shù)k的增多，保留下來的原始變量的信息越多，進(jìn)而發(fā)布數(shù)據(jù)集的概率分布就越接近原始數(shù)據(jù)集的概率分布。

圖3 不同ε取值下的均方誤差值比較(Adult數(shù)據(jù)集)Fig.3 Comparison of mean squared errors values under different ε values (Adult dataset)

圖4 不同ε取值下的均方誤差值比較(Magic04數(shù)據(jù)集)Fig.4 Comparison of mean squared errors values under different ε values (Magic04 dataset)

從2個(gè)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果還可以看出，在同等隱私保護(hù)度下，PPCA-DP方法發(fā)布數(shù)據(jù)集的MSE值低于PCA-based PPDP方法發(fā)布數(shù)據(jù)集的MSE值，這說明在同等隱私保護(hù)度下，本文PPCA-DP方法發(fā)布數(shù)據(jù)集的效用高于PCA-based PPDP方法發(fā)布數(shù)據(jù)集的效用。同時(shí)可以看出兩者的MSE值均受2個(gè)因素的影響，一個(gè)是主成分保留個(gè)數(shù)k，另一個(gè)是隱私保護(hù)預(yù)算ε，當(dāng)固定k的時(shí)候，MSE值隨著隱私預(yù)算ε的減小而增大，說明隨著隱私保護(hù)度的增高，加入的噪聲增多，所以MSE值變大，即發(fā)布數(shù)據(jù)的效用變低；當(dāng)固定隱私預(yù)算ε的時(shí)候，MSE值隨著k的增大而增大，這是因?yàn)楸Ａ舻闹鞒煞謧€(gè)數(shù)越多，加入的噪聲就越多，所以MSE值變大，因此當(dāng)前k個(gè)主成分已經(jīng)占有原始變量90%以上信息的時(shí)候，再過多的保留主成分所帶來的信息有限但勢必導(dǎo)致整體加入的噪聲變多，從而影響發(fā)布數(shù)據(jù)的效用。

3.2 SVM分類準(zhǔn)確率的比較

本節(jié)利用SVM分類準(zhǔn)確率衡量本文的PPCA方法和PPCA-DP方法發(fā)布數(shù)據(jù)集的效用，并與PCA-based PPDP方法作比較。圖5和圖6分別為2個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果，每個(gè)數(shù)據(jù)集分別在隱私預(yù)算ε取值為0.1、0.5、1進(jìn)行實(shí)驗(yàn)。

從圖5和圖6可以看出，PPCA方法和PPCA-DP方法發(fā)布數(shù)據(jù)集的SVM分類準(zhǔn)確率均高于PCA-based PPDP方法發(fā)布數(shù)據(jù)集的SVM分類準(zhǔn)確率，這說明PPCA方法和PPCA-DP方法發(fā)布數(shù)據(jù)集的效用均高于PCA-based PPDP方法發(fā)布數(shù)據(jù)集的效用。PPCA方法發(fā)布數(shù)據(jù)集的SVM分類準(zhǔn)確率隨著保留的主成分個(gè)數(shù)k的增大而增大，當(dāng)k接近原變量個(gè)數(shù)的時(shí)候，其SVM分類準(zhǔn)確率接近原數(shù)據(jù)集的SVM分類準(zhǔn)確率，這是因?yàn)镻PCA方法沒有加入差分隱私，而隨著k的增大保留的原始數(shù)據(jù)集的信息增多，因此發(fā)布數(shù)據(jù)集的概率分布就越接近原始數(shù)據(jù)集的概率分布。

圖5 不同ε取值下SVM分類準(zhǔn)確率比較(Adult數(shù)據(jù)集)Fig.5 Comparison of SVM prediction accuracy at different ε values (Adult dataset)

圖6 不同ε取值下SVM分類準(zhǔn)確率比較(Magic04數(shù)據(jù)集)Fig.6 Comparison of SVM prediction accuracy at different ε values (Magic04 dataset)

PPCA-DP方法引入了差分隱私，有較強(qiáng)的隱私保護(hù)效果，從圖5和圖6看出在同等隱私保護(hù)度下，其發(fā)布數(shù)據(jù)集的SVM分類準(zhǔn)確率略高于PCA-based PPDP方法發(fā)布數(shù)據(jù)集的SVM分類準(zhǔn)確率，兩者的共同點(diǎn)是隨著主成分個(gè)數(shù)k的增多，SVM分類準(zhǔn)確率均在下降，這是因?yàn)殡S著保留的主成分個(gè)數(shù)的增多，加入的噪聲增多，導(dǎo)致發(fā)布數(shù)據(jù)的效用下降。

4 結(jié)論

1)針對數(shù)據(jù)的高維度，相關(guān)性等特點(diǎn)，本文提出了2種隱私保護(hù)數(shù)據(jù)發(fā)布方法PPCA方法和PPCA-DP方法，其中PPCA-DP方法解決了相關(guān)數(shù)據(jù)的重復(fù)加噪問題，使得發(fā)布數(shù)據(jù)滿足差分隱私的同時(shí)提高了發(fā)布數(shù)據(jù)的效用。

2)理論和實(shí)驗(yàn)結(jié)果表明，從發(fā)布數(shù)據(jù)的矩陣低秩近似均方誤差和SVM分類準(zhǔn)確率2方面衡量發(fā)布數(shù)據(jù)的效用時(shí)，在相同隱私預(yù)算下，PPCA-DP方法發(fā)布數(shù)據(jù)的效用高于PCA-based PPDP方法發(fā)布數(shù)據(jù)的效用。

然而本文也有不足之處，主成分分析主要是針對高維數(shù)據(jù)的線性相關(guān)關(guān)系進(jìn)行降維，在下一步研究工作中將開展非線性關(guān)系數(shù)據(jù)的降維，另外，本文方法適用于數(shù)據(jù)擁有方為單方時(shí)，發(fā)布數(shù)據(jù)的隱私保護(hù)，在下一步研究中將擴(kuò)展為當(dāng)數(shù)據(jù)被多個(gè)數(shù)據(jù)擁有方所擁有時(shí)，如何能在保護(hù)數(shù)據(jù)隱私的情況下整合多方數(shù)據(jù)以供人們分析和利用。