基于聚類分析的數(shù)據(jù)流隱私保護(hù)算法

丁永紅

?

基于聚類分析的數(shù)據(jù)流隱私保護(hù)算法

丁永紅

（淮南聯(lián)合大學(xué)，安徽淮南 232001）

由于數(shù)據(jù)流具有無限、流動(dòng)迅速、變化頻繁的特點(diǎn)，因此，在進(jìn)行對(duì)其隱私保護(hù)時(shí)存在很大的困難．針對(duì)數(shù)據(jù)流的隱私保護(hù)，文章首先分析了數(shù)據(jù)流匿名隱私保護(hù)的特點(diǎn)，然后進(jìn)行算法的實(shí)施，及實(shí)驗(yàn)結(jié)果和分析．

聚類；數(shù)據(jù)流；隱私；保護(hù)算法；匿名

1 數(shù)據(jù)流的匿名隱私保護(hù)

社會(huì)經(jīng)濟(jì)快速發(fā)展導(dǎo)致數(shù)據(jù)存儲(chǔ)的爆炸式增長，時(shí)常會(huì)造成隱私泄露，甚至更嚴(yán)重后果[1]．為了防止信息被泄露而將一些敏感信息匿名隱藏起來，從而形成新的數(shù)據(jù)流，但是要確保數(shù)據(jù)的不變性和可用性，就不能單單地對(duì)敏感數(shù)據(jù)進(jìn)行隱藏和刪除，只能進(jìn)行一定意義和一定程度上的修改．對(duì)于數(shù)據(jù)匿名流的定義有許多種，大致分為以下幾個(gè)：（設(shè)原始數(shù)據(jù)為，輸出的新的數(shù)據(jù)流為，且新數(shù)據(jù)流中元組的輸出時(shí)延不超過δ）

定義1：匿名數(shù)據(jù)流，設(shè)數(shù)據(jù)流的屬性序列為(pid,a,a,…,a,q,q,…,q,ts)，其中pid為用戶身份標(biāo)識(shí)，q,q,…,q為準(zhǔn)標(biāo)識(shí)符屬性，a,a,…,a為其他屬性，為元組到達(dá)時(shí)刻，為由生成的匿名數(shù)據(jù)流，其中屬性id和被隱去，映射,若滿足：

1）對(duì)任意t∈,存在與對(duì)應(yīng)；

2）對(duì)任意，|DP(EQ)|≥,EP=·q·q,i=1,…,n},DP(EQ)為EQ（t'）中元組對(duì)應(yīng)的pid屬性不同的用戶組成的集合，則稱為匿名數(shù)據(jù)流．

定義2：時(shí)延約束，設(shè)有數(shù)據(jù)流匿名方法，若輸出的匿名數(shù)據(jù)流，滿足任意為原數(shù)據(jù)流中與對(duì)應(yīng)的元組，為給定正整數(shù)，則稱滿足時(shí)延約束．

定義3：元組泛化．設(shè)元組t(pid,u,u,…,u,u,u,…u,ts的泛化為g,g,…,g)=(f(u),f(u),…,f(u)),則：

1）當(dāng)q為數(shù)值型屬性時(shí)，f(u)=[r,r],u∈[r,r]；

2）當(dāng)q為分類型屬性是，f(u)=H,H為與q對(duì)應(yīng)的域泛化結(jié)構(gòu)中u的上層節(jié)點(diǎn)．

定義4：簇泛化．設(shè)g(g,g,…,g)為簇的泛化，則：

1）q為數(shù)值性屬性時(shí)，g=[r,r]r和r，分別為簇中所有元組在屬性q上的最小值和最大值．

2）q為分類型屬性時(shí)，g=H,H為簇中所有元組在屬性q的DGH上節(jié)點(diǎn)的共同最低父節(jié)點(diǎn)．

定義5：匿名簇．若簇滿足：

1）|DP(C)|≥,DP(C)為簇中元組對(duì)應(yīng)的pid屬性值不同的用戶組成的集合；

2）任意=g,t'為匿名后數(shù)據(jù)流中與對(duì)應(yīng)的元組，g為簇的泛化．則稱簇為匿名簇

定義6：元組泛化信息損失．元組t(pid,u,u,…,u,u,u,…u,ts)泛化為g,g,…,g后的信息損失為：，．

當(dāng)屬性為數(shù)值型屬性時(shí)，信息的損失為元組在該屬性上泛化后區(qū)間[r,r]的長度與該屬性值域[R,R]的比值；當(dāng)屬性值為分類型屬性時(shí)，信息損失為元組在該屬性上泛化后對(duì)應(yīng)的節(jié)點(diǎn)．

