基于分布式多關聯屬性的高維數據差分隱私保護方法

褚治廣，李俊燕，陳 昊，張 興

(1.北京工業大學 信息學部，北京 100124；2.遼寧工業大學 遼寧省工業互聯網網絡與數據安全重點實驗室，遼寧 錦州 121001)

0 引 言

在大數據的背景下，數據比以往更加的復雜，現實生活中更多的數據以高維的形式呈現。為此，充分挖掘高維數據的有用信息已經成為研究的熱點，但目前在對高維數據進行挖掘時常常忽略隱私的重要性，從而導致大量用戶隱私泄露。另外，通過關聯規則對高維數據進行挖掘的過程中，不僅要考慮敏感屬性還要考慮多種關聯屬性的影響[1]。例如，城市醫療大數據除了姓名、收入、家庭住址、疾病等敏感屬性，一些通過關聯分析得到的關聯屬性如階級層級、購物傾向等也會間接暴露患者的隱私信息，從而對病人的生活和身心健康造成危害。因此，如何確保在高效挖掘高維數據的同時保證用戶的隱私不被泄露成為日趨關注的焦點。

高維數據分析離不開降維[2]，文獻[3]利用Pawlak屬性約簡算法求出核屬性并通過啟發式擴展得到一個約簡，該約簡算法可有效剔除高維數據中的冗余信息，得到分類規則，但核屬性求解過程很麻煩。文獻[4]針對醫療數據，結合差分隱私和粗糙集提取規則，提出了一種挖掘醫療數據隱藏模式并保證患者隱私的新方法(DPRers)。該算法在數據挖掘過程中增加拉普拉斯噪聲實現差分隱私保護。只考慮了屬性之間的隱藏特性，針對關聯屬性沒有考慮，且上述方法對于高維大數據不能有效的處理。在分布式環境下，歐陽佳等[6]提出了一種基于差分隱私的數據發布方法，該方法采用分類討論的思想，提高了數據的可用性。即對全局采用安全數據積協議，對局部運用基于組合的定理。文獻[7]在分布式Hadoop框架下進行并行計算實現差分隱私關聯規則挖掘算法，但因為Hadoop不是內存級別的處理方式，每次讀取都需要存入HDFS中，存在大量IO操作，耗時較長。目前已有多種高維數據隱私保護方法[11-15]被提出，但隱私性和效用性仍無法有效平衡。文獻[8]針對多源數據，以樹結構優化存儲，先利用頻繁項集發布數據，再使用拉普拉斯機制和指數機制在數據發布的過程中進行保護，提高了發布數據的安全性，但該方法隨著數據擁有者的增多，噪聲的添加量也隨之增加，從而使得數據的效用性降低。因此文獻[9]利用啟發式截斷來降低全局敏感度，從而提高算法的可用性。同年，何文竹等[10]利用信息熵實現了結構化數據集的敏感屬性的分類分級保護，同時兼顧屬性的相關性和關聯關系，但該方法在大規模數據集中的表現不佳。

由上可知，當前高維數據發布方法都存在一些缺陷，一方面高維數據存在維度災難，導致一些傳統的數據挖掘方法很難起作用且處理效率很低，另一方面數據維度越多，數據的關聯性也會越高，會存在通過關聯數據推測出其它數據的危險，使用傳統的差分隱私進行保護，其保護水平往往很低，原因是維度越高的數據使用的噪聲越多，過多噪聲會造成數據的嚴重失真，并且可能會破壞屬性間的關聯性，可用性效果就會變差。因此我們提出一種基于分布式的多關聯屬性高維數據隱私保護方法(HDMPDP)，文章的貢獻主要有：

(1)本文利用主流的Spark分布式處理框架在分布式條件下，采用分塊的處理方式，利用鄰域粗糙集理論實現高效的數據降維同時提高了數據的處理效率。

(2)利用改進的關聯分析方法提取數據間的關聯規則，在關聯數據類中，針對敏感數據，使用敏感度劃分隱私保護的需求等級，并采用屬性信息熵作為敏感度衡量標準。

