1、k-匿名隱私保護相關技術探究【摘要】在數據發布領域，k-匿名技術是一種簡單有效的 隱私數據保護技術。因此國內外專家學者們對匿名化技術開 展了廣泛深入的研究工作以尋求防止或減少隱私泄露的有 效方法。本文根據已有的一些研究結論，闡述了匿名化技術 的一般概念、匿名化原則、匿名化方法和匿名化度量等方面, 并且介紹了兩種經典的匿名化算法。【關鍵詞】數據發布；匿名化技術；k-匿名1. 引言計算機處理能力、存儲技術及網絡技術的快速發展，信 息技術在組織中發揮的作用日益增加，一方面，使得信息共 享較之以前來得更為容易和方便，以數據庫為基礎的應用系 統成為經濟、金融、醫療等領域的信息基礎設施，大大地提 高了組織

2、的信息化程度；但是另一方面，這也使得數據庫系 統面對更多的安全威脅，隨之產生的隱私信息泄露現象屢見 不鮮，越來越多的因故意或疏忽造成的數據泄露的例子，使 人們對數據庫中的隱私保護問題日益重視。信息化過程中如 何在實現有效的信息共享的同時，有效地保護私有敏感信息 不被泄漏，已成為信息安全領域一個活躍的研究方向。cox 在1980年最先提出使用匿名的方法實現隱私保護，1986年 dalenius在針對人口普查記錄集的隱私保護應用了匿名技 術。自從匿名化概念提出以來，很多國內外的學者對匿名化 技術開展了廣泛的研究。例如l. sweeney提出了 一種用來保 護私有信息的k-匿名模型1。ji-won

3、byun, ashish kamra, elisa bertino, and ninghui li 在 2007 年提出 了 基于聚類 的高效k-匿名話算法2。在這篇文章中提出，k匿名問題 不需要有簇的數量的限制，但是每個簇中至少含有k條記錄, 所以，提出可以把k-匿名問題當作聚類問題，被稱為 k-member clustering problem0現在生活中，人們都很注 重隱私保護，尤其像是在醫院和銀行這種場合，大多數人可 能并不愿意讓別人知道自己的具體情況，所以怎樣既可以做 到不泄漏個人的隱私，又可以利用醫院和銀行中的個人信息 做科學研究，這種問題正是我們研究匿名發布信息的重要意 義所在。

4、下面文章將在第2部分介紹數據發布和匿名發布的相關 概念及定義，第3部分介紹常見的匿名算法，第4部分小結。2相關概念，相關定義2. 1匿名技術3匿名技術：是身份隱藏中最直接的技術。它作為隱私保 護的數據挖掘技術不對數據挖掘結果進行保護，也不將原始 數據進行隱藏偽裝，而是公布帶隱私的所有數據，但是他人 拿到隱私數據卻不能推導出該數據擁有者的身份。2.2匿名發布技術相關定義4定義1:屬性令：b(a1,，an)是一個有限數量元組的一個表，b的 有限元屬性元組是a1,，an。假設表 b(a1,，an), ai,，aj al,，an, 有一個元組twb,用tai,，aj來表示t中ai, , aj 的值vi

5、,，vj的有序序列。用bai,，aj來表示投影, 維持b中屬性ai, -aj的元組復制。定義2：類標識符假設一個實體集u, 個特定的實體表t(a1,，an), fc：ut以及fg：t-u,其中uu' .t的一個類標識符記為 qt,是一組屬性ai,，aj al,，an其中:pi$u所以 fg(fc (pi) qt)=pi.成立。定義3： k-匿名rt(a1, , an)是一個表qirt是與rt有關聯的類標 識符，并且僅當在rteqirt中出現的每一個有序的值至少要 在rtcqirt中出現k次的話，就說rt滿足k-匿名。推論：假設 rt(a1,，an)為一個表,qirt=(a1,an) 是

6、與rt相關聯的類標識符，ai, , ajal,，an, rt滿 足 甘匿名，那么在rtax中出現的每一個值的有序序列至 少要在rteqirt中出現k次,x=i,jo2.3信息發布度量相關定義2. 3.1 a匿名問題轉換成聚類問題2定義 1: k-member clustering problemk-member clustering problem需要從給出的n條記錄 中尋找一組簇，每個簇中至少含有k(k<n)條數據記錄，并且 簇內的距離之和最小。s代表n條記錄，k代表特定的匿名 參數，所以k-聚類問題可以表示為一組簇£= el, , em)定義為：1)2)3)4)e|表示簇e

