改進成分分析的差分隱私高維數據發布方法

褚治廣 張 興 張青云 李曉會 李萬杰

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

0 引 言

目前,許多數據收集機構需要將所收集原始數據(例如醫療數據、金融數據等)發布出去,以便于數據分析、挖掘,能夠從發布的數據中產生更為有效的決策支持。然而,發布的原始數據中涉及了大量的個人敏感信息,直接發布數據會致使個人隱私的嚴重泄露。因此,數據發布者需要通過特殊的保護技術處理隱私數據后將數據發布出去。

現階段,主要的隱私保護數據發布技術大致上分為三類：1) 基于數據加密的發布技術。例如AES加密、RSA加密等。2) 基于限制條件的發布技術。根據原始數據特性,有選擇性地發布含有敏感數據的數據,例如：k-匿名模型[1-3]、l-多樣性模型[4]、t-近似模型[5]等。3) 基于數據失真的發布技術。使得隱私數據失真的同時,保持原始數據的某些特性。這樣的技術主要有：隨機擾動[6-8]、凝聚[9-10]、交換技術[11]、注入噪聲[12-13]等。

作為基于數據失真的差分隱私保護技術,已成為隱私保護重點研究方向之一?，F階段,對于數據發布的研究主要聚焦于一維或低維數據。然而,這些數據發布方法均不適用于高維數據的發布,無法解決在處理高維數據發布時,隨著維度和維度值域的增加,形成的發布空間以指數型增長,遭遇“維度災難”的問題。因此,如何為數據研究者提供大量有效信息的同時,利用差分隱私技術保證原始高維數據的隱私安全變得極具挑戰。

基于此,本文提出一種基于改進成分分析的差分隱私高維數據發布方法(ICAHDP),使得數據隱私信息不被泄露的同時,發布的數據更好地接近原始數據。本文的主要貢獻總結如下：

1) 提出一種滿足差分隱私的主成分分析優化的高維數據發布方法(ICAHDP),減少了處理數據的時間和空間開銷,提高發布數據的可用性。正式證明ICAHDP滿足差分隱私。

2) 在ICAHDP中,為了降低成分分析方法在降維過程中的時間和空間成本,提出一種優化主成分分析(PCAO)的方法。利用屬性重要性對屬性進行過濾,壓縮數據空間,從而優化了高維數據降維時占用空間大、處理時間長的問題。此外,為了解決優化算法中主成分數量(k)的選取問題,引入基于互信息的評價機制對原始數據和已發布數據進行評價,確定最優k。

3) 考慮了高維數據中多敏感屬性的存在,而傳統的隱私預算分配方法不能滿足個性化的隱私保護。將敏感偏好度和最優匹配理論相結合,設計了敏感屬性層次保護策略,使高維數據在不同隱私要求下能夠發布。

4) 對不同的真實數據集進行廣泛的實驗。實驗結果表明,與PrivBayes[14]和JTree[15]等方法相比,ICAHDP不僅保證了已發布數據集的隱私性,而且顯著提高了數據的準確性和實用性。

1 相關工作

目前,對于高維數據發布方法的研究,已有少量研究成果[14-20],然而這些方法都存在著一些問題：

文獻[14,16-17]是基于概率圖模型的高維數據發布方法。其中,PriView[16]算法構建k個屬性對的邊緣分布,然后估計出高維數據的聯合分布。該方法假設數據中的所有屬性對相互獨立,均等地處理屬性對,然而在實際的高維數據集中,屬性之間大都存在相關性。Zhang等[14]提出的PrivBayes算法使用指數機制滿足差分隱私條件下,結合貝葉斯網絡近似屬性之間的聯合分布,生成高維數據集。然而利用指數機制挑選屬性對時,受到候選空間的大小的制約。候選空間越大,指數機制挑選屬性對的精度越低。Chen等[17]在上述方法的基礎上,提出了JTree算法。該算法采用稀疏向量技術尋找屬性對的關聯性,通過聯合樹構造屬性關系圖所確定的邊緣分布估計相應的聯合分布。然而稀疏向量技術不滿足差分隱私[15],致使JTree算法不能滿足差分隱私的要求。文獻[18]是基于投影技術的高維數據發布方法。PrivPfC[18]算法結合投影直方圖和卡方關聯測試達到高維數據發布的目的,然而,投影直方圖并沒有考慮到屬性之間的相關性,導致發布精度較低。Hb[19]算法結合直方圖技術和層次樹發布高維數據,但是當數據維度較高時,該方法發布的數據實用性越來越低。Jiang等[20]提出一種基于主成分分析的差分隱私數據發布方法,該方法首先構建噪聲協方差矩陣,然后通過還原加噪后的投影矩陣來發布數據。然而在構建噪聲協方差矩陣時浪費了一部分隱私預算,而且該方法在處理屬性維度較大的數據時,處理時間無法滿足實際要求。

