[發明專利]基于小波變換的差分隱私數據發布方法

有效

• 申請號: 201510041710.3
• 申請日: 2015-01-27
• 公開（公告）號: CN104573560B
• 公開（公告）日: 2018-06-19
• 發明（設計）人: 管海兵;姚建國;馬汝輝;李健;鄧煜
• 申請（專利權）人: 上海交通大學
• 主分類號: G06F21/62
• 分類號: G06F21/62
• 代理公司: 上海新天專利代理有限公司 31213
• 代理人: 張寧展

本發明公開了一種基于小波變換的差分隱私數據發布方法。通過把原始數據集的屬性取值概括為預定義概括樹結構中最頂層的取值，再利用概括樹結構自頂向下的細分取值，一步一步把概括化的屬性值轉化為細分的屬性值。在選擇屬性進行細分的選擇算法上，利用已有的指數加噪方法；在葉子節點的加噪中引入了小波變換的加噪方法，使得在滿足差分隱私保護的前提下，盡量減少新發布數據集相對原始數據集的噪音。本發明結合小波變換和指數機制協同加噪，有效的減少了在對原始數據集加噪過程中噪音的累積，并且符合差分隱私保護的定義，減少了隱私保護的代價，有效提高了差分隱私保護后數據集的利用率。

技術領域

本發明涉及計算機數據挖掘、數據隱私保護技術領域，具體地，涉及一種基于小波變化的差分隱私數據發布方法，用于解決差分隱私數據發布過程中噪音量過大的問題。

背景技術

信息技術的飛速發展使得各類數據的發布、采集、存儲和分析變得方便快捷.例如，醫院電子病例記錄病人基本信息、疾病信息及藥品購買記錄；人口普查記錄市民的家庭住址以及收入情況；金融業務服務會記錄客戶私有信息及其交易行為等，而這些數據的收集和發布直接給個人隱私造成威脅。

隱私保護技術可以解決數據發布和數據分析帶來的隱私威脅問題，如何發布和分析而又不泄露隱私信息是隱私保護技術的主要目的。已有的基于k匿名或者劃分的隱私保護方法，只適應特定背景知識下的攻擊而存在嚴重的局限性。差分隱私作為一種新出現的隱私保護框架，能夠防止攻擊者擁有任意背景知識下的攻擊并提供有力的保護。該模型不關心攻擊者擁有多少背景知識，通過向查詢或者分析結果中添加適當噪音來達到隱私保護效果，類似傳統的隱私保護技術，實施差分隱私保護技術主要考慮兩個方面的問題：(1)如何保證設計的算法滿足差分隱私，以確保數據隱私不被泄露；(2)如何減少噪音帶來的誤差，以提高數據的可用性。

差分隱私的形式化定義如下：

定義1：給定數據集D和D'，二者互相之間至多相差一條記錄，即|DΔD'|≤1.給定一個隱私算法A，Range(A)為A的取值范圍，若算法A在數據集D和D'上任意輸出結果O(O∈Range(A))滿足下列不等式，則A滿足ε差分隱私：

其中，概率Pr[·]由算法A的隨機性控制，也表示隱私被披露的風險；隱私預算參數ε表示隱私保護程度，ε越小隱私保護程度越高。從定義1可以看出差分隱 私技術限制了任意一條記錄對算法A輸出結果的影響.該定義是從理論角度確保算法A滿足ε差分隱私，而要實現差分隱私保護需要噪音機制的介入。

噪音機制是實現差分隱私保護的主要技術，常用的噪音添加機制分別為拉普拉斯機制與指數機制。而基于不同噪音機制且滿足差分隱私的算法所需噪音大小與全局敏感性(Global Sensitive)密切相關。

定義2.對于任意一個函數：f:D→R^d，函數f的全局敏感性為：

其中，D和D'至多相差一條記錄，R表示所映射的實數空間，d表示函數f的查詢維度，p表示度量Δf使用的L_p距離，通常使用L₁來度量。

拉普拉斯機制通過拉普拉斯分布產生的噪音擾動真實輸出值來實現差分隱私保護。

定理1.對于任一個函數f:D→R^d，若算法A的輸出結果滿足下列等式，則A滿足ε差分隱私：

A(D)＝f(D)+<Lap₁(Δf/ε),…,Lap_d(Δf/ε)>

其中，Lap_i(Δf/ε)(1≤i≤d)是相互獨立的拉普拉斯變量，噪音量大小與Δf成正比，與ε成反比.算法A的全局敏感性越大，所需噪音越大。