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

鄭　劍　鄒鴻珍

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

?

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

鄭劍鄒鴻珍

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

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

差分隱私線性回歸分析敏感性隱私預算

0　引　言

圖1　線性回歸模型實例

線性回歸分析是通過對給定數據集的屬性值和預測值的統計整理和分析，找出已知屬性和預測值的變化規律，用模型表示這種變化規律，并進行預測和分析?；貧w分析可應用于企業投資分析、醫療支出預測和機器學習等領域。圖1為線性回歸的一個實例，根據數據集中某臺設備的溫度和產量兩個屬性，找出這兩者的線性關系模型，這樣就能夠利用設備的溫度預測出該設備的產量。

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

應用差分隱私方法設計回歸分析的算法中，文獻[12]直接在輸出結果上添加噪音，在一定程度上保護了隱私，但是所需噪聲較大，影響預測精度；文獻[13,14]提出了一種邏輯回歸分析方法，直接對n個擾動函數的均值添加噪聲，添加噪音量有所減少，但該方法通用性不強。

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

1　相關理論

1.1相關定義

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

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

(1)

其中，ε表示隱私預算的代價，ε越小，數據保護程度越高。

定義2[16]對任意函數f：D→Rd，f的敏感性可定義為：

(2)

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

拉普拉斯機制的主要思想是通過添加拉普拉斯噪聲來實現保護隱私的效果。

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

1.2差分隱私組合特性

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

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

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

1.3問題描述

2　Diff-LR算法設計與分析

2.1Diff-LR算法設計

Diff-LR算法首先對線性回歸模型的目標函數進行推導，把它簡化成一個簡單的二次多項式函數；然后把目標函數分解成兩個子函數，計算它們各自的敏感性；對子函數合理分配隱私預算，再分別對兩個子函數的系數添加拉普拉斯噪聲，得到兩個新的子函數，重新組合成一個添加噪聲后的目標函數。當該目標函數取最小值時，得到最優的模型參數。

線性回歸模型的目標函數可做出如下推導：

(3)

那么，很容易把目標函數看作w的二次函數，可簡化為：

fD(w)=aw2+bw+c

(4)

(5)

(6)

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

Diff-LR算法如下：

1.ε=ε1+ε2

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

2.2算法分析

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

=exp(ε1)

(7)

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

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

3　實驗設計與分析

文中的實驗環境為Win7，3.6GHz，2.00GB，Diff-LR算法是用Matlab語言實現。同FM算法一樣，所用數據集US和Brazil都來自IntegratedPublicUseMicrodata[18]，分別包含370 000和190 000條數據集，對數據集中的每個屬性值進行預處理，使它們的取值范圍在[-1,1]。

本文通過選取數據集條數的80%作為訓練集，用來得到線性回歸模型，剩下20%為測試集，用來測試該模型的準確性。對實驗結果采用的評判標準是均方誤差errorRate，定義如下：

(8)

其中，n表示測試集數據元組個數，xi和yi是數據集中已經給出的數據。每條元組的均方誤差越小，線性回歸模型預測越準確。

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

圖2　兩種算法在數據集US上均方誤差errorRate結果比較

圖3　兩種算法在數據集Brazil上均方誤差errorRate結果比較

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

4　結　語

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

[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] 張嘯劍，孟小峰.面向數據發布和分析的差分隱私保護[J].計算機學報，2014，37(4)：927-949.

[10] 熊平，朱天清，王曉峰．差分隱私保護及其應用[J].計算機學報，2014,37(1)：576-590.

[11] 李揚，溫雯，謝光強．差分隱私保護研究綜述[J].計算機應用研究，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。江西省教育廳科學技術研究項目(GJJ13415)；江西理工大學科研基金重點課題(NSFJ2014-K11)。鄭劍，副教授，主研領域：隱私保護，可信軟件。鄒鴻珍，碩士生。

TP391

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