最優(yōu)聚類的k-匿名數(shù)據(jù)隱私保護(hù)機(jī)制

張 強(qiáng) 葉阿勇 葉幗華 鄧慧娜 陳愛(ài)民

(福建師范大學(xué)計(jì)算機(jī)與網(wǎng)絡(luò)空間安全學(xué)院 福州 350117) (福建省網(wǎng)絡(luò)安全與密碼技術(shù)重點(diǎn)實(shí)驗(yàn)室(福建師范大學(xué)) 福州 350117)

大數(shù)據(jù)時(shí)代中，數(shù)據(jù)資源具有可復(fù)制、可共享、無(wú)限增長(zhǎng)和供給的屬性，能夠打破傳統(tǒng)要素有限供給對(duì)增長(zhǎng)的制約.數(shù)據(jù)也因?yàn)榛ヂ?lián)網(wǎng)及人工智能技術(shù)的賦能，成為推動(dòng)社會(huì)經(jīng)濟(jì)發(fā)展變革的新“石油”[1-2].如今，數(shù)據(jù)已和其他要素一起融入經(jīng)濟(jì)價(jià)值創(chuàng)造過(guò)程之中，對(duì)生產(chǎn)力發(fā)展具有廣泛影響.在該過(guò)程中，越來(lái)越多的用戶數(shù)據(jù)被政府部門和服務(wù)提供商進(jìn)行流通共享，主要用于數(shù)據(jù)挖掘和數(shù)據(jù)發(fā)布.然而，數(shù)據(jù)發(fā)布共享在給人們帶來(lái)便利的同時(shí)，也增加了相關(guān)個(gè)體或組織泄露隱私信息的風(fēng)險(xiǎn)[3-4].例如，疾控中心需要收集各醫(yī)院的病例信息用于疾病預(yù)防與控制，而這些病例信息中往往就包含病人不希望被揭露的敏感數(shù)據(jù)(所患疾病).因此，必須對(duì)公開(kāi)發(fā)布的數(shù)據(jù)采取一定的隱私保護(hù)方法，防止攻擊者通過(guò)背景知識(shí)或鏈接攻擊等手段獲取到用戶隱私信息[5].

k-匿名(k-anonymity)模型是一種重要的個(gè)體隱私保護(hù)模型，近年來(lái)備受關(guān)注[6-7].該方法要求共享數(shù)據(jù)中存在一定數(shù)量(≥k)在準(zhǔn)標(biāo)識(shí)符上不可區(qū)分的記錄，使攻擊者最多只能以1/k的概率通過(guò)準(zhǔn)標(biāo)識(shí)屬性關(guān)聯(lián)出標(biāo)識(shí)屬性，從而保護(hù)了個(gè)體的隱私.k-匿名能有效防范鏈接攻擊，但面對(duì)復(fù)雜的背景知識(shí)攻擊時(shí)，攻擊者仍然有可能以較高概率推斷出個(gè)體與敏感信息之間的關(guān)聯(lián)關(guān)系.因此，研究者在k-匿名的基礎(chǔ)上又提出基于聚類的k-匿名技術(shù).其基本思想是：先將待發(fā)布的數(shù)據(jù)集劃分為若干簇，然后將每個(gè)簇內(nèi)記錄的準(zhǔn)標(biāo)識(shí)符泛化為相同的屬性值，生成等價(jià)類，從而實(shí)現(xiàn)數(shù)據(jù)集的匿名化[8-9].然而，現(xiàn)有基于聚類的匿名方法大都是通過(guò)尋找最優(yōu)k-等價(jià)集來(lái)平衡隱私性與可用性.從全局看，k-等價(jià)集并不一定是滿足k-匿名的最優(yōu)等價(jià)集，因此，隱私機(jī)制的可用性仍然不是最優(yōu).如圖1所示，待匿名的準(zhǔn)標(biāo)識(shí)屬性包含6個(gè)數(shù)據(jù)，如果采用經(jīng)典k-匿名的聚類方法，如KACA聚類匿名方法(k-anonymisation by clustering in attribute hierarchies)[10]和GAA-CP聚類匿名方法(greedyk-anonymity algorithm based on clustering partition)[11]等，它們的基本思想是把6個(gè)數(shù)據(jù)進(jìn)行均勻2-匿名聚類，那么數(shù)據(jù)集將被劃分成3個(gè)等價(jià)集，如圖1(a)所示，通過(guò)計(jì)算可得匿名數(shù)據(jù)集的總方差為131.但圖1(b)的聚類結(jié)果也滿足2-匿名要求，其方差為27.64.很明顯，現(xiàn)有的聚類匿名方案無(wú)法實(shí)現(xiàn)最優(yōu)的數(shù)據(jù)聚類結(jié)果.

Fig. 1 k-anonymous clustering methods圖1 k-匿名聚類方法

