差分隱私的高維數(shù)據(jù)發(fā)布研究綜述

張興，陳昊

（遼寧工業(yè)大學(xué) 電子與信息工程學(xué)院，遼寧 錦州 121001）

在大數(shù)據(jù)時(shí)代的背景下，數(shù)據(jù)呈現(xiàn)大量(數(shù)據(jù)量大)、多樣(數(shù)據(jù)樣式多)、高速(數(shù)據(jù)產(chǎn)生迅速)、低價(jià)值密度(數(shù)據(jù)有用性低)等特點(diǎn)，數(shù)據(jù)維度也出現(xiàn)井噴式劇增，同時(shí)也帶來了一些隱私安全問題。2020 年4 月，Cyble 安全公司報(bào)道稱有約2.67 億Facebook 用戶信息被黑客盜取，并公開在暗網(wǎng)銷售，造成大量用的敏感信息泄露，同年6 月，我國鄭州某民辦高校約2 萬名學(xué)生身份信息泄露，多名學(xué)生及家長接到大量騷擾和威脅電話。2021 年1 月8 日，某國外論壇公開販賣國內(nèi)某銀行1 679 萬條數(shù)據(jù)，并公開大量敏感數(shù)據(jù)樣本。同年3 月，安全研究人員發(fā)現(xiàn)某印度政府網(wǎng)站上存在安全問題導(dǎo)致孟加拉邦百萬人次核酸檢測結(jié)果泄露。報(bào)告中含有姓名、年齡、居住地址、檢測時(shí)間、婚姻狀況等大量敏感信息。大量的例子都說明大數(shù)據(jù)時(shí)代的背景下，數(shù)據(jù)安全問題變得尤為突出。

隱私數(shù)據(jù)泄露的同時(shí)也加劇了隱私保護(hù)的發(fā)展，相對于傳統(tǒng)的數(shù)據(jù)匿名化保護(hù)方法(如k-匿名[1]，l-多樣性[2]，t-緊密性[3]，(α,k)-匿名[4])存在不能抵御全部背景知識攻擊[5]的缺點(diǎn)，差分隱私因具有嚴(yán)格的數(shù)學(xué)定義和邏輯證明更加受到人們的廣泛關(guān)注。差分隱私在隱私保護(hù)數(shù)據(jù)發(fā)布(privacy-preserving data publishing，PPDP)應(yīng)用廣泛，可以對隱私進(jìn)行量化分析，在降低數(shù)據(jù)泄露風(fēng)險(xiǎn)的同時(shí)能更好地保障數(shù)據(jù)的效用性。

大數(shù)據(jù)呈現(xiàn)數(shù)據(jù)量大、數(shù)據(jù)樣式多、數(shù)據(jù)產(chǎn)生迅速、數(shù)據(jù)有用性低特點(diǎn)，數(shù)據(jù)規(guī)模越來越大，數(shù)據(jù)相比于以往更加復(fù)雜多變，高維數(shù)據(jù)存在“維度災(zāi)難”，導(dǎo)致傳統(tǒng)的分析手段失效，對于高維數(shù)據(jù)的挖掘變得更加困難。為了解決上述問題，常利用數(shù)據(jù)降維的思想，使高維數(shù)據(jù)映射到低維空間，在低維空間進(jìn)行數(shù)據(jù)分析。本文綜述了常見的對于高維數(shù)據(jù)的研究和差分隱私的結(jié)合方法，保證了在挖掘高維數(shù)據(jù)的同時(shí)可以降低數(shù)據(jù)泄露的風(fēng)險(xiǎn)。最后對未來的研究方向進(jìn)行展望。

1 特征降維和差分隱私

特征降維[6-7]是處理高維數(shù)據(jù)最常用的手段，如圖1 所示，一般特征降維分為特征抽取與特征選擇兩方面。前者是將原始數(shù)據(jù)的特征重新組合，生成包含原始信息的更精煉更具有代表性的特征；后者則是對數(shù)據(jù)進(jìn)行篩選，篩選出原始數(shù)據(jù)的部分特征，生成特征子集，特征子集反映出原始數(shù)據(jù)的絕大部分規(guī)律，子集的數(shù)據(jù)結(jié)構(gòu)更加清晰，便于分析。

圖1 特征降維Fig.1 Feature dimension reduction

而差分隱私是通過對輸出的結(jié)果添加適當(dāng)?shù)脑肼?多數(shù)為拉普拉斯機(jī)制、高斯機(jī)制和指數(shù)機(jī)制)實(shí)現(xiàn)對原始數(shù)據(jù)集的擾動，從而實(shí)現(xiàn)數(shù)據(jù)的隱私保護(hù)。差分隱私嚴(yán)格的數(shù)學(xué)定義如定義1。

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

