[發明專利]優先兼顧小桶可用性的差分隱私直方圖發布方法及系統

有效

• 申請號: 202110345856.2
• 申請日: 2021-03-31
• 公開（公告）號: CN113434897B
• 公開（公告）日: 2022-07-05
• 發明（設計）人: 徐正全;陳友勤;毛立暉
• 申請（專利權）人: 武漢大學
• 主分類號: G06F21/62
• 分類號: G06F21/62;G06F16/2458;G06F16/906
• 代理公司: 武漢科皓知識產權代理事務所(特殊普通合伙) 42222
• 代理人: 嚴彥

1.一種優先兼顧小桶可用性的差分隱私直方圖發布方法，其特征在于：包括以下步驟，

步驟A，初步擾動，包括將一部分隱私預算ε₁結合拉普拉斯差分隱私機制對原始直方圖進行初步擾動，得到初步擾動后的中間直方圖；

步驟B，閾值函數處理，包括根據隱私預算ε₁設置閾值，對初步擾動后的中間直方圖進行閾值處理，當中間直方圖中的桶的值小于閾值時，則變更為0，反之，保持不變；

步驟C，排序，包括對步驟B更新后的中間直方圖實施排序，得到從小到大排序的直方圖；

步驟D，分組聚類，包括利用剩余的隱私預算ε₂＝ε-ε₁，對已按從小到大排序的直方圖進行按序分組，得到分組集合，ε是總隱私預算；實現過程包括以下子步驟，

步驟D1，初始化分組集合為空集，當前最優分組包括第一個桶，待分組起始桶標識為1；

步驟D2，若已經對所有桶分組完畢，直接進入步驟D3，當還有待分的桶時，進行以下子步驟：

步驟D2-1，根據待分組起始桶標識初始化當前分組，并記為當前分組的最優分組；

步驟D2-2，遍歷當前分組和待分組起始桶之后的桶構成的各種連續區域組合，尋找一個誤差最小的組合，然后進入步驟D2-3；

步驟D2-3，更新已分組的集合和待分組桶的起始標識，接著下一個分組是從待分組桶的起始標識開始，重新回到步驟D2進行分組，直到所有的桶均已分組完畢；

步驟D3，返回分組集合；

步驟E，發布，包括對分組集合中的每個分組計算一個均值，然后對每個桶采用所屬分組的均值進行近似表示，接著結合剩余的隱私預算以拉普拉斯機制生成噪聲樣本值后與所屬分組包含桶的個數之間的比值作為最終噪聲的大小，得到實施擾動后的擾動直方圖，并用于發布。

2.如權利要求1所述的一種優先兼顧小桶可用性的差分隱私直方圖發布方法，其特征在于：步驟A的實現包括以下子步驟，

步驟A1，計算一部分隱私預算ε₁＝rate×ε,0＜rate＜1，其中，rate是隱私預算分配占比，ε是總隱私預算；

步驟A2，對原始直方圖H＝{H₁,H₂,…,H_n}實現初步差分隱私擾動，得到中間直方圖其中而Lap(1/ε₁)是一個以1/ε₁為尺度的拉普拉斯噪聲，其分布為：

其中，H₁,H₂,…,H_n是直方圖中的桶，n是桶數量，x是噪聲變量，λ是尺度參數。

3.如權利要求2所述的一種優先兼顧小桶可用性的差分隱私直方圖發布方法，其特征在于：步驟B中所述的閾值函數Threshold如下：

其中，θ＝ηlog(n)/ε₁，η＞0是一個調節參數，n為直方圖中桶的個數，桶標號i＝1,2,…n。

4.如權利要求3所述的一種優先兼顧小桶可用性的差分隱私直方圖發布方法，其特征在于：所述利用從小到大的排序算法Ascending_Sort實施排序的實現方式如下，

對于原始直方圖是無序的情況下，采取常見的從小到大的排序方式進行實現；針對已是有序的原始直方圖，則采取保序規則進行排序處理，以降低步驟A所進行的初步擾動而引起的排序誤差，進而進一步影響之后的分組聚類和發布。

5.如權利要求4所述的一種優先兼顧小桶可用性的差分隱私直方圖發布方法，其特征在于：步驟D2-2尋找一個誤差最小的組合時，

當前最小平均相對誤差為min＝E[err(C_i)]，其中分組C_i平均相對誤差即分組C_i相對誤差的期望；其含義是分組C_i中所包含的桶的平均值，|C_i|代表分組C_i中桶的個數。