為了解決以上問(wèn)題，本文提出一種基于聚類的最優(yōu)k-匿名數(shù)據(jù)隱私保護(hù)機(jī)制.通過(guò)建立數(shù)據(jù)距離與信息損失之間的線性關(guān)系，將k-匿名模型中的可用性最優(yōu)化問(wèn)題轉(zhuǎn)化為數(shù)據(jù)集的最優(yōu)聚類問(wèn)題，并利用貪婪算法和二分機(jī)制尋找滿足k-匿名約束條件的最優(yōu)等價(jià)集，從而實(shí)現(xiàn)滿足隱私性下的數(shù)據(jù)可用性最優(yōu)化.我們采用真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)分析，結(jié)果表明，在相同隱私約束的條件下本文方案展示了最小的信息損失.此外，當(dāng)數(shù)據(jù)之間相似性增大時(shí)，它在隱私和可用性權(quán)衡方面的優(yōu)勢(shì)將會(huì)變得更大.我們還展示了本文方案的效率，發(fā)現(xiàn)本文的數(shù)據(jù)匿名時(shí)間明顯優(yōu)于其他匿名方案.

1 相關(guān)工作

k-匿名作為一種有效的數(shù)據(jù)匿名手段，可以有效防止隱私泄露，自提出以來(lái)已經(jīng)被廣泛應(yīng)用于多個(gè)領(lǐng)域.Sweeney[12]在2002年提出了k-匿名模型.該模型保證攻擊者不能在準(zhǔn)標(biāo)識(shí)屬性上區(qū)分2個(gè)記錄，因?yàn)槊總€(gè)用戶被攻擊者正確識(shí)別的概率最多為1/k.k-匿名能有效防范鏈接攻擊，但面對(duì)復(fù)雜的背景知識(shí)攻擊時(shí)，攻擊者仍然有可能以較高的概率推斷出個(gè)體與敏感信息之間的關(guān)聯(lián)關(guān)系.因此，研究者在k-匿名的基礎(chǔ)上提出基于聚類的k-匿名技術(shù).

2006年，Aggarwal等人[13]在k-匿名中引入了聚類方法.Li等人[10]應(yīng)用聚類思想，提出了一種KACA匿名算法，它的主要思想是在匿名過(guò)程中循環(huán)合并等價(jià)類，直到所有等價(jià)類包含k個(gè)元組以上.該方法需要預(yù)定義所有的準(zhǔn)標(biāo)識(shí)屬性，并且沒(méi)有考慮敏感屬性多樣性特點(diǎn)，這樣會(huì)固化泛化模式，造成過(guò)多的信息損失.因此，王智慧等人[14]在文獻(xiàn)[10]基礎(chǔ)上考慮了敏感屬性多樣性，提出了一種l-聚類方法，它能夠滿足數(shù)據(jù)共享中對(duì)敏感屬性多樣性匿名的要求，減少了因過(guò)度泛化導(dǎo)致的信息丟失，但是該方法優(yōu)先考慮l-多樣性，在具體實(shí)現(xiàn)中可能會(huì)出現(xiàn)無(wú)解的情況.Liu等人[15]提出一種個(gè)性化擴(kuò)展(α,k)匿名模型來(lái)滿足個(gè)性化的隱私保護(hù)需求，根據(jù)敏感屬性的敏感程度將敏感屬性值分成若干組，并為每組限定屬性值的出現(xiàn)頻率，但是其沒(méi)有考慮敏感屬性的多樣性問(wèn)題.劉曉遷等人[16]提出了一種基于匿名聚類化的差分隱私保護(hù)數(shù)據(jù)發(fā)布方法，對(duì)匿名劃分的數(shù)據(jù)添加拉普拉斯噪聲，擾動(dòng)個(gè)體的真實(shí)數(shù)據(jù)，然而該方法只針對(duì)數(shù)值型數(shù)據(jù)，并沒(méi)有研究分類型和混合型數(shù)據(jù)發(fā)布隱私保護(hù)方法.因此，姜火文等人[11]利用貪心法和聚類劃分的思想，提出一種GAA-CP匿名算法是通過(guò)分類概化數(shù)值型和分類型準(zhǔn)標(biāo)識(shí)屬性，并分別度量其信息損失，聚類過(guò)程始終選取具有最小距離值的元組添加，從而保證信息損失總量趨于最小，但是該方法不能保證最優(yōu)的聚類結(jié)果.文獻(xiàn)[17]提出一種實(shí)現(xiàn)k-匿名性的新方法，在計(jì)算數(shù)據(jù)記錄之間的距離時(shí)考慮了準(zhǔn)標(biāo)識(shí)符屬性和敏感屬性之間的聯(lián)系、它們對(duì)敏感隱私的影響以及匿名過(guò)程中的信息丟失.同樣，差分隱私技術(shù)也可以引入聚類方法，Ni等人[18]提出了一種差分隱私保護(hù)的k-means聚類方法，通過(guò)添加自適應(yīng)噪聲和合并聚類，顯著提高了聚類的效用.具體來(lái)說(shuō)，為了獲得差分隱私的k簇，算法首先生成k個(gè)初始質(zhì)心，每次迭代添加自適應(yīng)噪聲得到k簇，最后將這些簇合并到k簇中.將聚類合并和自適應(yīng)噪聲結(jié)合使用可以進(jìn)一步顯著提高其效用，但是該算法因迭代過(guò)程復(fù)雜而影響實(shí)用性.Wang等人[19]提出差分隱私來(lái)釋放異構(gòu)數(shù)據(jù)進(jìn)行聚類分析，通過(guò)將聚類問(wèn)題轉(zhuǎn)化為分類問(wèn)題來(lái)解決這個(gè)問(wèn)題.該方法對(duì)原始數(shù)據(jù)進(jìn)行概率泛化，并在原始數(shù)據(jù)中加入噪聲以滿足差分隱私.但該方法不適用于分布式數(shù)據(jù)發(fā)布.為此，Wang等人[20]又提出一種任意分區(qū)數(shù)據(jù)的差分隱私數(shù)據(jù)發(fā)布機(jī)制，在半誠(chéng)實(shí)模型中用任意劃分的數(shù)據(jù)匿名化雙方數(shù)據(jù)的差分隱私方案且提出了一種分布式差分隱私匿名算法，保證該算法的每一步都滿足安全雙方計(jì)算的定義.

