[發明專利]一種用于局部差異隱私下的邊際釋放的一致自適應邊際

在審

• 申請號: 202010778159.1
• 申請日: 2020-08-05
• 公開（公告）號: CN112052475A
• 公開（公告）日: 2020-12-08
• 發明（設計）人: 王之涵
• 申請（專利權）人: 西安電子科技大學
• 主分類號: G06F21/62
• 分類號: G06F21/62;G06K9/62
• 代理公司: 北京權智天下知識產權代理事務所(普通合伙) 11638
• 代理人: 蔡金花

1.一種用于局部差異隱私下的邊際釋放的一致自適應邊際，其特征在于，包括以下步驟：

S1：聚合器將總體隨機分為大小相同的m個組；

S2：選擇一組m個邊際集和要使用的FO協議；

S3：聚合器將每個用戶分配給邊際之一，并通知用戶應報告哪個邊際；

S4：每個用戶將其私人價值v投影到他要報告的邊際上，并通過FO報告v的預測值；

S5：服務器在接收到用戶的報告后，使用FO的聚合算法來獲取嘈雜的邊緣表；

S6：給定這些嘈雜的邊際/視圖，可以直接計算一些三向邊際；

S7：生成k向邊距。

2.根據權利要求1所述的一種用于局部差異隱私下的邊際釋放的一致自適應邊際，其特征在于：所述步驟S1中，分組的具體步驟為：

S11:對混合屬性數據表可行的差分隱私保護方法

為加強隱私保護和提高數據可用性，提出一種可對混合屬性數據表執行差分隱私的數據保護方法，該方法首先采用ICMD聚類算法對數據進行聚類匿名，然后在此基礎上進行ε-差分隱私保護，ICMD聚類算法對數據表中的分類屬性和數值屬性采用不同方法計算距離和質心，并引入全序函數以滿足執行差分隱私的要求，通過聚類，實現了將查詢敏感度由單條數據向組數據的分化，降低了信息損失和信息紕漏的風險，

對于查詢函數f，若算法A有則算法A滿足ε-差分隱私，其中，Δf表示查詢函數的敏感性，指的是查詢函數f作用于鄰近數據集時產生的最大距離差，添加拉普拉斯噪聲引起的誤差

S12:混合型數據表中距離和質心計算

現有數據大多數為混合型數據表，即表中的數據屬性既有數值型又有分類型，針對不同屬性的數據有不同的距離計算和質心求解方法，采用單一的方法往往會造成信息丟失、質心偏差等問題，因而提出一種針對混合型數據表的距離計算和質心求解方法，

設混合型數據集D以及X,Y為數據集D中的記錄，每一個記錄具有p維分類屬性和q維數值屬性，計算數據記錄X,Y的距離d(X,Y)_c，首先分別計算其分類屬性距離d(X,Y)_n，定義如下：

S121:分類距離

對于數據表中的任意記錄X,Y，假設數據表含有p維分類屬性，則記錄X,Y的分類屬性部分的距離定義為：

其中，

由式中可知，每維分類屬性取值[0,1]，對于指數型，如果采用海明距離作為每維數據的距離，會導致分類屬性部分的距離被數值屬性部分的距離湮滅，因而采用如下定義計算數值屬性距離；

S122:數值距離

首先將數據記錄的數值屬性部分的每一維進行標準化處理，即X第q維值為其中為該維數據記錄的最大值，為該維數據記錄的最小值，則該數值部分距離為：

S123:混合距離

通過把數據記錄X,Y的分類屬性和數值屬性的距離相加可得它們之間的距離，即：D(X,Y)＝d(X,Y)_c+d(X,Y)_n；

S124:質心

設T是n維數據集D的一個等價類，t_i是等價類T的一條記錄，即t_i∈T,(i＝1,2,...,n)，是記錄t_i的數值屬性部分，是記錄t_i的分類屬性部分，即：設t^o是數值屬性的均值，t^c是屬性的泛化，則等價類T的質心為C(T)＝{t^o,t^c}。

S13:數據發布方法

針對混合性數據表，闡述其距離和質心的計算方法，提出一種滿足k匿名機制的聚類方法，然后對聚類后的數據添加噪聲，實現差分隱私保護。聚類操作減小了查詢函數的敏感性，進而可以通過添加較小的噪聲達到同樣的隱私保護效果，提高數據可用性；

S14:對混合數據表可行的聚類方法

在MDAV的基礎上，采用所述的混合屬性數據表距離和質心計算方法，提出一種對混合屬性數據表可行的聚類匿名化方法CMD，根據k-匿名的定義可知，該方法同時滿足k-匿名機制，

聚類算法CMD(D，k)：

輸入：D為有n≥2k條記錄的原始數據集，k為聚類最小尺寸。

輸出：滿足k-匿名的聚類數據集D′。

步驟：

計算聚類中心，并計算距離該中心最遠的紀錄r和距r最遠的紀錄s，作為兩個初始類中心；

分別計算距離r和s最近的k條記錄，并將其進行歸類，加入到數據集D′；

