張娛嘉,張景璐

(1.智己汽車(chē)科技有限公司,上海 201210;2.北京電子科技職業(yè)學(xué)院,北京 100176)

0 引言

使用各種軟件工具和算法對(duì)大量數(shù)據(jù)進(jìn)行抓取和處理是現(xiàn)代常見(jiàn)的獲取信息途徑。 其中聚類分析是一門(mén)重要技術(shù),把相似的對(duì)象通過(guò)靜態(tài)分類的方法分成多種組別和子集,每種子集具有相似的特征和屬性,作為一種非監(jiān)督性學(xué)習(xí),聚類分析可以有效處理數(shù)據(jù)挖掘、模式識(shí)別,圖像分析、網(wǎng)絡(luò)入侵檢測(cè)、大規(guī)模定位和市場(chǎng)細(xì)分等領(lǐng)域的問(wèn)題。

針對(duì)內(nèi)容的聚類分析和數(shù)據(jù)挖掘等技術(shù)的應(yīng)用中,存在兩個(gè)問(wèn)題,首先是信息的收集與處理需要考慮到隱私保護(hù)問(wèn)題,包括個(gè)人的重要身份信息,利用這些信息可能直接或者間接追溯到具體的個(gè)人,另外數(shù)據(jù)挖掘提供有價(jià)值信息的同時(shí)還可能泄露團(tuán)體的行為等敏感信息,要在發(fā)布信息時(shí)確切保護(hù)好用戶個(gè)人權(quán)益,就需要用差分隱私保護(hù)。

其次是龐大數(shù)據(jù)量帶來(lái)的效率問(wèn)題,對(duì)海量混雜的大數(shù)據(jù)進(jìn)行相關(guān)性查找和模式分析時(shí),單個(gè)計(jì)算機(jī)難以保證時(shí)間和效率,可以用并行的分布式計(jì)算。

聚類分析將未標(biāo)記的數(shù)據(jù)集劃分為簇,最廣為使用的算法即是Lloyd’s algorithm,也稱為K-means,Kmeans 需要選擇的參數(shù)較少,只需要選擇的參數(shù)是K,也就是所需要的簇?cái)?shù)和速度,使用分布式計(jì)算的MapReduce 框架來(lái)實(shí)現(xiàn)K-means[1]。 本文提出一種基于MapReduce 的K-means 差分隱私保護(hù)法,應(yīng)對(duì)多種背景下的惡意分析。

1 差分隱私保護(hù)

定義相鄰兩個(gè)數(shù)據(jù)集,若存在兩個(gè)數(shù)據(jù)庫(kù)名為D和D’,在兩個(gè)數(shù)據(jù)庫(kù)中,有n條數(shù)據(jù),狀態(tài)為1 或者0(ai= 1 或者0),這些數(shù)據(jù)形成一個(gè)集合{a1,a2,a3,...,an},這兩個(gè)集合就是相鄰集合。 定義一個(gè)隨機(jī)算法A,對(duì)同樣的輸入,該算法的輸出不是固定值,而是服從某一個(gè)分布,這個(gè)算法分別作用于上述兩個(gè)相鄰數(shù)據(jù)集,得到的兩個(gè)輸出分布會(huì)變得難以區(qū)分,所以差分隱私形式化的定義為:

Pr{A(D)=O} ≤e?Pr{A(D＇)=O}

當(dāng)算法A 作用相鄰數(shù)據(jù)集后,最終得到輸出O 的概率相差較小時(shí),可以認(rèn)為這個(gè)算法能達(dá)到差分隱私的效果,這樣觀察者僅僅通過(guò)觀察數(shù)據(jù)處理結(jié)果,很難找出具體某條數(shù)據(jù)的變化,從而保護(hù)數(shù)據(jù)集的隱私問(wèn)題。

從兩個(gè)數(shù)據(jù)集的拉普拉斯隨機(jī)分布圖看,在lamda為0.5,數(shù)據(jù)集A 值為-5,5,數(shù)據(jù)集B 為-4,5 的情況下,兩個(gè)laplace 分布呈現(xiàn)如圖1 所示的結(jié)果,保護(hù)隱私的目的需要使兩個(gè)分布盡可能接近。