定義7：簇泛化信息損失．簇泛化為g(g,g,…,g后的信息損失為：

定義8：數(shù)據(jù)流泛化平均信息損失．設(shè)g為元組t的泛化，則數(shù)據(jù)流在時(shí)刻t的平均信息損失為：

定義9：簇信息損失增量．簇在加入元組后產(chǎn)生的信息損失增量為：Enlargement(C,t)=Infoloss(C',gc')-Infoloss(C,gc)，其中：為增加元組之后的簇，表示為泛化后的簇．

2 基于聚類的數(shù)據(jù)流匿名算法

2.1 基本思想

數(shù)據(jù)流的匿名算法是一種很特殊的算法，而為了滿足這種特殊的要求，提出了三個(gè)基本原則：其一，無限和快速到達(dá)是數(shù)據(jù)流的兩個(gè)特點(diǎn)，而數(shù)據(jù)流的算法在進(jìn)行計(jì)算時(shí)只對(duì)數(shù)據(jù)流掃描一遍，并且所需的時(shí)間要在一定范圍內(nèi)[2]；其二，由于數(shù)據(jù)流有無限的特點(diǎn)，算法空間復(fù)雜度以一個(gè)常數(shù)為上界，而與反應(yīng)時(shí)間無關(guān)；其三，對(duì)于已發(fā)布的新的數(shù)據(jù)流要重復(fù)利用，降低因?qū)π畔⒛涿a(chǎn)生的損失．

2.2 算法實(shí)現(xiàn)

根據(jù)FCADS對(duì)數(shù)據(jù)流匿名計(jì)算，在滿足算法基本框架的基礎(chǔ)上，能夠?qū)?shù)據(jù)流進(jìn)行匿名計(jì)算．首先輸入數(shù)據(jù)流、屬性集、匿名參數(shù)和發(fā)布時(shí)延以及信息損失下限；輸出結(jié)果為滿足匿名參數(shù)匿名要求的新數(shù)據(jù)流．

Set為待發(fā)布元組集，初始化為空集

Set為已發(fā)布匿名簇集，初始化為空集

While≠ do

從中讀取一個(gè)元組加入Set

If |Set|≥then

Set=greedy Condense ( )

Output With Work Cluster Or Condensation

end

end while

if |Set|≥k then

Set=greedy Condense ( )

Output With Work Cluster Or Condensation (Set)

else

將Set中的所有元組抑制后輸出，并從中刪除已輸出元組

end if

對(duì)于greedy Condense ( )函數(shù)則有下列程序

Set

While |Set|≥do

從Set中隨機(jī)選擇一個(gè)元組

計(jì)算剩余|Set|-1個(gè)元組與的距離，并按照距離從小到大排序，選出前-1個(gè)和的pid值不同的元組，與組成新簇

將C加入Set

從Set中刪除C包含的元組

end while

if |Set|≥0 then

for each ti∈Setdo

在Set中查找加入t后信息損失的增量最小的簇

將t加入C

從Set中刪除t

end foreach

end if

返回Set

對(duì)于output With Work Cluster Or Condensation ()的程序如下

Output With Work Cluster Or Condensation (Set)

for eachC∈Setdo

for eachtCdo

Set

在Set中查找所有覆蓋t且簇信息損失增量最小的簇

將找到的簇添加到Set

ifSet≠then

從Set中隨機(jī)選擇一個(gè)簇C

If Infoloss(C)C) then

用C的泛化輸出t

從C中刪除t，并重新計(jì)算C的泛化

end if

end if

從Set中刪除t

end foreach

If |C|≥k then

用C的泛化輸出t

In Infoloss (C)

If |Set|≥cs/kthen

刪除Set中最早生成的簇

end if

將C加入Set

end if

else

用C的泛化輸出C中所有元組

end if

end for each

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

對(duì)于本文所用的算法的性能，可通過實(shí)驗(yàn)進(jìn)行分析,并參與CASTLE算法的比較．在進(jìn)行實(shí)驗(yàn)時(shí)，所采用的數(shù)據(jù)集是被隱私文獻(xiàn)廣受歡迎的UCI的Adult數(shù)據(jù)集．實(shí)驗(yàn)所選用的屬性集合為中的一部分，且這些屬性集合中的前6個(gè)和后4個(gè)分別為數(shù)值型屬性和分類型屬性．

