張興,陳昊
(遼寧工業大學 電子與信息工程學院,遼寧 錦州 121001)
在大數據時代的背景下,數據呈現大量(數據量大)、多樣(數據樣式多)、高速(數據產生迅速)、低價值密度(數據有用性低)等特點,數據維度也出現井噴式劇增,同時也帶來了一些隱私安全問題。2020 年4 月,Cyble 安全公司報道稱有約2.67 億Facebook 用戶信息被黑客盜取,并公開在暗網銷售,造成大量用的敏感信息泄露,同年6 月,我國鄭州某民辦高校約2 萬名學生身份信息泄露,多名學生及家長接到大量騷擾和威脅電話。2021 年1 月8 日,某國外論壇公開販賣國內某銀行1 679 萬條數據,并公開大量敏感數據樣本。同年3 月,安全研究人員發現某印度政府網站上存在安全問題導致孟加拉邦百萬人次核酸檢測結果泄露。報告中含有姓名、年齡、居住地址、檢測時間、婚姻狀況等大量敏感信息。大量的例子都說明大數據時代的背景下,數據安全問題變得尤為突出。
隱私數據泄露的同時也加劇了隱私保護的發展,相對于傳統的數據匿名化保護方法(如k-匿名[1],l-多樣性[2],t-緊密性[3],(α,k)-匿名[4])存在不能抵御全部背景知識攻擊[5]的缺點,差分隱私因具有嚴格的數學定義和邏輯證明更加受到人們的廣泛關注。差分隱私在隱私保護數據發布(privacy-preserving data publishing,PPDP)應用廣泛,可以對隱私進行量化分析,在降低數據泄露風險的同時能更好地保障數據的效用性。
大數據呈現數據量大、數據樣式多、數據產生迅速、數據有用性低特點,數據規模越來越大,數據相比于以往更加復雜多變,高維數據存在“維度災難”,導致傳統的分析手段失效,對于高維數據的挖掘變得更加困難。為了解決上述問題,常利用數據降維的思想,使高維數據映射到低維空間,在低維空間進行數據分析。本文綜述了常見的對于高維數據的研究和差分隱私的結合方法,保證了在挖掘高維數據的同時可以降低數據泄露的風險。最后對未來的研究方向進行展望。
特征降維[6-7]是處理高維數據最常用的手段,如圖1 所示,一般特征降維分為特征抽取與特征選擇兩方面。前者是將原始數據的特征重新組合,生成包含原始信息的更精煉更具有代表性的特征;后者則是對數據進行篩選,篩選出原始數據的部分特征,生成特征子集,特征子集反映出原始數據的絕大部分規律,子集的數據結構更加清晰,便于分析。

圖1 特征降維Fig.1 Feature dimension reduction
而差分隱私是通過對輸出的結果添加適當的噪聲(多數為拉普拉斯機制、高斯機制和指數機制)實現對原始數據集的擾動,從而實現數據的隱私保護。差分隱私嚴格的數學定義如定義1。
定義1ε-差分隱私(ε -differentail prvac):對兄弟數據集D1和D2(相差一條記錄),及其所有子集S,滿足隨機算法A:

則算法A滿足ε-差分隱私,其中e 為自然對數,ε 為隱私預算(衡量隱私保護程度)。一般情況下,實現差分隱私可以通過拉普拉斯機制(數值型)和指數機制(離散型)。因為兩種機制都依靠全局敏感度,故先定義全局敏感度。
定義2全局敏感度(global sensitivity):給定查詢函數f:D→Rd,D為輸入數據集,Rd為輸出數據集。在任意一對D1和D2上,函數f的全局敏感度為

其中‖f(D1)?f(D2)‖1是f(D1) 和f(D2) 間的一階距離。全局敏感度度量了當輸入數據集變化時,對相應輸出結果的影響。有了全局敏感度的概念后,給出Laplace 機制和指數機制定義。
定義3拉普拉斯機制(Laplace mechanism):給定數據集D和隱私預算ε,函數f的全局敏感度為 Δf,當f的輸出滿足:

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