基于以上分析,本文提出一種改進的成分分析優化的差分隱私高維數據發布方法ICAHDP。該方法通過引入屬性重要度和互信息評價機制對PCA進行優化,利用優化后的主成分分析法(PCAO)對數據進行降維。在數據降維的過程中,設計了個性化的拉普拉斯機制,既保證了ICAHDP滿足差分隱私的要求,又使隱私保護更加靈活。理論分析表明,所提的ICAHDP算法滿足ε-差分隱私。實驗表明,與現有的研究工作相比,ICAHDP算法產生的數據集的數據效用性均優于PrivBayes、DPPro和JTree等算法。

2 相關定義

2.1 差分隱私

差分隱私保護技術通過向原始數據集的轉換或其統計結果添加噪聲來達到隱私保護的目的。該方法確保了在任一數據集中更改一條記錄的操作而不影響查詢的輸出結果。此外,該模型可以抵御攻擊者掌握了除某一記錄外的所有信息的背景知識攻擊。

定義1差分隱私[21]。給定兩個數據集D和D′,二者完全相同或者至多相差一條記錄,給定隨機算法A,Range(A)表示A的值域,S為Range(A)的子集。如果A滿足式(1),則算法A滿足ε-差分隱私。

Pr[A(D)∈S]≤eε×Pr[A(D′)∈S]

(1)

式中：概率Pr[·]表示算法的概率,由算法A決定;ε為隱私預算,表示算法A的隱私保護程度,ε的值越小,A的隱私保護程度越高。

實現差分隱私保護常介入兩種噪聲機制,分別是拉普拉斯機制和指數機制[22]。本文主要采用Laplace噪聲機制。

定義2Laplace機制[22]。給定數據集D,對于任一查詢函數f：D→Rd,其敏感度為Δf,則隨機算法A(D)=f(D)+Y提供ε-差分隱私保護。其中,Y～Lap(Δf/ε)為隨機噪聲,表示Y是服從尺度參數為Δf/ε的Laplace噪聲分布。

Laplace機制[23]通過將服從Laplace分布的噪聲介入準確的查詢統計結果來達到ε-差分隱私保護的目的。設Laplace分布Lap(b)位置參數為0的概率密度函數為p(x),其表示形式為：

(2)

2.2 信息熵與互信息

1948年,Shannon將熱力學的熵引入信息論,提出了“信息熵”的概念,解決了信息度量的問題。信息熵表示事件中包含信息量的平均量。信息熵越高,表示包含的信息量越大;反之,信息熵越小,表示包含的信息量越少[24]。信息熵的定義為：

定義3設X是一個離散型隨機變量,則X的信息熵為：

(3)

式中：p(x)表示x發生的概率。

互信息[25](Mutual Information)是2個或2個以上隨機變量間相互依賴性的量度。它度量兩個事件之間信息量的相關性?；バ畔⒌亩x為：

(4)

式中：X和Y表示兩個離散隨機變量;p(x,y)表示X和Y的聯合概率分布函數;p(x)和p(y)分別為X和Y的邊緣概率分布函數。

由式(3)和式(4)推導可得互信息與信息熵之間的關系：

I(X,Y)=H(X)+H(Y)-H(X,Y)

(5)

2.3 主成分分析法

主成分分析法[26](PCA)是通過對多個原始隨機變量組成的數據集X={x1,x2,…,xn}的協方差矩陣進行分解,重新組合轉變為少數幾個各維度間互不相關的變量Q={y1,y2,…,ym},m

3 改進的高維數據發布方法

3.1 問題描述

