[發明專利]基于本地化差分隱私的兩階段k-means聚類處理系統及方法

在審

• 申請號: 202110730733.0
• 申請日: 2021-06-29
• 公開（公告）號: CN113537308A
• 公開（公告）日: 2021-10-22
• 發明（設計）人: 王寧;莊健;朱佩瑤;王志剛;殷波;王曉東;魏志強
• 申請（專利權）人: 中國海洋大學
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06F21/62
• 代理公司: 青島華慧澤專利代理事務所(普通合伙) 37247
• 代理人: 趙梅

本發明公開了基于本地化差分隱私的兩階段k?means聚類處理系統及方法，將隱私預算ε分成多份，用于多次迭代，在每次迭代時，包括兩個階段，每次迭代使用的隱私預算分配到兩個階段；第一階段基于隨機響應機制，建立滿足本地化差分隱私模型約束的用戶與中心點歸屬關系判定機制，第二階段基于拉普拉斯機制更新中心點，兩個階段都有效地避免了直接使用單個用戶的帶噪值完成聚類的構建，通過本發明解決k?means算法的每步迭代中用戶與中心點的歸屬關系判定以及中心點的更新過程中泄露用戶的敏感信息問題。

技術領域

本發明屬于數據聚類技術領域，涉及基于本地化差分隱私的k-means聚類算法，特別涉及基于本地化差分隱私的兩階段k-means聚類處理系統及方法。

背景技術

隨著信息時代的到來，數據已經應用在生活的方方面面，在人們享受數據給生活帶來便利的同時，數據中包含的隱私信息也越來越多，隱私泄露的風險也越來越嚴峻。如何在保護敏感信息的基礎上對數據進行使用，是當前面臨的重要挑戰。

聚類是一類有效的數據挖掘算法，是根據樣本的內在特征或相似性對樣本進行分組的一類方法。其中k-means是目前最流行和最簡單的聚類算法之一，k-means聚類算法的主要思想是：找到一種分類方法，使得每個聚類的中心點和聚類中的點之間的平方誤差最小。由于用戶數據可能包含敏感信息，所以在k-means算法的每步迭代中用戶與中心點的歸屬關系判定以及中心點的更新都會泄露用戶的敏感信息。

為了解決隱私泄露問題，現有的主流方法是使用差分隱私技術，其中差分隱私又可分為中心化差分隱私技術(Centralizer Differential Privacy,CDP)和本地化差分隱私技術(Local Differential Privacy,LDP)。很多學者基于CDP優化了k-means聚類算法，但是CDP是建立在可信第三方數據收集者的前提下的，由于這個前提過于苛刻，所以此類技術在實際部署中很少。基于LDP的k-means聚類算法便應運而生，LDP假設所有的第三方數據收集者都是不可信的，這保證了在面對強背景知識攻擊者以及不可信的第三方數據收集者的隱私攻擊時，LDP仍能為每一個客戶端用戶提供可靠的、具有理論保證的隱私保護服務。

現有的基于LDP的k-means算法的研究中，主要是將用戶的加噪數據直接發送給server端，有的方法是用戶每個點的距離向量擾動后發送給server端；有的方法是每個用戶將原始數據直接加噪后發送給server端，server端根據加噪的數據使用k-means進行處理。這種方案并非直接針對k-means的用戶屬于哪個簇和對應的中心點這兩個隱私信息進行隱私保護，而是著手于對用戶給出的原始數據進行擾動和加噪。對用戶的原始數據進行擾動之后，用戶原本的真實數據就無從得知了，將擾動的數據發送給聚類算法進行聚類，這樣也起到了一定的隱私保護作用。但是上述方案存在一定不足：在LDP模型下，針對每一個用戶位置加噪，加噪后的數據嚴重偏離真實值，單個帶噪數據沒有意義，只有基于大量帶噪數據計算的統計值是有意義的，該統計值可以用于作為真實統計值的估計。所以基于單個用戶的帶噪數據完成其與中心點歸屬關系的判定會得到無用的對用戶分組的結果。

鑒于此，本發明提出了一種基于LDP的兩階段k-means算法,分別應用滿足LDP的算法完成用戶與中心點歸屬關系的判定以及中心點的更新，解決了隱私泄露的問題。

發明內容

針對現有技術存在的不足，本發明提供一種基于本地化差分隱私的兩階段k-means聚類系統及方法，基于隨機響應機制，建立滿足本地化差分隱私模型約束的用戶與中心點歸屬關系判定機制；基于拉普拉斯機制，設計滿足本地化差分隱私模型約束的中心點更新方法，解決k-means算法的每步迭代中用戶與中心點的歸屬關系判定以及中心點的更新過程中泄露用戶的敏感信息問題。

為了解決上述技術問題，本發明采用的技術方案是：

基于本地化差分隱私的兩階段k-means聚類處理方法，將隱私預算ε分成多份，用于多次迭代，在每次迭代時，包括兩個階段，每次迭代使用的隱私預算分配到兩個階段；