鄭　劍　鄒鴻珍

(江西理工大學(xué)信息工程學(xué)院　江西 贛州 341000)

?

差異化隱私預(yù)算分配的線性回歸分析算法

鄭劍鄒鴻珍

(江西理工大學(xué)信息工程學(xué)院江西 贛州 341000)

針對(duì)用差分隱私方法進(jìn)行線性回歸分析敏感性偏大的問題，提出一種差異化的隱私預(yù)算分配算法Diff-LR(DifferentialPrivacyLinearRegression)。該算法首先把目標(biāo)函數(shù)分解成兩個(gè)子函數(shù)，再分別計(jì)算兩個(gè)子函數(shù)的敏感性、分配合理的隱私預(yù)算，并采用拉普拉斯機(jī)制給兩個(gè)子函數(shù)系數(shù)添加噪音。然后對(duì)子函數(shù)進(jìn)行組合，得到添加噪聲后的目標(biāo)函數(shù)，求取最優(yōu)線性回歸模型參數(shù)。最后利用差分隱私序列組合特性從理論上證明該算法滿足ε-差分隱私。實(shí)驗(yàn)結(jié)果表明，Diff-LR算法產(chǎn)生的線性回歸模型具有很高的預(yù)測(cè)準(zhǔn)確性。

差分隱私線性回歸分析敏感性隱私預(yù)算

0　引　言

圖1　線性回歸模型實(shí)例

線性回歸分析是通過對(duì)給定數(shù)據(jù)集的屬性值和預(yù)測(cè)值的統(tǒng)計(jì)整理和分析，找出已知屬性和預(yù)測(cè)值的變化規(guī)律，用模型表示這種變化規(guī)律，并進(jìn)行預(yù)測(cè)和分析?；貧w分析可應(yīng)用于企業(yè)投資分析、醫(yī)療支出預(yù)測(cè)和機(jī)器學(xué)習(xí)等領(lǐng)域。圖1為線性回歸的一個(gè)實(shí)例，根據(jù)數(shù)據(jù)集中某臺(tái)設(shè)備的溫度和產(chǎn)量?jī)蓚€(gè)屬性，找出這兩者的線性關(guān)系模型，這樣就能夠利用設(shè)備的溫度預(yù)測(cè)出該設(shè)備的產(chǎn)量。

在實(shí)際應(yīng)用中，直接發(fā)布回歸模型參數(shù)容易泄露預(yù)測(cè)函數(shù)和數(shù)據(jù)集的數(shù)據(jù)信息。為了防止這種隱私泄露，隱私保護(hù)就變得非常重要。常用的隱私保護(hù)方法有k-anonymity[1]、l-diversity[2]、t-closeness[3]等，但是這些方法大部分都是基于某種背景知識(shí)。2006年Dwork[4]提出了差分隱私的理論體系，該模型不論攻擊者具有多少背景知識(shí)，都能夠通過添加噪聲的方式，在較高程度上保護(hù)數(shù)據(jù)集隱私的同時(shí)盡可能減小數(shù)據(jù)的失真。文獻(xiàn)[5]用差分隱私的方法實(shí)現(xiàn)了社會(huì)網(wǎng)絡(luò)數(shù)據(jù)的發(fā)布。文獻(xiàn)[6]基于差分隱私對(duì)一批線性計(jì)數(shù)查詢提出了一個(gè)最優(yōu)方案。文獻(xiàn)[7]提出了一種發(fā)布差分隱私直方圖的有效方法。文獻(xiàn)[8]提出了一種基于遺傳算法的多用途差分隱私模型。文獻(xiàn)[9-11]總結(jié)了各種面向數(shù)據(jù)發(fā)布和分析的隱私保護(hù)方法，指出基于差分隱私的回歸分析方法，并表明把差分隱私和回歸分析進(jìn)行結(jié)合和拓展也是一大研究熱點(diǎn)。

應(yīng)用差分隱私方法設(shè)計(jì)回歸分析的算法中，文獻(xiàn)[12]直接在輸出結(jié)果上添加噪音，在一定程度上保護(hù)了隱私，但是所需噪聲較大，影響預(yù)測(cè)精度；文獻(xiàn)[13,14]提出了一種邏輯回歸分析方法，直接對(duì)n個(gè)擾動(dòng)函數(shù)的均值添加噪聲，添加噪音量有所減少，但該方法通用性不強(qiáng)。

