多敏感屬性K-匿名模型的實現?

王靜 閆仁武 劉亞梅

（江蘇科技大學計算機科學與工程學院鎮江212003）

多敏感屬性K-匿名模型的實現?

王靜 閆仁武 劉亞梅

（江蘇科技大學計算機科學與工程學院鎮江212003）

L-MDAV算法結合L-多樣性模型和MDAV微聚集算法來實現K-匿名模型，但是L-MDAV算法只考慮了單一敏感屬性下的約束，而在實際發布的數據中不可能只有一個敏感屬性，論文在該算法的基礎上提出了基于多敏感屬性的MDAV算法，文中僅以兩種敏感屬性為例，因此算法命名為（L1，L2）-MDAV算法。論文在根據用戶不同敏感屬性的不同保護需求下為用戶個性化定義敏感屬性的敏感度。實驗結果表明，論文提出的算法相比于L-MDAV算法能夠更好地保護隱私數據安全。

多敏感屬性；K-匿名；L-多樣性；微聚集算法

Class NumberTP3-05

1 引言

在享受信息技術快速發展所帶來的便捷的同時，我們暴露了大量與個體相關的數據。這些數據被各個部門或者研究機構收集并且發布，這一趨勢所帶來的危害是更多的個人隱私數據得不到保護，造成大量的隱私泄露。

為了保護數據發布過程中隱私數據的安全，研究者們提出了數據匿名發布技術，先后出現了K-匿名模型［1］、L-多樣性模型［2］、T-接近模型［3］等匿名隱私保護模型。

上述幾種模型通常采用泛化［4］技術來實現，然而通過泛化技術得到的數據質量無法得到保證，往往失真度較高，且算法的時間復雜度較大。因此，微聚集算法應用于隱私保護模型得到大量研究［5］。

考慮到實際應用中發布的數據不可能只有一個敏感屬性，因此本文在實現單敏感屬性L-多樣性的L-MDAV算法［6］的基礎上提出了基于多敏感屬性［7］的L-多樣性的MDAV算法。本文的算法適合多敏感屬性，但是為了更好地描述，文中以兩個敏感屬性為例，因此算法命名為（L1，L2）-MDAV算法。

2 相關概念

定義1（準標識符）給定一個表T，當通過一組屬性集合與外部表鏈接可以獲得識別個體的元組信息，則稱該屬性集合為表T的準標識符。

定義2（K-匿名）給定表T中的一個元組，如果表中有至少K-1個元組與該元組存在相同的準標識符，則稱該元組滿足K-匿名。

定義3（K-劃分）給定一個表T，將該表基于準標識符劃分成g個類，其中每個類的元組個數要大于等于K，稱滿足這類劃分的表為K-劃分。

定義4（聚集）將給定的表基于該表的準標識符進行K-劃分為g個類，用每個類的質心來代替給定數據表每個類的所有元素稱為聚集。

定義5（L-多樣性）對于給定的表T，若該表的等價類中至少含有L個“表現良好“［8］的敏感屬性，則稱該等價類滿足L-多樣性模型。

表1 原始數據表

表1所示為原始的發布數據，name是顯式標識符，｛age，sex，zipcode｝是準標識符，disease是敏感屬性。表2是表1的2-多樣性表。

表2 多樣化后的數據表

3 度量空間

對于給定的表T，其屬性又分為連續型和分類型屬性，本文重點以連續型屬性為例來實現K-匿名模型。

3.1 數據標準化

考慮到不同的連續型屬性會有不同的單位以及不同的取值范圍，比如年齡通常取值是兩位數，而郵編如45000，這樣兩個取值范圍差距較大的不同屬性值往往會對結果造成較大的差異，導致不能準確地衡量兩個元組之間的實際距離。本文首先對數據進行預處理，去除異常值，然后用式（1）對預處理后的數據進行標準化來提高實驗結果的可靠性。本文選擇用極差法［9］將全部屬性值映射到［0，1］區間，公式如下：

其中X為新數據，x為原數據，Xmin是屬性X取值的最小值，Xmax是屬性X取值的最大值。

3.2 距離度量

