[發(fā)明專利]一種基于層次模型的差分隱私邏輯網(wǎng)格空間數(shù)據(jù)發(fā)布方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202110040810.X
• 申請(qǐng)日: 2021-01-13
• 公開（公告）號(hào): CN112784297B
• 公開（公告）日: 2022-11-08
• 發(fā)明（設(shè)計(jì)）人: 張偉;倪松;陳云芳
• 申請(qǐng)（專利權(quán)）人: 南京郵電大學(xué)
• 主分類號(hào): G06F21/62
• 分類號(hào): G06F21/62
• 代理公司: 南京蘇高專利商標(biāo)事務(wù)所(普通合伙) 32204
• 代理人: 柏尚春

1.一種基于層次模型的差分隱私邏輯網(wǎng)格空間數(shù)據(jù)發(fā)布方法，其特征在于：包括有以下步驟：

S1：四分自適應(yīng)劃分：對(duì)數(shù)據(jù)域進(jìn)行四分自適應(yīng)網(wǎng)格劃分，將數(shù)據(jù)域劃分為若干個(gè)細(xì)粒度網(wǎng)格，并對(duì)這些細(xì)粒度網(wǎng)格的真實(shí)計(jì)數(shù)值添加噪聲，具體包括以下步驟：

S1.1：根據(jù)數(shù)據(jù)域的數(shù)據(jù)點(diǎn)個(gè)數(shù)N、分配的隱私保護(hù)預(yù)算α₁ε和常數(shù)c，計(jì)算粗粒度劃分參數(shù)m₁：

其中取c＝10，再對(duì)數(shù)據(jù)域進(jìn)行粒度為m₁×m₁的粗粒度劃分，得到m₁×m₁個(gè)粗粒度網(wǎng)格，并對(duì)每個(gè)粗粒度網(wǎng)格的真實(shí)計(jì)數(shù)上添加隱私保護(hù)預(yù)算為α₁ε的拉普拉斯噪聲；

S1.2：根據(jù)每個(gè)粗粒度網(wǎng)格內(nèi)噪聲計(jì)數(shù)N′、分配的隱私保護(hù)預(yù)算α₂ε和常數(shù)c₂，計(jì)算細(xì)粒度劃分參數(shù)m₂，其計(jì)算公式為：

其中取c₂＝c/2，再對(duì)每個(gè)粗粒度網(wǎng)格進(jìn)行粒度為m₂×m₂的細(xì)粒度劃分，并對(duì)每個(gè)細(xì)粒度網(wǎng)格的真實(shí)計(jì)數(shù)上添加隱私保護(hù)預(yù)算為α₂ε的拉普拉斯噪聲；

S1.3：對(duì)每個(gè)粗粒度網(wǎng)格與其所包含的所有細(xì)粒度網(wǎng)格進(jìn)行一致性約束；

S2：邏輯合并：將噪聲計(jì)數(shù)值相似的鄰近細(xì)粒度網(wǎng)格進(jìn)行合并，形成邏輯網(wǎng)格；進(jìn)一步將分布密度相似的邏輯網(wǎng)格合并成若干個(gè)邏輯網(wǎng)格域；

S3：邏輯劃分：根據(jù)查詢貢獻(xiàn)率，將邏輯網(wǎng)格劃分成若干個(gè)葉子網(wǎng)格，具體包括以下步驟：

S3.1：以對(duì)原始數(shù)據(jù)域進(jìn)行粒度為m₁×max(m₂)所形成的最細(xì)粒網(wǎng)格作為計(jì)算單元來(lái)計(jì)算查詢貢獻(xiàn)率；

S3.2：根據(jù)查詢貢獻(xiàn)度對(duì)邏輯網(wǎng)格進(jìn)行劃分；

S4：構(gòu)建層次模型：將邏輯網(wǎng)格域、邏輯網(wǎng)格、葉子網(wǎng)格構(gòu)建成層次模型并對(duì)每層的節(jié)點(diǎn)計(jì)數(shù)添加噪聲并進(jìn)行后置處理，最后將所得層次模型發(fā)布，具體包括以下步驟：

S4.1：對(duì)每個(gè)層次模型的根節(jié)點(diǎn)邏輯網(wǎng)格真實(shí)計(jì)數(shù)、中間節(jié)點(diǎn)邏輯網(wǎng)格真實(shí)計(jì)數(shù)、葉子節(jié)點(diǎn)葉子網(wǎng)格真實(shí)計(jì)數(shù)分別添加拉普拉斯噪聲進(jìn)行擾動(dòng)；

S4.2：對(duì)層次結(jié)構(gòu)進(jìn)行一致性約束后處理，并對(duì)所得結(jié)果進(jìn)行發(fā)布。

2.根據(jù)權(quán)利要求1所述的一種基于層次模型的差分隱私邏輯網(wǎng)格空間數(shù)據(jù)發(fā)布方法，其特征在于：所述S2具體包括以下步驟：

S2.1.1：對(duì)每個(gè)粗粒度網(wǎng)格內(nèi)的相鄰細(xì)粒度網(wǎng)格采用平方和誤差SSE作為指標(biāo)進(jìn)行合并，公式如下：

即當(dāng)兩個(gè)鄰近的細(xì)粒度網(wǎng)格的噪聲計(jì)數(shù)值接近，且兩個(gè)鄰近的細(xì)粒度網(wǎng)格的SSE在閾值θ內(nèi)，則判定這兩個(gè)網(wǎng)格單元是分布相似的；

S2.1.2：對(duì)S2.1.1合并得出的位置相鄰且不屬于同一個(gè)粗粒度網(wǎng)格內(nèi)的區(qū)域進(jìn)行合并，形成邏輯網(wǎng)格，采用的合并指標(biāo)為分布密度ρ：

其中c_i為區(qū)域的噪聲計(jì)數(shù)，S_i為區(qū)域面積，設(shè)合并閾值為Φ；

S2.2：對(duì)位置不相鄰且數(shù)據(jù)分布相近的邏輯網(wǎng)格進(jìn)行邏輯上的合并，形成邏輯網(wǎng)格域，其合并指標(biāo)仍采用分布密度如公式(5)所示，合并閾值仍采用Φ。