面向混合型數(shù)據(jù)集自適應(yīng)聚類的差分隱私保護(hù)算法

張學(xué)典，周圣英

（上海理工大學(xué)光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093）

0 引言

大數(shù)據(jù)時(shí)代，數(shù)據(jù)處理方式不斷優(yōu)化，數(shù)據(jù)處理量迎來了井噴式增長(zhǎng)。越來越多的研究機(jī)構(gòu)投入到這些數(shù)字資源研究分析中，通過合理的數(shù)據(jù)挖掘分析方式，獲得高價(jià)值度的有效信息，從而支持各行各業(yè)緊密融合發(fā)展，推動(dòng)實(shí)現(xiàn)企業(yè)、政府部門等組織的管理決策高效化。然而在提供巨大潛在利益的同時(shí)，無差別地將個(gè)人數(shù)據(jù)暴露在公共視野中，將會(huì)對(duì)個(gè)人隱私安全造成相當(dāng)大的危害。因此，在合理使用用戶個(gè)人數(shù)據(jù)的同時(shí)應(yīng)該兼顧用戶隱私安全。但是，如何在保證大數(shù)據(jù)發(fā)布信息可用的同時(shí)又能做到保護(hù)隱私數(shù)據(jù)安全，已然是當(dāng)前數(shù)據(jù)發(fā)布隱私保護(hù)研究的熱點(diǎn)問題。

在數(shù)據(jù)發(fā)布中，敵手可以通過鏈接攻擊（敵手將獲取到的當(dāng)前發(fā)布的信息同通過其他渠道獲取到的外部相關(guān)信息進(jìn)行關(guān)聯(lián)對(duì)應(yīng)，從而推理出用戶隱私數(shù)據(jù)，這種攻擊手段能夠造成隱私泄露）獲取個(gè)體隱私數(shù)據(jù)。為了防范敵手通過鏈接攻擊造成隱私泄露問題，k-匿名及其擴(kuò)展模型被提出，k-匿名算法旨在通過概括及隱私隱匿技術(shù)，通過發(fā)布精度低的數(shù)據(jù)，達(dá)到保護(hù)隱私數(shù)據(jù)的目的，k-anonymity 要求發(fā)布信息中的每條記錄至少同其他（k-1）條待發(fā)布記錄具有完全相同的標(biāo)識(shí)符屬性，從而達(dá)到減少鏈接攻擊所導(dǎo)致的隱私泄露目的。雖然k-匿名隱私保護(hù)模型已被證明能夠保證以下3 點(diǎn)：①敵手無法知道某個(gè)用戶是否在公開數(shù)據(jù)集中；②給定一個(gè)用戶，敵手無法確認(rèn)該用戶是否有某項(xiàng)敏感信息；③敵手無法將數(shù)據(jù)與用戶一一對(duì)應(yīng)。但是，在面對(duì)敵手基于背景知識(shí)的攻擊時(shí)，即使原始數(shù)據(jù)集中的敏感屬性并不相同，敵手依然能夠通過多次比較已掌握的相關(guān)背景信息高概率地獲取隱私信息；若經(jīng)過k-匿名處理后得到的數(shù)據(jù)組內(nèi)對(duì)應(yīng)敏感屬性值相同，則更易遭受敵手發(fā)起的同質(zhì)化攻擊進(jìn)而造成隱私泄露。

2006 年，Dwork在處理統(tǒng)計(jì)數(shù)據(jù)庫的隱私泄露問題時(shí)提出差分隱私（Difference Privacy，DP）的概念：差分隱私保護(hù)模型是一種建立在嚴(yán)格數(shù)學(xué)證明基礎(chǔ)上的數(shù)學(xué)模型，對(duì)隱私泄露風(fēng)險(xiǎn)做定量的形式化證明。該模型假設(shè)敵手采用最大程度的背景知識(shí)攻擊，通過對(duì)需要進(jìn)行隱私保護(hù)的真實(shí)數(shù)據(jù)添加隨機(jī)擾動(dòng)因子以提供隱私保護(hù)，并保證這些經(jīng)過處理的數(shù)據(jù)仍具有較高可用性。這種方式較k-匿名隱私保護(hù)模型能夠提供更加安全的隱私保證。