圖2 拉普拉斯分布Fig.2 Laplace distributions
定義4指數機制(index mechanism):給定數據集D,輸出為一個實體對象 γ∈R,μ(D,R) 為可用性函數,Δμ為函數 μ(x,R) 的敏感度,若以正比于的概率從輸入中選擇并輸出r,則算法A滿足 ε-差分隱私。其中u(y,r)|。
經過特征降維后的數據,仍具有原始數據的絕大部分信息,再經過差分隱私處理后用于數據發布,在保證數據分析有效性的同時,可以大大提高數據的隱私保護程度。
特征抽取[8]一般分為線性特征抽取和非線性特征抽取兩類。由于線性特征抽取應用較多,這里則著重介紹。它是根據數據之間的線性關系進行數據的特征轉換,產生的新特征復雜度更小,維數更低。
代表的方法是主成分分析方法[9],由于差分隱私直到2006 年才由Dwork 首次提出[10-12],所以主成分分析差分隱私算法近幾年才慢慢成為研究的熱點,它采用高維數據的主成分降維與加噪機制融合的方式,有效對高維數據進行隱私保護的同時還可以保證數據的高可用性。2012 年,Chaudhuri 等[13]首次提出可用于數據發布的隱私保護算法,該算法采用指數機制來添加噪音實現了PCA 滿足差分隱私的要求,相較于子線性查詢(SULQ)框架,采用此種方式可以得到數據的更多方差。但該算法缺乏收斂時間保證。針對這個問題,2013 年,Kapralov 等[14]在此基礎上提出一種用于低秩近似矩陣的混合規劃算法,解決了因收斂時間保證從而造成隱私泄露的問題,但該算法時間復雜度較高,在用于高維數據發布時執行效率較低。
而Jiang 等[15]則是采用拉普拉斯機制來實現主成分分析差分隱私保護,它將一部分隱私預算去構建噪聲協方差矩陣,剩余的隱私預算用于對投影矩陣的加噪。戚名鈺等[16]和徐亞紅等[17]分別在2017 年和2018 年對此方法進行改進,兩者同樣采用拉普拉斯機制,直接分解原始數據的協方差矩陣,然后在投影矩陣上加噪音,相比原來更為簡便。但前者針對數據發布后面臨的數據挖掘工作,又提出了一種基于線性判別分析的差分隱私數據發布算法,該算法是針對分類問題的優化,提高了發布數據分類精度和高可用性。后者通過設計的3 種不同的加噪方式,得出了均分加噪效果更好的結論。
2020 年,彭長根等[18]根據傳統的主成分分析差分隱私算法大多只能用于捕獲線性關系,提出最大信息系數(MIC)實現主成分分析的差分隱私算法(MIC-PCA-DP),該算法利用MIC 構建主成分分析,在捕獲線性關系的同時也可以捕獲非線性關系和多函數關系,利用特征值占比加噪的方式對降維后的數據進行合理加噪,優化了噪聲的分配方式,使算法執行效率進一步提升。2021 年,顧貞等[19]提出概率主成分分析的差分隱私數據發布方法,即由概率主成分分析的生成模型生成數據集發布,使得發布的數據集滿足差分隱私。該方法在SVM 分類準確率方面可以保持良好的數據效用。
特征選擇[20]是數據預處理的一種常用手段,它能有效降低高維數據的特征維數,過濾重復數據和噪聲數據,輸出滿足要求的特征子集。特征選擇通常包含特征子集生成、特征子集評價、停止準則和驗證過程4 個過程,如圖3 所示。