則算法A滿足ε-差分隱私，其中e 為自然對數(shù)，ε 為隱私預(yù)算(衡量隱私保護(hù)程度)。一般情況下，實(shí)現(xiàn)差分隱私可以通過拉普拉斯機(jī)制(數(shù)值型)和指數(shù)機(jī)制(離散型)。因?yàn)閮煞N機(jī)制都依靠全局敏感度，故先定義全局敏感度。

定義2全局敏感度(global sensitivity)：給定查詢函數(shù)f:D→Rd，D為輸入數(shù)據(jù)集，Rd為輸出數(shù)據(jù)集。在任意一對D1和D2上，函數(shù)f的全局敏感度為

其中‖f(D1)?f(D2)‖1是f(D1) 和f(D2) 間的一階距離。全局敏感度度量了當(dāng)輸入數(shù)據(jù)集變化時(shí)，對相應(yīng)輸出結(jié)果的影響。有了全局敏感度的概念后，給出Laplace 機(jī)制和指數(shù)機(jī)制定義。

定義3拉普拉斯機(jī)制(Laplace mechanism)：給定數(shù)據(jù)集D和隱私預(yù)算ε，函數(shù)f的全局敏感度為 Δf，當(dāng)f的輸出滿足：

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

圖2 拉普拉斯分布Fig.2 Laplace distributions

定義4指數(shù)機(jī)制(index mechanism)：給定數(shù)據(jù)集D，輸出為一個(gè)實(shí)體對象 γ∈R,μ(D,R) 為可用性函數(shù)，Δμ為函數(shù) μ(x,R) 的敏感度，若以正比于的概率從輸入中選擇并輸出r，則算法A滿足 ε-差分隱私。其中u(y,r)|。

經(jīng)過特征降維后的數(shù)據(jù)，仍具有原始數(shù)據(jù)的絕大部分信息，再經(jīng)過差分隱私處理后用于數(shù)據(jù)發(fā)布，在保證數(shù)據(jù)分析有效性的同時(shí)，可以大大提高數(shù)據(jù)的隱私保護(hù)程度。

1.1 基于線性特征抽取的差分隱私

特征抽取[8]一般分為線性特征抽取和非線性特征抽取兩類。由于線性特征抽取應(yīng)用較多，這里則著重介紹。它是根據(jù)數(shù)據(jù)之間的線性關(guān)系進(jìn)行數(shù)據(jù)的特征轉(zhuǎn)換，產(chǎn)生的新特征復(fù)雜度更小，維數(shù)更低。

代表的方法是主成分分析方法[9]，由于差分隱私直到2006 年才由Dwork 首次提出[10-12]，所以主成分分析差分隱私算法近幾年才慢慢成為研究的熱點(diǎn)，它采用高維數(shù)據(jù)的主成分降維與加噪機(jī)制融合的方式，有效對高維數(shù)據(jù)進(jìn)行隱私保護(hù)的同時(shí)還可以保證數(shù)據(jù)的高可用性。2012 年，Chaudhuri 等[13]首次提出可用于數(shù)據(jù)發(fā)布的隱私保護(hù)算法，該算法采用指數(shù)機(jī)制來添加噪音實(shí)現(xiàn)了PCA 滿足差分隱私的要求，相較于子線性查詢(SULQ)框架，采用此種方式可以得到數(shù)據(jù)的更多方差。但該算法缺乏收斂時(shí)間保證。針對這個(gè)問題，2013 年，Kapralov 等[14]在此基礎(chǔ)上提出一種用于低秩近似矩陣的混合規(guī)劃算法，解決了因收斂時(shí)間保證從而造成隱私泄露的問題，但該算法時(shí)間復(fù)雜度較高，在用于高維數(shù)據(jù)發(fā)布時(shí)執(zhí)行效率較低。