在高維數據發布時,現有的大多數方法都會遭受維度“災難”的問題,引入較大的噪聲,導致發布的數據的可用性很低。因此,在高維數據發布中,設計出既能解決維度災難帶來數據可用性較低的問題又能滿足數據隱私安全的發布方法是亟需迫切的。本文提出一種基于主成分分析優化的差分隱私高維數據發布保護方法,對高維數據進行降維優化及隱私保護,經該方法產生的發布數據滿足：1) 具有較好的數據效用,利于數據挖掘、分析操作等;2) 滿足差分隱私保護,為數據提供最優的隱私保護效果。

3.2 高維數據發布機制

改進的成分分析優化的差分隱私高維數據發布方法的運行機制如圖1所示。

圖1 成分分析優化的差分隱私高維數據發布框架

基于主成分分析優化的差分隱私高維數據發布方法具體的步驟如下：

1) 首先確定屬性重要度閾值,對原始數據中的屬性進行篩選,將原始數據中的無用屬性和缺失值較多的屬性剔除。

2) 對經過屬性篩選后的數據,利用主成分分析法對數據進行降維。對降維過程中,對產生的投影矩陣加入Laplace噪聲,使得數據滿足差分隱私。

3) 在滿足差分隱私的前提下,對數據屬性的敏感偏好進行分級,并結合最優匹配理論來分配隱私預算。將不同大小的噪聲添加到數據集中不同敏感偏好的屬性中,實現個性化的噪聲添加方法,使發布的數據具有更好的可用性。

4) 在數據的降維過程中,進行多次的主成分個數k值的選取,通過互信息評價機制,計算原始數據與加噪數據的互信息,確定最優的k值,從而確定最佳的發布數據。

3.3 篩選屬性

本文算法通過計算屬性的信息熵,作為屬性重要度衡量指標,利用屬性重要度閾值,對屬性進行篩選。

信息熵應用于衡量屬性“重要”程度時,該屬性的信息熵越大,表示該屬性包含的信息量越多,則屬性的“重要”程度越高;反之屬性的信息熵越小,表示該屬性包含的信息量越小,屬性的“重要”程度越低。在數據降維時,盡可能保留屬性重要度越高的屬性,剔除重要度越低的屬性。在衡量屬性保留或者舍棄時,本文以屬性重要度閾值Th作為界限。閾值的確定采用以下方案：

計算選擇的屬性在數據中所占的比重。計算式如式(6)所示。

(6)

通過計算數據集中各個屬性的信息熵,按照重要度大小排列屬性,以屬性重要度閾值作為界限,屬性的重要度大于閾值時,說明該屬性包含的信息量多于閾值下的信息量,在數據降維時保留該屬性;反之屬性的信息熵小于閾值時,表示該屬性包含的信息量少于閾值下的信息量,在數據降維時剔除該屬性。

3.4 數據降維加噪

若數據集D經篩選屬性后產生的數據集為Do,利用主成分分析法對其進行降維,降維過程如下：

計算樣本的協方差矩陣：

(7)

對協方差矩陣進行特征分解：

Cov=UTCU

(8)

式中：C表示Cov特征分解后的對角矩陣;U表示特征值所對應的特征向量構成的特征矩陣。

選取k個特征值所對應的k個特征向量組成矩陣Uk,將原始數據投影到矩陣Uk上,得到投影矩陣：

(9)

在投影矩陣Z中添加Laplace噪聲,得到噪聲矩陣Zo。

還原得到原始數據矩陣的低階近似矩陣：

(10)

在投影矩陣上添加Laplace噪聲,由于用戶對自身數據的隱私需求不同,不同的屬性的敏感程度不同,因此需要為不同的敏感屬性添加不同的噪聲量,提供不同的隱私保護程度。本文設計了個性化地添加噪聲的策略。

定義4敏感屬性偏好。敏感屬性偏好表示用戶對敏感屬性數據的重視程度。即同意哪些屬性被披露,禁止哪些屬性被披露。

定義5敏感偏好度。為了便于在隱私保護過程中定量分析敏感屬性的偏好,需要對敏感屬性偏好進行量化,用于表示敏感屬性的重要程度,稱為敏感偏好度SP。設數據集D中存在n個敏感屬性{P1,P2,…,Pn},敏感屬性pi的數據不愿被披露程度權重作為pi的敏感偏好度spi。

由每一個敏感屬性敏感偏好度spi組成DSP={sp1,sp2,…,spn}為D的敏感偏好度集合,其中spi為[0,1]區間中的一個數值。

