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

1、基于匿名機(jī)制的數(shù)據(jù)發(fā)布中隱私泄露控制技術(shù)第一章引言1.1 研究背景數(shù)據(jù)發(fā)布環(huá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í)符、敏感屬性三類。數(shù)據(jù)發(fā)布時(shí)直接刪 除標(biāo)識(shí)符以保護(hù)個(gè)體隱私。但是可能存在攻擊者通過準(zhǔn)標(biāo)識(shí)符與外部公開的數(shù)據(jù)源進(jìn)行 鏈接攻擊（linking attack） 1,導(dǎo)致個(gè)體隱私的泄露。研究表明，這種鏈接攻擊可以識(shí)別 大量美國(guó)公民的身份1o例如，假設(shè)一個(gè)網(wǎng)站上發(fā)布了一個(gè)醫(yī)療信息表，為保護(hù)個(gè)體隱私，將原始數(shù)據(jù)中能 識(shí)別個(gè)體身份的標(biāo)識(shí)符（姓名）刪除之

2、后得到數(shù)據(jù)發(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

3、心臟病t741男734561禽流感t842男734533禽流感t943女734553禽流感表1-2選民登記表姓名年齡性別郵編愛麗絲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

4、.1 匿名保護(hù)模型1.2.1.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ù)集 滿足k-匿名。定義1.21等價(jià)類 一個(gè)等價(jià)類即數(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ù)集中用抽象的屬性值來代替原來具體的屬性值， 隱匿是指隱匿是指直接刪除數(shù)據(jù)集中某些屬性值或記錄。k-匿名通過泛化和隱匿使得等價(jià)類中每個(gè)記錄

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

6、卻無法將法蘭克與其中的某 個(gè)記錄相對(duì)應(yīng)起來，從而避免法蘭克隱私的泄露。表1-3 3 -匿名化表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í)攻擊的問題4。k -匿名模型由于忽略了敏感屬性值的多樣性，可能造成個(gè)體敏感屬性的隱私泄露，即同質(zhì)性攻擊。例如，假 設(shè)表1-4是表1-1的另一個(gè)滿足3-匿名模型的匿名

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

8、疾病t140-41*7345*失眠t240-41*7345*心臟病t340-41*7345*失眠t444-45男7345*心臟病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-匿名模型的不足。定義184 l-多樣性原則一個(gè)等價(jià)類如果對(duì)于敏感屬性 s至少包含l個(gè)不同的敏感屬性值，那么該等價(jià)類是l-多樣性的。如果數(shù)據(jù)集t中的每個(gè)等價(jià)類是l-多樣性的， 則稱該數(shù)據(jù)集滿足l-

9、多樣性。該模型除了要求滿足k-匿名之外，還要求每個(gè)等價(jià)類的敏感屬性值具有多樣性以防 止敏感屬性的隱私泄露。例如，表 1-5是表1-1的一個(gè)滿足3-多樣性模型的匿名化表， 其中，l=3, q 1=(年齡，性別，郵編)。表1-5中生成了 3個(gè)等價(jià)類t1, t2, t7, t4, t5, t9, t3, t6, t8。每個(gè)等價(jià)類中的記錄在(年齡，性別,郵編)上具有相同的屬性 值，并且在敏感屬性疾病上具有 3個(gè)不同值。因而，表1-5中的數(shù)據(jù)能夠防止鏈接攻擊 所導(dǎo)致的敏感屬性隱私泄露。雖然l-多樣性模型可以提供比k-匿名模型更強(qiáng)的隱私保護(hù)，但是，l-多樣性模型依 然存在不足之處，l-多樣性模型同樣采用泛

10、化和隱匿技術(shù)對(duì)原始數(shù)據(jù)進(jìn)行匿名處理，因 而也存在信息損失的情況。表1-5 3-多樣性表年齡性別郵編疾病t140-41*7345*失眠t240-41*7345*心臟病t740-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ù)表之間通過group-

