面向本地差分隱私的K-Prototypes聚類方法

張國(guó)鵬，陳學(xué)斌*，王豪石，翟 冉，馬 征

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

0 引言

在網(wǎng)絡(luò)數(shù)字空間中，數(shù)據(jù)信息的安全與隱私是一個(gè)至關(guān)重要的問(wèn)題。數(shù)據(jù)作為可以進(jìn)行分配的生產(chǎn)要素，在保證數(shù)據(jù)公開(kāi)使用的前提下，用戶本人的自身利益不存在損害和泄露成為當(dāng)前關(guān)注熱點(diǎn)之一。2020 年發(fā)布《數(shù)據(jù)安全法（草案）》，明確規(guī)定任何組織、個(gè)人收集數(shù)據(jù)過(guò)程中必須采取合法正當(dāng)手段。大數(shù)據(jù)時(shí)代，信息技術(shù)使社會(huì)生活的產(chǎn)品和服務(wù)逐漸變?yōu)閿?shù)據(jù)形態(tài)，數(shù)據(jù)資源的應(yīng)用和使用正在逐漸滲透到各個(gè)行業(yè)領(lǐng)域，各方對(duì)隱私保護(hù)和數(shù)據(jù)安全使用問(wèn)題更加重視。2006 年Dwork［1］提出的差分隱私（Differential Privacy，DP）是一種新型的隱私保護(hù)機(jī)制，嚴(yán)格定義了數(shù)據(jù)隱私保護(hù)的強(qiáng)度，對(duì)于一個(gè)數(shù)據(jù)集增加或刪除任何一條記錄都不會(huì)影響到最后的查詢效果。相較于現(xiàn)有的隱私模型，例如K-anonymity、L-diversity、T-closeness 模型，需要特殊的攻擊假設(shè)和背景知識(shí)的方法，差分隱私因自身隱私強(qiáng)度和獨(dú)特優(yōu)勢(shì)受到當(dāng)前學(xué)術(shù)界研究者的廣泛關(guān)注。

聚類分析是數(shù)據(jù)挖掘的主要任務(wù)之一，在銀行、醫(yī)藥等多個(gè)領(lǐng)域被廣泛地應(yīng)用。聚類對(duì)無(wú)標(biāo)簽的數(shù)據(jù)進(jìn)行若干簇或類別的劃分，根據(jù)獲得數(shù)據(jù)的分布情況進(jìn)行頻率統(tǒng)計(jì)或均值求解。作為數(shù)據(jù)挖掘中一種聚類方法，K-Prototypes 算法［2］結(jié)合了K-means［3］和K-modes［4］聚類算法的核心，同樣是將數(shù)據(jù)點(diǎn)到聚類中心的距離劃分為K個(gè)聚類，使許多混合型數(shù)據(jù)得到了廣泛的應(yīng)用。這些數(shù)據(jù)為挖掘有用的信息提供了巨大的便利，但是也存在對(duì)隱私的威脅，因?yàn)檫@些數(shù)據(jù)通常包含個(gè)人的敏感信息，例如：攻擊者可以從醫(yī)療處方中推斷病人患的是哪種疾病，或者可以從用戶的軌跡數(shù)據(jù)推斷用戶在哪里生活或工作。因此在獲取高質(zhì)量數(shù)據(jù)分析的同時(shí)，保護(hù)用戶的隱私成為迫切需要。在聚類中引入差分隱私技術(shù)逐漸成為了研究熱點(diǎn)。研究者針對(duì)信任模糊的第三方收集者，在中心化差分隱私的基礎(chǔ)上細(xì)化了對(duì)個(gè)人隱私的保護(hù)，提出了本地化差分隱私（Local Differential Privacy，LDP）［5］。在不暴露任何用戶隱私的前提下，在聚類分析中引入本地差分隱私，這樣既保證了用戶的隱私又保障了聚類的可用性。

1 相關(guān)工作