(3)應用信息熵對虛假的關聯屬性進行剔除同時對前面得到的不同屬性關聯度進行劃分，從而使添加的噪聲更合理。實驗驗證，HDMPDP方法在分布式條件下，通過上述兩方面的處理，在得到更加有效規則的情況下也能有效提升高維數據的隱私保護程度。

1 差分隱私

差分隱私保護方法通過對輸出的結果添加適當的噪聲實現對原始數據集的擾動，消除掉數據的個性特征，保護數據的隱私。差分隱私嚴格的數學定義如下：

定理1ε-差分隱私(ε-differentail prvacy)：對兄弟數據集D1和D2(相差一條記錄)，及其所有子集S，有隨機算法A，滿足式(1)

Pr[A(D1)∈S]≤eεPr[A(D2)∈S]

(1)

則算法A滿足ε-差分隱私，稱ε為隱私預算(衡量隱私保護程度)。差分隱私可以通過拉普拉斯機制(數值型)和指數機制(離散型)等進行實現。拉普拉斯機制通過添加噪聲，指數機制根據敏感度和隱私預算，計算各數據的權重進行選擇發布。兩種機制都依靠全局敏感度，接下來將介紹全局敏感度。

定義1 全局敏感度(global sensitivity)：給定查詢函數，D為輸入數據集，f(D) 為輸出數據集。在任意一對D1和D2上，函數的全局敏感度如式(2)所示

(2)

定理2 拉普拉斯機制(Laplace mechanism)：給定數據集D和隱私預算ε，函數f的全局敏感度為Δf，當f的輸出滿足

A(D)=f(D)+Lap(Δf/ε)

(3)

則稱算法A滿足ε-差分隱私，其中Lap(Δf/ε) 為滿足Laplace分布的隨機噪聲。Laplace分布如圖1所示。

圖1 Laplace分布

2 分布式多關聯屬性隱私保護方法

HDMPDP方法與文獻[15]中提到的基于Hadoop處理方案不同，Spark是基于內存級別的高效處理方案，避免了把中間過程存儲到分布式文件存儲HDFS中，從而較少大量IO操作能有效提高算法的執行效率，如圖2為Spark運行架構圖。因此本方案擬在分布式計算框架Spark中進行實現，針對高維數據計算開銷大，運算速度慢的情況，采用多處理機進行計算，提高運行效率的同時，更符合現在化的處理模式。

圖2 Spark運行架構

2.1 基于分布式的粗糙集降維

搭建Spark集群利用分布式計算框架如圖2所示，采用RDD(彈性分布式計算)的數據結構，把采集到的數據集保存在內存中，并且通過控制數據集的分區來達到數據存放處理最優化，這里分成多個Block，再針對每個Block分別進行數據的降維處理。

粗糙集理論是用于處理不確定關系的一種數學工具。將粗糙集用于高維數據降維能更好的保持原始數據的數據結構不丟失，但它僅適用于離散型數據，對于連續型數據并不適用。于是針對連續性數據采用鄰域粗糙集來擴展粗糙集的引用范圍，在粗糙集理論中，知識的表達是用決策系統表示的，一個決策系統由一個四元組表示

DS=(U，A，V，f)

其中論域U代表全體對象，A為屬性全體，V則為屬性的值域，f代表一個信息函數。具體含義可見文獻[3]。

于是對于每一個Block首先將數據分成離散型和連續型兩類，對于離散型數據根據粗糙集理論中不可區分關系與等價類的定義，計算出每個屬性的等價類；然后根據式(4)和式(5)計算得到每個屬性針對其它不同取值屬性的上、下近似

(4)

(5)

其中，R為A的任意一個子集，且 [x]R={y∈U|(x，y)∈R}。 在這里數據屬性間的關聯性可以用粗糙集中屬性依賴度k進行定量的度量(k=1表示D完全依賴C，k=0表示兩者沒有依賴關系)，由式(6)計算得到各個屬性的屬性依賴度關系再針對不同的屬性添加合理的噪聲。假設B?C， 定義決策屬性集合D對B的屬性依賴度的公式為

