最優聚類的k-匿名數據隱私保護機制

張 強 葉阿勇 葉幗華 鄧慧娜 陳愛民

(福建師范大學計算機與網絡空間安全學院 福州 350117) (福建省網絡安全與密碼技術重點實驗室(福建師范大學) 福州 350117)

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

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

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

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

1 相關工作

k-匿名作為一種有效的數據匿名手段，可以有效防止隱私泄露，自提出以來已經被廣泛應用于多個領域.Sweeney[12]在2002年提出了k-匿名模型.該模型保證攻擊者不能在準標識屬性上區分2個記錄，因為每個用戶被攻擊者正確識別的概率最多為1/k.k-匿名能有效防范鏈接攻擊，但面對復雜的背景知識攻擊時，攻擊者仍然有可能以較高的概率推斷出個體與敏感信息之間的關聯關系.因此，研究者在k-匿名的基礎上提出基于聚類的k-匿名技術.

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

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

2 預備知識

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

Table 1 Original Dataset表1 原始數據集

2.1 數據脫敏機制

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

1) 數值型準標識屬性.直接用等價集中各個數據屬性值的最小值域來代替原始數據的屬性值，實現最小泛化.例如，對于表1中的屬性Age，用最小值域[23,27]代替具體的取值“23”和“27”.

2) 分類型準標識屬性.各個屬性值可以根據泛化層次樹泛化為比原有屬性值更大的最小值代替，實現最小泛化.屬性值的最小泛化即為其對應的葉子節點的最小上界節點.例如，圖2為疾病的泛化層次樹，對于屬性Disease，我們可以用含義更廣的最小泛化節點“自身免疫病”代替具體的“流感”.

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

數據k-匿名一般是將數據按各個記錄的準標識屬性相近程度劃分為不同的等價集，然后對每個等價集進行泛化匿名.而聚類基本思想是將一個表數據按照相似程度劃分為若干類.因此，兩者自然可以相互結合.我們通過聚類來構造等價集，依此實現數據k-匿名.為了便于描述，我們給出了相關定義.

定義1.等價集.給定表數據S，若U為S中的準標識屬性集合，則每個在U上取值都相近的記錄集合構成一個等價集，記為Di.

定義2.等價記錄.經過泛化后的等價集Di，集合中所有記錄具有相同的準標識屬性值，統稱為等價記錄，記為lDi.

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

我們以表1為例進行隱私處理：移除標識屬性和其他屬性，對于準標識屬性進行泛化，對敏感屬性不做處理.表2為2-匿名后的結果，其中包括3個等價集，每個等價集中至少包含2條記錄.

Table 2 2-anonymous Dataset表2 2-匿名數據集

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

2.2 匿名數據集的隱私保證

我們使用S表示原始表數據，S′表示匿名后的表數據.表數據中每一行記錄對應1個個體，用li表示.為了保護數據的隱私，我們采用k-匿名對表數據進行隱私保護，并給出數據隱私保證的定義.

定義4.k-匿名數據隱私保護的安全性.假設S是原始表數據，采用k-匿名數據隱私保護機制對S中的準標識屬性泛化處理，并成功生成匿名表數據S′.在發布S′情況下，條件成立:

(1)

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

2.3 匿名數據集的可用性度量

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

1) 數值型數據的可用性度量

(2)

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

2) 分類型數據的可用性度量

(3)

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

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

(4)

2.4 問題定義

從直觀上看，用戶需要的隱私泄露越少，那么獲得的數據效用就越少，反之亦然.因此在基于我們的可用性度量來設計數據隱私發布機制M時，存在著隱私-可用性的平衡問題.從數據可用性來看，受隱私約束的最小信息損失是多少，以及如何設計數據發布機制來實現最小信息損失，這是一個很自然的問題.因此，本文通過目標定義來表述這個問題.

(5)

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

定義5提供了數據發布隱私保護框架，它包括構造等價集和泛化2個過程.具體地說，它以下面的形式來獲得最優的表數據發布機制：給定原始的數據集S，通過在隱私性約束條件下達到最小信息損失來構造匿名數據集S′，然后發布匿名數據集S′.定義5將k-匿名機制的最優化問題轉化為數據集的最優聚類問題，以k-匿名為約束條件，尋找信息損失最小的匿名數據集，實現最優的聚類結果.

3 基于最優聚類的k-匿名機制

3.1 總體框架

Fig. 3 k-anonymity mechanism based on optimal clustering圖3 基于最優聚類的k-匿名機制

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

(6)

