基于混洗差分的Web查詢大數(shù)據(jù)隱私保護方法

虞 娟

(馬鞍山師范高等?？茖W(xué)校 軟件工程系，安徽 馬鞍山 243000)

隨著科技和互聯(lián)網(wǎng)的不斷發(fā)展，Web網(wǎng)絡(luò)中的海量數(shù)據(jù)成為一筆巨大的財富。信息化時代的發(fā)展潮流是利用這些數(shù)據(jù)對各行各業(yè)的狀態(tài)進行分析實現(xiàn)數(shù)據(jù)共享[1-2]。然而數(shù)據(jù)共享時對Web大數(shù)據(jù)進行查詢過程中，會導(dǎo)致個人隱私泄露的概率加大。因此，Web查詢大數(shù)據(jù)的隱私保護受到普遍重視[3-4]。

大數(shù)據(jù)的隱私保護成為研究人員的研究主題。例如周藝華等人提出通過GeoHash算法用字符串代替查詢用戶的位置，并構(gòu)建Trie前綴樹，LBS服務(wù)器在前綴樹的基礎(chǔ)上匹配字符串，然后發(fā)送給用戶，通過此過程保護用戶信息，但是該方法只保護查詢用戶的位置信息，并未對查詢的數(shù)據(jù)進行隱私保護[5]。顧一鳴等人通過預(yù)先緩存機制實現(xiàn)連續(xù)查詢數(shù)據(jù)的隱私保護，其可有效處理連續(xù)查詢過程中出現(xiàn)的最大移動邊界攻擊問題，通過預(yù)先緩存的方法使得連續(xù)查詢數(shù)據(jù)的時間關(guān)聯(lián)度降低，增強數(shù)據(jù)隱私保護水平，但是該種方法隱私保護過程中未進行數(shù)據(jù)冗余的過濾處理，導(dǎo)致數(shù)據(jù)隱私保護效果大大降低[6]。

混洗差分隱私模型將洗牌者插入大數(shù)據(jù)和數(shù)據(jù)收集者之中，洗牌者接收混入噪聲的數(shù)據(jù)，并將其混洗，然后輸送給收集者分析，用戶和大數(shù)據(jù)之間關(guān)聯(lián)性通過洗牌操作切斷，有效地實現(xiàn)大數(shù)據(jù)的隱私保護[7]。

因此，本文提出一種基于混洗差分的Web查詢大數(shù)據(jù)隱私保護方法，保護查詢大數(shù)據(jù)隱私不被泄露。

1 Web查詢大數(shù)據(jù)隱私保護

在大數(shù)據(jù)環(huán)境的Web查詢系統(tǒng)中，由于一些查詢的數(shù)據(jù)具有關(guān)聯(lián)性，數(shù)據(jù)存在冗余現(xiàn)象。為了減少冗余數(shù)據(jù)量，通過關(guān)聯(lián)性分析刪去關(guān)聯(lián)數(shù)據(jù)[8-9]，減少大規(guī)模數(shù)據(jù)的數(shù)據(jù)量。此外在查詢數(shù)據(jù)時，不僅需要提高查詢系統(tǒng)的數(shù)據(jù)處理速度[10]，而且需要對查詢數(shù)據(jù)進行隱私保護，綜合以上問題，本文提出基于混洗差分的Web查詢大數(shù)據(jù)隱私保護方法。

基于混洗差分的Web查詢大數(shù)據(jù)隱私保護方法包括3個子模型：基于最大信息系數(shù)的特征選擇模型(MICFS)、并行梯度下降矩陣分解模型(PGMDM)和基于混洗差分的洗牌者多維擾動發(fā)布模型。

Web查詢大數(shù)據(jù)隱私保護過程如下：

(1)查詢數(shù)據(jù)集；

(2)通過MICFS求解數(shù)據(jù)間的相關(guān)性并設(shè)定閾值，將無關(guān)性數(shù)據(jù)構(gòu)建成特征數(shù)據(jù)集；

(3)根據(jù)特征數(shù)據(jù)集構(gòu)建相關(guān)性低的無關(guān)負(fù)載矩陣，通過并行梯度下降矩陣分解模型分解該無關(guān)負(fù)載矩陣；

