劉 萍，邱桃榮，段文影

（南昌大學(xué) 信息工程學(xué)院，江西 南昌330031）

0 引 言

怎樣發(fā)布既真實(shí)有效又能保護(hù)個(gè)人的隱私信息不被泄露的數(shù)據(jù)是亟需解決的重要問題。為了達(dá)到保護(hù)個(gè)人隱私的目的，最初的方法是僅刪除個(gè)人信息中唯一能識(shí)別具體元組的身份屬性，這個(gè)過程被稱為匿名化。文獻(xiàn) ［1］提出了K－anonymization規(guī)則來解決由于鏈接攻擊造成的隱私泄露問題。然而K－anonymization存在一定的不足之處，對(duì)敏感數(shù)據(jù)，它沒有做任何約束處理。為解決這個(gè)問題，在文獻(xiàn) ［2］中提出了一種新的隱私規(guī)則l－diversity，l－diversity規(guī)則提高了匿名組內(nèi)敏感屬性多樣性，降低了隱私泄露的風(fēng)險(xiǎn)，但是它并沒解決K－anonymization規(guī)則會(huì)大量丟失原始數(shù)據(jù)大量信息的缺點(diǎn)。另一方面，l－diversity模型對(duì)相似性攻擊沒有比較好的解決辦法。因此，依靠泛化技術(shù)文獻(xiàn)［3］提出了一種可以抵御相似性攻擊的匿名規(guī)則t－closeness，同樣基于泛化技術(shù)的隱私規(guī)則還包括 （c，k）－safe－ty［4］，privacy skyline［5］等。采用泛化技術(shù)的匿名規(guī)則在很大程度上降低了數(shù)據(jù)的精度和利用率。文獻(xiàn) ［6］采用一種交換方法，實(shí)現(xiàn)高精度的數(shù)據(jù)發(fā)布規(guī)則anatomy，該規(guī)則采用一種被稱為有損連接的方法。 （k，e）－anonymity［7］也是典型的采用交換來實(shí)現(xiàn)匿名化的模型。

由于傳統(tǒng)的匿名算法都是把數(shù)據(jù)表所有的準(zhǔn)標(biāo)識(shí)符屬性的重要度看成一致，采用相同的匿名強(qiáng)度實(shí)現(xiàn)k－劃分，所設(shè)計(jì)的匿名規(guī)則屬于單約束規(guī)則，所以采用這種傳統(tǒng)匿名規(guī)則設(shè)計(jì)方法對(duì)所要發(fā)布的高維數(shù)據(jù)表進(jìn)行隱私保護(hù)時(shí)會(huì)造成大量有用信息損失。文獻(xiàn) ［8］提出多約束規(guī)則以適應(yīng)多種約束條件，能夠較好地實(shí)現(xiàn)發(fā)布數(shù)據(jù)的隱私保護(hù)程度與數(shù)據(jù)可用性之間的平衡。但是其并未給出對(duì)于每個(gè)約束集約束參數(shù)的設(shè)定方法。本文考慮到不同的準(zhǔn)標(biāo)識(shí)符屬性對(duì)敏感屬性產(chǎn)生的影響程度是不同的，提出基于粗糙集理論的準(zhǔn)標(biāo)識(shí)符屬性維度劃分的匿名規(guī)則設(shè)計(jì)方法。該方法不需要先驗(yàn)知識(shí)，而是根據(jù)待發(fā)布數(shù)據(jù)表的特點(diǎn)，即根據(jù)準(zhǔn)標(biāo)識(shí)符屬性重要度的差別，對(duì)準(zhǔn)標(biāo)識(shí)符屬性維度進(jìn)行自動(dòng)劃分，實(shí)現(xiàn)多約束匿名參數(shù)的設(shè)計(jì)；對(duì)不同維度的劃分進(jìn)行相應(yīng)的匿名化操作。另外，針對(duì)分類型數(shù)據(jù)的特點(diǎn)，基于粗糙集理論和信息熵理論，設(shè)計(jì)了一種分類型數(shù)據(jù)可用性評(píng)估模型。該模型從泛化后的信息損失與等價(jià)類對(duì)集合劃分導(dǎo)致的信息熵改變兩方面綜合評(píng)估匿名化數(shù)據(jù)表的信息損失量。

