融合K- means 與指數機制的直方圖發布算法

張國興 趙俊杰 楊 杰

(中南民族大學計算機科學學院,湖北 武漢 430074)

1 概述

直方圖是一種常用的統計學工具,其通過桶計數來表達數據的統計特征。直方圖在數據共享、數據發布領域有著廣泛的應用。企業可以將用戶數據采集,匯總成為直方圖發布給第三方進行數據挖掘,從而獲取數據中有價值的信息。在數據發布的過程中,攻擊者通過獲取足夠多的背景知識,可以結合直方圖推斷出用戶信息,導致用戶的隱私信息泄露。例如,圖1 是某疾控中心發布的患病人數統計直方圖。若攻擊者已知Bob 存在于該直方圖中,并且掌握了除Bob 以外的其他患者所有信息,攻擊者可以通過查詢對比Bob 加入之前與之后的直方圖變化信息,從而推斷出Bob 所患的疾病。

圖1 患病人數統計直方圖

因此,為了保護數據的隱私。Dwork[1]等人提出了一種新型的隱私保護方案-差分隱私。差分隱私[1]作為一種較為流行的隱私保護技術,是一種嚴謹的數學模型,能夠為隱私保護提供可以量化的保證。其被廣泛應用于直方圖數據發布領域。但差分隱私存在一個明顯的缺點：在對數據進行隱私保護時,會使得數據的可用性下降。因此,如何在對直方圖進行隱私保護的同時,盡可能的保證數據的可用性,是該領域的研究重點。

本文主要貢獻如下：(1) 提出了一種融合K-means 與指數機制的直方圖發布算法 (Histogram publishing algorithm integrating K -means and Exponential mechanism;IKEM)。算法首先利用指數機制結合輪盤賭抽樣選取聚類中心點,使各中心點在數據中分布盡量離散；然后利用選取好的中心點對直方圖進行全局聚類分組；最后對分組添加噪聲并發布。(2)理論分析了IKEM 滿足ε-差分隱私。(3)通過實驗分析,表明了該算法在滿足隱私性的同時,可用性優于同類算法AHP[2]和IHP[3]。

2 背景知識

差分隱私要求相鄰數據庫中無論一條記錄是否在數據庫中,對算法的輸出結果都不會產生顯著的影響。

定義1 差分隱私定義[1]。對于相鄰數據集D1與D2,range(M)表示隨機算法M 的所有輸出的集合。Q 為range(M)的子集,若算法M 滿足：

3 融合K-means 與指數機制的直方圖發布算法

本文采用k-means 算法對直方圖數據進行分組聚類,但初始中心點的選取直接決定了分組的效果,若K個初始中心點屬于同一個簇,則會降低分組的準確性,因此要求聚類中心點選取盡量離散。

3.1 算法介紹

3.2 算法描述

本節對IKEM 算法描述包括：聚類中心點選取算法CPSA、k-means 聚類分組、分組求均值和添加拉普拉斯噪聲,具體過程描述如下：

由(4)式結合全局敏感度的定義可知,打分函數在相鄰數據集的直方圖上的的最大變化范圍為1,因此△u=1將(4)式代入(3)式中可以看出,待抽取的桶與已有各中心點間的最短距離越大,適應度函數值就越大,得到的抽樣概率也越大。

4 隱私性分析

5 可用性分析

5.1 評價標準

實驗主要采用均方誤差(MSE)作為算法可用性評估標準度量,表達式如下：

MSE 表示在查詢范圍Q 內,算法在原始直方圖與加噪直方圖之間產生的絕對誤差平方和的均值。實驗中,在相同的查詢范圍和隱私預算下,MSE 越小,發布直方圖數據可用性越高。

5.2 實驗環境

本文進行實驗的顯卡為AMD Ryzen 5 3600-6-Core Processor 3.60GHz；16G 內存；實驗平臺為windows10 系統；實驗所采用的方法為IKEM 算法、AHP 算法和IHP算法；通過對比實驗結果來對算法進行分析。實驗所用的數據集來自直方圖發布研究常用數據集socialnetwork；socialnetwork 包含了一個在線網站的65536 條人際關系的記錄。

5.3 實驗分析

實驗采用Java 語言實現IKEM、AHP 和IHP 算法。

分別以三種算法對上述socialnetwork 數據集處理30次,隱私預算分別取ln2、1 和1.5,最后取其平均值為最終處理結果,查詢范圍100～1000。實驗結果如圖2 所示。

從圖2 中的實驗結果中可以得出結論：三種算法的MSE 隨著隱私預算 的增大而減小,對應的隱私保護程度也隨之降低。固定查詢范圍和隱私預算可以看出,IHP算法利用層次劃分原理對直方圖進行分組劃分,在離散數值過多的數據集上,其劃分精度較低,查詢誤差也較大；AHP 算法由于是對添加噪聲之后的中間直方圖進行排序,其排序過程引入了額外的噪聲,導致查詢誤差較大,從而降低了數據的可用性；本文的IKEM 算法首先利用聚類中心點選取算法進行聚類中心點的選取,使中心點在數據中的分布盡量離散；然后對數據進行聚類劃分；最后對分組劃分添加噪聲,通過合理選取中心點提升了分組的準確性,進而提升了發布數據的可用性。

圖2 socialnetwork 數據集下算法對比結果

6 結論

針對直方圖數據發布中存在的數據可用性較差問題,本文提出了一種融合K-means 與指數機制的直方圖發布算法。該算法利用最短距離結合指數機制對抽樣出直方圖的聚類中心點,使聚類中心點在直方圖數據中的分布盡量離散,在保證數據隱私性的前提下,有效降低了分組誤差精度,提升了數據的可用性。下一步工作考慮算法優化,并將算法應用在動態數據流直方圖發布領域的研究。