多敏感屬性K-匿名模型的實(shí)現(xiàn)?

王靜 閆仁武 劉亞梅

（江蘇科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院鎮(zhèn)江212003）

多敏感屬性K-匿名模型的實(shí)現(xiàn)?

王靜 閆仁武 劉亞梅

（江蘇科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院鎮(zhèn)江212003）

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

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

Class NumberTP3-05

1 引言

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

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

上述幾種模型通常采用泛化［4］技術(shù)來實(shí)現(xiàn)，然而通過泛化技術(shù)得到的數(shù)據(jù)質(zhì)量無法得到保證，往往失真度較高，且算法的時(shí)間復(fù)雜度較大。因此，微聚集算法應(yīng)用于隱私保護(hù)模型得到大量研究［5］。

考慮到實(shí)際應(yīng)用中發(fā)布的數(shù)據(jù)不可能只有一個(gè)敏感屬性，因此本文在實(shí)現(xiàn)單敏感屬性L-多樣性的L-MDAV算法［6］的基礎(chǔ)上提出了基于多敏感屬性［7］的L-多樣性的MDAV算法。本文的算法適合多敏感屬性，但是為了更好地描述，文中以兩個(gè)敏感屬性為例，因此算法命名為（L1，L2）-MDAV算法。

2 相關(guān)概念

定義1（準(zhǔn)標(biāo)識(shí)符）給定一個(gè)表T，當(dāng)通過一組屬性集合與外部表鏈接可以獲得識(shí)別個(gè)體的元組信息，則稱該屬性集合為表T的準(zhǔn)標(biāo)識(shí)符。

定義2（K-匿名）給定表T中的一個(gè)元組，如果表中有至少K-1個(gè)元組與該元組存在相同的準(zhǔn)標(biāo)識(shí)符，則稱該元組滿足K-匿名。

定義3（K-劃分）給定一個(gè)表T，將該表基于準(zhǔn)標(biāo)識(shí)符劃分成g個(gè)類，其中每個(gè)類的元組個(gè)數(shù)要大于等于K，稱滿足這類劃分的表為K-劃分。

定義4（聚集）將給定的表基于該表的準(zhǔn)標(biāo)識(shí)符進(jìn)行K-劃分為g個(gè)類，用每個(gè)類的質(zhì)心來代替給定數(shù)據(jù)表每個(gè)類的所有元素稱為聚集。

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

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

表1所示為原始的發(fā)布數(shù)據(jù)，name是顯式標(biāo)識(shí)符，｛age，sex，zipcode｝是準(zhǔn)標(biāo)識(shí)符，disease是敏感屬性。表2是表1的2-多樣性表。

表2 多樣化后的數(shù)據(jù)表

3 度量空間

對(duì)于給定的表T，其屬性又分為連續(xù)型和分類型屬性，本文重點(diǎn)以連續(xù)型屬性為例來實(shí)現(xiàn)K-匿名模型。

3.1 數(shù)據(jù)標(biāo)準(zhǔn)化

考慮到不同的連續(xù)型屬性會(huì)有不同的單位以及不同的取值范圍，比如年齡通常取值是兩位數(shù)，而郵編如45000，這樣兩個(gè)取值范圍差距較大的不同屬性值往往會(huì)對(duì)結(jié)果造成較大的差異，導(dǎo)致不能準(zhǔn)確地衡量?jī)蓚€(gè)元組之間的實(shí)際距離。本文首先對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，去除異常值，然后用式（1）對(duì)預(yù)處理后的數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化來提高實(shí)驗(yàn)結(jié)果的可靠性。本文選擇用極差法［9］將全部屬性值映射到［0，1］區(qū)間，公式如下：

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

3.2 距離度量

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

3.3 微聚集算法的評(píng)價(jià)標(biāo)準(zhǔn)

3.3.1 數(shù)據(jù)的信息損失

本文采用EM4ADOM模型［10］來計(jì)算數(shù)據(jù)信息損失量。本文主要描述連續(xù)型數(shù)據(jù)，分類型數(shù)據(jù)的距離和信息損失度量見文獻(xiàn)［11］。

類的同質(zhì)性測(cè)度SSE如式（3）所示：

其中g(shù)為類的個(gè)數(shù)，ni為第i類的元組個(gè)數(shù)，

數(shù)據(jù)表同質(zhì)性測(cè)度SST如式（4）所示：

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

3.3.2 數(shù)據(jù)泄密風(fēng)險(xiǎn)

本文用基于距離的記錄鏈接（DLD）模型［12］來衡量匿名表中數(shù)據(jù)泄密風(fēng)險(xiǎn)。

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

設(shè)匿名表共有M條記錄，其中有N條鏈接成功的記錄，則DLD模型的泄密風(fēng)險(xiǎn)值用式（6）計(jì)算：

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

4.1 多敏感屬性匿名模型的發(fā)布方法

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

表3 敏感屬性的敏感度以及l(fā)值

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

