基于差異化聚類的分級(jí)隱私保護(hù)數(shù)據(jù)發(fā)布方法

劉海

（浙江金融職業(yè)學(xué)院經(jīng)營管理系，浙江杭州310018）

隨著計(jì)算機(jī)技術(shù)的不斷發(fā)展，許多與個(gè)體相關(guān)的信息在計(jì)算機(jī)上存儲(chǔ)，并且廣泛的被應(yīng)用于大量科學(xué)研究領(lǐng)域.這些與個(gè)體相關(guān)的信息，絕大多數(shù)是不需要進(jìn)行隱私保護(hù)的.而需要保護(hù)的僅僅是其中一些擁有特殊敏感信息的個(gè)體，比如在醫(yī)療信息表中，如果某人的疾病是癌癥或艾滋病，則對(duì)此類個(gè)體信息就應(yīng)該進(jìn)行保護(hù)，而絕大多數(shù)人得的是感冒、咳嗽等疾病，個(gè)體敏感信息的暴露并不會(huì)帶來很大的危害性.另一方面，對(duì)包含特殊敏感信息的個(gè)體，其保護(hù)也應(yīng)具有層次的差別，還是以醫(yī)療信息表為例，對(duì)某人得的是癌癥或艾滋病，因其傳染性等諸多不同，我們對(duì)其的保護(hù)程度也應(yīng)該有所不同.近年來，隱私保護(hù)數(shù)據(jù)發(fā)布也逐漸成為了學(xué)術(shù)研究的熱點(diǎn)，許多學(xué)者也提出各種隱私保護(hù)數(shù)據(jù)發(fā)布的模型.Sweeney L[1]等早在2002年就提出了利用k-匿名模型來解決隱私保護(hù)數(shù)據(jù)發(fā)布相關(guān)問題.該模型將數(shù)據(jù)集分為若干個(gè)簇，每個(gè)簇中元素至少K個(gè)，且簇中元素具有不可區(qū)分性.Machanavajjhala A[2]等在2006年于k-匿名的基礎(chǔ)上提出了L差異化，該模型要求在每個(gè)簇中至少含有L個(gè)well-pres?ent的敏感屬性，通過這種方式解決k-匿名中存在的同質(zhì)攻擊和背景知識(shí)攻擊的缺陷.Xiao Xiaokui[3]等在2007年提出了面向多次數(shù)據(jù)發(fā)布的隱私保護(hù)m-invariance模型，該模型通過保持在在每次數(shù)據(jù)發(fā)布簇中各屬性所占比例的不變性來進(jìn)行隱私保護(hù).Li NingHui[4]等在2007年提出了t-closeness模型，該模型提出每個(gè)簇中的敏感元組的分布應(yīng)該接近于該屬性的全局分布.楊曉春[5]等在2008年提出了多維桶模型，并設(shè)計(jì)了三種優(yōu)先算法來解決了非單一敏感屬性隱私泄露等相關(guān)問題.Tiancheng Li[6]在2012年初提出了Slicing模型，其沒有明確區(qū)分準(zhǔn)標(biāo)識(shí)符屬性和敏感屬性，而是依據(jù)屬性之間的關(guān)系先行切片，切片內(nèi)屬性間關(guān)系保持，切片外屬性間關(guān)系打亂，通過這種方式來處理隱私保護(hù)數(shù)據(jù)發(fā)布.

以上的這些模型在一定的領(lǐng)域或范圍內(nèi)也取得了良好的使用效果.本文提出的方法是通過分類、聚集、聚集、泛化的途徑.具體上首先將需要保護(hù)的敏感元組與大量不需要保護(hù)的敏感元組進(jìn)行分類.然后將不需要保護(hù)的敏感元組進(jìn)行聚集成簇，后測(cè)算需要保護(hù)的敏感元組與簇之間的距離，將要保護(hù)的敏感元組同簇中元組共同泛化，最后通過試驗(yàn)證明，對(duì)單一敏感屬性的隱私保護(hù)該方式也能取得很好的隱私保護(hù)效果.

1 相關(guān)概念

