優(yōu)秀碩士論文--基于匿名機(jī)制的數(shù)據(jù)發(fā)布中隱私泄露控制技術(shù)

1、 基于匿名機(jī)制的數(shù)據(jù)發(fā)布中隱私泄露控制技術(shù)第一章 引言1.1研究背景數(shù)據(jù)發(fā)布環(huán)境中存在的隱私泄露問(wèn)題使得數(shù)據(jù)發(fā)布隱私泄露控制技術(shù)的研究成為學(xué)術(shù)界和工業(yè)界關(guān)注的一個(gè)焦點(diǎn)。數(shù)據(jù)發(fā)布中的原始數(shù)據(jù)由記錄構(gòu)成，每個(gè)記錄均與一個(gè)個(gè)體相對(duì)應(yīng)，數(shù)據(jù)的屬性分為標(biāo)識(shí)符、準(zhǔn)標(biāo)識(shí)符、敏感屬性三類(lèi)。數(shù)據(jù)發(fā)布時(shí)直接刪除標(biāo)識(shí)符以保護(hù)個(gè)體隱私。但是可能存在攻擊者通過(guò)準(zhǔn)標(biāo)識(shí)符與外部公開(kāi)的數(shù)據(jù)源進(jìn)行鏈接攻擊(Linking Attack) 1，導(dǎo)致個(gè)體隱私的泄露。研究表明，這種鏈接攻擊可以識(shí)別大量美國(guó)公民的身份1。例如，假設(shè)一個(gè)網(wǎng)站上發(fā)布了一個(gè)醫(yī)療信息表，為保護(hù)個(gè)體隱私，將原始數(shù)據(jù)中能識(shí)別個(gè)體身份的標(biāo)識(shí)符（姓名）刪除之后得到數(shù)據(jù)

2、發(fā)布表，如表1-1所示。表1-1屬性組(年齡，性別，郵編 )為準(zhǔn)標(biāo)識(shí)符，敏感屬性為疾病。若攻擊者可以從另一個(gè)網(wǎng)站上瀏覽如表1-2選民登記表的信息，獲知表中法蘭克的年齡屬性值為45，性別屬性值為男，郵編 屬性值為734532。攻擊者很容易從表1-1推出法蘭克患有心臟病，造成了法蘭克的隱私泄露。為了阻止數(shù)據(jù)發(fā)布中的鏈接攻擊，一個(gè)有效的手段是對(duì)原始數(shù)據(jù)進(jìn)行匿名化處理，從而控制個(gè)體隱私信息的泄露。表1-1醫(yī)療信息表年齡性別郵編疾病t141女734562失眠t240女734552心臟病t341男734532失眠t444男734555心臟病t544男734555失眠t645男734532心臟病t741男7

3、34561禽流感t842男734533禽流感t943女734553禽流感表1-2選民登記表姓名年齡性別郵編愛(ài)麗絲41女734562貝蒂40女734552約翰41男734532比爾44男734555艾迪44男734555法蘭克45男734532凱恩41男734561杰克42男734533珍妮43女7345531.2國(guó)內(nèi)外研究進(jìn)展分析數(shù)據(jù)發(fā)布要求匿名數(shù)據(jù)既具有安全性又具有可用性，然而兩者是相互矛盾的。因此，數(shù)據(jù)匿名化研究的重點(diǎn)是設(shè)計(jì)高效的匿名保護(hù)模型和匿名算法，以使得匿名數(shù)據(jù)在保證安全性的同時(shí)，最大限度地提供可用性。目前，國(guó)內(nèi)外匿名化技術(shù)的研究已經(jīng)取得了許多的成果。1.2.1匿名保護(hù)模型1.2.1

4、.1 k-匿名模型(k-anonymity)定義1.11 k-匿名 假設(shè)TA1,A2,An為一個(gè)數(shù)據(jù)集，QIT為與之相關(guān)的準(zhǔn)標(biāo)識(shí)符。當(dāng)且僅當(dāng)數(shù)據(jù)集T中每個(gè)記錄的準(zhǔn)標(biāo)識(shí)符屬性值在數(shù)據(jù)集中至少出現(xiàn)k次，則該數(shù)據(jù)集滿(mǎn)足k-匿名。定義1.21 等價(jià)類(lèi) 一個(gè)等價(jià)類(lèi)即數(shù)據(jù)集TA1,A2,An中一組具有相同準(zhǔn)標(biāo)識(shí)符屬性值的記錄。 針對(duì)數(shù)據(jù)發(fā)布中的鏈接攻擊，文獻(xiàn)1,2提出了k-匿名技術(shù)。文獻(xiàn)3提出實(shí)現(xiàn)k-匿名的泛化和隱匿方法，泛化是指在數(shù)據(jù)集中用抽象的屬性值來(lái)代替原來(lái)具體的屬性值，隱匿是指隱匿是指直接刪除數(shù)據(jù)集中某些屬性值或記錄。k-匿名通過(guò)泛化和隱匿使得等價(jià)類(lèi)中每個(gè)記錄具有相同的準(zhǔn)標(biāo)識(shí)符屬性值，攻擊者無(wú)法將

5、個(gè)體與某個(gè)記錄對(duì)應(yīng)起來(lái)，從而保護(hù)個(gè)體身份的泄露。例如，表1-3是表1-1的一個(gè)滿(mǎn)足3-匿名模型的匿名化表，其中，匿名參數(shù)=，準(zhǔn)標(biāo)識(shí)符為屬性組(年齡，性別，郵編 )，敏感屬性為疾病。表1-3中生成了3個(gè)等價(jià)類(lèi)t1，t2，t7，t4，t5，t6，t3，t8，t9。若在網(wǎng)站上用表1-3代替表1.的醫(yī)療信息表，那么攻擊者即使知道表1-2選民登記表中某個(gè)記錄的信息，也無(wú)法推斷出該記錄與表1-3中某一特定記錄相關(guān)聯(lián)。例如假設(shè)攻擊者從1-2選民登記表中獲知法蘭克的信息，與表1-3鏈接時(shí)，雖然知道法蘭克在t4，t5，t6等價(jià)類(lèi)中，卻無(wú)法將法蘭克與其中的某個(gè)記錄相對(duì)應(yīng)起來(lái)，從而避免法蘭克隱私的泄露。表1-3 -

6、匿名化表1年齡性別郵編疾病t140-41*7345*失眠t240-41*7345*心臟病t740-41*7345*禽流感t444-45男7345*心臟病t544-45男7345*失眠t644-45男7345*心臟病t341-43*7345*失眠t841-43*7345*禽流感t941-43*7345*禽流感但是， k-匿名模型存在同質(zhì)性攻擊和背景知識(shí)攻擊的問(wèn)題4。k -匿名模型由于忽略了敏感屬性值的多樣性，可能造成個(gè)體敏感屬性的隱私泄露，即同質(zhì)性攻擊。例如，假設(shè)表1-4是表1-1的另一個(gè)滿(mǎn)足3-匿名模型的匿名化表，表1-4中生成了3個(gè)等價(jià)類(lèi)t1，t2，t3，t4，t5，t6，t7，t8，t9。

