[發明專利]一種密度峰值聚類算法的差分隱私保護方法

在審

• 申請號: 201710680326.7
• 申請日: 2017-08-10
• 公開（公告）號: CN107451618A
• 公開（公告）日: 2017-12-08
• 發明（設計）人: 孟小峰;郭勝娜
• 申請（專利權）人: 中國人民大學
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06F21/60
• 代理公司: 北京紀凱知識產權代理有限公司11245
• 代理人: 徐寧,孫楠

技術領域

本發明涉及一種差分隱私保護方法，特別是關于一種密度峰值聚類算法的差分隱私保護方法。

背景技術

隨著差分隱私保護的技術出現，對于傳統的聚類算法，出現了很多差分隱私保護的聚類方法。但是對于大數據下新型的聚類算法還沒提出相應的隱私保護方法。隱私保護k-means聚類和隱私保護DBSCAN已經被研究。不同于差分隱私，他們不能夠對會潛在泄露個人信息的結果提供保護。聚類的結果中可能包含新的實體或結點之間未知的關系，因此聚類可能揭示敏感信息。

到目前為止，研究最多的是對k-means聚類算法的隱私保護。從2003到2008 年，大多數的k-means算法研究采用安全多方計算，其中數據的分布類型包括垂直數據，水平數據和混合數據。上述工作采用的是Yao協議和同態加密技術。隱私代價是通過計算和通信成本來衡量的，對比于同態加密技術的隱私代價，Yao 協議代價將更大，而且同態加密技術的加密成本也是不容忽視的。傳統的基于分割的聚類算法(最常見的為k-means算法)不能夠發現非球面形狀的聚簇，基于密度的聚類方法可以識別，經典的基于密度的聚類算法為DBSCAN。對此聚類算法的一些隱私保護工作包括Kunar et al.(針對水平和垂直分布的數據)，以及 Jinfeiet.al(數據分布特征可以是任意分布的)，他們都是基于Pailler的加法同態加密技術的乘法協議。但是，這些安全函數保護協議都忽略了一個問題就是沒有函數使用來保護隱私的，他們并不提供保護個人敏感信息不被泄露。自從差分隱私被提出并被數據庫領域廣泛接受后，隱私保護要求已經實現了從句法模型更嚴格的差分隱私模型。

當然，其中去多工作是針對k-means算法。例如，McSherry構建了PINQ系統，實現了差分隱私保護k-means聚類算法。Nissim et al.提出了抽樣與聚合框架，并應用到了GUPT系統中，也實現了對k-means算法進行了隱私保護。Zhang et al. 提出了基于遺傳算法的差分隱私模型擬合，也應用到了k-means算法。

在數據類型多樣性的背景下，Alex Rodriguez和Alessandro Laio提出了快速搜索和發現密度峰值的聚類算法(DPC算法)。此聚類算法能夠聚出任意形狀和任意維度的數據集，它可以很好的應用于生物信息學、文獻計量學、模式識別。據我們所知，目前關于此聚類算法還沒有隱私保護的工作。

發明內容

針對上述問題，本發明的目的是提供一種密度峰值聚類算法的差分隱私保護方法，該方法能解決大數據背景下的新型密度峰值聚類算法的隱私保護，保證聚類的正確性。

為實現上述目的，本發明采取以下技術方案：一種密度峰值聚類算法的差分隱私保護方法，其特征在于包括以下步驟：1)基于Voronoi圖分割的方法對數據對象進行分組；2)對數據集D中每一個點x_i計算局部密度2.1)需要從分組聚簇S_i復制四個點到S_j；2.2)往數據集中添加噪音：

式中，ρ'表示加入噪音后的局部密度值，表示點x_i和點x_j之間的距離，d_c表示閾值，Lap(β)表示加入的噪音，β表示加入的噪音量，χ()表示是一個函數，如果l＜0，則χ(l)＝1；否則χ(l)＝0，GS_ρ表示局部密度函數ρ的敏感度，ε₁表示第一階段隱私預算；2.3)如果d_c滿足如下不等式，則ρ'的計算滿足ε-差分隱私保護：

3)對每一個點x_i計算密度距離并將數據集中添加噪音，其處理方法與步驟2.1)至2.2)相同，使δ”的計算滿足ε-差分隱私。

進一步，所述步驟1)中，假設數據對象為數據集D，對于數據集D，挑選M 個點作為初始中心點集；然后根據垂直線，將數據集D分割成M個相互不相交的分組，數據集D中的每一個點被分配到最近的初始中心點所在的分組中。