劉 海

?

基于敏感元組的聚類匿名數(shù)據(jù)發(fā)布

劉 海*

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

在數(shù)據(jù)發(fā)布的過(guò)程中, 為了保護(hù)個(gè)人隱私常需對(duì)所有準(zhǔn)標(biāo)識(shí)符進(jìn)行泛化操作, 而實(shí)際涉及到個(gè)人隱私相關(guān)敏感屬性元組是非常少的. 據(jù)此, 從這些涉及個(gè)人隱私的敏感屬性的元組出發(fā), 將剩余大量?jī)H涉及非敏感屬性元組依據(jù)敏感屬性值不同進(jìn)行分組, 最后對(duì)分組中元組以計(jì)算與個(gè)人隱私屬性相關(guān)敏感屬性距離的方式, 選取距離最短的元組進(jìn)行泛化, 其余元組并不進(jìn)行泛化, 通過(guò)這種方式, 提高了數(shù)據(jù)的利用率, 并有效減少信息的損失.

隱私保護(hù); 數(shù)據(jù)發(fā)布;匿名; 泛化; 聚類

近年來(lái), 許多與個(gè)體相關(guān)的數(shù)據(jù)包括人口統(tǒng)計(jì)數(shù)據(jù)、患者醫(yī)療數(shù)據(jù)等需要進(jìn)行公開(kāi)發(fā)布, 有的是供各類科研機(jī)構(gòu)進(jìn)行數(shù)據(jù)分析和預(yù)測(cè)使用, 還有就是由于政策導(dǎo)向的要求. 這些發(fā)布的數(shù)據(jù)可能被存儲(chǔ)或者處理, 為了保護(hù)某些個(gè)體的隱私, 傳統(tǒng)的方法僅僅進(jìn)行個(gè)體身份識(shí)別屬性的隱匿或者加密, 單純采用這種方法隱私保護(hù)效果很差, 窺探者可以通過(guò)發(fā)布數(shù)據(jù)集中的準(zhǔn)標(biāo)識(shí)符與外部表進(jìn)行連接等操作, 從而推斷出個(gè)體希望保護(hù)的敏感屬性. 據(jù)美國(guó)統(tǒng)計(jì)局的一份統(tǒng)計(jì)資料顯示, 只要獲得1位美國(guó)公民的性別、年齡和郵政編碼, 則87%美國(guó)公民的身份就能夠被確認(rèn). 針對(duì)發(fā)布數(shù)據(jù)產(chǎn)生信息效益的同時(shí)如何對(duì)個(gè)體隱私信息有效保護(hù)這一問(wèn)題, 許多學(xué)者提出了隱私保護(hù)的模型及匿名化的方法. P.Samarati和L. Sweeney[1]在2002年率先提出了匿名模型, 該模型能保證發(fā)布中的數(shù)據(jù)有條元組在準(zhǔn)標(biāo)識(shí)符上是一致的, 從而該模型能夠避免數(shù)據(jù)表和表之間的連接攻擊, 但該模型容易受到背景知識(shí)攻擊和同質(zhì)攻擊. Machanavajjhala[2]在2006年針對(duì)匿名模型的缺點(diǎn), 提出了l-多樣性模型, 要求在每一個(gè)分組中的敏感屬性個(gè)數(shù)要大于l個(gè), 從而避免同質(zhì)攻擊. 后來(lái)一些學(xué)者也提出了改進(jìn)的模型, N. LI[3]在2007年提出了-closeness模型, 在每個(gè)匿名分組中的敏感屬性的不僅要具有l(wèi)-多樣性而且敏感屬性在每個(gè)分組中的分布與其在全表中的分布差異要小于. 楊曉春[4]等在2008年提出了面向多敏感屬性的隱私保護(hù)方法, 該方法利用多維桶技術(shù), 并分別設(shè)計(jì)了最大桶優(yōu)先、最大單維容量?jī)?yōu)先及最大多維容量等優(yōu)先算法來(lái)解決數(shù)據(jù)發(fā)布過(guò)程中的隱私泄漏問(wèn)題. Wong R[5]在2009年提出了(,)匿名模型, 該匿名模型通過(guò)限定簇中敏感屬性出現(xiàn)的頻率均小于的方式來(lái)達(dá)到敏感屬性的多樣性, 降低概率攻擊的可能性從而實(shí)現(xiàn)隱私保護(hù). Mingqiang Xue[6]等在2012年提出利用位圖集及組內(nèi)循環(huán)相關(guān)部分隱匿等方式實(shí)現(xiàn)數(shù)據(jù)的隱私保護(hù). Tiancheng Li[7]在2012年初提出了Slicing方法, 其將準(zhǔn)標(biāo)識(shí)符和敏感屬性進(jìn)行切片, 切片內(nèi)保持屬性之間關(guān)系, 切片外屬性之間關(guān)系打亂的方式來(lái)處理隱私保護(hù)數(shù)據(jù)發(fā)布.

