褚治廣 張 興 張青云 李曉會(huì) 李萬(wàn)杰

(遼寧工業(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ù)會(huì)致使個(gè)人隱私的嚴(yán)重泄露。因此,數(shù)據(jù)發(fā)布者需要通過(guò)特殊的保護(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ī)擾動(dòng)[6-8]、凝聚[9-10]、交換技術(shù)[11]、注入噪聲[12-13]等。

作為基于數(shù)據(jù)失真的差分隱私保護(hù)技術(shù),已成為隱私保護(hù)重點(diǎn)研究方向之一?，F(xiàn)階段,對(duì)于數(shù)據(jù)發(fā)布的研究主要聚焦于一維或低維數(shù)據(jù)。然而,這些數(shù)據(jù)發(fā)布方法均不適用于高維數(shù)據(jù)的發(fā)布,無(wú)法解決在處理高維數(shù)據(jù)發(fā)布時(shí),隨著維度和維度值域的增加,形成的發(fā)布空間以指數(shù)型增長(zhǎng),遭遇“維度災(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中,為了降低成分分析方法在降維過(guò)程中的時(shí)間和空間成本,提出一種優(yōu)化主成分分析(PCAO)的方法。利用屬性重要性對(duì)屬性進(jìn)行過(guò)濾,壓縮數(shù)據(jù)空間,從而優(yōu)化了高維數(shù)據(jù)降維時(shí)占用空間大、處理時(shí)間長(zhǎng)的問題。此外,為了解決優(yōu)化算法中主成分?jǐn)?shù)量(k)的選取問題,引入基于互信息的評(píng)價(jià)機(jī)制對(duì)原始數(shù)據(jù)和已發(fā)布數(shù)據(jù)進(jìn)行評(píng)價(jià),確定最優(yōu)k。

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

4) 對(duì)不同的真實(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)工作

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

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

基于以上分析,本文提出一種改進(jìn)的成分分析優(yōu)化的差分隱私高維數(shù)據(jù)發(fā)布方法ICAHDP。該方法通過(guò)引入屬性重要度和互信息評(píng)價(jià)機(jī)制對(duì)PCA進(jìn)行優(yōu)化,利用優(yōu)化后的主成分分析法(PCAO)對(duì)數(shù)據(jù)進(jìn)行降維。在數(shù)據(jù)降維的過(guò)程中,設(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ù)通過(guò)向原始數(shù)據(jù)集的轉(zhuǎn)換或其統(tǒng)計(jì)結(jié)果添加噪聲來(lái)達(dá)到隱私保護(hù)的目的。該方法確保了在任一數(shù)據(jù)集中更改一條記錄的操作而不影響查詢的輸出結(jié)果。此外,該模型可以抵御攻擊者掌握了除某一記錄外的所有信息的背景知識(shí)攻擊。

定義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,對(duì)于任一查詢函數(shù)f：D→Rd,其敏感度為Δf,則隨機(jī)算法A(D)=f(D)+Y提供ε-差分隱私保護(hù)。其中,Y～Lap(Δf/ε)為隨機(jī)噪聲,表示Y是服從尺度參數(shù)為Δf/ε的Laplace噪聲分布。

Laplace機(jī)制[23]通過(guò)將服從Laplace分布的噪聲介入準(zhǔn)確的查詢統(tǒng)計(jì)結(jié)果來(lái)達(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ī)變量間相互依賴性的量度。它度量?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)是通過(guò)對(duì)多個(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ù)方法都會(huì)遭受維度“災(zāi)難”的問題,引入較大的噪聲,導(dǎo)致發(fā)布的數(shù)據(jù)的可用性很低。因此,在高維數(shù)據(jù)發(fā)布中,設(shè)計(jì)出既能解決維度災(zāi)難帶來(lái)數(shù)據(jù)可用性較低的問題又能滿足數(shù)據(jù)隱私安全的發(fā)布方法是亟需迫切的。本文提出一種基于主成分分析優(yōu)化的差分隱私高維數(shù)據(jù)發(fā)布保護(hù)方法,對(duì)高維數(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) 首先確定屬性重要度閾值,對(duì)原始數(shù)據(jù)中的屬性進(jìn)行篩選,將原始數(shù)據(jù)中的無(wú)用屬性和缺失值較多的屬性剔除。

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

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

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