圖3 特征選擇Fig.3 Feature selection
2013 年,萬文強[21]首次將差分隱私機制融入到特征選擇之中,將差分隱私與基于統計理論(基尼指數和誤分類增益)的特征選擇相結合,并采用分布式計算框架(Map-Reduce)實現分布式環境下的差分隱私特征選擇方法。DPDFS 算法能在選取重要特征的同時,有效保護用戶數據隱私性不被泄露。
但上述算法并未考慮進行差分隱私的先后順序對數據安全性的影響,且對于隱私預算 ε 的選取比較隨機,效率較低。DPDFS 算法只適用于數據的預處理階段,對后續的數據挖掘(分類和聚類等)并不適用。下述方法是針對上述問題的解決方案。
2014 年,Yang 等[22],首先驗證了基于差分隱私的集成特征選擇算法的性能,得出在相同的環境下,先加入差分隱私保護的效果優于先進行特征選擇的效果,并利用ObjectivePerturbation 策略增加了特征選擇算法的隱私保護強度。
2018 年,高原秀男[23]針對概率攻擊問題,提出來基于特征選擇和離群點檢測的差分隱私算法,并針對醫療數據進行分析實驗,在滿足安全性要求的前提下,提高數據發布的可用性。DPFSOD 是一種聚類算法,可以用于數據分析階段,且對于隱私預算 ε 的選擇,采用了數據集分簇后最小簇中元組數目相結合的方式,得到隱私預算ε 值的取值范圍。2018 年,劉中鋒[24],針對多值的特征選擇,提出了基于局部學習的帶有輸出干擾策略的差分隱私集成特征選擇算法,該算法采用了基于輸出干擾的策略(向輸出結果添加噪聲)來保護隱私。并證明了局部差分隱私特征選擇算法性能優于全局差分隱私特征選擇算法。
以上提出的3 種方法,均從不同角度改進了DPDFS 算法的不足,在同一數據集上,均能達到更優的隱私保護效果。
1988 年,慕春棣等[25]首次提出貝葉斯網絡(Bayesian network)的概念,其本質是一種概率圖模型,即通過先驗知識,建立隨機變量間的依賴關系,進而求取條件概率。貝葉斯網絡是由結點(代表變量) 和連接結點的邊(代表依賴關系) 組成,本質為一個有向無環圖(directed acyclic graph,DAG),可以有效處理變量間的依賴關系。圖4 是一個簡單的貝葉斯網絡模型,其中包含6 個屬性結點和5 條有向邊。