使用傳統(tǒng)差分隱私保護(hù)模型時(shí)，會(huì)在原始數(shù)據(jù)集中添加大量噪聲，這將破壞數(shù)據(jù)可用性，繼而影響后續(xù)數(shù)據(jù)挖掘效果。研究指出，可以通過降低查詢敏感度、合理分配隱私預(yù)算提高差分隱私保護(hù)數(shù)據(jù)可用性。因此，如何設(shè)計(jì)合適的算法實(shí)現(xiàn)這一目標(biāo)將是本文考慮的主要問題。傳統(tǒng)差分隱私發(fā)布算法大多針對(duì)單一屬性數(shù)據(jù)，即數(shù)值型或分類型數(shù)據(jù)，而在實(shí)際應(yīng)用環(huán)境中，數(shù)據(jù)類型都是混合屬性（包含數(shù)值型及分類型數(shù)據(jù)），如醫(yī)療大數(shù)據(jù)、車輛信息大數(shù)據(jù)等。鑒于此，設(shè)計(jì)出滿足差分隱私要求的，同時(shí)保證處理后數(shù)據(jù)可用性的面向混合型數(shù)據(jù)集的差分隱私算法具有重要意義。

1 相關(guān)概念及定義

1.1 相關(guān)工作

傳統(tǒng)聚類算法是以某種方式對(duì)一組對(duì)象進(jìn)行分組，通過數(shù)據(jù)屬性間的差異度對(duì)數(shù)據(jù)集進(jìn)行分組處理，可以實(shí)現(xiàn)將單一個(gè)體泛化到整組數(shù)據(jù)中以降低查詢敏感度。在這種情況下，對(duì)于待差分隱私保護(hù)處理數(shù)據(jù)，能夠有效降低差分隱私噪聲量，從而提高數(shù)據(jù)可用性。

本文分析現(xiàn)有差分隱私保護(hù)算法優(yōu)缺點(diǎn)，結(jié)合混合型數(shù)據(jù)集保護(hù)要求，通過改進(jìn)k-prototype算法及快速聚類算法，提出一種適用于混合型數(shù)據(jù)集差分隱私保護(hù)的方法。雖然傳統(tǒng)的k-prototype算法能夠?qū)旌闲蛿?shù)據(jù)集進(jìn)行有效聚類，但由于沒有固定的初始聚類中心選取方法，在一般情況下均采用隨機(jī)方法確定聚類中心，會(huì)導(dǎo)致最終聚類效果穩(wěn)定性差，進(jìn)而影響差分隱私噪聲添加，降低數(shù)據(jù)可用性。而快速聚類算法通過樣本距離及密度衡量樣本間連接的緊密程度，但傳統(tǒng)快速聚類往往對(duì)數(shù)值型數(shù)據(jù)集采用“決策圖”方法判定聚類中心，混合型數(shù)據(jù)集相較于數(shù)值型數(shù)據(jù)集更為復(fù)雜，不可采用一般方法。結(jié)合上述傳統(tǒng)混合型數(shù)據(jù)聚類方法所存在的問題，本文提出了一種基于密度和距離自適應(yīng)選擇初始聚類中心的差分隱私保護(hù)算法。通過計(jì)算混合型數(shù)據(jù)集中各樣本點(diǎn)的鄰域密度和相對(duì)距離（相異度），劃分出k個(gè)密度大且相對(duì)距離較遠(yuǎn)的樣本點(diǎn)作為初始聚類中心，完成聚類；對(duì)生成的聚類結(jié)果，計(jì)算得到其數(shù)值型聚類中心，同時(shí)生成分類型數(shù)據(jù)的屬性值集合；然后判斷每一條記錄的聚類類別，將其數(shù)值型屬性替換為聚類中心并使用Laplace 方法添加噪聲，對(duì)分類型屬性采用指數(shù)機(jī)制選擇輸出，從而得到經(jīng)過差分隱私保護(hù)的結(jié)果。本文所提出算法的評(píng)價(jià)指標(biāo)主要有3 項(xiàng)：數(shù)據(jù)誤差率、規(guī)范化簇內(nèi)方差及制定隱私預(yù)算下的隱私保護(hù)程度。