當(dāng)數(shù)據(jù)量和參數(shù)變化時(shí)，實(shí)驗(yàn)要記錄變化所帶來的平均信息損失和運(yùn)行時(shí)間，對(duì)于平均信息損失，可以運(yùn)用以下公式來計(jì)算：

為了彌補(bǔ)FAANST只能進(jìn)行數(shù)值型數(shù)據(jù)的處理，而不能對(duì)算法的性能進(jìn)行充分的測試，特設(shè)計(jì)兩組實(shí)驗(yàn)：第一組實(shí)驗(yàn)用于對(duì)新算法和CASTLE算法的測試；第二組實(shí)驗(yàn)用于對(duì)新算法、CASTLE和FAANST算法的測試[3]．兩組實(shí)驗(yàn)的屬性都從以上給出的十個(gè)屬性中選取，而第二組實(shí)驗(yàn)所用的屬性值均為數(shù)值型屬性．

首先進(jìn)行第一組實(shí)驗(yàn)，其中各算法的參數(shù)如表1所示，c0取1.

表1 第一組實(shí)驗(yàn)的算法參數(shù)表

進(jìn)行第一組實(shí)驗(yàn)，并將實(shí)驗(yàn)關(guān)于平均信息損失的結(jié)果以圖表的形式表現(xiàn)出來，如圖1所示．

（a）隨數(shù)據(jù)流大小變化 （b）隨值變化 （c）隨δ值變化 （d）隨屬性數(shù)量變化

圖1 CASTLE和FCADS在第一組實(shí)驗(yàn)中的平均信息損失

從圖1中我們可知：當(dāng)數(shù)據(jù)流的大小、值、δ值和屬性的數(shù)量發(fā)生變化時(shí)，CASTLE算法的平均信息損失都普遍高于FCADS算法．由圖1中（a）圖可知，數(shù)據(jù)流大小對(duì)兩種算法的平均信息損失的影響都很小，且數(shù)據(jù)流越大兩種算法對(duì)平均信息損失的影響越趨于平緩．由圖1中（b）圖可知，值的變化對(duì)兩種算法對(duì)平均信息損失的影響較大，且值越大，即元組越多，兩種算法對(duì)平均信息損失的影響也就越大[4]．由圖1中（c）圖可知，δ值越大，兩種算法對(duì)平均信息損失產(chǎn)生的影響越小，且最后趨于平緩，但前期的影響較大．由圖1中（d）圖可知，兩種算法對(duì)平均信息損失量隨屬性的數(shù)量增多而增多．總的來說，從圖1中可以知道，對(duì)于CASTLE和FCADS這兩種算法對(duì)平均信息損失，值和值的影響很大．

對(duì)于第一組實(shí)驗(yàn)，關(guān)于運(yùn)行時(shí)間的結(jié)果如圖2所示：

（a）隨數(shù)據(jù)流大小變化 （b）隨值變化 （c）隨δ值變化 （d）隨屬性數(shù)量變化

圖2 CASTLE和FCADS在第一組實(shí)驗(yàn)的運(yùn)行時(shí)間

由圖2可知，當(dāng)數(shù)據(jù)流大小、值、δ值和屬性的數(shù)量發(fā)生變化時(shí)，CATLE的運(yùn)行時(shí)間總比FCADS的運(yùn)行時(shí)間長．由圖2中（a）圖可知，隨著數(shù)據(jù)流的增長，CASTLE和FCADS的運(yùn)行時(shí)間成正比例增長，且CASTLE受數(shù)據(jù)流影響較大．由圖2中（b）圖可知，當(dāng)值較小時(shí)，值對(duì)CASTLE算法關(guān)于時(shí)間的影響較大，且成遞增趨勢，當(dāng)值越大時(shí)，其變化越小，但總體是遞增的；對(duì)于FCADS算法對(duì)運(yùn)行時(shí)間來說，值是有上限的．由圖2中（c）圖可以看出δ值的變化對(duì)CASTLE的影響較大，且CASTLE算法的反應(yīng)時(shí)間隨δ值的增大而增大，F(xiàn)CADS幾乎不受δ的影響．由圖2中（d）所示，屬性的數(shù)量幾乎不影響FCADS算法的運(yùn)行時(shí)間，但是對(duì)CASTLE算法的運(yùn)行時(shí)間的影響比較大，且隨著屬性數(shù)量的增加，CASTLE算法的運(yùn)行時(shí)間也在不斷的增加．