(6)

再利用式(7)計算互信息量，求出相對核CORE。采用互信息的屬性約簡算法可以有效把高維數據中不相關的冗余信息剔除，得到更合理分類規則，對于連續型數據則采用鄰域粗糙集實現屬性約簡過程

I(C，D)=H(D)-H(D|C)

(7)

采用粗糙集理論實現高維數據降維的同時，利用屬性間的依賴度作為屬性關聯度。根據所需數據維度以及分類效果設置不同閾值δ1， 計算得到的屬性之間的關聯度進行屬性分類。

2.2 基于信息熵改進的關聯分析

通過關聯分析挖掘將發現大量存在于數據集中隱藏關聯性的信息，進而得到某些能推測出敏感屬性的關聯屬性集，為此，可對該屬性集添加合理噪聲從而實現差分隱私保護。

一般關聯分析包含兩個過程：即從數據集中尋找頻繁項集(支持度)，從頻繁項集中生成關聯規則(置信度)。

支持度：某項集在數據集中出現的概率

support(A)=count(A)/count(dataset)=P(A)

置信度：項集A發生時，則項集B發生的概率。置信度體現的是關聯規則的可靠程度，如果關聯規則{A->B}的置信度較高，則說明當A發生時，B有很大概率也會發生，這樣就可能會帶來研究價值

Apriori算法是經典的關聯分析算法，一般只用于單維、單層的關聯規則，對多維的規則并不適用。就多維數據而言，常采用FP-Tree算法得到多維規則，可以更加高效的挖掘頻繁項集，但仍存在挖掘時間較長且有大量無效或冗余規則的問題，因此本文在分布式環境下采用屬性信息熵優化針對粗糙集降維后的數據進行二次篩選，剔除冗余項，提高算法的執行效率。

在分布式條件下對于每一個Blcok實現屬性分組后，再進行一次改進的滿足差分隱私的關聯分析，目的是尋找各個Block對應項目集合或對象集合間的頻繁模式、關聯性。屬性信息熵H(P)常常用來描述信息出現的不確定程度，如式(8)所示

(8)

式中的對數一般取2為底，單位為比特。

針對高維情況，假設一事件由n個維度屬性描述，則它第i個維度屬性信息熵用式(9)中的Ei表示

Ei=-∑x∈XiPi(x)log2(PI(x))，i=1，2，…，n

(9)

式中：Xi代表第i個指標的屬性集合，Pi(x) 是第i維中x發生的概率。

在關聯數據類中，針對敏感數據，將根據敏感度劃分隱私保護的需求等級，采用屬性信息熵作為敏感度衡量標準。利用屬性信息熵對不確定性進行度量，剔除虛假的關聯屬性還可以對前面得到的不同屬性關聯度進行劃分，設置分類閾值δ2， 對大于閾值的規則進行剔除，從而保證規則的有效性。

2.3 算法描述

本文提出的算法專注于高維數據集中屬性數據的發布。整個處理流程主要包含兩大環節。首先，在分布式環境下，運用經過優化的粗糙集理論對原始數據集實施降維操作，以降低數據處理的復雜性和計算成本。其次，本文采用經過改進的關聯分析算法，并結合差分隱私技術，對經過降維處理的數據集進行噪聲添加，確保輸出的數據集滿足差分隱私保護要求，從而在保證數據可用性的同時，有效保護用戶的隱私信息。整體流程如圖3所示，算法具體流程如下：

圖3 算法流程

算法1：基于分布式的粗糙集降維

輸入：DS，Blcok數，閾值δ1

輸出：降維后的數據集O

(1)對DS按照輸入的Block數進行劃分，把連續型和離散型劃分到不同的Block中；

(2)根據粗糙集理論中不可區分關系與等價類的定義，計算出每個屬性的等價類；