(4)通過基于混洗差分的洗牌者多維擾動發(fā)布模型實現(xiàn)無關(guān)負(fù)載矩陣的隱私保護；

(5)發(fā)送添加擾動后的結(jié)果給查詢者。

1.1 基于最大信息系數(shù)的特征選擇模型的冗余數(shù)據(jù)處理

Web查詢系統(tǒng)具有數(shù)據(jù)量大、查詢次數(shù)多的特點，為了提高Web查詢大數(shù)據(jù)查詢的提取速度，依據(jù)用戶的查詢信息構(gòu)建一個查詢數(shù)據(jù)集。根據(jù)最大信息系數(shù)和啟發(fā)式搜索算法，在該查詢數(shù)據(jù)集里，設(shè)定特征和類別、特征和特征的關(guān)聯(lián)性，將無關(guān)性數(shù)據(jù)構(gòu)建成特征集。利用基于最大信息系數(shù)的特征選擇模型，去掉冗余數(shù)據(jù)。

設(shè)定存在一個n條樣本的Web查詢大數(shù)據(jù)特征集，用m表示特征數(shù)，用c表示類別。特征集表示為：F={f1,f2,…,fm,c}。用MIC(fi,c)表示任意特征fi和類別c的相關(guān)性，且MIC(fi,c)∈[0,1]。MIC(fi,c)值的大小，決定fi和c的相關(guān)性的強弱，其值越大，相關(guān)性越強，此時的fi是強相關(guān)特征；其值越小，相關(guān)性越弱，此時的fi是弱相關(guān)特征。用MIC(fi,fj)描述fi與fj的相關(guān)性，fi和fj的可替代性隨著MIC(fi,fj)值的增大而增強，若MIC(fi,fj)=0，則fi和fj沒有可替代性，二者之間相互獨立。

利用MICFS對數(shù)據(jù)集的無關(guān)性處理。該過程通過以下5步實現(xiàn)，流程圖如圖1所示。

(1)在n條樣本的特征F={f1,f2,…,fm,c}中，確定其原始數(shù)據(jù)集D和空集B。

(2)求解該特征集中特征fi和類別c的最大值MIC(fi,c)。

(3)將第(2)步中的最大值當(dāng)作初始變量，D=D-(fi)，B=B+(fi)。

(4)通過貪心算法求解出fi和fj中的最大值MIC(fB,fi)，將其當(dāng)成下個候選變量，求解出新候選變量的最大值如式(1)所示。

(1)

(5)重復(fù)操作第(4)步，選定特征的個數(shù)等于設(shè)定值時結(jié)束操作，并用選定的特征構(gòu)建數(shù)據(jù)集B。

1.2 基于并行梯度下降矩陣分解模型的Web查詢大數(shù)據(jù)的快速提取

用戶通過Web查詢系統(tǒng)查詢數(shù)據(jù)時，存在數(shù)據(jù)量多以及查詢回合多的問題，是一種批量線性查詢過程。為了進一步提高用戶對Web查詢大數(shù)據(jù)的提取速度，通過融合交替方向乘子法和低秩機制形成的并行梯度下降矩陣分解模型，將分解后的查詢數(shù)據(jù)無關(guān)負(fù)載矩陣并行處理，減少Web查詢大數(shù)據(jù)的查詢時間[11-12]。

(2)

(3)

其中，W表示根據(jù)特征數(shù)據(jù)集B構(gòu)建無關(guān)負(fù)載矩陣；將W分解成A和L兩個矩陣；β表示分解系數(shù)。A是隨著L的更新而更新，式(2)用來計算A。

并行梯度下降矩陣分解模型以矩陣的特性為基礎(chǔ)，將W分解成多個矩陣，并將這些矩陣分別發(fā)放到各個節(jié)點上，并完成計算。矩陣分解過程如圖2所示。

PGMDM主要通過以下幾步完成。

(1)以用戶查詢要求為基礎(chǔ)，構(gòu)建初始結(jié)果負(fù)載矩陣。

(2)以通過基于最大信息系數(shù)的特征選擇模型得出關(guān)聯(lián)屬性為依據(jù)，初始化查詢數(shù)據(jù)的負(fù)載矩陣，刪去負(fù)載矩陣中有關(guān)聯(lián)的數(shù)據(jù)，形成無關(guān)負(fù)載矩陣。

