基于自組織聚類的多敏感屬性數(shù)據(jù)發(fā)布算法

， ,

(1.北京電子科技學(xué)院 研究生部， 北京 100070； 2.西安電子科技大學(xué) 計(jì)算機(jī)學(xué)院， 陜西 西安 710071)

隨著數(shù)據(jù)挖掘技術(shù)的飛速發(fā)展以及數(shù)據(jù)擁有者對隱私數(shù)據(jù)泄露問題的高度關(guān)注，隱私數(shù)據(jù)發(fā)布技術(shù)不斷進(jìn)步。如何保證隱私數(shù)據(jù)在發(fā)布后敏感信息不易被攻擊，同時數(shù)據(jù)可挖掘性能夠得到極大保證，針對這一問題，國內(nèi)外學(xué)者給出了多種可行方案。

l-匿名模型[1]、l-多樣性模型[2]和l-closeness模型[3]是比較經(jīng)典的3種隱私保護(hù)模型。基于這些模型，許多算法被相繼提出[4-10]。這些算法在處理單敏感數(shù)據(jù)發(fā)布時雖然有可觀的抗攻擊性，但是不適用于多敏感數(shù)據(jù)發(fā)布。針對多敏感屬性數(shù)據(jù)發(fā)布隱私保護(hù)，楊曉春等[11]提出了基于有損鏈接的多維分桶技術(shù)，其將每一敏感值映射到對應(yīng)分桶，按照策略分組，實(shí)現(xiàn)組內(nèi)滿足l-多樣性。其他基于有損鏈接很多算法被提出[10-12]，但有損鏈接會破壞非敏感屬性與敏感屬性間的關(guān)聯(lián)關(guān)系，影響到發(fā)布后數(shù)據(jù)的信息可挖掘性。與有損鏈接的方法對比，無損鏈接的方法較好地保存了敏感數(shù)據(jù)與非敏感數(shù)據(jù)關(guān)聯(lián)性。基于無損鏈接的算法較少，文獻(xiàn)[13]中提出了基于l-多樣性模型的無損鏈接發(fā)布算法,但不適用于敏感屬性值多樣性差異過大的情況。為了解決該問題，本文中提出了(l,x,w)多樣性模型，該模型通過約束等價組內(nèi)敏感屬性多樣性及均勻性來實(shí)現(xiàn)匿名保護(hù)，并基于該模型提出了多敏感屬性數(shù)據(jù)發(fā)布的基于信息熵的l-多樣性聚類(entropy basedl-diversity clustering, EBLC)匿名算法。該算法按照非敏感屬性對數(shù)據(jù)進(jìn)行聚類后，在同簇中按照策略生成滿足多樣性的等價組，對等價組內(nèi)元組泛化后進(jìn)行發(fā)布。對該算法進(jìn)行仿真實(shí)驗(yàn)，通過運(yùn)行效率、信息損失等實(shí)驗(yàn)結(jié)果驗(yàn)證算法的匿名效果。

1 基本概念

對于一般待發(fā)布數(shù)據(jù)，針對其屬性可劃分為個人標(biāo)識屬性(individually identifying attribute, IIA)、準(zhǔn)標(biāo)識符屬性(quasi-identifier attribute, QIA)以及敏感屬性(sensitive attribute, SA)。IIA用于直接識別個人身份信息，QIA可結(jié)合外部數(shù)據(jù)識別個人信息，SA包含個體隱私信息。

設(shè)T={Q1,Q2, …,Qp,S1,S2, …,Sd}(p為分類性屬性個數(shù)，d為數(shù)值性屬性個數(shù))為待發(fā)布數(shù)據(jù)集，其中Qi(1≤i≤p)表示準(zhǔn)標(biāo)識符屬性，|Qi|表示敏感屬性Qi在T中不同值的個數(shù)。Sj(1≤j≤d)表示敏感屬性， |Sj|表示敏感屬性Sj在T中不同值的個數(shù)。T中有n個元組ti(1≤i≤n)，T的元組數(shù)目用|T|=n表示，對任意元組ti∈T，用ti、X表示元組ti在屬性X上的取值。