本地差分隱私將對(duì)數(shù)據(jù)集的隱私處理過(guò)程從第三方服務(wù)器轉(zhuǎn)移至用戶個(gè)人，使得用戶個(gè)人對(duì)數(shù)據(jù)能夠獨(dú)立處理和保護(hù)自己的敏感信息。本地差分隱私的研究方向目前集中于擾動(dòng)機(jī)制的研究以及統(tǒng)計(jì)數(shù)據(jù)之后發(fā)布操作［6］，且已經(jīng)運(yùn)用到實(shí)際任務(wù)中，例如谷歌瀏覽器使用RAPPOR（Randomized Aggregatable Privacy-Preserving Ordinal Response）方法［7］對(duì)分類型數(shù)據(jù)進(jìn)行頻率估計(jì)。RAPPOR 采用隨機(jī)響應(yīng)技術(shù)［8］和Bloom Filter 技術(shù)保證了數(shù)據(jù)收集者無(wú)法窺探到用戶個(gè)人信息，對(duì)數(shù)據(jù)起到了隱私保護(hù)。Nguyên等［9］提出了對(duì)離散型數(shù)據(jù)的擾動(dòng)方法Harmony，他們將Harmony 運(yùn)用到隨機(jī)梯度下降中，對(duì)每次迭代的梯度進(jìn)行擾動(dòng)，并證明了在本地差分隱私下的小批量梯度下降優(yōu)于隨機(jī)梯度下降?；诰垲惙治鲞M(jìn)行隱私保護(hù)的研究中，Blum等［10］提出了一種差分隱私K-means 算法，可以有效防止隱私泄露；但由于增加了噪聲，使聚類結(jié)果的可用性降低。Ren等［11］提出了一種新的基于差分隱私的DPLK-means（Differential Privacy Laplace K-means）算法，它通過(guò)對(duì)原始數(shù)據(jù)集劃分的每個(gè)子集執(zhí)行差分隱私K-means 算法來(lái)改進(jìn)初始中心點(diǎn)的選擇，相較于文獻(xiàn)［10］算法提高了聚類結(jié)果的可用性。之后，越來(lái)越多的研究改進(jìn)了支持差分隱私的Kmeans 聚類算法［12-13］。Xia 等［14］提出了分布式場(chǎng)景下的第一個(gè)本地差分隱私下K-means 聚類算法，與中心化差分隱私下的K-means 算法有相似的聚類性能。彭春春等［15］提出了一種支持本地化差分隱私技術(shù)的K-modes 算法，很大程度上降低了第三方竊取用戶信息的可能性。Lv 等［16］提出基于中心化差分隱私的混合數(shù)據(jù)，目的是將K-means 和K-modes 算法結(jié)合處理混合型的數(shù)據(jù)集，進(jìn)行聚類分析。由于目前的數(shù)據(jù)不再是單一型的數(shù)值型或分類型，在實(shí)際應(yīng)用中，大量的數(shù)據(jù)集都是包含混合型的屬性；因此受到可信的第三方數(shù)據(jù)收集者的假設(shè)限制，本文提出了一個(gè)支持本地化差分隱私技術(shù)的隱私保護(hù)聚類方案LDPK-Prototypes（Local Differential Privacy K-Prototypes）。LDPK-Prototypes 使用隨機(jī)響應(yīng)機(jī)制來(lái)擾動(dòng)用戶數(shù)據(jù)，使用戶進(jìn)行數(shù)據(jù)的隱私處理，服務(wù)端則負(fù)責(zé)收集和恢復(fù)數(shù)據(jù)集進(jìn)行聚類，達(dá)到隱私保護(hù)目的的同時(shí)保證了聚類可用性。如圖1 所示，與中心化差分隱私相比，本地化差分隱私技術(shù)能對(duì)用戶的敏感信息實(shí)現(xiàn)更徹底的保護(hù)。

圖1 數(shù)據(jù)隱私處理框架Fig.1 Data privacy processing framework

2 理論基礎(chǔ)與定義

2.1 本地差分隱私

定義1LDP［5，17］。對(duì)于給定ε∈R+，給定n個(gè)用戶，每個(gè)用戶對(duì)應(yīng)一條記錄，隨機(jī)擾動(dòng)機(jī)制M，值域Range（M），當(dāng)且僅當(dāng)任意兩條記錄x、x'和輸出結(jié)果y(y?Range(M)) 滿足式（1），則M滿足ε-本地化差分隱私。

