面向混合型數據集自適應聚類的差分隱私保護算法
2022-03-07 06:58:20張學典周圣英
軟件導刊 2022年2期
張學典，周圣英
（上海理工大學光電信息與計算機工程學院，上海 200093）
0 引言
大數據時代，數據處理方式不斷優(yōu)化，數據處理量迎來了井噴式增長。越來越多的研究機構投入到這些數字資源研究分析中，通過合理的數據挖掘分析方式，獲得高價值度的有效信息，從而支持各行各業(yè)緊密融合發(fā)展，推動實現企業(yè)、政府部門等組織的管理決策高效化。然而在提供巨大潛在利益的同時，無差別地將個人數據暴露在公共視野中，將會對個人隱私安全造成相當大的危害。因此，在合理使用用戶個人數據的同時應該兼顧用戶隱私安全。但是，如何在保證大數據發(fā)布信息可用的同時又能做到保護隱私數據安全，已然是當前數據發(fā)布隱私保護研究的熱點問題。
在數據發(fā)布中，敵手可以通過鏈接攻擊（敵手將獲取到的當前發(fā)布的信息同通過其他渠道獲取到的外部相關信息進行關聯對應，從而推理出用戶隱私數據，這種攻擊手段能夠造成隱私泄露）獲取個體隱私數據。為了防范敵手通過鏈接攻擊造成隱私泄露問題，k-匿名及其擴展模型被提出，k-匿名算法旨在通過概括及隱私隱匿技術，通過發(fā)布精度低的數據，達到保護隱私數據的目的，k-anonymity 要求發(fā)布信息中的每條記錄至少同其他（k-1）條待發(fā)布記錄具有完全相同的標識符屬性，從而達到減少鏈接攻擊所導致的隱私泄露目的。雖然k-匿名隱私保護模型已被證明能夠保證以下3 點：①敵手無法知道某個用戶是否在公開數據集中；②給定一個用戶，敵手無法確認該用戶是否有某項敏感信息；③敵手無法將數據與用戶一一對應。但是，在面對敵手基于背景知識的攻擊時，即使原始數據集中的敏感屬性并不相同，敵手依然能夠通過多次比較已掌握的相關背景信息高概率地獲取隱私信息；若經過k-匿名處理后得到的數據組內對應敏感屬性值相同，則更易遭受敵手發(fā)起的同質化攻擊進而造成隱私泄露。
2006 年，Dwork在處理統(tǒng)計數據庫的隱私泄露問題時提出差分隱私（Difference Privacy，DP）的概念：差分隱私保護模型是一種建立在嚴格數學證明基礎上的數學模型，對隱私泄露風險做定量的形式化證明。該模型假設敵手采用最大程度的背景知識攻擊，通過對需要進行隱私保護的真實數據添加隨機擾動因子以提供隱私保護，并保證這些經過處理的數據仍具有較高可用性。這種方式較k-匿名隱私保護模型能夠提供更加安全的隱私保證。
使用傳統(tǒng)差分隱私保護模型時，會在原始數據集中添加大量噪聲，這將破壞數據可用性，繼而影響后續(xù)數據挖掘效果。研究指出，可以通過降低查詢敏感度、合理分配隱私預算提高差分隱私保護數據可用性。因此，如何設計合適的算法實現這一目標將是本文考慮的主要問題。傳統(tǒng)差分隱私發(fā)布算法大多針對單一屬性數據，即數值型或分類型數據，而在實際應用環(huán)境中，數據類型都是混合屬性（包含數值型及分類型數據），如醫(yī)療大數據、車輛信息大數據等。鑒于此，設計出滿足差分隱私要求的，同時保證處理后數據可用性的面向混合型數據集的差分隱私算法具有重要意義。
1 相關概念及定義
1.1 相關工作
傳統(tǒng)聚類算法是以某種方式對一組對象進行分組，通過數據屬性間的差異度對數據集進行分組處理，可以實現將單一個體泛化到整組數據中以降低查詢敏感度。在這種情況下，對于待差分隱私保護處理數據，能夠有效降低差分隱私噪聲量，從而提高數據可用性。
本文分析現有差分隱私保護算法優(yōu)缺點，結合混合型數據集保護要求，通過改進k-prototype算法及快速聚類算法，提出一種適用于混合型數據集差分隱私保護的方法。雖然傳統(tǒng)的k-prototype算法能夠對混合型數據集進行有效聚類，但由于沒有固定的初始聚類中心選取方法，在一般情況下均采用隨機方法確定聚類中心，會導致最終聚類效果穩(wěn)定性差，進而影響差分隱私噪聲添加，降低數據可用性。而快速聚類算法通過樣本距離及密度衡量樣本間連接的緊密程度，但傳統(tǒng)快速聚類往往對數值型數據集采用“決策圖”方法判定聚類中心，混合型數據集相較于數值型數據集更為復雜，不可采用一般方法。結合上述傳統(tǒng)混合型數據聚類方法所存在的問題，本文提出了一種基于密度和距離自適應選擇初始聚類中心的差分隱私保護算法。通過計算混合型數據集中各樣本點的鄰域密度和相對距離（相異度），劃分出k個密度大且相對距離較遠的樣本點作為初始聚類中心，完成聚類；對生成的聚類結果，計算得到其數值型聚類中心，同時生成分類型數據的屬性值集合；然后判斷每一條記錄的聚類類別，將其數值型屬性替換為聚類中心并使用Laplace 方法添加噪聲，對分類型屬性采用指數機制選擇輸出，從而得到經過差分隱私保護的結果。本文所提出算法的評價指標主要有3 項：數據誤差率、規(guī)范化簇內方差及制定隱私預算下的隱私保護程度。
1.2 差分隱私基本定義
傳統(tǒng)隱私保護技術在面對攻擊者結合相關背景知識進行攻擊時，存在較大安全隱患，而差分隱私保護通過嚴格的數學方法克服了這一缺陷。該過程是通過向真實數據集添加隨機擾動因素而實現，此外要求保證數據在添加干擾因素后仍然具有較高的可用性，以確保在任一經過差分隱私保護處理的數據集中進行查詢操作而不影響結果，進而實現隱私保護。
定義1
（ε
-差分隱私）設有隨機查詢算法M
，以及任意兩相鄰數據集D
和D
（有且僅有一條記錄相異），若算法M
對D
和D
的任意輸出S
?Ran
ge(M
)滿足：
M
能夠為數據集提供ε
-差分隱私保護，參數ε
稱為隱私保護預算，算法M
的隱私保護強度可以通過ε
進行衡量，ε
越小隱私保護程度越高；反之ε
越大，則表明隱私保護程度越低。定義2
（全局敏感度）設有一個查詢函數f
:D
→D
，對于參與其中的任意兩相鄰數據集D
和D
，函數f
的全局敏感度定義為：
f
是在兩個數據集上分別執(zhí)行，其中||f
(D
)-f
(D
)||
表示向量元素絕對值之和，即1-階范數距離。差分隱私保護主要通過向原數據集添加擾動噪聲而實現，而在實際應用中，常見的噪聲添加機制主要有Laplace 機制和指數機制。其中，Laplace 機制針對數值型數據進行隨機擾動處理，添加的擾動因子符合正態(tài)分布，而指數機制則主要處理非數值型數據的擾動。全局敏感度和差分隱私預算共同影響噪聲機制。
定理1
（Laplace 機制）對于已有數據集D
，設有一查詢函數f
:D
→D′
，其全局敏感度為Δf
，如果算法K 滿足：
K
提供ε
-差分隱私保護。
定理2
（指數機制）對于任意一個給定的可用性函數μ
(D
,r
) →R
，若存在算法M
滿足：
除上述基本性質及定理外，差分隱私還存在以下組合性質，這些性質能夠保證將差分隱私保護運用到反復迭代過程中，結果始終滿足差分隱私。同時，以下性質也是實現合理分配差分隱私預算的基礎。
定義4
（并行組合性）同樣在給定數據集D
上，若存在隨機算法A
，能夠提供ε
-差分隱私保護，則將數據集D
劃分為互不相交的子集{D
,D
,…,D
}，則算法A
在{D
,D
,…,D
}上的并行操作所構成的算法也提供ε
-差分隱私保護。2 面向混合型數據集的差分隱私保護算法
2.1 樣本相異度及鄰域密度計算
混合型數據集包含數值型屬性及分類型屬性，因此對于不同數據類型需要采用不同的差異性度量方法。本文對數值型數據采用閔可夫斯基距離計算方法，對于給定的表示為x
=(x
,x
,…,x
)∈R
和x
=(x
,x
,…,x
)∈R
的樣本，其中n
表示維度，則樣本間距離可定義為：
p
是閔可夫斯基距離的階，本文取p
=1，即樣本間距離公式為：
x
=(x
,x
,…,x
)∈R
和x
=(x
,x
,…,x
)∈R
的樣本，其中n
表示維度，對于x
和x
的某一分類型屬性x
和x
，定義函數：
樣本間的簡單匹配距離為：
X
={x
,x
,…,x
}，每個樣本x
(i
=1,2,…,n
)都有p
個屬性，以a
,a
,…,a
,a
,…,a
表示屬性，其中a
,a
,…,a
為數值型，a
,…,a
為分類型。隨機選擇初始聚類中心C
={c
,c
,…,c
}，則樣本與聚類中心的相異度為：
γ
為分類型屬性對于相異度判斷影響所設權重。由傳統(tǒng)k-prototype 定義可知，對于簇中樣本需要確定代價損失函數確定各變量與聚類中心的距離，定義如下：
U
是維度為n
×k
取值為{0,1}的關聯度矩陣，有：
x
是否屬于第j
個簇，若屬于則U
=1，否則為0。而在執(zhí)行聚類迭代過程中，聚類中心可能會不斷發(fā)生變化，因此對于聚類中心的第q
個數值型屬性c
有：
q
個分類型屬性c
，則取數據集所有樣本中，按關聯度加權后，值頻率最高的值，即隸屬于該簇的所有樣本第q
個分類型屬性出現頻率最高的值：
X
={x
,x
,…,x
}中任意兩個樣本x
、x
間的平均距離定義為：
X
={x
,x
,…,x
}中任意樣本的鄰域密度ρ
為：
e
(x
,x
,ρ
)為核密度函數，其定義為：
2.2 基于密度和距離自適應的聚類中心選擇
綜上所述，對于混合型數據集聚類流程描述如下：
Step1：對于初始混合型數據集的每一條樣本計算其鄰域密度ρ
；Step2：通過遍歷按密度降序排列C
={C
,C
,…,C
}，定義集合M
，將排序后鄰域密度最大的樣本C
加入到集合M
中；Step3：繼續(xù)迭代C
，若集合C
中存在滿足對于任意M
∈M
都有dist
(C
,M
)>L
，則將C
添加到集合M
中，直至迭代完集合C
中的所有元素，則集合M
中所有元素即為初始聚類中心，此時簇數為|M|；Step4：根據相異度公式計算原始數據集中的每一個樣本x
與|M|個聚類中心的dist
(x
,c
)，將x
劃分到Min
(dist
(x
,c
))的簇中；Step5：計算樣本與聚類中心間的關聯度矩陣；
Step6：重新計算每個簇的聚類中心（數值型屬性按照式（12）計算，分類型屬性按照式（13）計算）；
Step7：根據計算出來的聚類中心，判斷原簇中數據是否發(fā)生變化，若無變化，聚類結束，得到聚類后的數據集，否則返回Step3；
Step8：判斷是否達到最大迭代次數，若達到結束聚類，否則依舊返回Step3。
2.3 聚類結果差分隱私保護
對經過聚類操作的數據集進行添加噪聲處理，采用Laplace 機制對聚類中心的數值型屬性添加噪聲，即：
而對于聚類中心的分類型屬性，使用Laplace 機制添加噪聲沒有意義，由于分類型屬性的構成是從有限集中選取，因此通過差分隱私的指數機制，以一定概率選擇輸出，故根據式（4）可得：
完整算法描述如下：
Input
：混合型數據集X
，數據維度d，迭代次數t，初始聚類中心點集M，隱私預算ε
，聚類簇數目n
，數值型屬性數目p
，分類型屬性數目d
-p
3 實驗分析
3.1 數據集處理
實驗中所需的混合型數據集選用在隱私保護領域廣泛應用的UCI（University of California）Machine Learning Reposity中的Adult數據集，在處理其無效內容及空屬性記錄后，共有30 162條備用記錄。本文在考慮數據集本身所具有的異構屬性類型數據后，選擇其中8項作為評估數據集進行處理，包括數值型屬性：age、hours-per-week 和分類型屬性：workclass、education、occupation、race、sex、native-country。
差分隱私對于混合型數據集的數據可用性是通過聚類中心替換簇內樣本記錄并添加對應噪聲所產生的信息缺失加以定量。而信息缺失可以通過樣本與聚類中心的距離進行量化，即通過式（10）的誤差平方和加以衡量。
在保證數據可用性的同時，需要對差分隱私保護前本文算法對于數據集的聚類性能進行評估，考慮使用規(guī)范化簇內方差（N
ormalized Intracluster Variance，NICV）衡量，但是傳統(tǒng)計算方法只針對數值型數據集有效，而對于混合型數據集聚類后的簇內方差計算需要進行合理推廣，其計算公式如下：
C
是簇的聚類中心，x
(a
)表示樣本x
的數值型屬性值，N
為簇內樣本總量，p
表示樣本數值型屬性個數，q
表示樣本分類型屬性個數，Pr(x
(a
))表示選中x
(a
)的概率。3.2 實驗結果與分析
實驗過程中，將數據集分別在本文提出算法與傳統(tǒng)DPk-means算法以及MDAV算法上運行。傳統(tǒng)DPkmeans算法在處理混合型數據集時沒有任何分類操作，對每一條記錄的每一項屬性不加區(qū)分地進行差分隱私保護處理；MDAV算法通過微聚類方式再結合差分隱私保護進行數據發(fā)布。
對Adult 數據集作預處理，將其分類型屬性取值歸一化處理到{0,1}上，將隱私保護預算ε
的值從0 提高到1.0。圖1 展示了在數據集上執(zhí)行3 種算法得到的數據誤差率，圖2則是NICV 值的比較，圖3 是在固定隱私保護預算ε
下，通過調節(jié)簇個數探究本文算法對于隱私信息的保護程度。
Fig.1 Data error rate of data set under different algorithms圖1 數據集在不同算法下的數據誤差率
Fig.2 Comparison of NICV values圖2 NICV 值比較
Fig.3 Privacy protection degree of the proposed algorithm when ε= 0.4圖3 ε= 0.4 時本文算法隱私保護程度
如圖1 所示，在相同ε
下，本文提出的差分隱私發(fā)布算法具有更低的誤差，且隨著ε
增加，誤差保持相對穩(wěn)定。因此，經過本文差分隱私發(fā)布算法處理的數據更接近原始數據，在數據挖掘中具有實際應用價值。由圖2 可以明顯看出，本文提出的發(fā)布算法在NICV 值上明顯小于其他兩種算法，并且隨著ε
的變化趨于穩(wěn)定，說明本文算法的聚類效果在處理混合型數據集時具有明顯優(yōu)勢。從圖3 可以看出，隨著發(fā)布數據初始聚類簇數的增加，原數據集的隱私保護效果逐漸提升，然而在實際實驗中，隨著簇數增加，算法運行時間明顯變長。這是因為簇數增加，聚類中心的選擇變多，需要向更多簇添加不同的差分隱私保護，從而增加了運行時間。在未來研究中，將著重降低簇數提升算法時間復雜度。4 結語
本文提出的面向混合型數據集的自適應聚類差分隱私保護算法，通過結合快速聚類算法、k-prototype 聚類算法的特性，能夠基于密度和距離，自適應確定初始聚類中心，對于分類型屬性和數值型屬性進行差別處理，使其滿足聚類要求，反復迭代完成混合型數據集的自適應聚類，再向聚類后的簇中心加入對應擾動因子以滿足差分隱私要求；在實現聚類高效處理的同時又能不過度降低數據有效性，從而達到保護隱私數據的目的。在此基礎上，通過探究在實驗數據集下初始簇個數變化，尋找數據可用性和隱私披露之間的平衡點，證明確實適用于混合數據集的差分隱私保護。