1.2 差分隱私基本定義

傳統(tǒng)隱私保護(hù)技術(shù)在面對(duì)攻擊者結(jié)合相關(guān)背景知識(shí)進(jìn)行攻擊時(shí)，存在較大安全隱患，而差分隱私保護(hù)通過嚴(yán)格的數(shù)學(xué)方法克服了這一缺陷。該過程是通過向真實(shí)數(shù)據(jù)集添加隨機(jī)擾動(dòng)因素而實(shí)現(xiàn)，此外要求保證數(shù)據(jù)在添加干擾因素后仍然具有較高的可用性，以確保在任一經(jīng)過差分隱私保護(hù)處理的數(shù)據(jù)集中進(jìn)行查詢操作而不影響結(jié)果，進(jìn)而實(shí)現(xiàn)隱私保護(hù)。

定義1

（

ε

-差分隱私）設(shè)有隨機(jī)查詢算法

M

，以及任意兩相鄰數(shù)據(jù)集

D

和

D

（有且僅有一條記錄相異），若算法

M

對(duì)

D

和

D

的任意輸出

S

?

Ran

ge(

M

)滿足：

則稱算法

M

能夠?yàn)閿?shù)據(jù)集提供

ε

-差分隱私保護(hù)，參數(shù)

ε

稱為隱私保護(hù)預(yù)算，算法

M

的隱私保護(hù)強(qiáng)度可以通過

ε

進(jìn)行衡量，

ε

越小隱私保護(hù)程度越高；反之

ε

越大，則表明隱私保護(hù)程度越低。

定義2

（全局敏感度）設(shè)有一個(gè)查詢函數(shù)

f

:

D

→

D

，對(duì)于參與其中的任意兩相鄰數(shù)據(jù)集

D

和

D

，函數(shù)

f

的全局敏感度定義為：

函數(shù)

f

是在兩個(gè)數(shù)據(jù)集上分別執(zhí)行，其中

||f

(

D

)-

f

(

D

)

||

表示向量元素絕對(duì)值之和，即1-階范數(shù)距離。

差分隱私保護(hù)主要通過向原數(shù)據(jù)集添加擾動(dòng)噪聲而實(shí)現(xiàn)，而在實(shí)際應(yīng)用中，常見的噪聲添加機(jī)制主要有Laplace 機(jī)制和指數(shù)機(jī)制。其中，Laplace 機(jī)制針對(duì)數(shù)值型數(shù)據(jù)進(jìn)行隨機(jī)擾動(dòng)處理，添加的擾動(dòng)因子符合正態(tài)分布，而指數(shù)機(jī)制則主要處理非數(shù)值型數(shù)據(jù)的擾動(dòng)。全局敏感度和差分隱私預(yù)算共同影響噪聲機(jī)制。

定理1

（Laplace 機(jī)制）對(duì)于已有數(shù)據(jù)集

D

，設(shè)有一查詢函數(shù)

f

:

D

→

D′

，其全局敏感度為

Δf

，如果算法K 滿足：

則算法

K

提供

ε

-差分隱私保護(hù)。

定理2

（指數(shù)機(jī)制）對(duì)于任意一個(gè)給定的可用性函數(shù)

μ

(

D

,

r

) →

R

，若存在算法

M

滿足：

除上述基本性質(zhì)及定理外，差分隱私還存在以下組合性質(zhì)，這些性質(zhì)能夠保證將差分隱私保護(hù)運(yùn)用到反復(fù)迭代過程中，結(jié)果始終滿足差分隱私。同時(shí)，以下性質(zhì)也是實(shí)現(xiàn)合理分配差分隱私預(yù)算的基礎(chǔ)。

定義4

（并行組合性）同樣在給定數(shù)據(jù)集

D

上，若存在隨機(jī)算法

A

，能夠提供

ε

-差分隱私保護(hù)，則將數(shù)據(jù)集

D

劃分為互不相交的子集{

D

,

D

,…,

D

}，則算法

A

