個(gè)性化(p，α，k)-匿名隱私保護(hù)算法

蒲 東 方 睿

(成都信息工程大學(xué) 四川 成都 610225)

0 引 言

我們在享受信息技術(shù)發(fā)展給我們帶來便捷的同時(shí)，也暴露了大量與個(gè)體相關(guān)的數(shù)據(jù)， 而這些數(shù)據(jù)被政府、商業(yè)機(jī)構(gòu)等存儲(chǔ)、發(fā)布[1]。這些數(shù)據(jù)往往隱含大量的個(gè)人信息，因此，很容易造成個(gè)人隱私信息泄露[2-3]。例如， 公開的醫(yī)療記錄，可能對某位病人的隱私構(gòu)成威脅。因此，如何高效地保護(hù)個(gè)人隱私數(shù)據(jù)不被泄露， 同時(shí)減少數(shù)據(jù)的損失成為了當(dāng)下研究的熱點(diǎn)問題之一。

目前，保護(hù)個(gè)人隱私信息主要有三種技術(shù)方式[4]：數(shù)據(jù)加密技術(shù)、數(shù)據(jù)失真技術(shù)和數(shù)據(jù)匿名化技術(shù)。其中數(shù)據(jù)加密技術(shù)利用加密函數(shù)將原數(shù)據(jù)轉(zhuǎn)換為加密數(shù)據(jù)，提高了數(shù)據(jù)安全性，但是也極大地破壞了數(shù)據(jù)的可用性；數(shù)據(jù)失真技術(shù)是通過添加噪聲的方式給數(shù)據(jù)并保持?jǐn)?shù)據(jù)特性，該方法雖然保持了數(shù)據(jù)的原有的特性，但是不能保證數(shù)據(jù)安全性，還降低了可用信息數(shù)據(jù)的占比；數(shù)據(jù)匿名化技術(shù)采用不同匿名策略對數(shù)據(jù)進(jìn)行壓縮或者抽象，并保證隱私不被泄露的同時(shí)，又使得數(shù)據(jù)可用性最大化。因此，通常采用數(shù)據(jù)匿名化的技術(shù)實(shí)現(xiàn)個(gè)人隱私保護(hù)[5]。

1998年Samarati等首次提出了匿名化的概念，國內(nèi)外專家對其展開了廣泛深入的研究，找到防止或者減少隱私泄露同時(shí)使最大化數(shù)據(jù)可用性的方法。2002年Sweeney等匿名化概念首次提出了一種匿名的k-匿名模型[6]，對發(fā)布數(shù)據(jù)劃分成多個(gè)等價(jià)類且使每個(gè)等價(jià)類中至少有k個(gè)元組在準(zhǔn)標(biāo)識(shí)符屬性上相同，使攻擊者不能判別隱私信息所屬的個(gè)體。雖然k-匿名模型方法能有效減少準(zhǔn)標(biāo)識(shí)符屬性泄露風(fēng)險(xiǎn)，但是沒有保護(hù)機(jī)制減少敏感屬性泄露的風(fēng)險(xiǎn)，不能達(dá)到有效的保護(hù)隱私的目的[7-8]。2007年,針對敏感屬性泄露問題Machanavajjhala等[9]在k-匿名的基礎(chǔ)上提出了l多樣性-匿名模型，要求等價(jià)類中敏感屬性的敏感屬性值至少有l(wèi)個(gè)“良性”值；Li等[10]提出了t-接近模型，要求等價(jià)類中敏感屬性值的分布和原數(shù)據(jù)表的分布間距不大于閾值t。之后文獻(xiàn)[11]基于k匿名模型提出了(α，k)-匿名模型，在滿足看匿名模型的前提，同時(shí)要求敏感屬性值出現(xiàn)頻率小于等于α。文獻(xiàn)[12]在防止同質(zhì)攻擊思想提出了p-sensitive k-匿名模型，對等價(jià)類中每個(gè)敏感屬性值出現(xiàn)的種類數(shù)進(jìn)行限制：每個(gè)等價(jià)類中每個(gè)敏感屬性值至少出現(xiàn)p個(gè)不同敏感屬性值。這些模型提供了表級(jí)別的保護(hù)粒度，都能在一定程度上防止或者減少隱私泄露風(fēng)險(xiǎn)，但是沒有考慮個(gè)人需求，造成了一些不必要的信息損失。

