劉 萍，邱桃榮，段文影

（南昌大學 信息工程學院，江西 南昌330031）

0 引 言

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

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

1 相關概念

1.1 粗糙集基本概念簡介

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

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

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

定義2［10］DT ＝（U，C ∪D，V，f）是一個決策表，其條件屬性和決策屬性分別是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）是一個決策表，其條件屬性集為C，決策屬性集為D，任一條件屬性c∈C關于D 的屬性重要度定義為：Sig（c）＝I（D｜（C－｛c｝））－I（D｜C）＋I（D｜｛c｝）。

1.2 多約束規(guī)則

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

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

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

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

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

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

由于經典的K－匿名化將數(shù)據表看成單一約束，即C ＝＜QI，K ＞，其中QI 為數(shù)據表的全部準標識符。本文將這個匿名參數(shù)K 視為屬性集QI 的屬性平均重要度下對應的匿名參數(shù)。

定義6 準標識符QI 的平均重要度及對應的匿名參數(shù)：給定數(shù)據表T ＝（U，QI，SA）和匿名參數(shù)K，準標識符QI 對應的平均重要度記為kQI，則定義數(shù)據表準標識符QI 的平均重要度所對應的匿名參數(shù)為K 。

本文根據約束子集屬性平均重要度的不同，相應約束子集的匿名參數(shù)取值也不同，約束子集屬性平均重要度與準標識符QI 的屬性平均重要度及其它們多對應的匿名參數(shù)之間的關系定義如下。

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

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

算法1：約束集劃分算法

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

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

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

步驟1 根據定義4，計算所有準標識符屬性重要度，其屬性重要度集合kSet＝｛kattr1，…，kattrm｝。

步驟2 對kSet采用基于密度的聚類技術進行聚類，生成h個簇，即得到重要度子集subkSet1，…，subkSeth，將其對應的準標識符集劃分為相應的h 個簇，即subQISet1，…，subQISeth。

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

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

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

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

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

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

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

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

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

步驟2 根據約束集把表T 劃分成h 個子表T1，T2，…，Th；

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

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

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

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

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

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

其一是知識性的粗糙性 （屬性對論域的劃分）；

其二是粗糙集的邊界。

于是根據上述定義，本文對粗糙熵定義提出改進如下：

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

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

4 測試與比較

4.1 實驗環(huán)境

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

4.2 實驗數(shù)據集介紹

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

4.3 實驗中的相關參數(shù)

4.4 實驗比較結果

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

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

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

C2＝｛＜occupation，relationship ＞，K2｝；

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

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

4.4.1 泄密風險分析

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

表1是針對Adult數(shù)據集分別用2 種匿名算法生成的匿名表的風險評估測試結果。

表1 Adult匿名表的風險評估結果

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

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

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

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

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

5 結束語

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

［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ù)據庫—概念、發(fā)展和挑戰(zhàn) ［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］.計算機研究與發(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）.［劉明，葉曉俊.個性化K－匿名模型 ［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］.南京大學學報 （自然科學），2010，46 （5）：487－493.］

［10］MIAO Duoqian.Rough sets theory algorithms and application［M］.Beijing：Tsinghua University Press，2008：174－180（in Chinese）.［苗奪謙.粗糙集理論、算法與應用 ［M］.北京：清華大學出版社，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）.［陳建明，韓建明.面向微聚集技術的k－匿名數(shù)據質量評估模型 ［J］.計算機應用研究，2010，27 （6）：2345－2347.］