1 相關(guān)概念

1.1 粗糙集基本概念簡介

粗糙集理論是用于處理含糊性和不確定性的一種數(shù)學(xué)工具［9］。該理論主要從不完整的數(shù)據(jù)集中發(fā)現(xiàn)模式和規(guī)律，在短短20多年里，粗糙集理論已經(jīng)在各個(gè)領(lǐng)域得到了廣泛的應(yīng)用。在數(shù)據(jù)發(fā)布中的隱私保護(hù)中，需要進(jìn)行保護(hù)的數(shù)據(jù)往往有冗余及缺失，是一個(gè)不完整的信息系統(tǒng)。由于粗糙集在屬性約簡方面具有獨(dú)特的優(yōu)勢，因此它在數(shù)據(jù)發(fā)布中隱私保護(hù)的應(yīng)用也越來越得到重視。

DT ＝（U，C∪D，V，f）是一個(gè)決策表，參考文獻(xiàn) ［10］中的定義。

定義1［10］DT ＝（U，C ∪D，V，f）是一個(gè)決策表，R表示等價(jià)關(guān)系，X U 是任一子集，則其下近似定義為（X）＝∪｛Y ∈U／R｜Y X｝，上近似定義為（X）＝∪｛Y ∈U／R｜Y ∩X ≠｝。則其R－正區(qū)域記為：POSR（X）＝R（X），R－負(fù)區(qū)域記為：NEGR（X）＝U－（X）。

定義2［10］DT ＝（U，C ∪D，V，f）是一個(gè)決策表，其條件屬性和決策屬性分別是C 和D，稱C 在D 中以程度k（0 ≤k ≤1）依賴于C，記成C →kD ，其中k ＝card（POSC（D））／card（U），POSC（D）是D 的C－正區(qū)域。

定義4［10］DT ＝（U，C ∪D，V，f）是一個(gè)決策表，其條件屬性集為C，決策屬性集為D，任一條件屬性c∈C關(guān)于D 的屬性重要度定義為：Sig（c）＝I（D｜（C－｛c｝））－I（D｜C）＋I(xiàn)（D｜｛c｝）。

1.2 多約束規(guī)則

用一個(gè)三元組T ＝（U，QI，SA）表示未經(jīng)隱私保護(hù)的數(shù)據(jù)表，它實(shí)質(zhì)上是一個(gè)決策表，QI 表示準(zhǔn)標(biāo)識(shí)符屬性集，和信息系統(tǒng)中的條件屬性集CA 相對(duì)應(yīng)，敏感屬性集用SA表示，和信息系統(tǒng)中的決策屬性集D 相對(duì)應(yīng)。數(shù)據(jù)表T 稱為待發(fā)布數(shù)據(jù)表。

匿名約束C 描述C ＝＜QI，K ＞。其中QI ＝｛attr1，…，attrm｝，QI 為約束的準(zhǔn)標(biāo)識(shí)符，由一組屬性attri，i＝1，2，…，m 組成。K 為約束C 的匿名參數(shù)，即有K 條元組上在QI 上相等。多約束規(guī)則有如下定義［8］：一個(gè)約束集被表示為CSet＝｛C1，C2，…，Cr｝，其中Ci＝＜QIi，Ki＞，i＝1，2，…，r，ci表示第i個(gè)約束。r為約束集CSet中的約束數(shù)目，記作｜CSet｜。

2 基于屬性重要度的多約束匿名參數(shù)的選擇

2.1 基于屬性重要度的匿名化參數(shù)K 值選擇的數(shù)據(jù)模型

對(duì)于一個(gè)待發(fā)布數(shù)據(jù)表T，如果其所有元組滿足經(jīng)過匿名化處理得到表T′，劃分得到若干個(gè)等價(jià)類，每個(gè)等價(jià)類中的元組數(shù)目不小于K，則稱表T＇滿足K－匿名，K 為匿名化參數(shù)。