假設元組i和元組j經過數據標準化處理后表示為Xi=(xi1，xi2，…，xip)，Xj=(xj1，xj2，…，xjp)元組為p維向量，則元組Xi和元組Xj之間的距離用歐幾里得距離公式表示為

3.3 微聚集算法的評價標準

3.3.1 數據的信息損失

本文采用EM4ADOM模型［10］來計算數據信息損失量。本文主要描述連續型數據，分類型數據的距離和信息損失度量見文獻［11］。

類的同質性測度SSE如式（3）所示：

其中g為類的個數，ni為第i類的元組個數，

數據表同質性測度SST如式（4）所示：

給定一個數據表，該表的同質性測度SST是不會變的，但是對于不同的算法或者不同的參數值所劃分的表SSE是不同的。因此信息損失量IL用式（5）計算

3.3.2 數據泄密風險

本文用基于距離的記錄鏈接（DLD）模型［12］來衡量匿名表中數據泄密風險。

定義6（鏈接成功）從匿名表中任意選擇一個元組r，計算出原始表中所有的元組到r的距離，把最近的元組記為r（1），第二近的元組記為r（2），如果r是由若r（1）（或者r（2））匿名化得到的，則稱r鏈接成功。

設匿名表共有M條記錄，其中有N條鏈接成功的記錄，則DLD模型的泄密風險值用式（6）計算：

4 基于多敏感屬性的（L1，L2）-MDAV算法

4.1 多敏感屬性匿名模型的發布方法

基于多敏感屬性的（L1，L2）-MDAV算法，本文說明僅以兩個敏感屬性為例，多個敏感屬性方法以此類推。首先為兩個敏感屬性定義敏感度，不同的用戶所要保護的敏感屬性的級別是不同的，因此，用戶可以根據自身需求定義不同敏感屬性的敏感度，再根據不同的L值對敏感數據實行不同的級別約束，以滿足用戶的個性化需求。表3以兩個敏感屬性disease和occupation為例，將disease定義更高的敏感度。

表3 敏感屬性的敏感度以及l值

表4 原始數據表

表4中｛age，zipcode｝為準標識符，disease和oc-cupation為敏感屬性。表5是表4的（3，2）-多樣性表。

表5 多樣化后的數據表

4.2 （L1，L2）-MDAV算法

輸入：待發布數據表T，兩個不同敏感屬性的多樣性參數L1，L2

輸出：滿足多敏感屬性（L1，L2）-多樣性約束的匿名表T′

步驟：

1）T′=T；

2）計算數據表T中所有記錄的中心xˉ；

3）找出數據表中離中心xˉ最遠的記錄r；

4）在表T′以r為中心，找出離r最近的K-1條記錄與r組成一個類，并且要求類中第一敏感屬性和第二敏感屬性分別滿足L1-多樣性和L2-多樣性；

5）從表T中刪除這些記錄；

6）若表T中剩下記錄第一敏感值的多樣性大于2L1且第二敏感屬性值的多樣性大于2L2，則執行步驟2）；

7）若表T中剩下的記錄第一敏感屬性值多樣性在［L1，2L1-1］或者第二敏感屬性值多樣性在［L2，2L2-1］中，則剩下的記錄歸為一類；

8）否則，將表T中剩下的記錄分別計算到所有類中心的距離，選擇距離最小的類進行插入；

9）輸出滿足多敏感屬性（L1，L2）-多樣性約束的匿名表T′。

5 實驗結果與分析

本文實驗平臺為Core2.2GHz/4GB，Windows7，涉及的代碼使用Matlab實現。采用census微數據［13］集作為測試數據，實現了MDAV，L-MDAV以及本文提出的（L1，L2）-MDAV三種算法在該數據集下的信息損失量與數據泄密風險的比較。

5.1 信息損失量比較

5.1.1 L值不變，隨K值的變化情況

圖1各算法信息損失量隨k變化情況

信息損失量采用式（5）計算，由圖1可以看出K值變大，三種算法的信息損失均會變大，這是因為類越大，類的同質性會越大，因此信息損失量會變大。固定K值，三種算法的信息損失量由小到大依次是MDAV、L-MDAV、（L1，L2）-MDAV，這是因為三種算法的約束性是越來越強，類的平均大小會有所增加，因此數據的信息損失也會增加。

