多項(xiàng)式回歸的差分隱私保護(hù)算法

謝雅琪，楊 庚,2

(1.南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210046；2.江蘇省大數(shù)據(jù)安全與智能處理重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210023)

0 引 言

多項(xiàng)式回歸是利用數(shù)理統(tǒng)計(jì)中的回歸分析，來(lái)確定兩種或兩種以上變量間相互依賴的非線性定量關(guān)系的一種統(tǒng)計(jì)分析方法，一般應(yīng)用于數(shù)據(jù)屬性之間的關(guān)聯(lián)呈非線性的情況，擁有比線性回歸更加廣泛的應(yīng)用場(chǎng)合，在數(shù)據(jù)挖掘領(lǐng)域中通常使用它對(duì)數(shù)據(jù)進(jìn)行預(yù)測(cè)。

挖掘的數(shù)據(jù)集包含一些敏感屬性，在數(shù)據(jù)挖掘過(guò)程和數(shù)據(jù)發(fā)布中，如不加保護(hù)會(huì)引起隱私泄露[1]。在回歸分析中，常用的隱私保護(hù)算法有幾種類型：匿名算法、數(shù)據(jù)加密和數(shù)據(jù)擾動(dòng)[2]等。匿名算法中，k-匿名算法使用較為廣泛；數(shù)據(jù)加密算法的研究中，常用的有同態(tài)加密[3]、安全多方計(jì)算[4]等；此外還有數(shù)據(jù)泛化[5]。

差分隱私(Differential Privacy，DP)[6]屬于數(shù)據(jù)擾動(dòng)算法，它以數(shù)學(xué)理論為支撐，為數(shù)據(jù)的隱私保護(hù)提供了有力手段[7]。DP通過(guò)對(duì)數(shù)據(jù)集或者查詢函數(shù)添加噪聲等方式實(shí)現(xiàn)隱私保護(hù)。DP最為基礎(chǔ)的兩個(gè)機(jī)制為拉普拉斯機(jī)制和指數(shù)機(jī)制[8]，分別應(yīng)用于查詢函數(shù)的輸出是數(shù)值型和非數(shù)值型的情況，該文涉及的機(jī)制都是拉普拉斯機(jī)制。

在面向回歸分析的差分隱私算法研究中，通常對(duì)數(shù)據(jù)集或查詢函數(shù)加噪聲。前者如Lei[9]提出的DPME算法，后者如函數(shù)擾動(dòng)機(jī)制[10]。添加噪聲的過(guò)程中，可以選擇是否對(duì)代價(jià)函數(shù)進(jìn)行敏感度分析。不做敏感度分析的情況下，可能會(huì)引入不必要的噪聲；如果進(jìn)行敏感度分析，相較于前者，能夠減輕噪聲添加過(guò)量影響可用性的問(wèn)題[11]，具有代表性的算法是Zhang等[12]提出的FM(Function Mechanism)，現(xiàn)在許多研究者都在研究基于FM的改進(jìn)算法[13-16]。

1 相關(guān)工作

2006年，Dwork提出了差分隱私的定義，它通過(guò)對(duì)數(shù)據(jù)集或者模型添加噪聲實(shí)現(xiàn)隱私保護(hù)。相較于傳統(tǒng)的隱私保護(hù)算法，差分隱私不僅擁有數(shù)學(xué)理論作為支撐，而且能夠無(wú)視攻擊者所擁有的知識(shí)背景，提供了有力的隱私保護(hù)。目前，差分隱私的機(jī)制仍在逐步完善中[17-18]。在差分隱私保護(hù)算法被提出后，面向回歸分析領(lǐng)域的差分隱私算法研究在噪聲添加機(jī)制方面主要分為了兩類：直接對(duì)數(shù)據(jù)集添加噪聲和對(duì)查詢函數(shù)添加噪聲。

早期面向回歸分析領(lǐng)域的差分隱私研究集中在對(duì)數(shù)據(jù)集添加噪聲方面，如Lei的DPME算法[9]，但這些算法不對(duì)數(shù)據(jù)集進(jìn)行分析，直接對(duì)數(shù)據(jù)添加噪聲，在數(shù)據(jù)集的維度較大時(shí)，會(huì)引入大量不必要的噪聲影響數(shù)據(jù)集的可用性。