圖4 貝葉斯網絡模型Fig.4 Bayesian network model
相比于特征降維方法,貝葉斯網絡用圖模型來表示數據間的依賴關系,更加直觀且更容易被理解。高維數據因具有“維度災難”和數據稀疏性等特點,使得數據的效用性很低,使得一般的隱私保護方法失去原有的保護效果。但貝葉斯網絡能更容易確保數據屬性間的一致性和完備性,因此在高維數據中有更廣泛的應用空間,同時貝葉斯網絡采用屬性節點間的互信息大小來表示屬性間的依賴程度,它將先驗知識和樣本知識結合,更加適用于稀疏性的高維數據。
對高維數據的隱私保護方法研究中,很多沒有考慮“維度災難”問題直接加噪;也有一部分研究是對高維數據降維再對降維后的數據集注入噪聲,但是這些方法仍然存在一些問題。為解決這些問題,2014 年,Zhang 等[26]提出了一種基于貝葉斯網絡的差分隱私保護發布方法(PrivBayes)。該方法利用構建的貝葉斯網絡實現對高維數據的降維,然后采用拉普拉斯機制對構建好的貝葉斯網絡進行加噪,實現了差分隱私保護。但在構建貝葉斯網絡時,首個屬性字段節點選擇方式隨機,這種構造方式導致構造出來的貝葉斯網絡具有不確定性,容易遭到攻擊者模擬攻擊,造成隱私的泄露。由于指數機制對屬性對進行選擇,隨著屬性對的增多,選擇精度會明顯下降。針對屬性對選擇隨機的問題,2016 年王良等[27]提出了一種基于加權貝葉斯網絡的隱私數據發布方法(加權PrivBayes),該方法通過屬性字段結點在發布數據集中的重要程度,為每一個屬性字段結點增加一個權重值。并將K2評分函數和互信息相結合,所構建的貝葉斯網絡模型的分類精度更高。進一步優化屬性字段結點加入噪聲的順序,相比于PrivBayes 模型在發布數據集精確性和算法效率性上有明顯提升。
上述方法同樣存在構建的貝葉斯網絡不唯一,精度不夠高的問題,如果對原始數據集多次構建,可能會泄露隱私。同時該方法的隱私預算需要手動分配,有可能導致噪聲的加入不合理,對數據的效用性和隱私性有影響。下面的研究就上面出現的問題給出了較合理的解決方案。
2017 年湯詩一[28]提出利用小波變換的方式實現差分隱私下的數據發布,同時用改良的F函數(捕獲更多的互信息量)替換互信息,得到更準確的依賴關系,從而使構建的貝葉斯網絡的精度更高。算法的核心思想是使用低維邊緣分布去刻畫貝葉斯網絡,隨后對低維邊緣分布中的每一項均添加相同的拉普拉斯噪聲,抽樣形成帶噪聲的合成數據集D*。雖然小波變換實現了范圍查詢精度的提升,但該算法只能在單機環境下運行,且未將敏感字段作為第一考慮對象,導致算法普適性不足。
針對PriveBayes 算法中加入噪聲不合理,影響數據效用性的問題,2019 年Li 等[29]提出SSPrivBayes(smooth sensitivity privacy Bayes)算法,該算法引入了平滑敏感度的概念,即在分析實際的數據集的同時考慮局部數據集變化,從而得到不同屬性敏感度,有利于在進行差分隱私時減少噪聲的攝入,來提高數據發布的效用性。并針對PriveBayes 算法在構建貝葉斯網絡搜索空間效率低的問題,提出了一種高效的貝葉斯網絡搜索空間算法PBCPC(privacy Bayesian candidate parents and children),該算法通過啟發式方法得到目標變量的候選父子集,在屬性數量過多時,算法運行效率明顯高于PriveBayes。2018 年,Wei 等[30]針對高維數據差分隱私發布中存在的數據稀疏性問題,提出基于馬爾可夫網的高維數據差分隱私發布的方法(PrivMN),即采用馬爾可夫模型度量屬性間的依賴性,然后結合圖形近似推理算法計算高維數據差分隱私的分布,該算法能有效降低噪聲攝入量,同時還解決了在精確推理中存在的計算復雜性高的問題。
針對現有的在基于構建貝葉斯網絡差分隱私模型中,存在的貝葉斯網絡不唯一和隱私預算分配不合理的情況,2019 年唐雨薇[31]提出了一種優化的貝葉斯差分隱私(OBDP)模型。該模型通過互信息構建網絡、評分函數和組合優化算法得到候選稀疏節點集,采用爬山算法計算兩個節點的凈增益,確保構建的網絡是唯一的。同時劃分敏感屬性和非敏感屬性及不同的屬性簇,對不同的屬性簇添加不同程度的噪聲,從而確保隱私運算分配更合理。
上述方法從不同角度優化了貝葉斯網絡,但都不適用于群智感知系統的高維數據發布,因此,任雪斌等[32]針對群智感知系統采用本地差分隱私保護方法,即用感知服務器接收用戶的隱私信息,然后計算其聯合概率分布和互信息值從而構建出貝葉斯網絡模型,最后按不同屬性信息降維,合成新的數據集,經過大量仿真實驗對比,驗證了該合成數據的有效性。2020 年,肖彪等[33]利用屬性段首選機制并利用聚類的方法取代等寬法對數據進行離散化處理,該算法避免了對首個屬性段屬性的隨機化選擇,提高了數據的可用性。
樹模型[34],即通過構建特征子樹實現高維數據的降維。最早,在PrivBayes 的基礎上Chen 等[35]在2015 年提出一種基于抽樣推理的差分隱私發布方法(JTree 算法),該方法采用基于抽樣的框架和閾值機制相融合的方式構建屬性依賴圖,然后利用聯合樹最小化誤差,在依賴圖中識別出一組邊緣表逼近聯合分布,最終實現高維數據發布。
但上述方法中構建的團圖容易出現局部最優。針對這些問題,2018 年張嘯劍等[36]提出了一種基于聯合樹的差分隱私高維數據發布算法(PrivHD 算法),該算法利用馬爾可夫網絡對高維數據進行降維并結合高通濾波的方式對生成的屬性對進行過濾,最后采用聯合樹生成完全團圖,該過程符合差分隱私要求,在數據查詢和分類上均高于JTree 算法。同年,蘇煒航等[37]采用隱樹模型對高維數據的關聯屬性對進行過濾,該算法(LTMDP 算法)在生成隱變量過程中通過互信息值提前分組,在分組過程中引入指數機制使該過程滿足差分隱私,在隱樹結構學習中引入拉普拉斯機制并采用自頂向下的采樣方式生成高維數據集,該算法采用隱樹模型在執行效率和分析精度上高于PrivBayes 算法。2019 年,郝志峰等[38]引入格雷碼和語義樹對PrivBayes 算法改進,提出了基于語義樹和貝葉斯網絡的發布算法(PrivBayes-Hierarchical 算法),該算法用格雷碼使插入的噪聲魯棒性更好,提高數據的高可用性,同時采用語義層次樹減少數據誤差,提高分類精度。
上述3 種方法均采用不同的樹模型,對從不同角度對PrivBayes 算法進行改進,因此在執行效率上均優于傳統的PrivBayes 算法。
針對在高維數據中搜索日志泄露的問題,陸葉等[39]利用前綴樹的思想,提出一種滿足差分隱私的前綴樹方法,該算法通過前綴樹把項集中小于k的剪枝,然后關聯頻繁項,對用戶的ID 進行差分隱私保護,保證了用戶的敏感信息不被泄露,但該算法執行效率較低。同樣采用前綴樹的實例,2017 年王曉男[40]針對多維順序數據,采用改良的前綴樹對數據集采用分層加噪,減少了隱私預算的消耗,在降低相對誤差的同時使模型的執行效率和安全性得到提升。2020 年,鄧蔚等[41]采用指數機制和Laplace 機制分別處理連續型特征和離散型特征并準確找到最佳分裂特征和分裂點,采用等差預算分配加噪策略。該算法充分利用了隱私預算,提高了分類準確度。
隨著數據維度的增加,數據之間關聯程度也會提高,而差分隱私對于關聯數據的保護水平往往很低,原因是維數的增加導致噪聲的增多,如果采用傳統的加噪方式,可能會破壞屬性間的關聯性,從而降低數據的效用性。雖然很多方法針對這個問題,采用互信息去計算屬性間的相關性,然后對不同數據采用分別加噪的方式去降低噪聲的添加量,但對敏感數據和非敏感數據的區分往往存在較大誤差。
粗糙集理論是由Pawlak 教授[42]提出的,它是用于處理不確定關系的一種數學工具。
定義5決策系統(decision system):在粗糙集理論中,知識的表達是用決策系統表示的,一個決策系統由一個四元組表示:

式中:U為非空有限集,稱為論域;A為非空有限屬性集,由條件屬性集C和決策屬性集D組成;V=Uα∈AVα,Vα是屬性α的值域;f:U×A→V是信息函數(樣本空間到屬性空間)數據屬性間的關聯性,可以用粗糙集中屬性依賴度k進行衡量(k為1 表示D完全依賴C),然后再針對不同的屬性添加合理的噪聲。屬性集D在C上的依賴度公式為

Pawlak 屬性約簡算法[43]可以有效把高維數據中不相關的冗余信息剔除,得到分類規則。該算法的主要思想是求出核屬性并啟發式擴展,最后得到一個約簡。但該方法計算核屬性過程較繁瑣,因此王一斌[44]利用差別矩陣來構成差分函數,通過析取和合取運算去簡化區分函數,從而可以快速得到所有的約簡。2017 年孫志鵬[45]針對高維數據的屬性約簡利用粗糙集理論去改進K均值算法,提出自適應的粗糙集K均值算法,該算法有效提高了聚類的精度。2019 年Li 等[46]針對醫療數據,首次將差分隱私和粗糙集提取規則相結合,提出了一種挖掘醫療數據中隱藏模式、保障患者隱私的新方法(DPRers)。該算法利用拉普拉斯機制在數據挖掘過程中增加噪聲,同時使數據的效用最大化。2019 年Luo 等[47]利用粗糙集對高維數據的降維的同時,引入信息熵衡量數據的敏感度達到更合理的加噪方式,提高了數據的效用性。
粗糙集具有的優勢和高維數據的特點十分契合,比普通的降維方法有著天然的優勢,因此兩者的結合往往能夠起到很好的隱私保護效果。
隨機投影[48]能有效解決高維數據“維度災難”問題。它的理論依據是Johnson-Lindenstrauss 引理。
定義6Johnson-Lindenstrauss 引理:任意給定一個整數d>0,存在ε∈(0,1) 和 δ<1/2,k=,存在一個映射f:Rd→Rk,x∈Rd,