7、如果攻擊者從1-2選民登記表中獲知杰克的信息，與表1-4鏈接起來(lái)時(shí)，雖然無(wú)法確定杰克與表1-4中具體的某個(gè)記錄相對(duì)應(yīng)，但通過(guò)準(zhǔn)標(biāo)識(shí)符屬性值可以知道杰克在表1-4的t7，t8，t9等價(jià)類(lèi)中，由于該等價(jià)類(lèi)的敏感屬性值均為禽流感，攻擊者容易知道杰克患有禽流感，杰克的隱私被泄露。同時(shí)，k -匿名還可能遭遇攻擊者利用預(yù)先知道的背景知識(shí)來(lái)進(jìn)行攻擊。此外，k -匿名模型由于通過(guò)泛化準(zhǔn)標(biāo)識(shí)符屬性達(dá)到匿名的目的也導(dǎo)致大量原始信息的損失，降低了匿名數(shù)據(jù)的可用性。表1-4 -匿名化表2年齡性別郵編疾病t140-41*7345*失眠t240-41*7345*心臟病t340-41*7345*失眠t444-45男7345

8、*心臟病t544-45男7345*失眠t644-45男7345*心臟病t741-43*7345*禽流感t841-43*7345*禽流感t941-43*7345*禽流感1.2.1.2 l-多樣性模型(l-diversity)文獻(xiàn)4提出了l-多樣性模型(l-diversity)以彌補(bǔ)k-匿名模型的不足。定義1.34 l-多樣性原則一個(gè)等價(jià)類(lèi)如果對(duì)于敏感屬性S至少包含l個(gè)不同的敏感屬性值，那么該等價(jià)類(lèi)是l-多樣性的。如果數(shù)據(jù)集T中的每個(gè)等價(jià)類(lèi)是l-多樣性的，則稱(chēng)該數(shù)據(jù)集滿(mǎn)足l-多樣性。該模型除了要求滿(mǎn)足k-匿名之外，還要求每個(gè)等價(jià)類(lèi)的敏感屬性值具有多樣性以防止敏感屬性的隱私泄露。例如，表1-5是表1

9、-1的一個(gè)滿(mǎn)足3-多樣性模型的匿名化表，其中，l，Q(年齡，性別，郵編 )。表1-5中生成了3個(gè)等價(jià)類(lèi)t1，t2，t7，t4，t5，t9，t3，t6，t8。每個(gè)等價(jià)類(lèi)中的記錄在(年齡，性別，郵編 )上具有相同的屬性值，并且在敏感屬性疾病上具有3個(gè)不同值。因而，表1-5中的數(shù)據(jù)能夠防止鏈接攻擊所導(dǎo)致的敏感屬性隱私泄露。雖然l-多樣性模型可以提供比k-匿名模型更強(qiáng)的隱私保護(hù)，但是，l-多樣性模型依然存在不足之處，l-多樣性模型同樣采用泛化和隱匿技術(shù)對(duì)原始數(shù)據(jù)進(jìn)行匿名處理，因而也存在信息損失的情況。表1-5 3-多樣性表年齡性別郵編疾病t140-41*7345*失眠t240-41*7345*心臟病t

10、740-41*7345*禽流感 t443-44*73455*心臟病t543-44*73455*失眠t943-44*73455*禽流感t341-45男73453*失眠t641-45男73453*心臟病t841-45男73453*禽流感1.2.1.3 Anatomy匿名模型文獻(xiàn)5提出了獨(dú)特的匿名方法Anatomy，該方法首先將數(shù)據(jù)集按l-多樣性匿名模型劃分，將劃分結(jié)果分成準(zhǔn)標(biāo)識(shí)符屬性表和敏感屬性表發(fā)布，兩張數(shù)據(jù)表之間通過(guò)Group-ID關(guān)聯(lián)。Anatomy匿名模型對(duì)等價(jià)類(lèi)的準(zhǔn)標(biāo)識(shí)符屬性不作泛化和隱匿處理，直接將準(zhǔn)標(biāo)識(shí)符屬性數(shù)據(jù)發(fā)布，因而保留了大量原始數(shù)據(jù)的信息，大大提高了匿名數(shù)據(jù)的可用性。同時(shí)，A

11、natomy將數(shù)據(jù)分成兩張表發(fā)布，使得攻擊者無(wú)法將個(gè)體的準(zhǔn)標(biāo)識(shí)符屬性和敏感屬性一一對(duì)應(yīng)起來(lái)，提高了數(shù)據(jù)的安全性。由于Anatomy匿名模型是在l-多樣性模型的基礎(chǔ)上提出的，l-多樣性模型上存在的一些不足，在Anatomy匿名模型中也依然存在。例如，表1-6是表1-1的一個(gè)滿(mǎn)足Anatomy模型的匿名化結(jié)果，假設(shè)攻擊者知道某個(gè)個(gè)體在Group-ID為1的等價(jià)類(lèi)中。雖然攻擊者可以從準(zhǔn)標(biāo)識(shí)符屬性表獲知該個(gè)體的年齡，性別，郵編具體值，但他無(wú)法從敏感屬性表中準(zhǔn)確獲得敏感屬性疾病的值，由于Group-ID為1的疾病值的個(gè)數(shù)為3，因此攻擊者只能以1/3的幾率進(jìn)行猜測(cè)。數(shù)據(jù)發(fā)布中，研究出提供更強(qiáng)保護(hù)能力的匿名

12、模型依然是匿名保護(hù)中的主要工作，因此，研究者們?cè)趉-匿名模型和l-多樣性模型的基礎(chǔ)上，又提出了一些新的匿名模型6-8。表1-6 Anatomy表(a) 準(zhǔn)標(biāo)識(shí)符屬性表Group-ID年齡性別郵編141女734562140女734552142男734561244男734555244男734555243女734553341男734532345男734532342男734533(b) 敏感屬性表Group-ID疾病統(tǒng)計(jì)1失眠11心臟病11禽流感 12心臟病12失眠12禽流感13失眠13心臟病13禽流感11.2.2 匿名算法采用匿名技術(shù)由原始數(shù)據(jù)生成最優(yōu)匿名數(shù)據(jù)是一個(gè)NP難問(wèn)題9,10，因此，設(shè)計(jì)出高

13、效的近似最優(yōu)算法是匿名保護(hù)中的重要工作。目前數(shù)據(jù)發(fā)布中采用的匿名技術(shù)主要有：泛化和隱匿、聚類(lèi)以及交換等技術(shù)。采用泛化和隱匿技術(shù)的匿名算法主要有： Datafly算法11、MinGen最小泛化算法3、Incognito算法12、GA（Genetic Algorithm）算法13、自底向上的泛化方法14、自頂向下的泛化方法15、基于多維空間劃分的k-匿名方法16。國(guó)內(nèi)研究者也在文獻(xiàn)17-20中對(duì)泛化和隱匿技術(shù)進(jìn)行了研究。泛化和隱匿技術(shù)將等價(jià)類(lèi)中不同的準(zhǔn)標(biāo)識(shí)符屬性值泛化為相同值以達(dá)到隱私保護(hù)的目的，造成了原始數(shù)據(jù)大量信息的損失。同時(shí)，基于泛化和隱匿技術(shù)的匿名算法采用基于泛化層次結(jié)構(gòu)的策略會(huì)引起不必要

