基于k-prototype聚類的差分隱私混合數據發布算法

屈晶晶，蔡 英，范艷芳，夏紅科

北京信息科技大學計算機學院，北京100101

大數據時代，數據的發布和利用是推動知識、經濟和社會進步的關鍵。相關研究機構會利用這些數據資源，進行挖掘分析，從而為大眾提供更好的服務。然而在提供巨大利益的同時，向公眾發布個人數據將對用戶的隱私構成相當大的威脅。為了確保用戶隱私安全，需要對其進行保護。但是，如何保證所發布的數據既是可用的，又不會泄露數據中所包含的隱私信息，成為數據發布隱私保護研究的重難點。

k-anonymity[1]及其擴展的系列算法是保護用戶隱私信息的重要方式。k-anonymity 旨在使每個記錄與至少k-1 個其他記錄無法區分。k-anonymity 側重于處理準標識符屬性（例如，年齡、性別、郵政編碼和民族），因為它們可鏈接到外部可識別的數據源中的類似屬性。雖然k-anonymity 已被證明可提供相當有用的匿名結果，但是在攻擊者可能獲得其他背景知識的前提下，對于小k，它很容易受到缺乏非匿名機密屬性的多樣性攻擊。已提出對k-anonymity 模型的若干改進，包括l-diversity[2]和t-closeness[3]，可以防止這種情況發生。

差分隱私模型[4]作為一種眾所周知的隱私保護模型，可以在不對攻擊者的背景知識做任何假設的前提情況下，通過向數據查詢或者分析結果中添加一定量的噪聲進行對數據的擾動從而提供隱私保證。通過這種方式，發布的數據不會影響任何個人的隱私，因此差分隱私提供了比k-anonymity 模型更加強大的隱私保證。

差分隱私數據發布分為交互式框架和非交互式框架。在非交互式框架下，一般通過兩種形式生成差分隱私數據集：一種是數據管理者針對用戶可能提出的所有查詢請求計算查詢結果，然后執行差分隱私保護算法進行一次性發布，該結果與采用kanonymity 模型技術發布的通用數據集相比，無法提供數據分析需要的更多數據細節；另一種是發布一個經過差分隱私處理的通用數據集，用戶可對處理過的數據集進行任意的查詢操作，該方法需要在發布的數據集中加入大量噪聲，可能會破壞數據可用性。研究表明，可以通過降低查詢敏感度、合理分配隱私預算來提高差分隱私保護數據發布的可用性[5]。

因此，在發布差分隱私通用數據集的過程中，如何設計合適的算法降低查詢敏感度，減少噪聲誤差，提升數據可用性將會是本文重點考慮的問題。除此之外，目前提出的差分隱私通用數據集發布方法大都針對處理單一屬性類型[6-8]，例如只對數值型屬性或者分類型屬性進行數據發布，對于混合型數據發布的研究相對較少。然而，在實際應用中，很多數據集都是包含混合屬性，如醫療數據、人口普查數據等。因此，研究針對混合數據集的差分隱私數據發布方法對滿足實際應用需求具有重要意義。

1 相關工作和預備知識

1.1 相關工作

差分隱私最初被用于限制在數據庫上返回查詢答案時產生的披露風險，但是這種交互式場景下的應用嚴格限制了數據分析，因為它只允許回答有限數量的查詢，從而促進了非交互式場景下數據發布的隱私保護研究。

在非交互式場景下，發布滿足差分隱私數據集的主要方法是基于直方圖發布[9-12]。然而，當屬性數量增加時，基于直方圖的方法具有嚴重的局限性：對于固定屬性粒度，直方圖區間的數量隨著屬性的數量呈指數增長，這對計算成本和準確性都有嚴重影響。除此之外，直方圖發布方法僅是提供了分區數據的近似計數而無法提供數據細節，因此限制了數據分析效用。因此可以通過生成滿足差分隱私的通用數據集來克服此限制。最簡單的方法是收集一組滿足差分隱私的查詢結果，該組查詢要求查詢原始數據集中的每個單獨記錄。但是，為此類查詢獲得滿足差分隱私所需的噪聲量太大，以至于差分隱私數據集無法保持可用性。可以通過降低查詢敏感度、減少噪聲添加量來提高差分隱私保護數據發布的可用性。

聚類算法在依據屬性差異度對數據進行分組預處理后，可以實現函數查詢敏感度由單一個體數據到組數據的分化，通過降低查詢敏感度可降低滿足差分隱私所需的噪聲量，從而提升數據可用性。