文獻(xiàn)[10]中提出了基于有損鏈接的(l1,l2, …,lm)模型，文獻(xiàn)[13]中提出了(l,m)多樣性模型。在文獻(xiàn)[10]中，(l1,l2, …,lm)模型與噪聲添加配合使用才能抵抗概率攻擊，但是引入的噪聲污染了數(shù)據(jù)，而文獻(xiàn)[13]中(l,m)模型不適用于敏感屬性值個數(shù)差異過大情況，特別是，當(dāng)某一個敏感屬性取值為2時，此時l的選取受到該敏感屬性候選值個數(shù)限制。本文中提出(l,x)多樣性模型用以解決此類問題。

定義2((l,x)多樣性)gi為T的一個等價組，對于任意敏感屬性Sj，多樣性變量x為

x=min{l, |Sj|}

。

(1)

若等價組gi在敏感屬性Sj上的不同取值數(shù)不小于x， 則稱等價組gi滿足(l,x)多樣性； 若對任意gi∈T，gi均滿足(l,x)多樣性， 則稱T滿足(l,x)多樣性。

敏感屬性信息如表1所示。當(dāng)l=3時，顯然年收入的屬性個數(shù)已經(jīng)無法滿足l-多樣性。

表1 敏感屬性信息

盡管也可以使用(l1,l2, …,lm)模型進(jìn)行數(shù)據(jù)匿名發(fā)布，但是該模型需要引入噪聲，這會污染數(shù)據(jù)。若使用(l,m)模型則需要調(diào)整使l=2，這樣使得發(fā)布后數(shù)據(jù)的安全性降低，無論使用以上哪種模型都不合適；而當(dāng)使用(l,x)多樣性模型在生成等價組時，只需要使敏感值多樣性小于l的敏感屬性滿足x多樣性即可。表2所示為一個l=3時的滿足(l,x)多樣性的等價組。

2 算法介紹

2.1 聚類生成

近些年來，基于聚類的敏感數(shù)據(jù)發(fā)布算法不斷發(fā)展[7,9-10,14-17]，但大多是基于有損鏈接或者單敏感屬性。其中文獻(xiàn)[18]中提出的(t, sim, dif)算法在抗概率攻擊以及同質(zhì)攻擊方面均有良好表現(xiàn)；但是，由于該算法是從敏感屬性部分生成聚類構(gòu)造等價組，同時，該算法為單敏感屬性數(shù)據(jù)發(fā)布算法，因此無法解決多敏感數(shù)據(jù)發(fā)布問題。基于文獻(xiàn)[18]中通過聚類尋找等價組思路，本文中提出了針對多敏感屬性數(shù)據(jù)發(fā)布的EBLC算法，由非敏感屬性生成聚類構(gòu)造等價組，通過對原數(shù)據(jù)進(jìn)行去噪點(diǎn)以及聚類劃分，在聚類基礎(chǔ)上生成滿足目標(biāo)約束的等價組，保證生成等價組有全局最優(yōu)信息損失與抗攻擊性。

表2 多樣性為3時滿足(l, x)多樣性的等價組

2.1.1 距離定義

本文中主要針對分類型數(shù)據(jù)及數(shù)值型數(shù)據(jù)進(jìn)行研究， 根據(jù)不同類型數(shù)據(jù)， 定義不同的距離度量公式。

定義3(非數(shù)值型屬性距離) 設(shè)屬性X為分類型屬性，按照不同取值構(gòu)建屬性值分層樹，設(shè)xi表示該屬性的某一取值，則距離函數(shù)為

Dclassi(xi,xj)=|1/flevel(xi,xj)-1/flevel(xi)|+

|1/flevel(xi,xj)-1/flevel(xj)| ，

(2)

式中：flevel(xi)表示分類值xi在分層樹中的層級；flevel(xi,xj)表示值xi、xj在分層樹中最小祖先節(jié)點(diǎn)的層級；Dclassi(xi,xj)表示屬性值xi與xj的分類距離。

定義4(數(shù)值型屬性距離) 設(shè)屬性X為數(shù)值型屬性，xi為該屬性的某一取值，則距離函數(shù)為

Ddigit(xi,xj)=|xi-xj|/(max{X}-min{X})，

(3)

式中：Ddigit(xi,xj)表示數(shù)值屬性值xi與xj的距離；max{X}表示屬性X最大值；min{X}表示屬性X的最小值。

定義5(元組距離) 元組ti、tj(i≠j)為表T的2個元組，則元組間距離函數(shù)為