3.3 篩選屬性

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

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

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

(6)

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

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

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

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

(7)

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

Cov=UTCU

(8)

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

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

(9)

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

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

(10)

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

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

定義5敏感偏好度。為了便于在隱私保護(hù)過(guò)程中定量分析敏感屬性的偏好,需要對(duì)敏感屬性偏好進(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ù)擁有者要求對(duì)敏感屬性數(shù)據(jù)進(jìn)行保護(hù)的傾向程度,可以由數(shù)據(jù)擁有者的主觀評(píng)價(jià)或敏感程度而確定。敏感偏好度越大,該敏感屬性的隱私保護(hù)需求越高,反之,敏感偏好度越小,該敏感屬性的隱私保護(hù)需求越低。

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

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

定義6隱私造價(jià)。設(shè)Tij=Gi×εj是隱私預(yù)算為εj對(duì)于隱私保護(hù)強(qiáng)度Gi對(duì)應(yīng)的敏感偏好等級(jí)的隱私造價(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è)敏感屬性等級(jí)之間的連線形成的圖為一個(gè)偏好隱私預(yù)算分配圖PA。

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

算法1加噪方法

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

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

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

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

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

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

本文引進(jìn)互信息的概念,通過(guò)計(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對(duì)優(yōu)化主成分分析的高維數(shù)據(jù)發(fā)布的實(shí)現(xiàn)進(jìn)行了概述。利用屬性重要度篩選屬性、最優(yōu)主成分個(gè)數(shù)k的確定方法對(duì)主成分分析法在差分隱私數(shù)據(jù)發(fā)布中的改進(jìn),很大程度地提升了數(shù)據(jù)的可用性和減少了數(shù)據(jù)處理的時(shí)間。

算法2ICAHDP

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

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

1.對(duì)每一個(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.對(duì)投影矩陣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)評(píng)價(jià)

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

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是美國(guó)人口普查數(shù)據(jù),記錄了48 842條個(gè)人信息;Diabetes是1999年-2008年美國(guó)130家醫(yī)院的糖尿病患者數(shù)據(jù),記錄了101 767條糖尿病患者信息;TIC是某保險(xiǎn)公司的客戶信息數(shù)據(jù),記錄了98 220條客戶信息。數(shù)據(jù)集的數(shù)據(jù)類型、樣本數(shù)及維度如表2所示。

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

為了評(píng)估本文算法的性能,分別采用以上三種數(shù)據(jù)集,對(duì)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ù)測(cè)。本文針對(duì)不同數(shù)據(jù)集選取不同的屬性作為分類屬性。為進(jìn)一步評(píng)價(jià)算法的有效性,使用誤分類率(Misclassification rate)作為數(shù)據(jù)可用性的衡量標(biāo)準(zhǔn),來(lái)度量發(fā)布數(shù)據(jù)的SVM分類結(jié)果的準(zhǔn)確性。

首先在Adult、Diabetes、TIC數(shù)據(jù)集上,通過(guò)5種算法生成添加噪聲后的發(fā)布數(shù)據(jù)集,將70%的生成數(shù)據(jù)作為訓(xùn)練集,30%的數(shù)據(jù)作為測(cè)試集,然后在發(fā)布數(shù)據(jù)集上構(gòu)建SVM分類器?；?種算法為隨機(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ù)測(cè)。在Diabetes數(shù)據(jù)集上,分別以是否為男性、是否再次入住醫(yī)院作為分類屬性做出預(yù)測(cè)。在TIC數(shù)據(jù)集上,分別以否擁有房子、是否結(jié)婚作為分類屬性做出預(yù)測(cè)。

圖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ù)映射到低維空間,通過(guò)將隱私預(yù)算分配給低維數(shù)據(jù),可以將噪聲添加到更加敏感的屬性中。對(duì)于其他屬性,將會(huì)減少噪聲干擾,使數(shù)據(jù)的實(shí)用性得到極大的提高,最終產(chǎn)生發(fā)布的數(shù)據(jù)比其他解決方案具有更好的實(shí)用性。

5 結(jié) 語(yǔ)

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