在日常生活中，對于不同的個(gè)體敏感度，相同的敏感屬性敏感度也不一定不相同，因此，在進(jìn)行個(gè)性化隱私保護(hù)就必須依據(jù)個(gè)體差異下對敏感屬性值的敏感度進(jìn)行個(gè)性化保護(hù)[13]。文獻(xiàn)[14]采用個(gè)人隱私自治原則，局部敏感屬性編碼思想對敏感屬性進(jìn)行個(gè)性化泛化提出了個(gè)性化k-匿名算法。文獻(xiàn)[15]基于l多樣性-匿名模型提出了個(gè)性化(α,l)-多樣性匿名模型，要求匿名后的數(shù)據(jù)滿足l多樣性-匿名模型的同時(shí)，多樣性表的敏感屬性值的頻率不大于α。文獻(xiàn)[16]提出了基于(α，k)-匿名模型建立了個(gè)性化(α，k)-匿名隱私保護(hù)模型，通過對準(zhǔn)標(biāo)識(shí)符屬性進(jìn)行k匿名隱私保護(hù)方法劃分等價(jià)類，且將敏感屬性值敏感度劃分成不同的敏感組，然后對不同級(jí)別敏感度的敏感組設(shè)置不同的閾值α，從而達(dá)到個(gè)性化隱私保護(hù)的目的。文獻(xiàn)[17]在對多敏感屬性進(jìn)行保護(hù)的情形下，提出了對多敏感值進(jìn)行保護(hù)的個(gè)性化隱私保護(hù)算法。文獻(xiàn)[18]提出了用聚類的方式實(shí)現(xiàn)個(gè)性化的一種基于變長聚類的個(gè)性化匿名保護(hù)方法。文獻(xiàn)[5]基于p-sensitive k匿名模型建立了個(gè)性化(p，k)-匿名模型，通過對敏感屬性的敏感度進(jìn)行分級(jí)劃分成不同等級(jí)的敏感屬性值，然后對不同等級(jí)的敏感屬性值泛化為不同層次的低精度的敏感屬性泛化值，達(dá)到對敏感屬性值個(gè)性化匿名隱私保護(hù)的目的。由此可見，個(gè)性化保護(hù)越來越受到關(guān)注和重視。

本文基于個(gè)性化(p，k)-匿名模型和個(gè)性化(α，k)-匿名模型，提出針對匿名后的數(shù)據(jù)損失度較大，和存在同質(zhì)攻擊的泄露隱私風(fēng)險(xiǎn)的改進(jìn)的個(gè)性化隱私保護(hù)算法。根據(jù)個(gè)體間敏感程度的差異將敏感屬性值進(jìn)行劃分成高、中、低不同的敏感級(jí)別。根據(jù)敏感屬性的不同等級(jí)采用不同的匿名保護(hù)的方法：通過建立敏感屬性泛化樹，將高敏感度的屬性值進(jìn)行降級(jí)泛化，達(dá)到降低高敏感屬性泄露的風(fēng)險(xiǎn)，然后針對中敏感屬性和低敏感屬性通過閾值α限制等價(jià)類中每個(gè)敏感屬性值的出現(xiàn)的頻率。以此降低匿名后數(shù)據(jù)的損失和隱私泄露風(fēng)險(xiǎn)，使數(shù)據(jù)可用性的最大化。

1 匿名模型

數(shù)據(jù)集中的屬性根據(jù)功能可以劃分為三種類別[1]，第一類是標(biāo)識(shí)符屬性I，可以根據(jù)其屬性的值唯一確定標(biāo)識(shí)某一個(gè)個(gè)體的屬性，例如居民身份證號(hào)屬性、姓名屬性等。因此，如果要進(jìn)行數(shù)據(jù)發(fā)布時(shí)，就必須用某種隱藏方式保證其隱私，通常我們都會(huì)采用直接刪除其屬性的方式；第二類是可以通過鏈接其他數(shù)據(jù)表識(shí)別個(gè)體的屬性或?qū)傩约系臏?zhǔn)標(biāo)識(shí)符屬性QI，例如性別屬性、郵編屬性、年齡屬性等；最后一類是可以帶表個(gè)體隱私的屬性我們稱為敏感屬性S，例如健康狀況屬性、收入情況屬性等，不同的個(gè)體對隱私定義也不一樣，因此，敏感屬性的選擇可能也不同。