2011年，Chaudhuri等[10]提出了一種對(duì)回歸模型的代價(jià)函數(shù)的系數(shù)添加噪聲的差分隱私保護(hù)算法，并且對(duì)代價(jià)函數(shù)的敏感度進(jìn)行了分析，進(jìn)一步減少了噪聲的添加量，提高了數(shù)據(jù)的可用性。在此基礎(chǔ)上，Zhang等[12]提出了函數(shù)機(jī)制FM，該算法進(jìn)一步提高了訓(xùn)練結(jié)果的精確性。Wang等[15]基于FM算法的思路，提出了DPC算法，主要為了應(yīng)對(duì)模型逆向攻擊(Model Inversion Attack)[19]，提高數(shù)據(jù)的安全性。

該文的主要貢獻(xiàn)為：設(shè)計(jì)了三個(gè)面向多項(xiàng)式回歸的差分隱私算法，通過(guò)多組實(shí)驗(yàn)衡量并比較它們?cè)跀?shù)據(jù)可用性方面的性能，并且優(yōu)化了算法使其能用于高維度的數(shù)據(jù)集。

2 理論基礎(chǔ)

2.1 多項(xiàng)式回歸分析

多項(xiàng)式回歸分析是根據(jù)自變量與因變量的依賴關(guān)系進(jìn)行建模的統(tǒng)計(jì)分析方法,通常在自變量和因變量呈非線性關(guān)系時(shí)使用，如圖1，是一個(gè)簡(jiǎn)單一元二次多項(xiàng)式回歸的擬合結(jié)果，圖中點(diǎn)對(duì)應(yīng)每條數(shù)據(jù)(x,y)。

圖1 簡(jiǎn)單多項(xiàng)式回歸的擬合結(jié)果

多項(xiàng)式回歸的擬合可以通過(guò)變量替換，將其轉(zhuǎn)換成多元線性回歸處理，通過(guò)如公式(2)的映射，將每個(gè)g(x)轉(zhuǎn)化為新的自變量zi，就可以得到多元線性回歸模型。

(1)

(2)

(3)

(4)

(5)

2.2 差分隱私保護(hù)技術(shù)

定義1(差分隱私[6])：當(dāng)且僅當(dāng)算法A的輸入為兩個(gè)鄰近數(shù)據(jù)集D1和D2(最多只有一條記錄有差別的兩個(gè)數(shù)據(jù)集)且滿足式(6)時(shí)，算法A滿足ε-差分隱私。

Pr[A(D1)∈0]≤eε·Pr[A(D2)∈0]

(6)

其中，ε是可以任意設(shè)置的隱私預(yù)算，Pr[A(D1)∈0]代表輸入為D1時(shí)，算法A的輸出屬于集合O的概率。

2.3 全局敏感度

定義2(全局敏感度)：假設(shè)有兩個(gè)鄰近數(shù)據(jù)集D和D',那么對(duì)于一個(gè)函數(shù)f：D→Rd，它的全局敏感度定義為：

(7)

3 面向多項(xiàng)式回歸分析的差分隱私保護(hù)機(jī)制

3.1 多項(xiàng)式回歸算法

(8)

再對(duì)式(8)利用最小二乘法求得ω*：

(9)

3.2 面向多項(xiàng)式回歸分析的差分隱私保護(hù)算法

3.2.1 面向多項(xiàng)式回歸的函數(shù)算法

面向多項(xiàng)式回歸的函數(shù)算法(Functional Mechanism on Polynomial Regression)簡(jiǎn)稱FM-on-PR。

(10)

FM-on-PR對(duì)回歸模型的代價(jià)函數(shù)使用多項(xiàng)式逼近后轉(zhuǎn)化為多項(xiàng)式，如式(11)：

根據(jù)式(4)和式(11)，可以將fD(ω)簡(jiǎn)化為fD(ω)=aω2+bω+c，對(duì)系數(shù)a,b,c各添加上服從Lap(Δf/)分布的噪聲，如式(12)所示：

(12)

全局敏感度的推導(dǎo)與計(jì)算過(guò)程如下：

對(duì)于鄰近數(shù)據(jù)集D和D'，以及它們的代價(jià)函數(shù)fD(ω)和fD'(ω)：

根據(jù)全局敏感度的定義(見(jiàn)定義2)有：

由此，可以得到全局敏感度Δ為：

(13)

算法1：FM-on-PR。

輸入：數(shù)據(jù)集D，隱私預(yù)算，代價(jià)函數(shù)fD(ω)；

2：for each 1≤j≤Jdo

3： for eachφ∈Φjdo

5： end for

6：end for

由2.1節(jié)可知，因?yàn)槎囗?xiàng)式回歸可以通過(guò)變量替換轉(zhuǎn)為多元線性回歸進(jìn)行訓(xùn)練，因此任意多項(xiàng)式回歸的代價(jià)函數(shù)最終都可以表示為式(4)的多元線性回歸形式。

