基于差分隱私的海量數據發布方法研究

顏 飛 張 興 李 暢 李萬杰 李 帥

(遼寧工業大學電子與信息工程學院 遼寧 錦州 121001)

0 引 言

隨著信息技術，特別是大數據技術和人工智能領域研究的飛速發展，海量數據的收集、存儲、發布和分析變得越來越容易。但從數據安全和個人隱私保護層面來看，大數據應用也帶來了很大的數據安全隱患。而且數據的安全和隱私數據的泄露不僅會影響到個人利益，甚至會威脅到國家的網絡空間安全。面對如此復雜的大數據背景，大數據面臨著諸多安全問題，其中如何從大數據中分析挖掘出更多的價值而又很好地保護數據的隱私安全顯得尤為重要[1]。

從個人隱私安全層面來看，一旦隱私信息被泄露，用戶個人隱私無異于“裸奔”。對于企業來說，確保用戶數據安全和隱私安全是必須面對和解決的問題，若數據安全和隱私保障存在問題，將會影響大數據和人工智能的進一步推廣應用。在未來發展中，如果國家在數據安全控制方面失去了主動權，那么必將受制于他人。因此，確保大數據安全和隱私安全十分重要，針對大數據安全和隱私保護的關鍵技術的研究值得更進一步探索，而且大數據安全和隱私保護也將逐漸上升至國家戰略層面。

為了有效地保護個人隱私安全，研究人員提出了許多隱私保護模型，例如基于匿名技術的K-anonymity[2]、L-diversity[3]、M-invariance[4]、T-closeness[5]等。由于以匿名為基礎的隱私保護模型均需特殊的攻擊假設和一定的背景知識，且未能對隱私保護強度進行量化分析，因此在實際應用中具有較大的局限性。尤其是在海量數據的背景下，用戶的原始信息可能在經過數據挖掘分析和深度學習的某個過程中被非法者破壞、攻擊和篡改，用戶信息的隱私安全面臨著嚴重的威脅[6]。因此，差分隱私[7]作為一種新型、輕量級的隱私保護算法，引起了研究人員的關注。它通過對發布數據進行隨意擾動，使得在傳統意義上無論攻擊者具有何種背景知識都無法識別一條記錄是否在原數據表中[8]，可以解決數據發布所隱藏的潛在隱私威脅。但針對海量數據的隱私保護數據發布往往會出現數據敏感度增大、隱私預算枯竭和數據噪聲過大等問題，對后期的數據分析造成較嚴重影響。并且在采用直方圖發布方法存在離群點導致數據高敏感問題，更容易泄露隱私。因此，針對離群點的分組劃分問題，文獻[9]在等寬劃分的基礎上提出了一個差值集的概念來處理在分組時由于離群點存在可能會導致的劃分誤差。該方法在面對充滿離群點的數據集時有著很好的表現，但在分組劃分階段需計算所有數據的差值集，對于大數據集來說差值集計算效率問題成為必須解決的問題。

研究人員在提高大數據集的計算效率方面也做了許多研究工作。文獻[10]采用高效的MapReduce并行計算模型實現了k-means聚類算法，有效提高了k-means算法的運行效率。針對云平臺的開放性使攻擊者擁有大量的攻擊背景知識[11]，攻擊者可以通過關聯背景知識和聚類結果來竊取數據隱私[12-13]。文獻[14-15]將隱私保護機制融入Hadoop平臺下的MapReduce分布式計算框架，實現了海量分布式數據的隱私保護算法。華為研究人員為滿足數據挖掘需求，實施部署了滿足差分隱私保護的大數據分析平臺[16]。

雖然MapReduce分布式計算框架的使用可高效處理海量數據，但該框架在算法迭代過程需多次讀寫硬盤數據，消耗大量I/O通信資源，并且過多的噪聲擾動也會增加隱私保護算法的復雜度開銷[17]。針對以上分析，為了提高數據隱私保護程度和數據的可用性，解決差值集計算效率問題，本文以海量靜態數據的發布需求為出發點，提出一種滿足ε-差分隱私保護的適用于Spark內存迭代的SPDP-GS(Spark Differential privacy-Grouping Smothing)算法。該方法可提高離群點判斷速度和差值集計算效率，并有效控制基于直方圖的數據發布方法中的離群點對數據發布的敏感度的影響，具有一定的應用價值和理論研究意義。