14、的信息損失。為了解決泛化和隱匿技術(shù)存在的不足，在數(shù)據(jù)的匿名化中引入聚類(lèi)技術(shù)?；诰垲?lèi)的匿名化方法的主要思想是：首先將數(shù)據(jù)劃分為多個(gè)聚類(lèi)，然后分別泛化每個(gè)聚類(lèi)的準(zhǔn)標(biāo)識(shí)符屬性以達(dá)到匿名化。文獻(xiàn)21提出模糊c-均值算法。文獻(xiàn)22提出基于k-modes的算法。文獻(xiàn)23,24提出了基于k-means聚類(lèi)算法的k-匿名方法。文獻(xiàn)25提出MDAV k-匿名算法。在MDAV算法的基礎(chǔ)上，文獻(xiàn)26提出了V-MDAV(Variable-MDAV)算法。文獻(xiàn)27,28 提出了帶權(quán)重的聚類(lèi)方法。文獻(xiàn)29-32 提出了基于聚類(lèi)的k-匿名算法?；诰垲?lèi)的匿名算法不依賴(lài)于泛化層次結(jié)構(gòu)，因此生成的匿名數(shù)據(jù)集具有更高可用性。數(shù)

15、據(jù)交換是將數(shù)據(jù)集中某些屬性的值進(jìn)行互換以防止隱私泄露 33-35。文獻(xiàn)5提出了一種不基于泛化和隱匿技術(shù)的交換方法Anatomy。文獻(xiàn)36-38也提出了基于交換的隱私數(shù)據(jù)發(fā)布算法。采用交換技術(shù)的匿名化算法通過(guò)交換增加了隱私數(shù)據(jù)的不確定性，從而保護(hù)隱私數(shù)據(jù)的安全。并且交換技術(shù)直接發(fā)布準(zhǔn)標(biāo)識(shí)符屬性，保留了原始數(shù)據(jù)的大量信息，極大地提高了匿名數(shù)據(jù)聚集查詢(xún)的準(zhǔn)確性。1.2.3匿名質(zhì)量評(píng)估匿名化原始數(shù)據(jù)必然會(huì)引起信息損失，需要找到適合的評(píng)估機(jī)制來(lái)計(jì)算匿名后的信息損失以衡量匿名算法和匿名數(shù)據(jù)集的優(yōu)劣。以下是匿名質(zhì)量評(píng)估中常用的信息損失評(píng)估機(jī)制：定義1.131, 32 等價(jià)類(lèi)信息損失IL(e)。假設(shè)等價(jià)類(lèi)er

16、1,rk由準(zhǔn)標(biāo)識(shí)符由數(shù)值屬性(N1,Nm)和分類(lèi)屬性(C1,Cn)構(gòu)成，則等價(jià)類(lèi)信息損失IL(e)為：公式中|e|是e中記錄個(gè)數(shù)，|Ni|表示數(shù)值屬性的范圍， 和分別是e中關(guān)于屬性Ni的最大最小值。|Cj| 表示分類(lèi)屬性的不同屬性值個(gè)數(shù)，表示e中關(guān)于屬性Cj的不同屬性值個(gè)數(shù)。定義1.232 總體信息損失Total_IL。若e1,em是匿名數(shù)據(jù)集T中所有等價(jià)類(lèi)的集合，那么T的總體信息損失為：。總體信息損失能夠反映匿名數(shù)據(jù)集相對(duì)原始數(shù)據(jù)集所產(chǎn)生的信息損失。此外，文獻(xiàn)39中定義的可區(qū)分度量機(jī)制也可用來(lái)衡量匿名化質(zhì)量。定義1.339 可區(qū)分度量DM (Discernability Metric)定義為

17、，其中|E|表示等價(jià)類(lèi)E中的記錄個(gè)數(shù)，DM的值即為數(shù)據(jù)集中每一個(gè)等價(jià)類(lèi)大小的平方的和。可區(qū)分度量的意義在于：等價(jià)類(lèi)越大可區(qū)分度就越小，意味著一個(gè)記錄在大的等價(jià)類(lèi)中難以區(qū)分。定義1.45 聚集查詢(xún)平均相對(duì)錯(cuò)誤率。一個(gè)查詢(xún)的相對(duì)錯(cuò)誤率為|act est|/act， act是對(duì)原始數(shù)據(jù)進(jìn)行查詢(xún)獲得的實(shí)際結(jié)果，est是對(duì)匿名數(shù)據(jù)進(jìn)行查詢(xún)獲得的推測(cè)結(jié)果。每個(gè)查詢(xún)相對(duì)錯(cuò)誤率的和的平均值即為聚集查詢(xún)平均相對(duì)錯(cuò)誤率。1.3論文的組織本文共分為四章，各章節(jié)內(nèi)容組織如下：第一章為引言，闡述研究數(shù)據(jù)發(fā)布中匿名化與敏感信息保護(hù)技術(shù)的意義，分析與評(píng)述國(guó)內(nèi)外有關(guān)數(shù)據(jù)發(fā)布中匿名模型、匿名化與敏感信息保護(hù)技術(shù)方面的研究進(jìn)展，

18、給出本文章節(jié)的組織結(jié)構(gòu)。在第二章中，將著重討論基于聚類(lèi)的敏感屬性l-多樣性匿名化算法的設(shè)計(jì)與實(shí)現(xiàn)。首先，分析提出基于聚類(lèi)的敏感屬性l-多樣性匿名化算法的動(dòng)機(jī)，然后根據(jù)不同的聚類(lèi)種子記錄的選擇方式以及聚類(lèi)前生成不同的聚類(lèi)記錄候選集，提出了2個(gè)滿(mǎn)足l-多樣性模型的聚類(lèi)算法，并通過(guò)對(duì)真實(shí)數(shù)據(jù)的實(shí)驗(yàn)來(lái)評(píng)估這兩個(gè)算法的性能。第三章將討論基于l-多樣性的多敏感屬性匿名化技術(shù)問(wèn)題。首先分析多個(gè)敏感屬性的數(shù)據(jù)發(fā)布存在的隱私泄露風(fēng)險(xiǎn)，從而提出了一個(gè)滿(mǎn)足l-多樣性模型的多敏感屬性匿名化算法，并通過(guò)實(shí)驗(yàn)驗(yàn)證這個(gè)算法的有效性。第四章總結(jié)本文的工作成果，并對(duì)下一步的研究方向做出展望。第二章 基于聚類(lèi)的匿名化算法2.1問(wèn)

19、題分析本章討論基于聚類(lèi)的匿名化。以往的匿名化研究工作中，大多采用泛化和隱匿技術(shù)實(shí)現(xiàn)數(shù)據(jù)的匿名化。但是基于泛化和隱匿的匿名化算法由于受到泛化層次結(jié)構(gòu)的限制，導(dǎo)致一些不必要的信息損失。為了降低信息損失,一些學(xué)者將聚類(lèi)方法應(yīng)用到數(shù)據(jù)的匿名化上。事實(shí)表明，基于聚類(lèi)的方法能夠生成高質(zhì)量的匿名數(shù)據(jù)集。但是，基于聚類(lèi)的匿名化算法中，大多是基于k-匿名模型的，沒(méi)有考慮敏感屬性值的多樣性，存在著隱私泄露的風(fēng)險(xiǎn)。因此，本章研究提出2個(gè)滿(mǎn)足l-多樣性模型的聚類(lèi)算法LCA-FC(l-diversity clustering algorithm, select furthest seed and compare wit

20、h centroid)和LCA-RC (l-diversity clustering algorithm, randomly select seed and compare with centroid)，以避免敏感屬性的隱私泄露。2.2基于聚類(lèi)的敏感屬性l-多樣性匿名化算法.在基于聚類(lèi)的匿名化算法中，聚類(lèi)種子記錄的選擇和尋找信息損失最小記錄的方式是非常重要的，將會(huì)影響到聚類(lèi)的質(zhì)量。選擇聚類(lèi)種子記錄時(shí)，可以隨機(jī)選擇數(shù)據(jù)集的一個(gè)記錄，也可以選擇最遠(yuǎn)的記錄作為聚類(lèi)種子記錄。尋找信息損失最小記錄時(shí)，可以計(jì)算整個(gè)聚類(lèi)和每個(gè)候選記錄的信息損失來(lái)找到信息損失最小記錄，也可以計(jì)算聚類(lèi)代表記錄和每個(gè)候選記錄的信

