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

張國鵬，陳學斌*，王豪石，翟 冉，馬 征

（1.華北理工大學 理學院，河北 唐山 063210；2.河北省數據科學與應用重點實驗室（華北理工大學），河北 唐山 063210；3.唐山市數據科學重點實驗室（華北理工大學），河北 唐山 063210）

0 引言

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

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

1 相關工作

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

圖1 數據隱私處理框架Fig.1 Data privacy processing framework

2 理論基礎與定義

2.1 本地差分隱私

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

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

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

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

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

2.2 K-Prototypes聚類算法

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

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

其中：η是分類特征的權重，用來調節兩種不同類型數據對總體距離貢獻度的比重，從而避免聚類結果值偏向分類型特征或者數值型特征。

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

K-Prototypes 算法的目標函數如下所示：

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

2.3 優化差分隱私聚類算法

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

算法1 ODPC 算法。

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

3 LDPK-Prototypes聚類算法

3.1 聚類算法的改進

3.1.1 聚類中心的選取

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

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

定義5構造相異矩陣，記為Qdis。

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

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

定義7數據集的總體相異性定義如下：

數據集的總體相異性與全體數據的分布有關，體現了數據集的稀疏程度。

算法2 聚類中心選取。

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

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

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

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

3.1.2 熵權法

K-prototypes 算法中數值型和分類型的權重η是人為地隨機指定，這樣對聚類的效果會造成影響；另外由于數值型特征和分類型特征的差異度計算存在缺陷，忽略了不同屬性對于聚類結果的影響程度，沒有全面地考慮兩種類型數據的結構特點，造成分類型特征差異度權衡類內總體對象的差異度。基于上述問題，提出加入熵權法來衡量不同屬性的權重，從而提高算法的準確率。具體步驟如下。

1）數據標準化且非負處理。

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

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

3）確定各屬性的權重：

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

3.1.3 改進的K-Prototypes算法

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

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

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

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

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

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

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

步驟2 由式（10）得出數據集的屬性權重，將其代入新的距離公式（11）。

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

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

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

3.2 用戶端-服務端概況

3.2.1 用戶端操作

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

1）編碼（Encode）。

①數值型特征。

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

②分類型特征。

對于Xi的q個分類型特征，則首先利用LabelEncoder 標簽編碼進行轉化，將特征值置為相應的序號xiq∈{1，2，…，k}，再按數值型特征方法進行轉換。

2）擾動（Perturb）。

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

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

算法4 特征擾動。

3.2.2 服務端操作

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

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

3.2.3 聚類方案

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

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

3.3 隱私分析

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

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

證明 根據用戶端編碼擾動過程：

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

其中：

4 實驗與結果分析

4.1 實驗環境與數據集

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

表1 不同數據集的特征Tab.1 Characteristics of different dataset

4.2 實驗評價標準

由于噪聲的引入，數據可用性的影響在隱私保護中尤為重要，通過采用F-measure 值（F）［21］可以很好地衡量加噪后的數據的可用性；與其他評價指標相比，F-measure 值得到的結果更有針對性。F-measure 值結合了數據挖掘與信息檢索中準確率（ACcuracy，AC）和召回率（REcall，RE），定義如下：

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

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

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

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

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

4.3 實驗結果分析

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

1）隱私預算ε對NICV 的影響。

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

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

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

如圖5 所示，當隱私預算ε較小時，ODPC 算法比LDPKPrototypes 算法的聚類可用性高；這是因為本文提出的算法是基于不可信的第三方數據處理，在隱私預算ε較小時，為了達到相似的隱私保護性需要加入更大的噪聲保護初始數據。隨著ε的增加，LDPK-Prototypes 算法的F也逐漸增加且高于ODPC 算法，因為隱私保護程度降低同時添加的噪聲量也會降低，而本地差分隱私隨著隱私預算的增加可以以更高的概率將原始數據的信息保留，較小的概率擾動為差別很大的數據信息，因此聚類可用性也得到提高。

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

3）其他指標分析。

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

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

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

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

5 結語

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