基于聚類分析的個性化異構數據發布

聶 靜，常 濤，劉 維，呂小紅，王 晨，楊知方

(1.國網重慶市電力公司，重慶 400014；2.輸配電裝備及系統安全與新技術國家重點實驗室(重慶大學)，重慶 400014)

在如今的大數據時代，數據的價值已經越來越被人們所重視[1-2]。對于公共數據發布中存在的隱私保護問題也越來越受到關注，如何實現安全有效的數據發布成為了一個研究熱點[3]。

在大數據中，異構數據已經越來越普遍。異構數據通常由關系數據和集值數據組成，因此異構數據的隱私保護一般分為關系數據匿名化與集值數據匿名化[4]。對于關系數據匿名化問題，文獻[5]隱藏識別屬性和敏感屬性之間的相關性，并生成k-匿名相似性數據以顯示身份和屬性。文獻[6]通過在泛化過程中添加不確定性，可以有效發布差分隱私數據。對于集值數據匿名化問題，文獻[7]提出一種數據分區技術，用于斷開標識屬性之間的關聯，并在最終查詢結果中添加噪聲。文獻[8]提出KP匿名模型，通過區分集值屬性中的敏感項和非敏感項，滿足多樣性相關性來防止屬性泄漏。雖然上述方法取得了一定的效果，但是許多方法均是單獨處理關系數據或集值數據，對于異構數據來說是否有效還需進一步研究，且均沒有考慮。

針對異構數據匿名化，也有一系列研究，文獻[9]提出一個差分隱私回歸分析模型，將目標函數轉化為多項式形式，并對多項式表示的系數加入噪聲。文獻[10]將差分隱私與決策樹相結合，提供分類器的隱私保護，還使用小批量梯度下降算法來保護訓練數據的隱私。雖然這些工作針對某些特定數據考慮了異構數據的聚類性能，但是缺乏泛化性能，即上述匿名化過程不考慮一般性的聚類分析任務，因此用戶在使用時缺乏靈活性與實用性。

針對上述問題，現提出一種基于聚類分析的個性化異構數據發布方法。利用聚類標簽對聚類結構進行編碼，并結合泛化技術和輸出擾動來掩蓋原始數據。以期有效解決異構數據發布問題。

1 差分隱私

(1)

參數ε被稱為隱私預算，它是通過隨機機制M來控制隱私保證的程度。ε越小意味著隱私保護程度越高。ε默認為一個正數并且它的數值通常比較小，如0.1、0.5和0.8。

附加噪音的量不僅取決于隱私預算ε還取決于隨機機制的全局敏感度。全局敏感度反映了兩個相鄰數據集上函數輸出的最大差分。

(2)

定義3(拉普拉斯機制)[12]：給定一個數據集D，隱私預算ε和一個隨機函數f:D→R，其全局敏感度是Δf，算法M(D)=f(D)+Lap(Δf/ε)滿足ε-差分隱私。

差分隱私有兩個重要的屬性。它們在判斷一種機制是否滿足差分隱私中起著重要的作用。

順序組合表明當許多差分隱私被應用于相同的數據集時隱私預算和噪聲會線性增加。

屬性2(平行組合)：M={M1,M2,…,Mm}是一組隱私機制。如果每個Mi在不相交的數據集子集上提供ε-差分隱私，則Mi將提供(max{ε1,ε2,…,εm})-差分隱私。平行組合表明當應用于不同數據集子集中的一組差分隱私，其隱私保護程度取決于εi的最大值。

2 問題描述

假設數據所有者希望通過將特定于個人的數據發布給數據接受方來進行聚類分析。這些原始數據可以被定義為一組記錄D={r1,r2,…,rn}}，每個記錄ri(1≤i≤n)代表一種具有d屬性A={A1,A2,…,Ad}的個人信息。假定每一種屬性Aj(1≤j≤d)可以是分類的，數值的或集合值的，并且為每個分類或集合值的屬性給出了分類樹。在發布之前，應刪除明確的標識符，如名稱和駕駛執照編號。

