基于K-means 方法的MapReduce 模型社交網絡隱私保護研究

張娛嘉,張景璐

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

0 引言

使用各種軟件工具和算法對大量數據進行抓取和處理是現代常見的獲取信息途徑。 其中聚類分析是一門重要技術,把相似的對象通過靜態分類的方法分成多種組別和子集,每種子集具有相似的特征和屬性,作為一種非監督性學習,聚類分析可以有效處理數據挖掘、模式識別,圖像分析、網絡入侵檢測、大規模定位和市場細分等領域的問題。

針對內容的聚類分析和數據挖掘等技術的應用中,存在兩個問題,首先是信息的收集與處理需要考慮到隱私保護問題,包括個人的重要身份信息,利用這些信息可能直接或者間接追溯到具體的個人,另外數據挖掘提供有價值信息的同時還可能泄露團體的行為等敏感信息,要在發布信息時確切保護好用戶個人權益,就需要用差分隱私保護。

其次是龐大數據量帶來的效率問題,對海量混雜的大數據進行相關性查找和模式分析時,單個計算機難以保證時間和效率,可以用并行的分布式計算。

聚類分析將未標記的數據集劃分為簇,最廣為使用的算法即是Lloyd’s algorithm,也稱為K-means,Kmeans 需要選擇的參數較少,只需要選擇的參數是K,也就是所需要的簇數和速度,使用分布式計算的MapReduce 框架來實現K-means[1]。 本文提出一種基于MapReduce 的K-means 差分隱私保護法,應對多種背景下的惡意分析。

1 差分隱私保護

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

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

當算法A 作用相鄰數據集后,最終得到輸出O 的概率相差較小時,可以認為這個算法能達到差分隱私的效果,這樣觀察者僅僅通過觀察數據處理結果,很難找出具體某條數據的變化,從而保護數據集的隱私問題。

從兩個數據集的拉普拉斯隨機分布圖看,在lamda為0.5,數據集A 值為-5,5,數據集B 為-4,5 的情況下,兩個laplace 分布呈現如圖1 所示的結果,保護隱私的目的需要使兩個分布盡可能接近。

圖1 數據集的Laplace 分布

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

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

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

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

圖2 差分隱私算法應對的攻擊模式

3 算法設計

4 可用性實驗

為了驗證新的Map-Reduce 模型進行保護差分隱私的有效性,選擇“Blood”和“Gramma”數據庫來進行驗證,關注的兩個標準是召回率和精確率。 F-measure可以整合召回率和精確率,用F-measure 來證明集群可用性。 F-measure 越大,兩個聚類結果的相似性越強,添加噪聲的算法對聚類的影響很小[8]。 將f 方法和標準數據集之間的相似性寫為 F1,去對比方法和作為F2之間的相似性[9]。 運行過程中,增加的噪聲服從拉普拉斯隨機分布,結果具有隨機性。

5 結語

本文利用基于MapReduce 的K-means 方法來實現差分隱私保護,在MapReduce 的框架下,并行計算聚類,最終利用Laplace 的機制實現差分隱私保護,同時提高了這個算法的效率和隱私性。