敏感偏好度反映了數據擁有者要求對敏感屬性數據進行保護的傾向程度,可以由數據擁有者的主觀評價或敏感程度而確定。敏感偏好度越大,該敏感屬性的隱私保護需求越高,反之,敏感偏好度越小,該敏感屬性的隱私保護需求越低。

根據敏感屬性敏感偏好度值spi,將敏感屬性劃分為m個等級,對應m個隱私保護強度。差分隱私保護強度與隱私預算有關,每個等級對應一個隱私預算,如表1所示。

表1 敏感屬性等級與隱私預算對應表

定義6隱私造價。設Tij=Gi×εj是隱私預算為εj對于隱私保護強度Gi對應的敏感偏好等級的隱私造價。

定義7最優匹配。設有二部圖(x,y),如果找到一組匹配數最大的方案,記為最大匹配。若|x|=|y|=匹配數時,該匹配方案為最優匹配(PM)。

定義8偏好隱私預算分配圖。設能為發布數據提供最大數據效用的隱私預算,與每個敏感屬性等級之間的連線形成的圖為一個偏好隱私預算分配圖PA。

本文設計的加噪方式類似于二部圖的最優匹配。給定一組敏感屬性對應的m個敏感等級,一組k個隱私預算的集合,將這組敏感屬性等級以使發布的數據與原始數據的I(*)最大的方式匹配給這組隱私預算。最匹配的過程是先設置每個初始敏感屬性的隱私損失Pli=0,計算Tij,用Tij-Pli表示敏感屬性在Gi下的信息量損失,然后根據損失函數構造偏好隱私預算分配圖PA,檢查圖中是否存在完美匹配。如果存在,匹配過程結束,得到一個最優匹配;否則存在受限隱私預算,把與受限隱私預算關聯的敏感屬性的Pli加一個單位,重復上述過程,直到存在完美匹配結束。加噪方法如算法1所示。

算法1加噪方法

輸入：敏感屬性{P1,P2,…,Pm},差分隱私預算εj。

輸出：最優匹配PM。

1. 對于每一個Pi做以下操作：

2. 設置初始敏感屬性的隱私損失Pli=0

3. 對于每一個隱私預算εj做以下操作：

4. 計算Tij

5. 偏好隱私預算分配圖PA

6.IF存在完美匹配

7. 結束匹配

8. 獲得最優匹配方案PM

9.Else

10. Pli+1

11. 返回第5步

12.End

主成分個數k的選取,在整個算法過程中閾值進行人為的選取是不切實際的,主成分分析k值的選擇很大程度地影響著數據的安全性、可用性、處理數據花費時間。k值選擇過小,導致較多的屬性被剔除,還原后的噪聲數據的可用性較低;k值選擇過大,還原后的噪聲數據更加接近原始數據,但是數據的安全性降低。因此,怎樣選擇最優的主成分個數k是PCA優化算法的挑戰之一。

3.5 互信息評價機制

本文引進互信息的概念,通過計算不同主成分個數k值下的噪聲數據與原始數據的互信息大小,利用均值法,將最接近均值的k值,作為發布數據安全性和實用性達到最優的主成分個數。

互信息越大,變量之間的相關性越強,數據實用性越強。用互信息去衡量加噪后的數據集更接近原始數據集的關系是可行的。

3.6 算法描述

基于主成分分析優化的差分隱私高維數據發布算法如算法2所示。算法2對優化主成分分析的高維數據發布的實現進行了概述。利用屬性重要度篩選屬性、最優主成分個數k的確定方法對主成分分析法在差分隱私數據發布中的改進,很大程度地提升了數據的可用性和減少了數據處理的時間。

算法2ICAHDP

輸入：原始數據集Sm×n,屬性重要度閾值Th,差分隱私預算ε。

輸出：發布數據集S″。

1.對每一個屬性做以下操作：

2.計算屬性ci的信息熵H(ci)

5.END IF

6.END

7.計算b11,bi21,…,bp1

9.得到向量B=[b11,b21,…,bp1]T

12.計算Cov=UTCU,

其中C=Λ=diag[λ1,λ2,…,λp]

13.選擇U中最大的k個特征向量組成特征向量矩陣Up×k

14.k值的選取,根據互信息值確定

15.計算得到投影矩陣Zk×n