21、息損失來(lái)找到信息損失最小記錄。而選擇聚類(lèi)代表記錄時(shí)，可以選擇聚類(lèi)質(zhì)心，也可以隨機(jī)選擇聚類(lèi)的一個(gè)記錄作為聚類(lèi)代表記錄。選擇不同的方式，將會(huì)產(chǎn)生不同的聚類(lèi)效果。大多數(shù)已有的基于聚類(lèi)的k-匿名算法沒(méi)有滿(mǎn)足敏感屬性值l-多樣性的要求，存在著隱私泄露的風(fēng)險(xiǎn)。因此，根據(jù)不同的聚類(lèi)種子記錄的選擇方式以及聚類(lèi)時(shí)生成不同的聚類(lèi)記錄候選集，本文提出了基于聚類(lèi)的敏感屬性l-多樣性匿名化算法LCA-FC和LCA-RC。它們的主要思想是：給定一個(gè)n個(gè)記錄的數(shù)據(jù)集T和l-多樣性參數(shù)l，首先計(jì)算數(shù)據(jù)集T不同敏感屬性值個(gè)數(shù)，如果該值大于等于l，選擇一個(gè)記錄作為種子開(kāi)始建立一個(gè)聚類(lèi)，然后每次從聚類(lèi)記錄候選集中選擇一個(gè)與聚類(lèi)信息

22、損失最小的記錄加入該聚類(lèi)，直到聚類(lèi)中記錄個(gè)數(shù)為l時(shí)結(jié)束，從而生成一個(gè)聚類(lèi)（即等價(jià)類(lèi)）。然后，滿(mǎn)足條件的情況下選擇一個(gè)記錄作為新的種子記錄，重復(fù)相同的過(guò)程建立下一個(gè)聚類(lèi)。最后，對(duì)于剩余的記錄，分別計(jì)算它們與已經(jīng)生成的每個(gè)聚類(lèi)之間的信息損失，然后加入到信息損失最小的聚類(lèi)中。LCA-FC算法在數(shù)據(jù)集中選擇距離上次種子記錄最遠(yuǎn)的記錄作為聚類(lèi)種子記錄，LCA-RC算法則在數(shù)據(jù)集中隨機(jī)選擇一個(gè)記錄作為聚類(lèi)種子記錄，兩者均通過(guò)計(jì)算聚類(lèi)質(zhì)心和聚類(lèi)記錄候選集的每個(gè)記錄的信息損失來(lái)找到信息損失最小記錄，但聚類(lèi)記錄候選集不同。本文算法在計(jì)算聚類(lèi)質(zhì)心時(shí)，各個(gè)數(shù)值型屬性值采用聚類(lèi)的各個(gè)數(shù)值型屬性平均值，而各個(gè)分類(lèi)屬性值

23、則采用聚類(lèi)的各個(gè)分類(lèi)屬性中出現(xiàn)頻率最高的值。算法處理的數(shù)據(jù)包括數(shù)值屬性和分類(lèi)屬性，信息損失機(jī)制必須既適用于數(shù)值型數(shù)據(jù)又適用于分類(lèi)型數(shù)據(jù)的信息損失計(jì)算。因此聚類(lèi)所產(chǎn)生的信息損失采用1.2.3小節(jié)定義的信息損失機(jī)制來(lái)衡量。下面分別描述基于聚類(lèi)的敏感屬性l-多樣性匿名化算法LCA-FC和LCA-RC：算法2.1 LCA-FC算法 輸入：原始數(shù)據(jù)集T和l-多樣性模型參數(shù)l；輸出：符合l-多樣性模型要求的匿名數(shù)據(jù)集tableBeginStep1: 計(jì)算數(shù)據(jù)集T不同敏感屬性值個(gè)數(shù)；if (T中不同敏感屬性值個(gè)數(shù)<l) then不能滿(mǎn)足l-多樣性，return T;end if;匿名數(shù)據(jù)集table=

24、；r=從T中隨機(jī)選取一個(gè)記錄;Step2: while (T中不同敏感屬性值個(gè)數(shù)>=l) do聚類(lèi)C=r;聚類(lèi)質(zhì)心centroid=r;數(shù)據(jù)集T=Tr;聚類(lèi)記錄候選集LT=從數(shù)據(jù)集T中選擇與種子記錄敏感屬性不相同的記錄；while (|C|<l) domin=;for (i=1, 候選集LT記錄個(gè)數(shù)) dorecord=LT中第i個(gè)記錄；if (record的敏感屬性值與聚類(lèi)C中記錄的敏感屬性值相同) continue;il= record 到聚類(lèi)C質(zhì)心的信息損失IL recordcentroid;if(il<min) thenmin=il;minrecord=record;

25、end if;end for;聚類(lèi)C=聚類(lèi)C信息損失最小記錄minrecord;候選集LT= LT信息損失最小記錄 minrecord ;數(shù)據(jù)集T=T信息損失最小記錄 minrecord ;重新計(jì)算聚類(lèi)質(zhì)心centroid;end while匿名數(shù)據(jù)集table=table生成的聚類(lèi)C;重新計(jì)算T中不同敏感屬性值個(gè)數(shù)；r=計(jì)算距離記錄r最遠(yuǎn)的記錄;end whileStep3: while (|T|0) dor=從T中隨機(jī)取記錄r;T=Tr;for (i=1, 匿名數(shù)據(jù)集table中的聚類(lèi)個(gè)數(shù)) doC=第i個(gè)聚類(lèi)；if (C的記錄個(gè)數(shù)>=2*l-1) then continue;il=

26、記錄r與聚類(lèi)C質(zhì)心信息損失IL rcentroid;if (il<min) thenmin=il;minc=i;end if;end for;信息損失最小聚類(lèi)minc = r信息損失最小聚類(lèi)minc;end whileStep4: 將匿名數(shù)據(jù)集table中的每個(gè)聚類(lèi)的所有記錄在準(zhǔn)標(biāo)識(shí)符上的屬性值用該聚類(lèi)代表記錄準(zhǔn)標(biāo)識(shí)符上的屬性值代替，完成匿名化，得到最后輸出的匿名數(shù)據(jù)集table。End算法2.2 LCA-RC算法 輸入：原始數(shù)據(jù)集T和l-多樣性模型參數(shù)l；輸出：符合l-多樣性模型要求的匿名數(shù)據(jù)集tableBeginStep1: 計(jì)算數(shù)據(jù)集T不同敏感屬性值個(gè)數(shù)，種子記錄候選集LS=從數(shù)據(jù)