以上的這些模型, 考慮得相對(duì)比較周全, 但一般而言, 發(fā)布數(shù)據(jù)集中的敏感屬性中涉及到隱私的屬性是非常少的, 需要進(jìn)行保護(hù)的也僅僅是這些屬性, 比如在醫(yī)療信息表中, 僅僅需要保護(hù)的是癌癥、愛(ài)滋病等相關(guān)元組信息, 其余大量元組敏感屬性為普通感冒、頭痛等疾病, 并不需要進(jìn)行保護(hù). 本文從需要保護(hù)的敏感屬性出發(fā), 依托數(shù)據(jù)集本身特點(diǎn), 通過(guò)將不需要隱匿敏感屬性的元組按敏感屬性值不同進(jìn)行分組, 并依據(jù)的大小不同, 從每個(gè)分組中分別尋找元組來(lái)組成匿名組的方式來(lái)提高匿名組中的匿名多樣性, 利用計(jì)算每個(gè)分組中元組和需匿名敏感元組最短距離的方式, 來(lái)降低泛化程度, 提高數(shù)據(jù)的利用率.

表1 原始數(shù)據(jù)表T

1 相關(guān)概念

在數(shù)據(jù)發(fā)布的過(guò)程中, 一般可以按照數(shù)據(jù)的屬性將數(shù)據(jù)劃分為四種類型: ①個(gè)體識(shí)別屬性. 其可以顯式表示出個(gè)體身份特征的屬性, 如姓名、身份證號(hào)碼等, 這些屬性在數(shù)據(jù)發(fā)布前, 一般已經(jīng)被隱匿或刪除, 如表1中的姓名. ②準(zhǔn)標(biāo)識(shí)屬性. 一個(gè)準(zhǔn)標(biāo)識(shí)屬性是由一組屬性構(gòu)成的屬性組, 且能夠通過(guò)連接運(yùn)算標(biāo)識(shí)出數(shù)據(jù)表中的個(gè)體信息, 如表1中的屬性組{Age, Zip, Sex}. ③敏感屬性. 指的是與個(gè)體敏感信息相關(guān)的屬性, 包括: 薪水、疾病等, 如表1中的Disease. ④其它屬性. 描述個(gè)體的一些其它信息.

表2 匿名化表T*

定義1(等價(jià)類): 一個(gè)等價(jià)類是由若干個(gè)元組構(gòu)成的集合, 這些元組在準(zhǔn)標(biāo)識(shí)符上具有相同的屬性值. 例如, 在表2中Bob和Ales其在準(zhǔn)標(biāo)識(shí)符Age上具有相同的年齡范圍[19, 20], Zip上均為[12 k, 20 k], Sex上均為M.

定義2(數(shù)據(jù)泛化): 在不違背原有語(yǔ)義的基礎(chǔ)上, 使用相同的抽象屬性值來(lái)代替多個(gè)元組中的不同屬性值. 例如, Bob的年齡為20, 我們可以將其年齡泛化為[18, 25]的一個(gè)年齡范圍, 通過(guò)泛化使得數(shù)據(jù)的范圍更廣, 相應(yīng)的數(shù)據(jù)精度也降低了.

