大數(shù)據(jù)環(huán)境中非交互式查詢差分隱私保護(hù)模型

許 斌，梁曉兵，沈 博

1.中國電力科學(xué)研究院有限公司，北京100192

2.中國科學(xué)院信息工程研究所 信息安全國家重點實驗室，北京100093

3.中國科學(xué)院大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院，北京100049

1 引言

隨著互聯(lián)網(wǎng)與信息技術(shù)的發(fā)展，利用計算機網(wǎng)絡(luò)及其他信息采集設(shè)備所產(chǎn)生的海量數(shù)據(jù)蘊含著巨大的價值，使用這些數(shù)據(jù)對各類行業(yè)的狀態(tài)進(jìn)行數(shù)據(jù)挖掘和分析的數(shù)據(jù)共享模式，已成為信息化時代的發(fā)展潮流。然而，數(shù)據(jù)共享帶來便捷的同時也伴隨著個人隱私數(shù)據(jù)泄露的風(fēng)險，因此隱私保護(hù)數(shù)據(jù)發(fā)布受到廣泛關(guān)注。k-anonymity[1]、l-diversity[2]、t-closeness[3]等傳統(tǒng)的隱私保護(hù)模型，使用泛化、抑制等方法將全部數(shù)據(jù)記錄劃分成若干等價組，使組內(nèi)數(shù)據(jù)記錄無法區(qū)分。但這些傳統(tǒng)的隱私保護(hù)模型由于缺少對隱私泄露風(fēng)險與攻擊模型的定量化分析，因此需不斷地針對新的泄露風(fēng)險提出修補方案。差分隱私（Differential Privacy）[4]數(shù)據(jù)保護(hù)模型從根本上解決了傳統(tǒng)隱私保護(hù)模型的不足，對隱私泄露風(fēng)險給出了嚴(yán)格的、定量化的表示和證明。

差分隱私數(shù)據(jù)發(fā)布分為交互式與非交互式兩種保護(hù)場景。差分隱私在交互式數(shù)據(jù)保護(hù)發(fā)布場景中應(yīng)用效果良好，它通過對在線提交的查詢答案添加隨機噪聲的方式，以達(dá)到個人隱私保護(hù)的目的。而在非交互式大數(shù)據(jù)保護(hù)發(fā)布場景中，需要離線處理數(shù)據(jù)集使其全部可能的查詢答案都滿足差分隱私保護(hù)，由于大量數(shù)據(jù)之間的相關(guān)性與差分隱私的噪聲機制關(guān)聯(lián)，數(shù)據(jù)之間的相關(guān)性越高引入到查詢答案中的噪聲越多，導(dǎo)致發(fā)布數(shù)據(jù)失去效用性。

已有研究工作主要集中在設(shè)計差分隱私批查詢與合成數(shù)據(jù)機制解決上述存在的問題。Zhang等人[5]假設(shè)數(shù)據(jù)屬性之間存在相關(guān)性，并對存在相關(guān)性的數(shù)據(jù)進(jìn)行建模，用模型生成一組邊緣值來模擬原始數(shù)據(jù)集的分布。Chen等人[6]提出聚類與差分隱私結(jié)合的方法，生成合成數(shù)據(jù)進(jìn)行發(fā)布。Mohammed等人[7]提出了一種滿足差分隱私的匿名算法DiffGen，用于保護(hù)進(jìn)行數(shù)據(jù)挖掘時個人的隱私信息。Xiao等人[8]提出一種小波變換的方法Privelet，用于減少數(shù)據(jù)集的敏感度。Li等人[9]提出了回答線性計數(shù)查詢集的矩陣機制，通過查詢集變換的矩陣定義工作負(fù)載，并對其添加拉普拉斯噪聲后使用估計值來生成提交的查詢的答案。Huang等人[10]將查詢集轉(zhuǎn)換為一組正交查詢以減少查詢之間的相關(guān)性，從而降低查詢集的敏感度。Yuan等人[11]提出一種低秩機制，使批量線性查詢的結(jié)果總體誤差最小。