定義5 約束子集屬性平均重要度：給定一個(gè)數(shù)據(jù)表T＝（U，QI，SA），對(duì)任意約束Ci＝＜QIi，Ki＞，QIiQI，i＝1，2，…，r，設(shè)QIi＝｛attri1，attri2，…，attris｝，則QIi子集的平均重要度記為kQIi，定義為，其中kattrij是屬性attrij，j＝1，2，…，s的屬性重要度。

由于經(jīng)典的K－匿名化將數(shù)據(jù)表看成單一約束，即C ＝＜QI，K ＞，其中QI 為數(shù)據(jù)表的全部準(zhǔn)標(biāo)識(shí)符。本文將這個(gè)匿名參數(shù)K 視為屬性集QI 的屬性平均重要度下對(duì)應(yīng)的匿名參數(shù)。

定義6 準(zhǔn)標(biāo)識(shí)符QI 的平均重要度及對(duì)應(yīng)的匿名參數(shù)：給定數(shù)據(jù)表T ＝（U，QI，SA）和匿名參數(shù)K，準(zhǔn)標(biāo)識(shí)符QI 對(duì)應(yīng)的平均重要度記為kQI，則定義數(shù)據(jù)表準(zhǔn)標(biāo)識(shí)符QI 的平均重要度所對(duì)應(yīng)的匿名參數(shù)為K 。

本文根據(jù)約束子集屬性平均重要度的不同，相應(yīng)約束子集的匿名參數(shù)取值也不同，約束子集屬性平均重要度與準(zhǔn)標(biāo)識(shí)符QI 的屬性平均重要度及其它們多對(duì)應(yīng)的匿名參數(shù)之間的關(guān)系定義如下。

定義7 約束子集屬性平均重要度與對(duì)應(yīng)匿名參數(shù)：給定一個(gè)數(shù)據(jù)表T ＝（U，QI，SA），對(duì)任意約束Ci＝＜QIi，Ki＞，QIiQI，i＝1，2，…，r，對(duì)應(yīng)QIi的平均重要度記為kQIi。則定義Ki為：Ki＝K＊kQI／kQIi。

2.2 基于屬性重要度的約束集劃分算法

算法1：約束集劃分算法

設(shè)T ＝（U，QI，SA）是一個(gè)待發(fā)布的數(shù)據(jù)表，準(zhǔn)標(biāo)識(shí)符集被記作QISet＝｛attr1，…，attrm｝，準(zhǔn)標(biāo)識(shí)符attri，i＝1，…，m 的屬性重要度記為kattri，i＝1，…，m。

輸入：待發(fā)布數(shù)據(jù)表T，其有n個(gè)體，m 維準(zhǔn)標(biāo)識(shí)符屬性，初始匿名參數(shù)K。

輸出：約束集CSet＝｛C1，…，Cr｝

步驟1 根據(jù)定義4，計(jì)算所有準(zhǔn)標(biāo)識(shí)符屬性重要度，其屬性重要度集合kSet＝｛kattr1，…，kattrm｝。

步驟2 對(duì)kSet采用基于密度的聚類技術(shù)進(jìn)行聚類，生成h個(gè)簇，即得到重要度子集subkSet1，…，subkSeth，將其對(duì)應(yīng)的準(zhǔn)標(biāo)識(shí)符集劃分為相應(yīng)的h 個(gè)簇，即subQISet1，…，subQISeth。

步驟3 根據(jù)定義5求出每個(gè)重要度子集的平均屬性重要度，得到相應(yīng)的平均屬性重要度集合＝｛kQI1，kQI2，…，kQIh｝。

步驟4 由初始的匿名參數(shù)K，根據(jù)定義6和定義7求得相應(yīng)的每個(gè)約束的匿名化參數(shù)｛K1，K2，…，Kh｝。