而Jiang 等[15]則是采用拉普拉斯機(jī)制來實(shí)現(xiàn)主成分分析差分隱私保護(hù)，它將一部分隱私預(yù)算去構(gòu)建噪聲協(xié)方差矩陣，剩余的隱私預(yù)算用于對投影矩陣的加噪。戚名鈺等[16]和徐亞紅等[17]分別在2017 年和2018 年對此方法進(jìn)行改進(jìn)，兩者同樣采用拉普拉斯機(jī)制，直接分解原始數(shù)據(jù)的協(xié)方差矩陣，然后在投影矩陣上加噪音，相比原來更為簡便。但前者針對數(shù)據(jù)發(fā)布后面臨的數(shù)據(jù)挖掘工作，又提出了一種基于線性判別分析的差分隱私數(shù)據(jù)發(fā)布算法，該算法是針對分類問題的優(yōu)化，提高了發(fā)布數(shù)據(jù)分類精度和高可用性。后者通過設(shè)計(jì)的3 種不同的加噪方式，得出了均分加噪效果更好的結(jié)論。

2020 年，彭長根等[18]根據(jù)傳統(tǒng)的主成分分析差分隱私算法大多只能用于捕獲線性關(guān)系，提出最大信息系數(shù)(MIC)實(shí)現(xiàn)主成分分析的差分隱私算法(MIC-PCA-DP)，該算法利用MIC 構(gòu)建主成分分析，在捕獲線性關(guān)系的同時(shí)也可以捕獲非線性關(guān)系和多函數(shù)關(guān)系，利用特征值占比加噪的方式對降維后的數(shù)據(jù)進(jìn)行合理加噪，優(yōu)化了噪聲的分配方式，使算法執(zhí)行效率進(jìn)一步提升。2021 年，顧貞等[19]提出概率主成分分析的差分隱私數(shù)據(jù)發(fā)布方法，即由概率主成分分析的生成模型生成數(shù)據(jù)集發(fā)布，使得發(fā)布的數(shù)據(jù)集滿足差分隱私。該方法在SVM 分類準(zhǔn)確率方面可以保持良好的數(shù)據(jù)效用。

1.2 基于特征選擇的差分隱私

特征選擇[20]是數(shù)據(jù)預(yù)處理的一種常用手段，它能有效降低高維數(shù)據(jù)的特征維數(shù)，過濾重復(fù)數(shù)據(jù)和噪聲數(shù)據(jù)，輸出滿足要求的特征子集。特征選擇通常包含特征子集生成、特征子集評價(jià)、停止準(zhǔn)則和驗(yàn)證過程4 個(gè)過程，如圖3 所示。

圖3 特征選擇Fig.3 Feature selection

2013 年，萬文強(qiáng)[21]首次將差分隱私機(jī)制融入到特征選擇之中，將差分隱私與基于統(tǒng)計(jì)理論(基尼指數(shù)和誤分類增益)的特征選擇相結(jié)合，并采用分布式計(jì)算框架(Map-Reduce)實(shí)現(xiàn)分布式環(huán)境下的差分隱私特征選擇方法。DPDFS 算法能在選取重要特征的同時(shí)，有效保護(hù)用戶數(shù)據(jù)隱私性不被泄露。

但上述算法并未考慮進(jìn)行差分隱私的先后順序?qū)?shù)據(jù)安全性的影響，且對于隱私預(yù)算 ε 的選取比較隨機(jī)，效率較低。DPDFS 算法只適用于數(shù)據(jù)的預(yù)處理階段，對后續(xù)的數(shù)據(jù)挖掘(分類和聚類等)并不適用。下述方法是針對上述問題的解決方案。

2014 年，Yang 等[22]，首先驗(yàn)證了基于差分隱私的集成特征選擇算法的性能，得出在相同的環(huán)境下，先加入差分隱私保護(hù)的效果優(yōu)于先進(jìn)行特征選擇的效果，并利用ObjectivePerturbation 策略增加了特征選擇算法的隱私保護(hù)強(qiáng)度。

2018 年，高原秀男[23]針對概率攻擊問題，提出來基于特征選擇和離群點(diǎn)檢測的差分隱私算法，并針對醫(yī)療數(shù)據(jù)進(jìn)行分析實(shí)驗(yàn)，在滿足安全性要求的前提下，提高數(shù)據(jù)發(fā)布的可用性。DPFSOD 是一種聚類算法，可以用于數(shù)據(jù)分析階段，且對于隱私預(yù)算 ε 的選擇，采用了數(shù)據(jù)集分簇后最小簇中元組數(shù)目相結(jié)合的方式，得到隱私預(yù)算ε 值的取值范圍。2018 年，劉中鋒[24]，針對多值的特征選擇，提出了基于局部學(xué)習(xí)的帶有輸出干擾策略的差分隱私集成特征選擇算法，該算法采用了基于輸出干擾的策略(向輸出結(jié)果添加噪聲)來保護(hù)隱私。并證明了局部差分隱私特征選擇算法性能優(yōu)于全局差分隱私特征選擇算法。