聚類分析的任務是將對象分成若干組，使相似的對象在組中，不同的對象在不同的組中，聚類的結果可以用聚類結構來表示。

定義5(聚類結構)[14]：設g是聚類的個數，數據集D={r1,r2,…,rn}的聚類結構被定義為一個矩陣Un×g，矩陣的每個元素ei,j∈{1,0}(1≤i≤n,1≤j≤g)代表了記錄ri到第j個聚類的聚類分配，也就是說，當ei,j等于1時記錄ri屬于第j個簇，而當ei,j等于0時ri不屬于第j個簇。

基于上述假設，有如下定義：

定義6(聚類分析差分隱私異構數據)：給定一個數據集D={r1,r2,…,rn}和隱私預算ε，對異構數據進行聚類分析的匿名化問題是使是使數據集D使不同類型的屬性上匿名化。例如，滿足ε-差分隱私并且盡可能與D的聚類結構保持相似的匿名數據集D′={r′1,r′2,…}。

3 異構數據發布方法

3.1 差分隱私的泛化算法

首先，數據所有者在原始數據集D上使用一種聚類算法來確定初始的聚類結構，同一聚類中的記錄有相同的聚類標簽。與數據集D相比，標記的數據集D*具有d+1個屬性A*={A1,A2,…,Ad,Class}，其中Class表示類標簽；即除了D中的原始屬性d，D*中的每條記錄ri也有一個類標簽。因此，保存D的聚類結構意味著在匿名化過程中保留識別這些類標簽的能力，然后通過在D*上執行所提出的差分隱私算法來獲取匿名數據集D′。如果D′不夠令人滿意，則數據所有者可以返回到第一步并且調整算法因子，即分類樹，聚類算法的選擇和聚類的數量。重復上述步驟直到得到效能滿意的D′。第四步，數據所有者將數據集D′釋放給數據接收者。

為異構數據提出了一種稱為DPHeter的差分隱私的泛化算法，該算法基于自上而下的專業化技術[15]。專業化從最一般的狀態開始，然后通過將某些值替換為更具體的值來迭代下降，直到達到預定義的專業化數量。專業化過程就是根據相應的分類樹，由表示將父值p→Children(p)替換為其直接連接的子值Children(p)。交替使用術語“子節點”和“子值”。在下文中，還將可以替換為其直接關聯的子值的父值稱為“cut”。

圖1顯示了數據的專業化過程。首先，將每個值都概括為圖1所示對應的分類樹上的最上面的值，并且初始值∪cut為{[19,75],ANY_SEX,**}。假設將ANY_SEX剪切以向下切割，然后由于ANY_SEX→M,F和當前∪cut被更新為{[19,75],M,F,**}。

圖1 分類樹示意圖Fig.1 Schematic diagram of classification tree

確保專業化過程滿足ε-差分隱私的關鍵是確定匿名化的每一步都是差分隱私的。其關鍵步驟包括切割選擇和劃分記錄。

選擇用指數機制來選擇割集是因為該機制是為離散備選方案設計的。根據定義4可知，這個過程是需要效用函數的。另外采用屬性與類標簽之間的信息增益作為效用函數。這是因為切割上的每個專業化的過程中都傾向于通過生成特定的屬性值來增加信息，并且信息增益能夠基于這些值使類標簽“更可預測化”。計算數據集D中屬性值x的熵的方法為

(3)

一般化為其子值的屬性值p的效用函數定義為

(4)

在每一次的專業化過程中，首先通過式(4)完成每個割集候選的效用分數，然后根據指數機制有效地選擇一個割以向下劃分。Children(ANY_SEX)={M,F}。根據式(4)中ANY_SEX效用分數計算為