1）如果QIi[t1]和QIi[t2]為數(shù)值型屬性，則我們定義該屬性之間的距離為：

2）如果QIi[t1]和QIi[t2]為分類型屬性，則我們定義該屬性之間的距離為：

其中ancestor(QIi[t1],QIi[t2])表示分類樹中t1元組的第i個(gè)屬性和t2元組的第i個(gè)屬性的最小共同祖先.|Ai|表示分類樹的高度.例如在圖1中Without-pay和Never-worked的最小共同祖先為Unemployed，而整個(gè)分類樹的高度為2，故它們之間的距離為0.5.

圖1 工作階層的泛化層次Fig.1 The generation level of workclass

3）σi值依據(jù)元組中屬性的重要程度不同而分別進(jìn)行設(shè)置.

假設(shè)數(shù)據(jù)集中元組包含n個(gè)屬性，用QIi[t1]表示元組t1第i個(gè)屬性，數(shù)據(jù)集中部分元組已經(jīng)形成簇集G{C1、C2、…Cn}.則元組t1和簇Cj的距離為：

其中r為簇Cj中元組的個(gè)數(shù).

2 算法

算法前提：

1）需要保護(hù)的敏感屬性相對(duì)較少，且存在保護(hù)級(jí)差.

2）敏感屬性與準(zhǔn)標(biāo)識(shí)符屬性之間是可區(qū)分的.

3）對(duì)每個(gè)元組，敏感屬性有且只有一個(gè).

4）敏感屬性與準(zhǔn)標(biāo)識(shí)符屬性均不為空.

2.1 算法的三個(gè)步驟

第一步Algorithm：Clustering stage

輸入：待發(fā)布的數(shù)據(jù)表T（剔除包含重要敏感屬性的元組），匿名參數(shù)k，權(quán)重矢量W.

輸出：滿足k匿名的數(shù)據(jù)表PT，及表T中剩余的部分元組.

1）將數(shù)據(jù)表T中隱匿個(gè)體標(biāo)識(shí)屬性

2）簇集初始化G=?

while（|T|≥2k）do

A.隨機(jī)選取表T中一個(gè)元組ttemp，tfst1=max

k-匿名：給定一數(shù)據(jù)集，該模型將該數(shù)據(jù)集劃分為若干個(gè)簇，使得每個(gè)簇中元組個(gè)數(shù)均大于等于k.簇中元素在準(zhǔn)標(biāo)識(shí)符QI上均有相同的屬性值.

敏感性分級(jí)（ai，k）匿名：給定一匿名表PT，準(zhǔn)標(biāo)識(shí)符QI，敏感屬性SA，將敏感屬性SA按敏感程度分級(jí)，并對(duì)每個(gè)級(jí)別的SA滿足敏感約束ai，則稱該匿名表PT關(guān)于準(zhǔn)標(biāo)識(shí)符QI及敏感屬性集SA滿足敏感性分級(jí)（ai，k）匿名.

距離度量：數(shù)據(jù)集中的元組包含數(shù)值型屬性和分類型屬性，計(jì)算兩元組之間的距離需要分別計(jì)算數(shù)值型屬性之間的距離和分類型數(shù)據(jù)之間的距離，再將它們恰當(dāng)?shù)慕Y(jié)合起來.

假設(shè)數(shù)據(jù)集中元組包含n個(gè)屬性，用QIi[t1]和QIi[t2]分別表示元組t1第i個(gè)屬性和t2的第i個(gè)屬性，則元組t1和t2之間的距離定義為：(Dis(ttemp,t))，tfst2=max(Dis(tfst1,t)).

B.以tfst1和tfst2為中心查找距離它們最近的k-1個(gè)元組，并將這兩個(gè)簇C tfst1、C tfst2并入簇集G中.

C.T=T-{C tfst1}-{C tfst2}

第二步Algorithm：Adjustment stage

輸入：簇集G{C1、C2、…Cx}，及表T中剩余的部分元組.

輸出：滿足k匿名的簇集G{C1、C2、…Cx}.

While(T!=?)

