基于概率主成分分析的差分隱私數據發布方法

顧貞， 張國印，，宋蕾

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

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

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

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

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

基于以上研究，本文提出2種隱私保護數據發布方法:

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

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

1 差分隱私及主成分分析

差分隱私為敏感信息提供了可用數學公式量化的、嚴格的隱私保護，差分隱私的本質是隨機擾動，有Laplace機制[18]和指數機制[19]，Laplace機制適用于數值型查詢，指數機制適用于非數值型查詢，本文采用Laplace機制。

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

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

(1)

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

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

(2)

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

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

Σ=UTΛU

(3)

2 基于PPCA模型和PPCA-DP模型的隱私數據發布方法

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

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

x=Ws+μ+ξ

(4)

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

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

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

(5)

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

(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的極大似然估計為：

(10)

(11)

基于此本節提出2種隱私數據發布方法，分別是基于概率主成分分析模型的隱私數據發布方法及基于概率主成分分析的差分隱私數據發布方法。

2.1 基于PPCA模型的隱私數據發布方法

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

算法1：基于PPCA模型的隱私數據發布方法。

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

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

算法過程為：

1)輸入數據集Xn×p；

2)數據規范化處理，將數據變換在[0,1]取值；

3)計算樣本均值和樣本協方差陣：

(12)

(13)

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

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

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)生成新的數據集X′n×p。

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

2.2 基于PPCA-DP模型的隱私數據發布方法

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

算法2：基于PPCA-DP的隱私數據發布方法。

輸入：原始數據集Xn×p。

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

1)輸入數據集Xn×p；

2)數據規范化處理，將數據變換在[0,1]取值；

3)計算樣本均值和樣本協方差陣；

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

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

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)生成新的數據集X′n×p；

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

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

由向量范數的定義知：

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分類實驗

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

針對2種方法，本節與文獻[8]提出的PCA-based PPDP方法做了對比實驗，從矩陣低秩近似誤差MSE值和SVM分類準確率2方面分別比較這3種方法發布數據集的功效。

Adult和Magic04數據集的特征值占比如圖2所示，可看出Adult數據集的前9個主成分的累積貢獻率可以達到90%以上，Magic04數據集的前4個主成分的累積貢獻率可以達到90%以上。

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

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

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

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

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

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

從2個數據集的實驗結果還可以看出，在同等隱私保護度下，PPCA-DP方法發布數據集的MSE值低于PCA-based PPDP方法發布數據集的MSE值，這說明在同等隱私保護度下，本文PPCA-DP方法發布數據集的效用高于PCA-based PPDP方法發布數據集的效用。同時可以看出兩者的MSE值均受2個因素的影響，一個是主成分保留個數k，另一個是隱私保護預算ε，當固定k的時候，MSE值隨著隱私預算ε的減小而增大，說明隨著隱私保護度的增高，加入的噪聲增多，所以MSE值變大，即發布數據的效用變低；當固定隱私預算ε的時候，MSE值隨著k的增大而增大，這是因為保留的主成分個數越多，加入的噪聲就越多，所以MSE值變大，因此當前k個主成分已經占有原始變量90%以上信息的時候，再過多的保留主成分所帶來的信息有限但勢必導致整體加入的噪聲變多，從而影響發布數據的效用。

3.2 SVM分類準確率的比較

本節利用SVM分類準確率衡量本文的PPCA方法和PPCA-DP方法發布數據集的效用，并與PCA-based PPDP方法作比較。圖5和圖6分別為2個數據集上的實驗結果，每個數據集分別在隱私預算ε取值為0.1、0.5、1進行實驗。

從圖5和圖6可以看出，PPCA方法和PPCA-DP方法發布數據集的SVM分類準確率均高于PCA-based PPDP方法發布數據集的SVM分類準確率，這說明PPCA方法和PPCA-DP方法發布數據集的效用均高于PCA-based PPDP方法發布數據集的效用。PPCA方法發布數據集的SVM分類準確率隨著保留的主成分個數k的增大而增大，當k接近原變量個數的時候，其SVM分類準確率接近原數據集的SVM分類準確率，這是因為PPCA方法沒有加入差分隱私，而隨著k的增大保留的原始數據集的信息增多，因此發布數據集的概率分布就越接近原始數據集的概率分布。

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

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

PPCA-DP方法引入了差分隱私，有較強的隱私保護效果，從圖5和圖6看出在同等隱私保護度下，其發布數據集的SVM分類準確率略高于PCA-based PPDP方法發布數據集的SVM分類準確率，兩者的共同點是隨著主成分個數k的增多，SVM分類準確率均在下降，這是因為隨著保留的主成分個數的增多，加入的噪聲增多，導致發布數據的效用下降。

4 結論

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

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

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