與上述計算類似，u([19,75])=0.281 2，u(**)=0.095 4，根據指數機制，[19,75],ANY_SEX,**被選擇為切割的可能性分別是56.12%、24.85%和19.04%。

選擇剪切后，原始記錄分為不同的組。因為它們具有預定義的分類樹，所以分類屬性的劃分策略是固定的。因此分類屬性的分區函數的全局敏感性為1。根據當前選擇的分類切割和相應的分類樹，記錄分區的步驟應滿足差分隱私。

與分類屬性相比，集值屬性專門化的區別在于子節點組合的存在。假設選擇一個設定值p,在它對應的分類樹上有t個子節點。在p上的一般化將產生總共2t-1個子集。為了提高DPHeter的效率,應該盡早的剪掉子集。由于差分性隱私需要不確定性，因此通過驗證其噪聲大小是否大于閾值，將其視為“非空”。也就是說，如果子分區的噪聲大小大于閾值，則保留該子分區。否則，將其視為“空”，應該修剪。閾值可以由數據所有者控制。

如文獻[15]中所述，無需為數字屬性提供分類樹。如果選擇了數字分割以向下分割，則在搜索分割的分割值時將動態生成或擴展其相應的分類樹。不應為分割隨機選擇分割值，因為從不包含該值的數據集中選擇相同值的可能性為0。這意味著對數值屬性的分割值的選擇是概率性的。再次使用指數機制，計算數字切割中每個屬性值的效用得分，并使用指數機制選擇屬性值作為數字切割的分割值。選擇屬性值c作為數字割點p的分割值的概率定義為

(5)

式中：ε為隱私預算；Δu為式(4)的全局敏感度；u(c)(或u(xi))為c(或xi)的效用分數；I(p)為剪切p的屬性值的集合。Age屬性最初被概括為[19,75)cut。如果選擇[19,75)cut進行分割，將計算每個屬性值在19～75范圍內的效用得分，并且概率地選擇一個值作為[19,75)cut的分割值。考慮21類屬性；然后，根據等式(4)，u(21)計算如下：

u(21)=H21(D)-

0.144 5。

在計算完所有的u(·)后，式(5)用于計算每個值被選作實際拆分值的概率。首先，為dnum數值屬性初始化分割值，其中dnum是數值屬性的數量。然后，針對每一輪專業化，概率性地選擇切割。如果切割是設置值的，則應驗證其非空子節點，以確定它們是否真的是“非空”；如果切割為數字，則為其選擇分割值。請注意，這兩種情況是互斥的。每個葉分區節點中的確切記錄數不能直接發布，因為對于不同的數據，該數目可能不同。可以通過在每個節點中的記錄數量上增加噪聲來掩蓋這種差分。

3.2 隱私分析

定理1DPHeter滿足ε-差分隱私。

定理2DPHeter時間復雜度為O(h·nlog2n)。

證明：DPHeter為數值屬性選擇一個時間復雜度為O(nlog2n)地分割值，其中n是輸入的大小數據集。dnum數值屬性確定拆分值，其時間復雜度為O(dnum·nlog2n)。通過遍歷具有d屬性，其時間復雜度為O(d·nlog2n)的輸入數據集，然后DPHeter無需遍歷所有數據記錄，而是根據為∪cut中候選數據保留的某些信息來計算效用分數；因此相應的時間復雜度僅要求是O(n)。根據定義4，從指數機制選擇切割時，它的成本與離散切割的數量成正比。因此，基于概率選擇算法的成本為O(|∪cuti|)，其中|∪cuti|是∪cuti的大小，數值屬性選擇的時間復雜度為O(nlog2n)的分隔值。通常|∪cuti|比n小的多。因此，循環迭代效能滿意算法成本為O(h·nlog2n)。其他計算均可以在恒定的時間O(1)內被完成。因此，DPHeter的總運行時間為O(h·nlog2n)。

4 實驗與分析

4.1 實驗設置與數據集