定義3(數(shù)值屬性泛化的信息損失): 為泛化后屬性范圍和泛化前屬性范圍的比值計(jì)算信息損失. 用如下式1來(lái)計(jì)算.QI[1]和QI[2]分別表示等價(jià)類中1元組的第個(gè)屬性和2元組的第個(gè)屬性. 例如, 在表2中Bob的年齡泛化為[19, 20], 則可以計(jì)算該數(shù)值屬性泛化的信息損失為: (20-19)/(45-19) = 1/6 = 0.17.

定義5(元組失真度): 元組在準(zhǔn)標(biāo)識(shí)符屬性集上, 數(shù)值屬性泛化的信息損失和分類屬性泛化的信息損失之和, 用式(3)計(jì)算.表示等價(jià)類中屬性組的個(gè)數(shù),w為第個(gè)屬性的權(quán)重. 等價(jià)類中每個(gè)屬性組對(duì)元組間距離的影響是不同的, 所以可以為每個(gè)屬性組設(shè)置一個(gè)權(quán)重, 來(lái)反映屬性對(duì)元組信息損失的影響.

2 算法

算法的基本前提假設(shè): 敏感屬性有且只有一個(gè). 敏感屬性和其他屬性之間是可區(qū)分的. 敏感元組在數(shù)據(jù)表中所占比例很低. 輸入: 待發(fā)布的數(shù)據(jù)表{1,2,3, …,QI,}, 敏感值集合, 匿名參數(shù), 權(quán)重矢量. 輸出: 滿足隱私保護(hù)要求的發(fā)布表*

2.1 正確性分析

對(duì)于*而言, 每個(gè)匿名組的元組數(shù)均為, 一則: 對(duì)于每一個(gè)匿名組中僅有一個(gè)元組屬于敏感元組; 二則: 對(duì)于匿名組實(shí)現(xiàn)了最大化的敏感元組差異性; 三則: 剩余的非敏感屬性元組并不需要進(jìn)行泛化. 通過(guò)這種方式: ①降低了需要匿名的元組個(gè)數(shù), 僅僅是在匿名組中的元組需要進(jìn)行匿名運(yùn)算, 減少了信息損失; ②通過(guò)選取對(duì)匿名元組而言最近的元組進(jìn)行泛化操作, 降低了泛化高度, 同樣也減少了信息損失.

2.2 復(fù)雜性分析

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

實(shí)驗(yàn)環(huán)境為: 2.67 GHz Pentium CPU, 2 G內(nèi)存, windows XP操作系統(tǒng), 程序使用C語(yǔ)言, 在C-Free 5.0平臺(tái)上實(shí)現(xiàn), 實(shí)驗(yàn)采用來(lái)自UCI machine learning repository的Adult標(biāo)準(zhǔn)數(shù)據(jù)集, 該數(shù)據(jù)集共有48 842個(gè)記錄, 首先刪除數(shù)據(jù)集中Age、Workclass、Martial-status、Race、Education屬性有為空的元組, 然后選取Adult數(shù)據(jù)庫(kù)中前3萬(wàn)條數(shù)據(jù)記錄作為實(shí)驗(yàn)數(shù)據(jù), 以年齡、工作階層、婚姻狀況和種族作為準(zhǔn)標(biāo)識(shí)屬性, 并以Education作為敏感屬性進(jìn)行試驗(yàn), 見(jiàn)表3.

選取Preschool作為需要隱匿的Education屬性中的敏感屬性, 該屬性共有41條, 其余15個(gè)敏感屬性數(shù)均遠(yuǎn)遠(yuǎn)大于41, 本文在2個(gè)方面進(jìn)行比較.

表3 Adult數(shù)據(jù)庫(kù)部分?jǐn)?shù)據(jù)描述

3.1 信息量損失比較