Range（M）表示經(jīng)過(guò)隨機(jī)擾動(dòng)機(jī)制后產(chǎn)生的所有數(shù)據(jù)集合；ε（隱私預(yù)算）越小，對(duì)于數(shù)據(jù)隱私保護(hù)程度越強(qiáng)，同時(shí)數(shù)據(jù)的實(shí)用效果越弱。

差分隱私的組合性可以進(jìn)行更優(yōu)的隱私預(yù)算分配，達(dá)到更好的隱私保護(hù)效果；同樣本地差分隱私也具有以下性質(zhì)。

性質(zhì)1 序列組合性［18］。假設(shè)給定數(shù)據(jù)集U，具有n個(gè)隨機(jī)響應(yīng)算法M，如Mi={M1，M2，…，Mn}，算法Mi滿足εi-本地差分隱私，則n個(gè)Mi（U）算法構(gòu)成的序列也滿足本地差分隱私。

性質(zhì)2 并行組合性［18］。假設(shè)給 定數(shù)據(jù) 集U={U1∪U2∪… ∪Un}，其中數(shù)據(jù)集Ui（1 ≤i≤n）和Uj（1 ≤j≤n，i≠j）是互不相交的子集，算法Mi滿足εi-本地差分隱私，則n個(gè)Mi（Ui）算法構(gòu)成的序列也滿足max｛εi｝-本地差分隱私。

2.2 K-Prototypes聚類算法

設(shè)一個(gè)數(shù)據(jù)集U={X1，X2，…，Xn}，一共有n個(gè)數(shù)據(jù)記錄，并且數(shù)據(jù)集中每個(gè)數(shù)據(jù)記錄有d個(gè)特征，即Xi={xi1，xi2，…，xip，xi(p+1)，…，xid}（1 ≤i≤n），xi1～xip表示數(shù)值型特征共有p個(gè)，xi（p+1）～xid表示分類型特征共有q（q=d-p）個(gè)。首先設(shè)聚類的個(gè)數(shù)為K，最開(kāi)始的簇中心集合為V={V1，V2，…，VK}，隨著不斷地重復(fù)迭代獲得的中間過(guò)程簇中心集合為O={O1，O2，…，OK}，距離公式如定義2 所示。

定義2樣本Xi到聚類中心樣本Vi的距離為：

其中：η是分類特征的權(quán)重，用來(lái)調(diào)節(jié)兩種不同類型數(shù)據(jù)對(duì)總體距離貢獻(xiàn)度的比重，從而避免聚類結(jié)果值偏向分類型特征或者數(shù)值型特征。

定義3數(shù)據(jù)集U在聚類過(guò)程中劃分類簇表示為集合O={O1，O2，…，OK}，其中K表示簇中心集的個(gè)數(shù)并且Oi∪Oj=?（1≤i，j≤K），即集合O是數(shù)據(jù)集U的一個(gè)聚類劃分，依此循環(huán)。

K-Prototypes 算法的目標(biāo)函數(shù)如下所示：

其中：?ij∈｛0，1｝，1 表示數(shù)據(jù)記錄Xi被聚類劃分至第j個(gè)類簇中心集；0 表示未劃分，每個(gè)數(shù)據(jù)記錄僅被劃分到一個(gè)類簇中心集。

2.3 優(yōu)化差分隱私聚類算法

Lv 等［16］提出了基于K-means 和K-modes 兩種算法相結(jié)合的中心化差分隱私，稱為ODPC（Optimizing and Differentially Private Clustering）算法，主要思想為：對(duì)于數(shù)值型的特征，采用拉普拉斯機(jī)制對(duì)中心加噪；對(duì)于分類型的特征，采用幾何機(jī)制對(duì)屬性的頻率加噪。添加噪聲的頻率上選擇質(zhì)心對(duì)應(yīng)的屬性值。引入真實(shí)的質(zhì)心和加噪后的質(zhì)心之間的損失函數(shù)來(lái)計(jì)算分配每次迭代過(guò)程的最小隱私預(yù)算，并由總的隱私預(yù)算和最小的隱私預(yù)算來(lái)確定迭代次數(shù)。