此外，根據(jù)推導(dǎo)，全局敏感度的公式(13)表明其只與數(shù)據(jù)集的維度有關(guān)，與代價(jià)函數(shù)是否為線性并無(wú)關(guān)系。因此全局敏感度的計(jì)算公式同樣適用于轉(zhuǎn)換為多元線性回歸之后的多項(xiàng)式回歸。由此達(dá)成了使用FM算法的前提條件，后續(xù)的幾個(gè)算法同理。

3.2.2 面向多項(xiàng)式回歸的不同系數(shù)擾動(dòng)函數(shù)算法

面向多項(xiàng)式回歸的不同系數(shù)擾動(dòng)函數(shù)算法(Functional Mechanism with Different Perturbation of Coefficients on Polynomial Regression)簡(jiǎn)稱DPC-on-PR。

定義Xs是包含了所有會(huì)泄露隱私的敏感屬性xs的集合。在FM算法的基礎(chǔ)上(見(jiàn)3.2.1)，對(duì)φ也進(jìn)行劃分：只要φ中有包含了任何一個(gè)Xs中的元素對(duì)應(yīng)的系數(shù)ωs，就將其納入集合Φs，否則納入Φn中。對(duì)于Φs中的φ項(xiàng)，分給其相對(duì)較少隱私預(yù)算s， 而分給Φn的隱私預(yù)算n則相對(duì)更多。設(shè)s=γn，其中0<γ<1。給代價(jià)函數(shù)添加完噪聲后，只需對(duì)添加過(guò)噪聲的代價(jià)函數(shù)進(jìn)行最優(yōu)化求解，算法流程如下：

算法2：DPC-on-PR。

輸入：數(shù)據(jù)集D，隱私預(yù)算，代價(jià)函數(shù)fD(ω)，隱私預(yù)算比率γ；

1：設(shè)置Φs={}，Φn={};

2：for each 1≤j≤Jdo

3： for eachφ∈Φjdo

4：ifφ不包括任意屬于敏感集Xs中元素的ωs

5：then將φ添加至集合Φn；

6：else將φ添加至集合Φs；

7： end if

8： end for

9：end for

10：計(jì)算全局敏感度Δ(算法同(13))；

14：for each 1≤j≤Jdo

15： for eachφ∈Φjdo

16： ifφ∈Φnthen

18： else

20： end if

21： end for

22：end for

首先可以算出：

證畢。

3.2.3 面向多項(xiàng)式回歸的差分隱私預(yù)算分配算法

面向多項(xiàng)式回歸的差分隱私預(yù)算分配算法(Differentiated Privacy Budget Allocation on Polynomial Regression)簡(jiǎn)稱DPBA-on-PR。

根據(jù)式(13)，可以得到代價(jià)函數(shù)fD(ω)的全局敏感度為ΔfD(ω)=2(2d+d2)。

隨后，將fD(ω)(fD(ω)的表達(dá)式同式(4)形式)拆解開(kāi)為2個(gè)單項(xiàng)式，分別為：

根據(jù)式(13)，同理可得gD(ω)和hD(ω)的全局敏感度分別為ΔgD(ω)=2d2,ΔhD(ω)=4d。

可以發(fā)現(xiàn)整個(gè)多項(xiàng)式的全局敏感度和兩個(gè)單項(xiàng)式的全局敏感度滿足如下關(guān)系：

ΔfD(ω)=2(2d+d2)=ΔgD(ω)+ΔhD(ω)

算法3：DPBA-on-PR。

輸入：數(shù)據(jù)集D，隱私預(yù)算，代價(jià)函數(shù)fD(ω)；

1：計(jì)算gD(ω)的全局敏感度Δf1，hD(ω)的全局敏感度Δf2；

2：設(shè)gD(ω)的系數(shù)是a，hD(ω)的系數(shù)是b；

3：if Δf1>Δf2then

5：else

7：end if

算法流程中的參數(shù)β，是用來(lái)調(diào)節(jié)gD(ω)和hD(ω)的隱私預(yù)算分配比率的變量，其取值范圍的端點(diǎn)(見(jiàn)上述算法流程中步驟4)分別對(duì)應(yīng)著將總的隱私預(yù)算全部分配給gD(ω)和全部分配給hD(ω)。顯然，gD(ω)相對(duì)于hD(ω)自然有較高的全局敏感度(式(13))，因此必須合理制定β的取值使得gD(ω)添加噪聲規(guī)模較小。