步驟5 得到數(shù)據(jù)表的約束集CSet ＝｛＜subQISet1，K1＞，＜suQISet2，K2＞，…，＜subQISeth，Kh＞｝。

2.3 多約束條件的匿名化方法

基于上述分析，本文提出一種多約束條件的匿名化方法，描述如下：

算法2：多約束條件的匿名化算法

輸入：待發(fā)布數(shù)據(jù)表T ＝（U，QI，SA）

輸出：可發(fā)布數(shù)據(jù)表T′

步驟1 根據(jù)算法1，得到數(shù)據(jù)表的約束集CSet＝｛＜subQISet1，K1＞，＜suQISet2，K2＞，…，＜subQISeth，Kh＞｝；

步驟2 根據(jù)約束集把表T 劃分成h 個(gè)子表T1，T2，…，Th；

步驟3 對(duì)任意子表Ti，i＝1，2，…，h，根據(jù)對(duì)應(yīng)的屬性子集subQISeti和匿名參數(shù)Ki進(jìn)行Ki－匿名化；

步驟4 根據(jù)每個(gè)元素的ID 合并所有子表，重新生成所有元組，最終得到可發(fā)布數(shù)據(jù)表T′。

3 基于粗糙熵的分類型數(shù)據(jù)可用性評(píng)估模型

泛化其本質(zhì)是對(duì)于等價(jià)類中的每個(gè)屬性，用一個(gè)集合去代替，可以用粗糙集理論去度量其數(shù)據(jù)可用性。本文定義經(jīng)過泛化后數(shù)據(jù)表中屬性的粗糙度及近似精度如下：

由于數(shù)據(jù)類型分成分類型數(shù)據(jù)、連續(xù)型數(shù)據(jù)和混合型數(shù)據(jù)。為此，針對(duì)不同類型的數(shù)據(jù)集，要設(shè)計(jì)不同類型的數(shù)據(jù)可用性評(píng)估模型。針對(duì)分類型數(shù)據(jù)的特點(diǎn)，基于粗糙集理論和信息熵理論，本文設(shè)計(jì)了一種分類型數(shù)據(jù)可用性評(píng)估模型。

按照粗糙集觀點(diǎn)，粗糙集的不確定性由兩方面原因造成：

其一是知識(shí)性的粗糙性 （屬性對(duì)論域的劃分）；

其二是粗糙集的邊界。

于是根據(jù)上述定義，本文對(duì)粗糙熵定義提出改進(jìn)如下：

定義9 設(shè)T′＝（U，QI，SA）是一個(gè)有n個(gè)個(gè)體，m 維屬性的經(jīng)過匿名算法處理后的數(shù)據(jù)表，U 為其全域，設(shè)該數(shù)據(jù)表的族集U／QI ＝｛X1，X2，…，Xg｝，則該數(shù)據(jù)表的粗糙熵定義為

我們用此粗糙熵來衡量數(shù)據(jù)的分類型數(shù)據(jù)表經(jīng)過泛化后的數(shù)據(jù)表的可用性或信息損失量。

4 測試與比較

4.1 實(shí)驗(yàn)環(huán)境

本實(shí)驗(yàn)平臺(tái)的操作系統(tǒng)為Windows 7 （32位系統(tǒng)）。算法采用MATLAB 7.0 實(shí)現(xiàn)。運(yùn)行的機(jī)器配置為處理器：Intel Core i3M380 2.53Ghz，內(nèi)存：DDR3 2G。

4.2 實(shí)驗(yàn)數(shù)據(jù)集介紹

使用的數(shù)據(jù)集為UCI數(shù)據(jù)集中的Adult數(shù)據(jù)集作為測試數(shù)據(jù) （刪除所有連續(xù)型變量）測試分類型數(shù)據(jù)的微聚集算法，該數(shù)據(jù)是美國人口普查的信息結(jié)果。數(shù)據(jù)庫元組個(gè)數(shù)452 22個(gè)，從中隨機(jī)抽取1000個(gè)作為測試數(shù)據(jù)。

4.3 實(shí)驗(yàn)中的相關(guān)參數(shù)