(4)

2.1.2 聚類的生成算法

使用k均值的方法進(jìn)行聚類，考慮到傳統(tǒng)k均值方法的k值以及初始點(diǎn)的設(shè)定對聚類結(jié)果的影響，本文中使用自組織k均值算法(self-organizingk-means algorithm, SOKM) 。

算法1：自組織k均值算法。

輸入：元數(shù)據(jù)集表T、 停止條件δ。

輸出：數(shù)據(jù)集聚類信息表T′。

1) 令聚類數(shù)目Cnum=1，T′記錄T的簇劃分以及簇中心距離信息，令可移動元組數(shù)目Cmove=|T|，對原數(shù)據(jù)集T使用二分k均值算法進(jìn)行二分;

2) 遍歷當(dāng)前所有分簇，對每一個分簇進(jìn)行二分聚類，對比其他簇中元組與其原簇質(zhì)心距離與新生簇質(zhì)心的距離，將該元組劃入距離近的一簇，統(tǒng)計(jì)每一次二分后移動的元組數(shù)目，選擇移動數(shù)目多的簇進(jìn)行二分；

3) 令Cmove等于元組最大移動數(shù)目，令Cnum+1，并更新T′；

4) 檢查Cmove與δ，當(dāng)Cmove小于δ時停止分裂，輸出T′，否則重復(fù)步驟2)和3)直到滿足停止條件。

考慮到離群點(diǎn)對匿名算法的影響，在聚類部分對離群點(diǎn)進(jìn)行處理，計(jì)算所有簇的半徑，依據(jù)半徑設(shè)定離群點(diǎn)判定閾值，當(dāng)超出該閾值則判定為離群點(diǎn)，劃入簇0中。

2.2 算法核心介紹

2.2.1 (l,x,w)多樣性

信息熵常被用來描述信源的不確定度。為了提升發(fā)布數(shù)據(jù)抗同質(zhì)攻擊以及概率攻擊的能力，在生成等價組時使用信息熵作為策略之一。

(5)

定義7(敏感標(biāo)準(zhǔn)熵) 設(shè)gi為一滿足(l,x)多樣性的等價組， 對于任意敏感屬性Sj， 其標(biāo)準(zhǔn)熵函數(shù)為

(6)

當(dāng)?shù)葍r組gi中敏感屬性Sj的多樣性數(shù)目為x時，可知其敏感標(biāo)準(zhǔn)熵為其信息熵的最大值，此時該屬性的不確定度最大。

定義8((l,x,w)多樣性) 設(shè)gi為一滿足(l,x)多樣性的等價組， 對于任意敏感屬性Sj，若等價組中該敏感屬性敏感信息熵與敏感標(biāo)準(zhǔn)熵之比不小于w，則稱等價組gi滿足(l,x,w)多樣性，若T中所有等價組均滿足(l,x,w)多樣性，則稱T滿足(l,x,w)多樣性。

EBLC算法即對原始數(shù)據(jù)集T在聚類劃分得到T′后， 分簇尋找滿足(l,x,w)多樣性的等價組， 最后對同一等價組按分組中心泛化， 最終得到發(fā)布數(shù)據(jù)集T*。 對于泛化后產(chǎn)生的信息損失， 給出以下定義。

定義9(等價組信息損失) 設(shè)gi為一滿足(l,x,w)多樣性的等價組，t為等價組中的元組，t′為等價組組中心，定義等價組泛化信息損失函數(shù)為

(7)

定義10(全局信息損失) 設(shè)T*為數(shù)據(jù)集處理后得到的滿足(l,x,w)多樣性的待發(fā)布數(shù)據(jù)集，其等價組集合G={g1,g2, …,gs}，全局信息損失函數(shù)為

(8)

定義11(平均信息損失)T*為數(shù)據(jù)集T處理后得到的滿足(l,x,w)多樣性的待發(fā)布數(shù)據(jù)集，Iinfoloss(T*)為全局信息損失，則平均信息損失函數(shù)為

ηinfoloss(T*)=Iinfoloss(T*)/|T*|

，

(9)

式中|T*|為數(shù)據(jù)集T*的元組數(shù)目。

2.2.2 基于信息熵的多樣性聚類匿名算法

算法2：EBLC算法。