文獻(xiàn)[15]提出了一種函數(shù)機(jī)制FM(FunctionalMechanism)，通過對(duì)目標(biāo)函數(shù)的系數(shù)統(tǒng)一添加噪聲，得到添加噪聲后的目標(biāo)函數(shù)，再計(jì)算出最優(yōu)的預(yù)測(cè)模型參數(shù)。該方法通用性強(qiáng)，適用于線性回歸和邏輯回歸等多種分析方法，但是算法的敏感性偏高，造成添加噪聲偏大，使模型預(yù)測(cè)精度偏低。對(duì)于這個(gè)問題，本文提出一種針對(duì)線性回歸分析的差分隱私算Diff-LR。通過對(duì)線性回歸模型的目標(biāo)函數(shù)進(jìn)行分解，分配合理的隱私預(yù)算，再用拉普拉斯噪聲分別對(duì)兩個(gè)子函數(shù)的系數(shù)進(jìn)行擾動(dòng)，降低了整個(gè)算法的敏感性，減少了添加的拉普拉斯噪聲，使線性回歸模型預(yù)測(cè)更準(zhǔn)確。

1　相關(guān)理論

1.1相關(guān)定義

定義1[4](ε-差分隱私)設(shè)有兩個(gè)數(shù)據(jù)集D1和D2，D1和D2最多相差一個(gè)元組，給定一個(gè)隨機(jī)隱私函數(shù)A，Range(A)表示A可能輸出結(jié)果O的取值范圍(O∈Rang(A))，如果A滿足下列不等式，則稱函數(shù)A滿足ε-差分隱私。

Pr[A(D1)=O]≤eε×Pr[A(D2)=O]

(1)

其中，ε表示隱私預(yù)算的代價(jià)，ε越小，數(shù)據(jù)保護(hù)程度越高。

定義2[16]對(duì)任意函數(shù)f：D→Rd，f的敏感性可定義為：

(2)

其中，D1，D2為給定的數(shù)據(jù)集，相差至多一條元組。

拉普拉斯機(jī)制的主要思想是通過添加拉普拉斯噪聲來實(shí)現(xiàn)保護(hù)隱私的效果。

定理1[16]對(duì)于任一函數(shù)f：D→Rd，D為數(shù)據(jù)集，Δf表示其敏感性的大小，那么隨機(jī)算法：

1.2差分隱私組合特性

差分隱私包含兩個(gè)重要的組合性質(zhì)[18]，一是序列組合性，二是并行組合性。

性質(zhì)1[17](序列組合性)給定一個(gè)數(shù)據(jù)集D，任一隨機(jī)函數(shù)Ai滿足εi-差分隱私，其中1≤i≤n，則函數(shù)Ai構(gòu)成的組合函數(shù)對(duì)同一數(shù)據(jù)集D滿足∑εi-差分隱私。

性質(zhì)2[17](并行組合性)設(shè)任一隨機(jī)函數(shù)Ai滿足εi-差分隱私，其中1≤i≤n，對(duì)于互不相交的數(shù)據(jù)集Di，則函數(shù)Ai(Di)構(gòu)成的組合函數(shù)滿足(max(εi))-差分隱私。

1.3問題描述

2　Diff-LR算法設(shè)計(jì)與分析

2.1Diff-LR算法設(shè)計(jì)

Diff-LR算法首先對(duì)線性回歸模型的目標(biāo)函數(shù)進(jìn)行推導(dǎo)，把它簡(jiǎn)化成一個(gè)簡(jiǎn)單的二次多項(xiàng)式函數(shù)；然后把目標(biāo)函數(shù)分解成兩個(gè)子函數(shù)，計(jì)算它們各自的敏感性；對(duì)子函數(shù)合理分配隱私預(yù)算，再分別對(duì)兩個(gè)子函數(shù)的系數(shù)添加拉普拉斯噪聲，得到兩個(gè)新的子函數(shù)，重新組合成一個(gè)添加噪聲后的目標(biāo)函數(shù)。當(dāng)該目標(biāo)函數(shù)取最小值時(shí)，得到最優(yōu)的模型參數(shù)。