算法1 ODPC 算法。

Lv 等［16］提出的ODPC 算法是建立在可信第三方服務(wù)器基礎(chǔ)上進(jìn)行數(shù)據(jù)的統(tǒng)計(jì)和共享，但可信的第三方服務(wù)器在實(shí)際應(yīng)用中并不存在；由于初始聚類中心點(diǎn)是隨機(jī)選取的，可能會(huì)導(dǎo)致算法陷入局部最優(yōu)解，以及忽略了不同屬性對(duì)聚類結(jié)果的影響程度，導(dǎo)致運(yùn)行結(jié)果不穩(wěn)定。針對(duì)上述問(wèn)題，本文提出基于本地差分隱私的改進(jìn)的K-prototypes 聚類算法，即LDPK-Prototypes。

3 LDPK-Prototypes聚類算法

3.1 聚類算法的改進(jìn)

3.1.1 聚類中心的選取

基于K-Prototypes 聚類算法［19］的初始聚類中心是隨機(jī)選擇的，這種隨機(jī)性會(huì)導(dǎo)致算法陷入局部最優(yōu)，運(yùn)行結(jié)果不穩(wěn)定；因此結(jié)合文獻(xiàn)［20］中給出的相異性度量方法對(duì)初始聚類中心的選取進(jìn)行改進(jìn)，擾動(dòng)后的數(shù)據(jù)集U={X1，X2，…，Xn}，具體方法如下。

定義4用數(shù)據(jù)記錄的歐氏距離表示它們之間的相異度：

定義5構(gòu)造相異矩陣，記為Qdis。

定義6均值相異性是數(shù)據(jù)點(diǎn)Xi與數(shù)據(jù)集中每個(gè)數(shù)據(jù)記錄的距離平均值，記為Adis（Xi）。

其中：Adis（Xi）反映數(shù)據(jù)記錄Xi在整個(gè)數(shù)據(jù)集的位置情況，其值越大，說(shuō)明Xi周圍數(shù)據(jù)分布越稀疏且與其他數(shù)據(jù)記錄遠(yuǎn)離程度越高；反之越稠密。

定義7數(shù)據(jù)集的總體相異性定義如下：

數(shù)據(jù)集的總體相異性與全體數(shù)據(jù)的分布有關(guān)，體現(xiàn)了數(shù)據(jù)集的稀疏程度。

算法2 聚類中心選取。

步驟1 對(duì)數(shù)據(jù)集的屬性進(jìn)行預(yù)處理，防止數(shù)值之間差異過(guò)大，影響距離計(jì)算。

步驟2 根據(jù)式（4）～（7），分別計(jì)算相異度dis、構(gòu)造相異矩陣Qdis、均值相異度Adis（xi）和總體相異度Tdis。

步驟3 選取arg max［Adis（xi）］為第1 個(gè)初始聚類中心o1，接著從剩余的數(shù)據(jù)記錄中選取arg max［Adis（xi）］，計(jì)算與之前的聚類中心的相異度：若dis(xi，oj|j=1，2，…，K-1) ＞Tdis，則聚類中心加1；否則選取第2 大的均值相異度進(jìn)行計(jì)算，依次進(jìn)行選取。

步驟4 若選取聚類中心個(gè)數(shù)滿足要求，則聚類中心選取完畢，否則重復(fù)步驟3。

3.1.2 熵權(quán)法

K-prototypes 算法中數(shù)值型和分類型的權(quán)重η是人為地隨機(jī)指定，這樣對(duì)聚類的效果會(huì)造成影響；另外由于數(shù)值型特征和分類型特征的差異度計(jì)算存在缺陷，忽略了不同屬性對(duì)于聚類結(jié)果的影響程度，沒(méi)有全面地考慮兩種類型數(shù)據(jù)的結(jié)構(gòu)特點(diǎn)，造成分類型特征差異度權(quán)衡類內(nèi)總體對(duì)象的差異度?；谏鲜鰡?wèn)題，提出加入熵權(quán)法來(lái)衡量不同屬性的權(quán)重，從而提高算法的準(zhǔn)確率。具體步驟如下。