以上提出的3 種方法，均從不同角度改進(jìn)了DPDFS 算法的不足，在同一數(shù)據(jù)集上，均能達(dá)到更優(yōu)的隱私保護(hù)效果。

2 貝葉斯網(wǎng)絡(luò)和差分隱私

2.1 貝葉斯網(wǎng)絡(luò)模型

1988 年，慕春棣等[25]首次提出貝葉斯網(wǎng)絡(luò)(Bayesian network)的概念，其本質(zhì)是一種概率圖模型，即通過先驗(yàn)知識，建立隨機(jī)變量間的依賴關(guān)系，進(jìn)而求取條件概率。貝葉斯網(wǎng)絡(luò)是由結(jié)點(diǎn)(代表變量) 和連接結(jié)點(diǎn)的邊(代表依賴關(guān)系) 組成，本質(zhì)為一個(gè)有向無環(huán)圖(directed acyclic graph，DAG)，可以有效處理變量間的依賴關(guān)系。圖4 是一個(gè)簡單的貝葉斯網(wǎng)絡(luò)模型，其中包含6 個(gè)屬性結(jié)點(diǎn)和5 條有向邊。

圖4 貝葉斯網(wǎng)絡(luò)模型Fig.4 Bayesian network model

相比于特征降維方法，貝葉斯網(wǎng)絡(luò)用圖模型來表示數(shù)據(jù)間的依賴關(guān)系，更加直觀且更容易被理解。高維數(shù)據(jù)因具有“維度災(zāi)難”和數(shù)據(jù)稀疏性等特點(diǎn)，使得數(shù)據(jù)的效用性很低，使得一般的隱私保護(hù)方法失去原有的保護(hù)效果。但貝葉斯網(wǎng)絡(luò)能更容易確保數(shù)據(jù)屬性間的一致性和完備性，因此在高維數(shù)據(jù)中有更廣泛的應(yīng)用空間，同時(shí)貝葉斯網(wǎng)絡(luò)采用屬性節(jié)點(diǎn)間的互信息大小來表示屬性間的依賴程度，它將先驗(yàn)知識和樣本知識結(jié)合，更加適用于稀疏性的高維數(shù)據(jù)。

2.2 基于貝葉斯網(wǎng)絡(luò)的差分隱私

對高維數(shù)據(jù)的隱私保護(hù)方法研究中，很多沒有考慮“維度災(zāi)難”問題直接加噪；也有一部分研究是對高維數(shù)據(jù)降維再對降維后的數(shù)據(jù)集注入噪聲，但是這些方法仍然存在一些問題。為解決這些問題，2014 年，Zhang 等[26]提出了一種基于貝葉斯網(wǎng)絡(luò)的差分隱私保護(hù)發(fā)布方法(PrivBayes)。該方法利用構(gòu)建的貝葉斯網(wǎng)絡(luò)實(shí)現(xiàn)對高維數(shù)據(jù)的降維，然后采用拉普拉斯機(jī)制對構(gòu)建好的貝葉斯網(wǎng)絡(luò)進(jìn)行加噪，實(shí)現(xiàn)了差分隱私保護(hù)。但在構(gòu)建貝葉斯網(wǎng)絡(luò)時(shí)，首個(gè)屬性字段節(jié)點(diǎn)選擇方式隨機(jī)，這種構(gòu)造方式導(dǎo)致構(gòu)造出來的貝葉斯網(wǎng)絡(luò)具有不確定性，容易遭到攻擊者模擬攻擊，造成隱私的泄露。由于指數(shù)機(jī)制對屬性對進(jìn)行選擇，隨著屬性對的增多，選擇精度會明顯下降。針對屬性對選擇隨機(jī)的問題，2016 年王良等[27]提出了一種基于加權(quán)貝葉斯網(wǎng)絡(luò)的隱私數(shù)據(jù)發(fā)布方法(加權(quán)PrivBayes)，該方法通過屬性字段結(jié)點(diǎn)在發(fā)布數(shù)據(jù)集中的重要程度，為每一個(gè)屬性字段結(jié)點(diǎn)增加一個(gè)權(quán)重值。并將K2評分函數(shù)和互信息相結(jié)合，所構(gòu)建的貝葉斯網(wǎng)絡(luò)模型的分類精度更高。進(jìn)一步優(yōu)化屬性字段結(jié)點(diǎn)加入噪聲的順序，相比于PrivBayes 模型在發(fā)布數(shù)據(jù)集精確性和算法效率性上有明顯提升。

