[發明專利]一種具有差分隱私的安全多方k-means聚類方法

有效

• 申請號: 202110101184.0
• 申請日: 2021-01-26
• 公開（公告）號: CN112765664B
• 公開（公告）日: 2022-12-27
• 發明（設計）人: 張恩;趙樂;李會敏;姬聰敏;陳宛楨
• 申請（專利權）人: 河南師范大學
• 主分類號: G06F21/62
• 分類號: G06F21/62;G06K9/62
• 代理公司: 北京華際知識產權代理有限公司 11676
• 代理人: 曹書華

1.一種具有差分隱私的安全多方k-means聚類方法，其特征在于：存在m個參與方U₁,U₂,…,U_m，各個參與方U_i有輸入數據集D_i，其中D_i＝d_i,1,…,d_i,l,i∈{1,…,m}，添加噪聲采用的兩個差分隱私預算分別為ε₁,ε₂，首先初始化聚類中心，每個參與者U_i接收添加噪聲之后的聚類中心{C_1,1,…,C_1,k}，如果相鄰兩次聚類中心之間的距離和η大于閾值則繼續迭代，參與者U_i計算出數據點p_x,p_x∈D與各個聚類中心C_j(1≤j≤k)的歐幾里得距離，得到數據點p_x與聚類中心C_j的距離最小，則把數據點p_x統計到O_j集合中，統計出O_j集合中的數據點數目Num_i,j，以及數據點屬性和Sum_i,j，為保護聚類中心的隱私，參與方U_i產生隨機數a_i.j,g_i.j，并把a_i.j,g_i.j發送至主機S₁，把Sum_i,j-a_i,j，Num_i,j-g_i,j發送至主機S₂，主機S₁將從所有用戶接收到的隨機數a_i.j,g_i.j進行累加，得到第j個聚類對應的隨機數和，分別為主機S₂將從所有用戶接收到的Sum_i,j-a_i,j,Num_i,j-g_i,j進行累加，分別為主機S₁,S₂分別根據差分隱私預算ε₁,ε₂，產生噪聲b_z,j，g_z,j，對主機S₁,S₂計算的A_j,V_j,B_j,W_j進行隱私保護,同時主機S₁,S₂利用混淆電路進行聚類中心更新得到新的聚類中心C_z,j(C_z,j為第z次迭代產生的聚類中心)，每個用戶通過判斷新的聚類中心與上次迭代求出的聚類中心之間的距離η，如果η大于閾值則執行下次迭代，否則返回最終的聚類中心C_z,1,…,C_z,k；

在初始化階段，參數設置：m個參與方U₁,U₂,…,U_m，每個參與方U_i有數據集D_i，其中每個數據集包含的數據表示為D_i＝d_i,1,…,d_i,l,i＝{1,…,m}，ε₁,ε₂分別是添加噪聲采用的兩個差分隱私預算，k是聚類的個數，所有參與者：U₁,U₂,…,U_m執行下列步驟：

a.如果參與方的個數m小于聚類分類個數k，則每個參與方U_i從各自所擁有的數據集D_i中選擇個數據點作為前個初始聚類中心然后再隨機選擇個參與方，每個選中的參與方各自從他們的數據集D_i中隨機選取一個數據點作為后個初始聚類中心如果參與方的個數m大于或等于聚類個數k，則隨機選擇k個參與者，每個選中的參與方各自從他們的數據集D_i中隨機選取一個數據點作為初始聚類中心；

b.參與方產生與聚類中心對應的隨機數{a₁,…,a_k}，并將隨機數{a₁,…,a_k}發送至主機S₁，將{c₁-a₁,…,c_k-a_k}發送到主機S₂；

c.主機S₁,S₂分別以差分隱私預算分別為ε₁,ε₂為{a₁,…,a_k}和{c₁-a₁,…,c_k-a_k}生成對應的Laplace噪聲{b₁,…,b_k}，{g₁,…,g_k}，主機S₁,S₂用混淆電路計算C_1,i＝(c_i-a_i)+a_i+b_i+g_i,i＝{1,…,k}；

d.每個用戶U_i接收添加噪聲之后的聚類中心{C_1,1,…,C_1,k}；

在迭代階段，參數設置：m個參與方U₁,U₂,…,U_m，每個參與方U_i擁有數據集D_i，其中p_x表示數據集D_i中的數據點，記作p_x∈D_i，ε₁,ε₂分別是添加噪聲采用的兩個差分隱私預算，k是聚類個數，O₁,O₂,…,O_k是k個聚類集合，閾值η是距離參數，迭代參數為z，Sum_i,j,Num_i,j分別為第i次迭代中聚類O_j集合中數據點屬性之和以及數據點數目之和，所有參與者：U₁,U₂,…,U_m執行下列步驟：

A.判斷距離參數η與閾值的大小關系，如果則迭代次數z＝z+1；

B.計算參與者中的所有數據點到各個聚類中心的距離||p_x-C_z,j||,p_x∈D_i，j＝{1,…,k}，如果||p_x-C_z,j||≤||p_x-C_z,v||,p_x∈D_i,1≤v≤k則把數據劃分到聚類O_j，統計出聚類O_j集合中的數據點數目Num_i,j＝|O_j|，以及聚類O_j集合中數據點屬性和為保護聚類中心的隱私，參與方U_i產生隨機數a_i.j,g_i.j，并把a_i.j,g_i.j發送至主機S₁，把Sum_i,j-a_i,j，Num_i,j-g_i,j發送至主機S₂；

C.主機S₁將從所有用戶接收到的隨機數a_i.j,g_i.j進行累加，得到第j個聚類對應的隨機數和，分別為主機S₁根據差分隱私預算ε₁，為A_j,V_j產生噪聲

D.主機S₂將從所有用戶接收到的Sum_i,j-a_i,j,Num_i,j-g_i,j進行累加，分別為主機S₂分別根據差分隱私預算ε₂，為B_j,W_j產生噪聲達到對B_j,W_j的隱私保護；

E.主機S₁,S₂利用混淆電路計算每個用戶令進行聚類中心更新，并計算兩次迭代之間聚類中心的距離如果則輸出最終的聚類中心C_z,1,…,C_z,k，否則返回步驟a。