所有的實驗都是在一臺3.4 GHz的CPU為英特爾酷睿i7，內存大小為16 GB，操作系統為Windows 10(64位)的個人電腦上進行的。下面所給出的每個結果都是運行5次以上的平均值。

實驗使用了兩個公開的數據集，即Adult和MIMIC-III。Adult數據集包含人口普查記錄，文獻表明，該數據集已廣泛用于測試匿名方法。在實驗中，刪除了類標簽，并將此數據集用于聚類分析。為了綜合一個異構數據集，假設一個人可以有多個職業，然后將具有相同屬性值的記錄組合到一條記錄中，從而使職業屬性為集值。為了綜合處理，放棄了三個數值屬性(即fnlwg，資本收益和資本損失)、因為它們可能產生更少的異構記錄。因此，保留了28 308條記錄，這些記錄具有7個分類屬性，6個數字屬性和一個集值屬性。為簡化問題，將合成數據集稱為Adult。

第二個數據集MIMIC-III是醫療研究的重要公共資源。它由一些臨床注釋表組成，包括護理記錄和出院摘要。具體來說，根據共享的subject_id列將三個表連接在一起。然后，將相同subject_id的多個ICD-9代碼合并為一行。檢索了48 612條記錄，并選擇了7個分類屬性，即性別、婚姻狀況、宗教、種族、入學類型、保險方式、入學來源和一個集值屬性ICD-9代碼。

選擇K均值和平分K均值僅包含一個算法參數，即聚類數K，而不是考慮聚類參數的不同組合[16-17]。任何聚類算法都需要某種方法來測量對象之間的距離或相似性。因此介紹兩個異構記錄的語義距離度量。如果讓x1、x2表示來自同一域的兩個屬性值，則x1和x2之間的距離計算如下：

(6)

式(6)中:path(x1,x2)為x1和x2之間最短路徑的長度；H是相應分類法樹的高度。歸一化定義的優勢在于，分類樹的所有葉節點可以具有不同的深度。兩個異構記錄之間的距離，即r1和r2，定義為

(7)

PPDP的目標是在保護可觀數據實用性的同時保護原始數據集的私人信息。通過匿名前后的聚類結構的相似性來確定數據實用性。也就是說，匿名化前后的聚類結構越相似，匿名化數據集的效用就越高。在實驗中，應用兩個指標F-measure和MatchPoint評估兩個聚類結構的相似性。

考慮兩個聚類結構T和P，將T中的每個聚類Ti視為“真實聚類”，將P中的每個聚類Pj視為“預測聚類”。令numij表示同時包含在Ti和Pj中的記錄數，并且|·|表示聚類中對象的數量。Ti和Pj的聚類精度(Precison)、召回率(Recall)和F測度F-Measure計算如下：

(8)

(9)

F(Ti,Pj)=2×

(10)

它測量聚類Pj預測的準確性，該預測基于Precison和Recall描述了真實的聚類Ti。真實聚類Ti的成功預測是通過Ti的“最佳”預測聚類Pj來衡量的，即Pj的最大化F(Ti,Pj)。因此，加權最大F-Measure的總和用于評估聚類結構P的質量，并且P的整體F-Measure計算為

(11)

式(11)中：|D|是原始數據集D中的記錄數。F-Measure(P)的范圍是0～1。F-Measure(P)的值越大，比較的兩個聚類結構越相似。

如果兩個保留在同一個聚類C1中的記錄在C2中一起保存，并且C1中不同聚類的兩個記錄被分在C2中不同的聚類里則說明兩個聚類結構C1和C2相同。對于每個聚類結構，都將生成一個方矩陣Matrix(·)來表示每對記錄之間的關系。也就是說，如果第i個記錄和第j個記錄在同一聚類中，則Matrix(·)的第(i,j)個元素等于1；否則等于0。然后，定義MatchPoint來表示Matrix(C1)和Matrix(C2)中出現的相同值的百分比：