上述方法同樣存在構(gòu)建的貝葉斯網(wǎng)絡(luò)不唯一，精度不夠高的問題，如果對原始數(shù)據(jù)集多次構(gòu)建，可能會泄露隱私。同時(shí)該方法的隱私預(yù)算需要手動分配，有可能導(dǎo)致噪聲的加入不合理，對數(shù)據(jù)的效用性和隱私性有影響。下面的研究就上面出現(xiàn)的問題給出了較合理的解決方案。

2017 年湯詩一[28]提出利用小波變換的方式實(shí)現(xiàn)差分隱私下的數(shù)據(jù)發(fā)布，同時(shí)用改良的F函數(shù)(捕獲更多的互信息量)替換互信息，得到更準(zhǔn)確的依賴關(guān)系，從而使構(gòu)建的貝葉斯網(wǎng)絡(luò)的精度更高。算法的核心思想是使用低維邊緣分布去刻畫貝葉斯網(wǎng)絡(luò)，隨后對低維邊緣分布中的每一項(xiàng)均添加相同的拉普拉斯噪聲，抽樣形成帶噪聲的合成數(shù)據(jù)集D*。雖然小波變換實(shí)現(xiàn)了范圍查詢精度的提升，但該算法只能在單機(jī)環(huán)境下運(yùn)行，且未將敏感字段作為第一考慮對象，導(dǎo)致算法普適性不足。

針對PriveBayes 算法中加入噪聲不合理，影響數(shù)據(jù)效用性的問題，2019 年Li 等[29]提出SSPrivBayes(smooth sensitivity privacy Bayes)算法，該算法引入了平滑敏感度的概念，即在分析實(shí)際的數(shù)據(jù)集的同時(shí)考慮局部數(shù)據(jù)集變化，從而得到不同屬性敏感度，有利于在進(jìn)行差分隱私時(shí)減少噪聲的攝入，來提高數(shù)據(jù)發(fā)布的效用性。并針對PriveBayes 算法在構(gòu)建貝葉斯網(wǎng)絡(luò)搜索空間效率低的問題，提出了一種高效的貝葉斯網(wǎng)絡(luò)搜索空間算法PBCPC(privacy Bayesian candidate parents and children)，該算法通過啟發(fā)式方法得到目標(biāo)變量的候選父子集，在屬性數(shù)量過多時(shí)，算法運(yùn)行效率明顯高于PriveBayes。2018 年，Wei 等[30]針對高維數(shù)據(jù)差分隱私發(fā)布中存在的數(shù)據(jù)稀疏性問題，提出基于馬爾可夫網(wǎng)的高維數(shù)據(jù)差分隱私發(fā)布的方法(PrivMN)，即采用馬爾可夫模型度量屬性間的依賴性，然后結(jié)合圖形近似推理算法計(jì)算高維數(shù)據(jù)差分隱私的分布，該算法能有效降低噪聲攝入量，同時(shí)還解決了在精確推理中存在的計(jì)算復(fù)雜性高的問題。

針對現(xiàn)有的在基于構(gòu)建貝葉斯網(wǎng)絡(luò)差分隱私模型中，存在的貝葉斯網(wǎng)絡(luò)不唯一和隱私預(yù)算分配不合理的情況，2019 年唐雨薇[31]提出了一種優(yōu)化的貝葉斯差分隱私(OBDP)模型。該模型通過互信息構(gòu)建網(wǎng)絡(luò)、評分函數(shù)和組合優(yōu)化算法得到候選稀疏節(jié)點(diǎn)集，采用爬山算法計(jì)算兩個(gè)節(jié)點(diǎn)的凈增益，確保構(gòu)建的網(wǎng)絡(luò)是唯一的。同時(shí)劃分敏感屬性和非敏感屬性及不同的屬性簇，對不同的屬性簇添加不同程度的噪聲，從而確保隱私運(yùn)算分配更合理。

上述方法從不同角度優(yōu)化了貝葉斯網(wǎng)絡(luò)，但都不適用于群智感知系統(tǒng)的高維數(shù)據(jù)發(fā)布，因此，任雪斌等[32]針對群智感知系統(tǒng)采用本地差分隱私保護(hù)方法，即用感知服務(wù)器接收用戶的隱私信息，然后計(jì)算其聯(lián)合概率分布和互信息值從而構(gòu)建出貝葉斯網(wǎng)絡(luò)模型，最后按不同屬性信息降維，合成新的數(shù)據(jù)集，經(jīng)過大量仿真實(shí)驗(yàn)對比，驗(yàn)證了該合成數(shù)據(jù)的有效性。2020 年，肖彪等[33]利用屬性段首選機(jī)制并利用聚類的方法取代等寬法對數(shù)據(jù)進(jìn)行離散化處理，該算法避免了對首個(gè)屬性段屬性的隨機(jī)化選擇，提高了數(shù)據(jù)的可用性。