線性回歸模型的目標(biāo)函數(shù)可做出如下推導(dǎo)：

(3)

那么，很容易把目標(biāo)函數(shù)看作w的二次函數(shù)，可簡(jiǎn)化為：

fD(w)=aw2+bw+c

(4)

(5)

(6)

對(duì)子函數(shù)g(w)、t(w)分配隱私預(yù)算ε1、ε2，根據(jù)拉普拉斯機(jī)制的特性可知，拉普拉斯噪音量的大小與函數(shù)的敏感性成正比，與隱私預(yù)算成反比。為了減少添加的噪聲量，當(dāng)敏感性較大時(shí)分配較大的隱私預(yù)算，敏感性較小時(shí)分配較小的隱私預(yù)算。根據(jù)計(jì)算的Δ1和Δ2的大小可知，敏感性在數(shù)據(jù)集屬性維度d較大時(shí)，g(w)的敏感性比t(w)的敏感性更大。因此，分配隱私預(yù)算ε1、ε2時(shí)，使ε1≥ε2，即對(duì)于固定隱私預(yù)算ε，通過合理分配ε1、ε2，就可以減少噪音,使線性回歸模型預(yù)測(cè)更準(zhǔn)確。

Diff-LR算法如下：

1.ε=ε1+ε2

3.g(w)=aw2，t(w)=bw

2.2算法分析

基于下面定理的證明，驗(yàn)證算法Diff-LR的正確性。

=exp(ε1)

(7)

定理3Diff-LR算法滿足ε-差分隱私

Diff-LR算法主要是對(duì)線性回歸模型的目標(biāo)函數(shù)拆分后的兩個(gè)子函數(shù)分別計(jì)算敏感性，分配差異化的隱私預(yù)算以及對(duì)子函數(shù)的系數(shù)分別添加噪音，對(duì)于隨機(jī)添加的噪音可能致使系數(shù)可能變成負(fù)數(shù)，造成不存在最優(yōu)解問題，本文引用了文獻(xiàn)[15]提出的正則化和譜修剪方法來避免這種情況。

3　實(shí)驗(yàn)設(shè)計(jì)與分析

文中的實(shí)驗(yàn)環(huán)境為Win7，3.6GHz，2.00GB，Diff-LR算法是用Matlab語言實(shí)現(xiàn)。同F(xiàn)M算法一樣，所用數(shù)據(jù)集US和Brazil都來自IntegratedPublicUseMicrodata[18]，分別包含370 000和190 000條數(shù)據(jù)集，對(duì)數(shù)據(jù)集中的每個(gè)屬性值進(jìn)行預(yù)處理，使它們的取值范圍在[-1,1]。

本文通過選取數(shù)據(jù)集條數(shù)的80%作為訓(xùn)練集，用來得到線性回歸模型，剩下20%為測(cè)試集，用來測(cè)試該模型的準(zhǔn)確性。對(duì)實(shí)驗(yàn)結(jié)果采用的評(píng)判標(biāo)準(zhǔn)是均方誤差errorRate，定義如下：

(8)

其中，n表示測(cè)試集數(shù)據(jù)元組個(gè)數(shù)，xi和yi是數(shù)據(jù)集中已經(jīng)給出的數(shù)據(jù)。每條元組的均方誤差越小，線性回歸模型預(yù)測(cè)越準(zhǔn)確。

分別對(duì)數(shù)據(jù)集US和Brazil進(jìn)行實(shí)驗(yàn)，針對(duì)不同數(shù)據(jù)集，不同的隱私預(yù)算ε值，Diff-LR算法和FM算法對(duì)實(shí)驗(yàn)結(jié)果產(chǎn)生影響如圖2和圖3所示。通過合理分配隱私預(yù)算參數(shù)ε1、ε2，當(dāng)隱私預(yù)算ε相同時(shí)，Diff-LR算法比FM算法均方誤差更小，即Diff-LR算法添加噪聲后的線性回歸模型預(yù)測(cè)比FM算法更準(zhǔn)確。隨著ε逐漸增大，Diff-LR算法均方誤差errorRate不斷接近無噪音預(yù)測(cè)模型產(chǎn)生的誤差，在保護(hù)隱私的同時(shí)極大降低了數(shù)據(jù)失真。不論對(duì)于較大數(shù)據(jù)集US還是較小數(shù)據(jù)集Brazil，Diff-LR算法都比FM算法的errorRate更小。同時(shí)，無論隱私預(yù)算怎么變化，無噪音模型的均方誤差基本不變。