本文所做的工作與上述工作不同，通過將機器學(xué)習(xí)、信息論和差分隱私結(jié)合解決非交互式數(shù)據(jù)發(fā)布中的問題。應(yīng)用最大信息系數(shù)對原始數(shù)據(jù)集進(jìn)行相關(guān)性分析，選擇相關(guān)性低的數(shù)據(jù)記錄作為查詢集，解決查詢間高相關(guān)性的問題。對選出的數(shù)據(jù)記錄使用K-means 算法進(jìn)行分塊處理，使其滿足范圍查詢，通過計算敏感度與添加拉普拉斯噪聲使其滿足差分隱私。將滿足差分隱私的范圍查詢集作為訓(xùn)練樣本進(jìn)行訓(xùn)練，生成預(yù)測模型，用它預(yù)測并回答未知查詢。

2 預(yù)備知識

2.1 最大信息系數(shù)

最大信息系數(shù)（Maximum Information Coefficient）由Reshef[12]等人在2011年提出，它以信息論與互信息論為基礎(chǔ)用來檢測數(shù)據(jù)集中變量之間潛在的線性或非線性關(guān)聯(lián)關(guān)系，被廣泛應(yīng)用于大數(shù)據(jù)的相關(guān)性分析，通過網(wǎng)格劃分方法計算不同網(wǎng)格中兩個變量形成的概率分布來計算所有不同網(wǎng)格的最大互信息[13]。

定義1（互信息）給定變量A={ai,i=1,2,…,n}和B={bi,i=1,2,…,n}，n 為樣本數(shù)量，則

式中p(a,b)為A 和B 的聯(lián)合概率密度，p(a)和p(b)分別為A 和B 的邊緣概率密度，使用直方圖估計對上述的概率密度進(jìn)行估計。

定義2（最大互信息）假設(shè)D={(ai,bi),i=1,2,…,n}為一個有限的有序?qū)Φ募希x劃分G 將變量A的值域分成x 段，將變量B 的值域分成y 段，G 即為x×y的網(wǎng)格。在得到的每一種網(wǎng)格劃分內(nèi)部計算互信息MI(A,B)，相同x×y 的網(wǎng)格劃分有多種，取不同劃分方式中的MI(A,B)最大值作為劃分G 的互信息值，則

式中，D|G 表示數(shù)據(jù)D 在使用G 進(jìn)行劃分。

定義3（特征矩陣）將不同劃分下得到的最大歸一化的MI 值組成特征矩陣M(D)x,y，則

定義4（最大信息系數(shù)）設(shè)n 是數(shù)據(jù)集D 中兩個隨機變量X 和Y 形成的散點數(shù)，則

式中，B(n)為網(wǎng)格x×y 的上限值，當(dāng)B(n)=n0.6時效果最好。

2.2 差分隱私

差分隱私的本質(zhì)上是一種基于數(shù)據(jù)失真的隱私保護(hù)技術(shù)，其基本思想是在最大限度的保證數(shù)據(jù)庫查詢可用性，同時最大限度地保護(hù)數(shù)據(jù)庫中的個人隱私不被泄露。

定義5（ε-差分隱私）對于給定鄰近數(shù)據(jù)集D 和D′，| DΔ D′|=1，若存在隱私算法M，Range(M)是M的取值范圍，若算法M 在數(shù)據(jù)集D 和D′上的任意輸出結(jié)果S(S ∈Range(M))滿足下式，則稱算法M 滿足ε-差分隱私，其中ε 表示隱私預(yù)算。

從上式中可以看出，隱私預(yù)算ε 越小，隱私保護(hù)的程度越高。

定義6（全局敏感度）[14]定義鄰近數(shù)據(jù)集D 和D′，對于任意的查詢函數(shù)f:D →Rd，則查詢函數(shù)的全局敏感度為：