輸入：元數(shù)據(jù)集T、 聚類信息T′、 多樣性l、 敏感熵比值w。

輸出：可發(fā)布數(shù)據(jù)表T*。

1) 獲取表T所有敏感屬性的多樣性集L={l1,l2, …,ld}；

2) 由T′得到所有的簇集合信息C={c1,c2, …,ck}，按照簇半徑進(jìn)行升序排序得到半徑信息矩陣R；

3) 分別計(jì)算所有簇中心距離，并按照升序排序，得到簇間距離信息矩陣N，令T*為空，并依據(jù)T′得到所有簇的半徑升序矩陣Cradius；

4) 選擇當(dāng)前簇集中半徑最小的簇作為等價組生成簇ci，令等價組gtmp為空;

5) 當(dāng)ci中元組數(shù)目大于l時，按照第1次添加l條元組，第1次之后每次添加1條元組的原則向空的gtmp中添加記錄，每次添加后檢查gtmp是否滿足(l,x,w)并刪除ci中對應(yīng)元組；

6) 當(dāng)gtmp滿足(l,x,w)多樣性時將gtmp中元組添加到T*，并清空gtmp；

7) 重復(fù)步驟5)和6)直到ci為空并從C中刪除當(dāng)前ci；

8) 此時若gtmp非空則選擇剩余簇中質(zhì)心與當(dāng)前ci質(zhì)心最近的簇作為新的ci，若gtmp為空則對照Cradius與C選擇C中半徑最小的簇最為新的ci；

9) 重復(fù)步驟5)到8)直到C為空，得到T*，對T*中元組按照不同等價組質(zhì)心對其進(jìn)行泛化后發(fā)布T*。

2.3 基于信息熵的多樣性聚類匿名算法復(fù)雜度分析

本算法對數(shù)據(jù)匿名處理分為2個部分即聚類及等價組的生成。

聚類部分的每一次二分可分為記錄重劃分以及簇二分2個部分， 這2個部分每一次的時間復(fù)雜度分別為O(n-ni)和O(nit),其中ni為當(dāng)前遍歷簇大小，t為二分聚類的平均迭代次數(shù)； 遍歷所有簇的時間復(fù)雜度為O[nt+n(ktmp-1)]， 其中ktmp為每一次遍歷時的分簇總數(shù)； 聚類部分的時間復(fù)雜度為O(nkt+nk2)， 其中k為最終的分簇數(shù)目。

等價組生成部分復(fù)雜度最壞情況為O(n2)，最優(yōu)情況為O(n)，因此，EBLC算法復(fù)雜度最壞情況為O[n(kt+k2+n)]，最優(yōu)情況為O[n(kt+k2+1)]。

2.4 基于信息熵的多樣性聚類匿名算法抗攻擊分析

由于等價組滿足(l,x,w)多樣性， 因此任意等價組內(nèi)元組t， 對任意敏感屬性Si， 可以保證至少存在x-1條元組與t在屬性Si上的取值不同，保證了發(fā)布后數(shù)據(jù)的抗同質(zhì)攻擊能力。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)方案

為了驗(yàn)證EBLC算法有效性，通過仿真實(shí)驗(yàn)，對EBLC算法進(jìn)行實(shí)現(xiàn)，從執(zhí)行時間、信息泄露、信息損失等方面評估EBLC算法的性能，實(shí)驗(yàn)結(jié)果為30次實(shí)驗(yàn)的平均值。硬件環(huán)境為Intel(R) Core(TM)i3-3240CPU@3.40GHz 4.00GB RAM。實(shí)驗(yàn)軟件環(huán)境為Windows10平臺、 MATLAB2016a軟件。

3.2 實(shí)驗(yàn)數(shù)據(jù)

使用匿名算法研究領(lǐng)域通用的標(biāo)準(zhǔn)測試數(shù)據(jù)集，即UCI Machine Learning Repository中的Adult標(biāo)準(zhǔn)數(shù)據(jù)集。

實(shí)驗(yàn)選取的屬性集合如表3、 4所示

表3 實(shí)驗(yàn)數(shù)據(jù)集信息

表4 敏感屬性候選信息

3.3 實(shí)驗(yàn)結(jié)果

3.3.1 運(yùn)行效率