進(jìn)行第二組實(shí)驗(yàn)時(shí)，對(duì)FAANST和FCADS兩種算法的參數(shù)?。?100，屬性數(shù)量為6，δ=10 000，τ=0.5，c取1.則關(guān)于第二組實(shí)驗(yàn)中，兩種算法對(duì)平均信息損失的影響如圖3所示：

（a）隨數(shù)據(jù)流大小變化 （b）隨值變化 （c）隨δ值變化 （d）隨屬性數(shù)量變化

圖3 FAANST和FCADS在第二組實(shí)驗(yàn)中的平均信息損失

由圖3可知：在數(shù)據(jù)流大小、值、值和屬性的數(shù)量影響因素下，F(xiàn)AANST和FCADS兩種算法的平均信息損失的影響相差較小，且平均信息損失隨數(shù)據(jù)流的增加以及的增加而減少，隨值的增加和屬性數(shù)量的增加而增加．經(jīng)兩種算法的比較，F(xiàn)CADS算法對(duì)平均信息的損失影響相對(duì)FAANST算法而言要小．

通過圖1與圖3比較可得：在只有數(shù)值型的數(shù)據(jù)流中數(shù)據(jù)流的大小和值的變化對(duì)平局信息損失的影響與含有多種屬性數(shù)據(jù)流的變化是相同的，在數(shù)據(jù)流大小和值方面，分類型數(shù)據(jù)比數(shù)值型數(shù)據(jù)更敏感．

在第二組實(shí)驗(yàn)中，關(guān)于FAANST和FCADS兩種算法在運(yùn)行時(shí)間上的影響如圖4所示：

（a）隨數(shù)據(jù)流大小變化 （b）隨值變化 （c）隨δ值變化 （d）隨屬性數(shù)量變化

圖4 FAANSTA和FCADS在第二組實(shí)驗(yàn)中的運(yùn)行時(shí)間

由圖4可知：FAANSTA算法的運(yùn)行時(shí)間普遍大于FCADS算法的運(yùn)行時(shí)間，即FCADS算法的運(yùn)行速度快于FAANSTA算法的運(yùn)行速度，且數(shù)據(jù)流量越大，兩種算法運(yùn)行的速度差越大．FAANSTA和FCADS兩種算法的運(yùn)行時(shí)間隨數(shù)據(jù)流、值和屬性數(shù)量的值增大都增大，隨值的增大都減?。ㄟ^圖4和2比較可知：在只有數(shù)值型和混合型的數(shù)據(jù)流中，數(shù)據(jù)流大小和值對(duì)算法運(yùn)行時(shí)間的影響是一致的．

做好隱私保護(hù)就要不斷加強(qiáng)對(duì)數(shù)據(jù)流的保護(hù)．隨著經(jīng)濟(jì)與科技的發(fā)展，隱私的泄露還存在著很大的隱患，因此要不斷加強(qiáng)隱私的安全保護(hù)．

[1] 翟國富，陳金豹，邢通.基于聚類分析的航天繼電器多余物檢測方法研究[J].振動(dòng)與沖擊，2013（2）.

[2] 李征.基于動(dòng)態(tài)膜計(jì)算的聚類算法[D].鄭州：河南大學(xué)，2013.

[3] 彭顯剛，賴家文，陳奕.基于聚類分析的客戶用電模式智能識(shí)別方法[J].電力系統(tǒng)保護(hù)與控制，2014（19）.

[4] 羅養(yǎng)霞，房鼎益.基于聚類分析的軟件胎記特征選擇[J].電子學(xué)報(bào)，2013（12）.

（責(zé)任編輯：涂正文）

Data Stream Privacy Protection Algorithm Based on Clustering Analysis

DING Yonghong

with the development of economy and technology, privacy leakage has become a hidden danger which is badly in need of an effective protection. Because of the characteristics of data stream, such as limitlessness, rapid flow, and frequent changes, it is very difficult to prevent the leakage of privacy. This paper first analyzes the characteristics of anonymity privacy protection of the data stream, and then carries out the implementation of the algorithm, following with the experimental results and analysis.

clustering; data stream; privacy; protection algorithm; anonymity

TP311

A

1009-8135（2016）03-0033-05

2016-02-20

丁永紅（1975-），男，安徽安慶人，安徽淮南聯(lián)合大學(xué)計(jì)算機(jī)系講師，主要研究計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)．

中國民航信息技術(shù)科研基地開放基金課題：基于函數(shù)依賴的民航大數(shù)據(jù)共享與隱私保護(hù)研究（編號(hào)：CAAC-ITRB-201404）階段性成果