MatchPoint[Matrix(C1),Matrix(C2)]=

(12)

如果Matrix(C1)和Matrix(C2)中第(i,j)個元素的值相同，則mij=1；否則，mij=0，并且|D|是原始數據集D中的記錄數。MatchPoint的范圍是0～1。MatchPoint的值越大，比較的兩個聚類結構越相似。

4.2 結果分析

4.2.1 數據實用性和隱私

在該實驗中，改變了隱私預算ε，專業化數目h和聚類數k，以觀察F-measure和MatchPoint。

圖2～圖5顯示了Adult的結果。其中，圖5(a)顯示了當ε=0.1且h=4時，最小F-measure為0.540 8。圖5(a)還顯示當ε=0.1且h=16最大F-measure為0.784 0。與F-measure相比，不同于ε和h值的MatchPoint值的跨度較小，在0.727 0～0.931 4范圍內。有一個明顯的趨勢表明隨著較高的ε導致較少的干擾和較少的噪音，F-measure隨ε的增加而增加。另外，F-measure和MatchPoint也隨著h的增加而增加，因為更詳細的信息保留在用于聚類的匿名數據集中。但是，從一定的h開始，隨著h的進一步增加，F-measure和MatchPoint保持相同或減少。這是因為h的值越高，表示分區樹中的葉子節點越多，并且葉子節點的數量越多，作用于這些葉子中的記錄數的拉普拉斯機制產生的噪聲越多節點。圖6～圖9顯示了MIMIC的F-measure和MatchPoint值的相似趨勢，只有在獲得最佳性能的情況下和h的值不同。這些結果表明，DPHeter即使對于不同的匿名性要求，也可以在匿名化后保持原始數據集的相似聚類結構。

圖2 3均值Adult數據的效用Fig.2 3 utility of mean Adult data

圖3 5均值Adult數據的效用Fig.3 5 utility of mean Adult data

圖4 對等分3均值Adult數據的效用Fig.4 The utility of Adult data with equal 3-means

圖5 對等分5均值Adult數據的效用Fig.5 The utility of Adult data with equal 5-means

圖6 3均值匿名MIMIC的數據效用Fig.6 3 utility of mean MIMIC data

圖7 5均值匿名MIMIC的數據效用Fig.7 5 utility of mean MIMIC data

圖8 對等分3均值匿名MIMIC的數據效用Fig.8 Data utility for 3-means anonymous MMIC

圖9 對等分5均值匿名MIMIC的數據效用Fig.9 Data utility for 5-means anonymous MIMIC

4.2.2 不同匿名化算法上的數據實用程序

為了驗證提出的聚類算法聚類質量是否比沒有這傾向的一般差分隱私的聚類質量更好，在ARX工具中將本文算法與(ε,δ)-差分隱私進行了比較。(ε,δ)-差分隱私是ε-差分隱私的松弛版本，因為前者允許以δ為邊界的錯誤概率。因為只有關系數據可以輸入到ARX，所以首先將異構的Adult和MIMIC轉換為關系數據。具體來說，將為值屬性集合的每個值創建一個二進制屬性。例如，如果屬性是值集合的并且具有兩個值，即x1和x2，則記錄的模式將為“0 1”“1 0”或“1 1”。此類轉換僅對ARX執行，對DPHeter不執行。之所以為(ε,δ)-差分隱私設置δ=1×10-5和δ=1×10-11，是因為對于該工具，這兩個值分別是最大和最小可接受值。將DPHeter的h固定為16。結果如圖10～圖13所示。這些數字表明，在每個隱私預算上，DPHeter的F-measure值明顯優于(ε,δ)-差分隱私。例如，在圖11(a)和圖13(a)中，即使ε=0.1，Adult的F-measure為0.633 1，而MIMIC的F-measure為0.642 8，而當δ=1×10-5時Adult和F-measure的(ε,δ)-差分隱私的F-measure分別僅為0.201 5和0.332 8,但是，MatchPoint值之間的差分較小。這是因為匿名前后位于不同聚類中的兩個記錄的情況也對MatchPoint的值起了積極的意義。