綜上所述，現(xiàn)有的數(shù)據(jù)隱私保護(hù)機(jī)制不能解決k-匿名模型中數(shù)據(jù)可用性的最優(yōu)化問(wèn)題，無(wú)法最小化信息損失.因此，本文提出一種基于最優(yōu)聚類的k-匿名隱私保護(hù)機(jī)制，利用貪婪算法和二分機(jī)制尋找滿足k-匿名約束條件的最優(yōu)聚類，從而實(shí)現(xiàn)k-匿名模型的可用性最優(yōu)化.

2 預(yù)備知識(shí)

在一般情況下，數(shù)據(jù)是以2維表數(shù)據(jù)形式進(jìn)行共享.表數(shù)據(jù)中每一行記錄對(duì)應(yīng)一個(gè)個(gè)體，每一條記錄又包含多個(gè)屬性，這些屬性大致可分為4類：標(biāo)識(shí)屬性(ID)、準(zhǔn)標(biāo)識(shí)屬性(U)、敏感屬性(V)和其他屬性(N).標(biāo)識(shí)屬性是指可以直接區(qū)分個(gè)體的屬性，例如姓名、身份證號(hào)碼和電話號(hào)碼；準(zhǔn)標(biāo)識(shí)符屬性是指通過(guò)鏈接可以推斷出個(gè)體身份的屬性，如性別、年齡和家庭地址等；敏感屬性是指包含隱私信息的屬性，如疾病和年收入等.表1為待發(fā)布的原始數(shù)據(jù)集，其中“Name”為標(biāo)識(shí)屬性，“Gender”“Age”“Zip”為準(zhǔn)標(biāo)識(shí)屬性，“Disease”為敏感屬性.數(shù)據(jù)隱私保護(hù)的本質(zhì)就是要切斷敏感屬性與標(biāo)識(shí)屬性的聯(lián)系，防止攻擊者在兩者間建立一一對(duì)應(yīng)關(guān)系.此外，鏈接攻擊可以從準(zhǔn)標(biāo)識(shí)符屬性推斷出個(gè)體與敏感屬性間的關(guān)聯(lián)關(guān)系.因此，最極端和簡(jiǎn)單的隱私方法就是直接刪除標(biāo)識(shí)屬性和準(zhǔn)標(biāo)識(shí)屬性.但僅剩下敏感屬性的數(shù)據(jù)表對(duì)于數(shù)據(jù)挖掘和數(shù)據(jù)發(fā)布等應(yīng)用而言將變得毫無(wú)用處.因此，數(shù)據(jù)隱私保護(hù)的一般研究目標(biāo)是在刪除標(biāo)識(shí)屬性的基礎(chǔ)上，對(duì)準(zhǔn)標(biāo)識(shí)屬性進(jìn)行適當(dāng)?shù)拿撁籼幚?，以維持隱私性與可用性間的平衡.

Table 1 Original Dataset表1 原始數(shù)據(jù)集

2.1 數(shù)據(jù)脫敏機(jī)制

數(shù)據(jù)共享的主要隱私保護(hù)方法是數(shù)據(jù)匿名，而泛化是數(shù)據(jù)匿名的主要手段.泛化是指將原始數(shù)據(jù)中某個(gè)準(zhǔn)標(biāo)識(shí)屬性的具體值用一個(gè)更廣的值域來(lái)代替.其隱私保護(hù)的思想就是通過(guò)泛化值域使得不同記錄在準(zhǔn)標(biāo)識(shí)屬性上不可區(qū)分，從而阻止針對(duì)具體準(zhǔn)標(biāo)識(shí)屬性值的表連接.由于鏈接攻擊依賴不同數(shù)據(jù)表間的表連接，因此k-匿名能夠有效地防范表鏈接攻擊.從保證最小化數(shù)據(jù)信息損失角度出發(fā)，我們對(duì)不同的準(zhǔn)標(biāo)識(shí)屬性類型采用不同方式的泛化.

1) 數(shù)值型準(zhǔn)標(biāo)識(shí)屬性.直接用等價(jià)集中各個(gè)數(shù)據(jù)屬性值的最小值域來(lái)代替原始數(shù)據(jù)的屬性值，實(shí)現(xiàn)最小泛化.例如，對(duì)于表1中的屬性Age，用最小值域[23,27]代替具體的取值“23”和“27”.

