[發(fā)明專利]一種基于MapReduce的差分隱私K均值聚類方法

有效

• 申請?zhí)枺?/td>: 201710546207.2
• 申請日: 2017-07-06
• 公開（公告）號: CN107423636B
• 公開（公告）日: 2021-05-04
• 發(fā)明（設(shè)計(jì)）人: 尚濤;趙錚;楊英;馬旭;關(guān)振宇;劉建偉
• 申請（專利權(quán)）人: 北京航空航天大學(xué)
• 主分類號: G06F21/62
• 分類號: G06F21/62;G06K9/62;G06F16/2458
• 代理公司: 北京慧泉知識產(chǎn)權(quán)代理有限公司 11232
• 代理人: 王順榮;唐愛華

1.一種基于MapReduce的差分隱私K均值聚類方法，其特征在于：該方法包含以下步驟：

步驟1：對數(shù)據(jù)進(jìn)行歸一化處理；數(shù)據(jù)集D中記錄數(shù)為N條，分別記為x_i,1≤i≤N；每條數(shù)據(jù)維數(shù)為d，即數(shù)據(jù)集D中某一數(shù)據(jù)值x_i＝(x_i1,x_i2,...,x_id)^T是d維屬性，T表示行列式的轉(zhuǎn)置運(yùn)算；讀取數(shù)據(jù)集D的每條記錄x_i，設(shè)置第一條記錄x₁的每維屬性為其所在維的初始最大值max和初始最小值min，將剩余記錄的各維屬性分別與max和min比較大小，得到每維屬性的最大值Max和最小值Min，通過歸一化公式將x_i的各維屬性歸一化處理至空間[0,1]^d中，形成新數(shù)據(jù)集D'；

根據(jù)MapReduce框架，將數(shù)據(jù)處理任務(wù)分為兩部分：Map階段和Reduce階段，其中分別定義了Mapper類、Reducer類；

從步驟2到步驟4，用于在MapReduce中實(shí)現(xiàn)優(yōu)化的Canopy算法，確定初始中心點(diǎn)；

步驟2：確定優(yōu)化Canopy算法中每個Map任務(wù)中的局部中心點(diǎn)；主任務(wù)Driver調(diào)用MapReduce中的Mapper類，map函數(shù)中設(shè)置集合Q為空，設(shè)置迭代次數(shù)L為map函數(shù)中的局部數(shù)據(jù)集大小；在不超過迭代次數(shù)的前提下，若集合Q為空，求數(shù)據(jù)集D'中數(shù)據(jù)點(diǎn)x_i與坐標(biāo)原點(diǎn)距離的最小值min，將該數(shù)據(jù)點(diǎn)x_i保存至集合Q，若集合Q不為空，計(jì)算數(shù)據(jù)集D'中每個數(shù)據(jù)點(diǎn)與集合Q中每個數(shù)據(jù)點(diǎn)的距離得出數(shù)據(jù)集D'中任意一個數(shù)據(jù)點(diǎn)與集合Q中每個數(shù)據(jù)點(diǎn)的最小距離，從所述最小距離中獲取最大者Dist_min，保存至集合Q中；

設(shè)已知前m個中心點(diǎn)，那么第m+1個中心點(diǎn)應(yīng)是待選取數(shù)據(jù)點(diǎn)中與前m個中心點(diǎn)之間最小距離中最大者，公式如下：

L表示當(dāng)前任務(wù)中數(shù)據(jù)集的數(shù)據(jù)總量，DisCollect(m+1)表示待確定的第m+1個中心點(diǎn)與前m個中心點(diǎn)間距中的最小值，Dist_min(m+1)表示第m+1個中心點(diǎn)應(yīng)是最小距離中的最大值；這樣就避免了區(qū)域半徑T₂的設(shè)置；

首先，使用距離坐標(biāo)原點(diǎn)最近、最遠(yuǎn)的數(shù)據(jù)點(diǎn)代替數(shù)據(jù)集中初始距離最遠(yuǎn)的數(shù)據(jù)；其次，先求取局部Canopy中心點(diǎn)，以此為基礎(chǔ)求取全局中心點(diǎn)；最后，生成局部Canopy中心點(diǎn)時(shí)，為降低迭代次數(shù)，選擇迭代次數(shù)為此處L為局部數(shù)據(jù)集大小，