將值分別取4、7、10、13查看信息的損失, 從圖1中可以看出隨著K值的增加, 泛化的元組平均信息的損失也逐漸增加, 一方面信息損失的比例在增加, 這是因?yàn)殡S著值增加, 泛化的元組數(shù)也增加, 顯然會(huì)帶來(lái)更多的信息損失. 另一方面信息損失隨著值增大, 增加不多, 是因?yàn)榉夯M及其屬性總數(shù)從656(41 × 4 × 4)到2 132(41 × 4 × 13)遠(yuǎn)小于測(cè)試數(shù)據(jù)集中元組及其屬性總數(shù)1 920 000(30 000 × 4 × 16).

圖1 不同K值的信息損失

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

將值分別取4、7、10、13查看信息的損失, 從圖2中可以看出隨著值的增加, 程序的運(yùn)行時(shí)間也逐漸增加, 在= 13時(shí)候其運(yùn)行時(shí)間是= 4時(shí)候的接近5倍, 其原因是: 一方面, 每進(jìn)行一次聚集, 需要搜索的元組數(shù)在= 13時(shí)候是= 4的3倍, 另一方面, 一次生成多個(gè)不同的隨機(jī)數(shù)的時(shí)間隨著值增加也顯著增大.

圖2 不同K值的運(yùn)行時(shí)間

4 總結(jié)

在隱私保護(hù)數(shù)據(jù)發(fā)布的研究過(guò)程中, 僅僅簡(jiǎn)單的對(duì)敏感屬性進(jìn)行泛化處理及隱匿操作, 會(huì)造成不必要的大量數(shù)據(jù)的信息損失及極低的數(shù)據(jù)處理效率. 模型通過(guò)先對(duì)數(shù)據(jù)集中的數(shù)據(jù)進(jìn)行分析, 選取部分?jǐn)?shù)據(jù)進(jìn)行泛化, 一方面, 能夠滿足匿名數(shù)據(jù)集中差異程度最大化; 另一方面, 在保證了數(shù)據(jù)匿名要求的同時(shí), 最大限度地保留原有數(shù)據(jù)的屬性.

[1] Sweenty L.-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. l-Diversity:Privacy beyond-anonymity[A]. Proc of the 22nd International Conference on Data Engineering[C]. USA: IEEE Press, 2006: 24—36.

[3] Li N H, Li T C, Venkatasubramani S. t-closeness:privacy beyond k-anonymity and l-diversity[A]. ICDE 2007: Proceedings of the 23rd International conference on Data Engineering. Washington[C]. DC: IEEE Computer Society, 2007: 106—115.

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

[5] WONG R, LI J, FU A,et al. (,)-anonymous data publishing[J]. Journal of Intelligent Information Systems, 2009, 33(2): 209—234.

[6] Xue M Q, Panagiotis K, Chedy R, et al. Anonymizing Set-Valued Data by Nonreciprocal Recoding[J]. The 18th ACM Data SIGKDD International Conference on Knowledge Discovery and Data Mining KDD, 2012, 12: 1050—1058.

[7] Li Tiancheng. Slicing: A New Approach for Privacy Preserving Data Publishing[J]. IEEE Trans Knowl Data Eng, 2012, 24(3): 561—574.

On anonymous data publishing based on sensitive tuple cluster

LIU Hai

(Management Department, Zhejiang Financial College, Hangzhou 310018, China)

During the process of data publishing, in order to protect personal privacy, data owner often has to generalize all the quasi-identifier, but in fact the tuple involving personal privacy is very few. So our method starts from the tuples, then divides the remainder into groups according to different sensitive attribute value. Finally, our method selects one tuple per group which is shortest to the tuple involving personal privacy for generalization. The rest tuples need not to be generalized. In this way, our method has improved the utilization rate of the data and reduced the loss of information effectively.

privacy preservation; data publishing;-anonymous; generalization; cluster

10.3969/j.issn.1672-6146.2013.04.015

TP 309.2

1672-6146(2013)04-0060-04

email: feelnice_cn@126.com.

2013-09-09

浙江省教育廳2012年度高校科研項(xiàng)目(Y201224136)

(責(zé)任編校:劉剛毅)