1 差分隱私保護理論

差分隱私保護主要通過對發布數據進行隨意擾動，使得攻擊者使用傳統方法攻擊時，無論擁有何種背景知識均無法輕易識別出某條記錄是否一定在原數據表中。

1.1 差分隱私定義

定義1對于給定的2個至多相差1條記錄的數據集D1以及D2，f為隨機算法，range(f)表示算法f的所有輸出構成的集合，S為range(f)的子集。若算法f滿足Pr[f(D1)∈S]≤eε×Pr[f(D2)∈S]，則算法f具有ε-差分隱私性。

其中，ε為隱私保護預算，代表算法的隱私保護水平，ε的取值越小，隱私保護水平越高。

1.2 Laplace噪聲機制

差分隱私保護的實現機制是采用數據擾動，數據擾動常用方法之一是采用Laplace[19]噪聲機制來實現數據加噪，該機制使用拉普拉斯分布所產生噪聲添加到真實輸出值中來實現差分隱私保護。

定義2對于任意一個函數f:D→Rd，算法Y滿足Y(D)=f(D)+。

其中，函數Lapi(Δf/ε)(1≤i≤d)表示拉普拉斯密度函數；Δf=maxD1,D1|f(D1)-f(D2)|為函數f(D)的查詢敏感度。D1、D2為兄弟數據集；d為查詢維度。

1.3 差分隱私組合特性

在差分隱私保護研究中，為證明算法滿足差分隱私，需滿足如下差分隱私組合特性：序列組合性和并列組合性。

性質1[19]給定數據庫D與n個隨機算法fi，且fi滿足εi-差分隱私，那么fi(D)序列組合滿足ε-差分隱私，且ε=∑εi。

性質2[19]設將給定數據庫D劃分成n個不相交的子集，D={D1,D2,…，Dn}，若任意算法fi滿足ε-差分隱私，則序列fi在D上的操作結果仍滿足ε-差分隱私。

2 Spark框架下SPDP-GS直方圖數據發布方法

為了提高對隱私數據的保護程度和挖掘結果的可用性，解決文獻[9]中差值集計算效率問題，以海量數據的統計特征為出發點，提出一種適用于Spark框架的滿足ε-差分隱私保護的海量靜態數據直方圖發布方法。

2.1 數據發布處理框架

本文提出一個滿足差分隱私保護需求的非交互式計算框架系統，其結構示意如圖1所示。該框架主要由3個部分組成：原始數據收集和存儲，Spark框架下的數據處理和存儲，數據的隱私保護處理。

圖1 Spark框架下差分隱私保護模型

數據管理層，首先將原始數據集導入HDFS進行數據的管理，然后數據從HDFS讀取到Spark框架形成RDD數據集，并進行map操作、執行join操作和Shuffle過程，最后將RDD處理結果輸出并保存到HDFS。

隱私處理，對待發布數據的隱私保護處理主要是借助Spark并行計算框架對經過預處理的數據進行分類統計、特征提取和聚類分組等計算任務，并對分組進行添加Laplace噪聲。

2.2 Spark框架下k-means并行化改進

1) 初始化k個初始聚類中心，形成樣本聚類。

2) 遍歷數據樣本，若boundDistance

3) 計算各聚類內數據均值，更新聚類中心。

4) 循環Step1-Step3，直到達到指定迭代次數或聚類收斂聚類中心不再變化。

5) 輸出聚類處理結果。

2.3 SPDP-GS算法設計

在大數據應用背景下，基于Spark框架的差分隱私保護直方圖發布方法主要目的在于滿足海量數據計算效率的要求下，提供有效的隱私保護方法。對于滿足差分隱私保護的直方圖發布方法，文獻[21]通過對數據集進行排序、分組以及求各分組均值，再添加Laplace噪聲。但是在可能會存在大量離群點數據集時，會導致隱私泄露，而且簡單的等寬分組方法容易導致誤差增大問題。所以，文獻[9]在文獻[21]的基礎之上提出了采用插值集概念處理分組過程中由于離散點問題而導致的劃分誤差問題。但該方法對于海量數據集的處理來說差值集的計算量巨大。