在高維度的數(shù)據(jù)集中，根據(jù)全局敏感度的計(jì)算方法(式(13))，gD(ω)的全局敏感度Δf1更是遠(yuǎn)遠(yuǎn)高于Δf2的，因此為了保證訓(xùn)練結(jié)果的準(zhǔn)確性，gD(ω)應(yīng)該被分配到更多的隱私預(yù)算使得對(duì)其添加的噪聲規(guī)模降低，根據(jù)算法3流程中的步驟4，β的取值就要增大。

表1總結(jié)了β為各個(gè)取值時(shí)，gD(ω)和hD(ω)被分配到的噪聲服從的分布。

表1 β的取值以及gD(ω)和hD(ω)的噪聲分布

(14)

最終β的取值范圍為：

證明：如果給gD(ω)，hD(ω)分別分配隱私預(yù)算g，h，且設(shè)=h+g。根據(jù)FM機(jī)制中的相關(guān)證明(定理2)，這三個(gè)單獨(dú)的代價(jià)函數(shù)又分別滿足g-差分隱私，h-差分隱私。于是，由定理1差分隱私的串行組合性可知，ΔfD(ω)的算法滿足-差分隱私。

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)環(huán)境為Intel(R) Core(TM) i7-9750H CPU 2.60 GHz,16G內(nèi)存。實(shí)驗(yàn)使用的數(shù)據(jù)集為：來(lái)自UCI的聯(lián)合循環(huán)發(fā)電廠(CCPP)數(shù)據(jù)集、個(gè)人家庭用電(IHEPC)數(shù)據(jù)集和Kaggle上獲取的diamond鉆石價(jià)格預(yù)測(cè)數(shù)據(jù)集。屬性如表2所示。

表2 實(shí)驗(yàn)中使用的數(shù)據(jù)集

為了驗(yàn)證所設(shè)計(jì)算法的可行性，在這三個(gè)數(shù)據(jù)集上依次使用該算法進(jìn)行訓(xùn)練，通過(guò)訓(xùn)練結(jié)果的精確度來(lái)判斷它們的可用性。此外，為了檢測(cè)隱私預(yù)算對(duì)模型準(zhǔn)確性的影響，對(duì)每個(gè)數(shù)據(jù)集也將以不同的隱私預(yù)算進(jìn)行多次訓(xùn)練。由于噪聲的影響，也會(huì)進(jìn)行多次實(shí)驗(yàn)取結(jié)果的均值。

4.2 實(shí)驗(yàn)結(jié)果及其分析

4.2.1 隱私預(yù)算對(duì)擬合結(jié)果準(zhǔn)確度的影響

回歸分析有多種性能指標(biāo)衡量其精確性，該文使用擬合優(yōu)度(R2)來(lái)衡量訓(xùn)練模型的準(zhǔn)確性，R2的取值不會(huì)超過(guò)1，越接近1表示訓(xùn)練結(jié)果的準(zhǔn)確度越高，特別地，當(dāng)R2<0時(shí)，表示擬合結(jié)果尚不如取數(shù)據(jù)集的平均值的精度高。

在多項(xiàng)式回歸的階數(shù)設(shè)置方面，經(jīng)測(cè)試，對(duì)于CCPP數(shù)據(jù)集，將它們的階數(shù)設(shè)置為3最佳；對(duì)于IHEPC數(shù)據(jù)集和Diamond數(shù)據(jù)集，設(shè)置為2最佳。

從圖2可見(jiàn)，三個(gè)數(shù)據(jù)集的訓(xùn)練結(jié)果均遵循隱私預(yù)算越大，訓(xùn)練出的模型精確度越高的規(guī)律，并且當(dāng)隱私預(yù)算足夠大時(shí)，幾個(gè)算法之間的精確度差距甚微，同時(shí)與無(wú)隱私保護(hù)的算法的精確度接近。

圖2 在不同隱私預(yù)算下對(duì)三個(gè)數(shù)據(jù)集進(jìn)行回歸訓(xùn)練的結(jié)果

另一方面，無(wú)論基于哪個(gè)數(shù)據(jù)集的實(shí)驗(yàn)，結(jié)果都表明DPBA-on-PR算法擁有最高的精確度，其次是FM-on-PR算法，DPC-on-PR算法最次。由于DPC-on-PR算法提出的目的是為了加強(qiáng)FM-on-PR算法的數(shù)據(jù)安全性，它只對(duì)會(huì)泄露隱私的特征變量添加更多噪聲，并考慮每個(gè)特征變量與輸出的關(guān)聯(lián)性，因此可能會(huì)對(duì)高敏感度的特征變量添加很多不必要的噪聲，從而大大降低訓(xùn)練結(jié)果的準(zhǔn)確性，因此精確性方面不如FM-on-PR算法。