例如，表1所示為病歷的原數(shù)據(jù)表，表中屬性Name的屬性值是可以唯一標(biāo)識(shí)個(gè)體，因此，NAME為標(biāo)識(shí)符屬性，發(fā)布數(shù)據(jù)時(shí)應(yīng)該刪除其屬性避免隱私泄露；Sex、Age、Zipcode是準(zhǔn)標(biāo)識(shí)符屬性，對表操作時(shí)應(yīng)該匿名化操作；Disease是敏感屬性。

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

定義1(k匿名[19])假設(shè)數(shù)據(jù)表T{A1,A2,…,An}，QI是T中可以通過鏈接的其他數(shù)據(jù)表識(shí)別個(gè)體的準(zhǔn)標(biāo)識(shí)符屬性，T在QI上的投影為T[QI]，如果每組值在QI投影T[QI]至少重復(fù)出現(xiàn)k次，則稱T滿足k匿名。

定義2(等價(jià)類[19])假設(shè)數(shù)據(jù)表T{A1,A2,…,An}，數(shù)據(jù)表子集取元組中準(zhǔn)標(biāo)識(shí)符屬性值相同的集合，則稱該集合為一個(gè)等價(jià)類。

因此，如果數(shù)據(jù)表滿足k匿名，則任意一個(gè)等價(jià)類中準(zhǔn)標(biāo)識(shí)符屬性上相等的元組數(shù)至少為k。

表2為2-匿名數(shù)據(jù)表，將表1中的標(biāo)識(shí)符隱藏，將準(zhǔn)標(biāo)識(shí)符屬性通過泛化操作輸出精度較低的值。

表2 2-匿名數(shù)據(jù)表

定義3((α，k)-匿名模型[16])數(shù)據(jù)表T{A1,A2,…,An}，匿名后數(shù)據(jù)表T′，如果T′滿足k匿名，每個(gè)等價(jià)類元組數(shù)至少為k，在準(zhǔn)標(biāo)識(shí)符屬性上取值一致，且在敏感屬性的取值相同取值重復(fù)出現(xiàn)的頻率不大于α，則稱匿名后的數(shù)據(jù)表T′滿足(α，k)-匿名模型。

表3為(0.5，2)-匿名數(shù)據(jù)表，將表1中的標(biāo)識(shí)符隱藏，將準(zhǔn)標(biāo)識(shí)符屬性通過泛化操作輸出精度較低的值。敏感屬性使其滿足每個(gè)等價(jià)類中同一敏感屬性的頻率大于0.5。

表3 (0.5，2)-匿名數(shù)據(jù)表

定義4((p，k)-匿名模型[5])數(shù)據(jù)表T{A1,A2,…,An}，匿名后數(shù)據(jù)表T′，如果T′滿足k匿名，每個(gè)等價(jià)類元組數(shù)至少為k，在準(zhǔn)標(biāo)識(shí)符屬性上取值一致，且在敏感屬性上不同取值個(gè)數(shù)不小于p，則稱匿名后的數(shù)據(jù)表T′滿足(p，k)-匿名模型。

表4為(2，2)-匿名數(shù)據(jù)表，將表1中的標(biāo)識(shí)符隱藏，將準(zhǔn)標(biāo)識(shí)符屬性通過泛化操作輸出精度較低的值，將敏感屬性泛化，并使其滿足每個(gè)等價(jià)類中不同敏感屬性值至少有2個(gè)。

表4 (2，2)-匿名數(shù)據(jù)表

2 個(gè)性化(p，α，k)-匿名隱私保護(hù)模型