2) 分類型準(zhǔn)標(biāo)識(shí)屬性.各個(gè)屬性值可以根據(jù)泛化層次樹(shù)泛化為比原有屬性值更大的最小值代替，實(shí)現(xiàn)最小泛化.屬性值的最小泛化即為其對(duì)應(yīng)的葉子節(jié)點(diǎn)的最小上界節(jié)點(diǎn).例如，圖2為疾病的泛化層次樹(shù)，對(duì)于屬性Disease，我們可以用含義更廣的最小泛化節(jié)點(diǎn)“自身免疫病”代替具體的“流感”.

Fig. 2 Generalization hierarchy tree for “disease”圖2 “疾病”屬性的泛化層次樹(shù)

數(shù)據(jù)k-匿名一般是將數(shù)據(jù)按各個(gè)記錄的準(zhǔn)標(biāo)識(shí)屬性相近程度劃分為不同的等價(jià)集，然后對(duì)每個(gè)等價(jià)集進(jìn)行泛化匿名.而聚類基本思想是將一個(gè)表數(shù)據(jù)按照相似程度劃分為若干類.因此，兩者自然可以相互結(jié)合.我們通過(guò)聚類來(lái)構(gòu)造等價(jià)集，依此實(shí)現(xiàn)數(shù)據(jù)k-匿名.為了便于描述，我們給出了相關(guān)定義.

定義1.等價(jià)集.給定表數(shù)據(jù)S，若U為S中的準(zhǔn)標(biāo)識(shí)屬性集合，則每個(gè)在U上取值都相近的記錄集合構(gòu)成一個(gè)等價(jià)集，記為Di.

定義2.等價(jià)記錄.經(jīng)過(guò)泛化后的等價(jià)集Di，集合中所有記錄具有相同的準(zhǔn)標(biāo)識(shí)屬性值，統(tǒng)稱為等價(jià)記錄，記為lDi.

定義3.k-匿名.給定表數(shù)據(jù)S和等價(jià)集D，若S中的任意D至少包括k條記錄，則稱S滿足k-匿名.

我們以表1為例進(jìn)行隱私處理：移除標(biāo)識(shí)屬性和其他屬性，對(duì)于準(zhǔn)標(biāo)識(shí)屬性進(jìn)行泛化，對(duì)敏感屬性不做處理.表2為2-匿名后的結(jié)果，其中包括3個(gè)等價(jià)集，每個(gè)等價(jià)集中至少包含2條記錄.

Table 2 2-anonymous Dataset表2 2-匿名數(shù)據(jù)集

如表2所示，每一行代表1條等價(jià)記錄.其中，“行1,2”和“行3,4”均為1個(gè)等價(jià)集合，各包含2條等價(jià)記錄；“行5,6,7”為1個(gè)等價(jià)集，包含3條等價(jià)記錄.

2.2 匿名數(shù)據(jù)集的隱私保證

我們使用S表示原始表數(shù)據(jù)，S′表示匿名后的表數(shù)據(jù).表數(shù)據(jù)中每一行記錄對(duì)應(yīng)1個(gè)個(gè)體，用li表示.為了保護(hù)數(shù)據(jù)的隱私，我們采用k-匿名對(duì)表數(shù)據(jù)進(jìn)行隱私保護(hù)，并給出數(shù)據(jù)隱私保證的定義.

定義4.k-匿名數(shù)據(jù)隱私保護(hù)的安全性.假設(shè)S是原始表數(shù)據(jù)，采用k-匿名數(shù)據(jù)隱私保護(hù)機(jī)制對(duì)S中的準(zhǔn)標(biāo)識(shí)屬性泛化處理，并成功生成匿名表數(shù)據(jù)S′.在發(fā)布S′情況下，條件成立:

(1)

那么，就稱該k-匿名數(shù)據(jù)隱私保護(hù)方案是安全的.其中，k表示用戶對(duì)數(shù)據(jù)隱私保護(hù)需求，Pr(li|S′)表示攻擊者從發(fā)布的匿名表數(shù)據(jù)S′中正確識(shí)別出真實(shí)記錄li的概率.為了達(dá)到該目標(biāo)，需要保證對(duì)于表數(shù)據(jù)S中的每一個(gè)等價(jià)集Di中記錄個(gè)數(shù)都不少于k.

2.3 匿名數(shù)據(jù)集的可用性度量

為了從匿名數(shù)據(jù)集中獲得有用的信息，匿名數(shù)據(jù)的信息損失必須限制在一定閾值內(nèi).由于數(shù)據(jù)分為數(shù)值型數(shù)據(jù)和分類型數(shù)據(jù)，我們針對(duì)不同的數(shù)據(jù)類型，給出了不同的信息損失度量方法[21].

1) 數(shù)值型數(shù)據(jù)的可用性度量

(2)

例如，屬性Age的值域?yàn)閇0,100]，假設(shè)某一條記錄的屬性Age為40，其泛化后的取值為[40,50]，則該條記錄屬性Age泛化后的信息損失為(50-40)/100=0.1.

2) 分類型數(shù)據(jù)的可用性度量

(3)

例如，圖2中的疾病屬性的泛化層次樹(shù)有8個(gè)葉子節(jié)點(diǎn)，則|Bj|=8，若將“癌癥”泛化為“后天性疾病”.而“后天性疾病”的子葉節(jié)點(diǎn)個(gè)數(shù)為2，則其泛化后的信息損失為1/4.

結(jié)合1)和2)，我們可以計(jì)算任意表數(shù)據(jù)S在匿名處理后的數(shù)據(jù)可用性：