7、的大小，表示在第i個數據項， (x, y) 表示數據x和y的距離。2. 3.2距離函數每個聚類問題的核心是用距離函數處理各個數據點的 不同和使成本函數在聚類問題中最小。數據通常有數值型數據和類別型數據，對于數值型數 值，描述兩個數據之間的差異就是兩個數據的價值差異。這 種處理方法同樣適用于處理k-匿名問題中的數值型數據。定義2：數值型數據距離函數用d表示有限的數值域，數據vl, v2 (vl, v2wd)之間的距離可以定義為:其中vl, v2為兩數值型數據，|d|為有限數值域d的區 間大小。類別型數值可以用類別樹表示，假設類別樹的每個葉子 節點代表在域中的所有不同的值。定義3：類別型數據距離函

8、數用d表示類別型數據的域，td表示根據d所定義的類別 樹，數據vl, v2 (vl, v2£d)之間的距離可以定義為：it(t)表示樹t的高度，a(x, y)表示樹中結點x和y的 最小共同祖先結點。定義4：兩個數據的距離令qt=n1,，nm, cl,，cn為表t的準標識符屬 性，ni為數值屬性，cj (j=l-n)為類別屬性，所以兩個數據門，r2, (rl, r2gt)之間的距離可以定義為：ria表示記錄ri中屬性a的值，和是在定義 2和定義3中定義過的距離函數。2. 3. 3成本函數聚類問題的最終目的是k-匿名問題的數據，通過定義成 本函數表示因為泛化過程導致的信息失真(信息丟失)

9、，所 以成本函數越小越好。簇中的記錄被泛化是根據每個簇中相 同的原準標識符。假設數值型數據被泛化成一個區間最小, 最大h5,類別型數據簇中的數據都是有明顯區別的集合 6o根據以上的想法，定義了代表信息丟失的準標識(il)。定義5：信息丟失設e=rl,，rk是一個簇(等價類)，準標識屬性包含 數值型數據和類別型數據qt=n1,，nm, cl,，cn, tci是屬性ci的分類樹。minni、maxni分別為類e中屬性 ni的最小、最大值。uci是類e中屬性ci的值集合。所以 信息丟失可以定義為：e|表示簇e中的數據量，|n|表示數值型數據域的大小, h(t)表示樹t的高度，a(ucj)表示樹中結點

10、ucj中所以值 的最小共同祖先結點。根據上面的定義，可以把匿名表的總信息丟失定義如 下。定義6：總信息丟失設e為匿名表at中所有等價類集合，所以總信息丟失量可以定義為：total-il(at)=信息損失度量公式中的數值屬性度量方法只反映了每 一類中屬性值的覆蓋廣度，并沒有反映出原始準標識符屬性 和泛化后的屬性值之間的差異關系。3. 常見的匿名技術和算法3.1常見的匿名技術基于屬性層次的泛化匿名技術，如全域泛化4 7,局 部泛化8,單層泛化4 7 9和多層泛化8 10；基于 聚類的匿名技術2 11；基于劃分的方法5；基于無集搜 索的方法6。3.2常見的匿名算法k-匿名自提出以來，得到了學術界的普

11、遍關注，國內外 很多學者都從不同層面研究和發展了該技術。其中以 k. lefevre 和 raghu ramakrishnan 等人提出的 mondrian5 和incognito7為比較經典的k-匿名算法。3. 2. 1 mondrian 算法文獻5提出了多維k-匿名的概念，根據kd-tree的分 割方法提出了 mondrian算法，該方法允許同一時刻在多維 類身份屬性上進行泛化處理。多維k-匿名從全局泛化 (global recoding)和局部泛化(local recoding)的角度歸 納出兩種多維劃分模型嚴格多維劃分和寬松多維劃分。 這兩種模型用d維空間來表示準標識符屬性xi, x2