27、集T中選擇敏感屬性值相同且數(shù)目最多的所有記錄，聚類(lèi)記錄候選集LT= 數(shù)據(jù)集T-種子記錄候選集LS-敏感屬性值相同且數(shù)目最少的所有記錄；if (T中不同敏感屬性值個(gè)數(shù)<l) then 不能滿(mǎn)足l-多樣性，return T;end if;匿名數(shù)據(jù)集table=；Step2: while (T中不同敏感屬性值個(gè)數(shù)>=l) do r=種子記錄候選集LS中隨機(jī)選取一個(gè)記錄;聚類(lèi)C=r;聚類(lèi)質(zhì)心centroid=r;數(shù)據(jù)集T=T-r;while (|C|<l) domin=;for (i=1, 聚類(lèi)記錄候選集LT記錄個(gè)數(shù)) dorecord=LT中第i個(gè)記錄；if (record的敏感屬

28、性值與聚類(lèi)C中記錄的敏感屬性值相同) continue;il= record 與聚類(lèi)C質(zhì)心的信息損失IL recordcentroid;if (il<min) thenmin=il;minrecord=record;end if;end for;聚類(lèi)C=聚類(lèi)C信息損失最小記錄minrecord;候選集LT= LT信息損失最小記錄 minrecord ;數(shù)據(jù)集T=T信息損失最小記錄 minrecord ;重新計(jì)算聚類(lèi)質(zhì)心centroid;end while匿名數(shù)據(jù)集table=table生成的聚類(lèi)C;重新計(jì)算T中不同敏感屬性值個(gè)數(shù)，種子記錄候選集LS，聚類(lèi)記錄候選集LT；r=距離記錄r最遠(yuǎn)

29、的記錄;end whileStep3: while (|T|0) dor=從T中隨機(jī)取記錄r;T=Tr;for (i=1, 匿名數(shù)據(jù)集table中的聚類(lèi)個(gè)數(shù)) doC=第i個(gè)聚類(lèi)；if (C的記錄個(gè)數(shù)>=2*l-1) then continue;il=記錄r與聚類(lèi)C質(zhì)心信息損失IL rcentroid;if (il<min) thenmin=il;minc=i;end if;end for;信息損失最小聚類(lèi)minc = r信息損失最小聚類(lèi)minc;end whileStep4: 將匿名數(shù)據(jù)集table中的每個(gè)聚類(lèi)的所有記錄在準(zhǔn)標(biāo)識(shí)符上的屬性值用該聚類(lèi)代表記錄準(zhǔn)標(biāo)識(shí)符上的屬性值代替，

30、完成匿名化，得到最后輸出的匿名數(shù)據(jù)集table。EndLCA-FC和LCA-RC算法通過(guò)設(shè)置l-多樣性模型參數(shù)l，使得生成的每個(gè)聚類(lèi)至少有l(wèi)個(gè)不同的敏感屬性值，降低了隱私泄露的風(fēng)險(xiǎn)。重新分配剩余記錄時(shí)，若聚類(lèi)記錄個(gè)數(shù)達(dá)到2l-1時(shí)該聚類(lèi)則停止參與分配，控制生成聚類(lèi)的大小介于l和2l-1之間，以滿(mǎn)足最優(yōu)劃分。LCA-FC算法每次選擇距離上次種子記錄最遠(yuǎn)的記錄作為聚類(lèi)種子記錄，獲得了較好的劃分效果；選擇與種子記錄敏感屬性值不同的所有記錄作為候選集，在較大的記錄范圍中尋找信息損失最小記錄，可獲得較小的總體信息損失。LCA-RC算法每次從數(shù)據(jù)集中隨機(jī)選擇一個(gè)記錄作為聚類(lèi)種子記錄，選擇與聚類(lèi)中各記錄敏感

31、屬性值不相同且記錄數(shù)最多的一個(gè)敏感屬性值上的所有記錄作為候選集。該算法可較大減少剩余記錄，生成較多的聚類(lèi)，獲得較好的可區(qū)分度量。但是，由于LCA-RC算法生成的候選集較小，尋找信息損失最小記錄的范圍小，因而在獲得較好可區(qū)分度量的同時(shí)會(huì)導(dǎo)致比LCA-FC算法多一些的總體信息損失。此外，在生成聚類(lèi)時(shí)，若通過(guò)計(jì)算整個(gè)聚類(lèi)和每個(gè)候選記錄的信息損失來(lái)找到信息損失最小記錄加入聚類(lèi)，記錄的準(zhǔn)標(biāo)識(shí)符屬性值可能會(huì)被泛化到較大的值區(qū)域，引起較多的信息損失。因此，LCA-FC和LCA-RC算法總是計(jì)算聚類(lèi)質(zhì)心和每個(gè)候選記錄的信息損失來(lái)找到信息損失最小記錄，這樣可以減少信息的損失并提高算法效率。2.3實(shí)驗(yàn)結(jié)果與分析實(shí)

32、驗(yàn)硬件環(huán)境為Intel Pentium Dual E2180 2.0GHz CPU、2.0GB RAM，操作系統(tǒng)是Microsoft Windows XP。LK-member、LCA-FC和LCA-RC算法均采用C+語(yǔ)言編程實(shí)現(xiàn)，開(kāi)發(fā)環(huán)境是Microsoft visual Studio6.0。本文采用UC Irvine機(jī)器學(xué)習(xí)數(shù)據(jù)集中的真實(shí)數(shù)據(jù)集Adults人口普查數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)，這個(gè)數(shù)據(jù)集是匿名化研究領(lǐng)域的標(biāo)準(zhǔn)測(cè)試數(shù)據(jù)集。采用與文獻(xiàn)39一樣的方法對(duì)Adults數(shù)據(jù)進(jìn)行預(yù)處理，刪除存在信息缺失的記錄，得到30162個(gè)記錄的實(shí)驗(yàn)數(shù)據(jù)集。本文中只保留8個(gè)屬性: Age，Work Class，Ed

33、ucation，Marital Status，Race，Sex，Country，Occupation。其中Age和Education屬性為數(shù)值型屬性，其他屬性均為分類(lèi)屬性。用三個(gè)評(píng)價(jià)標(biāo)準(zhǔn)來(lái)衡量算法的有效性:(l) 總體信息損失Total-IL (2)可區(qū)分度量DM (3)運(yùn)行時(shí)間Running Time。為了進(jìn)行實(shí)驗(yàn)分析比較，本文對(duì)文獻(xiàn)32提出的基于k-匿名模型的k-member聚類(lèi)算法進(jìn)行修改，使之得到滿(mǎn)足l-多樣性模型的LK-member(l-diversity K-member)聚類(lèi)算法，LK-member算法采用選擇與上次種子記錄距離最遠(yuǎn)的記錄作為聚類(lèi)種子記錄，通過(guò)計(jì)算整個(gè)聚類(lèi)和每個(gè)候

34、選記錄的信息損失來(lái)找到信息損失最小記錄的策略。實(shí)驗(yàn)將本文提出的LCA-FC和LCA-RC算法與LK-member算法進(jìn)行總體信息損失、可區(qū)分度量和運(yùn)行時(shí)間性能比較。2.3.1 l-多樣性變化下實(shí)驗(yàn)結(jié)果分析實(shí)驗(yàn)中，取前7個(gè)屬性構(gòu)成準(zhǔn)標(biāo)識(shí)符，將屬性O(shè)ccupation作為敏感屬性，Occupation不同屬性值的個(gè)數(shù)為14個(gè)。實(shí)驗(yàn)中數(shù)據(jù)集Adults的記錄數(shù)n=30162，LK-member、LCA-FC和LCA-RC算法的l-多樣性模型參數(shù)l分別取值為2，3，4，5，6。總體信息損失、可區(qū)分度量和運(yùn)行時(shí)間三種實(shí)驗(yàn)結(jié)果分別如圖2-1、圖2-2和圖2-3所示。圖2-1 總體信息損失圖2-1的實(shí)驗(yàn)結(jié)果