1）數(shù)據(jù)標(biāo)準(zhǔn)化且非負(fù)處理。

假設(shè)數(shù)據(jù)集共有k個(gè)屬性，U={X1，X2，…，Xn}，其中Xi={xi1，xi2，…，xij}（1 ≤i≤n，1 ≤j≤k），因此對(duì)各數(shù)據(jù)集屬性標(biāo)準(zhǔn)化后的值為yij，則：

2）計(jì)算各個(gè)屬性的信息熵：

3）確定各屬性的權(quán)重：

屬性的差異性大小和聚類過(guò)程中屬性的重要程度成正比，特征的熵值增大，則特征的差異性隨之增大，導(dǎo)致特征賦予的權(quán)重比例越高；反之亦然。

3.1.3 改進(jìn)的K-Prototypes算法

設(shè)一個(gè)數(shù)據(jù)集U={X1，X2，…，Xn}，共有n個(gè)數(shù)據(jù)記錄，xi1～xip表示數(shù)值型特征共有p個(gè)，xi（p+1）～xid表示分類型特征共有q（q=d-p）個(gè)。

定義8樣本Xi到聚類中心樣本Vi的新距離為：

相較于其他的K-Prototypes 算法，本文算法的聚類中心不再隨機(jī)選取，而是根據(jù)相異性度量的方法求解，避免了局部最優(yōu)情況，提高了聚類算法的準(zhǔn)確性和穩(wěn)定性?？紤]了不同屬性之間的差異性，利用熵權(quán)法對(duì)各個(gè)屬性進(jìn)行權(quán)重賦值，有效避免了不同屬性對(duì)聚類結(jié)果的影響。

算法3 改進(jìn)的K-Prototypes 算法。

輸入 類簇中心個(gè)數(shù)K，含有n個(gè)數(shù)據(jù)記錄的混合型數(shù)據(jù)集U；

輸出 劃分結(jié)果K個(gè)簇C={C1，C2，…，CK}。

步驟1 根據(jù)算法2 計(jì)算得出K個(gè)類簇中心集V={V1，V2，…，VK}。

步驟2 由式（10）得出數(shù)據(jù)集的屬性權(quán)重，將其代入新的距離公式（11）。

步驟3 然后根據(jù)式（11），計(jì)算剩余的n-K個(gè)數(shù)據(jù)記錄與類簇中心之間的d（Xi，Vj），根據(jù)所得的結(jié)果向最近的類簇中心聚類劃分。

步驟4 重新計(jì)算K個(gè)類簇集合的數(shù)值型和分類型簇中心。

步驟5 重復(fù)步驟3、4，直到K個(gè)簇類的簇中心不再變化，即損失函數(shù)E的結(jié)果值不再發(fā)生變化，將得到最終的聚類結(jié)果。

3.2 用戶端-服務(wù)端概況

3.2.1 用戶端操作

基于本地差分隱私的方法是對(duì)本地位置進(jìn)行保護(hù)，用戶需要執(zhí)行編碼和擾動(dòng)兩個(gè)步驟。假設(shè)數(shù)據(jù)集U={X1，X2，…，Xn}，一共有n個(gè)數(shù)據(jù)記錄，xi1～xip表示數(shù)值型特征共有p個(gè)，xi（p+1）～xid表示分類型特征共有q個(gè)。

1）編碼（Encode）。

①數(shù)值型特征。

對(duì)于Xi的p個(gè)數(shù)值型特征，需要將其轉(zhuǎn)換成0/1 字符串。其中xip轉(zhuǎn)換為Bip={b1，b2，…，bm}，m=|B|ip是字符串長(zhǎng)度，具體如下：

②分類型特征。

對(duì)于Xi的q個(gè)分類型特征，則首先利用LabelEncoder 標(biāo)簽編碼進(jìn)行轉(zhuǎn)化，將特征值置為相應(yīng)的序號(hào)xiq∈{1，2，…，k}，再按數(shù)值型特征方法進(jìn)行轉(zhuǎn)換。

2）擾動(dòng)（Perturb）。