Li 等人[13]構建了一種新模型，即將k-anonymity算法與差分隱私保護相結合，并將該隱私保護模型應用于微數據的發布。趙興旺等人[14]提出了一種基于差分隱私保護k-means 聚類隱私保護方法，即區分所選中心點與設定點之間的隱私，但該方法的聚類可用性不僅依賴于隱私保護預算，還取決于數據集大小。Soria 等人[15-18]提出了一種非交互式方法，該方法使用微聚集和k-anonymity 模型將記錄分組到至少k個記錄中的簇中，以降低查詢函數靈敏度和添加到已發布數據集的噪聲量。文獻[15]指出，對于大小為n的數據集，至少需要k＞。文獻[16]設計了混合屬性數據集分組時需要的特殊微聚集算法，然后將k個微聚集數據集作為輸入，進行差分隱私保護。文獻[17]通過執行單個排名微聚合來解決前兩個文獻存在的問題，可以實現k≥2，但是只能處理包含單個屬性的數據集。文獻[18]針對不同應用場景，選擇出最佳差分隱私數據發布方案。文獻[19]研究了兩類交叉矩陣微聚集算法，分別為矩陣系數形式和頻譜分解形式。然后結合質心和其他統計信息代替簇中的原始記錄。劉曉遷等人[20]提出了一種基于DBSCAN（density-based spatial clustering of applications with noise）聚類的差分隱私數據發布方法，但該方法僅適用于數值屬性數據集。王紅等人[21]提出一種基于OPTICS（ordering points to identify the cluster structure）聚類的差分隱私保護算法，但該方法同樣只適用于數值屬性數據集。

因此，本文提出了一種數據發布算法，可以對混合屬性數據集進行差分隱私保護。k-prototype 聚類算法是處理混合數據類型的典型聚類分析算法。因此，本文針對k-prototype 算法改進了對數據集中數值屬性和分類屬性的差異度計算公式，能夠更好地對混合數值屬性和分類屬性數據進行聚類；除此之外，該算法通過聚類分組，可以降低差分隱私的敏感性從而減少所需添加的噪聲量，因此可以在提供隱私保護的同時提高數據可用性。

1.2 差分隱私保護

1.2.1 差分隱私定義

差分隱私保護技術通過向查詢結果中添加定量噪聲實現對數據的擾動，以確保在任一數據集中插入、更改、刪除記錄的操作不會影響查詢結果，進而達到隱私保護的目的。

定義1（ε-差分隱私[22]）設有隨機算法K，以及任何相鄰數據集D1和D2。若算法K滿足ε-差分隱私，則有：

其中，參數ε是隱私預算。算法K的隱私保護等級可以通過ε推導出來。ε越小，則表明隱私保護程度越高；反之，ε越大，則表明隱私保護程度越低。

1.2.2 噪音機制

實際應用中，常用的噪音機制包括Laplace機制[22]與指數機制[23]。噪聲量會影響數據安全性和可用性，與全局敏感度[13]密切相關。

定義2（全局敏感度[22]） 存在任意一個函數f:D→Rd，f的全局敏感度定義為：

其中，D1和D2表示任何相鄰的數據集，f是在數據集D上執行的查詢函數。全局敏感度Δf由查詢函數f決定。

定理1（Laplace 機制[22]）對于任意數據集D和函數f:D→Rd，若算法K的輸出結果滿足：

則算法K滿足ε-差分隱私保護。其中代表添加的噪聲量，噪音量與Δf成正比，與ε成反比，即查詢函數f的全局敏感度越大，所需噪音越大。Laplace機制主要處理數值型數據。

定理2（指數機制[23]） 給定一個可用性函數u:(D,r)→R，若算法K滿足：

則K滿足ε-差分隱私。其中，Δu為u(D,R)的全局敏感度。指數機制的關鍵技術是如何設計可用性函數u(D,R)（r∈Range，其中r表示從輸出域Range中所選擇的輸出項），u(D,R)用來評估輸出值r，u(D,R)越大，r被輸出的概率越大。指數機制主要處理非數值型數據。

1.2.3 差分隱私的組合性質

差分隱私保護技術存在兩個重要的組合性質[24]：序列組合性和并行組合性。

性質1（序列組合性[24]）給定數據庫D，存在n個隨機算法K，設Ki(1 ≤i≤n)滿足εi-差分隱私，則Ki在D上的順序操作滿足差分隱私。

性質2（并行組合性[24]）給定數據庫D，存在n個隨機算法K，設Ki(1 ≤i≤n)滿足εi-差分隱私，則Ki在D上的并行操作滿足max(εi)-差分隱私。

2 基于k-prototype 聚類的差分隱私混合數據發布算法（DP-k-prototype）