其中，R 表示函數(shù)所映射的實數(shù)空間，d 表示函數(shù)f 的查詢維度。

定義7（拉普拉斯機制）[15]給定數(shù)據(jù)集D 查詢函數(shù)f:D →R，如果算法M 的輸出滿足下式，則算法M 滿足ε-差分隱私。

3 非交互式差分隱私保護(hù)模型

在大數(shù)據(jù)環(huán)境下，設(shè)計滿足差分隱私約束的非交互式數(shù)據(jù)保護(hù)框架需要解決兩個主要問題：一是減少大量查詢之間的相關(guān)性；二是有效地處理未知查詢。為了有效解決上述問題，提出大數(shù)據(jù)環(huán)境中非交互式查詢差分隱私保護(hù)模型（NIQDP）。

3.1 非交互式查詢差分隱私保護(hù)模型

非交互式查詢差分隱私保護(hù)模型，如圖1所示。首先從數(shù)據(jù)相關(guān)性角度出發(fā)選出相關(guān)性低的數(shù)據(jù)記錄作為查詢集，同時采用差分隱私中的拉普拉斯機制和機器學(xué)習(xí)的線性回歸算法對查詢集進(jìn)行隱私保護(hù)及預(yù)測模型訓(xùn)練，將原始數(shù)據(jù)記錄輸入到預(yù)測模型中，輸出滿足差分隱私保護(hù)的查詢集。

非交互式查詢差分隱私保護(hù)模型由以下三個子模型組成。

（1）基于最大信息系數(shù)的特征選擇模型（Feature Selection model based on Maximum Information Coefficient，MICFS）：選取對原始大數(shù)據(jù)集D 采用MICFS模型，計算數(shù)據(jù)之間的相關(guān)性，通過設(shè)定閾值，選取相關(guān)性低的數(shù)據(jù)記錄作為特征集B。

（2）基于差分隱私的分塊數(shù)據(jù)保護(hù)模型（Block Data Protection model based on Differential Privacy，DPBDP）：采用DPBDP 模型，首先利用K-means 算法對特征集進(jìn)行K-區(qū)塊劃分，得到查詢集f( B )，然后對其添加拉普拉斯噪聲，獲得滿足差分隱私的查詢集。

（3）基于線性回歸的隱私保護(hù)預(yù)測模型（Privacy Protection Prediction model based on Linear Regression，LRPPP）：采用LRPPP模型，將查詢集f( B )與足差分隱私的查詢集f^( )B 作為訓(xùn)練樣本集，利用線性回歸算法對其進(jìn)行訓(xùn)練，生成預(yù)測模型。

3.2 基于最大信息系數(shù)的特征選擇模型

利用最大信息系數(shù)與啟發(fā)式搜索算法結(jié)合的方式從原始數(shù)據(jù)集中定義特征與類別、特征與特征間的相關(guān)性并于搜索選出最優(yōu)子集，選出相關(guān)性低的特征數(shù)據(jù)作為特征集。通過最大信息系數(shù)可以準(zhǔn)確地找到變量之間的依賴關(guān)系，從而可以在采用DPBDP 模型時更準(zhǔn)確地計算敏感度。

給定一個n 條樣本的特征集F={f1,f2,…,fm,c}，其特征數(shù)為m，類別為c。對任意特征fi與類別c 間的相關(guān)性定義為MIC(fi,c)，取值范圍在[0，1]。MIC(fi,c)值越大，表明fi與c 間的相關(guān)性越強，則fi為強相關(guān)特征；MIC(fi,c)值越小，表明fi與c 間的相關(guān)性越弱，則fi為弱相關(guān)特征。對任意特征fi和fj之間的相關(guān)性定義為MIC(fi,fj)，MIC(fi,fj)值越大，說明fi和fj間可替代性越強，MIC(fi,fj)值為0 時，說明fi和fj間相互獨立。

