[發(fā)明專利]一種基于四叉樹自適應劃分技術的二維空間數(shù)據(jù)差分隱私發(fā)布方法

在審

• 申請?zhí)枺?/td>: 202011013025.7
• 申請日: 2020-09-24
• 公開（公告）號: CN112131603A
• 公開（公告）日: 2020-12-25
• 發(fā)明（設計）人: 金媛媛;劉勝軍;謝飛;倪志偉;卜凡耀;陳千;朱旭輝;周芳;倪麗萍
• 申請（專利權）人: 合肥城市云數(shù)據(jù)中心股份有限公司;合肥工業(yè)大學
• 主分類號: G06F21/62
• 分類號: G06F21/62;G06K9/62
• 代理公司: 合肥國和專利代理事務所(普通合伙) 34131
• 代理人: 張祥騫

1.一種基于四叉樹自適應劃分技術的二維空間數(shù)據(jù)差分隱私發(fā)布方法，其特征在于，包括以下步驟：

11)二維空間數(shù)據(jù)的獲取，獲取待進行隱私發(fā)布的二維空間數(shù)據(jù)；

12)網格區(qū)域的劃分：對二維空間數(shù)據(jù)進行聚類，將二維空間數(shù)據(jù)根據(jù)密度聚類形成自適應網格，將數(shù)據(jù)空間劃分為不同密度的區(qū)域；

13)自適應網格區(qū)域的劃分處理：對自適應網格區(qū)域中數(shù)據(jù)分布最為稀疏的區(qū)域計數(shù)根據(jù)隱私預算直接添加噪音；對剩余密度區(qū)域作為密集區(qū)域采用四叉樹分割數(shù)據(jù)空間，將粗粒度區(qū)域進一步劃分為均勻細粒度區(qū)塊，以降低區(qū)域內的均勻假設誤差；

14)對四叉樹進行后置處理：對于縱向結構，采用重構算法自底向上改進四叉樹，有效減小均勻假設誤差；對于橫向結構，結合抽樣排序和貪心算法，將四叉樹劃分結果分層合并，有效減小長范圍區(qū)間查詢的誤差累計；

15)二維空間數(shù)據(jù)差分隱私的發(fā)布：對密集區(qū)域添加噪音分配隱私預算：將四叉樹與個性化分配隱私預算相結合，根據(jù)需求個性化調整相鄰兩層分配的隱私預算；對四叉樹分層添加噪音后融合已添加噪聲的稀疏區(qū)域后對外發(fā)布數(shù)據(jù)。

2.根據(jù)權利要求1所述的一種基于四叉樹自適應劃分技術的二維空間數(shù)據(jù)差分隱私發(fā)布方法的二維空間數(shù)據(jù)差分隱私發(fā)布方法，其特征在于，所述網格區(qū)域的劃分包括以下步驟：

21)根據(jù)待發(fā)布的二維數(shù)據(jù)集合L，創(chuàng)建兩個集合：一個只包含所有橫坐標位置記為L_x，另一個只包含所有縱坐標位置記為L_Y；

22)定義橫坐標和縱坐標的區(qū)間長度Δx和Δy，分別根據(jù)L_x、L_Y計算區(qū)間的密度，對區(qū)間進行密度判定，密度相似的臨近區(qū)間進行聚類，形成橫坐標和縱坐標的稠密區(qū)間和稀疏區(qū)間；

23)根據(jù)區(qū)間劃分結果，對二維數(shù)據(jù)集合L進行密度自適應網格劃分，得到粗粒度區(qū)塊，得到不同密度的區(qū)域。

3.根據(jù)權利要求1所述的一種基于四叉樹自適應劃分技術的二維空間數(shù)據(jù)差分隱私發(fā)布方法的二維空間數(shù)據(jù)差分隱私發(fā)布方法，其特征在于，所述自適應網格區(qū)域劃分處理包括以下步驟：

31)對于位于稀疏區(qū)域的第一層區(qū)塊，不再劃分，直接對其原始計數(shù)結果添加隱私預算為ε的Laplace噪聲；

32)已經進行網格劃分的數(shù)據(jù)集，根據(jù)第一層網格的劃分結果，對于橫軸和縱軸都處于密集區(qū)域的區(qū)塊，將區(qū)塊定義為一個根節(jié)點，進行四叉樹劃分；

33)對密集區(qū)塊的數(shù)據(jù)進行初始化分割，建立完整的滿四叉樹，將所有的二維數(shù)據(jù)存儲于相應四叉樹節(jié)點中。

4.根據(jù)權利要求1所述的一種基于四叉樹自適應劃分技術的二維空間數(shù)據(jù)差分隱私發(fā)布方法的二維空間數(shù)據(jù)差分隱私發(fā)布方法，其特征在于，所述對四叉樹進行后置處理包括以下步驟：

41)自底向上的對處于同一父節(jié)點下的葉子節(jié)點的計數(shù)值求均值，使用(1)式計算四叉樹向上重構后這部分區(qū)域加噪后的誤差Err；

其中，Y是規(guī)定的隱私預算下的平均噪音，num_i是四個葉子節(jié)點的真實計數(shù)值，i是同一父節(jié)點下四個葉子節(jié)點的編號；

42)通過比較Err與原始節(jié)點計數(shù)直接加噪后的誤差大小，來啟發(fā)式地判斷父節(jié)點區(qū)域是否均勻，如果直接加噪的節(jié)點誤差比重構后節(jié)點的誤差大，則將節(jié)點向上縮減重構來減小誤差；

43)分別對四叉樹各層節(jié)點進行抽樣排序，抽樣排序所需隱私預算為ε₁；

44)排序后，采用指數(shù)機制每次以正比于的概率選擇某層節(jié)點中最相似的兩個鄰近節(jié)點進行合并，

其中，ε₂為合并相似節(jié)點所設置的隱私預算，ε₃為第i層節(jié)點添加拉普拉斯噪音的隱私預算，G_s為誤差最小的n個可行合并方案集合；

45)采用貪心的思想對其進行合并加噪，利用(2)式計算總誤差Error，直到總誤差達到最小，

Error＝RE+NE，(2)

其中，RE為合并誤差，NE為噪音誤差。

5.據(jù)權利要求1所述的一種基于四叉樹自適應劃分技術的二維空間數(shù)據(jù)差分隱私發(fā)布方法的二維空間數(shù)據(jù)差分隱私發(fā)布方法，其特征在于，所述對密集區(qū)域添加噪音分配隱私預算包括以下步驟：

51)獲取四叉樹的深度h，定義相鄰兩層分配的隱私預算比值q(q1)，根據(jù)總添加拉普拉斯噪音隱私預算ε₃以及q_i，給四叉樹的第i層分配不同的隱私預算其中各層隱私預算滿足條件

52)按照所分配的隱私預算對四叉樹各層節(jié)點計數(shù)添加拉普拉斯噪音發(fā)布四叉樹各層區(qū)域的噪音計數(shù)。