11、id關(guān)聯(lián)。anatomy匿名模型對(duì)等價(jià)類的準(zhǔn)標(biāo)識(shí)符屬性不作泛化和隱匿處理，直接將準(zhǔn)標(biāo)識(shí)符屬性數(shù)據(jù)發(fā)布，因而保留了大量原始數(shù)據(jù)的信息，大大提高了匿名數(shù)據(jù)的可 用性。同時(shí)，anatomy將數(shù)據(jù)分成兩張表發(fā)布，使得攻擊者無法將個(gè)體的準(zhǔn)標(biāo)識(shí)符屬性 和敏感屬性一一對(duì)應(yīng)起來，提高了數(shù)據(jù)的安全性。由于anatomy匿名模型是在l-多樣性 模型的基礎(chǔ)上提出的，l-多樣性模型上存在的一些不足，在 anatomy匿名模型中也依然 存在。例如，表1-6是表1-1的一個(gè)滿足anatomy模型的匿名化結(jié)果，假設(shè)攻擊者知道某 個(gè)個(gè)體在group-id為1的等價(jià)類中。雖然攻擊者可以從準(zhǔn)標(biāo)識(shí)符屬性表獲知該個(gè)體的 年齡，性別，

12、郵編具體值，但他無法從敏感屬性表中準(zhǔn)確獲得敏感屬性疾病的值，由于 group-id為1的疾病值的個(gè)數(shù)為3,因此攻擊者只能以1/3的幾率進(jìn)行猜測(cè)。數(shù)據(jù)發(fā)布中，研究出提供更強(qiáng)保護(hù)能力的匿名模型依然是匿名保護(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)

13、計(jì)1失眠11心臟病11禽流感12心臟病12失眠12禽流感13失眠13心臟病13禽流感11.2.2 匿名算法采用匿名技術(shù)由原始數(shù)據(jù)生成最優(yōu)匿名數(shù)據(jù)是一個(gè)np難問題9,10,因此，設(shè)計(jì)出高效的近似最優(yōu)算法是匿名保護(hù)中的重要工作。目前數(shù)據(jù)發(fā)布中采用的匿名技術(shù)主要 有：泛化和隱匿、聚類以及交換等技術(shù)。采用泛化和隱匿技術(shù)的匿名算法主要有：datafly算法11、mingen最小泛化算法網(wǎng)incognito算法12、ga (genetic algorithm)算法13、自底向上的泛化方法14、自頂向 下的泛化方法15、基于多維空間劃分的k-匿名方法16。國(guó)內(nèi)研究者也在文獻(xiàn)17-20中對(duì) 泛化和隱匿技術(shù)進(jìn)行

14、了研究。泛化和隱匿技術(shù)將等價(jià)類中不同的準(zhǔn)標(biāo)識(shí)符屬性值泛化為 相同值以達(dá)到隱私保護(hù)的目的，造成了原始數(shù)據(jù)大量信息的損失。同時(shí)，基于泛化和隱 匿技術(shù)的匿名算法采用基于泛化層次結(jié)構(gòu)的策略會(huì)引起不必要的信息損失。為了解決泛化和隱匿技術(shù)存在的不足，在數(shù)據(jù)的匿名化中引入聚類技術(shù)?；诰垲?的匿名化方法的主要思想是：首先將數(shù)據(jù)劃分為多個(gè)聚類，然后分別泛化每個(gè)聚類的準(zhǔn) 標(biāo)識(shí)符屬性以達(dá)到匿名化。文獻(xiàn)21提出模糊c-均值算法。文獻(xiàn)22提出基于k-modes 的算法。文獻(xiàn)23,24提出了基于k-means聚類算法的k-匿名方法。文獻(xiàn)25提出mdav k- 匿名算法。在 mdav算法的基礎(chǔ)上，文獻(xiàn)26提出了 v-md

15、av(variable-mdav)算法。 文獻(xiàn)27,28提出了帶權(quán)重的聚類方法。文獻(xiàn)29-32提出了基于聚類的k-匿名算法?；?于聚類的匿名算法不依賴于泛化層次結(jié)構(gòu)，因此生成的匿名數(shù)據(jù)集具有更高可用性。數(shù)據(jù)交換是將數(shù)據(jù)集中某些屬性的值進(jìn)行互換以防止隱私泄露33-35。文獻(xiàn)5提出了一種不基于泛化和隱匿技術(shù)的交換方法anatomy。文獻(xiàn)36-38也提出了基于交換的隱私數(shù)據(jù)發(fā)布算法。采用交換技術(shù)的匿名化算法通過交換增加了隱私數(shù)據(jù)的不確定性，從 而保護(hù)隱私數(shù)據(jù)的安全。并且交換技術(shù)直接發(fā)布準(zhǔn)標(biāo)識(shí)符屬性，保留了原始數(shù)據(jù)的大量 信息，極大地提高了匿名數(shù)據(jù)聚集查詢的準(zhǔn)確性。1.2.3 匿名質(zhì)量評(píng)估匿名化原始數(shù)

