張國興 趙俊杰 楊 杰

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

1 概述

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

圖1 患病人數(shù)統(tǒng)計直方圖

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

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

2 背景知識

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

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

3 融合K-means 與指數(shù)機制的直方圖發(fā)布算法

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

3.1 算法介紹

3.2 算法描述

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

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

4 隱私性分析

5 可用性分析

5.1 評價標準

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

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

5.2 實驗環(huán)境

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

5.3 實驗分析

實驗采用Java 語言實現(xiàn)IKEM、AHP 和IHP 算法。

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

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

圖2 socialnetwork 數(shù)據(jù)集下算法對比結果

6 結論

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