(3)針對每個Block遍歷每個屬性，得到相應屬性的等價類，利用式(4)和式(5)，計算每個屬性相對于其它屬性的上近似和下近似，以確定它們的等價類；

(4)由式(6)計算得到屬性依賴度，用屬性間的依賴度作為屬性關聯度；

(5)由式(7)計算互信息量，令O為空，求出COREC(D)；

(6)根據所需數據維度以及分類效果設置不同閾值δ1， 根據計算得到屬性之間的關聯度，實現屬性的分類；

(7)在每個Block中得到分類子集，直到屬性關聯度小于δ1， 返回降維后的屬性集O；

(8)算法結束。

算法2：基于信息熵的關聯分析和敏感屬性集的差分隱私保護

輸入：降維后的數據集O，最小加權支持度min_sup，置信度，閾值δ2

輸出：滿足差分隱私的數據集O′

(1)對降維后的數據集O針對每一個Block進行關聯分析；

(2)采用改進的FP-Growth算法進行關聯數據挖掘，掃描數據集O；

(3)由式(9)計算不同Block中的屬性信息熵，根據其維度進行加權處理，由min_sup生成頻繁1-項集；

(4)掃描數據集，若有相同子節點則支持度計數加一，否則新建一個節點。最終生成一棵FP-Tree；

(5)由FP-Tree挖掘遞歸生成頻繁項集，根據設定的置信度，生成關聯規則；

(6)同時，根據屬性信息熵，對小于閾值δ2的無效規則進行剔除；

(7)將粗糙集和信息熵得到的屬性和關聯分析得到的關聯屬性分別進行加噪。得到與敏感屬性關聯度高的非敏感屬性數據，并將噪聲平均分配到其每一個屬性中。對于非關聯數據類中的敏感數據，按照設定隱私保護需求等級的比例將噪聲分配到敏感屬性；針對屬性無關的非敏感數據，則不添加噪聲。

(8)生成滿足差分隱私的數據集O′。

3 實驗結果與分析

3.1 實驗環境與數據集

為了測試本文算法的性能，實驗使用Java實現，搭建Hadoop 2.7.2和Spark 3.0分布式集群，節點個數為4，在3.30 GHz GPU、16RAM的Centos7.0操作系統上運行，采用1994年美國人口普查真實數據集Adult數據集，數據集樣本數量為45 222個，每個樣本包含15個屬性信息。其中有6個連續型屬性，9個離散型屬性。Adult數據集見表1。

表1 數據集

3.2 算法評估標準

本文在分布式條件下綜合考慮了數據間的多種關聯關

系，包括屬性關聯性和規則關聯性再結合差分隱私技術添加合理的噪聲實現多維數據的隱私保護數據發布，因此實驗主要分析算法的數據可用性、隱私保護程度和執行效率等因素。

針對數據可用性方面采用誤分率進行衡量，即原始數據集上的查詢和添加噪聲后查詢的絕對值和累加和。error值越小，表明原始記錄與差分隱私保護后的誤分類越低，數據信息損失越少。如式(10)所示

(10)

式中：e(A*) 和e(A) 分別代表有無噪聲添加。

針對隱私保護程度方面采用數據披露風險記錄關聯(RL)來度量，即采用差分隱私處理后的數據集正確匹配原始數據記錄的比例，如式(11)所示

(11)

式中：O′代表差分隱私保護后的數據記錄，如果不在記錄中則Pr(O′)=0，n為記錄數。經差分隱私保護處理后的記錄與原記錄之間的匹配率越低，表明兩者關聯性減弱，數據信息泄露的風險將越低。即RL值越小，數據信息泄露的可能性越小，保護性越好。

針對執行效率方面采用加速比來測試算法的并行效率。即在相同任務量下，單一處理器與多處理器花費時間的比值。該值越大表示并行計算過程中所消耗的時間越少，執行效率越高。如式(12)所示

(12)

式中：Ts和Tc分別代表單機和集群的運行時間。

3.3 實驗結果與分析