在隱私數據發布的背景下，可以將數據發布視為對數據集中每條記錄的連續查詢的收集答案。本章提出了基于k-prototype 聚類的差分隱私混合數據發布算法（DP-k-prototype）：采用k-prototype 聚類算法，首先隨機選取初始類中心，根據改進的元組屬性差異度計算方法對數據集進行聚類；然后根據最佳聚類結果，對每個聚類中的數值型屬性計算聚類中心，分類型屬性生成屬性值集合；接下來遍歷每一個數據記錄并確定其聚類類別，將數值型屬性替換為聚類中心值并采用拉普拉斯機制添加噪聲，對分類型屬性采用指數機制進行選擇；最后生成差分隱私數據集。由于查詢函數的靈敏度被分化到每組數據的k個記錄中，因此可減少噪音添加量，提高數據可用性。

2.1 元組屬性差異度計算

現有的大多數數據表都是混合數據表，也就是說，表中的數據屬性分為數值型和分類型。對于具有不同類型屬性的數據，存在不同的屬性差異度計算方法。假定在具有n個記錄和d維屬性的混合數據集D中，包含q維數值型屬性和p維分類型屬性（d=p+q），表示第i個數值型屬性，表示第j個分類型屬性。

與數值型屬性不同，分類型屬性需要通過建立概化層次樹來計算屬性差異度。每一個分類型屬性都要建立一棵概化層次樹。圖1 為Country 屬性的概化層次樹，葉子節點為Country 屬性上的各個屬性值。

Fig.1 Generalization hierarchy tree for“Country”圖1 Country 屬性概化樹

分類型屬性數據在不同程度上會影響著聚類結果，本文根據分類型屬性數據對聚類結果的影響程度和k-prototype 算法中分類型屬性權重所對應的權值計算元組間的差異度,從而提高聚類精度。兩個元組間的差異度計算公式為：

其中，wj表示在第j個分類型屬性所占的權重。

k-prototype 聚類需要選擇一個合適的損失函數來計算數值型和分類型變量對聚類中心點的距離。假定數據集的聚類個數為k，yim取值為{0,1}，表示在第m(1 ≤m≤k)個聚類中是否存在元組i，存在則為1，不存在則為0，則損失函數可以定義為：

2.2 混合數據表中聚類中心點計算

對于具有不同屬性的數據，若使用單一方法通常會導致信息丟失和中心偏差等問題。因此，本文采用了一種混合數據表的聚類中心求解方法。

假設存在具有n個記錄和d維屬性的混合數據集D，包括q維數值屬性和p維分類型屬性（d=p+q），數據集經過聚類算法被聚為k類。

假設輸入數據集中的q維屬性Aq是數值屬性的。因此，如果屬性(i=1,2,…,q)已被聚類，則聚類Cm(m=1,2,…,k)具有km個記錄表示等價類Cm中的j(j=1,2,…,km)元組中屬性Aqi的值。聚類的數值屬性中心計算為：

式中，km是聚類Cm中的元組數。

2.3 噪音添加方式

針對數值型屬性，采用Laplace 機制為聚類中心添加噪聲，計算公式如下：

與數值型屬性不同，分類型屬性從一組有限類別中獲取值，由于將拉普拉斯噪聲添加到聚類中心沒有任何意義，另一種獲得差分隱私輸出的方法在于以概率方式選擇聚類中心，這可以通過指數機制來完成。該機制根據輸入數據、差分隱私參數和質量標準選擇最接近最佳的中心點。在這種情況下，質量標準是每個分類型屬性值出現的概率。形式上，給定具有離散輸出r的函數，該機制根據輸入數據和質量標準選擇接近最優的輸出，同時保留ε-差分隱私。每個輸出與選擇概率Pr(r)相關聯，選擇概率Pr(r)隨質量標準呈指數增長，如下所示：

2.4 算法描述

在本文中，基于k-prototype 聚類的差分隱私靜態數據發布算法主要用于發布包含數值型屬性和分類型屬性的混合數據集。本文算法分為聚類分組階段和數據發布階段，第一階段利用改進的k-prototype 聚類算法實現對數據的聚類劃分，第二階段實現差分隱私數據發布。算法的具體流程如算法1 所示。

算法1DP-k-prototype