圖1 數(shù)據(jù)集的Laplace 分布

Pr{A(D)=O}≤e?·Pr{A(D＇)=O}+δ,δ是一個(gè)較小的常數(shù),使用高斯噪聲(Gaussian noise)就可以。新的常數(shù)加入,最終結(jié)果不可避免會(huì)不準(zhǔn)確,在數(shù)據(jù)量較大時(shí)噪聲的影響比較小,否則就會(huì)導(dǎo)致結(jié)果偏離準(zhǔn)確值,需要將δ設(shè)置成較小數(shù)值。 目標(biāo)是在更少的隱私預(yù)算下得到相同的噪聲尺度。

2 MapReduce 框架下的DP K-means 算法

K-means 每次迭代分為兩個(gè)階段,第一是去計(jì)算最接近均值μi的點(diǎn)的集合Si,第二是將這些新均值作為這些集合的質(zhì)心,這兩個(gè)階段分別是MapReduce 算法的Map 和Reduce 階段。 Map 階段對(duì)數(shù)據(jù)集中的每個(gè)點(diǎn)x 進(jìn)行操作。 最小化這個(gè)給定的x 的距離,計(jì)算x和每個(gè)平均值之間的平方距離,找到最后的平均值μi,發(fā)出一個(gè)鍵值對(duì),索引i 作為鍵,值是(x, 1)。 函數(shù)是:

如圖2 所示,假如相鄰數(shù)據(jù)A 與數(shù)據(jù)集B 的數(shù)據(jù)差分是數(shù)據(jù)n,對(duì)兩個(gè)數(shù)據(jù)集完成一系列查詢操作后,獲得結(jié)果1 和結(jié)果2,那么比對(duì)相鄰數(shù)據(jù)集A 和B 的差分和兩個(gè)結(jié)果1 和2 之間的差分,就可以明確得知研究對(duì)象n的具體數(shù)據(jù),如果有外部觀察者試圖破解結(jié)果,只能知道數(shù)據(jù)集B 與數(shù)據(jù)集A 相差n 條記錄,收集結(jié)果進(jìn)行分析后,分析者也無(wú)法得到單個(gè)記錄的信息。 所以MapReduce 框架下的K-means 算法,可以有效防止攻擊者因?yàn)楹?jiǎn)單的查詢操作而獲得新的信息[4]。

圖2 差分隱私算法應(yīng)對(duì)的攻擊模式

3 算法設(shè)計(jì)

4 可用性實(shí)驗(yàn)

為了驗(yàn)證新的Map-Reduce 模型進(jìn)行保護(hù)差分隱私的有效性,選擇“Blood”和“Gramma”數(shù)據(jù)庫(kù)來(lái)進(jìn)行驗(yàn)證,關(guān)注的兩個(gè)標(biāo)準(zhǔn)是召回率和精確率。 F-measure可以整合召回率和精確率,用F-measure 來(lái)證明集群可用性。 F-measure 越大,兩個(gè)聚類結(jié)果的相似性越強(qiáng),添加噪聲的算法對(duì)聚類的影響很小[8]。 將f 方法和標(biāo)準(zhǔn)數(shù)據(jù)集之間的相似性寫(xiě)為 F1,去對(duì)比方法和作為F2之間的相似性[9]。 運(yùn)行過(guò)程中,增加的噪聲服從拉普拉斯隨機(jī)分布,結(jié)果具有隨機(jī)性。

5 結(jié)語(yǔ)

本文利用基于MapReduce 的K-means 方法來(lái)實(shí)現(xiàn)差分隱私保護(hù),在MapReduce 的框架下,并行計(jì)算聚類,最終利用Laplace 的機(jī)制實(shí)現(xiàn)差分隱私保護(hù),同時(shí)提高了這個(gè)算法的效率和隱私性。