步驟3：采用局部中心點(diǎn)確定聚類個數(shù)K值，確定Canopy的區(qū)域半徑T₁；主任務(wù)Driver調(diào)用MapReduce中的Reducer類，reduce函數(shù)接收集合Q＝{Q₁,...Q_n}，n為大于1的正整數(shù)；首先計(jì)算P＝Count(Q)，P為集合Q的數(shù)據(jù)總量，設(shè)置循環(huán)次數(shù)為在不超過循環(huán)次數(shù)的前提下，循環(huán)計(jì)算集合Q中數(shù)據(jù)點(diǎn)之間距離最小值中最大者Dist2_min，并將Dist2_min對應(yīng)的集合Q中數(shù)據(jù)點(diǎn)保存至集合Q'，計(jì)算集合Q'的數(shù)據(jù)總量K，設(shè)置循環(huán)次數(shù)為K；在不超過循環(huán)次數(shù)K的前提下，計(jì)算得到集合Q'中Depth(i)的最大值并輸出區(qū)域半徑T₁＝Dist2_min，將集合中前i個點(diǎn)賦值至空集合U中；

當(dāng)Canopy個數(shù)低于或者超過類別數(shù)時(shí)，Dist_min的變化幅度小；當(dāng)Canopy個數(shù)接近或達(dá)到類別數(shù)時(shí)，該Dist_min值變化大；為了確定Canopy個數(shù)和區(qū)域半徑T₁，引入指標(biāo)Depth(i)表示Dist2_min變化幅度，公式如下：

Depth(i)＝|Dist2_min(i)-Dist2_min(i-1)|+|Dist2_min(i+1)-Dist2_min(i)|

當(dāng)i達(dá)到一定值時(shí)，Depth(i)取得最大值，此時(shí)設(shè)區(qū)域半徑T₁＝Dist2_min；

步驟4：將步驟3輸出的Canopy初始中心點(diǎn)集合U，以文件形式保存，再次調(diào)用Mapper類map函數(shù)計(jì)算各節(jié)點(diǎn)數(shù)據(jù)與中心點(diǎn)之間的歐氏距離D；當(dāng)D≤T₁，則將該數(shù)據(jù)點(diǎn)x_i歸于對應(yīng)的Canopy，得到K個Canopy并將結(jié)果輸出；

計(jì)算數(shù)據(jù)樣本x_j和聚類中心c_i兩者間的歐氏距離，定義如下：

d(x_j，c_i)＝||x_j-c_i||₂

其中

表示第i個聚類的中心點(diǎn)位置，i＝1,2,...,K，n_i是第i個聚類C_i中的數(shù)據(jù)點(diǎn)數(shù)目，x_j是第i個聚類中的數(shù)據(jù)點(diǎn)；

關(guān)于初始中心點(diǎn)的選擇問題，由于隨機(jī)性中心點(diǎn)對聚類的最后結(jié)果的影響大，上述步驟中輸出了K個Canopy，按照差分隱私K均值聚類方法得到加噪后的中心點(diǎn)，將其作為初始聚類中心點(diǎn)；即對于每個Canopy計(jì)算其數(shù)據(jù)點(diǎn)之和sum＝Sum(Canopy)與集合內(nèi)的數(shù)據(jù)點(diǎn)數(shù)目之和num＝Count(Canopy)，對sum和num添加隨機(jī)噪聲X然后兩者相除，將得到的數(shù)據(jù)點(diǎn)作為新的聚類中心隨機(jī)噪聲X為Laplace噪聲，即該噪聲服從Laplace分布Lap(b),b＝Δf/ε，Δf為全局敏感度，ε為隱私保護(hù)預(yù)算；