16、據(jù)必然會(huì)引起信息損失,需要找到適合的評(píng)估機(jī)制來計(jì)算匿名后的信息損失以衡量匿名算法和匿名數(shù)據(jù)集的優(yōu)劣以下是匿名質(zhì)量評(píng)估中常用的信息損失評(píng)15估機(jī)制：定義1.1口1, 32等價(jià)類信息損失il(e)。假設(shè)等價(jià)類er1,rk由準(zhǔn)標(biāo)識(shí)符由數(shù)值屬性 (n1,nm)和分類屬性(c1,cn)構(gòu)成，則等價(jià)類信息損失il(e)為：il(e) = e.( i =1,.,m(maxni-minni)nidistinctc十工ii_-)j.nc .-j公式中|e|是e中記錄個(gè)數(shù)，|ni|表示數(shù)值屬性的范圍，max和min分別是e中關(guān)于屬nin,性ni的最大最小值。|cj|表示分類屬性的不同屬性值個(gè)數(shù)，distinct表

17、示e中關(guān)于屬 ,disiincic,性cj的不同屬性值個(gè)數(shù)。定義1.232總體信息損失total_il。若e e1,em是匿名數(shù)據(jù)集t中所有等價(jià)類的 集合，那么t的總體信息損失為：total _ il(at) =e-il(e)?？傮w信息損失能夠反映匿名數(shù)據(jù)集相對(duì)原始數(shù)據(jù)集所產(chǎn)生的信息損失。止匕外，文獻(xiàn) 39中定義的可區(qū)分度量機(jī)制也可用來衡量匿名化質(zhì)量。定義 1.3網(wǎng) 可區(qū)分度量 dm (discernability metric)定義為 dm =工equivc1asses e e2，其中 |e|表示等價(jià)類e中的記錄個(gè)數(shù)，dm的值即為數(shù)據(jù)集中每一個(gè)等價(jià)類大小的平方的和。 可區(qū)分度量的意義在于：等

18、價(jià)類越大可區(qū)分度就越小，意味著一個(gè)記錄在大的等價(jià)類中 難以區(qū)分。定義1.45聚集查詢平均相對(duì)錯(cuò)誤率。一個(gè)查詢的相對(duì)錯(cuò)誤率為|act- est|/act, act 是對(duì)原始數(shù)據(jù)進(jìn)行查詢獲得的實(shí)際結(jié)果，est是對(duì)匿名數(shù)據(jù)進(jìn)行查詢獲得的推測(cè)結(jié)果。 每個(gè)查詢相對(duì)錯(cuò)誤率的和的平均值即為聚集查詢平均相對(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)展，給出 本文章節(jié)的組織結(jié)構(gòu)。在第二章中，將著重討論基于聚類的敏感屬性l-多樣性匿名化算法的設(shè)計(jì)與實(shí)現(xiàn)。

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

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

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

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

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

24、算法處理 的數(shù)據(jù)包括數(shù)值屬性和分類屬性，信息損失機(jī)制必須既適用于數(shù)值型數(shù)據(jù)又適用于分類 型數(shù)據(jù)的信息損失計(jì)算。因此聚類所產(chǎn)生的信息損失采用1.2.3小節(jié)定義的信息損失機(jī)制來衡量。下面分別描述基于聚類的敏感屬性l-多樣性匿名化算法lca-fc和lca-rc : 算法2.1 lca-fc 算法 輸入：原始數(shù)據(jù)集 t和1-多樣性模型參數(shù)l;輸出：符合1-多樣性模型要求的匿名數(shù)據(jù)集tablebeginstepl:計(jì)算數(shù)據(jù)集t不同敏感屬性值個(gè)數(shù)；if （t中不同敏感屬性值個(gè)數(shù) =l） do 聚類c=r;聚類質(zhì)心 centroid = r;數(shù)據(jù)集t=t.r;聚類記錄候選集1丁=從數(shù)據(jù)集t中選擇與種子記錄敏

