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

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

0 引言

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

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

1 相關(guān)工作

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

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

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

2.1 本地差分隱私

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

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

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

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

2.2 K-Prototypes聚類算法

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

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

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

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

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

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

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

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

算法1 ODPC 算法。

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

3 LDPK-Prototypes聚類算法

3.1 聚類算法的改進

3.1.1 聚類中心的選取

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

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

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

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

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

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

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

算法2 聚類中心選取。

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

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

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

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

3.1.2 熵權(quán)法

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

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

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

2）計算各個屬性的信息熵：

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

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

3.1.3 改進的K-Prototypes算法

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

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

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

算法3 改進的K-Prototypes 算法。

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

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

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

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

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

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

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

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

3.2.1 用戶端操作

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

1）編碼（Encode）。

①數(shù)值型特征。

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

②分類型特征。

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

2）擾動（Perturb）。

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

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

算法4 特征擾動。

3.2.2 服務(wù)端操作

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

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

3.2.3 聚類方案

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

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

3.3 隱私分析

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

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

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

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

其中：

4 實驗與結(jié)果分析

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

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

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

4.2 實驗評價標(biāo)準(zhǔn)

由于噪聲的引入，數(shù)據(jù)可用性的影響在隱私保護中尤為重要，通過采用F-measure 值（F）［21］可以很好地衡量加噪后的數(shù)據(jù)的可用性；與其他評價指標(biāo)相比，F(xiàn)-measure 值得到的結(jié)果更有針對性。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］可以很好地衡量聚類效果。計算公式如下：

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

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

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

4.3 實驗結(jié)果分析

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

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

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

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

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

如圖5 所示，當(dāng)隱私預(yù)算ε較小時，ODPC 算法比LDPKPrototypes 算法的聚類可用性高；這是因為本文提出的算法是基于不可信的第三方數(shù)據(jù)處理，在隱私預(yù)算ε較小時，為了達到相似的隱私保護性需要加入更大的噪聲保護初始數(shù)據(jù)。隨著ε的增加，LDPK-Prototypes 算法的F也逐漸增加且高于ODPC 算法，因為隱私保護程度降低同時添加的噪聲量也會降低，而本地差分隱私隨著隱私預(yù)算的增加可以以更高的概率將原始數(shù)據(jù)的信息保留，較小的概率擾動為差別很大的數(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ù)加噪后的聚類效果，主要原因是聚類中心點選取是根據(jù)數(shù)據(jù)記錄的差異度來確定聚類個數(shù)，有效地避免了局部最優(yōu)，提高了算法的穩(wěn)定性。由表2 可見，在不同數(shù)據(jù)集上LDPK-Prototypes 算法比ODPC算法平均準(zhǔn)確率分別提高了2.95%和12.41%。

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

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

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

5 結(jié)語

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