由于k匿名模型對除了標(biāo)識(shí)符屬性的取值進(jìn)行了匿名化，雖然可以有效地防止攻擊者通過鏈接攻擊的方式泄露隱私，但存在等價(jià)類中敏感屬性取值一致的情況，攻擊者可以通過同質(zhì)攻擊的方式竊取個(gè)人隱私，造成隱私泄露，因此要對敏感屬性進(jìn)行保護(hù)防止泄露隱私問題。由于不同的個(gè)體的敏感屬性不同且不同的敏感個(gè)體敏感度的不同，因此需要對敏感屬性進(jìn)行個(gè)性化隱私保護(hù)[13]。個(gè)性化(α，k)-匿名模型是基于(α，k)-匿名模型，對不同等級(jí)的敏感屬性設(shè)置不同的閾值α，雖然考慮了根據(jù)敏感度進(jìn)行分級(jí)保護(hù)，但是存在高敏感屬性泄露的風(fēng)險(xiǎn)，例如對表1進(jìn)行個(gè)性化(0.5，2)-匿名，發(fā)布的數(shù)據(jù)依然存在高敏感屬性值HIV，存在背景知識(shí)攻擊泄露的風(fēng)險(xiǎn)。個(gè)性化(p，k)-匿名模型基于(p，k)-匿名模型，根據(jù)不同等級(jí)的敏感屬性采用不同的泛化策略：將高敏感度的屬性值泛化到對應(yīng)樹的根節(jié)點(diǎn)的值；將中敏感度的屬性值泛化到對應(yīng)的父節(jié)點(diǎn)的值。其次，采用值的限定方法，使得泛化后的等價(jià)類中至少存在p個(gè)不同的屬性值。這種策略雖然提供了一種對不同敏感度的敏感屬性值的個(gè)性化隱私保護(hù)方法，但是也造成了巨大的數(shù)據(jù)損失，且如果數(shù)據(jù)分布相似度很高，則會(huì)有很大幾率泄露隱私。例如原始表中的敏感屬性取值HIV，經(jīng)過個(gè)性化(p，k)-匿名后屬性取值為疾病，假設(shè)HIV泛化后取值為內(nèi)科疾病，保護(hù)了個(gè)人隱私。因此在對敏感屬性的個(gè)性化保護(hù)的同時(shí)保證數(shù)據(jù)的可用性也同樣重要，本文主要使針對高敏感屬性值進(jìn)行泛化，然后針對中敏感屬性和低敏感屬性通過閾值α限制等價(jià)類中每個(gè)敏感屬性值的出現(xiàn)的頻率，使泛化后等價(jià)類中敏感屬性值分布均勻，以此降低匿名后數(shù)據(jù)的損失和隱私泄露風(fēng)險(xiǎn)。

2.1 敏感屬性的敏感度劃分

本文根據(jù)用戶對敏感屬性值的敏感度劃分敏感級(jí)別，針對個(gè)體敏感性的敏感度實(shí)施分級(jí)保護(hù)。

定義5(敏感屬等級(jí))，若在數(shù)據(jù)集為T，其中某個(gè)敏感屬性的值集合為{S1,S2,…,Sd}，對敏感屬性的敏感度評(píng)定。規(guī)定當(dāng)敏感度為[0，30]時(shí)為低敏感度，(30，60]為中敏感度，(60，90]為高敏感度。

表5為用戶的定義敏感度。

表5 敏感屬敏感度評(píng)定表

定義6(泛化屬性值敏感度)假設(shè)某個(gè)泛化屬性值Y,以其為根的子樹其子節(jié)點(diǎn)集合為{S1,S2,…,Sm},則泛化屬性值的敏感度為：

(1)

2.2 敏感屬性泛化樹

根據(jù)敏感屬性的取值對其屬性構(gòu)建屬性泛化樹G，將每個(gè)原始的敏感屬性的取值均存放在樹的葉子結(jié)點(diǎn)中，根據(jù)式(1)計(jì)算屬性泛化樹上每個(gè)泛化節(jié)點(diǎn)值的敏感度。對不同的敏感級(jí)別的敏感屬性值進(jìn)行不同方式的泛化，規(guī)定將高敏感級(jí)別的敏感屬性值泛化到中敏感級(jí)別的敏感屬性值，其他敏感屬性的泛化按照等價(jià)類中不同敏感屬性的個(gè)數(shù)和每個(gè)敏感屬性進(jìn)行相應(yīng)的泛化。如圖1所示，敏感屬性為疾病，取值為{Asthma，Pneumonia，F(xiàn)lu，Cancer，HIV，Measles}。若根據(jù)評(píng)分認(rèn)為Asthma(哮喘)是高敏感屬性泛化到下一級(jí)敏感屬性值呼吸病，若不能泛化到下一級(jí)敏感度則泛化到根節(jié)點(diǎn)疾病為止。

