一種基於k‑means的分布式差分隱私保護方法與流程

2023-06-03 02:14:56 1

本發明涉及一種分布式差分隱私保護方法，具體涉及一種基於k-means的分布式差分隱私保護方法。

背景技術：

目前，對智能電網大數據進行數據挖掘的主要任務之一就是聚類。而K-means是目前聚類算法中，一個使用較為廣泛的聚類算法。k-means聚類也稱為快速聚類，尤其適用於對大數據進行聚類的情形。對智能電網大數據集來說，K-means聚類算法具有可伸縮性和高效率性。然而，如何對智能電網大數據在進行分布式隱私保護K-means聚類數據挖掘是急需解決的問題，以實現數據分布式情況下的各參與方的隱私保護。

目前，國內外掀起了一股差分隱私保護技術的研究熱潮。相比其他的隱私保護技術，差分隱私保護機制是一種完全獨立於攻擊者背景知識的強隱私概念。差分隱私假定攻擊者擁有任意的背景知識，無論特定的個體記錄是否在數據集中，對該數據集的分析或查詢結果在形式上不可分，即分析或查詢結果不強依賴於單個記錄。同時，差分隱私可以在隱私保護和數據挖掘結果可用性之間取得很好的權衡。

差分隱私保護通過隨機噪聲的添加使包含敏感屬性的數據失真，同時保持某些數據或數據屬性不變。經過添加噪聲處理之後的數據仍然保持原有數據的某些統計特性，以便進行數據挖掘等操作。差分隱私的形式化定義如下：

定義1.給定兩個近鄰數據集D1和D2(D1和D2之間相差一條數據記錄)。給定一個隱私挖掘算法A，Range(A)表示A的取值範圍。若算法A在數據集D1和D2上輸出任意結果O(O∈Range(A))滿足下列不等式，則稱算法A滿足ε-差分隱私(0＜ε＜1)。

Pr(A(D1)＝O)≤exp(ε)×Pr(A(D2)＝O)

其中概率Pr(.)表示隱私披露的風險並且由隱私挖掘算法A的隨機性控制；隱私預算參數ε表示隱私保護程度，ε值越小表示隱私保護程度越高。從定義1可以看出，差分隱私限制了任意一個數據記錄對算法A輸出結果的影響，即它保證了在數據集中添加或者刪除一條記錄不會影響查詢輸出結果。

差分隱私保護機制通常是通過在查詢函數的返回值中加入適量Laplace噪聲來實現ε-差分隱私保護。本文使用Laplace噪聲添加機制實現對全局樸素貝葉斯分類模型的ε-差分隱私保護。下面給出Laplace機制的相關描述。當位置參數為0,尺度參數為b(b＞0)時，Laplace分布標記為Lap(b)，其概率密度函數為:

定義2.Laplace機制.給定數據集D，設有函數f：D→Rd，其敏感度為Δf∈R。那麼隨機算法M(D)＝f(D)+Y提供ε-差分隱私保護。其中Y～Lap(Δf/ε)為隨機噪聲且服從尺度參數為Δf/ε的Laplace分布。Δf表示函數f的敏感度由函數f決定且不同的函數通常具有不同的敏感度Δf，ε表示隱私參數且0＜ε＜1。滿足ε-差分隱私保護時，ε越小加入的噪聲越多隱私保護的級別越高。

敏感度Δf是決定加入噪聲大小的關鍵參數。敏感度是指數據集任意添加或者刪除一條數據記錄對查詢結果造成的最大改變。在差分隱私保護方法中定義了兩種敏感度即全局敏感度(Global Sensitivity)和局部敏感度(localSensitivity)。下面簡要介紹本文使用的全局敏感度。

定義3.全局敏感度.設有函數f：D→Rd，輸入為一數據集，輸出為一個d(d∈Z+)維實數向量。對於任意的近鄰數據集D1和D2，下面給出了函數f的全局敏感度度的計算公式。

其中||f(D1)-f(D2)||1表示f(D1)和f(D2)之間的1-階範數距離。函數的全局敏感度由函數本身決定，與數據集無關且不同的函數會有不同的全局敏感度。

引理1(Laplace分布的可分性).假設Lap(λ＝Δf/ε)是服從Laplace分布的噪聲，其概率密度函數是那麼噪聲Lap(λ)的分布具有無限可分性，即其中整數r≥1，和表示獨立同分布的服從伽瑪分布的隨機噪聲(其概率密度函數是g(x，r，λ)＝((1/λ)1/r/Γ(r))x1/r-1e-x/λ，x≥0)。

從引理1，可以看出一個Laplace噪聲(Lap(λ))可以由分布式環境下的r個參與方聯合生成，每個參與方添加的局部噪聲是因此，可以利用該機制讓r個分布式參與方聯合添加一個噪聲，以降低合謀攻擊的危險。