在{

D

,

D

,…,

D

}上的并行操作所構(gòu)成的算法也提供

ε

-差分隱私保護(hù)。

2 面向混合型數(shù)據(jù)集的差分隱私保護(hù)算法

2.1 樣本相異度及鄰域密度計(jì)算

混合型數(shù)據(jù)集包含數(shù)值型屬性及分類型屬性，因此對(duì)于不同數(shù)據(jù)類型需要采用不同的差異性度量方法。本文對(duì)數(shù)值型數(shù)據(jù)采用閔可夫斯基距離計(jì)算方法，對(duì)于給定的表示為

x

=(

x

,

x

,…,

x

)∈

R

和

x

=(

x

,

x

,…,

x

)∈

R

的樣本，其中

n

表示維度，則樣本間距離可定義為：

其中，

p

是閔可夫斯基距離的階，本文取

p

=1，即樣本間距離公式為：

而對(duì)于分類型屬性不能采用常規(guī)的距離計(jì)算方法，故本文采用簡(jiǎn)單匹配距離衡量分類型數(shù)據(jù)的相異度，簡(jiǎn)單匹配距離越大則表示樣本間相異性越高。對(duì)于給定的表示為

x

=(

x

,

x

,…,

x

)∈

R

和

x

=(

x

,

x

,…,

x

)∈

R

的樣本，其中

n

表示維度，對(duì)于

x

和

x

的某一分類型屬性

x

和

x

，定義函數(shù)：

樣本間的簡(jiǎn)單匹配距離為：

綜上所述，對(duì)于一個(gè)混合型數(shù)據(jù)集

X

={

x

,

x

,…,

x

}，每個(gè)樣本

x

(

i

=1,2,…,

n

)都有

p

個(gè)屬性，以

a

,

a

,…,

a

,

a

,…,

a

表示屬性，其中

a

,

a

,…,

a

為數(shù)值型，

a

,…,

a

為分類型。隨機(jī)選擇初始聚類中心

C

={

c

,

c

,…,

c

}，則樣本與聚類中心的相異度為：

其中，

γ

為分類型屬性對(duì)于相異度判斷影響所設(shè)權(quán)重。

由傳統(tǒng)k-prototype 定義可知，對(duì)于簇中樣本需要確定代價(jià)損失函數(shù)確定各變量與聚類中心的距離，定義如下：

其中，

U

是維度為

n

×

k

取值為{0,1}的關(guān)聯(lián)度矩陣，有：

即表示

x

是否屬于第

j

個(gè)簇，若屬于則

U

=1，否則為0。而在執(zhí)行聚類迭代過程中，聚類中心可能會(huì)不斷發(fā)生變化，因此對(duì)于聚類中心的第

q

個(gè)數(shù)值型屬性

c

有：

同理，對(duì)于聚類中心的第

q

個(gè)分類型屬性

c

，則取數(shù)據(jù)集所有樣本中，按關(guān)聯(lián)度加權(quán)后，值頻率最高的值，即隸屬于該簇的所有樣本第

q

個(gè)分類型屬性出現(xiàn)頻率最高的值：

數(shù)據(jù)集

X

={

x

,

x

,…,

x

}中任意兩個(gè)樣本

x

、

x

間的平均距離定義為：

數(shù)據(jù)集

X

={

x

,

x

,…,

x

}中任意樣本的鄰域密度

ρ

為：

其中，

e

(

x

,

x

,

ρ

)為核密度函數(shù)，其定義為：

2.2 基于密度和距離自適應(yīng)的聚類中心選擇

綜上所述，對(duì)于混合型數(shù)據(jù)集聚類流程描述如下：

Step1：對(duì)于初始混合型數(shù)據(jù)集的每一條樣本計(jì)算其鄰域密度

ρ

；Step2：通過遍歷按密度降序排列

C

={

C

,

C

,…,

C

}，定義集合

M

，將排序后鄰域密度最大的樣本

C

加入到集合

M

中；Step3：繼續(xù)迭代

C

，若集合

C

中存在滿足對(duì)于任意

M

∈

M

都有

dist

(

C

,

M

)>

L

，則將

C

添加到集合

M

中，直至迭代完集合

