劉海

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

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

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

1 相關(guān)概念

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

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

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

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

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

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

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

2 算法

算法前提：

1）需要保護的敏感屬性相對較少，且存在保護級差.

2）敏感屬性與準標識符屬性之間是可區(qū)分的.

3）對每個元組，敏感屬性有且只有一個.

4）敏感屬性與準標識符屬性均不為空.

2.1 算法的三個步驟

第一步Algorithm：Clustering stage

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

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

1）將數(shù)據(jù)表T中隱匿個體標識屬性

2）簇集初始化G=?

while（|T|≥2k）do

A.隨機選取表T中一個元組ttemp，tfst1=max

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

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

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

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

B.以tfst1和tfst2為中心查找距離它們最近的k-1個元組，并將這兩個簇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.隨機的從T中任選一個元組t，T=T-{t}.

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

第三步Algorithm：Distribution stage

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

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

While(T!=?)

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

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

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

2.2 算法正確性分析

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語

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

[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ā)布中面向多敏感屬性的隱私保護方法[J].計算機學報,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.