5.1.2 K值不變，隨L值的變化情況

圖2固定K值與約束L2的值，通過一個敏感屬性的多樣性參數的變化來比較L-MDAV和（L1，L2）-MDAV兩種算法的信息損失。可以看出，L值變大，信息損失量也會變大，并且（L1，L2）-MDAV算法的信息損失量較L-MDAV大，因為（L1，L2）-MDAV的約束更強。

圖2各算法信息損失量隨L變化情況

5.2 泄密風險評估

5.2.1 L值不變，隨K值的變化情況

泄密風險采用式（6）計算，圖3表明，隨著K值的增大，三種算法的泄密風險均變小，且本文提出的（L1，L2）-MDAV算法泄密風險最小，因為該算法是對多敏感屬性進行約束，約束性較前兩個算法都強，從而使得鏈接成功的元組數會變少，因此泄密風險減小。可以看出，（L1，L2）-MDAV算法不僅能滿足用戶對不同敏感屬性的個性化保護需求，還能減小發布數據的泄密風險。

圖3各算法泄密風險隨K變化情況

5.2.2 K值不變，隨L值變化情況

圖4固定K值和約束L2的值，該圖表明兩個算法隨著L值的增大泄密風險變小，并且（L1，L2）-MDAV算法的泄密風險較L-MDAV算法更小，這是因為增加了第二敏感屬性的約束，使得算法約束性更強，從而減小了數據泄密的風險。

圖4各算法泄密風險隨l變化情況

6 結語

（L1，L2）-MDAV算法在L-MDAV算法的基礎上增加了多敏感約束條件。從安全性上看，（L1，L2）-MDAV算法的約束條件更強，因此能達到更好的數據保密效果；從信息損失量上看，（L1，L2）-MDAV算法由于約束性較強，使得數據失真度較高，但是從算法的實驗結果來看，該算法與其他兩個算法的信息損失量差別不大；從實際出發，在數據發布的過程中，數據不可能只有一個敏感屬性，本文提出多敏感屬性個性化微聚集算法具有一定的實用價值。總之，本文提出的算法能更好地實現用戶的個性化需求，并能保證數據更小的泄密風險，獲得更安全的匿名表。

本文選擇的微聚集算法是定長微聚集算法MDAV算法，而變長微聚集算法如TFRP［14］、MST［15］等具有聚類質量高的優點，因此論文的下一步工作是研究基于滿足多敏感屬性多樣性的變長微聚集算法，以期得到更高質量的匿名表。

［1］Sweeney L.k-ANONYMITY：A MODEL FOR PROTECT?ING PRIVACY 1［J］.International J-ournal of Uncertain?ty，Fuzziness and Knowledge-Based Systems，2008，10（5）：557-570.

［2］Machanavajjhala A，Gehrke J，Kifer D，et al.L-diversi?ty：privacy beyond k-anonymity［J］.A-cm Transactions on Knowledge Discovery from Data，2006，1（1）：24-24.

［3］張健沛，謝靜，楊靜，等.基于敏感屬性值語義桶分組的t-closeness隱私模型［J］.計算機研究與發展，2014，51（1）：126-137. ZHANG Jianpei，XIE Jing，YANG Jing.A t-c-loseness Privacy Model Based on Sensitive A-ttribute Values Se?mantics Bucketization［J］.Journal of Computer Research and Development，2014，51（1）：126-137.

［4］劉樂偉.面向多敏感屬性的隱私保護方法研究［D］.北京：北京工業大學，2013. LIU Lewei.Research of privacy preserving methods for multiple seneitive attributes［D］.Beijing：Beijing Universi?ty of Technology，2013.

［5］程亮，蔣凡.基于微聚集的a-多樣性k-匿名大數據隱私保護［J］.信息網絡安全，2015（3）：19-22. CHENG Liang，JIANG Fan.a-diversity and k-anonymity Big Data Pri-vacy Preservation Based on Micro-aggrega?tion［J］.Netinfo Security，2015（3）：19-22.