為了減少合謀攻擊，本發明通過Laplace分布的無限可分性讓r個參與方聯合生成一個Laplace噪聲，但是，每一個參與方所生成的噪聲不足以保護自己的局部數據隱私。

技術實現要素：

為解決上述現有技術中的不足，本發明的目的是提供一種基於k-means的分布式差分隱私保護方法，本發明所採用的差分隱私保護技術定義了一個極其嚴格的攻擊模型，並對隱私洩漏風險進行了嚴格的數學證明和定量化表示。同時，差分隱私保護機制也能在k-means聚類數據挖據結果可用性和隱私保護級別兩方面取得更好的平衡。在嚴格的隱私披露風險度量下，實現了在加入少量噪聲的同時達到較高隱私保護標準的目的。

本發明的目的是採用下述技術方案實現的：

本發明提供一種基於k-means的分布式差分隱私保護方法，其改進之處在於，所述方法包括下述步驟：

⑴確定參與方Pt和數據挖掘方DM，以及對應局部資料庫中的數據記錄，所述數據記錄都是d維空間[0，1]d中的一個點；

⑵將d維空間[0，1]d中的樣本點集合聚合為k個聚簇，k∈Z+；

⑶數據挖掘方DM初始化，並按下述步驟⑷-⑻更新；

⑷參與方Pt將自己的局部資料庫中的樣本劃分成k個集合，即

⑸參與方Pt將經過同態加密機制加密之後的密文和發送給數據挖掘方DM；

⑹數據挖掘方DM根據密文和計算得到經過同態加密機制加密之後的密文Epk(sumj)和Epk(numj)；

⑺數據挖掘方DM對步驟⑹中得到的密文Epk(sumj)和Epk(numj)分別進行解密得到d維空間[0，numj]d的一個樣本點，重複執行k次得到全局的k個聚類中心{u1，...，uk}；

⑻不斷迭代執行步驟⑷-⑺直至點到集合的劃分不再變化或迭代次數達到上限。

進一步地，所述步驟⑴中，在數據水平分布情況下，設有r個參與方Pt和數據挖掘方DM；數據挖掘方DM和每一個參與方Pt均有對應的局部資料庫，資料庫中的每一個數據記錄都是d維空間[0，1]d中的一個點；r∈Z+；d∈Z+；t為參與方的個數，t∈[1，r]。

進一步地，所述步驟⑵中，設將d維空間[0，1]d中的一個樣本點集合聚合為k個聚簇，每個聚簇包括k』個中心點，則第j』個中心點為uj＝sumj/numj，則sumj是d維空間[0，numj]d的一個點，uj是d維空間[0，1]d的一個點；在d維空間[0，1]d的樣本點集合中添加或刪除一個點，對分母的影響最大為1，num的敏感度為1；

對於分子sumj，在d維空間[0，1]d的樣本點集中添加或刪除一個點，分子sumj每一維的變化最大為1；其中sumj表示第j個聚簇中所包含的樣本點之和，numj表示第j個聚簇中所包含的樣本點個數，整數numj≥1；k∈Z+；j表示聚簇，取值為1≤j≤k；j』表示中心點，取值為1≤j'≤k。

進一步地，所述步驟⑶中，數據挖掘方DM生成同態加密機制的公鑰pk和私鑰sk，並將公鑰pk發送給每一個參與方Pt，數據挖掘方DM依據先驗知識選擇樣本點集合k作為初始中心點集合{u1，...，uk}，並將初始中心點集合{u1，...，uk}發送給每一個參與方Pt，其中每一個初始中心點都是d維空間[0，1]d的一個點，並按步驟⑷-⑻更新。

進一步地，所述步驟⑷中，每一個參與方Pt(t∈[1，...，r])收到數據挖掘方DM發送過來的中心點集合{u1，...，uk}之後，將自己局部資料庫的每一個樣本點劃分到最近的中心點，最終將自己的局部資料庫中的樣本劃分成k個樣本點集合，即樣本點集合

進一步地，所述步驟⑸中，對於1≤j'≤k(步驟2中的中心點為第j個中心點，j的取值範圍也是1到k之間，與此處表述是一致的)，每一個參與方Pt計算得到集合內所有點之和和集合的樣本數目

首先對添加噪聲得到：

參與方Pt再將添加了噪聲之後得到的和基於同態加密機制對和分別進行加密得到密文和參與方Pt將經過同態加密機制加密之後的密文和發送給數據挖掘方DM；

其中，表示d維空間中的一個點；r，λ兩項均為伽馬分布函數的參數，ε為查分隱私保護的隱私洩露量，t為參與方的個數，為伽馬分布函數。