25、感屬性不相同的記錄； while （|c| l） domin = 00;for （i=1,，候選集lt記錄個(gè)數(shù)）do record=lt 中第i個(gè)記錄；if （record的敏感屬性值與聚類 c中記錄的敏感屬性值相同 ）continue; il= record到聚類 c質(zhì)心的信息損失 il record u centroid;if（ il =2*l-1） then continue;il=記錄r與聚類c質(zhì)心信息損失il r u centroid;if （il min） thenmin=il;minc=i;end if;end for;信息損失最小聚類minc = ru信息損失最小聚類minc;

26、end whilestep4:將匿名數(shù)據(jù)集table中的每個(gè)聚類的所有記錄在準(zhǔn)標(biāo)識(shí)符上的屬性值用該聚類代表記錄準(zhǔn)標(biāo)識(shí)符上的屬性值代替，完成匿名化，得到最后輸出的匿名數(shù)據(jù)集table。end算法2.2 lca-rc算法輸入：原始數(shù)據(jù)集 t和1-多樣性模型參數(shù)l;輸出：符合1-多樣性模型要求的匿名數(shù)據(jù)集tablebeginstepl:計(jì)算數(shù)據(jù)集t不同敏感屬性值個(gè)數(shù)，種子記錄候選集ls=從數(shù)據(jù)集t中選擇敏感屬性值相同且數(shù)目最多的所有記錄，聚類記錄候選集lt=數(shù)據(jù)集t-種子記錄候選集 ls-敏感屬性值相同且數(shù)目最少的所有記錄；if （ t中不同敏感屬性值個(gè)數(shù) =l） do二種子記錄候選集 ls中隨機(jī)選

27、取一個(gè)記錄；聚類c= r;聚類質(zhì)心 centroid = r;數(shù)據(jù)集t=t- r;while （|c|l） domin = 00;for （i=1,，聚類記錄候選集 lt記錄個(gè)數(shù)）dorecord=lt 中第i個(gè)記錄；if （record的敏感屬性值與聚類c中記錄的敏感屬性值相同）continue;il= record與聚類 c質(zhì)心的信息損失 il record u centroid;if （il =2* l-1） then continue;il=記錄r與聚類c質(zhì)心信息損失il r u centroid;if （il l,每次總是從最大桶 bk1中取出一個(gè)記錄，然后按從大到小的順序在其余桶

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

29、于1-多樣性模型的多敏感屬性匿名化算法msal形式描述如下：算法3.1基于1-多樣性模型的多敏感屬性匿名化算法msal輸入：原始數(shù)據(jù)集 敏感屬性個(gè)數(shù)n和1-多樣性模型參數(shù)1; 輸出：符合多個(gè)敏感屬性 1-多樣性要求的匿名數(shù)據(jù)集 tab1ebeginstep1:確定數(shù)據(jù)集中n個(gè)敏感屬性及n個(gè)敏感屬性的主次。 分別計(jì)算各敏感屬性的不同敏感屬性值個(gè)數(shù)；if （t中各敏感屬性的不同敏感屬性值個(gè)數(shù)=1&各敏感屬性的不同敏感屬性值個(gè)數(shù)=1） do二從最大桶maxbk中隨機(jī)選擇一個(gè)記錄； 等價(jià)類c=r;最大桶maxbk=最大桶maxbk -r;for (i=1; ibknum;i+) domax=0;for(j=0;j第i個(gè)桶的記錄數(shù)目；j+)dorec=第i個(gè)桶中第j個(gè)記錄；for(k=0; k等價(jià)類 c的記錄數(shù)；k+)do如果rec記錄與等價(jià)類c所有記錄在n-1個(gè)敏感屬性的屬性值完全不相同，則record= rec, record為符合條件的記錄，退出循環(huán)變量為k,j的循環(huán)；否則回到j(luò)循環(huán)，繼續(xù)從第i個(gè)桶中尋找符合條件的記錄；end forend for;如果不