(4)

2.4 問(wèn)題定義

從直觀上看，用戶需要的隱私泄露越少，那么獲得的數(shù)據(jù)效用就越少，反之亦然.因此在基于我們的可用性度量來(lái)設(shè)計(jì)數(shù)據(jù)隱私發(fā)布機(jī)制M時(shí)，存在著隱私-可用性的平衡問(wèn)題.從數(shù)據(jù)可用性來(lái)看，受隱私約束的最小信息損失是多少，以及如何設(shè)計(jì)數(shù)據(jù)發(fā)布機(jī)制來(lái)實(shí)現(xiàn)最小信息損失，這是一個(gè)很自然的問(wèn)題.因此，本文通過(guò)目標(biāo)定義來(lái)表述這個(gè)問(wèn)題.

(5)

其中,IL(S)表示數(shù)據(jù)S的信息損失.

定義5提供了數(shù)據(jù)發(fā)布隱私保護(hù)框架，它包括構(gòu)造等價(jià)集和泛化2個(gè)過(guò)程.具體地說(shuō)，它以下面的形式來(lái)獲得最優(yōu)的表數(shù)據(jù)發(fā)布機(jī)制：給定原始的數(shù)據(jù)集S，通過(guò)在隱私性約束條件下達(dá)到最小信息損失來(lái)構(gòu)造匿名數(shù)據(jù)集S′，然后發(fā)布匿名數(shù)據(jù)集S′.定義5將k-匿名機(jī)制的最優(yōu)化問(wèn)題轉(zhuǎn)化為數(shù)據(jù)集的最優(yōu)聚類問(wèn)題，以k-匿名為約束條件，尋找信息損失最小的匿名數(shù)據(jù)集，實(shí)現(xiàn)最優(yōu)的聚類結(jié)果.

3 基于最優(yōu)聚類的k-匿名機(jī)制

3.1 總體框架

Fig. 3 k-anonymity mechanism based on optimal clustering圖3 基于最優(yōu)聚類的k-匿名機(jī)制

為了減少k匿名帶來(lái)的數(shù)據(jù)信息損失，我們引入貪婪算法和二分機(jī)制來(lái)尋找滿足k-匿名約束條件的最優(yōu)聚類，實(shí)現(xiàn)隱私-可用性問(wèn)題的最優(yōu)解.總體思想如圖3所示，對(duì)于待發(fā)布的數(shù)據(jù)集S，以距離最小化原則將其劃分2個(gè)等價(jià)子集S1和S2，若S1和S2都滿足k-匿名且兩者的信息損失和小于S的信息損失，則執(zhí)行該拆分步驟，否則不拆分，成為1個(gè)葉子節(jié)點(diǎn)Sleaf，以此迭代.我們定義二分簇的約束條件

(6)

在上述二分簇機(jī)制中，距離最小化原則可以使得各個(gè)類之內(nèi)的數(shù)據(jù)最為相似，而各個(gè)類之間的數(shù)據(jù)相似度差別盡可能大，從而保證最優(yōu)的聚類劃分，實(shí)現(xiàn)最優(yōu)k-匿名.此外，為了最大程度地減少數(shù)據(jù)的信息損失，我們將表數(shù)據(jù)中記錄之間準(zhǔn)標(biāo)識(shí)屬性的相近性與泛化后數(shù)據(jù)的信息損失結(jié)合起來(lái)，通過(guò)定義記錄間的距離來(lái)反映數(shù)據(jù)泛化的信息損失大小.記錄間的距離越小，它們之間的準(zhǔn)標(biāo)識(shí)屬性就越相近，泛化到同一等價(jià)集后所造成的信息損失也就越小.

3.2 記錄間的距離

定義6.記錄間的距離.給定表數(shù)據(jù)S，S中任意2條記錄la和lb在對(duì)應(yīng)各個(gè)準(zhǔn)標(biāo)識(shí)屬性間距離的均值定義為記錄間的距離，記為dis(la,lb).

由定義6可知，記錄間的距離反映了它們之間準(zhǔn)標(biāo)識(shí)屬性的相似程度，由兩者在各個(gè)準(zhǔn)標(biāo)識(shí)屬性間的距離決定.準(zhǔn)標(biāo)識(shí)屬性可分為數(shù)值型和分類型，因此，針對(duì)不同類型的準(zhǔn)標(biāo)識(shí)屬性給出了不同的計(jì)算方法[16].

1) 數(shù)值型準(zhǔn)標(biāo)識(shí)屬性間距離

給定表數(shù)據(jù)S，對(duì)于S中任意2條記錄la和lb，假設(shè)ti為記錄la和lb中第i個(gè)數(shù)值型準(zhǔn)標(biāo)識(shí)屬性，則記錄la和lb中數(shù)值型準(zhǔn)標(biāo)識(shí)屬性ti的距離計(jì)算為

(7)

其中,|x|表示絕對(duì)值，maxS(ti)和minS(ti)分別為數(shù)值型屬性ti在表數(shù)據(jù)中的最大值和最小值.

2) 分類型準(zhǔn)標(biāo)識(shí)屬性間距離