對剩下的m條記錄，若m≥2k，則對剩下的數據記錄重復步驟1、2；

若m∈[k,2k-1]，則自成一類，加入到數據集D′；

否則，將剩下的m條記錄，劃分到距離格子最近的類中；

計算各類的類質心，并用其替換各類中的數據記錄；

返回替換后的數據表D′；

返回的數據表D′滿足k匿名機制，其中的每個組都至少擁有k條記錄，對每組記錄中的數值屬性和分類屬性，分別用均值和泛化值進行替換，降低了查詢函數的敏感性；

S15:可執行差分隱私保護的聚類改造方法

差分隱私和聚類算法提供了不同的信息紕漏保護，利用聚類算法能降低差分隱私中需要引入的噪聲，實現了查詢函數的敏感性分化，同時差分隱私保護能夠彌補聚類算法的不可抗力任意背景知識攻，兩者的結合能夠達到更好的隱私保護結果，并保留較好的數據可用性，

設M為聚類函數，f為查詢函數，為了有效降低的敏感度，M應該滿足對于數據集D和D′，其中，D為原始數據集，D′為對D修改一條記錄后生成的數據集，其聚類中心基本穩定，那么就要求數據集D′聚類后產生的所有簇與原本相對應的簇兩兩之間只有一條記錄不同，:聚類算法M為非敏感聚類的聚類函數才能執行差分隱私保護；

S16:非敏感聚類

假設數據集D，聚類函數M，D經M的聚類結果{C₁,C₂,...,C_n}，D′為對D只進行修改一條記錄得到的數據集，{C₁′,C₂′,...,C_n′}為D′經M的聚類結果，若聚類結果{C₁,C₂,...,C_n}和{C₁′,C₂′,...,C_n′}對應的簇中只有一個數據記錄不同，稱聚類算法M為非敏感聚類；

為了使聚類方法CMD滿足非敏感聚類，執行差分隱私進行數據保護，需要改變其中的距離函數D為一個全序函數，針對混合型數據表，可通過如下方式構造滿足全序關系的距離函數，

假設數據表D含有n維屬性，其中P維分類屬性，q維輸指數型，X，Y為數據表D中的任意數據記錄，Z為數據表D的聚類中心，通過定義5的距離公式計算距離Z最遠的數據記錄，記為X_b，并計算距離X_b最遠的數據記錄X_t，定義數據表D的邊界為{X_b,X_t}，則

式中，第i個組，為一個距離矩陣形式，是滿足全序關系的距離函數；

其中，

將上述距離函數引入聚類算法CMD，構造滿足非敏感聚類的聚類算法ICMD；

非敏感聚類算法ICMS(D,k)

輸入：D為有n≥2k條記錄的原始數據集，k為聚類最小尺寸，

輸出：可執行差分隱私保護的聚類數據集D′，

步驟：

計算原始數據集的邊界[X_b,X_t]；

分別計算距離X_b和X_t最近的k條記錄，并將其進行歸類，加入到數據集D′；

對剩下的m條記錄，若m≥2k，則對剩下的數據記錄重復步驟2；

否則，將剩下的m條記錄，劃歸到距離格子最近的類中；

計算各類的類質心，并用其替換各類中的數據記錄；

返回替換后的數據表D′，D′為將D聚類分類之后，對每一個組的值改為這一組的均值；

距離計算采用的計算方法，則ICMD滿足非敏感類算法定義，可對其結果執行差分隱私保護，對于查詢函數f_i，有由此可知，原始數據集經過聚類分組，實現了記錄隱藏和查詢敏感性由單條數據向組數據的分化；

S17:差分隱私保護數據發布方法

基于k匿名機制的聚類匿名不能夠抵御背景知識攻擊和同質攻擊，為了進一步保護，在聚類的基礎上對數據記錄添加噪聲，已達到差分隱私保護的目的，添加拉普拉斯噪聲，實現一種對混合屬性數據表實施噪聲擾動的數據保護方法ICMD-DP，

差分隱私保護算法ICMD-DP

輸入：D為有n≥2k條記錄的原始數據集，ε為隱私保護預算；

輸出：滿足k-匿名的ε-差分隱私數據集D_ε；

步驟：

對數據集D進行聚類處理ICMD(D，k)，返回數據集D′；

查詢函數f_i返回數據集D′第i條記錄的屬性，函數S_ε()為查詢結果添加拉普拉斯噪聲，則對于i∈(1,n)，x_i＝S_ε(f_i(D′))，將x_i加入數據集D_ε；

返回數據集D_ε；

每個查詢函數的結果滿足ε-差分隱私，又每條查詢針對的記錄不相交，則根據并行性原則可知，最終的數據集D_ε滿足ε-差分隱私；

對于聚集尺寸為k的數據集D，單個查詢敏感度小于Δf_i(D)/k，并且有n/k個相互獨立的查詢，因此若要滿足經ICMD-DP差分隱私保護的數據查詢敏感度小于原始數據集的查詢敏感度，則需有即由上可知，雖然經聚類算法處理將造成信息丟失，但該部分損失可由敏感度降低帶來的增益進行彌補。