在上述二分簇機制中，距離最小化原則可以使得各個類之內的數據最為相似，而各個類之間的數據相似度差別盡可能大，從而保證最優的聚類劃分，實現最優k-匿名.此外，為了最大程度地減少數據的信息損失，我們將表數據中記錄之間準標識屬性的相近性與泛化后數據的信息損失結合起來，通過定義記錄間的距離來反映數據泛化的信息損失大小.記錄間的距離越小，它們之間的準標識屬性就越相近，泛化到同一等價集后所造成的信息損失也就越小.

3.2 記錄間的距離

定義6.記錄間的距離.給定表數據S，S中任意2條記錄la和lb在對應各個準標識屬性間距離的均值定義為記錄間的距離，記為dis(la,lb).

由定義6可知，記錄間的距離反映了它們之間準標識屬性的相似程度，由兩者在各個準標識屬性間的距離決定.準標識屬性可分為數值型和分類型，因此，針對不同類型的準標識屬性給出了不同的計算方法[16].

1) 數值型準標識屬性間距離

給定表數據S，對于S中任意2條記錄la和lb，假設ti為記錄la和lb中第i個數值型準標識屬性，則記錄la和lb中數值型準標識屬性ti的距離計算為

(7)

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

2) 分類型準標識屬性間距離

給定表數據S，對于S中任意2條記錄la和lb，假設tj為記錄la和lb中第j個分類型準標識屬性，則記錄la和lb中分類型準標識屬性tj的距離為

(8)

其中,|la(tj)|和|lb(tj)|分別是分類屬性tj的屬性值總數；Numla(wj)和Numlb(wj)分別為la和lb中wj的葉子節點個數.

結合數值型準標識屬性間距離和分類型準標識屬性間距離，我們可以計算任意表數據S中記錄間的距離：

給定表數據S，對于S中任意2條記錄la和lb，假設有n個準標識屬性，其中數值型屬性個數為m，分類型屬性個數為n-m.ti為記錄la和lb中第i個數值型準標識屬性，tj為記錄la和lb中第j個分類型準標識屬性，則記錄la和lb間的距離計算為

(9)

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

3.3 基于聚類優化的匿名算法

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

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

輸入：數據集S、匿名參數k；

輸出：匿名數據集S′.

① 對S中所有的準標識屬性進行最小泛化;

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

/*尋找2個新核心*/

③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中，先將數據集中所有記錄看成一個等價集，對等價中所有的數據屬性進行最小泛化；然后，在等價集中選取距離最遠的2條記錄ζ1和ζ2作為新等價子集的中心，計算各條記錄與等價集中心之間的距離，并以距離最小化原則將S劃分為S1和S2；最后，判斷|S1|與|S2|中記錄的個數是否大于k，且它們的信息損失總和小于S的信息損失.如果是，則迭代此劃分過程；否則迭代終止.該聚類劃分方法可以使得各個類之內的數據最為相似，而各個類之間的數據相似度差別盡可能大，保證最優的聚類劃分，實現最優k-匿名.

4 算法分析

4.1 有效性分析

定理1.不同記錄準標識屬性間的距離與這2個屬性泛化后的信息損失成正比.

證明.假設2條記錄為la和lb.記錄間的準標識屬性分為數值型準標識屬性和分類型準標識屬性.

1) 數值型準標識屬性

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

(10)

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

(11)

則有

(12)

2) 分類型準標識屬性

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

(13)

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

(14)

則有

(15)

由此可得無論是數值型準標識屬性還是分類型準標識屬性，它們之間的距離與泛化后的信息損失成正比.因此，定理1成立.

證畢.

定理2.根據準標識屬性間距離最小原則，構造滿足k匿名的最優等價類，能夠保證生成的等價類具有最小泛化信息損失值.

證明.由定理1可知，數據的信息損失和數據間距離成正比，通過最小距離進行聚類劃分來實現k-匿名最優等價集，進而可以保證信息損失達到最小.

證畢.

定理3.COAA算法能找到最優解.

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

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

證畢.

4.2 安全性分析

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

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

5 實驗與結果分析

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

5.1 信息損失比較

為了分析數據信息損失度隨屬性維度|B|、匿名參數k和不同數據集大小的變化規律，我們進行了以下實驗.

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

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

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

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

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

5.2 執行時間比較

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

Fig. 7 Running time with different k values圖7 不同k值下的執行時間

Fig. 8 Running time with different data sets圖8 不同數據集大小下的執行時間

6 總 結

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

作者貢獻聲明：張強負責方案的討論、性能分析以及論文撰寫；葉阿勇指導方案的擬定和整體設計，把握論文創新性，并審閱修訂論文；葉幗華參與論文方案可行性討論與分析；鄧慧娜參與論文圖表設計與規劃；陳愛民參與論文公式與論文文字校對.