A.隨機(jī)的從T中任選一個(gè)元組t，T=T-{t}.

B.計(jì)算距離t最近的簇集，C=min(Dis(t,Ci))，并將t加入到簇集中，C=C∪{t}.

第三步Algorithm：Distribution stage

輸入：滿足k匿名的簇集G{C1、C2、…Cx}，各類具有分級(jí)匿名要求的元組集T*，敏感屬性的頻率約束a1、a2、...az（z為有敏感屬性約束要求的敏感屬性個(gè)數(shù)）.

輸出：滿足分級(jí)匿名模型的數(shù)據(jù)表PT.

While(T!=?)

A.從T*中任選一個(gè)元組，計(jì)算其到簇集G表中簇集的最近距離簇C=min(Dis(t*,Ci)).

B.假如（簇中該敏感屬性個(gè)數(shù)+1）≤簇中元素個(gè)數(shù)ai并且簇中元組個(gè)數(shù)不超過2k，則將該元組加入該簇集.否則G=G-{Ci}反復(fù)重新計(jì)算最近簇的距離.

依次對(duì)簇集中各個(gè)簇C中的元組進(jìn)行泛化，得到滿足分級(jí)匿名要求的數(shù)據(jù)表PT.

2.2 算法正確性分析

算法分為三步走，第一步對(duì)不包含重要敏感屬性的元組依據(jù)它們之間的距離進(jìn)行分類，簇集中的元組數(shù)均為k.第二步對(duì)剩余的不包含重要敏感屬性的元組計(jì)算它們和簇集的距離，將它們分別加入到距離其最近的簇集中.通過這兩部將非重要敏感屬性的元組進(jìn)行分類，且每個(gè)簇集中元組小于2k個(gè).通過第三步將具有分級(jí)匿名要求的元組集中元素綜合測(cè)算其與簇集的距離、計(jì)算簇集中元組個(gè)數(shù)、分級(jí)匿名的要求等，將包含重要敏感屬性的元組加入到各個(gè)簇集當(dāng)中去.因此該算法是正確的.

2.3 算法復(fù)雜度分析

算法第一步對(duì)不包含重要敏感屬性的元組進(jìn)行分類，其時(shí)間復(fù)雜度為：生成第一第二個(gè)簇的代價(jià)是O（2n+2（k-1）n），生成第三第四個(gè)簇的代價(jià)是O（2（n-2k）+2（k-1）（n-2k）），生成第五第六個(gè)簇的生成.所以算法第一步的平均時(shí)間花銷為：O（2n+2法第二步，共有X個(gè)簇，且每個(gè)簇中包含k個(gè)元組，因此T中至多有n-xk個(gè)剩余元組，對(duì)每個(gè)剩余元組需計(jì)算O（xk），所以共需執(zhí)行時(shí)間為O（（n-xk）（n），算法第三步復(fù)雜度也為O（n）.所以總的時(shí)間花銷為O（O（n2）+O（n）+O（n））=O（n2）.

3 試驗(yàn)及結(jié)果分析

3.1 試驗(yàn)數(shù)據(jù)及參數(shù)

試驗(yàn)環(huán)境為：Intel Core i5 2.67GHz CPU，2GB RAM，操作系統(tǒng)為Microsoft Windows XP，編譯環(huán)境是C-FREE 5.0.試驗(yàn)使用Adult標(biāo)準(zhǔn)數(shù)據(jù)集中的訓(xùn)練數(shù)據(jù)集，我們首先刪除該數(shù)據(jù)集中Age、Work?class、Martial-status、Race、Education屬性有為空的元組，其次我們?cè)谑Ｓ嘤涗浿须S機(jī)選取5000條記錄進(jìn)行試驗(yàn).其中以年齡、工作階層、婚姻狀況和種族作為準(zhǔn)標(biāo)識(shí)屬性，并以Education作為敏感屬性進(jìn)行試驗(yàn)，具體描述見表1.

表1 Adult數(shù)據(jù)庫試驗(yàn)數(shù)據(jù)描述Tab.1 The data feature of Adult database

