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

， ,

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

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

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

1 基本概念

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

設(shè)T={Q1,Q2, …,Qp,S1,S2, …,Sd}(p為分類(lèi)性屬性個(gè)數(shù)，d為數(shù)值性屬性個(gè)數(shù))為待發(fā)布數(shù)據(jù)集，其中Qi(1≤i≤p)表示準(zhǔn)標(biāo)識(shí)符屬性，|Qi|表示敏感屬性Qi在T中不同值的個(gè)數(shù)。Sj(1≤j≤d)表示敏感屬性， |Sj|表示敏感屬性Sj在T中不同值的個(gè)數(shù)。T中有n個(gè)元組ti(1≤i≤n)，T的元組數(shù)目用|T|=n表示，對(duì)任意元組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)模型不適用于敏感屬性值個(gè)數(shù)差異過(guò)大情況，特別是，當(dāng)某一個(gè)敏感屬性取值為2時(shí)，此時(shí)l的選取受到該敏感屬性候選值個(gè)數(shù)限制。本文中提出(l,x)多樣性模型用以解決此類(lèi)問(wèn)題。

定義2((l,x)多樣性)gi為T(mén)的一個(gè)等價(jià)組，對(duì)于任意敏感屬性Sj，多樣性變量x為

x=min{l, |Sj|}

。

(1)

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

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

表1 敏感屬性信息

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

2 算法介紹

2.1 聚類(lèi)生成

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

表2 多樣性為3時(shí)滿(mǎn)足(l, x)多樣性的等價(jià)組

2.1.1 距離定義

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

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

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

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

(2)

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

定義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個(gè)元組，則元組間距離函數(shù)為

(4)

2.1.2 聚類(lèi)的生成算法

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

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

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

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

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

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

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

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

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

2.2 算法核心介紹

2.2.1 (l,x,w)多樣性

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

(5)

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

(6)

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

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

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

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

(7)

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

(8)

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

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

，

(9)

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

2.2.2 基于信息熵的多樣性聚類(lèi)匿名算法

算法2：EBLC算法。

輸入：元數(shù)據(jù)集T、 聚類(lèi)信息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)前簇集中半徑最小的簇作為等價(jià)組生成簇ci，令等價(jià)組gtmp為空;

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

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

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

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

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

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

本算法對(duì)數(shù)據(jù)匿名處理分為2個(gè)部分即聚類(lèi)及等價(jià)組的生成。

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

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

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

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

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

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

為了驗(yàn)證EBLC算法有效性，通過(guò)仿真實(shí)驗(yàn)，對(duì)EBLC算法進(jìn)行實(shí)現(xiàn)，從執(zhí)行時(shí)間、信息泄露、信息損失等方面評(píng)估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平臺(tái)、 MATLAB2016a軟件。

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

使用匿名算法研究領(lǐng)域通用的標(biāo)準(zhǔn)測(cè)試數(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í)，數(shù)據(jù)量級(jí)改變條件下算法的運(yùn)行時(shí)間。觀察發(fā)現(xiàn)：隨著數(shù)據(jù)量的增加，算法的運(yùn)行時(shí)間隨之增加；同時(shí)，等價(jià)組生成部分的運(yùn)行時(shí)間較短，聚類(lèi)部分的運(yùn)行時(shí)間長(zhǎng)，但運(yùn)行時(shí)間仍然在可以接受范圍內(nèi)。

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

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

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

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

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