1.3 基于混洗差分的查詢數(shù)據(jù)隱私保護模型

1.3.1 混洗差分隱私

通過Randomized Response(RR)機制擾動真實數(shù)據(jù)。本地化差分隱私模型(LDP)利用RR機制完成自身數(shù)據(jù)擾動，進而實現(xiàn)Web查詢大數(shù)據(jù)的隱私保護。RR機制定義為：已知值域D={1,2,…,d}，用戶發(fā)送真實值概率為p，任意選取值域內(nèi)一個數(shù)值的概率為q。RR機制符合如式(4)所示。

(4)

混洗差分隱私將并行梯度下降矩陣分解模型后的無關(guān)負(fù)載矩陣L中的數(shù)據(jù)，作為用戶ui的Web查詢數(shù)據(jù)，將這些查詢數(shù)據(jù)作為數(shù)據(jù)集[14]，ti為ui中的數(shù)據(jù)且ti∈V。所有用戶ui符合εl的本地化差分隱私算法R:V→Y擾動vi:yi=R(vi)。受擾動后，n個用戶的擾動結(jié)果用O={y1,y2,…,yn}描述，第i個用戶的擾動結(jié)果用yi描述[15]，洗牌者對yi隨機洗牌操作用S:Yi→Yn描述。以上兩步的結(jié)合用機制M=R○S描述，M符合(εc,δ)混洗差分隱私。當(dāng)且僅當(dāng)針對任意數(shù)據(jù)集D和D′(二者之間僅相差一個用戶數(shù)據(jù))，任意輸出集合Y′?Yn，存在式(5)。

Pr[M(D)∈y′]≤δ+eεc×Pr[M(D′)∈y′]

(5)

在混洗差分隱私模型中，隱私毯子為用戶根據(jù)查詢得到的隨機答復(fù)。本地化差分隱私模型形成的分布可分解為真實值分布和隨機獨立分布(隱私毯子)，此過程叫做隱私毯子分解。式(5)可分解為如式(6)所示。

[RR(v)=y]=γPr[Uni(D)=y]+

(1-γ)PrV(y)

(6)

由于大數(shù)據(jù)中具有多維數(shù)據(jù)，維度高與取值域異構(gòu)的多維數(shù)據(jù)導(dǎo)致發(fā)布過程困難，因此本文提出基于混洗差分的洗牌者多維擾動發(fā)布模型解決此問題，實現(xiàn)大數(shù)據(jù)的隱私保護。

1.3.2 基于混洗差分的洗牌者多維擾動發(fā)布模型

混洗差分通過洗牌操作可對用戶同帶噪數(shù)據(jù)間的關(guān)聯(lián)性進行打亂操作，增強數(shù)據(jù)隱私保護性。因此，通過基于混洗差分的洗牌者多維擾動發(fā)布模型，實現(xiàn)Web查詢大數(shù)據(jù)的隱私保護。

通過統(tǒng)計數(shù)據(jù)的頻率分布，收集者以帶噪數(shù)據(jù)維度為基礎(chǔ)，并對其編號，再根據(jù)編號分組，得出第i個屬性取值是v的頻率信息如式(7)所示。

(7)

收集者依據(jù)洗牌后的數(shù)據(jù)完成頻率估計，依據(jù)該估計結(jié)果獲取誤差平方和SSE(sum square error)，通過SSE分析擾動的web大數(shù)據(jù)發(fā)布結(jié)果。本文提出滿足混洗差分隱私的多維類型數(shù)據(jù)頻率估計方法，可最大程度降低web大數(shù)據(jù)隱私保護的消耗，最大程度的確保大數(shù)據(jù)隱私保護時，發(fā)布的擾動數(shù)據(jù)誤差最小，且存在式(8)。

(8)

2 實驗分析

實驗以某Web網(wǎng)絡(luò)中的查詢數(shù)據(jù)集：Kosarak數(shù)據(jù)集(二進制)和Mexico數(shù)據(jù)集(非二進制)為實驗對象，描述數(shù)據(jù)的具體信息如表1所示。

表1 數(shù)據(jù)集