12、,，xd, 將每條元組根據各屬性值映射為多維空間的一個點，因此一 張表就是一個點集。與單維劃分對各屬性的域分別作劃分不同，多維劃分模 型將所有屬性域作為一個整體進行分割。嚴格多維劃分在各 屬性域的笛卡爾積dxlx-xdxd上定義一個劃分，也就是 把多維空間分割為多個互不重疊的區域，并將數據點映射為 它們所在的那個子空間。寬松多維劃分則是在dx1 x -xdxd上定義互不相同的多維區域，可以有重疊，并將每個數據點 映射為它所在區域中的一個。3. 2. 2 incognito 算法文獻7提出了 incognito算法，incognito是一種廣泛應用的k-匿名算法,能夠產生給定表的所有可能的k-匿

13、名全域泛化（一種全局重編碼技術）。算法首先檢查qi屬性中 的單屬性子集是否滿足k-匿名，然后迭代地檢查qi屬性的 多維屬性子集，每次迭代，用于檢查的屬性子集寬度增加1。 迭代過程包含兩個主要的部分：尋找k-匿名泛化點、候選點 和邊的生成。每輪迭代從一個由若干候選多屬性泛化模式構成的圖 開始。第i次迭代的泛化模式由若干寬度為it的qi屬性 集生成，記作ci。圖中表示直接泛化關系的連接邊的集合記 作ei。算法對圖中的候選點進行寬度優先搜索，通過判斷原 始表在候選點上是否滿足k-匿名，篩選出寬度為i的多屬性 泛化模式，記作si。算法從si生成寬度為i+1的候選點集ci+1和直接泛化 連接邊ei+1

14、o incognito的第i輪迭代使用一種經過改進的 自底向上的寬度優先搜索搜索來判斷原始表t在候選泛化模 式集ci上的k-匿名狀態。搜索開始于候選泛化圖中沒有邊 指向的“根”節點，算法通過自底向上地集成來得到各點上 的元組計數。這種寬度優先搜索同時也是基于“泛化性質” 的，如果原始表在某點上是k-匿名的，則該點的所有有連接 的上層點也能使表滿足k-匿名。因此，當搜索算法發現匿名 點，就將其直接泛化點做標記，并且后面的計算中不再予以 考慮。4. 結束語隨著計算機技術的發展，人們現在可以很容易的就取得 自己想要的信息。但是，伴隨而來的就是隱私數據泄露的問 題，這可能會侵害數據所有者的利益。為了能

15、夠使用已發布 的數據信息并且又可以不侵害信息所有者的利益，這是我們 所關心的，這也正是我們做此項研究的目的和意義。參考文獻1 l sweeney,l,k-aonyfnjty：a model for privacyj intemational journal on uncertainty fuzzinessandknowledgebasedsystems,2002,10 (5):557-570.2 j. w. byun,a. kamra,e. bertinoandn. li,effieient k-anonymization using clustering techniques,in：proc

16、eedings of database systems for advancedapplications(dasfaa2007),lncs4443. berlin：springer-v erlag,2007:188-200.3 馬延淮，唐美麗基于隱私保護的數據挖掘j計算 機工程,34(9):78-80.4 l. sweeney. achieving k-anonymity privacy protection using generalization and suppression. international journal on uncertainty,fuzziness and know

17、ledge-based systems,10 (5),2002：571-588.5 k. lefevre,d. dewitt and r. ramakrishnan,mondrian multidimensional k-anonymity,in：proceedingsof the international conference on data engineering (icde),atlanta,ga,usa,2006.6 r. j. bayardo and r agrawa 1. data privacy through optimal k-anonymization.in intern

18、ational conference on data engineering,2005.7 k. lefevre,d. dewitt and r. ramakrishnan,incognito：efficient full-domain k-anonymity,in：proceedings of the acm sigmod international conference on management of data(sigmod),baltimore,md,usa,2005.8 b. c. m. fung, k. wang and p. s. yu, top-down specialization for information and privacy preservation,in：proceedings of the internationalconferenee on data engineering（icde）,tokyo,japan,2005.9 p. sanarati,protecting respondents，privacy in microdata release,ieee transactions on knowledge and data engineering 13（2001）,1010-1027.10 v.siyengor,tronsf