[發明專利]一種基于直方圖的面向數據流差分隱私發布方法

有效

• 申請號: 201510430312.0
• 申請日: 2015-07-21
• 公開（公告）號: CN105046160B
• 公開（公告）日: 2018-08-03
• 發明（設計）人: 夏小玲;劉慧藝;石秀金;王紹宇;于守健
• 申請（專利權）人: 東華大學
• 主分類號: G06F21/60
• 分類號: G06F21/60
• 代理公司: 上海泰能知識產權代理事務所 31233
• 代理人: 宋纓;孫健

本發明涉及一種基于直方圖的面向數據流差分隱私發布方法，包括以下步驟：對于每一個時刻i，數據流接收的數據集為D_i，對數據集D_i中屬性A出現的不同元素值進行統計，并按照元素值的大小升序排列，對頻數進行歸一化處理為P；記最后一次發布的含噪局部最優直方圖所對應的真實數據的分布歸一化后為Q，計算P與Q的EMD相似度τ；若τ＞σ，則給數據集D_i分配隱私預算其中，并給數據集D_i添加相應的拉普拉斯噪聲得到數據集O_i；對數據集O_i利用分組與合并策略，進行局部最優直方圖發布。本發明在保證每個窗口中隱私總預算不超過ε時，發布數據的可用性較好。

技術領域

本發明涉及差分隱私發布技術領域，特別是涉及一種基于直方圖的面向數據流差分隱私發布方法。

背景技術

由于信息化技術的快速發展，用戶的隱私信息泄露的問題逐漸凸顯，隱私保護技術也引起人們的關注。差分隱私是一種強隱私保護模型，該模型假定攻擊者具有除某一條記錄以外的其他所有記錄信息，即使在這一最大化背景知識下，差分隱私仍然能保證這條記錄的隱私信息不被泄露。

目前關于數據流的差分隱私發布技術主要針對的是{0,1}所組成的二進制流，這些方法不足以應用于真實的應用程序中，真實的應用程序是基于窗口的，并且數據流也不會僅僅局限于二進制流，而應是任意數值型數據流。由于每個窗口中的隱私預算是固定的，若考慮給每個子窗口分配相同的隱私預算，當窗口的大小增大時，每個子窗口分配的隱私預算會減小，使得添加的噪聲增大，導致數據的可用性降低。面向更一般的數據流，如何在保證每個窗口中的隱私總預算不超過ε時，合理的分配隱私預算，并且能有效的快速發布直方圖統計信息，同時保證數據具有一定的可用性，成為一項急需解決的任務。

發明內容

本發明所要解決的技術問題是提供一種基于直方圖的面向數據流差分隱私發布方法，以達到每個窗口中隱私總預算不超過ε時，發布數據的可用性較好。

本發明解決其技術問題所采用的技術方案是：提供一種基于直方圖的面向數據流差分隱私發布方法，包括以下步驟：

(1)對于每一個時刻i，數據流接收的數據集為D_i，對數據集D_i中屬性A出現的不同元素值進行統計，并按照元素值的大小升序排列，對頻數進行歸一化處理為P；

(2)記最后一次發布的含噪局部最優直方圖所對應的真實數據的分布歸一化后為Q，計算P與Q的EMD(Earth Mover’s Distance)相似度τ；

(3)若τ＞σ，則給數據集D_i分配隱私預算其中，并給數據集D_i添加相應的拉普拉斯噪聲得到數據集O_i，其中，σ為設定的閾值，ε為隱私總預算，w為滑動窗口大小，ε_j為第j個子窗口已分配的預算大小；

(4)對數據集O_i利用分組與合并策略，進行局部最優直方圖發布。

所述步驟(3)中若τ≤σ時，則不發布數據集D_i,即數據集O_i＝null。

所述步驟(3)中數據集O_i＝D_i+＜Lap(λ_i)＞^m，其中，＜Lap()＞為拉普拉斯噪聲、m的大小為數據集D_i中屬性A出現的不同元素值的個數。

所述步驟(3)中若在一個窗口內，數據集連續突變，為了減緩λ_i遞增速度，需減緩ε_i的分配，則給數據集D_i分配隱私預算

所述步驟(4)中局部最優直方圖發布包括以下子步驟：