如圖2所示，本文中定義的基于最大信息系數(shù)的特征選擇模型對原始數(shù)據(jù)集進(jìn)行特征選擇的過程：

圖1 非交互式查詢隱私保護(hù)模型

（1）給定一個具有n 條樣本的特征集F={f1,f2,…,fm,c}的原始數(shù)據(jù)集D 和為空數(shù)據(jù)集B。

（2）從F 中選取候選變量fi，計算fi和c之間的最大信息系數(shù)MIC(fi;c)。

（3）以計算出的最大MIC 值作為初始變量，D=D-{fi}，B=B+{fi}；

（5）重復(fù)步驟（4）直到選定特征的個數(shù)達(dá)到設(shè)定的值后，輸出包含選定特征的訓(xùn)練樣本集B。

圖2 基于最大信息系數(shù)的特征選擇模型流程圖

3.3 基于差分隱私的分塊數(shù)據(jù)保護(hù)模型

對于大數(shù)據(jù)集，實現(xiàn)單個數(shù)據(jù)記錄的差分隱私保護(hù)會消耗過多的計算資源和隱私預(yù)算，將經(jīng)過MICFS 模型后的特征集分塊后，對每個數(shù)據(jù)塊實現(xiàn)差分隱私保護(hù)后，根據(jù)差分隱私的并行組合性質(zhì)[3]，可以實現(xiàn)整個特征集的差分隱私保護(hù)。

定義8（k-塊差分隱私）B={D1,D2,…,Dk}為大數(shù)據(jù)集D 的k-塊劃分?jǐn)?shù)據(jù)集，即D1,D2,…,Dk是彼此獨立，對 于，其中，是數(shù)據(jù)集Di與刪除數(shù)據(jù)集Di的第j 條數(shù)據(jù)后產(chǎn)生的數(shù)據(jù)集之間的不同數(shù)據(jù)記錄。對于任意輸出S ∈R滿足下式，則滿足k-塊差分隱私。

其中，A為隱私機制，f 為查詢函數(shù)。

對于數(shù)據(jù)集B={D1,D2,…,Dk}，如果每個數(shù)據(jù)塊Di滿足隱私預(yù)算為εi的k-塊差分隱私，根據(jù)差分隱私的并行組合性質(zhì)，則

對于給定查詢函數(shù)，實現(xiàn)隱私機制A實際上是對查詢函數(shù)添加符合拉普拉斯分布的噪聲，拉普拉斯分布具有對稱性，基于這一觀察，提出了均值-拉普拉斯機制。

定義9（均值-拉普拉斯機制）給定隱私機制A，查詢函數(shù)f，數(shù)據(jù)集B 與隱私預(yù)算ε，若滿足下式，則滿足均值-拉普拉斯機制。

執(zhí)行DPBDP模型分四個步驟：

（1）k-塊劃分。將執(zhí)行MICFS 模型后產(chǎn)生的數(shù)據(jù)集B 應(yīng)用k-means 聚類算法進(jìn)行劃分成為k-數(shù)據(jù)塊并獲得數(shù)據(jù)集B={D1,D2,…,Dk}，D1,D2,…,Dk是彼此獨立的，D1∪D2∪…∪Dk=D。

（2）計算敏感度。對于數(shù)據(jù)塊Di，計算每個數(shù)據(jù)塊Di(i=1,2,…,k)中刪除一條記錄j 及其相關(guān)記錄的值，得到鄰近數(shù)據(jù)集，并計算Di上查詢函數(shù)f 的敏感度。

（3）實現(xiàn)拉普拉斯噪聲。在計算相關(guān)敏感度后，根據(jù)定義9完成拉普拉斯噪聲添加。

（4）實現(xiàn)數(shù)據(jù)集B 的差分隱私。重復(fù)步驟（2）與（3）直到數(shù)據(jù)集B 中所有數(shù)據(jù)塊實現(xiàn)差分隱私保護(hù)。

3.4 基于線性回歸的隱私保護(hù)預(yù)測模型