3 樹模型和差分隱私

樹模型[34]，即通過構(gòu)建特征子樹實(shí)現(xiàn)高維數(shù)據(jù)的降維。最早，在PrivBayes 的基礎(chǔ)上Chen 等[35]在2015 年提出一種基于抽樣推理的差分隱私發(fā)布方法(JTree 算法)，該方法采用基于抽樣的框架和閾值機(jī)制相融合的方式構(gòu)建屬性依賴圖，然后利用聯(lián)合樹最小化誤差，在依賴圖中識別出一組邊緣表逼近聯(lián)合分布，最終實(shí)現(xiàn)高維數(shù)據(jù)發(fā)布。

但上述方法中構(gòu)建的團(tuán)圖容易出現(xiàn)局部最優(yōu)。針對這些問題，2018 年張嘯劍等[36]提出了一種基于聯(lián)合樹的差分隱私高維數(shù)據(jù)發(fā)布算法(PrivHD 算法)，該算法利用馬爾可夫網(wǎng)絡(luò)對高維數(shù)據(jù)進(jìn)行降維并結(jié)合高通濾波的方式對生成的屬性對進(jìn)行過濾，最后采用聯(lián)合樹生成完全團(tuán)圖，該過程符合差分隱私要求，在數(shù)據(jù)查詢和分類上均高于JTree 算法。同年，蘇煒航等[37]采用隱樹模型對高維數(shù)據(jù)的關(guān)聯(lián)屬性對進(jìn)行過濾，該算法(LTMDP 算法)在生成隱變量過程中通過互信息值提前分組，在分組過程中引入指數(shù)機(jī)制使該過程滿足差分隱私，在隱樹結(jié)構(gòu)學(xué)習(xí)中引入拉普拉斯機(jī)制并采用自頂向下的采樣方式生成高維數(shù)據(jù)集，該算法采用隱樹模型在執(zhí)行效率和分析精度上高于PrivBayes 算法。2019 年，郝志峰等[38]引入格雷碼和語義樹對PrivBayes 算法改進(jìn)，提出了基于語義樹和貝葉斯網(wǎng)絡(luò)的發(fā)布算法(PrivBayes-Hierarchical 算法)，該算法用格雷碼使插入的噪聲魯棒性更好，提高數(shù)據(jù)的高可用性，同時(shí)采用語義層次樹減少數(shù)據(jù)誤差，提高分類精度。

上述3 種方法均采用不同的樹模型，對從不同角度對PrivBayes 算法進(jìn)行改進(jìn)，因此在執(zhí)行效率上均優(yōu)于傳統(tǒng)的PrivBayes 算法。

針對在高維數(shù)據(jù)中搜索日志泄露的問題，陸葉等[39]利用前綴樹的思想，提出一種滿足差分隱私的前綴樹方法，該算法通過前綴樹把項(xiàng)集中小于k的剪枝，然后關(guān)聯(lián)頻繁項(xiàng)，對用戶的ID 進(jìn)行差分隱私保護(hù)，保證了用戶的敏感信息不被泄露，但該算法執(zhí)行效率較低。同樣采用前綴樹的實(shí)例，2017 年王曉男[40]針對多維順序數(shù)據(jù)，采用改良的前綴樹對數(shù)據(jù)集采用分層加噪，減少了隱私預(yù)算的消耗，在降低相對誤差的同時(shí)使模型的執(zhí)行效率和安全性得到提升。2020 年，鄧蔚等[41]采用指數(shù)機(jī)制和Laplace 機(jī)制分別處理連續(xù)型特征和離散型特征并準(zhǔn)確找到最佳分裂特征和分裂點(diǎn),采用等差預(yù)算分配加噪策略。該算法充分利用了隱私預(yù)算，提高了分類準(zhǔn)確度。

4 粗糙集及隨機(jī)投影的差分隱私

4.1 基于粗糙集的差分隱私