C

中的所有元素，則集合

M

中所有元素即為初始聚類中心，此時(shí)簇?cái)?shù)為|M|；Step4：根據(jù)相異度公式計(jì)算原始數(shù)據(jù)集中的每一個(gè)樣本

x

與|M|個(gè)聚類中心的

dist

(

x

,

c

)，將

x

劃分到

Min

(

dist

(

x

,

c

))的簇中；

Step5：計(jì)算樣本與聚類中心間的關(guān)聯(lián)度矩陣；

Step6：重新計(jì)算每個(gè)簇的聚類中心（數(shù)值型屬性按照式（12）計(jì)算，分類型屬性按照式（13）計(jì)算）；

Step7：根據(jù)計(jì)算出來的聚類中心，判斷原簇中數(shù)據(jù)是否發(fā)生變化，若無變化，聚類結(jié)束，得到聚類后的數(shù)據(jù)集，否則返回Step3；

Step8：判斷是否達(dá)到最大迭代次數(shù)，若達(dá)到結(jié)束聚類，否則依舊返回Step3。

2.3 聚類結(jié)果差分隱私保護(hù)

對(duì)經(jīng)過聚類操作的數(shù)據(jù)集進(jìn)行添加噪聲處理，采用Laplace 機(jī)制對(duì)聚類中心的數(shù)值型屬性添加噪聲，即：

而對(duì)于聚類中心的分類型屬性，使用Laplace 機(jī)制添加噪聲沒有意義，由于分類型屬性的構(gòu)成是從有限集中選取，因此通過差分隱私的指數(shù)機(jī)制，以一定概率選擇輸出，故根據(jù)式（4）可得：

完整算法描述如下：

Input

：混合型數(shù)據(jù)集

X

，數(shù)據(jù)維度d，迭代次數(shù)t，初始聚類中心點(diǎn)集M，隱私預(yù)算

ε

，聚類簇?cái)?shù)目

n

，數(shù)值型屬性數(shù)目

p

，分類型屬性數(shù)目

d

-

p

3 實(shí)驗(yàn)分析

3.1 數(shù)據(jù)集處理

實(shí)驗(yàn)中所需的混合型數(shù)據(jù)集選用在隱私保護(hù)領(lǐng)域廣泛應(yīng)用的UCI（University of California）Machine Learning Reposity中的Adult數(shù)據(jù)集，在處理其無效內(nèi)容及空屬性記錄后，共有30 162條備用記錄。本文在考慮數(shù)據(jù)集本身所具有的異構(gòu)屬性類型數(shù)據(jù)后，選擇其中8項(xiàng)作為評(píng)估數(shù)據(jù)集進(jìn)行處理，包括數(shù)值型屬性：age、hours-per-week 和分類型屬性：workclass、education、occupation、race、sex、native-country。

差分隱私對(duì)于混合型數(shù)據(jù)集的數(shù)據(jù)可用性是通過聚類中心替換簇內(nèi)樣本記錄并添加對(duì)應(yīng)噪聲所產(chǎn)生的信息缺失加以定量。而信息缺失可以通過樣本與聚類中心的距離進(jìn)行量化，即通過式（10）的誤差平方和加以衡量。

在保證數(shù)據(jù)可用性的同時(shí)，需要對(duì)差分隱私保護(hù)前本文算法對(duì)于數(shù)據(jù)集的聚類性能進(jìn)行評(píng)估，考慮使用規(guī)范化簇內(nèi)方差（

N

ormalized Intracluster Variance，NICV）衡量，但是傳統(tǒng)計(jì)算方法只針對(duì)數(shù)值型數(shù)據(jù)集有效，而對(duì)于混合型數(shù)據(jù)集聚類后的簇內(nèi)方差計(jì)算需要進(jìn)行合理推廣，其計(jì)算公式如下：

其中，

C

是簇的聚類中心，

x

(

a

)表示樣本

x

的數(shù)值型屬性值，

N

為簇內(nèi)樣本總量，

p

表示樣本數(shù)值型屬性個(gè)數(shù)，

q

表示樣本分類型屬性個(gè)數(shù)，Pr(

x

(

a

))表示選中