圖2　兩種算法在數(shù)據(jù)集US上均方誤差errorRate結(jié)果比較

圖3　兩種算法在數(shù)據(jù)集Brazil上均方誤差errorRate結(jié)果比較

Diff-LR算法的均方誤差比FM算法均方誤差更小的原因有兩點(diǎn)。1)Diff-LR算法對(duì)目標(biāo)函數(shù)進(jìn)行拆分，使得其中一個(gè)子函數(shù)的敏感性為4d，另一個(gè)子函數(shù)的敏感性為2d2，而FM算法的敏感性為2(2d+d2+1)。根據(jù)拉普拉斯機(jī)制性質(zhì)可知，拉普拉斯中噪音量的大小與敏感性成正比，算法的敏感性越大所需要的噪聲越大。因?yàn)镕M算法敏感性比Diff-LR算法敏感性更大，所以FM算法添加噪聲產(chǎn)生的影響比Diff-LR算法更大，造成Diff-LR算法比FM算法均方誤差更小，預(yù)測(cè)更準(zhǔn)確。2)FM算法和Diff-LR算法均滿足ε-差分隱私，不同的是，F(xiàn)M算法是把隱私預(yù)算ε分配給整個(gè)目標(biāo)函數(shù)，而Diff-LR算法通過分別給兩個(gè)子函數(shù)分配不同的隱私預(yù)算ε1、ε2，同時(shí)保證ε=ε1+ε2。Diff-LR算法為了減少添加的噪聲量，給敏感性較大的函數(shù)分配較大的隱私預(yù)算，給敏感性較小的函數(shù)分配較小的隱私預(yù)算，即ε1≥ε2，添加的噪聲更少，數(shù)據(jù)失真更小，預(yù)測(cè)精度更高。

4　結(jié)　語

本文提出了一種基于差分隱私的Diff-LR算法，用于針對(duì)線性回歸模型分析。該算法把目標(biāo)函數(shù)拆分成兩個(gè)子函數(shù)，分別分配合理的隱私預(yù)算，通過降低算法敏感性，減少了添加的拉普拉斯噪聲量，在滿足差分隱私的同時(shí)，使線性回歸模型預(yù)測(cè)得更加精確。實(shí)驗(yàn)結(jié)果表明了針對(duì)線性回歸分析Diff-LR算法相對(duì)于FM算法的優(yōu)越性。

[1]SweeneyL.K-anonymity:amodelforprotectingprivacy[J].InternationalJournalonUncertainty,FuzzinessandKnowledgeBasedSystems,2002,10(5):557-570.

[2]MachanavajjhalaA,KiferD,GehrkeJ,etal.l-diversity:Privacybeyondk-anonymity[J].ACMTransactionsonKnowledgeDiscoveryfromData,2007,1(1):3.

[3]LiN,LiT,VenkatasubramanianS.t-closeness:Privacybeyondk-anonymityandl-diversity[C]//Proceedingsofthe23rdInternationalConferenceonDataEngineering(ICDE). 2007,7:106-115.

[4]DworkC.Differentialprivacy[M]//Automata,LanguagesandProgramming,SpringBerlinHeidelberg,2006:1-12.

[5]ChenR,AcsG,CastellucciaC.Differentiallyprivatesequentialdatapublicationviavariable-lengthn-grams[C]//Proceedingsofthe2012ACMConferenceonComputerandCommunicationsSecurity(CCS),2012:638-649.

[6]YuanG,ZhangZ,WinslettM,etal.Low-rankmechanism:Optimizingbatchqueriesunderdifferentialprivacy[J].ProceedingsoftheVLDBEndowment,2012,5(11):1352-1363.