根據(jù)上述編碼后的二進(jìn)制字符串，利用隨機(jī)響應(yīng)機(jī)制［8］實(shí)現(xiàn)本地差分隱私的每位比特位的擾動(dòng)，Bip擾動(dòng)后表示為，具體擾動(dòng)機(jī)制如下：

根據(jù)擾動(dòng)機(jī)制可以看到每個(gè)比特位擾動(dòng)為”1”或”0”的概率都是f/2，可以看出每位比特如何進(jìn)行擾動(dòng)，第三方收集者也無(wú)法知道確切真實(shí)值；因?yàn)橛脩舾嬖V服務(wù)端的真實(shí)值可能性很小，即1 -f，顯然f越大得到的隱私保護(hù)越強(qiáng)。經(jīng)過(guò)這種擾動(dòng)方式后每個(gè)比特位滿足ε-本地差分隱私［7］，其隱私預(yù)算為ε=ln

算法4 特征擾動(dòng)。

3.2.2 服務(wù)端操作

用戶數(shù)據(jù)集U={X1，X2，…，Xn}，其中含有d維屬性，表示數(shù)值型特征共有p個(gè)，分類型特征共有q(q=d-p)個(gè)。服務(wù)端目的在于根據(jù)用戶上傳數(shù)據(jù)信息后將用戶劃分為K個(gè)簇并返回最終的簇中心C={C1，C2，…，CK}及類簇集合；在用戶將數(shù)據(jù)上傳服務(wù)端時(shí)需提前進(jìn)行擾動(dòng)保護(hù)其自身隱私，服務(wù)端收集完之后要將擾動(dòng)后的特征信息盡量恢復(fù)至原始的信息，具體做法指將擾動(dòng)后的二進(jìn)制數(shù)據(jù)轉(zhuǎn)換為初始的整數(shù)，以便更好分析用戶聚類效果。具體的操作流程如圖2所示。

圖2 LDPK-Prototypes流程Fig.2 Flow chart of LDPK-Prototypes

3.2.3 聚類方案

本文提出LDPK-prototypes 聚類方案如圖3 所示。方案由用戶端和不可信的第三方服務(wù)器組成。用戶端負(fù)責(zé)用戶數(shù)據(jù)的隱私處理，即擾動(dòng)，相較于中心差分隱私，對(duì)于敏感數(shù)據(jù)的隱私處理在于用戶，有效地保護(hù)了用戶的個(gè)人隱私。服務(wù)器端則負(fù)責(zé)對(duì)擾動(dòng)數(shù)據(jù)的收集和恢復(fù)及聚類。用戶端采用3.2.1 節(jié)的方法將數(shù)值型和分類型的數(shù)據(jù)進(jìn)行隨機(jī)響應(yīng)方式擾動(dòng)處理，擾動(dòng)結(jié)束后將數(shù)據(jù)上傳至服務(wù)器端。不可信的服務(wù)器端則負(fù)責(zé)收集擾動(dòng)數(shù)據(jù)進(jìn)行數(shù)據(jù)的恢復(fù)和合成，最后在生成的數(shù)據(jù)集中選取適當(dāng)?shù)木垲愔行?，?.2.2 節(jié)的算法流程執(zhí)行K-prototypes 聚類算法，具體過(guò)程如算法2。

圖3 LDPK-prototypes聚類方案Fig.3 LDPK-prototypes clustering scheme

3.3 隱私分析

本節(jié)將從本地差分隱私的定理以及部分性質(zhì)對(duì)LDPKprototypes 算法的隱私進(jìn)行分析證明。

定理1每位比特經(jīng)過(guò)算法4 擾動(dòng)后，每個(gè)比特位滿足ε1-本地差分隱私，其中ε1=。

證明 根據(jù)用戶端編碼擾動(dòng)過(guò)程：

定理2當(dāng)每一位擾動(dòng)后的比特位滿足ε1-本地差分隱私，則每個(gè)用戶擾動(dòng)后的特征xid也滿足mε1-本地差分隱私，同時(shí)每個(gè)用戶記錄Xi也滿足本地差分隱私。

其中：

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

4.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)集

