面向差分隱私的BIRCH算法研究

王豪石，張淑芬，董燕靈，李帥

（1.華北理工大學(xué)理學(xué)院，河北唐山 063210；2.河北省數(shù)據(jù)科學(xué)與應(yīng)用重點(diǎn)實(shí)驗(yàn)室，河北唐山 063210；3.唐山市數(shù)據(jù)科學(xué)重點(diǎn)實(shí)驗(yàn)室，河北唐山 063210）

0 引言

大數(shù)據(jù)時(shí)代，數(shù)據(jù)信息呈爆炸式增長(zhǎng)，這些數(shù)據(jù)包含了生活的方方面面，例如，瀏覽器瀏覽的歷史數(shù)據(jù)、用戶瀏覽淘寶和京東等電商網(wǎng)站數(shù)據(jù)、手機(jī)客戶端上的登錄數(shù)據(jù)和使用數(shù)據(jù)、用戶的社交網(wǎng)站數(shù)據(jù)等。這些數(shù)據(jù)直接或者間接地涉及了用戶隱私信息，使得很多企業(yè)可以利用數(shù)據(jù)挖掘技術(shù)挖掘出用戶的喜好和生活習(xí)慣，以獲得巨大的利益。對(duì)于用戶而言，這可能會(huì)造成個(gè)人隱私泄露。如果這些數(shù)據(jù)被一些不法之人惡意利用，可能會(huì)給用戶帶來(lái)難以預(yù)料的人身傷害和財(cái)產(chǎn)安全。此外，用戶的一些不正規(guī)操作也可能導(dǎo)致用戶信息泄露。因此，如何保護(hù)用戶隱私成為當(dāng)前亟待解決的問(wèn)題。

隨著數(shù)據(jù)泄露事件頻發(fā)，隱私保護(hù)技術(shù)越來(lái)越受到學(xué)術(shù)界的重視。目前，已有針對(duì)敏感數(shù)據(jù)的隱私保護(hù)方法可分為：數(shù)據(jù)失真、抑制發(fā)布及數(shù)據(jù)加密。其中，數(shù)據(jù)失真是通過(guò)加入擾動(dòng)實(shí)現(xiàn)隱私保護(hù)；抑制發(fā)布是根據(jù)真實(shí)情況對(duì)數(shù)據(jù)進(jìn)行有條件的發(fā)布；數(shù)據(jù)加密是采用加密技術(shù)對(duì)數(shù)據(jù)集中的敏感數(shù)據(jù)進(jìn)行加密處理。在數(shù)據(jù)挖掘中，聚類分析是根據(jù)研究對(duì)象的特征進(jìn)行分類，但在其聚類分析中經(jīng)常會(huì)出現(xiàn)隱私泄露問(wèn)題，如何保護(hù)數(shù)據(jù)隱私安全逐漸成為研究的焦點(diǎn)。對(duì)此，彭春春等針對(duì)數(shù)據(jù)可用性與隱私保護(hù)性，利用本地化差分隱私方法在本地進(jìn)入隨機(jī)擾亂，之后在K-modes算法的初始中心點(diǎn)上將出現(xiàn)次數(shù)最多的數(shù)據(jù)作為初始中心點(diǎn)，提出支持本地化差分隱私保護(hù)的K_modes聚類方法；蔡英等使用針對(duì)混合型數(shù)據(jù)，利用Laplace機(jī)制對(duì)數(shù)值型添加噪聲，用指數(shù)機(jī)制對(duì)分類型數(shù)據(jù)加噪，提出基于K-prototype聚類的差分隱私混合數(shù)據(jù)發(fā)布算法；傅彥銘等對(duì)K-means++算法在選取初始化中心點(diǎn)和迭代中心點(diǎn)中存在的隱私泄露問(wèn)題，提出一種基于拉普拉斯機(jī)制的差分隱私保護(hù)K-means++聚類算法研究。

在BIRCH算法構(gòu)建聚類特征樹(shù)時(shí)存在聚類特征隱私泄露現(xiàn)象，故本文提出面向差分隱私的BIRCH算法。在BIRCH算法構(gòu)造聚類特征樹(shù)的聚類特征SS與LS中添加拉普拉斯噪聲，以實(shí)現(xiàn)保護(hù)聚類特征的隱私安全。實(shí)驗(yàn)結(jié)果表明，本文提出的DPBIRCH算法能在保證聚類結(jié)果準(zhǔn)確性的情況下，添加不同的隨機(jī)噪聲，實(shí)現(xiàn)不同級(jí)別的數(shù)據(jù)隱私保護(hù)效果。