通過DPBDP 模型，得到含噪聲查詢集A( B )與真實查詢集f( B )，A( B )與f( B )作為訓(xùn)練樣本集T=＜f( B),A( B )＞通過LRPPP模型進(jìn)行訓(xùn)練，將產(chǎn)生的預(yù)測模型來預(yù)測新的未知查詢。假設(shè)用拉普拉斯方法直接對原始大數(shù)據(jù)集D 處理的真實查詢集為f( D )與含噪聲查詢集A( D )，通過DPBDP 模型對訓(xùn)練集所添加的噪聲要小于用拉普拉斯對直接對原始數(shù)據(jù)集D 添加的噪聲，因為原始數(shù)據(jù)集的f( D )中查詢之間相關(guān)，而f( B )中的查詢是從原始數(shù)據(jù)集中選出的相關(guān)性低的數(shù)據(jù)記錄，根據(jù)定義6，GSB比原始查詢集的敏感度GSD小，敏感度越小所添加的噪聲越少。

如算法1所示，執(zhí)行LRPPP模型主要分三個步驟：

（1）產(chǎn)生訓(xùn)練樣本集：通過MICFS 模型和DPBDP模型產(chǎn)生，產(chǎn)生訓(xùn)練樣本集T=＜f( B),A( B )＞。

（2）訓(xùn)練模型：利用線性回歸（Ridge Regression）算法訓(xùn)練樣本集T=＜f( B),A( B )＞訓(xùn)練預(yù)測模型M。

（3）進(jìn)行預(yù)測：將產(chǎn)生的預(yù)測模型M 用來預(yù)測新的未知查詢集fD，將輸出預(yù)測結(jié)果A( D )作為查詢集的含噪聲答案。

算法1 隱私保護(hù)預(yù)測模型發(fā)布算法

輸入：樣本集的查詢集f( B )，樣本集的含噪查詢集A( B)，隱私預(yù)算ε，原始數(shù)據(jù)集D。

輸出：隱私保護(hù)數(shù)據(jù)集A( D)。

1.產(chǎn)生訓(xùn)練樣本集T=＜f( B),A( B )＞；

2.使用線性回歸算法訓(xùn)練樣本集并產(chǎn)生預(yù)測模型M；

3.將原始數(shù)據(jù)集D 輸入到預(yù)測模型M，A( D)=fD(M)；

4.輸出隱私保護(hù)數(shù)據(jù)集A( D)。

當(dāng)生成預(yù)測模型M 時，可以由預(yù)測模型M 生成不消耗任何隱私預(yù)算未知的新查詢隱私保護(hù)答案。

4 實驗結(jié)果與分析

4.1 實驗設(shè)置

實驗從數(shù)據(jù)效用性與算法性能角度對比NIQDP、Laplace Mechanism（LM）[16]、Private Multiplicative Weights（PMW）Mechanism[17]、Matrix Mechanism（MM）[18]。實驗采用Boosting the accuracy of differentially private histograms through consistency[19]的Nettrace、Search Logs 與Netflix 數(shù)據(jù)集。本文實驗?zāi)Ｐ陀肞ython 語言實現(xiàn)。實驗單機環(huán)境為Intel Core i5 CPU 2.3 GHz，8 GB 內(nèi)存，Microsoft Windows 10 操作系統(tǒng)。

4.2 實驗分析

（1）數(shù)據(jù)效用性分析

實驗將NIQDP與LM、PMW、MM 這三種技術(shù)的效用性進(jìn)行比較、分析。除了傳統(tǒng)的Laplace Mechanism（LM）外，Private Multiplicative Weights（PMW）所做的工作是減少批查詢之間的相關(guān)性，Matrix Mechanism（MM）所用的是差分隱私中最常用的迭代發(fā)布方法，這兩種機制與本文所提的模型相同，只能處理范圍查詢，因此，只測試范圍查詢，隱私預(yù)算ε 的取值范圍為0.1到1。