［6］王茜，張剛景.實現單敏感屬性多樣性的微聚集算法［J］.計算機工程與應用，2015（11）：72-75. WANG Qian，ZHANG Gangjing.Microaggregation algo?rithm for single sensitive attribute diversely［J］.Computer Engineering and Applications，2015（11）：72-75.

［7］唐印滸，鐘誠.基于變長聚類的多敏感屬性概率k-匿名算法［J］.計算機工程與設計，2014（8）：2660-2665. TANG Yinhu，ZHONG Cheng.Probabilistic k-anonymity algo-rithm with multi-sensitive attributes based on variab len-gth clustering［J］.Computer Engineering and Design，2014（8）：2660-2665.

［8］Domingo-Ferrer J，Mateo-Sanz J M，Torra V.Comparing SDC Methods for Microdata on the Basis of Information LossandDisclosure［C］//ProceedingsofETK-NTTS 2001，Luxemburg：Eurostat，2001.

［9］Chang C C，Li Y C，Huang W H.TFRP：An efficient mi?croaggregation algorithm for statistical disclosure control［J］.Journal of Systems&Software，2007，80（11）：1866-1878.

［10］陳建明，韓建民.面向微聚集技術的k-匿名數據質量評估模型［J］.計算機應用研究，2010，27（6）：2344-2347. CHEN Jianming，HAN Jianmin.valuation model for q-uality of k-anonymity data oriented to microa-ggre?gat-ion［J］.Application Research of Computers，2010，27（6）：2344-2347.

［11］Domingo-Ferrer J，Mateo-Sanz J M.Practical data-ori?ented microaggregation for statistical disclosure control［J］.IEEE Transactions on Knowledge&Data Engineer?ing，2002，14（1）：189-201.

［12］王茜，甘榮慶.一種高效的微聚集k-匿名算法［J］.世界科技研究與發展，2013，35（1）：38-40. WANG Qian，GANRongqing.An Efficient Micro-aggre?gation Algorithm f-or K-Anonymity［J］.World Sci-tech R&D，2013，35（1）：38-40.

［13］Domingo-Ferrer J，Sebé F，Solanas A.A polynomial t-ime approximation to optimal multivariate microag?gr-egation［J］.Computers&Mat-hematics with Applica?ti-ons，2008，55（4）：714-732.

［14］Laszlo M，Mukherjee S.Minimum Spanning Tree Parti?tioning Algorithm for Microaggregat-ion［J］.IEEE Trans?actions on Knowledge&Data Engineering，2010，17（7）：902-911.

［15］楊靜，王超，張健沛.基于敏感屬性熵的微聚集算法［J］.電子學報，2014，42（7）：1327-1337. YANG Jing，WANG Chao，ZHANG Jianpei.Micro-Ag?gregation Algorithm Based on Sensitive Attribute Entropy［J］.Acta Electronica Sinica，2014，42（7）：1327-1337.

Implementation of K-anonymous Model with Multi-sensitive Attributes

WANG JingYAN RenwuLIU Yamei
（School of Computer Science and Engineering，Jiangsu University of Science and Technology，Zhenjiang212003）

L-MDAV algorithm combined with L-diversity model and MDAV algorithm to implement the K-anonymous mod?el，but L-MDAV algorithm only considers the single sensitive attribute，in the actual，released data may not have only one sensitive attribute，so，on the basis of the algorithm the article propose a MDAV algorithm with multi-sensitive attributes.In this paper，with only two sensitive attributes as an example，so the algorithm named（L1，L2）-MDAV algorithm.According to user's protection for dif?ferent sensitive attributes have different requirements to define the different values of L.As the experimental results show，the pro?posed algorithm can protect the privacy of privacy data perfectly compared with L-MDAV algorithm.

multi-sensitive，attributes，K-anonymous，L-diversity，microaggregation algorithm

TP3-05

10.3969/j.issn.1672-9722.2017.07.029

2017年1月7日，

2017年2月23日

王靜，女，碩士研究生，研究方向：信息安全，數據挖掘。閆仁武，男，副教授，碩士生導師。劉亞梅，女，碩士研究生，研究方向：數據挖掘。