采用本文方法在不同的無關(guān)性系數(shù)情況下，分析Mexico數(shù)據(jù)集和Kosarak數(shù)據(jù)集的無關(guān)性，結(jié)果分別如表2所示。

表2 數(shù)據(jù)集數(shù)據(jù)無關(guān)性分析

通過表1、表2可以看出，經(jīng)過本文方法對Kosarak和Mexico數(shù)據(jù)集進行數(shù)據(jù)無關(guān)處理后，在不同取值的無關(guān)性系數(shù)下，Kosarak和Mexico數(shù)據(jù)集包含的項均顯著減少，說明本文方法有效降低了實驗Web大數(shù)據(jù)集中的冗余數(shù)據(jù)，為后續(xù)數(shù)據(jù)隱私保護提供可靠的基礎(chǔ)。

本次實驗驗證本文方法對Kosarak數(shù)據(jù)集和Mexico數(shù)據(jù)集的隱私保護能力，實驗改變隱私預(yù)算εc的值，通過誤差平方和(SSE)分析本文方法對兩種實驗數(shù)據(jù)集中數(shù)據(jù)的混洗擾動發(fā)布結(jié)果，結(jié)果如圖3所示。

圖3 隱私保護結(jié)果

由圖3可以看出，采用本文方法對Kosarak數(shù)據(jù)集隱私保護時，在εc<0.2時，隱私數(shù)據(jù)擾動發(fā)布的SSE逐漸減小，εc≥0.2時SSE趨于穩(wěn)定，數(shù)據(jù)擾動發(fā)布保護效果越好。采用本文方法對Mexico數(shù)據(jù)集進行隱私保護時，在εc<0.4時，隱私數(shù)據(jù)擾動發(fā)布的SSE逐漸減小，εc≥0.4時SSE趨于穩(wěn)定，數(shù)據(jù)擾動發(fā)布保護效果越好。

本文方法對Mexico數(shù)據(jù)集中包含網(wǎng)絡(luò)數(shù)據(jù)進行隱私保護，保護前后的對比結(jié)果見圖4。

(a)保護前

通過圖4實驗結(jié)果可以看出，本文方法可以實現(xiàn)Web網(wǎng)絡(luò)查詢信息的保護處理，保護后的網(wǎng)絡(luò)信息安全性高，不易被非法者窺探。

以保護后的Web查詢大數(shù)據(jù)隱私被攻擊捕獲概率作為衡量指標(biāo)，隨機選取Mexico數(shù)據(jù)集，測試該數(shù)據(jù)集在不同查詢數(shù)據(jù)規(guī)模時，Web查詢數(shù)據(jù)在被本文方法保護前后的被捕獲概率，結(jié)果用圖5描述。

圖5 捕獲概率統(tǒng)計

分析圖5可以看出，當(dāng)Web查詢數(shù)據(jù)規(guī)模不同時，數(shù)據(jù)隱私被捕獲的概率出現(xiàn)無規(guī)律分布狀態(tài)，主要是因為Web網(wǎng)絡(luò)的攻擊類型具有多樣性，導(dǎo)致攻擊捕獲數(shù)據(jù)隱私的概率也呈現(xiàn)出無規(guī)則狀態(tài)。當(dāng)數(shù)據(jù)量相同時，采用本文方法進行隱私保護后數(shù)據(jù)隱私被攻擊捕獲的概率，遠(yuǎn)遠(yuǎn)低于未采用本文方法進行隱私保護的數(shù)據(jù)隱私被捕獲的概率。該結(jié)果說明：本文方法可有效降低Web查詢大數(shù)據(jù)隱私被捕獲的概率。

3 結(jié)論

在Web查詢大數(shù)據(jù)隱私保護中引入混洗差分的方法，提出基于混洗差分的Web查詢大數(shù)據(jù)隱私保護方法。該方法通過基于最大信息系數(shù)的特征選擇模型、并行梯度下降矩陣分解模型和基于混洗差分的洗牌者多維擾動發(fā)布模型實現(xiàn)Web查詢大數(shù)據(jù)隱私保護，為Web查詢大數(shù)據(jù)隱私保護提供一種新方法，未來在查詢大數(shù)據(jù)隱私保護問題上可大量應(yīng)用本文方法。