試驗(yàn)主要分析基于差異化聚類的分級(jí)隱私保護(hù)數(shù)據(jù)發(fā)布過程的信息損失和執(zhí)行時(shí)間.我們選取Education屬性中的“1st-4th”和“10th”作為需要隱匿的敏感屬性，先測(cè)算其個(gè)數(shù)分別為21和133，并預(yù)先設(shè)置“1st-4th”頻率約束a1=1/6,“10th”頻率約束a2=1/3.需要隱匿的敏感屬性個(gè)數(shù)概率遠(yuǎn)小于5000個(gè)，具備需要隱匿的敏感屬性的特性.我們?cè)趦蓚€(gè)方面進(jìn)行比較.

3.2 信息損失量、泛化元組數(shù)比較

我們將k值分別取6、12、18、24并分別查看信息總損失量及涉及到的泛化元組數(shù)，我們可以看到隨著k值的增大，不僅匿名信息的損失總量在增加，泛化的元組數(shù)也在增加.這是因?yàn)殡S著k值的增大，在算法第一步中聚類的元組數(shù)不斷增加，需要保護(hù)的敏感屬性泛化的元組數(shù)同樣也增加了.在帶來更高隱私保護(hù)的同時(shí)，匿名信息的損失量也不可避免增加.

3.3 執(zhí)行時(shí)間的比較

我們將k值分別取6、12、18、24并分別查看其算法運(yùn)行時(shí)間，我們可以看到隨著k值的增大，執(zhí)行時(shí)間先減少后增加.這是因?yàn)殡S著k值的增大，原先算法第一步執(zhí)行無須保護(hù)元組的聚類所用時(shí)間相對(duì)在不斷減少，而算法第三步將需要保護(hù)的敏感屬性所在元組聚類到無須保護(hù)的元組所在的聚類所用時(shí)間不斷增加，試驗(yàn)得出在k值為18左右總用時(shí)最少.

4 結(jié)語

隱私保護(hù)數(shù)據(jù)發(fā)布相關(guān)熱點(diǎn)很多，包括數(shù)據(jù)集的多次發(fā)布、多敏感屬性隱私保護(hù)、敏感屬性動(dòng)態(tài)可變保護(hù)、高維度數(shù)據(jù)保護(hù)等一系列隱私保護(hù)問題.本文針對(duì)單一敏感屬性隱私保護(hù)相關(guān)問題進(jìn)行研究.通過試驗(yàn)證明該算法能在最大限度保留原有數(shù)據(jù)屬性的同時(shí)，通過少量泛化操作來滿足不同數(shù)據(jù)保護(hù)度的要求.

[1] Sweenty L.k-anonymity:a model for protecting privacy[J].International Journal on Uncertainty.Fuzziness and Knowledge-based Systems,2002,10(5):557-570.

[2] Machanavajjhala A,Gehrke J,Kifer D.1-Diversity:Priva?cy beyond K-anonymity[A].Proceedings Roger S.Barge of the 22nd International Conference on Data Engineering[C].USA:IEEE Press,2006:24-36.

[3] Xiaokui Xiao,Yufei Tao.m-invariance:Towards privacy preserving re-publication of dynamic datasets[A].Lizhu Zhou.Proceedings of the 2007 ACM SIGMOD interna?tional conference on Management of data[C].USA:ACM 2007:689-700.

[4] LI N H,LI T C,Venkatasubramanian S.t-closeness:priva?cy beyond k-anonymity and l-diversity[A].Adnan Yazi ci.Proceedings of the 23rd International conference on Da?ta Engineering[C].USA:IEEE Press,2007:106-115.

[5] 楊曉春,王雅哲,王斌,等.數(shù)據(jù)發(fā)布中面向多敏感屬性的隱私保護(hù)方法[J].計(jì)算機(jī)學(xué)報(bào),2008,31（4）:574-586.

[6] Tiancheng Li,Ninghui Li,Jian Zhang,et al.Slicing:A New Approach for Privacy Preserving Data Publishing[J].IEEE Trans Knowl Data Eng,2012,24(3):561-574.