針對HDMPDP算法，設定隱私預算ε分別為0.01，0.3，0.6，0.8，1.0。一般隱私預算越小說明數據中注入的噪聲越多，隱私保護程度越高，數據損失就越大。對比OBDP和PrivBayes算法進行實驗對比，兩者均采用貝葉斯網絡實現高維數據的降維，前者是對后者采用互信息優化貝葉斯網絡的構建過程。則3類算法造成的誤分類Error如圖4所示。

圖4 ε取不同值時，Error變化情況

圖4展示了3類算法在不同隱私預算下的分類誤差。實驗結果表明，隨著隱私預算的增加，3類算法的隱私誤差都呈現減小的趨勢，隱私保護程度都在增加。本文的HDMPDP方法稍優于其它兩種方法，因為該算法只針對敏感屬性和滿足一定條件的非敏感屬性進行了隱私保護處理，考慮到不滿足條件的非敏感數據對隱私泄露的影響較小，無需再分配額外的隱私預算，數據集整體添加的噪聲量減少，數據的效用性也隨之增加。

為了驗證本文提出算法的有效性，使用此算法驗證發布數據的可用性和數據信息的安全性，將HDMPDP算法與同類算法在Adult數據集上進行對比，衡量指標為信息損失大小和數據泄露風險。實驗設置設定隱私預算分別為0.01、0.2、0.4、0.8、1.0，分別對比HDMPDP算法與基于Hadoop算法的RL值，結果如圖5所示。

圖5 ε取不同值時，RL值變化情況

由圖5可知，當隱私預算ε設定為0.01時，RL值達到最低點，表示此時隱私泄露的風險最小。這是因為在數據中加入了大量的噪聲，從而保護了隱私。然而，這種大量的噪聲也導致了數據可用性的降低。當隱私預算增加到0.2和0.4時，無論是采用本文提出的HDMPDP算法還是傳統的Hadoop算法，RL值都相近，表明兩種算法在此時的隱私保護效果相當。當隱私預算超過0.4后，隨著預算的增加，RL值急劇上升，這意味著數據泄露的風險也隨之增大。但本文算法的數據泄露風險還是較低些，因此綜合考慮數據可用性和數據泄露風險，本文的HDMPDP算法在取0.4時算法性能最優。

為驗證HDMPDP算法執行的效率，本節對其算法加速比進行衡量。我們取在隱私預算為0.4的情況下，分別在數據集下將HDMPDP算法與基于MR的算法的運行時間進行對比，獨立運行10次后各取其平均值。通過對比運行時間，可對HDMPDP算法的性能進行評估，結果如圖6所示。

圖6 節點數對加速比的影響

從圖6中可以看出，隨著節點數量的增多，HDMPDP算法產生了較高的加速比，運行時間不斷減少，性能表現最佳。由此可說明本文使用的Spark框架分布式計算在迭代運算效率方面高于MapReduce框架。

4 結束語

本文研究了高維數據多關聯屬性的隱私保護問題，提出了一種新的分布式環境下針對高維數據和多關聯屬性的隱私保護方法(HDMPDP)。首先采用Spark框架對傳統的降維方法進行了改進，利用互信息進行第一次特征篩選，使用屬性間的依賴度作為屬性關聯度，減少降維過程中的信息損失，同時提升處理效率。其次在降維后的數據處理階段，本文運用了基于信息熵優化的關聯分析方法進行深入挖掘，為了確保數據隱私不被泄露，對分類后的數據集進行差分隱私保護。通過實驗驗證，本文提出的HDMPDP算法與同類算法相比，能在保證數據泄露風險較小的情況下，提升算法的運行效率，提高數據的可用性。但是本文在算法的優劣評價，沒有一個明確的標準。對于評價標準的確定有待日后的進一步研究；并且文中針對隱私預算的分配采用了均分原則，這樣可能會造成隱私預算分配的不合理從而降低隱私保護的效率。因此，下一階段主要研究的目標是，設計不同的隱私分配方案以及再更加復雜的數據集上解決高維數據的發布效率問題。