x

(

a

)的概率。

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

實(shí)驗(yàn)過程中，將數(shù)據(jù)集分別在本文提出算法與傳統(tǒng)DPk-means算法以及MDAV算法上運(yùn)行。傳統(tǒng)DPkmeans算法在處理混合型數(shù)據(jù)集時(shí)沒有任何分類操作，對(duì)每一條記錄的每一項(xiàng)屬性不加區(qū)分地進(jìn)行差分隱私保護(hù)處理；MDAV算法通過微聚類方式再結(jié)合差分隱私保護(hù)進(jìn)行數(shù)據(jù)發(fā)布。

對(duì)Adult 數(shù)據(jù)集作預(yù)處理，將其分類型屬性取值歸一化處理到{0,1}上，將隱私保護(hù)預(yù)算

ε

的值從0 提高到1.0。圖1 展示了在數(shù)據(jù)集上執(zhí)行3 種算法得到的數(shù)據(jù)誤差率，圖2則是NICV 值的比較，圖3 是在固定隱私保護(hù)預(yù)算

ε

下，通過調(diào)節(jié)簇個(gè)數(shù)探究本文算法對(duì)于隱私信息的保護(hù)程度。

Fig.1 Data error rate of data set under different algorithms圖1 數(shù)據(jù)集在不同算法下的數(shù)據(jù)誤差率

Fig.2 Comparison of NICV values圖2 NICV 值比較

Fig.3 Privacy protection degree of the proposed algorithm when ε= 0.4圖3 ε= 0.4 時(shí)本文算法隱私保護(hù)程度

如圖1 所示，在相同

ε

下，本文提出的差分隱私發(fā)布算法具有更低的誤差，且隨著

ε

增加，誤差保持相對(duì)穩(wěn)定。因此，經(jīng)過本文差分隱私發(fā)布算法處理的數(shù)據(jù)更接近原始數(shù)據(jù)，在數(shù)據(jù)挖掘中具有實(shí)際應(yīng)用價(jià)值。由圖2 可以明顯看出，本文提出的發(fā)布算法在NICV 值上明顯小于其他兩種算法，并且隨著

ε

的變化趨于穩(wěn)定，說明本文算法的聚類效果在處理混合型數(shù)據(jù)集時(shí)具有明顯優(yōu)勢(shì)。從圖3 可以看出，隨著發(fā)布數(shù)據(jù)初始聚類簇?cái)?shù)的增加，原數(shù)據(jù)集的隱私保護(hù)效果逐漸提升，然而在實(shí)際實(shí)驗(yàn)中，隨著簇?cái)?shù)增加，算法運(yùn)行時(shí)間明顯變長(zhǎng)。這是因?yàn)榇財(cái)?shù)增加，聚類中心的選擇變多，需要向更多簇添加不同的差分隱私保護(hù)，從而增加了運(yùn)行時(shí)間。在未來研究中，將著重降低簇?cái)?shù)提升算法時(shí)間復(fù)雜度。

4 結(jié)語

本文提出的面向混合型數(shù)據(jù)集的自適應(yīng)聚類差分隱私保護(hù)算法，通過結(jié)合快速聚類算法、k-prototype 聚類算法的特性，能夠基于密度和距離，自適應(yīng)確定初始聚類中心，對(duì)于分類型屬性和數(shù)值型屬性進(jìn)行差別處理，使其滿足聚類要求，反復(fù)迭代完成混合型數(shù)據(jù)集的自適應(yīng)聚類，再向聚類后的簇中心加入對(duì)應(yīng)擾動(dòng)因子以滿足差分隱私要求；在實(shí)現(xiàn)聚類高效處理的同時(shí)又能不過度降低數(shù)據(jù)有效性，從而達(dá)到保護(hù)隱私數(shù)據(jù)的目的。在此基礎(chǔ)上，通過探究在實(shí)驗(yàn)數(shù)據(jù)集下初始簇個(gè)數(shù)變化，尋找數(shù)據(jù)可用性和隱私披露之間的平衡點(diǎn)，證明確實(shí)適用于混合數(shù)據(jù)集的差分隱私保護(hù)。