因此，本文提出了借助Spark平臺采用k-means改進算法對分組進行最優劃分，對每個分組求均值，再在各分組的平均數上添加Laplace噪聲，對隱私算法保護處理后的數據進行發布。基于Spark框架的SPDP-GS算法主要由：統計分類和DP-protection兩部分，主要步驟描述如下：

1) 采用Hash_map按屬性進行分類統計。

3) 采用Laplace機制添加噪聲：Y(D)=f(D)+lap(Δf/ε)。

4) 對待發布數據進行直方圖發布。

2.4 SPDP-GS算法描述

本節描述SPDP-GS算法包括：數據的類型統計、k-means聚類分組、分組求均值和添加Laplace噪聲，具體過程如下所述：

算法1k-means聚類分組劃分算法

輸入：經Hash_map算法統計分類后數據集D{x1,x2,…,xn}，聚類簇數k。

輸出：聚類分組C={c1,c2,…，ck}，組內均值ucj，組內數據數量numcj。

1)KMeansCluster(hashmapResult)

2) {Kmeans.setMax(k);

//設定聚類中心數k

3)

sourcedata=kmeans.loadData(hashmapresult);

//讀取統計分類結果數據集

4) fori=1 ton

5) { forj=1 tok

6) {

7) if (boundDistance

8) thenbestDistance←realDistance;

//計算xi與各均值向量uj距離

//將對應值加入相應簇

//更新均值向量

12)numcj=numcj+1;

//類內數據個數統計

13) }

14) }

15)result:RDD[(int,Ck)]; //聚類結果存入RDD

16) 輸出：組內均值ucj，組內數據數量numcj

17) }

算法2差分隱私直方圖發布

輸入：聚類分組C={c1,c2,…，ck}，查詢任務Q，查詢敏感度Δf(Q)。

輸出：滿足ε-差分隱私的數據集Dε。

1) 依據查詢任務f(Q)返回分組C中對應查詢記錄；

2.5 SPDP-GS數據發布方法

針對待發布數據集可能存在大量離群點導致隱私泄露風險增大和海量數據集的差值計算效率低的問題，滿足差分隱私保護的海量數據發布成為本文研究的著眼點。通常，數據集中難以避免地存在一些離群點，離群點的存在可能誘發隱私泄露和誤差增大問題。

例如，某疾病監控中心，需周期性更新某些疾病確診患者，而所發布數據又不能泄露確診患者年齡、住址等隱私信息。因此，可采用差分隱私保護方法對發布數據進行處理，數據隱私保護后再發布。實例具體說明如下：若將圖2(a)所示數據直接發布，擁有相關背景知識的人很容易推斷離散點數據的隱私信息。采用文獻[21]和本文所提出的方法將數據集D={32,28,43,45,48,2}進行分組劃分，可有效解決隱私泄露問題。

(a) 原始直方圖(b) 排序后直方圖

(c) 采用GS劃分 (d) 采用SPDP-GS劃分圖2 不同方法所得直方圖劃分圖

2.6 數據隱私安全性分析

2.6.1 隱私驗證

本文所述算法的隱私性主要從算法滿足ε-差分隱私的定義和性質角度加以論證。由于噪聲添加在分組劃分后的各分組之中，所以主要證明直方圖發布算法是否滿足ε-差分隱私。

定理1算法SPDP-GS滿足ε-差分隱私。

證明：由算法1中分組策略和噪聲添加方法可知，每次滑動窗口的經過將會產生d個分組，而每分組所分得的隱私預算為d/ε。差分隱私方法中敏感度Q設置為1，即Δ(Q)=1。假設數據集D1和D2最多相差一條記錄，即|D1-D2|≤1，|D2-D1|≤1。由定義1可知，Pr[f(D1=D′)]≤eε×Pr[f(D2=D′)]。由性質2可知該直方圖發布算法滿足ε-差分隱私。

2.6.2 數據可用性分析

本節所述算法采用聚類方法對數據進行聚類分組，將相似數組(相似分組指的是直方圖數值相近的若干個桶)劃分在一個分組內，并對同一分組內的數據以平均值表示。因此，發布數據會產生兩種誤差：一是由各分組均值產生的近似誤差SSE(Sum Squared Error)；二是因添加拉普拉斯噪聲而產生的誤差。

(1)

3 實驗設計與分析

