[發明專利]一種MapReduce框架下基于差分隱私的匿名協同方法

在審

• 申請號: 201711210206.7
• 申請日: 2017-11-28
• 公開（公告）號: CN107862220A
• 公開（公告）日: 2018-03-30
• 發明（設計）人: 許國艷;宋健;朱帥;李敏佳;張網娟
• 申請（專利權）人: 河海大學
• 主分類號: G06F21/62
• 分類號: G06F21/62
• 代理公司: 南京蘇高專利商標事務所(普通合伙)32204
• 代理人: 柏尚春

1.一種MapReduce框架下基于差分隱私的匿名協同方法，其特征在于，該方法包括以下步驟：

(1)啟動輸入，復制數據集至HDFS，歸一化數據；

(2)對預處理完的所述數據集進行切片處理；

(3)在分布式計算結點上執行Map分任務，首先計算屬性到對應中心點的距離，然后判斷記錄所屬等價類類別；

(4)在分布式計算結點上執行Reduce分任務，首先添加Laplace噪聲，然后計算等價類質心匿名，使得最終的結果滿足ε-差分隱私保護；

(5)更新質心文件，輸出結果，所述結果收斂則結束，否則返回(3)和(4)。

2.根據權利要求1所述的MapReduce框架下基于差分隱私的匿名協同方法，其特征在于，步驟(2)中，所述將所述數據集切片具體包括：

對于P維數據集T＝{x₁,x₂,x₃,…,x_n}，其中，n表示所述數據集T包含的記錄數；確定k-劃分的參數k值，將所述數據集T分為m個數據片，將每個所述數據片設為D_j(1≤j≤m)，得到M_j←{x₁,...x_i...,x_m}，其中，x為所述數據集T中的數據，M_j為j個切片下的作用數據集。

3.根據權利要求1所述的MapReduce框架下基于差分隱私的匿名協同方法，其特征在于，步驟(3)中，所述執行Map分任務具體包括：

(31)計算每一個記錄到該記錄相應的質心距離，測度公式為其中，y_ij是所述數據集T的第i個屬性的第j個記錄，是所述數據集T的第i個屬性的質心值，p表示所述數據集T包含的屬性個數；

(32)輸出置空；

(33)對所述數據集切片記錄使用均值排序方法進行排序；根據k值大小，找出排好序集合中的第一條和最后一條記錄f、l，找到離f最近的k-1條記錄組成等價類S₁，找到離l最近的k-1條記錄組成等價類S₂，記作S＝S∪{S₁,S₂}&&M_i＝M_i-S₁-S₂，遞歸時先將S設置為空集，其中，M_i為i個切片下的作用數據集；

(34)記錄所映射的鍵值對<key,value>，其中，key為所述數據集切片記錄隸屬等價類中心標識，value為所述數據集切片記錄屬性向量。

4.根據權利要求1所述的MapReduce框架下基于差分隱私的匿名協同方法，其特征在于，步驟(4)中，所述執行Reduce分任務具體包括：

(41)接收所述Map分任務階段的鍵值對<key,value>，并將所述鍵值對添加Laplace噪聲，并分派任務；

(42)計算所述等價類中記錄的數目num以及每個所述記錄屬性向量之和sum，同時進行Laplace加躁處理得到匿名記錄的數目num'和匿名記錄屬性向量之和sum'；

(43)計算匿名質心向量x'＝sum'/num'，用所述匿名質心代替其他值，返回匿名數據集；

(44)輸出<key,value>。

5.根據權利要求1或者3所述的MapReduce框架下基于差分隱私的匿名協同方法，其特征在于，步驟(5)中，所述最終的結果滿足ε-差分隱私保護的條件為第i次遞歸過程中加入的隨機噪聲為Lap(P+1)(2ⁱ⁺¹/ε)，其中，ε為隱私保護預算，P為所述數據集的維度。