進一步地，所述步驟⑹中，數據挖掘方DM收到所有參與方Pt(t∈[r])發送的密文之後，然後通過分別計算下述式子：

和

得到經過同態加密機制加密之後的密文Epk(sumj)和Epk(numj)；

其中sumj表示d維空間[0，numj]d的一個樣本點，整數numj大於0。

進一步地，所述步驟⑺中，數據挖掘方DM對步驟⑹中得到的密文Epk(sumj)和Epk(numj)分別進行解密得到sumj＝Dsk(Epk(sumj))和numj＝Dsk(Epk(numj))，進而得到第j個聚簇的中心點即uj＝sumj/numj；重複執行步驟k次，直到得到全局的k個聚類中心{u1，...，uk}。

與最接近的現有技術相比，本發明提供的技術方案具有的優異效果是：

相比其他的隱私保護技術，差分隱私保護機制定義了一個極其嚴格的攻擊模型：攻擊者已知除一條數據記錄以外的所有數據記錄。在該攻擊模型下，攻擊者也無法從任何相關的背景知識或者關聯的信息中推斷出剩餘一條數據記錄的任何隱私信息。差分隱私保護機制不僅對隱私洩漏風險進行了嚴格的數學證明和定量化表示，還能在隱私保護和數據挖掘結果可用性之間取得很好的權衡。本發明首次將差分隱私保護機制引入到水平分布式k-means隱私保護算法。該基於k-means的水平分布式差分隱私保護算法能夠提供更強的隱私保護保障，同時也能保證結果的可用性。此外，每一個參與方添加的噪聲不足以保護自己的數據隱私。因此本發明採用同態加密機制，對各參與方的隱私數據提供更進一步的安全性保障。相比現有的分布式k-means隱私保護算法，本文提出的基於k-means的分布式差分隱私保護算法能提供更強的隱私和安全性保證。

附圖說明

圖1是本發明提供的是實驗中使用的用於測試差分隱私k-means聚類算法性能的數據示意圖；

圖2是本發明提供的基於k-means的分布式差分隱私保護方法的流程圖。

具體實施方式

下面結合附圖對本發明的具體實施方式作進一步的詳細說明。

以下描述和附圖充分地示出本發明的具體實施方案，以使本領域的技術人員能夠實踐它們。其他實施方案可以包括結構的、邏輯的、電氣的、過程的以及其他的改變。實施例僅代表可能的變化。除非明確要求，否則單獨的組件和功能是可選的，並且操作的順序可以變化。一些實施方案的部分和特徵可以被包括在或替換其他實施方案的部分和特徵。本發明的實施方案的範圍包括權利要求書的整個範圍，以及權利要求書的所有可獲得的等同物。在本文中，本發明的這些實施方案可以被單獨地或總地用術語「發明」來表示，這僅僅是為了方便，並且如果事實上公開了超過一個的發明，不是要自動地限制該應用的範圍為任何單個發明或發明構思。

本發明使用同態加密機制對各參與方的隱私數據提供進一步的安全性保障。同態加密算法機制的描述如下：

同態加密算法機制是滿足下列條件的一個六元組

⑴M是明文空間；

⑵C是密文空間；

⑶K是公私鑰對集合；

⑷是同態運算符；

⑸對於任意的(pk，sk)∈K(pk稱作公鑰，sk稱作私鑰)，對應一個加密算法Epk∈E(E是加密算法集合，E：M→C)和解密算法Dsk∈D(D是解密算法集合，D：C→M)，且對任意的m∈M，滿足c＝Epk(m)，m＝Dsk(c)＝Dsk(Epk(m))，其中Epk和Dsk都是多項式時間內可執行的。

⑹對於所有的(pk，sk)∈K，由推出是計算上不可能的。

⑺對任意的x，y∈M，

根據運算符的不同，可分為加同態加密和乘同態加密算法。本專利使用了加同態性的算法，其可表述為

k-means聚類算法的基本思想是從數據集中任意選擇k個數據對象作為初始聚類中心，計算每個對象與這些中心點之間的距離，並根據最小距離將每個數據對象劃分到指定的簇，然後重新計算每個簇的中心點，以新中心點作為新的聚類中心。循環迭代上述過程，直至每個簇的數據不再發生變化。在k-means聚類算法中，計算離每個樣本點最近的中心點會洩漏隱私。通過對k-means進行分析發現，計算中心點時需要用集合內所有點之和除以數目。因此，只要發布點之和與數目的近似值就不會洩漏隱私。

本發明提供的基於k-means的分布式差分隱私保護方法的流程圖如圖2所示，包括下述步驟：