4.4 實(shí)驗(yàn)比較結(jié)果

將本文采用智能約束集劃分隱私保護(hù)規(guī)則實(shí)現(xiàn)的匿名化方法 （稱本文算法）與傳統(tǒng)k－匿名規(guī)則的微聚集算法（MDAV 算法）在數(shù)據(jù)集Adult上進(jìn)行測試比較。

根據(jù)Adult數(shù)據(jù)集的特點(diǎn)，基于粗糙集屬性重要度的計(jì)算，我們得到的約束集為：

C1＝｛＜education，marital－status＞，K1｝；

C2＝｛＜o(jì)ccupation，relationship ＞，K2｝；

C3＝｛＜native－country，workclass＞，K3｝；

而K1：K2：K3＝5：3：1（取整后的近似比）。

4.4.1 泄密風(fēng)險(xiǎn)分析

實(shí)驗(yàn)中用于基于評(píng)估泄密方顯的方式是基于元組鏈接的評(píng)估方法 （DLD）。比較了基于k－匿名規(guī)則的傳統(tǒng)微聚集算法和本文算法的泄密風(fēng)險(xiǎn)。

表1是針對(duì)Adult數(shù)據(jù)集分別用2 種匿名算法生成的匿名表的風(fēng)險(xiǎn)評(píng)估測試結(jié)果。

表1 Adult匿名表的風(fēng)險(xiǎn)評(píng)估結(jié)果

通過上述實(shí)驗(yàn)結(jié)果可以看出，在相同的k值上，本文風(fēng)險(xiǎn)泄露多一些。但差距不大。傳統(tǒng)K－匿名模型把元組劃分成若干等價(jià)類。但本文算法只在根據(jù)約束集劃分的子表上成等價(jià)類。合并后得到的可發(fā)布數(shù)據(jù)表并不滿足K－匿名條件，元組的失真度相對(duì)較小。每個(gè)元組距離原始元組的距離變小，所以鏈接到原始元組的概率增大。

4.4.2 數(shù)據(jù)可用性分析

表2是針對(duì)Adult數(shù)據(jù)集分別采用2 種匿名算法測試匿名化后數(shù)據(jù)可用性的測試結(jié)果。

由上述實(shí)驗(yàn)結(jié)果可以看出，本文提出的模型劃分方法降低了原始數(shù)據(jù)表的維度，每個(gè)子表在較低的維度把元組劃分成若干等價(jià)類，更好的保護(hù)了數(shù)據(jù)的真實(shí)性。而傳統(tǒng)微聚集算法本文算法隨著準(zhǔn)標(biāo)識(shí)符個(gè)數(shù)的增加，即維度增大，要付出更大的代價(jià)實(shí)現(xiàn)匿名化。本文算法可以通過選擇更大的k值降低數(shù)據(jù)泄露的風(fēng)險(xiǎn)。如設(shè)置k＝5時(shí)，本文算法的數(shù)據(jù)可用性要好于k＝4時(shí)傳統(tǒng)微聚集算法的數(shù)據(jù)可用性，泄露的風(fēng)險(xiǎn)也更低。

表2 Adult匿名表的信息損失量

5 結(jié)束語

不同的準(zhǔn)標(biāo)識(shí)符屬性對(duì)敏感屬性產(chǎn)生的影響程度是不同的，采用相同匿名參數(shù)進(jìn)行的劃分會(huì)造成不必要的信息損失。本文通過基于粗糙集方法研究和設(shè)計(jì)維度劃分的匿名規(guī)則。所提出的規(guī)則所得到的可發(fā)布數(shù)據(jù)表并不是一個(gè)k－匿名劃分，而是在相應(yīng)的約束子集上具有不同k－劃分，從而實(shí)現(xiàn)了對(duì)屬性在不同層次上的概括。實(shí)驗(yàn)結(jié)果表明，所提出的多約束的匿名參數(shù)選擇方法能平衡數(shù)據(jù)的保護(hù)程度與數(shù)據(jù)可用性之間的關(guān)系。下一步工作包括完善和優(yōu)化所提出的方法，并進(jìn)一步與其它優(yōu)秀的匿名算法進(jìn)行比較實(shí)驗(yàn)，同時(shí)進(jìn)一步深入針對(duì)連續(xù)數(shù)據(jù)和混合的不同屬性類型研究評(píng)價(jià)數(shù)據(jù)可用性的模型等。