16.對投影矩陣Zk×n添加噪聲

18.得到帶有噪聲的矩陣Z(noise)

19.計算e11,e21,…,ep1

20.得到向量E(noise)=[e11,e21,…,ep1]T

21.還原數據集S″

22.S″=Up×k×Z(noise)+repmat(E(noise),1,n)

23.求出互信息I(Sm×n,S″),確定最優K值。

3.7 算法隱私保護效果分析

定理1所提出的ICAHDP算法滿足ε-差分隱私保護。

證明由算法可知：

噪聲矩陣為：

由Laplace機制即證：

因為特征向量矩陣Up×k中的任意兩個特征向量互相正交,則有：

所以：

得證。

得出結論：ICAHDP算法滿足ε-差分隱私保護。。

4 實驗評價

為了對ICAHDP算法的有效性進行驗證,本節將采用具體的實驗進行分析說明。

4.1 實驗設置

實驗環境：Windows 10操作系統,Intel(R) Core(TM) i3-8100 CPU 3.6 GHz,16 GB內存。所涉及的算法和代碼用Python實現。

實驗數據：實驗中采用UCI Adult、Diabetes 130-US hospitals for years 1999年-2008年 Data Set(Diabetes)和TIC三個數據集,三者均被廣泛運用于數據發布。Adult是美國人口普查數據,記錄了48 842條個人信息;Diabetes是1999年-2008年美國130家醫院的糖尿病患者數據,記錄了101 767條糖尿病患者信息;TIC是某保險公司的客戶信息數據,記錄了98 220條客戶信息。數據集的數據類型、樣本數及維度如表2所示。

表2 數據集描述

為了評估本文算法的性能,分別采用以上三種數據集,對ICAHDP、PrivBayes、JTree、DPPro算法、NoPrivacy(不加噪聲)進行高維數據發布時,采用SVM分類算法度量數據的有效性。使用發布后的數據構建SVM分類模型,選擇一個屬性作為分類屬性,其他屬性作為特征,訓練SVM分類器,并且做出預測。本文針對不同數據集選取不同的屬性作為分類屬性。為進一步評價算法的有效性,使用誤分類率(Misclassification rate)作為數據可用性的衡量標準,來度量發布數據的SVM分類結果的準確性。

首先在Adult、Diabetes、TIC數據集上,通過5種算法生成添加噪聲后的發布數據集,將70%的生成數據作為訓練集,30%的數據作為測試集,然后在發布數據集上構建SVM分類器?；?種算法為隨機算法,為了減少只進行一次實驗產生不可避免的誤差,因此在三種數據集上分別進行了10次實驗,計算實驗結果的平均值作為最終的實驗結果。

4.2 實驗結果分析

在Adult數據集上,分別以是否擁有大學學歷、是否結婚作為分類屬性做出預測。在Diabetes數據集上,分別以是否為男性、是否再次入住醫院作為分類屬性做出預測。在TIC數據集上,分別以否擁有房子、是否結婚作為分類屬性做出預測。

圖2、圖3及圖4分別展示了5種算法在Adults、Diabetes、TIC數據集上的誤分類結果。

(a) Adult, education

(a) TIC, house

可以觀察到,幾乎在所有情況下,ICAHDP始終在4個數據集上表現出比其他解決方案更好的性能。這是因為ICAHDP可以實質上提取數據集中屬性的主要成分。將高維數據映射到低維空間,通過將隱私預算分配給低維數據,可以將噪聲添加到更加敏感的屬性中。對于其他屬性,將會減少噪聲干擾,使數據的實用性得到極大的提高,最終產生發布的數據比其他解決方案具有更好的實用性。

5 結 語

針對高維數據發布問題,首先,闡述了隱私保護的研究背景和意義;其次,分析現有的高維數據發布方法的優點與不足;最后,提出一種改進成分分析的差分隱私高維數據發布方法ICAHDP。理論分析表明,ICAHDP不但對高維數據發布具有較好的優化而且滿足差分隱私。實驗結果表明,ICAHDP算法與現有的同類算法相比,生成的數據集具有較好的效用性。盡管ICAHDP針對高維數據隱私保護有較好的效果,但是該方法也存在著一些局限性,例如其研究對象只能針對數值型靜態高維數據。因此,未來將針對動態的、非數值型高維數據發布提出相應的差分隱私保護方法。