35、反映了匿名化數(shù)據(jù)產(chǎn)生的總體信息損失。由于LK-member總是選擇與整個(gè)聚類(lèi)信息損失最小的記錄來(lái)生成聚類(lèi)，隨著l值的增大，生成的聚類(lèi)所包含記錄個(gè)數(shù)增多，記錄的準(zhǔn)標(biāo)識(shí)符屬性值可能會(huì)被泛化到更大的值區(qū)域，這將會(huì)引起更多的總體信息損失。而LCA-FC和LCA-RC算法總是選擇與聚類(lèi)質(zhì)心信息損失最小的記錄生成聚類(lèi)，隨著l值的增大，總體信息損失增長(zhǎng)較平穩(wěn)。LCA-FC算法由于采用選擇距離上次種子記錄最遠(yuǎn)的記錄作為聚類(lèi)種子記錄，并且在較大的候選集中尋找信息損失最小記錄的策略，因此獲得比LCA-RC算法小一些的總體信息損失。圖2-2 可區(qū)分度量圖2-2的實(shí)驗(yàn)結(jié)果表明，由于可區(qū)分度量只與聚類(lèi)大小有關(guān)，LCA-

36、RC算法總是從與聚類(lèi)中各記錄敏感屬性值不相同且記錄數(shù)最多的一個(gè)敏感屬性值上的所有記錄中選擇信息損失最小記錄加入聚類(lèi)，較大地減少了剩余記錄的產(chǎn)生，生成較多的聚類(lèi)，聚類(lèi)也較小，因而DM值較小，從而獲得了較好的可區(qū)分度。LK-member算法和LCA-FC算法產(chǎn)生剩余記錄較多些，因此可區(qū)分度相對(duì)較差些。圖2-3 運(yùn)行時(shí)間圖2-3的實(shí)驗(yàn)結(jié)果表明，LCA-FC和LCA-RC算法的運(yùn)行時(shí)間較少，而LK-member算法的運(yùn)行時(shí)間較多。這是由于LK-member算法需要計(jì)算整個(gè)聚類(lèi)和每個(gè)候選記錄的信息損失，而LCA-FC和LCA-RC算法只需計(jì)算聚類(lèi)質(zhì)心和每個(gè)候選記錄的信息損失，并且采用聚類(lèi)記錄候選集。因此

37、，LK-member算法所花費(fèi)的時(shí)間較多。此外，LCA-FC算法生成的候選集相對(duì)來(lái)說(shuō)比LCA-RC算法大一些，尋找信息損失最小記錄所花的時(shí)間也多一些，因此，LCA-FC算法所需的運(yùn)行時(shí)間比LCA-RC算法的運(yùn)行時(shí)間多一些。2.3.2 準(zhǔn)標(biāo)識(shí)符維數(shù)變化下實(shí)驗(yàn)結(jié)果分析實(shí)驗(yàn)中數(shù)據(jù)集Adults的記錄數(shù)n=30162，l=4，LK-member、LCA-FC和LCA-RC算法分別取前Age，Work Class，Education，Marital Status，Race，Sex，Country ，Occupation 屬性中前2，3，4，5，6個(gè)屬性構(gòu)成準(zhǔn)標(biāo)識(shí)符，將屬性O(shè)ccupation作為敏感屬性

38、，Occupation不同屬性值的個(gè)數(shù)為14個(gè)?？傮w信息損失、可區(qū)分度量和運(yùn)行時(shí)間三種實(shí)驗(yàn)結(jié)果分別如圖2-4、圖2-5和圖2-6所示。圖2-4 總體信息損失圖2-4表明LK-member、LCA-FC和LCA-RC算法的總體信息損失均隨準(zhǔn)標(biāo)識(shí)符維數(shù)增加而增加。這是由于隨著準(zhǔn)標(biāo)識(shí)符維數(shù)的增加，數(shù)據(jù)泛化時(shí)需要在等價(jià)類(lèi)更多屬性上進(jìn)行泛化，相應(yīng)地，總體信息損失也增多。圖2-5 可區(qū)分度量圖2-5的實(shí)驗(yàn)結(jié)果表明，LK-member和LCA-FC算法可區(qū)分度量的值均隨準(zhǔn)標(biāo)識(shí)符維數(shù)增加而增加，而LCA-RC算法可區(qū)分度量的值變化較小。隨準(zhǔn)標(biāo)識(shí)符維數(shù)增加，LK-member和LCA-FC算法生成的等價(jià)類(lèi)越大，

39、可區(qū)分度越小。而LCA-RC算法產(chǎn)生的剩余記錄少，生成等價(jià)類(lèi)數(shù)目較多，大小變化不大，因而獲得的可區(qū)分度變化不大。圖2-6 運(yùn)行時(shí)間圖2-6的實(shí)驗(yàn)結(jié)果表明，LK-member、LCA-FC和LCA-RC算法的運(yùn)行時(shí)間均隨準(zhǔn)標(biāo)識(shí)符維數(shù)增加而增加。這是由于隨著準(zhǔn)標(biāo)識(shí)符維數(shù)的增加，生成等價(jià)類(lèi)所進(jìn)行的計(jì)算和比較工作增加，因此所花費(fèi)的時(shí)間也較多。2.3.3 數(shù)據(jù)集記錄個(gè)數(shù)變化下實(shí)驗(yàn)結(jié)果分析實(shí)驗(yàn)中數(shù)據(jù)集Adults的記錄數(shù)n=30162，l=5，LK-member、LCA-FC和LCA-RC算法分別取數(shù)據(jù)集記錄個(gè)數(shù)分別為5000，10000，150000，20000，25000，30162。將屬性O(shè)ccup

40、ation作為敏感屬性，Occupation不同屬性值的個(gè)數(shù)為14個(gè)?？傮w信息損失、可區(qū)分度量和運(yùn)行時(shí)間三種實(shí)驗(yàn)結(jié)果分別如圖2-7、圖2-8和圖2-9所示。圖2-7 總體信息損失圖2-7反映了 LK-member、LCA-FC和LCA-RC算法的總體信息損均隨著數(shù)據(jù)集記錄數(shù)增加而增加。由于匿名數(shù)據(jù)集的總體信息損失是所有等價(jià)類(lèi)信息損失的和，在固定的l值下，隨著數(shù)據(jù)集記錄數(shù)增加，所生成等價(jià)類(lèi)數(shù)目增多，總體信息損失也隨之增加。圖2-8 可區(qū)分度量圖2-8反映了 LK-member、LCA-FC和LCA-RC算法可區(qū)分度量的值均隨著數(shù)據(jù)集記錄數(shù)增加而增加。由于可區(qū)分度量的值即為數(shù)據(jù)集中每一個(gè)等價(jià)類(lèi)大小