圖1所示為敏感屬性m=3、多樣性l=4、信息熵比率w=0.75時，數(shù)據(jù)量級改變條件下算法的運(yùn)行時間。觀察發(fā)現(xiàn)：隨著數(shù)據(jù)量的增加，算法的運(yùn)行時間隨之增加；同時，等價組生成部分的運(yùn)行時間較短，聚類部分的運(yùn)行時間長，但運(yùn)行時間仍然在可以接受范圍內(nèi)。

圖1還給出了平均信息損失隨數(shù)據(jù)量增長時的變化情況。從圖中發(fā)現(xiàn)，數(shù)據(jù)量級的改變對平均信息損失沒有明顯的影響。

3.3.2 敏感屬性數(shù)目改變時算法信息損失

圖2所示為數(shù)據(jù)量為4 000、多樣性l=4時，EBLC算法在不同敏感屬性以及信息熵比下信息損失的變化情況。從圖中可以發(fā)現(xiàn)，在不同敏感屬性下，當(dāng)信息熵比率控制在0.65時其平均信息損失不超過0.45，表明算法在抗攻擊性以及信息損失方面均有良好表現(xiàn)。同時可以看出：在相同信息熵比下， 平均信息損失與敏感屬性數(shù)目呈現(xiàn)正相關(guān)關(guān)系； 在敏感屬性數(shù)目相同時， 平均信息損失也與信息熵比呈正相關(guān)關(guān)系。

圖1 基于信息熵的l多樣性聚類算法的運(yùn)行時間

圖2 敏感屬性數(shù)目變化時的信息損失

為了使新增加的敏感屬性滿足多樣性要求，在同等條件下，當(dāng)敏感屬性數(shù)目增多時，原等價組元組可能需要添加新的元組，這會造成組內(nèi)非敏感屬性的泛化程度提高，帶來了更多的信息損失。同時，當(dāng)信息熵比率上升時，等價組中同一屬性的多樣性分布均勻度需要提升，也會導(dǎo)致原等價組元組數(shù)目的增加，造成非敏感屬性泛化程度提高，導(dǎo)致平均信息損失的增加。

3.3.3 多樣性數(shù)目改變時算法信息損失

圖3所示為數(shù)據(jù)量為4 000、敏感屬性個數(shù)m=3時，EBLC算法在不同多樣性以及信息熵比下信息損失的變化情況。從圖中可以發(fā)現(xiàn)，在不同多樣性條件下，當(dāng)信息熵比率控制在0.65時，數(shù)據(jù)的平均信息損失不超過0.5，表明算法在抗攻擊性以及信息損失方面均表現(xiàn)良好。同時可以看出：在相同信息熵比下， 平均信息損失與多樣性數(shù)目呈現(xiàn)正相關(guān)關(guān)系；在多樣性數(shù)目相同時，平均信息損失也與信息熵比呈正相關(guān)關(guān)系。

圖3 多樣性數(shù)目變化時的信息損失

在信息熵相同、多樣性數(shù)目增長時，原等價組需要添加新的多樣性元組，會造成泛化程度提高，引起平均信息損失的增加。當(dāng)多樣性數(shù)目不變而信息熵比提高時，為了提高等價組內(nèi)敏感屬性多樣性的均勻性，也需要向等價組添加新的元組，造成平均信息損失的增加。

4 結(jié)語

本文中基于對原數(shù)據(jù)集進(jìn)行聚類分簇后從同簇內(nèi)元組生成滿足(l,x,w)等價組的思路，提出了一種針對多敏感屬性數(shù)據(jù)隱私發(fā)布的ELBC匿名算法，并對其進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明：該算法有效降低了發(fā)布后數(shù)據(jù)敏感信息易受到同質(zhì)攻擊以及概率攻擊的風(fēng)險，提升了數(shù)據(jù)發(fā)布的安全性；算法在不同敏感屬性數(shù)目以及不同多樣性數(shù)目條件下對數(shù)據(jù)進(jìn)行匿名發(fā)布后，數(shù)據(jù)的信息損失仍然能保證在可靠范圍內(nèi)，較大程度保證了發(fā)布數(shù)據(jù)的可挖掘價值。不足之處是本文中等價組內(nèi)屬性的l-多樣性為語法的多樣性，在下一步工作中，將會更多地進(jìn)行基于語義多樣性的算法研究。