給定表數(shù)據(jù)S，對(duì)于S中任意2條記錄la和lb，假設(shè)tj為記錄la和lb中第j個(gè)分類型準(zhǔn)標(biāo)識(shí)屬性，則記錄la和lb中分類型準(zhǔn)標(biāo)識(shí)屬性tj的距離為

(8)

其中,|la(tj)|和|lb(tj)|分別是分類屬性tj的屬性值總數(shù)；Numla(wj)和Numlb(wj)分別為la和lb中wj的葉子節(jié)點(diǎn)個(gè)數(shù).

結(jié)合數(shù)值型準(zhǔn)標(biāo)識(shí)屬性間距離和分類型準(zhǔn)標(biāo)識(shí)屬性間距離，我們可以計(jì)算任意表數(shù)據(jù)S中記錄間的距離：

給定表數(shù)據(jù)S，對(duì)于S中任意2條記錄la和lb，假設(shè)有n個(gè)準(zhǔn)標(biāo)識(shí)屬性，其中數(shù)值型屬性個(gè)數(shù)為m，分類型屬性個(gè)數(shù)為n-m.ti為記錄la和lb中第i個(gè)數(shù)值型準(zhǔn)標(biāo)識(shí)屬性，tj為記錄la和lb中第j個(gè)分類型準(zhǔn)標(biāo)識(shí)屬性，則記錄la和lb間的距離計(jì)算為

(9)

其中,E(x)為x的均值.

3.3 基于聚類優(yōu)化的匿名算法

基于3.1節(jié)和3.2節(jié)的分析，本節(jié)提出一種基于聚類優(yōu)化的匿名算法(clustering optimization anonymous algorithm, COAA)，具體的偽代碼見(jiàn)算法1.

算法1.基于聚類優(yōu)化的匿名算法COAA(S,k).

輸入：數(shù)據(jù)集S、匿名參數(shù)k；

輸出：匿名數(shù)據(jù)集S′.

① 對(duì)S中所有的準(zhǔn)標(biāo)識(shí)屬性進(jìn)行最小泛化;

②ζ1,ζ2←newCore(S);

/*尋找2個(gè)新核心*/

③S1←{ζ1},S2←{ζ2};

④ for eachli∈S/*2-聚類*/

⑤ ifdis(li,ζ1)

⑥S1←S1+{li};

⑦ else

⑧S2←S2+{li};

⑨ end if

⑩ end for

|S1|>kand |S2|>k)

在算法1中，先將數(shù)據(jù)集中所有記錄看成一個(gè)等價(jià)集，對(duì)等價(jià)中所有的數(shù)據(jù)屬性進(jìn)行最小泛化；然后，在等價(jià)集中選取距離最遠(yuǎn)的2條記錄ζ1和ζ2作為新等價(jià)子集的中心，計(jì)算各條記錄與等價(jià)集中心之間的距離，并以距離最小化原則將S劃分為S1和S2；最后，判斷|S1|與|S2|中記錄的個(gè)數(shù)是否大于k，且它們的信息損失總和小于S的信息損失.如果是，則迭代此劃分過(guò)程；否則迭代終止.該聚類劃分方法可以使得各個(gè)類之內(nèi)的數(shù)據(jù)最為相似，而各個(gè)類之間的數(shù)據(jù)相似度差別盡可能大，保證最優(yōu)的聚類劃分，實(shí)現(xiàn)最優(yōu)k-匿名.

4 算法分析

4.1 有效性分析

定理1.不同記錄準(zhǔn)標(biāo)識(shí)屬性間的距離與這2個(gè)屬性泛化后的信息損失成正比.

證明.假設(shè)2條記錄為la和lb.記錄間的準(zhǔn)標(biāo)識(shí)屬性分為數(shù)值型準(zhǔn)標(biāo)識(shí)屬性和分類型準(zhǔn)標(biāo)識(shí)屬性.

1) 數(shù)值型準(zhǔn)標(biāo)識(shí)屬性

假設(shè)數(shù)值型屬性ti泛化為[pi,qi]，則它們泛化后的信息損失為

(10)

由于la(ti)和lb(ti)之間的距離為

(11)

則有

(12)

2) 分類型準(zhǔn)標(biāo)識(shí)屬性

假設(shè)分類型屬性tj泛化為wj，那么記錄la，lb在分類屬性Bj上泛化后的信息損失定義為

(13)

由于la(tj)和lb(tj)之間的距離為

(14)

則有

(15)

由此可得無(wú)論是數(shù)值型準(zhǔn)標(biāo)識(shí)屬性還是分類型準(zhǔn)標(biāo)識(shí)屬性，它們之間的距離與泛化后的信息損失成正比.因此，定理1成立.

證畢.

定理2.根據(jù)準(zhǔn)標(biāo)識(shí)屬性間距離最小原則，構(gòu)造滿足k匿名的最優(yōu)等價(jià)類，能夠保證生成的等價(jià)類具有最小泛化信息損失值.

證明.由定理1可知，數(shù)據(jù)的信息損失和數(shù)據(jù)間距離成正比，通過(guò)最小距離進(jìn)行聚類劃分來(lái)實(shí)現(xiàn)k-匿名最優(yōu)等價(jià)集，進(jìn)而可以保證信息損失達(dá)到最小.

證畢.

定理3.COAA算法能找到最優(yōu)解.