本文實(shí)驗(yàn)的硬件環(huán)境為：Intel Core i5-7200U CPU 2.50 GHz 處理器，內(nèi)存8 GB，操作系統(tǒng)為Windows 10 64 位，使用Python 語(yǔ)言進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)的數(shù)據(jù)集采用UCI 數(shù)據(jù)集中的Adult 數(shù)據(jù)集和Heart 數(shù)據(jù)集，Adult 數(shù)據(jù)集有48 842個(gè)數(shù)據(jù)記錄，是混合型數(shù)據(jù)集，考慮到空屬性的影響，最終共有30 161 個(gè)數(shù)據(jù)記錄，本文選擇4 個(gè)數(shù)字屬性和6 個(gè)分類屬性構(gòu)成數(shù)據(jù)記錄；同樣Heart 數(shù)據(jù)集共有918 個(gè)數(shù)據(jù)記錄，選擇4 個(gè)數(shù)值屬性和4 個(gè)分類屬性構(gòu)成數(shù)據(jù)記錄。不同數(shù)據(jù)集的特征如表1 所示。

表1 不同數(shù)據(jù)集的特征Tab.1 Characteristics of different dataset

4.2 實(shí)驗(yàn)評(píng)價(jià)標(biāo)準(zhǔn)

由于噪聲的引入，數(shù)據(jù)可用性的影響在隱私保護(hù)中尤為重要，通過(guò)采用F-measure 值（F）［21］可以很好地衡量加噪后的數(shù)據(jù)的可用性；與其他評(píng)價(jià)指標(biāo)相比，F(xiàn)-measure 值得到的結(jié)果更有針對(duì)性。F-measure 值結(jié)合了數(shù)據(jù)挖掘與信息檢索中準(zhǔn)確率（ACcuracy，AC）和召回率（REcall，RE），定義如下：

為了使召回率和準(zhǔn)確率獲得同等的權(quán)重，設(shè)置α=1。F-measure 值的范圍在［0，1］，如果得到F-measure 值越大則意味著聚類算法得到的結(jié)果可用性越高。

另外，采用規(guī)范化簇內(nèi)方差（Normalized Intra-Cluster Variance，NICV）［22］可以很好地衡量聚類效果。計(jì)算公式如下：

其中：n為數(shù)據(jù)集的大小，Ci是第i個(gè)簇心，x為每個(gè)類簇的數(shù)據(jù)記錄。NICV 值越大則聚類效果越差，反之說(shuō)明聚類效果越好。

最后，采用蘭德系數(shù)（Rand Index，RI），它是比較兩個(gè)聚類結(jié)果差異性的指標(biāo)，也可以比較一個(gè)聚類算法的結(jié)果和真實(shí)分類情況。本文用其衡量?jī)蓚€(gè)簇類的準(zhǔn)確率，其公式為：

其中：是所有可能的樣本對(duì)個(gè)數(shù)，a表示兩個(gè)簇類中的同類別的元素對(duì)數(shù)，b表示兩個(gè)簇類中的不同類別的元素對(duì)數(shù)。RI取值范圍為［0，1］，值越大意味著兩個(gè)簇的聚類結(jié)果越相似。

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

實(shí)驗(yàn)分別在Adult 數(shù)據(jù)集和Heart 數(shù)據(jù)集上運(yùn)行了未受任何隱私保護(hù)的聚類算法K-Prototypes 算法、EKPCA（Enhanced K-Prototypes mixed data Clustering Algorithm）［23］、ODPC 算法［16］以及本文提出的LDPK-Prototypes 算法。在數(shù)據(jù)集上運(yùn)行50 次未進(jìn)行隱私保護(hù)K-Prototypes 算法和EKPCA，取得聚類效果最好情況下的NICV 指標(biāo)作為評(píng)估的參照物，設(shè)置隱私預(yù)算ε為｛0.01，0.1，0.2，0.5，1，1.5，2｝，在相同ε值下，在數(shù)據(jù)集上分別運(yùn)行ODPC 算法和LDPKPrototypes 算法20 次后得到F-measure 和NICV 的平均值。

1）隱私預(yù)算ε對(duì)NICV 的影響。