3.1 實驗環境

本文實驗對算法的運行效率以及隱私保護數據的結果可用性進行考慮。實驗選取3臺主機搭建Spark平臺，每臺機器均為雙核IntelCorei3處理器，4 GB內存，操作系統選用Ubuntu，hadoop-2.7.2和Spark 2.2.0；JDK的版本是1.8.0_121，Scala-2.12.3。

本實驗所用數據集來自“Kaggle：The Home of Data Science”網站所以提供的Transactions商場交易數據，包括商品類型、品牌、交易日期、采購量和交易金額；另一個數據集為US Census 1990 raw data，該數據集包含了來自1990年美國人口普查數據(PUMS) 1%的樣本，詳細信息見表1。

表1實驗數據集

名稱大小/GB記錄數/個屬性類型數/個Transactions19.6349 655 790836US-Census8232 458 28568

3.2 數據預處理

本實驗選取交易數據集的category(商品類型)和US Census的age屬性作為數據處理對象。對數據集中category和age字段的各種商品類型進行統計。但category字段的值不應該為0值，因此需在數據統計過程中對取值為0的記錄予以清除，不納入統計。

3.3 數據可用性度量

本文選取選取交易數據集的category屬性和US Census的age屬性作為敏感屬性進行數據組劃分。主要采用和方差[23]和絕對誤差(AE)兩種評估標準度量算法的可用性。表達式如下：

(2)

首先，本實驗選取Transactions數據集，對隱私預算ε所產生的數據可用性的影響展開研究。實驗過程中分別取隱私預算參數ε為0.5、0.75、1和1.5。

圖3給出了隱私預算ε變化下絕對誤差的變化趨勢。結果表明，算法絕對誤差隨著隱私預算ε的增大而減少。而且，本文所述方法的隱私保護效果和數據可用性上相較于GS方法和S-GS方法更優。

圖3 不同ε值下的絕對誤差

接下來分別在Transactions和US-Census數據集上，通過改變離群點數量num來對AE結果進行研究,從而判斷本文所述方法與文獻[9,21]所述方法在數據發布結果可用性上的優劣情況。

實驗過程中ε取值設置為1.5，實驗結果如圖4和圖5所示。在Transactions和US-Census數據集上，存在隨著離群點的個數的增加，導致發布結果的絕對誤差增大的現象。由絕對誤差計算公式可得，離群點的數量的增多會導致分組劃分的誤差增大。本文方法比文獻[9,21]所述方法表現更好的主要原因為采用固定的分組劃分不可避免的出現離群點分組劃分不合理的問題，從而導致分組過程中誤差增大的問題。

圖4 數據集Transactions下不同離群點的絕對誤差

圖5 數據集US-Census下不同離群點的絕對誤差

3.4 算法時間效率分析

本文采用了對原始數據集進行Hash_map算法進行分類統計，將統計結果進行數據對外發布。而數據發布之前，對其中離散點的處理采用k-means聚類方法進行合理組聚類，對同一類內數據進行求均值，從而減少S-GS方法在大數據背景下的差值集計算量巨大的問題。

每組實驗分別做了5次測試，取5次平均時間作為最終結果，如圖6所示。

圖6 算法時間效率

由圖6可知，Spark平臺參與運算的子節點數量越多，算法執行時間顯著減少，說明Spark平臺可以較好地解決大數據的運行效率問題。采用Spark平臺進行差分隱私數據發布可有效保證發布數據的隱私安全及運算效率。

4 結 語

為了提高隱私數據的保護程度和保證數據挖掘結果的可用性，解決海量靜態數據直方圖發布過程中差值集計算效率低、存在隱私泄露安全隱患問題，研究了大數據背景下的差分隱私保護數據發布方法，提出一種Spark框架下的滿足差分隱私保護的直方圖數據發布方法。本文借助Spark計算平臺實現對海量數據的分類統計、聚類分析和分析結果的差分隱私保護。文中給出了數據處理的計算框架，并對各部分做了簡要闡述。通過對實驗結果中的總體誤差和隱私預算ε進行分析，相較于GS方法和S-GS方法數據可用性上更佳，而且解決了S-GS方法在海量數據計算中的差值集計算問題，滿足數據隱私安全性需求，同時保證發布數據具有較好的可用性，具有一定的應用價值。