本算法第1～10 行是聚類分組階段，第11～17 行是差分隱私數據發布階段。第1 行，進行m次初始中心點的選擇。第2～9 行，是初始中心點選擇后的聚類過程：首先，遍歷數據集中的每一個元組ta，采用元組屬性度計算方法分別計算元組ta與中心值Cj(1 ≤j≤k)的差異度div(ta,Cj)；其次，將其分到距離最近（具有最小差異度）的聚類中；再次，對于每個聚類，重新定位中心點并計算其中心值Cj(1 ≤j≤k)；最后，確定每個聚類中的元組是否發生更改，如果更改，返回第4行；如果沒有更改，則計算損失函數值Ei。第10 行，比較m次初始點選擇中損失函數值的結果，選擇損失函數值最小時的聚類結果。第11、12 行，對于每一個聚類，針對數值型屬性計算第j個聚類中的聚類中心值；針對分類型屬性則生成屬性值集合。第13～15行，針對數據集D中的每一條數據記錄ta：首先，判斷其聚類類別。其次，判斷每一維屬性是屬于數值屬性還是分類屬性。如果是數值型屬性，則將其替換為聚類中心值，然后采用Laplace 機制噪聲獨立地添加到每個屬性值中；如果是分類型屬性，則根據所屬聚類屬性值集合中該屬性的中心候選者的選擇標準，使用指數機制選擇所輸出的屬性值。最后，將數據集D中每一個數據記錄替換為滿足差分隱私的數據記錄；第16、17 行，生成并返回滿足差分隱私保護的數據集。

3 隱私分析

本文將從差分隱私的概念及組合性質兩方面對DP-k-prototype算法的隱私性進行分析證明。

定理3DP-k-prototype算法滿足ε-差分隱私。

證明設有任何相鄰數據集D1和D2，K(D1)和K(D2) 分別表示在數據集D1和D2上執行DP-kprototype 算法后輸出的結果，S和O分別表示DP-kprototype 算法在相鄰數據集D1和D2上所有數值屬性數據和分類屬性數據輸出的結果,?表示滿足差分隱私的數據集。根據差分隱私保護的要求，在原始數據集中改變任意一條記錄后，算法K的輸出結果概率幾乎沒有顯著變化，因此即證明≤exp(ε)。令f(D1)和f(D2)分別表示在數據集D1和D2的查詢結果，表示在上的查詢結果。針對數值屬性數據，Pr[K(D1)∈S]∝，則：

根據差分隱私的并行組合性質[17]，對于數據集D中沒有交集的數據執行隱私保護預算為ε的隨機算法K，那么整個數據集均滿足ε-差分隱私。在DPk-prototype 算法中，由于k個聚類內的數據均無交集，根據差分隱私的并行組合性質，為每個聚類分配的隱私預算均為該算法的整體隱私預算ε。與此同時，每個聚類中數值型屬性和分類型屬性數據也均無交集，根據差分隱私的并行組合性質，為每個屬性維度分配的隱私預算均為該聚類的隱私預算ε，且已證明數值型屬性數據和分類型屬性數據的計算查詢滿足ε-差分隱私。因此，DP-k-prototype 算法滿足ε-差分隱私。

4 實驗評估

4.1 實驗數據集

實驗數據集選擇隱私保護研究領域被廣泛使用的UCI 機器學習數據庫中的Adult 數據集，該數據集由48 842 個記錄和14 個屬性組成。刪除具有空屬性的記錄后，共有30 162 條記錄。為了同時考慮具有異構屬性類型的數據，本文從“Adult”選取8 個屬性如表1 所示，派生5 個評估數據集。其中第一個評估數據集包括3 個屬性（2 個數字型屬性和1 個分類型屬性），每個評估數據集增加1 個分類型屬性，最后一個評估數據集包括8 個屬性（2 個數字型屬性和6 個分類型屬性）。

Table 1 Adult dataset properties表1 Adult數據集屬性

4.2 實驗評價標準

在本文提出的方法中，數據可用性是通過由聚類中心替換聚類內的記錄且采用差分隱私保護技術所產生的信息損失來測量。其中，信息損失可以通過誤差平方和（sum of squared errors，SSE）量化，這是聚類中通用的信息損失測量方法。SSE 被定義為待發布數據集中的原始記錄元組與差分隱私數據集中對應元組之間距離的平方和，計算公式如下：

對于數值型屬性，d(ta(Ai),ta′(Ai))對應于標準歐幾里德距離，而對于分類型屬性，使用式（7）計算其距離。

隱私保護能力通過信息披露來衡量，信息披露越小，隱私保護能力越強。信息披露表示為與差分隱私數據集正確匹配的原始數據記錄的百分比，即記錄關聯（record linkages，RL）：

其中，n表示原始數據集的數據記錄數量，差分隱私數據記錄t′的記錄關聯概率Pr(t′)計算為：

其中，G是距離t′最小的原始記錄集合，距離采用式（13）進行計算。如果正確的原始記錄t在G中，則Pr(t′) 表示在G中猜測t的概率，即1/|G| ；否則，Pr(t′)=0。由于差分隱私并不排除記錄鏈接成功的可能性。因此，RL 越小，隱私泄露的可能性就越低，隱私保護能力就越好。