圖1 敏感屬性泛化樹

2.3 精度度量

本文主要采用泛化技術(shù)來實(shí)現(xiàn)匿名操作，因此一定存在信息的損失。本文參考文獻(xiàn)[5]的對分類型屬性進(jìn)行層次泛化的精度測量和數(shù)值型屬性進(jìn)行區(qū)間泛化的精度測量，并給出以下相關(guān)定義。

定義7(分類型屬性損失度)假設(shè)某一屬性值P通過泛化樹泛化到節(jié)點(diǎn)Q，若Q節(jié)點(diǎn)子樹的個(gè)數(shù)記為MQ，則屬性值P泛化到節(jié)點(diǎn)Q信息損失度為：

(2)

式中：C表示P的父節(jié)點(diǎn)。

例如，如果將圖1中Asthma泛化到了疾病節(jié)點(diǎn)，則P=Asthma，Q=疾病，C=呼吸病，泛化過程中子樹個(gè)數(shù)序列為{M呼吸病=3，M疾病=3}，因此從Asthma泛化到了疾病節(jié)點(diǎn)信息損失為Loss(Asthma，疾病)=8/9。

定義8(數(shù)值型屬性損失度)假設(shè)某一數(shù)值型屬性值P通過屬性泛化樹泛化為Q，泛化的區(qū)間為[L,R]，則損失度為：

(3)

例如將屬性年齡25泛化到25～30,泛化區(qū)間為[25，30]，則泛化后損失為Loss(25，25～30)=4/5。

3 算法設(shè)計(jì)

本文提出的一種對敏感屬性的個(gè)性化保護(hù)的匿名隱私保護(hù)算法為個(gè)性化(p，α，k)-匿名隱私保護(hù)算法，算法對不同等級(jí)的敏感屬性采用不同的隱私方法策略：對高敏感屬性進(jìn)行泛化操作，避免高敏感屬性值泄露。針對中敏感等級(jí)和低敏感等級(jí)的敏感屬性采用個(gè)性化閾值α方法進(jìn)行隱私保護(hù)。算法的大體思想是：將高敏感屬性的值泛化為中敏感屬性值，然后限定等價(jià)類中等級(jí)敏感屬性值和低敏感屬性值出現(xiàn)的頻率不大于α，并保證等價(jià)類中不同敏感屬性值的個(gè)數(shù)不小于p。

算法思想步驟：

1) 根據(jù)準(zhǔn)標(biāo)識(shí)符屬性值的相似性分成每組k條記錄的若干元組的集合，將每個(gè)組泛化成等價(jià)類。

2) 將每個(gè)等價(jià)類中按敏感度由高到低進(jìn)行排列，并將高敏感屬性值向上泛化成下一級(jí)敏感屬性值。

3) 統(tǒng)計(jì)每個(gè)等價(jià)中的不同敏感屬性值的個(gè)數(shù)是否大于p，若小于p則將相對高的敏感屬性值進(jìn)行泛化并使得泛化后的值的頻率小于α，直到等價(jià)類中不同的敏感屬性值個(gè)數(shù)大于等于p。

4) 核查每個(gè)等價(jià)類中每個(gè)屬性值的頻率是否小于等于α，若大于α則進(jìn)行泛化操作，并使得泛化后值的頻率不能大于α。

算法個(gè)性化(p，α，k)-匿名隱私保護(hù)算法。

輸入待發(fā)布的原始數(shù)據(jù)表T，敏感屬性敏感度評(píng)定表ST，匿名參數(shù)k，等價(jià)類不同敏感屬性值個(gè)數(shù)最小參數(shù)p，每個(gè)敏感值在等價(jià)類中出現(xiàn)的最大頻率α。

