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

許 斌，梁曉兵，沈 博

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

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

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

1 引言

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

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

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

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

2 預備知識

2.1 最大信息系數(shù)

最大信息系數(shù)（Maximum Information Coefficient）由Reshef[12]等人在2011年提出，它以信息論與互信息論為基礎用來檢測數(shù)據(jù)集中變量之間潛在的線性或非線性關聯(lián)關系，被廣泛應用于大數(shù)據(jù)的相關性分析，通過網(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 的邊緣概率密度，使用直方圖估計對上述的概率密度進行估計。

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

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

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

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

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

2.2 差分隱私

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

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

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

定義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 非交互式差分隱私保護模型

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

3.1 非交互式查詢差分隱私保護模型

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

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

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

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

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

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

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

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

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

圖1 非交互式查詢隱私保護模型

（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）重復步驟（4）直到選定特征的個數(shù)達到設定的值后，輸出包含選定特征的訓練樣本集B。

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

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

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

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

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

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

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

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

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

（1）k-塊劃分。將執(zhí)行MICFS 模型后產生的數(shù)據(jù)集B 應用k-means 聚類算法進行劃分成為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 及其相關記錄的值，得到鄰近數(shù)據(jù)集，并計算Di上查詢函數(shù)f 的敏感度。

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

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

3.4 基于線性回歸的隱私保護預測模型

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

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

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

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

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

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

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

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

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

2.使用線性回歸算法訓練樣本集并產生預測模型M；

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

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

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

4 實驗結果與分析

4.1 實驗設置

實驗從數(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ù)集。本文實驗模型用Python 語言實現(xiàn)。實驗單機環(huán)境為Intel Core i5 CPU 2.3 GHz，8 GB 內存，Microsoft Windows 10 操作系統(tǒng)。

4.2 實驗分析

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

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

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

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

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

（2）算法性能分析

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

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

5 結束語

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

圖4 算法性能對比

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