證明. 我們把本文COAA算法記為A，其解記為RA.如果算法A不是最優(yōu)的，那么就一定存在其他最優(yōu)算法.假設(shè)RB是和RA最相近的一個(gè)最優(yōu)算法解.其中，“最相近”是指算法B和算法A生成的前k-1個(gè)葉子集都相同，從第k個(gè)開(kāi)始不同.

綜上所述，我們找到了一個(gè)最優(yōu)解RB′，它和RA具有共同葉子集個(gè)數(shù)有k個(gè)，這和我們前提假設(shè)最多有k-1個(gè)相同相矛盾，所以，算法A是最優(yōu)的.

證畢.

4.2 安全性分析

在COAA算法中，對(duì)聚類后的數(shù)據(jù)進(jìn)行泛化處理，其本質(zhì)是對(duì)一定范圍內(nèi)的數(shù)據(jù)進(jìn)行匿名處理，以區(qū)域值代替具體的取值，故泛化處理后的數(shù)據(jù)取值相同，進(jìn)而攻擊者不能猜測(cè)出具體的數(shù)據(jù).COAA算法主要分為等價(jià)集劃分和泛化匿名2個(gè)階段.在等價(jià)集劃分階段，保證每一個(gè)等價(jià)集的記錄個(gè)數(shù)都大于等于k.在泛化匿名階段，保證同一等價(jià)集中各個(gè)記錄的準(zhǔn)標(biāo)識(shí)屬性取值相同.因此，在匿名數(shù)據(jù)集S′中任取一條等價(jià)記錄lDi，至少存在k-1條其他記錄，并且它們具有相同的準(zhǔn)標(biāo)識(shí)屬性值.顯然，匿名數(shù)據(jù)表S′滿足k-匿名，能夠有效抵制鏈接攻擊，有效保護(hù)數(shù)據(jù)隱私.

Fig. 4 How the information loss changes with |B| when k is constant圖4 k值固定時(shí)數(shù)據(jù)信息丟失隨屬性維數(shù)|B|的變化規(guī)律

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

本節(jié)通過(guò)實(shí)驗(yàn)分析驗(yàn)證COAA算法的性能，并且將COAA算法與文獻(xiàn)[12]提出的KACA算法和文獻(xiàn)[16]中提出的GAA-CP算法進(jìn)行比較.本實(shí)驗(yàn)所采用的數(shù)據(jù)來(lái)源于機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中的Adult數(shù)據(jù)集(AD-data)，保留了其中2 000個(gè)記錄的表數(shù)據(jù).本文與文獻(xiàn)[16]一樣，每一條記錄都保留了Age,Gender,Education,Marital Status,Race,Work Class,Native Country,Salary Class,Occupation這9個(gè)數(shù)據(jù)屬性，其中Occupation為敏感屬性.實(shí)驗(yàn)環(huán)境為：Intel?CoreTMi5-3470U CPU@3.20 GHz 2.40 GHz；4 GB(RAM)內(nèi)存；Windows 10專業(yè)版64位操作系統(tǒng)，基于X64的處理器；算法均采用MATLAB R2019a實(shí)現(xiàn).考慮到實(shí)驗(yàn)誤差的影響，每組實(shí)驗(yàn)重復(fù)進(jìn)行5次，結(jié)果取平均值.

5.1 信息損失比較

為了分析數(shù)據(jù)信息損失度隨屬性維度|B|、匿名參數(shù)k和不同數(shù)據(jù)集大小的變化規(guī)律，我們進(jìn)行了以下實(shí)驗(yàn).

Fig. 5 How the information loss changes with k when |B| is constant圖5 屬性維度|B|固定時(shí)數(shù)據(jù)信息損失隨k值的變化規(guī)律

1) 研究了不同的匿名k值對(duì)數(shù)據(jù)信息損失度的影響.圖4(a)～4(d)給出了當(dāng)k=4,6,8,10時(shí)，COAA算法、GAA-CP算法和KACA算法中數(shù)據(jù)屬性維度的變化對(duì)數(shù)據(jù)信息損失量大小的影響.從圖4中可以看到，隨著匿名參數(shù)k值的增大，3種算法下表數(shù)據(jù)的信息損失度也在不斷增大.這是由于隨著k值的增大，等價(jià)集中記錄的個(gè)數(shù)增加，將這些記錄進(jìn)行泛化為同一屬性值時(shí)，需要增大泛化程度，這樣各記錄數(shù)據(jù)的信息損失度將會(huì)增大，進(jìn)而總體的信息損失度也會(huì)增大.而且從圖4中可以發(fā)現(xiàn)，始終有IL(COAA)

2) 研究了對(duì)于同一個(gè)數(shù)據(jù)屬性維度|B|，不同的匿名k值對(duì)數(shù)據(jù)信息損失度的影響.圖5給出了當(dāng)|B|=3,5,7,9時(shí)，COAA算法、GAA-CP算法和KACA算法中匿名參數(shù)k值的變化對(duì)數(shù)據(jù)信息損失量大小.從圖5中可以看出，對(duì)于同一個(gè)|B|值，隨著匿名參數(shù)k值的增大，信息損失度也在不斷增大.這是由于隨著k值的增大，等價(jià)集中的元組的記錄個(gè)數(shù)增加，將這些記錄進(jìn)行泛化時(shí)，需要增大泛化程度，這樣各記錄數(shù)據(jù)的信息損失度將會(huì)增大，進(jìn)而總體的信息損失度也會(huì)增大.