隨著數(shù)據(jù)維度的增加，數(shù)據(jù)之間關(guān)聯(lián)程度也會提高，而差分隱私對于關(guān)聯(lián)數(shù)據(jù)的保護(hù)水平往往很低，原因是維數(shù)的增加導(dǎo)致噪聲的增多，如果采用傳統(tǒng)的加噪方式，可能會破壞屬性間的關(guān)聯(lián)性，從而降低數(shù)據(jù)的效用性。雖然很多方法針對這個(gè)問題，采用互信息去計(jì)算屬性間的相關(guān)性，然后對不同數(shù)據(jù)采用分別加噪的方式去降低噪聲的添加量，但對敏感數(shù)據(jù)和非敏感數(shù)據(jù)的區(qū)分往往存在較大誤差。

粗糙集理論是由Pawlak 教授[42]提出的，它是用于處理不確定關(guān)系的一種數(shù)學(xué)工具。

定義5決策系統(tǒng)(decision system)：在粗糙集理論中，知識的表達(dá)是用決策系統(tǒng)表示的，一個(gè)決策系統(tǒng)由一個(gè)四元組表示：

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

Pawlak 屬性約簡算法[43]可以有效把高維數(shù)據(jù)中不相關(guān)的冗余信息剔除，得到分類規(guī)則。該算法的主要思想是求出核屬性并啟發(fā)式擴(kuò)展，最后得到一個(gè)約簡。但該方法計(jì)算核屬性過程較繁瑣，因此王一斌[44]利用差別矩陣來構(gòu)成差分函數(shù)，通過析取和合取運(yùn)算去簡化區(qū)分函數(shù)，從而可以快速得到所有的約簡。2017 年孫志鵬[45]針對高維數(shù)據(jù)的屬性約簡利用粗糙集理論去改進(jìn)K均值算法，提出自適應(yīng)的粗糙集K均值算法，該算法有效提高了聚類的精度。2019 年Li 等[46]針對醫(yī)療數(shù)據(jù)，首次將差分隱私和粗糙集提取規(guī)則相結(jié)合，提出了一種挖掘醫(yī)療數(shù)據(jù)中隱藏模式、保障患者隱私的新方法(DPRers)。該算法利用拉普拉斯機(jī)制在數(shù)據(jù)挖掘過程中增加噪聲，同時(shí)使數(shù)據(jù)的效用最大化。2019 年Luo 等[47]利用粗糙集對高維數(shù)據(jù)的降維的同時(shí)，引入信息熵衡量數(shù)據(jù)的敏感度達(dá)到更合理的加噪方式，提高了數(shù)據(jù)的效用性。

粗糙集具有的優(yōu)勢和高維數(shù)據(jù)的特點(diǎn)十分契合，比普通的降維方法有著天然的優(yōu)勢，因此兩者的結(jié)合往往能夠起到很好的隱私保護(hù)效果。

4.2 基于隨機(jī)投影的差分隱私

隨機(jī)投影[48]能有效解決高維數(shù)據(jù)“維度災(zāi)難”問題。它的理論依據(jù)是Johnson-Lindenstrauss 引理。

定義6Johnson-Lindenstrauss 引理：任意給定一個(gè)整數(shù)d>0，存在ε∈(0,1) 和 δ<1/2，k=，存在一個(gè)映射f:Rd→Rk，x∈Rd，