步驟5：設(shè)置添加的隨機(jī)噪聲；隨機(jī)噪聲為Laplace噪聲，即該噪聲服從Laplace分布Lap(b),b＝Δf/ε，Δf為全局敏感度，ε為隱私保護(hù)預(yù)算；設(shè)置添加噪聲的隱私保護(hù)預(yù)算參數(shù)ε；若聚類執(zhí)行時(shí)迭代執(zhí)行總m未知，那么在聚類迭代執(zhí)行時(shí)不斷變換隱私預(yù)算參數(shù)ε的值，采用的為首次迭代使用預(yù)算值是ε/2，后續(xù)的迭代中每輪使用的隱私預(yù)算是剩余值的1/2，即ε_m＝ε/2^m；設(shè)置添加噪聲的全局敏感度參數(shù)Δf，Δf＝d+1，d為數(shù)據(jù)維數(shù)；

定義：設(shè)有函數(shù)f：D→R^d，輸入是數(shù)據(jù)集D，輸出是d維實(shí)數(shù)向量，對于任意兩個鄰近數(shù)據(jù)集D₁和D₂：

則稱Δf為函數(shù)的全局敏感度；

對于兩個鄰近數(shù)據(jù)集D₁和D₂，兩個數(shù)據(jù)集的屬性均為d維，基于步驟4)中數(shù)據(jù)點(diǎn)數(shù)目之和num在兩個數(shù)據(jù)集中最多只有一條記錄之差，對于計(jì)數(shù)查詢而言，num的敏感度值為Δf_num＝1；對于的數(shù)據(jù)點(diǎn)之和sum，為便于求和查詢函數(shù)的分析，將兩個數(shù)據(jù)集D₁和D₂的d維屬性分別進(jìn)行歸一化處理，歸一化到[0,1]^d，則差分隱私K均值聚類方法獲取中心點(diǎn)的計(jì)算就相當(dāng)于直方圖查詢時(shí)在區(qū)間[0,1]^d中進(jìn)行了劃分，對于sum來說，當(dāng)數(shù)據(jù)集D₁和D₂只有至多有一條記錄不同時(shí)，計(jì)算數(shù)據(jù)點(diǎn)之和每個屬性值變化最大為1，由公式可知該求和查詢sum的全局敏感度為Δf_sum＝d，所以整體Δf＝d+1；

步驟6：主任務(wù)Driver讀取步驟4輸出的K個Canopy，對于每個Canopy計(jì)算其數(shù)據(jù)點(diǎn)之和sum＝Sum(Canopy)

與集合內(nèi)的數(shù)據(jù)點(diǎn)數(shù)目之和num＝Count(Canopy)，

對sum和num添加隨機(jī)噪聲X然后兩者相除，將得到的數(shù)據(jù)點(diǎn)作為新的聚類中心

Map階段負(fù)責(zé)的任務(wù)有：(1)map函數(shù)開始時(shí)會讀入上輪迭代或者初始的聚類中心點(diǎn)；(2)每一個Map任務(wù)對于接收到的數(shù)據(jù)塊，分別執(zhí)行數(shù)據(jù)點(diǎn)與聚類中心點(diǎn)距離的計(jì)算操作，并把該數(shù)據(jù)點(diǎn)歸至最小距離的聚類；(3)輸出鍵值對(key,value)，key為數(shù)據(jù)所在的聚類標(biāo)號，value為數(shù)據(jù)的各維屬性向量值；之后對得到的鍵值對執(zhí)行歸并操作，將帶有同樣key值的鍵值對進(jìn)行(key,value)歸并統(tǒng)計(jì)每個聚類下的數(shù)據(jù)點(diǎn)數(shù)目，此時(shí)key仍代表聚類標(biāo)號，value1則代表數(shù)據(jù)的各維屬性值和聚類中的數(shù)據(jù)數(shù)目，將新的鍵值對(key,value1)輸出；

Reduce階段負(fù)責(zé)的任務(wù)有：接收鍵值對(key,value1)，計(jì)算同一聚類下的數(shù)據(jù)點(diǎn)各維屬性之和sum，根據(jù)數(shù)據(jù)點(diǎn)之和sum和數(shù)據(jù)點(diǎn)數(shù)目之和num計(jì)算新的聚類中心點(diǎn)；之后由主任務(wù)決定是否符合迭代結(jié)束條件；

從步驟7到步驟9，用于在MapReduce中實(shí)現(xiàn)差分隱私K均值算法得到最終結(jié)果；