[7]XuJ,ZhangZ,XiaoX,etal.Differentiallyprivatehistogrampublication[J].TheInternationalJournalonVeryLargeDataBases,2013,22(6): 797-822.

[8]ZhangJ,XiaoX,YangY,etal.PrivGene:differentiallyprivatemodelfittingusinggeneticalgorithms[C]//Proceedingsofthe2013internationalconferenceonManagementofdata,ACM,2013:665-676.

[9] 張嘯劍，孟小峰.面向數(shù)據(jù)發(fā)布和分析的差分隱私保護(hù)[J].計(jì)算機(jī)學(xué)報(bào)，2014，37(4)：927-949.

[10] 熊平，朱天清，王曉峰．差分隱私保護(hù)及其應(yīng)用[J].計(jì)算機(jī)學(xué)報(bào)，2014,37(1)：576-590.

[11] 李揚(yáng)，溫雯，謝光強(qiáng)．差分隱私保護(hù)研究綜述[J].計(jì)算機(jī)應(yīng)用研究，2012，29(9)：3201-3211.

[12]SmithA.Privacy-preservingstatisticalestimationwithoptimalconvergencerate[C]//Proceedingson43thannualACMsymposiumonTheoryofComputing(STOC),ACM,2011:813-822.

[13]ChaudhuriK,MonteleoniC.Privacy-preservinglogisticregression[C]//AdvancesinNeuralInformaationProcessingSystems. 2009: 289-296.

[14]ChaudhuriK,MonteleoniC,SarwateAD.Differentiallyprivateempiricalriskminimization[J].TheJournalofMachineLearningResearch,2011,12: 1069-1109.

[15]ZhangJ,ZhangZ,XiaoX,etal.FunctionalMechanism:Regressionanalysisunderdifferentialprivacy[C]//ProceedingsoftheVLDBEndowment,2012,5(11): 1364-1375.

[16]DworkC,McsherryF,NissimK,etal.Calibratingnoisetosensitivityinprivatedataanalysis[C]//Proceedingsofthe3thTheoryofCryptographyConference(TCC),NewYork,USA,2006: 363-385.

[17]McsherryF.Privacyintegratedqueries:anextensibleplatformforprivacy-preservingdataanalysis[J].CommunicationsoftheACM,2010,53(9): 89-97.

[18]MinnesotaPopulationCenter.Integratedpublicusemicrodataseries-international:Version5.0[OL].[2009].https://international.ipums.org.

LINEARREGRESSIONANALYSISALGORITHMOFDIFFERENTIALPRIVACYBUDGETALLOCATION

ZhengJianZouHongzhen

(School of Information Engineering, Jiangxi University of Science and Technology, Ganzhou 341000, Jiangxi, China)

Fortheproblemofrelativelybigsensitivitywhenusingdifferentialprivacymethodtomakelinearregressionanalysis,thispaperputsforwardthedifferentialprivacybudgetallocationalgorithm-Diff-LR.First,thealgorithmdividestheobjectivefunctionintotwosub-functions,thencalculatesthesensitivitiesofthemseparatelyandallocatesreasonableprivacybudgettothem,aswellasusesLaplacetransformmechanismtoaddnoisestothecoefficientsofthem.Afterthat,itcombinesthesetwosub-functions,andgetstheobjectivefunctionwiththenoiseadded.Thenitcalculatestheoptimallinearregressionparameters,andfinallyemploysthecharacteristicofdifferentialprivacysequencecombinationtoprovetheoreticallythisalgorithmsatisfiesε-differentialprivacy.ExperimentalresultsshowthatthelinearregressionmodelgeneratedbyDiff-LRhashighpredictiveaccuracy.

DifferentialprivacyLinearregressionanalysisSensitivityPrivacybudget

2014-08-13。江西省教育廳科學(xué)技術(shù)研究項(xiàng)目(GJJ13415)；江西理工大學(xué)科研基金重點(diǎn)課題(NSFJ2014-K11)。鄭劍，副教授，主研領(lǐng)域：隱私保護(hù)，可信軟件。鄒鴻珍，碩士生。

TP391

ADOI:10.3969/j.issn.1000-386x.2016.03.065