1 相關(guān)技術(shù)

1.1 差分隱私

定義1

差分隱私。假設(shè)隨機(jī)算法

B

滿足

ε

-差分隱私保護(hù)，則對(duì)任意相鄰的兩個(gè)集合

D

和

D

以及

P

的任意子集

S

，滿足如下條件：

其中，

ε

是使用者的指定常數(shù)，Pr(.)為概率密度函數(shù)，

D

和

D

為兩個(gè)只差一條數(shù)據(jù)的相鄰數(shù)據(jù)集，

P

是

B

所有的輸出集合。從數(shù)學(xué)的角度看，只要參數(shù)

ε

足夠小，攻擊者是很難從相差為1的數(shù)據(jù)集

D

和

D

中經(jīng)過(guò)分析發(fā)現(xiàn)用戶的一些真實(shí)信息。

定義2

全局敏感度。Δ

f

是查詢函數(shù)

f

的敏感度，定義為：

其中，D和D是具有相同結(jié)構(gòu)的數(shù)據(jù)集，且至多相差一個(gè)元素。

由定義3可知，差分隱私下的拉普拉斯噪聲由敏感度Δ

q

與隱私預(yù)算參數(shù)

ε

決定。Δ

q

越大，添加的噪聲越大，Δ

q

越小，添加的噪聲越小，添加噪聲的值跟Δ

q

成正比；反觀

ε

值的情況，

ε

越大添加的噪聲越小，

ε

越小添加的噪聲越大，添加噪聲的值與

ε

的值成反比。從不同參數(shù)的拉普拉斯的噪聲分布圖（見(jiàn)圖1）可以看出其與

ε

的值成反比。

Fig.1 Laplace noise mechanism圖1 拉普拉斯噪聲機(jī)制

1.2 層次聚類

聚類是根據(jù)數(shù)據(jù)特征將一個(gè)數(shù)據(jù)集劃分為不同的子集或者簇的過(guò)程，聚類算法包括基于劃分的聚類、基于層次的聚類、基于密度的聚類。BIRCH算法（Balanced Iterative Reducingand Clustering Using Hierarchies）是常見(jiàn)的層次聚類算法之一，主要思想是用三元組表示一個(gè)簇點(diǎn)的相關(guān)信息。其算法基本流程為：①遍歷數(shù)據(jù)集，根據(jù)初始化的閾值，建立起初始聚類特征樹(shù)；②修改閾值，將滿足新閾值條件的簇構(gòu)造成一棵新樹(shù)，并判斷所有節(jié)點(diǎn)是否滿足修改后的閾值，對(duì)大于閾值條件的進(jìn)行分裂，并根據(jù)就近原則加入所屬的特征樹(shù)中。重復(fù)步驟②，直到一棵完整的樹(shù)凝聚完成。

2 面向差分隱私保護(hù)的BIRCH算法

2.1 BIRCH算法

BIRCH算法利用聚類特征樹(shù)（Clustering Feature Tree，簡(jiǎn)稱CFTree）實(shí)現(xiàn)聚類，其聚類特征樹(shù)類似于平衡B+樹(shù)。

聚類特征（

Clustering

Feature

，CF）是一個(gè)包括簇信息的三元組（N，LS，SS），其中N代表樣本點(diǎn)的個(gè)數(shù)；LS代表所有樣本點(diǎn)的線性和，SS代表所有樣本點(diǎn)的平方和。

可加性定理表明，每個(gè)父節(jié)點(diǎn)的三元組的值是其所有子節(jié)點(diǎn)三元組值之和，這一性質(zhì)使得在更新CF Tree時(shí)算法效率更加高效。

2.2 DPBIRCH算法

本文針對(duì)在構(gòu)造CF Tree中存在的CF隱私泄露現(xiàn)象，提出了面向差分隱私的BIRCH算法（DPBIRC算法）。在BIRCH算法構(gòu)造CF Tree的CF中的LS與SS中加入拉普拉斯噪聲，最終達(dá)到保護(hù)CF的隱私信息和數(shù)據(jù)的作用。在DPBIRCH聚類算法流程中最關(guān)鍵的步驟是在建立聚類特征樹(shù)中加入拉普拉斯噪聲，其噪聲添加過(guò)程如下：

步驟1：新數(shù)據(jù)添加后，檢查CF所對(duì)應(yīng)的球體半徑閾值，當(dāng)閾值小于T，則更新路徑上所有CF的三元組，并且在LS與SS中添加拉普拉斯噪聲，到此，插入結(jié)束，轉(zhuǎn)入步驟3；