Johnson-Lindenstrauss 引理[49]表明將d維空間的n個(gè)點(diǎn)映射到k維(k

當(dāng)投影矩陣構(gòu)建完成后，投影矩陣泄露可能也會導(dǎo)致數(shù)據(jù)的泄露。針對這個(gè)問題，2013 年楊靜等[50]利用哈希函數(shù)產(chǎn)生隨機(jī)投影矩陣并引入安全子空間去保障構(gòu)建投影矩陣的安全性。同年，針對高維數(shù)據(jù)的稀疏性問題，Hardt 等[51]利用隨機(jī)投影方法使輸入矩陣滿足差分隱私的低秩近似逼近，同時(shí)給出誤差邊界，并針對誤差邊界為空的情況，通過冪迭代法替換原來生成的特征向量，增強(qiáng)擾動可靠性的同時(shí)，該方法還能減少由于添加噪聲所引起的誤差邊界，消除了數(shù)據(jù)矩陣秩具有的依賴關(guān)系。2014 年趙家石[52]就高維稀疏數(shù)據(jù)易遭到攻擊者通過重建原始數(shù)據(jù)，導(dǎo)致隱私泄露的問題，采用噪聲投影擾動和差分隱私結(jié)合，即先進(jìn)行投影轉(zhuǎn)換，在此基礎(chǔ)上添加噪聲(相互獨(dú)立的隨機(jī)數(shù))，可有效確保擾動數(shù)據(jù)的可用性。

兩者都是針對高維數(shù)據(jù)的稀疏性問題，但從不同角度給出了不同的處理方案，共同點(diǎn)都是采用投影轉(zhuǎn)換的思考方式。

近年，在保護(hù)數(shù)據(jù)據(jù)隱私的前提下去發(fā)布高維數(shù)據(jù)集引起了數(shù)據(jù)庫界越來越多的關(guān)注。2017年Xu 等[53]針對現(xiàn)有的差分隱私無法解決由于干擾誤差和計(jì)算復(fù)雜度增加對高維數(shù)據(jù)發(fā)布失效的問題，提出了一種基于隨機(jī)投影的數(shù)發(fā)布算法(DPPro)，主要思想采用隨機(jī)投影將數(shù)據(jù)集從高維空間投影到隨機(jī)選擇的低維空間中，以保持歐式距離不變，從而使用戶根據(jù)距離進(jìn)行分割。然后對每個(gè)矢量添加高斯噪聲，這樣，可以在最小化添加噪聲量的同時(shí)最大化提高效用性，確保發(fā)布數(shù)據(jù)的隱私性。針對高維數(shù)值型數(shù)據(jù)(多個(gè)數(shù)值型屬性)，在處理較大屬性個(gè)數(shù)時(shí)誤差較大的問題，2020 年孫慧中等[54]滿足本地差分隱私的高維數(shù)值型數(shù)據(jù)收集算法(Multi-RPHM),與DPPro 算法不同之處的，用戶自己通過隨機(jī)投影對原始高維數(shù)據(jù)降維，然后發(fā)送給數(shù)據(jù)收集者，數(shù)據(jù)收集者再進(jìn)行維度還原，生成高維擾動數(shù)據(jù)集用于數(shù)據(jù)發(fā)布。

5 方法對比

本節(jié)將以上提到的技術(shù)及算法進(jìn)行匯總比較，列舉出了各種方法代表算法的優(yōu)缺點(diǎn)，如表1所示，基于特征抽取、貝葉斯網(wǎng)絡(luò)、樹模型、粗糙集、投影和差分隱私結(jié)合的方法比較。

表1 降維方法比較Table 1 Comparison of dimensionality reduction methods

續(xù)表1

為了更直觀比較各個(gè)技術(shù)的內(nèi)在聯(lián)系和主要區(qū)別，給出各個(gè)算法的針對不同場景的對比表格，包括PPCA 和DPPro、PrivBayes 和DPRers、PrivMN 和PrivHD 在不同場景下的優(yōu)缺點(diǎn)和數(shù)據(jù)可用性分析，如表2 所示。

表2 降維算法比較Table 2 Comparison of dimensionality reduction algorithms

6 結(jié)束語

大數(shù)據(jù)時(shí)代下，對高維數(shù)據(jù)的挖掘比以往任何時(shí)候都更加迫切，采用非常規(guī)手段往往會導(dǎo)致用戶隱私的泄露。差分隱私是一種被嚴(yán)格證明的隱私保護(hù)模型，可有效抵制各種安全攻擊。因此把差分隱私應(yīng)用到高維數(shù)據(jù)上可以有效實(shí)現(xiàn)數(shù)據(jù)的隱私安全保障。本文就高維數(shù)據(jù)的差分隱私模型作出詳細(xì)歸納總結(jié)，包括將特征降維、貝葉斯網(wǎng)絡(luò)、樹模型等方法與其結(jié)合應(yīng)用，分析了不同方法的優(yōu)缺點(diǎn)和應(yīng)用場景。

未來，數(shù)據(jù)將會更加復(fù)雜多變，因此必定會產(chǎn)生更多問題。

1)屬性關(guān)聯(lián)性強(qiáng)。數(shù)據(jù)屬性之間往往存在關(guān)聯(lián)性，隨著數(shù)據(jù)維度的增加，屬性間的關(guān)聯(lián)性更加復(fù)雜。近期提出一些研究方法，如通過粗糙集的屬性依賴度去度量屬性的關(guān)系程度，然后針對不同屬性添加不同的噪聲。但相關(guān)研究的文章仍然較少，未來有較大的空間亟待研究。

2)算法復(fù)雜度高。目前，差分隱私在高維數(shù)據(jù)的應(yīng)用大多停留在實(shí)驗(yàn)階段，往往伴隨著較高的時(shí)間復(fù)雜度，導(dǎo)致算法的效率較低，無法高效地應(yīng)用到生產(chǎn)實(shí)踐中。因此，亟需對算法進(jìn)行優(yōu)化，以滿足實(shí)際應(yīng)用的需要。