4.2.2 DPBA-on-PR算法中β取值對(duì)訓(xùn)練精確度的影響

因?yàn)閷?duì)該算法中隱私預(yù)算分配策略的優(yōu)化是針對(duì)高維度的數(shù)據(jù)集，所以這部分實(shí)驗(yàn)中，選取維度較高的diamond數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，經(jīng)過(guò)數(shù)據(jù)集預(yù)處理后，它的原始維度d為9，將其多項(xiàng)式形式的目標(biāo)函數(shù)轉(zhuǎn)換為多元線性回歸之后的維度d0達(dá)到了54。同樣，衡量準(zhǔn)確性的標(biāo)準(zhǔn)仍然是擬合優(yōu)度R2。

圖3是DPBA-on-PR算法取不同β值并在不同隱私預(yù)算下的訓(xùn)練結(jié)果，橫坐標(biāo)epsilon是隱私預(yù)算的取值，縱坐標(biāo)是擬合優(yōu)度R2；標(biāo)簽為value1的曲線中β取值均為value1=Δf1(即式(14)中的不等式上限)，在本實(shí)驗(yàn)中具體取值為5 832(計(jì)算公式參考表2)；標(biāo)簽為value2的曲線中的β取值為即式(14)中的不等式的中間項(xiàng)以及得出的β取值新上限)，在本實(shí)驗(yàn)中具體取值為5 771；標(biāo)簽為value3的曲線中的β的取值為即式(14)中的不等式下限)，在本實(shí)驗(yàn)中具體取值為5 621。

由于value1與value2的R2_score(即縱坐標(biāo)值)差值和value2與value3的差值相差過(guò)大不便于比較，因此將比較結(jié)果分在了兩張圖表中。

圖3 DPBA-on-PR算法中β取值對(duì)準(zhǔn)確性的影響

圖3(a)中，β取值為value1時(shí)，在=0.01和0.1的情況下，實(shí)驗(yàn)得到的R2_score均遠(yuǎn)遠(yuǎn)小于-1，而在此圖中，value1代表的曲線在這兩個(gè)取值上均以-1代替表示，僅代表在這兩種情況下，訓(xùn)練結(jié)果不理想。結(jié)果看來(lái)，β取值為value2的訓(xùn)練精確度比value1時(shí)高很多，尤其在隱私預(yù)算較小時(shí)更明顯。

圖3(b)中，β取值為value3時(shí)，如3.2.3小節(jié)所述，此時(shí)的DPBA-on-PR算法就與FM-on-PR算法一致，β取值為value2的訓(xùn)練精確度比取值為value3時(shí)高，結(jié)合4.2.1的實(shí)驗(yàn)，這也證明了DPBA-on-PR算法的精確度性能是優(yōu)于FM-on-DPBA的。

綜上，在3.2.3節(jié)中β的取值策略是可行的。

5 結(jié)束語(yǔ)

該文研究并設(shè)計(jì)了三個(gè)面向多項(xiàng)式回歸的差分隱私保護(hù)算法，并且理論證明了它們滿足差分隱私性質(zhì)；三個(gè)算法與無(wú)隱私保護(hù)的多項(xiàng)式算法的訓(xùn)練結(jié)果進(jìn)行的比較，也證明了它們的可用性；此外經(jīng)實(shí)驗(yàn)，得出了數(shù)據(jù)可用性最高的算法為DPBA-on-PR的結(jié)論。由于DPC-on-PR和DPBA-on-PR分別在數(shù)據(jù)安全性和數(shù)據(jù)可用性方面進(jìn)行了改進(jìn)，因此在實(shí)際應(yīng)用中，可以根據(jù)需求來(lái)對(duì)兩個(gè)算法進(jìn)行選擇?？傮w來(lái)說(shuō)，面向多項(xiàng)式回歸分析的差分隱私算法研究的重點(diǎn)是數(shù)據(jù)的安全性和可用性間平衡的問(wèn)題，通常這方面研究的切入點(diǎn)是隱私預(yù)算的分配與全局敏感度的計(jì)算，目前，全局敏感度的計(jì)算也并沒(méi)有達(dá)到相當(dāng)精確的程度，因此，噪聲的添加量仍有優(yōu)化的余地，這也將是未來(lái)面向多項(xiàng)式回歸的差分隱私保護(hù)算法研究的方向。