步驟2：當(dāng)前葉子節(jié)點(diǎn)上CF的個(gè)數(shù)小于葉子節(jié)點(diǎn)最大CF的個(gè)數(shù)，這時(shí)創(chuàng)建一個(gè)新的CF，放入新數(shù)據(jù)，將新的CF節(jié)點(diǎn)放入這個(gè)葉子節(jié)點(diǎn)，更新路徑上所有的CF三元組，并在LS與SS中添加拉普拉斯噪聲，此時(shí)，插入結(jié)束。

DPBIRCH算法流程具體如下。

算法1：DPBIRCH算法

上述算法中，枝平衡因子B是指父節(jié)點(diǎn)中子節(jié)點(diǎn)的最大數(shù)目；葉平衡因子L是指葉子節(jié)點(diǎn)中CF的最大數(shù)目；閾值T是指葉子節(jié)點(diǎn)子聚類的最大直徑。

2.3 隱私性分析

在拉普拉斯機(jī)制中，如果算法中的隨機(jī)函數(shù)能夠滿足拉普拉斯的分布噪聲，就能夠?qū)崿F(xiàn)對(duì)數(shù)據(jù)的隱私保護(hù)。DPBIRCH通過(guò)在BIRCH算法中的聚類特征SS與LS添加噪聲，實(shí)現(xiàn)差分隱私保護(hù)。本文設(shè)定兩個(gè)拉普拉斯機(jī)制函數(shù)，其隱私預(yù)算都為

ε

，其中一個(gè)對(duì)SS添加噪聲，另一個(gè)對(duì)LS添加噪聲。

證明：算法1中的第8、13與9、14滿足差分隱私。

假設(shè)

D

和

D

是任意相鄰數(shù)據(jù)集，

B

是加噪算法，LS加噪后為L(zhǎng)S，根據(jù)拉普拉斯機(jī)制：

同理可證SS的加噪過(guò)程為：

根據(jù)差分隱私的并行組合原理，在每次更新的聚類特征SS中加噪消耗隱私預(yù)算的值等于總的隱私預(yù)算

ε

，LS中加噪消耗隱私預(yù)算的值等于總的隱私預(yù)算

ε

；根據(jù)差分隱私的串行組合原理，DPBIRCH算法消耗總的隱私預(yù)算為2

ε

。

2.4 DPBIRCH算法評(píng)價(jià)指標(biāo)

面向差分隱私的BIRCH算法可以從兩個(gè)指標(biāo)進(jìn)行分析，分別為差分隱私保護(hù)強(qiáng)度和聚類的準(zhǔn)確性。

（1）差分隱私保護(hù)強(qiáng)度。差分隱私下的保護(hù)強(qiáng)度受隱私保護(hù)預(yù)算參數(shù)

ε

的影響，當(dāng)隱私保護(hù)預(yù)算參數(shù)

ε

的值越小，添加的拉普拉斯噪聲就越大，差分隱私保護(hù)強(qiáng)度越高；反之，當(dāng)隱私保護(hù)的預(yù)算參數(shù)

ε

值越大，添加的拉普拉斯噪聲就越小，差分隱私保護(hù)強(qiáng)度越低。

（2）聚類準(zhǔn)確性。RI指標(biāo)（Rand Index），簡(jiǎn)稱蘭德系數(shù)，是一種用排列組合的方式對(duì)聚類進(jìn)行評(píng)價(jià)，用于比較各聚類算法的準(zhǔn)確性。本文將其用于比較添加噪聲后數(shù)據(jù)聚類結(jié)果與原始數(shù)據(jù)聚類結(jié)果的相似度，如式（4）所示。

ARI指標(biāo)（Adjusted Rand Index）簡(jiǎn)稱調(diào)整蘭德指數(shù)。ARI解決了RI不能很好地描述隨機(jī)分配簇標(biāo)記向量相似度的問(wèn)題。ARI的定義如式（5）所示。

其中，

E

表示期望，max表示最大值。

ARI

的范圍為［-1，1］，

ARI

的值越大表示不同簇之間的相似度越高，ARI的值接近于0表示隨機(jī)分配簇，

ARI

的值為負(fù)數(shù)表示預(yù)測(cè)的簇向量非常差。本文算法通過(guò)設(shè)置不同的隱私預(yù)算參數(shù)

ε

，比較原始的數(shù)據(jù)聚類結(jié)果與添加拉普拉斯噪聲后的數(shù)據(jù)聚類結(jié)果，計(jì)算出ARI指標(biāo)與RI指標(biāo)的值，從而在保證聚類準(zhǔn)確性的同時(shí)實(shí)現(xiàn)數(shù)據(jù)隱私保護(hù)。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)設(shè)計(jì)