圖10 Adult數據不同的5-均值匿名算法Fig.10 Different 5-means anonymity algorithms for Adult data

圖11 Adult數據不同的對等分5-均值匿名算法Fig.11 Different 5-means anonymity algorithms for Adult data

圖12 5均值的MIMIC匿名算法Fig.12 5 mean MIMIC anonymous algorithm

圖13 對等分5均值的MIMIC匿名算法Fig.13 5 mean MIMIC anonymous algorithm

當0.1≤ε≤1評估ARX工具中DPHeter相對于(ε,1×10-5)的DPHeter改進時，還對0.1≤ε≤1成對測試用例進行了一系列單尾t檢驗。證明DPHeter的改善在α=5%時具有顯著地統計學意義。從這些結果可以推出，提出的方法在聚類質量方面勝過了一般的匿名化方法。

4.2.3 可擴展性

在可擴展性方面，將DPHeter與ARX中的(ε,δ)-差分隱私進行了比較。與第4.2.2節中的實驗相似，為(ε,δ)-差分隱私設置δ=1×10-5和δ=1×10-11，為DPHeter設置h=16。并固定了ε=1并進行了5-均值聚類。通過隨機復制它們的記錄，生成了多個版本的Adult和MIMIC。為了比較，圖14顯示了具有200 000～1 000 000條數據記錄的DPHeter和ARX在Adult和MIMIC上的結果。該圖表明，在運行時方面，ARX比DPHeter更有效，因為ARX不考慮數據分析任務。在搜索數值屬性的分割值時，DPHeter將計算當前值范圍內所有可能數值的效用分數。在拆分集值屬性時，DPHeter根據分類樹考慮當前父節點的子節點的組合。通過維護和更新信息，而不是重復掃描所有數據記錄，進一步提高了DPHeter的運行速度。而在MIMIC上花費的時間比在Adult上花費的時間更長。這是因為中有成千上萬個代碼，并且相應的分類樹比t中的職業屬性樹大得多，這意味著選擇代碼屬性進行拆分時需要更多的計算時間。

圖14 兩個數據集的可擴展性Fig.14 Scalability of two datasets

DPHeter的適應性。雖然在第4節中只使用了k-均值和等分k-均值來評估DPHeter的性能，但是其他的聚類算法，如DBSCAN，可以集成到本文算法中。本文算法提供了一個靈活的框架，在這個框架中，聚類算法可以被視為“插件”組件。DPHeter利用將聚類結果對原始數據進行匿名化處理，而并非一種聚類算法。然而，數據匿名化前后用于聚類的距離度量應該保持不變，或者至少相似，以獲得更好的數據效用。否則，不同聚類策略所生成的聚類結構將會完全不同。同時，DPHeter的關注點是在數據發布的前后保持聚類結構的相似性。如果原始數據不適用于聚類分析或者某些聚類算法無法產生好的聚類結果，那么DPHeter就無法幫助數據或其匿名版本生成更好的數據。

5 結論

提出了一種用于聚類分析的異構數據發布方法。該方法利用聚類標簽對聚類結構進行編碼，并結合泛化技術和輸出擾動來掩蓋原始數據。通過分析實驗結果可得如下結論。

(1)提出的方法即使對于不同的匿名性要求，也可以在匿名化后保持原始數據集的相似聚類結構。

(2)引入了差分隱私方法的聚類質量比為引入差分隱私的匿名化方法更高，說明差分隱私有助于聚類性能的提高。

(3)提出的方法提供了一個適應性較強的框架，可以結合不同的聚類算法，且都能夠具有良好的數據實用。在這些不同實體聚類算法中使用的記錄之間的距離度量應保持相同或相似。否則，由不同聚類算法產生的聚類結構可能完全不同。