Johnson-Lindenstrauss 引理[49]表明將d維空間的n個點映射到k維(k 當投影矩陣構建完成后,投影矩陣泄露可能也會導致數據的泄露。針對這個問題,2013 年楊靜等[50]利用哈希函數產生隨機投影矩陣并引入安全子空間去保障構建投影矩陣的安全性。同年,針對高維數據的稀疏性問題,Hardt 等[51]利用隨機投影方法使輸入矩陣滿足差分隱私的低秩近似逼近,同時給出誤差邊界,并針對誤差邊界為空的情況,通過冪迭代法替換原來生成的特征向量,增強擾動可靠性的同時,該方法還能減少由于添加噪聲所引起的誤差邊界,消除了數據矩陣秩具有的依賴關系。2014 年趙家石[52]就高維稀疏數據易遭到攻擊者通過重建原始數據,導致隱私泄露的問題,采用噪聲投影擾動和差分隱私結合,即先進行投影轉換,在此基礎上添加噪聲(相互獨立的隨機數),可有效確保擾動數據的可用性。 兩者都是針對高維數據的稀疏性問題,但從不同角度給出了不同的處理方案,共同點都是采用投影轉換的思考方式。 近年,在保護數據據隱私的前提下去發布高維數據集引起了數據庫界越來越多的關注。2017年Xu 等[53]針對現有的差分隱私無法解決由于干擾誤差和計算復雜度增加對高維數據發布失效的問題,提出了一種基于隨機投影的數發布算法(DPPro),主要思想采用隨機投影將數據集從高維空間投影到隨機選擇的低維空間中,以保持歐式距離不變,從而使用戶根據距離進行分割。然后對每個矢量添加高斯噪聲,這樣,可以在最小化添加噪聲量的同時最大化提高效用性,確保發布數據的隱私性。針對高維數值型數據(多個數值型屬性),在處理較大屬性個數時誤差較大的問題,2020 年孫慧中等[54]滿足本地差分隱私的高維數值型數據收集算法(Multi-RPHM),與DPPro 算法不同之處的,用戶自己通過隨機投影對原始高維數據降維,然后發送給數據收集者,數據收集者再進行維度還原,生成高維擾動數據集用于數據發布。 本節將以上提到的技術及算法進行匯總比較,列舉出了各種方法代表算法的優缺點,如表1所示,基于特征抽取、貝葉斯網絡、樹模型、粗糙集、投影和差分隱私結合的方法比較。 表1 降維方法比較Table 1 Comparison of dimensionality reduction methods 續表1 為了更直觀比較各個技術的內在聯系和主要區別,給出各個算法的針對不同場景的對比表格,包括PPCA 和DPPro、PrivBayes 和DPRers、PrivMN 和PrivHD 在不同場景下的優缺點和數據可用性分析,如表2 所示。 表2 降維算法比較Table 2 Comparison of dimensionality reduction algorithms 大數據時代下,對高維數據的挖掘比以往任何時候都更加迫切,采用非常規手段往往會導致用戶隱私的泄露。差分隱私是一種被嚴格證明的隱私保護模型,可有效抵制各種安全攻擊。因此把差分隱私應用到高維數據上可以有效實現數據的隱私安全保障。本文就高維數據的差分隱私模型作出詳細歸納總結,包括將特征降維、貝葉斯網絡、樹模型等方法與其結合應用,分析了不同方法的優缺點和應用場景。 未來,數據將會更加復雜多變,因此必定會產生更多問題。 1)屬性關聯性強。數據屬性之間往往存在關聯性,隨著數據維度的增加,屬性間的關聯性更加復雜。近期提出一些研究方法,如通過粗糙集的屬性依賴度去度量屬性的關系程度,然后針對不同屬性添加不同的噪聲。但相關研究的文章仍然較少,未來有較大的空間亟待研究。 2)算法復雜度高。目前,差分隱私在高維數據的應用大多停留在實驗階段,往往伴隨著較高的時間復雜度,導致算法的效率較低,無法高效地應用到生產實踐中。因此,亟需對算法進行優化,以滿足實際應用的需要。5 方法對比



6 結束語