本文實(shí)驗(yàn)采用Python語(yǔ)言實(shí)現(xiàn)面向差分隱私的BIRCH算法。實(shí)驗(yàn)平臺(tái)內(nèi)存為16GB，操作系統(tǒng)為Win10系 統(tǒng)，CPU為Intel core i5-9300H 2.40GHz，顯卡為GTX16504G GDDR5，Python語(yǔ)言的版本為3.8.3，開(kāi)發(fā)工具為Pycharm 2020.2.3，實(shí)驗(yàn)所用的數(shù)據(jù)集是從UCI數(shù)據(jù)集上下載的MAGICGamma Telescope數(shù)據(jù)集（MAGIC伽瑪望遠(yuǎn)鏡數(shù)據(jù)集）。其實(shí)驗(yàn)數(shù)據(jù)集基本信息如表1所示。

Table1 Basic information of experimental data set表1 實(shí)驗(yàn)數(shù)據(jù)集基本信息

為了驗(yàn)證DPBIRCH算法的隱私保護(hù)性，本文實(shí)驗(yàn)在不同隱私保護(hù)預(yù)算參數(shù)的值與簇值情況下，通過(guò)比較原始數(shù)據(jù)聚類結(jié)果與添加拉普拉斯噪聲后的數(shù)據(jù)聚類結(jié)果，計(jì)算出RI指標(biāo)與ARI指標(biāo)的值，并觀察RI指標(biāo)與ARI指標(biāo)值的變化情況。

具體操作如下：首先，設(shè)置不同的簇值，通過(guò)添加相同的拉普拉斯噪聲觀察原始數(shù)據(jù)聚類結(jié)果與添加拉普拉斯噪聲后數(shù)據(jù)聚類結(jié)果的RI指標(biāo)和ARI指標(biāo)值變化情況；其次，設(shè)置簇值相同時(shí)，通過(guò)添加不同的拉普拉斯噪聲觀察原始數(shù)據(jù)聚類結(jié)果與添加拉普拉斯噪聲后數(shù)據(jù)聚類結(jié)果的RI指標(biāo)與ARI指標(biāo)值變化情況。其中，隱私保護(hù)預(yù)算參數(shù)

ε

的取值分別為0.01、0.05、0.1、0.2、0.4、0.8，簇的取值分別為2、3、4、5，交替進(jìn)行對(duì)比實(shí)驗(yàn)，并觀察取10次聚類結(jié)果平均值后的RI指標(biāo)與ARI指標(biāo)值變化情況。由于對(duì)數(shù)據(jù)集作了歸一化處理，且范圍為［0，1］區(qū)間，故根據(jù)敏感度的定義可知Δ

q

的值為1。

3.2 實(shí)驗(yàn)結(jié)果與分析

針對(duì)在UCI數(shù)據(jù)集上的MAGICGamma Telescope數(shù)據(jù)集，使用本文面向差分隱私的BIRCH算法對(duì)該數(shù)據(jù)集在進(jìn)行BIRCH算法時(shí)設(shè)置不同簇值以及不同隱私保護(hù)預(yù)算參數(shù)

ε

的值進(jìn)行對(duì)比實(shí)驗(yàn)，觀察原始數(shù)據(jù)聚類結(jié)果與添加拉普拉斯噪聲后數(shù)據(jù)聚類結(jié)果的RI指標(biāo)與ARI指標(biāo)值的情況，并統(tǒng)計(jì)與分析所得的RI指標(biāo)和ARI指標(biāo)值變化情況。取10次聚類結(jié)果平均值后的RI指標(biāo)與ARI指標(biāo)值的情況如表2、表3所示。

Table2 MAGIC Gamma Telescope RIindica tor values on the dataset表2 MAGIC Gamma Telescope數(shù)據(jù)集上的RI指標(biāo)值情況

Table 3 MAGIC Gamma Telescope ARI index values on the dataset表3 MAGIC Gamma Telescope數(shù)據(jù)集上的ARI指標(biāo)值的情況

表2、圖2為在MAGICGamma Telescope數(shù)據(jù)集上隱私保護(hù)預(yù)算參數(shù)

ε

的值和簇值對(duì)應(yīng)的RI指標(biāo)值變化情況；表3、圖3為在MAGICGamma Telescope數(shù)據(jù)集上隱私保護(hù)預(yù)算參數(shù)

ε