3) 研究了在k=6，|B|=7時(shí)，不同數(shù)據(jù)集大小對(duì)數(shù)據(jù)信息損失度的影響.圖6給出COAA算法、GAA-CP算法和KACA算法中數(shù)據(jù)集大小的變化對(duì)數(shù)據(jù)信息損失量的影響.從圖6中可以看出，隨著數(shù)據(jù)個(gè)數(shù)的增加，3種模型的信息損失度都在不斷增大.這是由于匿名化操作的數(shù)據(jù)個(gè)數(shù)增加，需要處理的數(shù)據(jù)屬性值也會(huì)增加，進(jìn)而導(dǎo)致信息損失變大.而且從圖6可以發(fā)現(xiàn)，對(duì)于不同大小的數(shù)據(jù)集，本文所提的COAA算法的信息損失小于GAA-CP算法和KACA算法.

Fig. 6 The change for information loss with different data sets圖6 信息損失隨不同數(shù)據(jù)集大小的變化規(guī)律

5.2 執(zhí)行時(shí)間比較

圖7和圖8分別給出了COAA算法、GAA-CP算法和KACA算法隨不同的匿名參數(shù)k以及不同數(shù)據(jù)集下的執(zhí)行時(shí)間的比較.從圖8可以看出，當(dāng)k值發(fā)送變化時(shí)，其執(zhí)行時(shí)間也相應(yīng)改變.隨著k值的增大，執(zhí)行時(shí)間也在不斷增加.這是因?yàn)閗值增大，等價(jià)集中記錄的個(gè)數(shù)增加，泛化所需要的時(shí)間變長(zhǎng)，進(jìn)而執(zhí)行時(shí)間變長(zhǎng).在圖8中，我們?cè)O(shè)置了k=6,7的情況下執(zhí)行時(shí)間隨著數(shù)據(jù)集大小的變化規(guī)律，可以發(fā)現(xiàn)，隨著數(shù)據(jù)集的增大，運(yùn)行時(shí)間逐漸增加，這是由于數(shù)據(jù)集變大，相應(yīng)的等價(jià)集數(shù)量增加，進(jìn)而在泛化時(shí)所需要的時(shí)間也相應(yīng)變長(zhǎng).并且在圖7和圖8中，COAA算法的執(zhí)行時(shí)間相比GAA-CP算法和KACA算法，執(zhí)行時(shí)間總是最短.原因是：本文方法對(duì)數(shù)據(jù)進(jìn)行聚類劃分時(shí)始終采取二分法機(jī)制，在滿足可用性約束條件下進(jìn)行聚類劃分.由于我們聚類劃分的截止條件為2點(diǎn)：1)滿足等價(jià)集中記錄個(gè)數(shù)不少于k；2)劃分后子集合的信息損失(可用性)小于劃分前集合的信息損失,約束條件比其他2種算法更嚴(yán)格，所以聚類劃分次數(shù)相比其他2種算法較少，即執(zhí)行時(shí)間更短.

Fig. 7 Running time with different k values圖7 不同k值下的執(zhí)行時(shí)間

Fig. 8 Running time with different data sets圖8 不同數(shù)據(jù)集大小下的執(zhí)行時(shí)間

6 總 結(jié)

基于聚類的k-匿名機(jī)制是當(dāng)前數(shù)據(jù)隱私保護(hù)的主要方法，它能有效防范針對(duì)隱私的背景攻擊和鏈接攻擊.為了解決基于聚類的k-匿名機(jī)制中可用性和隱私性的平衡問(wèn)題，本文提出了一種基于貪心算法和二分聚類思想的最優(yōu)k-匿名數(shù)據(jù)隱私保護(hù)機(jī)制.選取表數(shù)據(jù)中最遠(yuǎn)的2條記錄作為聚類中心，然后按照k-匿名約束對(duì)數(shù)據(jù)集進(jìn)行迭代2-聚類劃分，盡可能使得各個(gè)類之內(nèi)的數(shù)據(jù)最為相似，從而保證了在滿足隱私需求條件下聚類的信息損失總量最小，即解決了k-匿名約束條件下的可用性最優(yōu)問(wèn)題.實(shí)驗(yàn)結(jié)果表明，在相同隱私約束的條件下，本文方案展示了最小的信息損失.此外，當(dāng)數(shù)據(jù)之間相似性增大時(shí)，它在隱私和可用性權(quán)衡方面的優(yōu)勢(shì)將會(huì)變得更大.我們還展示了本文方案的效率，發(fā)現(xiàn)本文方案數(shù)據(jù)匿名時(shí)間明顯優(yōu)于其他匿名方案.

作者貢獻(xiàn)聲明：張強(qiáng)負(fù)責(zé)方案的討論、性能分析以及論文撰寫(xiě)；葉阿勇指導(dǎo)方案的擬定和整體設(shè)計(jì)，把握論文創(chuàng)新性，并審閱修訂論文；葉幗華參與論文方案可行性討論與分析；鄧慧娜參與論文圖表設(shè)計(jì)與規(guī)劃；陳愛(ài)民參與論文公式與論文文字校對(duì).