41、的平方的和，隨著數(shù)據(jù)集記錄數(shù)增加，所生成等價(jià)類(lèi)數(shù)目也增多，可區(qū)分度量的值也隨之加大。圖2-9 運(yùn)行時(shí)間圖2-9給出了|QI|和l值固定時(shí)，數(shù)據(jù)集大小對(duì)LK-member、LCA-FC和LCA-RC算法運(yùn)行時(shí)間的影響。隨著數(shù)據(jù)集記錄數(shù)增加，生成等價(jià)類(lèi)數(shù)目也增多，計(jì)算工作量增大，因而 LK-member、LCA-FC和LCA-RC算法運(yùn)行時(shí)間均隨著數(shù)據(jù)集記錄數(shù)增加而增加。2.4本章小結(jié)針對(duì)基于k-匿名模型的聚類(lèi)算法中存在著敏感屬性隱私泄露的問(wèn)題，本章提出了滿(mǎn)足l-多樣性模型的聚類(lèi)算法LCA-FC和 LCA-RC。算法所生成的匿名數(shù)據(jù)集中每個(gè)聚類(lèi)至少有l(wèi)個(gè)不同的敏感屬性值，每個(gè)聚類(lèi)的大小介于l和2l

42、之間，滿(mǎn)足最優(yōu)劃分并提高數(shù)據(jù)的安全性。在聚類(lèi)前生成候選記錄集以減少不必要的計(jì)算和比較，總是選擇與聚類(lèi)質(zhì)心信息損失最小的記錄生成聚類(lèi)，以提高算法效率并減少信息的損失。實(shí)驗(yàn)結(jié)果表明，LCA-FC和LCA-RC算法具有較高執(zhí)行效率，生成的匿名數(shù)據(jù)具有較好的可用性。本章的主要研究成果已被中文核心期刊計(jì)算機(jī)工程與設(shè)計(jì)錄用，即將刊登發(fā)表在該期刊上45。第三章 多敏感屬性的匿名化算法3.1問(wèn)題的提出本章討論多敏感屬性數(shù)據(jù)的匿名化。為了解決數(shù)據(jù)發(fā)布中的隱私泄露問(wèn)題，k-匿名模型要求等價(jià)類(lèi)的每個(gè)記錄在準(zhǔn)標(biāo)識(shí)符上有相同的屬性值，防止了個(gè)體身份的泄露。但是，k-匿名模型沒(méi)有考慮到敏感屬性值的多樣化，存在著敏感屬性隱

43、私泄露的風(fēng)險(xiǎn)。文獻(xiàn)4提出l-多樣性模型彌補(bǔ)了k-匿名模型的缺陷，要求每個(gè)等價(jià)類(lèi)中敏感屬性足夠多樣性以避免敏感屬性的隱私泄露，實(shí)現(xiàn)單一敏感屬性的數(shù)據(jù)發(fā)布。然而，在現(xiàn)實(shí)當(dāng)中，數(shù)據(jù)集中往往包含不止一個(gè)的敏感屬性，如果將單一敏感屬性的匿名化方法應(yīng)用于多敏感屬性的數(shù)據(jù)集，將會(huì)造成信息的損失和隱私的泄露。例如，假設(shè)網(wǎng)上發(fā)布了一個(gè)如表3-1的醫(yī)療信息表，準(zhǔn)標(biāo)識(shí)符為屬性組(年齡，性別，郵編 )，敏感屬性為疾病和工作級(jí)別。例如，將單敏感屬性的匿名化方法應(yīng)用于表3-1獲得表3-2的3-多樣化表，生成了3個(gè)等價(jià)類(lèi)t1，t2，t7，t4，t5，t9，t3，t6，t8。每個(gè)等價(jià)類(lèi)中的記錄在準(zhǔn)標(biāo)識(shí)符上具有相同的屬性值，并

44、且在敏感屬性疾病上具有3個(gè)不同屬性值。但是表3-2只滿(mǎn)足了敏感屬性疾病的3-多樣性而忽略了另一個(gè)敏感屬性工作級(jí)別，觀(guān)察等價(jià)類(lèi)t1，t2，t7，在敏感屬性疾病上具有3-多樣性，但在敏感屬性工作級(jí)別上卻具有相同的敏感屬性值。因而，表3-2中的匿名數(shù)據(jù)存在著隱私泄露的風(fēng)險(xiǎn)。表3-1醫(yī)療信息表年齡性別郵編疾病工作級(jí)別t141女734531失眠無(wú)薪t240女734552心臟病無(wú)薪t341男734532失眠私營(yíng)t444男734555心臟病聯(lián)邦政府t543男734555失眠州政府t645男734532心臟病地方政府t742男734561胃炎無(wú)薪t842女734533禽流感聯(lián)邦政府t943男734553禽流感

45、從未工作t1040女734531胃炎自雇表3-2 3-多樣化表1年齡性別郵編疾病工作級(jí)別t140-41*7345*失眠無(wú)薪t240-41*7345*心臟病無(wú)薪t740-41*7345*胃炎無(wú)薪t443-44男73455*心臟病聯(lián)邦政府t543-44男73455*失眠州政府t943-44男73455*禽流感從未工作t340-45*73453*失眠私營(yíng)t640-45*73453*心臟病地方政府t840-45*73453*禽流感聯(lián)邦政府t1040-45*73453*胃炎自雇此外，即使多敏感屬性匿名數(shù)據(jù)集等價(jià)類(lèi)各個(gè)敏感屬性對(duì)于準(zhǔn)標(biāo)識(shí)符屬性分別滿(mǎn)足l-多樣性，也不能完全保證多敏感屬性的l-多樣性。例如表

46、3-3是表3-1的針對(duì)敏感屬性疾病和工作級(jí)別的一個(gè)滿(mǎn)足3-多樣化模型的匿名化處理結(jié)果。表3-3中生成了3個(gè)等價(jià)類(lèi)t1，t3，t4，t8，t2，t5，t10，t6，t7，t9。每個(gè)等價(jià)類(lèi)中的記錄在(年齡，性別，郵編 )上具有相同的屬性值，并且分別在敏感屬性疾病和工作級(jí)別上具有3個(gè)不同值。但是觀(guān)察等價(jià)類(lèi)t1，t3，t4，t8，如果攻擊者根據(jù)杰克的準(zhǔn)標(biāo)識(shí)符屬性值知道杰克對(duì)應(yīng)的記錄在等價(jià)類(lèi)t1，t3，t4，t8中，若攻擊者還知道杰克在敏感屬性疾病上的值不是“失眠”，那么攻擊者就可以推斷出杰克在敏感屬性工作級(jí)別上的值為“聯(lián)邦政府”。由于等價(jià)類(lèi)t1，t3，t4，t8中敏感屬性疾病和工作級(jí)別的值之間缺乏多樣

47、性，表3-3中的匿名數(shù)據(jù)依然存在著敏感屬性隱私泄露的風(fēng)險(xiǎn)。表3-3 3-多樣化表2年齡性別郵編疾病Workclasst141-44*73453*失眠無(wú)薪t341-44*73453*失眠州政府t441-44*73453*心臟病聯(lián)邦政府t841-44*73453*禽流感聯(lián)邦政府t240-43*7345*心臟病無(wú)薪t540-43*7345*失眠州政府t1040-43*7345*胃炎自雇t642-45男7345*心臟病地方政府t742-45男7345*胃炎無(wú)薪t942-45男7345*禽流感從未工作文獻(xiàn)4給出了一個(gè)多屬性l-多樣性的概念。定義4-14：（多屬性l-多樣性）假設(shè)T表由準(zhǔn)標(biāo)識(shí)符屬性Q1，Q