⑴在數據水平分布情況下，假設有r(r∈Z+)個參與方Pt(t∈[1，r])，一個數據挖掘方(Data Miner，DM)。數據挖掘方和每一個參與方都有自己的局部資料庫，資料庫中的每一個數據記錄都是d(d∈Z+)維空間[0，1]d中的一個點。

⑵假設將d維空間[0，1]d中的一個樣本點集合聚合為k(k∈Z+)個聚簇，每個聚簇包括k』個中心點，則第j』個中心點為uj＝sumj/numj，其中sumj表示第j個聚簇中所包含的樣本點之和，numj(整數numj≥1)表示第j個聚簇中所包含的樣本點個數。則sumj是d維空間[0，numj]d的一個點，而uj是d維空間[0，1]d的一個點。在d維空間[0，1]d的樣本點集中添加或刪除一個點，對分母的影響最大為1，因此num的敏感度為1。對於分子sumj，在d維空間[0，1]d的樣本點集中添加或刪除一個點，分子sumj每一維的變化最大為1。

⑶數據挖掘方首先生成同態加密機制的公鑰pk和私鑰sk，並將公鑰pk發送給每一個參與方Pt(t∈[1，...，r])。數據挖掘方DM然後依據一定的先驗知識選擇k個點作為初始中心點{u1，...，uk}(每一個初始中心點都是d維空間[0，1]d的一個點)，並將初始中心點集合{u1，...，uk}發送給每一個參與方Pt(t∈[1，...，r])，並按以下步驟更新：

⑷每一個參與方Pt(t∈[1，...，r])收到數據挖掘方DM發送過來的中心點集{u1，...，uk}之後，將自己局部資料庫的每一個樣本點劃分到最近的中心點，最終將自己的局部資料庫中的樣本劃分成k個集合，即

⑸對於1≤j'≤k，每一個參與方Pt(t∈[1，...，r])計算得到集合內所有點之和和集合的樣本數目首先對添加噪聲得到：

(其中，表示d維空間中的一個點)。參與方Pt再將添加了噪聲之後得到的和基於同態加密機制對和分別進行加密得到密文和最後參與方Pt將經過同態加密機制加密之後的密文和發送給數據挖掘方DM。

⑹數據挖掘方DM收到所有參與方Pt(t∈[r])發送的密文之後，然後通過分別計算和就可以得到經過同態加密機制加密之後的密文Epk(sumj)和Epk(numj)。其中sumj表示d維空間[0，numj]d的一個樣本點，整數numj大於0。

⑺數據挖掘方DM對步驟⑹中得到的密文Epk(sumj)和Epk(numj)分別進行解密得到sumj＝Dsk(Epk(numj))和numj＝Dsk(Epk(numj))，進而得到第j個中心點即uj＝sumj/numj。重複執行步驟k次，直到得到全局的k個聚類中心{u1，...，uk}。

⑻不斷迭代執行步驟⑷-⑺直至點到集合的劃分不再變化或迭代次數達到上限。

實施例一

下面結合智能電網中對用戶在不在家時用戶的用電情況對用戶進行聚類。通過試驗進一步說明查分隱私k-means聚類算法在數據的可用性和隱私保護兩個方面可以取得很好的平衡，進一步說明該方法的有效性。

圖1是實驗中使用的用於測試差分隱私k-means聚類算法性能的數據，該數據是關於用戶在不在家時，家裡的用電情況。該數據已經知道數據原有的聚類標籤。數據集的真實標籤，可以用於定量的描述聚類算法的聚類結果。

具體的實施方式如下所示：

a)首先收集得到一個用戶的訓練數據，即用戶在家和不在家兩種情況下的家庭用電數據，假設該數據集合的名稱是data。該數據集所對應的類別標籤為categories。

b)先用k-means聚類算法對該數據集進行聚類。得到聚類結果即準確率，如表格1所示。

表1訓練數據的描述

程序的運行語句為：

Res_kmeans＝kmeans(data,categories)；

c)再在上面的數據集上運行差分分隱私k-means聚類算法，得到聚類算法的聚類的準確率，如表格2所示。

表2試驗結果

表2描述的分別使用k-means聚類算法和差分隱私k-means聚類算法在上面描述的數據集上進行測試得到的實驗結果。實驗結果主要從聚類的準確率(Accuracy)對這兩個算法進行衡量比較。實驗結果表明，在進行差分隱私保護k-means聚類分析的同時，其算法準確性也不低於k-means算法，具有較好的隱私保護能力和聚類分析的實用性。

以上實施例僅用以說明本發明的技術方案而非對其限制，儘管參照上述實施例對本發明進行了詳細的說明，所屬領域的普通技術人員依然可以對本發明的具體實施方式進行修改或者等同替換，這些未脫離本發明精神和範圍的任何修改或者等同替換，均在申請待批的本發明的權利要求保護範圍之內。