改進(jìn)成分分析的差分隱私高維數(shù)據(jù)發(fā)布方法

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

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

0 引 言

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

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

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

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

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

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

3) 考慮了高維數(shù)據(jù)中多敏感屬性的存在,而傳統(tǒng)的隱私預(yù)算分配方法不能滿足個(gè)性化的隱私保護(hù)。將敏感偏好度和最優(yōu)匹配理論相結(jié)合,設(shè)計(jì)了敏感屬性層次保護(hù)策略,使高維數(shù)據(jù)在不同隱私要求下能夠發(fā)布。

4) 對不同的真實(shí)數(shù)據(jù)集進(jìn)行廣泛的實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明,與PrivBayes[14]和JTree[15]等方法相比,ICAHDP不僅保證了已發(fā)布數(shù)據(jù)集的隱私性,而且顯著提高了數(shù)據(jù)的準(zhǔn)確性和實(shí)用性。

1 相關(guān)工作

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

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

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

2 相關(guān)定義

2.1 差分隱私

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

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

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

(1)

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

實(shí)現(xiàn)差分隱私保護(hù)常介入兩種噪聲機(jī)制,分別是拉普拉斯機(jī)制和指數(shù)機(jī)制[22]。本文主要采用Laplace噪聲機(jī)制。

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

Laplace機(jī)制[23]通過將服從Laplace分布的噪聲介入準(zhǔn)確的查詢統(tǒng)計(jì)結(jié)果來達(dá)到ε-差分隱私保護(hù)的目的。設(shè)Laplace分布Lap(b)位置參數(shù)為0的概率密度函數(shù)為p(x),其表示形式為：

(2)

2.2 信息熵與互信息

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

定義3設(shè)X是一個(gè)離散型隨機(jī)變量,則X的信息熵為：

(3)

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

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

(4)

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

由式(3)和式(4)推導(dǎo)可得互信息與信息熵之間的關(guān)系：

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

(5)

2.3 主成分分析法

主成分分析法[26](PCA)是通過對多個(gè)原始隨機(jī)變量組成的數(shù)據(jù)集X={x1,x2,…,xn}的協(xié)方差矩陣進(jìn)行分解,重新組合轉(zhuǎn)變?yōu)樯贁?shù)幾個(gè)各維度間互不相關(guān)的變量Q={y1,y2,…,ym},m

3 改進(jìn)的高維數(shù)據(jù)發(fā)布方法

3.1 問題描述

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

3.2 高維數(shù)據(jù)發(fā)布機(jī)制

改進(jìn)的成分分析優(yōu)化的差分隱私高維數(shù)據(jù)發(fā)布方法的運(yùn)行機(jī)制如圖1所示。

圖1 成分分析優(yōu)化的差分隱私高維數(shù)據(jù)發(fā)布框架

基于主成分分析優(yōu)化的差分隱私高維數(shù)據(jù)發(fā)布方法具體的步驟如下：

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

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

3) 在滿足差分隱私的前提下,對數(shù)據(jù)屬性的敏感偏好進(jìn)行分級,并結(jié)合最優(yōu)匹配理論來分配隱私預(yù)算。將不同大小的噪聲添加到數(shù)據(jù)集中不同敏感偏好的屬性中,實(shí)現(xiàn)個(gè)性化的噪聲添加方法,使發(fā)布的數(shù)據(jù)具有更好的可用性。

4) 在數(shù)據(jù)的降維過程中,進(jìn)行多次的主成分個(gè)數(shù)k值的選取,通過互信息評價(jià)機(jī)制,計(jì)算原始數(shù)據(jù)與加噪數(shù)據(jù)的互信息,確定最優(yōu)的k值,從而確定最佳的發(fā)布數(shù)據(jù)。

3.3 篩選屬性

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

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

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

(6)

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

3.4 數(shù)據(jù)降維加噪

若數(shù)據(jù)集D經(jīng)篩選屬性后產(chǎn)生的數(shù)據(jù)集為Do,利用主成分分析法對其進(jìn)行降維,降維過程如下：

計(jì)算樣本的協(xié)方差矩陣：

(7)

對協(xié)方差矩陣進(jìn)行特征分解：

Cov=UTCU

(8)

式中：C表示Cov特征分解后的對角矩陣;U表示特征值所對應(yīng)的特征向量構(gòu)成的特征矩陣。

選取k個(gè)特征值所對應(yīng)的k個(gè)特征向量組成矩陣Uk,將原始數(shù)據(jù)投影到矩陣Uk上,得到投影矩陣：

(9)

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

還原得到原始數(shù)據(jù)矩陣的低階近似矩陣：

(10)

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

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

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

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

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