［1］REN Yi，PENG Zhiyong，TANG Zukai，et al.Privacy databaseconcepts，development and challenge［J］.Journal of Chinese Computer Systems，2008，29 （8）：1467－1474（in Chinese）.［任毅，彭智勇，唐祖鍇，等.隱私數(shù)據(jù)庫—概念、發(fā)展和挑戰(zhàn) ［J］.小型微型計(jì)算機(jī)系統(tǒng)，2008，29 （8）：1467－1474.］

［2］Machanavajjhala A，Gehrke J，Kifer D，et al.l－diversity：Privacy beyond k－anonymity ［C］／／Proceedings of the 22nd International Conference on Data Enginee－ring.IEEE Computer Society，2006：24－35.

［3］Li N，Li T，Venkatasubramanian S.T－closeness：Privacy beyond k－anonymity and l－diversity ［C］／／Proceedings of the 23rd International Conference on Data Engineering.IEEE，2007：106－115.

［4］Zhang Q，Koudas N，Srivastava D，et al.Aggregate query answering on anonymized tables［C］／／Proceedings of the 23rd International Conference on Data Engineering.IEEE，2007：116－125.

［5］Chen B C，Ramkrishnan R，LeFevre K.Privacy skyline：Privacy with multidimensional adversarial knowledge ［C］／／Proceedings of the 33rd International Conference on Very Large Data Bases.ACM，2007：770－781.

［6］LIU Yubao，HUANG Zhilan，F(xiàn)u Ada Wai Chee，et al.A data privacy preservation method based on lossy decomposition［J］.Journal of Computer Research and Development，2009，46 （7）：1217－1225 （in Chinese）.［劉玉葆，黃志蘭，傅慰慈，等.基于有損分解的數(shù)據(jù)隱私保護(hù)方法 ［J］.計(jì)算機(jī)研究與發(fā)展，2009，46 （7）：1217－1225.］

［7］Martin D，Kifer D，Machanavajjhala A，et al.Worst－case background knowledge in privacy ［C］／／Proceedings of the 23rd International Conference on Data Engineering.IEEE，2007：116－125.

［8］LIU Ming，YE Xiaojun.Personalized K－anonymity ［J］.Computer Engineering and Design，2008，29 （2）：282－286（in Chinese）.［劉明，葉曉俊.個(gè)性化K－匿名模型 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2008，29 （2）：282－286.］

［9］WANG Lu，QIU Taorong，HE Niu，et al.A method for feature selection based on rough sets and ant colony optimization algorithm ［J］.Journal of Nanjing University （Natural Sciences），2010，46 （5）：487－493 （in Chinese）.［王璐，邱桃榮，何妞，等.基于粗糙集和蟻群優(yōu)化算法的特征選擇方法［J］.南京大學(xué)學(xué)報(bào) （自然科學(xué)），2010，46 （5）：487－493.］

［10］MIAO Duoqian.Rough sets theory algorithms and application［M］.Beijing：Tsinghua University Press，2008：174－180（in Chinese）.［苗奪謙.粗糙集理論、算法與應(yīng)用 ［M］.北京：清華大學(xué)出版社，2008：174－180.］

［11］CHEN Jianming，HAN Jianming.Evaluation model for quality of k－anonymity data oriented tom icroaggregation ［J］.Application Research of Computers，2010，27 （6）：2345－2347（in Chinese）.［陳建明，韓建明.面向微聚集技術(shù)的k－匿名數(shù)據(jù)質(zhì)量評(píng)估模型 ［J］.計(jì)算機(jī)應(yīng)用研究，2010，27 （6）：2345－2347.］