4.3 實驗結果與分析

該實驗將本文提出的DP-k-prototype 算法與MDAV（maximum distance to average vector）[16]算法以及標準差分隱私算法在Adult 數據集上進行比較。選擇MDAV 算法的原因是，該算法是處理混合屬性數據集的差分隱私數據發布算法，且為該領域的經典算法。而標準差分隱私算法則是不對混合數據集進行任何分組處理，對每一條記錄執行查詢并進行差分隱私處理。

將隱私參數ε設置為{0.01,0.10,1.00,10.00}，根據不同屬性個數d(d={4,8}) 不斷調整聚類個數k(3 ≤k≤100)的大小，以進行數據可用性對比實驗，實驗中信息損失SSE 結果如圖2 所示。當ε={0.01,0.10}時，SSE 較大，當ε={1.00,10.00}時，SSE 較小，并逐漸減小。當ε=0.01 時，所添加噪聲量非常高，即使在采用本文算法降噪的情況下，數據可用性也非常低。隨著聚類個數k值增大，當ε={1.00,10.00}時，數據可用性逐步提升。

Fig.2 Changes in SSE when d is unchanged and k is changed圖2 當d 值確定、k 值變化時，SSE 變化情況

Fig.3 Changes in SSE when k is unchanged and d is changed圖3 當k 值確定、d 值變化時，SSE 變化情況

圖3 根據聚類個數k(k={4,20,40})不斷調整混合數據集屬性個數，以進行數據可用性對比實驗。在圖2中，可以看到隨著屬性數量的不斷增加，SSE也不斷增加。與圖2的表現一致，當ε={0.01,0.10}時，SSE較大（3 ≤d≤8），數據可用性較差；當ε={1.00,10.00}時，SSE 差距較小，并逐漸減小。與此同時，在每次調整的混合數據集屬性個數（3 ≤d≤8）中，前兩個屬性始終是數值型屬性,每次只增加一個分類型屬性。由于不同的分類型屬性個數不同，因此生成概化樹產生的信息損失也不同。故隨著屬性的增加，信息損失量增長趨勢與分類型屬性個數密切相關。

圖4 中，將屬性個數d設為8，隱私預算ε設為{0.01,0.10,1.00,10.00}，隨著聚類個數k的變化，信息披露RL 對比分析如圖4 所示。隨著聚類個數k的增加，當ε={0.01,0.10,1.00}時，RL 值的變化幅度較小，基本維持在0.002%左右；當ε=10.00 時，RL 值的變化呈現上升趨勢。這是因為當ε越大，添加的噪聲就越少，導致出現信息披露的風險就越高，因此隱私保護能力就越弱。從圖2 中可以看出，SSE 的大小直接取決于ε的值，當ε=1.00 或10.00 時，其數據可用性差距不大，但是ε越大，其隱私保護能力越弱，因此當ε=1.00 時獲得最佳結果。

Fig.4 Changes in RL when d equals 8 and k is changed圖4 當d=8、k 值變化時，RL 變化情況

Fig.5 Comparison of three algorithms when ε=1.00,d is unchanged and k is changed圖5 當ε=1.00、d 值確定、k 值變化時，三個算法情況比較

圖5 將本文提出算法DP-k-prototype 與同是處理混合屬性數據集的MDAV[9]算法以及標準差分隱私算法進行比較。當ε=1.00，d={4,8}時，隨著k的增加，MDAV 算法的SSE 在逐漸減小，DP-k-prototype算法的SSE 在逐漸減小后更趨于保持穩定，且DP-kprototype 的數據可用性始終高于MDAV。這是因為MDAV 算法對輸入數據的順序比較敏感，由微聚集形成的聚類不太均勻，因此會產生比較大的信息損失。而DP-k-prototype 算法在聚類的過程中，針對全局進行考慮，將屬性差異度最小的數據聚為一類，與數據輸入順序無關。

5 結束語

本文提出了一種可以在混合數據集上執行差分隱私的數據發布方法。針對這個問題，考慮了改進kprototype 聚類算法，并通過對數據集中的分類和數值屬性使用不同的方法計算屬性差異度。本文方法旨在將更可能相關的類似記錄分組，以降低差分隱私的敏感度和添加到查詢答案中的噪聲量。結合聚類中心值，對原始記錄采用差分隱私保護技術進行處理保護，針對數值型屬性使用Laplace 機制，分類型屬性使用指數機制，從而在提供隱私保護的同時提高數據可用性。