[發(fā)明專利]基于微聚集匿名的差分隱私保護方法

在審

• 申請?zhí)枺?/td>: 201710406535.2
• 申請日: 2017-06-01
• 公開（公告）號: CN107358113A
• 公開（公告）日: 2017-11-17
• 發(fā)明（設(shè)計）人: 吳響;劉偉;魏裕陽;毛亞青
• 申請（專利權(quán)）人: 徐州醫(yī)科大學(xué)
• 主分類號: G06F21/62
• 分類號: G06F21/62
• 代理公司: 北京盛凡智榮知識產(chǎn)權(quán)代理有限公司11616
• 代理人: 晏榮府

技術(shù)領(lǐng)域

本發(fā)明涉及數(shù)據(jù)匿名和差分隱私保護技術(shù)領(lǐng)域，具體是基于微聚集匿名的差分隱私保護方法。

背景技術(shù)

隨著信息技術(shù)的快速發(fā)展，信息量呈指數(shù)型增長。通過數(shù)據(jù)挖掘?qū)@些信息進行挖掘和分析，能夠獲得眾多有用的知識。然而，隨著數(shù)據(jù)挖掘技術(shù)在知識發(fā)現(xiàn)領(lǐng)域的廣泛應(yīng)用，隱私泄露問題也日益凸顯，因此如何在數(shù)據(jù)挖掘的過程中保證數(shù)據(jù)的隱私安全性成為亟待解決的問題。目前，隱私保護技術(shù)可大體分為三類：(1)限制發(fā)布；(2)數(shù)據(jù)失真；(3)數(shù)據(jù)加密。而在現(xiàn)有的方法中，為了提高隱私保護的效果，往往結(jié)合了多種隱私保護技術(shù)。

其中，k-匿名作為數(shù)據(jù)失真的常用技術(shù)，通過保證發(fā)布數(shù)據(jù)集中任何一條數(shù)據(jù)記錄至少有k-1條與其不可區(qū)分的記錄對原始數(shù)據(jù)進行匿名，實現(xiàn)單條記錄隱藏到一組數(shù)據(jù)中，因此能夠分化數(shù)據(jù)的敏感性。但是，k-匿名模型具有很大的缺陷，容易遭到各種復(fù)雜的背景知識及聯(lián)合攻擊。隨著背景知識的不斷擴大和計算能力的不斷提高，通過該方法保護的數(shù)據(jù)遭到背景攻擊和泄露的風(fēng)險日益加大。針對上述問題，Dwork等人提出了差分隱私保護技術(shù)。該技術(shù)定義了一個極為嚴(yán)格的攻擊模型，并用嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)公式證明了其隱私泄露的風(fēng)險。但是差分隱私保護技術(shù)往往會向原始數(shù)據(jù)中添加過量噪音，從而導(dǎo)致數(shù)據(jù)的可用性較差。

鑒于以上問題，國內(nèi)外研究學(xué)者將k-匿名與差分隱私保護方法結(jié)合起來，以此保證數(shù)據(jù)高隱私性與高可用性，目前有：采用k領(lǐng)域數(shù)據(jù)記錄均值替換的方法實現(xiàn)數(shù)據(jù)隱藏、IDP k-means聚類方法以及DCMDP方法。但是這些方法都有不足之處：k領(lǐng)域數(shù)據(jù)記錄均值替換的方法和IDP k-means聚類方法僅考慮到數(shù)據(jù)記錄劃分的準(zhǔn)確性和聚類可用性，并沒有對數(shù)據(jù)隱私性和可用性進行分析。DCMDP方法對原數(shù)據(jù)集匿名化處理的方式并不合理，導(dǎo)致發(fā)布數(shù)據(jù)的可用性大大降低。

發(fā)明內(nèi)容

為了克服上述技術(shù)缺點，本發(fā)明提供基于微聚集匿名的差分隱私保護方法，提升數(shù)據(jù)隱私性的同時，優(yōu)化隱私保護過程中數(shù)據(jù)過度泛化問題，降低信息損失量，保證了發(fā)布數(shù)據(jù)的可用性。

本發(fā)明是以如下技術(shù)方案實現(xiàn)的：基于微聚集匿名的差分隱私保護方法具體步驟如下：

一種基于微聚集匿名的差分隱私保護方法，包括一次劃分單元、二次劃分匿名單元以及加噪處理單元，具體步驟如下：

一次劃分單元：對屬性都是數(shù)值型的原始數(shù)據(jù)集D根據(jù)數(shù)據(jù)分布密度進行聚類處理，將原始數(shù)據(jù)集D劃分成若干個小數(shù)據(jù)集；

二次劃分匿名單元：對一次劃分單元的聚類結(jié)果集中的每一個小數(shù)據(jù)集進行再次劃分，使小數(shù)據(jù)集變成大小在k到2k-1的小類，并用小類的質(zhì)心的值代替小類中其余元組的值，從而使原始數(shù)據(jù)集D滿足最優(yōu)k-劃分的k-匿名；

加噪處理單元：為每一條匿名后的元組隨機添加拉普拉斯噪音，獲得具有噪音的數(shù)據(jù)表。

優(yōu)選的，一次劃分單元具體步驟如下：

1)將原始數(shù)據(jù)集D內(nèi)的所有點標(biāo)記為未訪問；

2)訪問原始數(shù)據(jù)集D內(nèi)一個標(biāo)記為未訪問的點u，獲取到這個點距離為e之內(nèi)(包括e)的所有點，個數(shù)記作p，同時更改這個點的標(biāo)記為已訪問；

3)如果p大于或等于Minp，則將步驟2)獲取的這p個點與點u聚集為一類；否則，點u暫時被標(biāo)記為噪音點；

4)如果原始數(shù)據(jù)集D中所有的點都被標(biāo)記為已訪問，則執(zhí)行步驟5)；否則，對未訪問的點重復(fù)執(zhí)行2)和3)；

5)如果存在一個點屬于若干個類，則取這若干個類的并集，形成一個新的類；否則，繼續(xù)執(zhí)行步驟6)；

6)計算無法被聚集的噪音點與各個聚類質(zhì)心的歐式距離，將噪音點歸入距離它最近的類中；

7)原始數(shù)據(jù)集D被劃分成多個小數(shù)據(jù)集。

優(yōu)選的，對一次劃分單元聚類結(jié)果集中的每個小數(shù)據(jù)集通過二次劃分匿名單元進行處理，具體步驟如下：

1)計算小數(shù)據(jù)集的質(zhì)心，獲取距離質(zhì)心最遠的點x₁，再獲取距離x₁最遠的點x₂，以x₁為中心，將x₁以及距離x₁最近的k-1個點劃分為一個等價類；同理，以x₂為中心也獲得一個等價類；

2)如果小數(shù)據(jù)集經(jīng)步驟1)后仍未被劃分的元組的數(shù)量大于或等于2k，則對這些未被劃分的元組重復(fù)執(zhí)行步驟2)，直至剩余的元組數(shù)量小于2k；如果未被劃分的元組的數(shù)量大于等于k且小于等于2k-1，則將這些元組劃分為一個類；否則，將未被劃分的元組劃分到距離各自最近的等價類中；