的值和簇值對(duì)應(yīng)的ARI指標(biāo)值變化情況。從圖2、圖3可以看出，整體上RI指標(biāo)與ARI指標(biāo)的值都隨著隱私保護(hù)參數(shù)預(yù)算

ε

值的增大而增大。其中，在比較原始的數(shù)據(jù)聚類結(jié)果與添加拉普拉斯噪聲后的數(shù)據(jù)結(jié)果而計(jì)算出的RI指標(biāo)與ARI指標(biāo)的情況看，當(dāng)簇值為2的情況下得到AI指標(biāo)與ARI指標(biāo)的值最大，且聚類效果最佳。其對(duì)應(yīng)RI指標(biāo)的值為0.864 01、0.926 10、0.937 67、0.939 64、0.959 44、0.964 08；ARI指標(biāo)的值為0.639 37、0.813 22、0.844 05、0.847 63、0.901 89、0.914 38。根據(jù)實(shí)驗(yàn)結(jié)果分析可知，在MAGICGamma Telescope數(shù)據(jù)集中添加不同的拉普拉斯噪聲，會(huì)對(duì)數(shù)據(jù)產(chǎn)生不同的隱私保護(hù)級(jí)別。總體上，當(dāng)差分隱私的隱私保護(hù)預(yù)算參數(shù)

ε

值越大，RI指標(biāo)與ARI指標(biāo)受到的影響越小，數(shù)據(jù)隱私的保護(hù)級(jí)別越小，可用性就越大，聚類所得到的RI指標(biāo)與ARI指標(biāo)的值越接近1；相反，當(dāng)差分隱私的隱私保護(hù)預(yù)算參數(shù)

ε

值越小，RI指標(biāo)與ARI指標(biāo)受到的影響就越大，數(shù)據(jù)隱私的保護(hù)級(jí)別越大，可用性就越小，聚類所得到的RI指標(biāo)與ARI指標(biāo)的值也越小。在確保聚類準(zhǔn)確性的前提下，為實(shí)現(xiàn)對(duì)數(shù)據(jù)的隱私保護(hù)，本文在利用DPBIRCH算法時(shí)，對(duì)于

ε

的取值有一定要求，

ε

的取值不能太小，否則影響到數(shù)據(jù)集的可用性與聚類的準(zhǔn)確性；同時(shí)

ε

的取值也不能太大，否則會(huì)起不到保護(hù)數(shù)據(jù)隱私的作用。由本文實(shí)驗(yàn)可知，在MAGIC Gamma Telescope 數(shù)據(jù)集上，當(dāng)

ε

的值等于0.2 時(shí)，RI 與ARI 指標(biāo)同

ε

小于0.2 時(shí)相比增長(zhǎng)明顯；且大于0.2時(shí)，RI 指標(biāo)與ARI 指標(biāo)同

ε

等于0.2 時(shí)增長(zhǎng)緩慢。故

ε

的值大于等于0.2 時(shí)，聚類結(jié)果的準(zhǔn)確率相比

ε

小于0.2 時(shí)提高明顯，同時(shí)也保護(hù)了數(shù)據(jù)隱私安全。

Fig.2 Relationship between RI index and differential privacy budget parameter ε value on MAGIC Gamma Telescope dataset圖2 MAGIC Gamma Telescope數(shù)據(jù)集上的RI指標(biāo)與差分隱私預(yù)算參數(shù)ε值之間的關(guān)系

Fig.3 Relationship between ARI index and differential privacy budget parameter ε value on MAGIC Gamma Telescope dataset圖3 MAGIC Gamma Telescope數(shù)據(jù)集上的ARI指標(biāo)與差分隱私預(yù)算參數(shù)ε值之間的關(guān)系

4 結(jié)語(yǔ)

基于傳統(tǒng)的BIRCH 算法在進(jìn)行聚類構(gòu)建CF Tree 時(shí)會(huì)存在CF 隱私泄露現(xiàn)象，為了保護(hù)BIRCH 算法中CF 的隱私安全，本文提出了面向差分隱私的BIRCH 算法，通過(guò)設(shè)置不同的隱私預(yù)算參數(shù)，對(duì)構(gòu)建聚類特征樹(shù)的聚類特征LS與SS 中添加噪聲，以驗(yàn)證不同隱私預(yù)算參數(shù)下聚類結(jié)果的準(zhǔn)確性與可用性。下一步將研究如何更加高效準(zhǔn)確地對(duì)數(shù)據(jù)添加噪聲，以及差分隱私保護(hù)在其他機(jī)器學(xué)習(xí)算法中的適用性。