輸出匿名表T′

(1) 將數(shù)據(jù)表中的所有屬性依次構(gòu)建屬性泛化樹，并根據(jù)敏感度評(píng)定表ST對敏感屬性泛化樹上的泛化值根據(jù)式(1)計(jì)算其泛化后的敏感度；

(2) 統(tǒng)計(jì)數(shù)據(jù)表的記錄數(shù)size，若size

(3) 從數(shù)據(jù)表中取出在準(zhǔn)標(biāo)識(shí)符屬性值上相似度最高的k條記錄元組，并將元組存放到t中，然后返回執(zhí)行(2)；

(4) 將數(shù)據(jù)表剩余的值根據(jù)準(zhǔn)標(biāo)識(shí)符屬性的相似度加入到list中的元組中；

(5) 按照i從1～n循環(huán)遍歷元組t={t1,t2,…,tn}：

① 若ti為非空集合，屬性集合A{A1,A2,…,Am}，初始化m個(gè)size(ti)大小的集合{set1,set2,…,setm}，按照j從1～m遍歷集合：

② 按照j從1～m遍歷，若屬性為敏感屬性將高敏感屬性泛化為下一級(jí)敏感屬性值并將每個(gè)屬性值ti,j存放到setj中；

③ 按照從1～m遍歷集合set，若Aj為準(zhǔn)標(biāo)識(shí)符屬性，則執(zhí)行④，若Aj為敏感屬性則執(zhí)行⑤；

④ 根據(jù)setj值的分布泛化到當(dāng)前屬性泛化樹中最小泛化的值Vj并將元組ti的當(dāng)前屬性的值全部設(shè)置為Vj；

⑤ 將當(dāng)前敏感屬性值ti[:,j]使其滿足其不同敏感值的個(gè)數(shù)不小于p且每個(gè)敏感值的頻率不大于α；

⑥ 返回元組t合并成匿名表T′。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)數(shù)據(jù)及參數(shù)

實(shí)驗(yàn)環(huán)境：Intel(R) Core(TM) i3-6100 CPU @3.70 GHz，4.00 GB內(nèi)存， Microsoft Windows10操作系統(tǒng)，編程語言為Python 3.6。實(shí)驗(yàn)選用的是UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫中的Adult數(shù)據(jù)集，刪除其中的缺省值處理得到共計(jì)30 162條記錄，本文選取其中6個(gè)屬性{Occupation，Age，Workclass，Education，Relationship，sex}，其數(shù)據(jù)結(jié)構(gòu)見表6。將Occupation作為敏感屬性，其他的作為準(zhǔn)標(biāo)識(shí)符屬性，敏感屬性O(shè)ccupation的屬性值設(shè)定的敏感度見表7。

表6 原UCI數(shù)據(jù)集Adult數(shù)據(jù)表結(jié)構(gòu)

表7 敏感屬性值敏感度

實(shí)驗(yàn)從信息損失度與執(zhí)行時(shí)間2個(gè)方面進(jìn)行分析比較。主要是比較以下模型：

(1) k-匿名模型：通過泛化樹最小信息代價(jià)泛化構(gòu)造匿名表，對定義的敏感屬性不進(jìn)行泛化處理。

(2) 個(gè)性化(α，k)-匿名模型：通過泛化樹最小信息代價(jià)泛化構(gòu)造匿名表，且對不同等級(jí)敏感度設(shè)定不同的閾值α，實(shí)現(xiàn)對敏感屬性個(gè)性化匿名保護(hù)。

(3) 個(gè)性化(p，k)-匿名模型：通過泛化樹最小信息代價(jià)泛化構(gòu)造匿名表，通過對不同等級(jí)敏感度的敏感屬性泛化不到不同的層次。高敏感屬性泛化為根節(jié)點(diǎn)，中敏感屬性泛化為父節(jié)點(diǎn)，并使等價(jià)類中不同敏感值的個(gè)數(shù)不小于閾值p，從而實(shí)現(xiàn)個(gè)性化匿名隱私保護(hù)。