根據(jù)敏感屬性敏感偏好度值spi,將敏感屬性劃分為m個(gè)等級,對應(yīng)m個(gè)隱私保護(hù)強(qiáng)度。差分隱私保護(hù)強(qiáng)度與隱私預(yù)算有關(guān),每個(gè)等級對應(yīng)一個(gè)隱私預(yù)算,如表1所示。

表1 敏感屬性等級與隱私預(yù)算對應(yīng)表

定義6隱私造價(jià)。設(shè)Tij=Gi×εj是隱私預(yù)算為εj對于隱私保護(hù)強(qiáng)度Gi對應(yīng)的敏感偏好等級的隱私造價(jià)。

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

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

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

算法1加噪方法

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

輸出：最優(yōu)匹配PM。

1. 對于每一個(gè)Pi做以下操作：

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

3. 對于每一個(gè)隱私預(yù)算εj做以下操作：

4. 計(jì)算Tij

5. 偏好隱私預(yù)算分配圖PA

6.IF存在完美匹配

7. 結(jié)束匹配

8. 獲得最優(yōu)匹配方案PM

9.Else

10. Pli+1

11. 返回第5步

12.End

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

3.5 互信息評價(jià)機(jī)制

本文引進(jìn)互信息的概念,通過計(jì)算不同主成分個(gè)數(shù)k值下的噪聲數(shù)據(jù)與原始數(shù)據(jù)的互信息大小,利用均值法,將最接近均值的k值,作為發(fā)布數(shù)據(jù)安全性和實(shí)用性達(dá)到最優(yōu)的主成分個(gè)數(shù)。

互信息越大,變量之間的相關(guān)性越強(qiáng),數(shù)據(jù)實(shí)用性越強(qiáng)。用互信息去衡量加噪后的數(shù)據(jù)集更接近原始數(shù)據(jù)集的關(guān)系是可行的。

3.6 算法描述

基于主成分分析優(yōu)化的差分隱私高維數(shù)據(jù)發(fā)布算法如算法2所示。算法2對優(yōu)化主成分分析的高維數(shù)據(jù)發(fā)布的實(shí)現(xiàn)進(jìn)行了概述。利用屬性重要度篩選屬性、最優(yōu)主成分個(gè)數(shù)k的確定方法對主成分分析法在差分隱私數(shù)據(jù)發(fā)布中的改進(jìn),很大程度地提升了數(shù)據(jù)的可用性和減少了數(shù)據(jù)處理的時(shí)間。

算法2ICAHDP

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

輸出：發(fā)布數(shù)據(jù)集S″。

1.對每一個(gè)屬性做以下操作：

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

5.END IF

6.END

7.計(jì)算b11,bi21,…,bp1

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

12.計(jì)算Cov=UTCU,

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

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

14.k值的選取,根據(jù)互信息值確定

15.計(jì)算得到投影矩陣Zk×n

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

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

19.計(jì)算e11,e21,…,ep1

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

21.還原數(shù)據(jù)集S″

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

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

3.7 算法隱私保護(hù)效果分析

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

證明由算法可知：

噪聲矩陣為：

由Laplace機(jī)制即證：

因?yàn)樘卣飨蛄烤仃嘦p×k中的任意兩個(gè)特征向量互相正交,則有：

所以：

得證。

得出結(jié)論：ICAHDP算法滿足ε-差分隱私保護(hù)。。

4 實(shí)驗(yàn)評價(jià)

為了對ICAHDP算法的有效性進(jìn)行驗(yàn)證,本節(jié)將采用具體的實(shí)驗(yàn)進(jìn)行分析說明。

4.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)環(huán)境：Windows 10操作系統(tǒng),Intel(R) Core(TM) i3-8100 CPU 3.6 GHz,16 GB內(nèi)存。所涉及的算法和代碼用Python實(shí)現(xiàn)。

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

表2 數(shù)據(jù)集描述

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

首先在Adult、Diabetes、TIC數(shù)據(jù)集上,通過5種算法生成添加噪聲后的發(fā)布數(shù)據(jù)集,將70%的生成數(shù)據(jù)作為訓(xùn)練集,30%的數(shù)據(jù)作為測試集,然后在發(fā)布數(shù)據(jù)集上構(gòu)建SVM分類器。基于5種算法為隨機(jī)算法,為了減少只進(jìn)行一次實(shí)驗(yàn)產(chǎn)生不可避免的誤差,因此在三種數(shù)據(jù)集上分別進(jìn)行了10次實(shí)驗(yàn),計(jì)算實(shí)驗(yàn)結(jié)果的平均值作為最終的實(shí)驗(yàn)結(jié)果。

4.2 實(shí)驗(yàn)結(jié)果分析

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

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

(a) Adult, education

(a) TIC, house

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

5 結(jié) 語

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