48、m1和敏感屬性S1, , Sm2構(gòu)成。若對(duì)于每一個(gè)Si （i=1，m2）為敏感屬性， Q1，Qm1, S1, , Si-1, Si+1, , Sm2為準(zhǔn)標(biāo)識(shí)符屬性時(shí)表T是l-多樣性，那么表T是l-多樣性。多屬性l-多樣性規(guī)則也存在一些不足，當(dāng)敏感屬性的維數(shù)增加時(shí)，需要越來(lái)越大的等價(jià)類(lèi)來(lái)確保敏感屬性的l-多樣性，那么泛化等價(jià)類(lèi)準(zhǔn)標(biāo)識(shí)符屬性時(shí)也將導(dǎo)致更多的信息損失。并且，文獻(xiàn)4雖然提出了一個(gè)多屬性l-多樣性的概念，但沒(méi)有作更深入的探討，也沒(méi)有給出算法實(shí)現(xiàn)多個(gè)敏感屬性的數(shù)據(jù)發(fā)布。因此，在文獻(xiàn)4、5的基礎(chǔ)上，本章提出并實(shí)現(xiàn)一個(gè)滿(mǎn)足多敏感屬性l-多樣性的匿名化算法MSAL (multivariate s

49、ensitive attribute l-diversity)，以提高數(shù)據(jù)的安全性。3.2 基于l-多樣性模型的多敏感屬性匿名化算法設(shè)計(jì)與分析基于l-多樣性模型的多敏感屬性匿名化算法MSAL的主要思想是：首先確定數(shù)據(jù)集中n個(gè)敏感屬性的主次，然后按n個(gè)敏感屬性主次序的逆次序分別對(duì)數(shù)據(jù)集進(jìn)行排序，使得n個(gè)敏感屬性各自屬性值相同的記錄盡可能排在一起。然后按照第一敏感屬性值的不同，將數(shù)據(jù)集記錄分到若干個(gè)桶中，使得每個(gè)桶中的記錄擁有相同的第一敏感屬性值。按記錄數(shù)從大到小對(duì)桶進(jìn)行排序, 得到非空桶BK1, BKbknum，如果非空桶的數(shù)目bknuml，每次總是從最大桶BK1中取出一個(gè)記錄，然后按從大到小的

50、順序在其余桶中選擇尋找l-1個(gè)記錄生成記錄數(shù)為l的等價(jià)類(lèi)，要求等價(jià)類(lèi)中每個(gè)敏感屬性的l個(gè)屬性值都不同。然后重新對(duì)桶排序，重復(fù)相同的過(guò)程建立下一個(gè)等價(jià)類(lèi)。最后，將剩余記錄分到生成的等價(jià)類(lèi)中，控制加入剩余記錄的等價(jià)類(lèi)的大小介于l和2l-1之間，并且也要求加入剩余記錄的類(lèi)每個(gè)敏感屬性滿(mǎn)足最頻繁敏感值出現(xiàn)的次數(shù)與該類(lèi)記錄數(shù)之比小于等于1/l。采用文獻(xiàn)5中的方法，將結(jié)果分成多張數(shù)據(jù)表發(fā)布，其中一張表包含等價(jià)類(lèi)ID和各準(zhǔn)標(biāo)識(shí)符屬性等字段，其余每張表包含等價(jià)類(lèi)ID、一個(gè)敏感屬性、敏感屬性值計(jì)數(shù)等字段，準(zhǔn)標(biāo)識(shí)符屬性表與各敏感屬性表之間通過(guò)等價(jià)類(lèi)ID關(guān)聯(lián)。算法中信息損失采用1.2.3小節(jié)定義的信息損失機(jī)制來(lái)衡量

51、。基于l-多樣性模型的多敏感屬性匿名化算法MSAL形式描述如下：算法3.1 基于l-多樣性模型的多敏感屬性匿名化算法MSAL 輸入：原始數(shù)據(jù)集T，敏感屬性個(gè)數(shù)n和l-多樣性模型參數(shù)l；輸出：符合多個(gè)敏感屬性l-多樣性要求的匿名數(shù)據(jù)集tableBeginStep1: 確定數(shù)據(jù)集中n個(gè)敏感屬性及n個(gè)敏感屬性的主次。分別計(jì)算各敏感屬性的不同敏感屬性值個(gè)數(shù)；if (T中各敏感屬性的不同敏感屬性值個(gè)數(shù)<l) then不能滿(mǎn)足l-多樣性，return T;end if;按n敏感屬性次序的逆次序，從最后一個(gè)敏感屬性開(kāi)始，分別對(duì)數(shù)據(jù)集進(jìn)行排序；按照第一敏感屬性值的不同，把數(shù)據(jù)集T的記錄分到桶BK中,桶的

52、數(shù)目bknum；按記錄數(shù)對(duì)非空桶進(jìn)行排序, 得到非空桶BK0, BKbknum-1；最大桶maxbk =BK0;匿名數(shù)據(jù)集table=；Step2: while (非空桶的數(shù)目bknum>=l&&各敏感屬性的不同敏感屬性值個(gè)數(shù)>=l) do r=從最大桶maxbk中隨機(jī)選擇一個(gè)記錄；等價(jià)類(lèi)C=r;最大桶maxbk=最大桶maxbkr;for (i=1; i<bknum;i+) do max=0;for(j=0;j<第i個(gè)桶的記錄數(shù)目;j+)dorec=第i個(gè)桶中第j個(gè)記錄；for(k=0;k<等價(jià)類(lèi)C的記錄數(shù);k+)do如果rec記錄與等價(jià)類(lèi)C所有

53、記錄在n-1個(gè)敏感屬性的屬性值完全不相同, 則 record= rec， record為符合條件的記錄，退出循環(huán)變量為k,j的循環(huán)；否則回到j(luò)循環(huán)，繼續(xù)從第i個(gè)桶中尋找符合條件的記錄；end forend for;如果不存在符合條件的記錄record，回到i循環(huán)，從下一個(gè)桶中尋找符合條件的記錄；否則，聚類(lèi)C=聚類(lèi)C符合條件的記錄maxrecord ;從找到符合條件記錄的桶中刪除該記錄;如果等價(jià)類(lèi)C的記錄數(shù)等于l，退出i循環(huán)；end for;匿名數(shù)據(jù)集table=table生成的等價(jià)類(lèi)C;重新按記錄數(shù)對(duì)非空桶進(jìn)行排序, 計(jì)算非空桶的數(shù)目bknum,得到非空桶BK0, BKbknum；最大桶maxbk =BK0;重新計(jì)算各敏感屬性的不同敏感屬性值個(gè)數(shù)；end whileStep3: 數(shù)據(jù)集LS=聚類(lèi)后剩余的記錄；while (|LS|0) dor=從LS中隨機(jī)取記錄r;tnum=匿名數(shù)據(jù)集table中的等價(jià)類(lèi)個(gè)數(shù);for (i=1,tnum) do如果第i個(gè)等價(jià)類(lèi)的記錄數(shù)>2l-1，則該等價(jià)類(lèi)停止參與計(jì)算；如果將記錄r加入類(lèi)i仍然滿(mǎn)足每個(gè)敏感屬性最頻繁敏感值出現(xiàn)的次數(shù)與該等價(jià)類(lèi)記錄數(shù)之比小于等于1/l，第i個(gè)等價(jià)類(lèi)符合條件