如圖4 所示，改進(jìn)后的K-Prototypes 算法相較于EKPCA有著同等優(yōu)勢(shì)的聚類效果。由圖4（b）可看出，改進(jìn)的K-prototypes 算法相較于EKPCA 算法的聚類效果提高了28.61%。當(dāng)隱私預(yù)算ε較小時(shí)，LDPK-Prototypes 算法比ODPC 算法有更好的聚類效果，隨著隱私預(yù)算ε的增加，ODPC 算法的NICV 隨著ε值的增大曲線變化較明顯，而LDPK-Prototypes 算法則相對(duì)穩(wěn)定降低；這是由于LDPKPrototypes 算法對(duì)聚類中心的優(yōu)化選擇及屬性相異度增強(qiáng)了聚類的效果。

圖4 不同數(shù)據(jù)集上不同ε下的NICV值比較Fig.4 Comparison of NICV value under different ε values on different datasets

2）隱私預(yù)算ε對(duì)F-measure 值的影響。

如圖5 所示，當(dāng)隱私預(yù)算ε較小時(shí)，ODPC 算法比LDPKPrototypes 算法的聚類可用性高；這是因?yàn)楸疚奶岢龅乃惴ㄊ腔诓豢尚诺牡谌綌?shù)據(jù)處理，在隱私預(yù)算ε較小時(shí)，為了達(dá)到相似的隱私保護(hù)性需要加入更大的噪聲保護(hù)初始數(shù)據(jù)。隨著ε的增加，LDPK-Prototypes 算法的F也逐漸增加且高于ODPC 算法，因?yàn)殡[私保護(hù)程度降低同時(shí)添加的噪聲量也會(huì)降低，而本地差分隱私隨著隱私預(yù)算的增加可以以更高的概率將原始數(shù)據(jù)的信息保留，較小的概率擾動(dòng)為差別很大的數(shù)據(jù)信息，因此聚類可用性也得到提高。

圖5 不同數(shù)據(jù)集上不同ε值下F-measure值的比較Fig.5 Comparison of F-measure value under different ε values on different datasets

3）其他指標(biāo)分析。

由圖6 可以看出，隨著ε值的增大LDPK-Prototypes 算法的RI 值均高于其他算法，這表明本地化差分隱私技術(shù)加噪后的聚類效果優(yōu)于中心化差分隱私技術(shù)加噪后的聚類效果，主要原因是聚類中心點(diǎn)選取是根據(jù)數(shù)據(jù)記錄的差異度來(lái)確定聚類個(gè)數(shù)，有效地避免了局部最優(yōu)，提高了算法的穩(wěn)定性。由表2 可見(jiàn)，在不同數(shù)據(jù)集上LDPK-Prototypes 算法比ODPC算法平均準(zhǔn)確率分別提高了2.95%和12.41%。

表2 不同數(shù)據(jù)集上RI值的對(duì)比Tab.2 RI value comparison on different datasets

圖6 不同數(shù)據(jù)集上RI值與均值對(duì)比Fig.6 RI value and mean value comparison on different datasets

最后，在整個(gè)聚類過(guò)程中，本文提出的 LDPK-Prototypes算法對(duì)于原始數(shù)據(jù)的處理只能通過(guò)用戶自己，因此不需要擔(dān)心第三方數(shù)據(jù)收集者是否可信；這樣的隱私保護(hù)性較強(qiáng)，適用場(chǎng)景更廣，實(shí)用程度更高。

5 結(jié)語(yǔ)

本文提出了一種基于改進(jìn)的K-Prototypes 本地化差分隱私聚類方案。在聚類過(guò)程中，使用相異性度量方法確定初始聚類中心；利用熵權(quán)法重新定義距離計(jì)算公式，擴(kuò)大了數(shù)據(jù)之間差異性，提高了算法的準(zhǔn)確率和穩(wěn)定性。在不需要可信第三方的前提下，本文算法與ODPC 算法有著相似的聚類性能表現(xiàn)。在未來(lái)研究中擬用混合不同的隱私方法處理數(shù)據(jù)集，用LDP 保護(hù)用戶在其隱私要求級(jí)別內(nèi)的數(shù)據(jù)隱私，用中心化差分隱私（Central Difference Privacy，CDP）保護(hù)用戶隱私免受其他可能的對(duì)手的攻擊。