(4) 個(gè)性化(p，α，k)-匿名模型：通過泛化樹最小信息代價(jià)泛化構(gòu)造匿名表，通過對不同等級(jí)敏感屬性采用不同的匿名方式：將高敏感屬性值泛化為中敏感屬性值，然后將其他等級(jí)的敏感屬性值采用閾值α進(jìn)行匿名化，并使等價(jià)類中不同敏感值的個(gè)數(shù)不小于閾值p，從而實(shí)現(xiàn)個(gè)性化匿名隱私保護(hù)。

4.2 執(zhí)行時(shí)間分析

設(shè)準(zhǔn)標(biāo)識(shí)符屬性個(gè)數(shù)為5、數(shù)據(jù)集大小為30 162，當(dāng)k值改變時(shí)，比較四個(gè)匿名算法的執(zhí)行時(shí)間，如圖2所示?？芍S著k值的增大，四種算法的執(zhí)行時(shí)間反而減小。這主要因?yàn)楸疚氖遣捎脧脑磾?shù)據(jù)集中取出準(zhǔn)標(biāo)識(shí)符屬性上相似度最高的k條記錄直到數(shù)據(jù)集為空為止，當(dāng)k值增大時(shí)，等價(jià)類的數(shù)量減少，因此執(zhí)行時(shí)間會(huì)減小。本文的個(gè)性化(p，α，k)匿名算法，因?yàn)樾枰獫M足的條件根據(jù)多樣化，進(jìn)行比較的次數(shù)會(huì)增加，因此比其他算法的執(zhí)行時(shí)間要高。

圖2 執(zhí)行時(shí)間

4.3 信息損失度分析

信息損失度用式(2)、式(3)來度量，設(shè)準(zhǔn)標(biāo)識(shí)符屬性個(gè)數(shù)為5，數(shù)據(jù)集大小為30 162，當(dāng)k值改變時(shí)，比較四種匿名算法的平均信息丟失程度，如圖3所示。四種算法的平均信息丟失程度隨著k值的增加而增加，因?yàn)閗值越大，每個(gè)等價(jià)類中元組的數(shù)量將增加，等價(jià)類中元組的泛化將更高，從而導(dǎo)致更多的信息丟失。其中，k匿名算法的平均信息丟失最小的原因是該算法僅對標(biāo)識(shí)符的屬性進(jìn)行泛化操作，因此信息平均損失度比其他三種匿名算法低；個(gè)性化(α，k)-匿名算法對不同的敏感級(jí)別的敏感屬性值設(shè)置不同閾值實(shí)現(xiàn)個(gè)性化匿名隱私保護(hù)，而個(gè)性化(p，α，k)-匿名算法只是對中級(jí)敏感屬性值和低級(jí)敏感屬性設(shè)置不同閾值，其信息損失要比個(gè)性化(α，k)-匿名算法低；個(gè)性化(p，k)-匿名算法將高敏感度的敏感屬性泛化到樹的根節(jié)點(diǎn)，中敏感度的敏感屬性泛化到父節(jié)點(diǎn)。而個(gè)性化(p，α，k)-匿名算法采用泛化樹和閾值α方法共同實(shí)現(xiàn)個(gè)性化隱私保護(hù)，只對高敏感度的敏感屬性采用泛化樹的方式泛化到父節(jié)點(diǎn)，其他敏感級(jí)別屬性值采用閾值α方法，因此信息損失度地個(gè)性化(p，k)-匿名要低。

圖3 平均損失度

5 結(jié) 語

本文提出了個(gè)性化(p，α，k)匿名隱私保護(hù)算法，根據(jù)敏感屬性值的屬性度、屬性泛化樹按照式(1)計(jì)算泛化屬性值敏感度；通過敏感級(jí)別定義建立對敏感屬性值分級(jí)，然后對高敏感度屬性值采用泛化樹進(jìn)行降級(jí)泛化，對中級(jí)敏感屬性值和低級(jí)敏感屬性值采用不同閾值α限制其在等價(jià)類的頻率。通過該算法匿名發(fā)布數(shù)據(jù)，雖然從時(shí)間上看，花費(fèi)了比其他算法多一點(diǎn)的時(shí)間代價(jià)，但是從隱私和信息損失方面，降低了數(shù)據(jù)隱私泄露風(fēng)險(xiǎn)和信息損失量。