劉 海

?

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

劉 海*

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

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

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

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

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

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

1 相關(guān)概念

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

表2 匿名化表T*

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

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

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

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

2 算法

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

2.1 正確性分析

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

2.2 復雜性分析

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

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

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

表3 Adult數(shù)據(jù)庫部分數(shù)據(jù)描述

3.1 信息量損失比較

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

圖1 不同K值的信息損失

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

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

圖2 不同K值的運行時間

4 總結(jié)

在隱私保護數(shù)據(jù)發(fā)布的研究過程中, 僅僅簡單的對敏感屬性進行泛化處理及隱匿操作, 會造成不必要的大量數(shù)據(jù)的信息損失及極低的數(shù)據(jù)處理效率. 模型通過先對數(shù)據(jù)集中的數(shù)據(jù)進行分析, 選取部分數(shù)據(jù)進行泛化, 一方面, 能夠滿足匿名數(shù)據(jù)集中差異程度最大化; 另一方面, 在保證了數(shù)據(jù)匿名要求的同時, 最大限度地保留原有數(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ā)布中面向多敏感屬性的隱私保護方法[J]. 計算機學報, 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年度高?？蒲许椖?Y201224136)

(責任編校:劉剛毅)