步驟7：主任務(wù)Driver調(diào)用MapReduce中的Mapper類，map函數(shù)首先讀取文件中的聚類中心點(diǎn)其中m為迭代次數(shù)，讀入到事先定義的集合R中，然后map函數(shù)讀取分任務(wù)中接收到的不同記錄x_i；分別得出每條記錄與聚類中心點(diǎn)的距離值Distance，得到與其距離值最小的聚類中心點(diǎn)c_k，將其劃分到此聚類，每個map函數(shù)輸出的應(yīng)是鍵值對(key,value)，其中key為數(shù)據(jù)記錄所在的聚類標(biāo)號，value為數(shù)據(jù)記錄的各維屬性值和聚類當(dāng)前數(shù)據(jù)記錄的數(shù)目，此時(shí)數(shù)目都為1；

步驟8：主任務(wù)Driver調(diào)用MapReduce中的Reducer類，Reduce分任務(wù)接收鍵值對(key，value)后，合并屬于同一個聚類標(biāo)號即同一個key值的聚類，reduce函數(shù)統(tǒng)計(jì)同一個類中數(shù)據(jù)數(shù)目總和num_k和每條數(shù)據(jù)記錄的各維屬性值總和sum_k，將兩者添加隨機(jī)噪聲得到num_k'和sum_k'，兩者相除獲取到新的聚類中心，并把該新的聚類中心的集合輸出；

步驟9：主任務(wù)Driver讀取接收步驟8最新生成的聚類中心集合和步驟7的K個聚類中心集合，得到這兩輪聚類中心點(diǎn)集合間的歐式距離Dis，若這兩輪中中心點(diǎn)集合的各維屬性之差的距離Dis小于指定閾值Threshold或者循環(huán)次數(shù)已經(jīng)到達(dá)迭代總數(shù)值M，則算法迭代終止，主任務(wù)Driver調(diào)用MapReduce中的Mapper類按照最新生成的聚類中心點(diǎn)集合C將數(shù)據(jù)集D'進(jìn)行實(shí)現(xiàn)聚類操作，輸出聚類后的結(jié)果；若不滿足要求，繼續(xù)重復(fù)步驟7～步驟9；

設(shè)有n個數(shù)據(jù)樣本X＝{x₁,x₂,…,x_n}為待處理數(shù)據(jù)集，其中x_j＝(x_j1,x_j2,…,x_jd)^T是d維向量，該算法目標(biāo)是得到總數(shù)為K的聚類中心點(diǎn)集合C＝{c₁,c₂,…,c_K}^T，再將數(shù)據(jù)集進(jìn)行劃分，判斷迭代是否重復(fù)的條件之一就是通過誤差平方和函數(shù)：

公式中S_i代表第i個聚類中數(shù)據(jù)樣本的集合，c_i是第i個聚類的中心點(diǎn)，d(x_j,c_i)代表計(jì)算數(shù)據(jù)樣本x_j和聚類中心c_i兩者間的歐氏距離，定義如下：

d(x_j，c_i)＝||x_j-c_i||₂

其中

表示第i個聚類的中心點(diǎn)位置，i＝1,2,…,K，n_i是第i個聚類中的數(shù)據(jù)點(diǎn)數(shù)目，x_j是第i個聚類中的數(shù)據(jù)點(diǎn)；

MapReduce并行框架下實(shí)施聚類過程時(shí)通過在每步reduce函數(shù)操作中添加服從Laplace分布的隨機(jī)噪聲來滿足保護(hù)隱私信息的需求；該聚類過程中的每次迭代與多個隨機(jī)算法的序列組合相似，根據(jù)差分隱私的組合性質(zhì)可知，設(shè)共有M次迭代，則該算法總共的ε值應(yīng)為：

其中ε_m代表第m次迭代消耗的隱私預(yù)算，預(yù)算分配方面，已確定的ε_m＝ε/2^m；

聚類中每次進(jìn)行迭代操作時(shí)，各個Reduce分任務(wù)之間是并行地處理，每輸出的結(jié)果與隨機(jī)算法的并行組合相似，根據(jù)并行組合性質(zhì)，則每次迭代中Reduce分任務(wù)執(zhí)行操作是使用的隱私預(yù)算均是ε_m。