表4中｛age，zipcode｝為準(zhǔn)標(biāo)識(shí)符，disease和oc-cupation為敏感屬性。表5是表4的（3，2）-多樣性表。

表5 多樣化后的數(shù)據(jù)表

4.2 （L1，L2）-MDAV算法

輸入：待發(fā)布數(shù)據(jù)表T，兩個(gè)不同敏感屬性的多樣性參數(shù)L1，L2

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

步驟：

1）T′=T；

2）計(jì)算數(shù)據(jù)表T中所有記錄的中心xˉ；

3）找出數(shù)據(jù)表中離中心xˉ最遠(yuǎn)的記錄r；

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

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

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

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

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

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

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

本文實(shí)驗(yàn)平臺(tái)為Core2.2GHz/4GB，Windows7，涉及的代碼使用Matlab實(shí)現(xiàn)。采用census微數(shù)據(jù)［13］集作為測(cè)試數(shù)據(jù)，實(shí)現(xiàn)了MDAV，L-MDAV以及本文提出的（L1，L2）-MDAV三種算法在該數(shù)據(jù)集下的信息損失量與數(shù)據(jù)泄密風(fēng)險(xiǎn)的比較。

5.1 信息損失量比較

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

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

信息損失量采用式（5）計(jì)算，由圖1可以看出K值變大，三種算法的信息損失均會(huì)變大，這是因?yàn)轭愒酱螅惖耐|(zhì)性會(huì)越大，因此信息損失量會(huì)變大。固定K值，三種算法的信息損失量由小到大依次是MDAV、L-MDAV、（L1，L2）-MDAV，這是因?yàn)槿N算法的約束性是越來越強(qiáng)，類的平均大小會(huì)有所增加，因此數(shù)據(jù)的信息損失也會(huì)增加。

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

圖2固定K值與約束L2的值，通過一個(gè)敏感屬性的多樣性參數(shù)的變化來比較L-MDAV和（L1，L2）-MDAV兩種算法的信息損失。可以看出，L值變大，信息損失量也會(huì)變大，并且（L1，L2）-MDAV算法的信息損失量較L-MDAV大，因?yàn)椋↙1，L2）-MDAV的約束更強(qiáng)。

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

5.2 泄密風(fēng)險(xiǎn)評(píng)估

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

泄密風(fēng)險(xiǎn)采用式（6）計(jì)算，圖3表明，隨著K值的增大，三種算法的泄密風(fēng)險(xiǎn)均變小，且本文提出的（L1，L2）-MDAV算法泄密風(fēng)險(xiǎn)最小，因?yàn)樵撍惴ㄊ菍?duì)多敏感屬性進(jìn)行約束，約束性較前兩個(gè)算法都強(qiáng)，從而使得鏈接成功的元組數(shù)會(huì)變少，因此泄密風(fēng)險(xiǎn)減小。可以看出，（L1，L2）-MDAV算法不僅能滿足用戶對(duì)不同敏感屬性的個(gè)性化保護(hù)需求，還能減小發(fā)布數(shù)據(jù)的泄密風(fēng)險(xiǎn)。

圖3各算法泄密風(fēng)險(xiǎn)隨K變化情況

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

圖4固定K值和約束L2的值，該圖表明兩個(gè)算法隨著L值的增大泄密風(fēng)險(xiǎn)變小，并且（L1，L2）-MDAV算法的泄密風(fēng)險(xiǎn)較L-MDAV算法更小，這是因?yàn)樵黾恿说诙舾袑傩缘募s束，使得算法約束性更強(qiáng)，從而減小了數(shù)據(jù)泄密的風(fēng)險(xiǎn)。

圖4各算法泄密風(fēng)險(xiǎn)隨l變化情況

6 結(jié)語

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

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

［1］Sweeney L.k-ANONYMITY：A MODEL FOR PROTECT?ING PRIVACY 1［J］.International J-ournal of Uncertain?ty，F(xiàn)uzziness 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］.計(jì)算機(jī)研究與發(fā)展，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］劉樂偉.面向多敏感屬性的隱私保護(hù)方法研究［D］.北京：北京工業(yè)大學(xué)，2013. LIU Lewei.Research of privacy preserving methods for multiple seneitive attributes［D］.Beijing：Beijing Universi?ty of Technology，2013.

［5］程亮，蔣凡.基于微聚集的a-多樣性k-匿名大數(shù)據(jù)隱私保護(hù)［J］.信息網(wǎng)絡(luò)安全，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］王茜，張剛景.實(shí)現(xiàn)單敏感屬性多樣性的微聚集算法［J］.計(jì)算機(jī)工程與應(yīng)用，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］唐印滸，鐘誠.基于變長(zhǎng)聚類的多敏感屬性概率k-匿名算法［J］.計(jì)算機(jī)工程與設(shè)計(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］陳建明，韓建民.面向微聚集技術(shù)的k-匿名數(shù)據(jù)質(zhì)量評(píng)估模型［J］.計(jì)算機(jī)應(yīng)用研究，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］.世界科技研究與發(fā)展，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］.電子學(xué)報(bào)，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日

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