丁永紅

?

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

丁永紅

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

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

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

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

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

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

1）對任意t∈,存在與對應；

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

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

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

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

2）當q為分類型屬性是，f(u)=H,H為與q對應的域泛化結構中u的上層節(jié)點．

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

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

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

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

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

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

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

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

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

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

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

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

2.1 基本思想

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

2.2 算法實現(xiàn)

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

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

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

While≠ do

從中讀取一個元組加入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

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

Set

While |Set|≥do

從Set中隨機選擇一個元組

計算剩余|Set|-1個元組與的距離，并按照距離從小到大排序，選出前-1個和的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

對于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中隨機選擇一個簇C

If Infoloss(C)C) then

用C的泛化輸出t

從C中刪除t，并重新計算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 實驗及結果分析

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

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

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

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

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

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

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

圖1 CASTLE和FCADS在第一組實驗中的平均信息損失

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

對于第一組實驗，關于運行時間的結果如圖2所示：

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

圖2 CASTLE和FCADS在第一組實驗的運行時間

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

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

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

圖3 FAANST和FCADS在第二組實驗中的平均信息損失

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

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

在第二組實驗中，關于FAANST和FCADS兩種算法在運行時間上的影響如圖4所示：

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

圖4 FAANSTA和FCADS在第二組實驗中的運行時間

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

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

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

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

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

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

（責任編輯：涂正文）

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)合大學計算機系講師，主要研究計算機網(wǎng)絡技術．

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