如圖3 所示，觀察到NIQDP 在三個數(shù)據(jù)集的所有值上都有較低的MAE。在圖3（a）中，當(dāng)ε=0.3 時，NIQDP、LM、PMW 與MM 的MAE 為分別為21.982 1、105.570 5、70.097 1、63.643 2；當(dāng)ε=1 時，NIQDP、LM、PMW 與MM 的MAE 分 別 為5.519 8、31.645 2、21.439 6、18.761 9。

在圖3（b）、（c）中也觀察到了NIQDP 的改進(jìn)，由于用于回答測試查詢的預(yù)測過程不消耗任何隱私預(yù)算，而僅在訓(xùn)練查詢中添加噪聲，因此所提出的NIQDP 機制具有更好的性能。傳統(tǒng)Laplace Mechanism（LM）在回答數(shù)據(jù)集中的每個查詢時都消耗隱私預(yù)算ε，并且敏感度受到查詢集之間的相關(guān)性的影響，導(dǎo)致查詢答案不準(zhǔn)確。實驗結(jié)果表明NIQDP在回答大量查詢時的有效性。

在差分隱私方法中，隱私預(yù)算ε 體現(xiàn)了隱私機制能夠提供的隱私保護(hù)水平。從圖3 中還可以觀察到ε 對NIQDP 性能的影響，通過將隱私預(yù)算ε 設(shè)置為從0.1 到1，來評估NIQDP 在各種隱私保護(hù)級別的表現(xiàn)。隨著ε的增加，MAE評估變得更好，這意味著隱私保護(hù)水平越低，效用越好。

（2）算法性能分析

查詢集的大小在預(yù)測中起著至關(guān)重要的作用，實驗通過對查詢集的大小取值來測試對算法效率的影響。通過MICFS 模型選出1 000 個相關(guān)性低的數(shù)據(jù)記錄作為查詢集，將訓(xùn)練集m 的大小設(shè)置為100到1 000，在隱私預(yù)算ε=1 的情況下進(jìn)一步比較NIQDP、PMW與MM的執(zhí)行時間。

如圖4，觀察到NIQDP是三種機制中執(zhí)行時間最快的，三種機制的執(zhí)行時間與訓(xùn)練集大小m 沒有顯示出強相關(guān)性，PMW和MM的執(zhí)行時間隨著查詢大小m 的增加而增加。此外，NIQDP 的執(zhí)行時間對m 的變化不敏感。

5 結(jié)束語

圖3 數(shù)據(jù)效用性對比

圖4 算法性能對比

在隱私保護(hù)與大數(shù)據(jù)發(fā)布的研究中，使用差分隱私方法實現(xiàn)對大數(shù)據(jù)的隱私保護(hù)數(shù)據(jù)發(fā)布是目前的研究熱點。但現(xiàn)有的差分隱私方法在非交互式的大數(shù)據(jù)環(huán)境下實現(xiàn)大量查詢保護(hù)時，存在無法提供準(zhǔn)確查詢結(jié)果及有效處理大量未知新查詢的問題，針對這兩個問題，本文提出了NIQDP模型。該模型將數(shù)據(jù)發(fā)布問題轉(zhuǎn)化為機器學(xué)習(xí)問題，通過最大信息系數(shù)衡量數(shù)據(jù)之間的依賴關(guān)系，并提取相關(guān)性低的特征集作為訓(xùn)練樣本，對訓(xùn)練樣本集進(jìn)行隱私加噪，實現(xiàn)差分隱私保護(hù)后，通過線性回歸算法對其進(jìn)行訓(xùn)練產(chǎn)生預(yù)測模型，最終由預(yù)測模型發(fā)布滿足差分隱私的查詢答案。在真實數(shù)據(jù)集和合成數(shù)據(jù)集上都進(jìn)行了廣泛的實驗，結(jié)果表明所提出NIQDP模型性能均優(yōu)于傳統(tǒng)隱私保護(hù)模型。