多屬性泛化的K-匿名算法

宋明秋，王 琳，姜寶彥，鄧貴仕

?

多屬性泛化的-匿名算法

宋明秋，王 琳，姜寶彥，鄧貴仕

(大連理工大學(xué)系統(tǒng)工程研究所 大連 遼寧 116024)

針對現(xiàn)有的-匿名模型中存在泛化屬性選取不唯一和數(shù)據(jù)過度泛化的問題，提出多屬性泛化的-匿名算法。在-匿名模型實現(xiàn)的過程中，引入屬性近似度概念，定量刻畫準標識符屬性的離散程度，進而確定泛化的準標識符屬性；同時采用廣度優(yōu)先泛化的方法，避免數(shù)據(jù)被過度泛化，最終實現(xiàn)數(shù)據(jù)表的-匿名要求。實驗結(jié)果表明，多屬性泛化的-匿名模型可以提高泛化后數(shù)據(jù)精度，其處理效率和Datafly算法相當。該算法有效地解決了取值最多準標識符屬性存在多個時的泛化屬性選取問題，并且防止屬性被過度泛化，提高數(shù)據(jù)的可用性。

泛化;-匿名; 隱私保護; 關(guān)系型數(shù)據(jù)

隨著網(wǎng)絡(luò)技術(shù)的高速發(fā)展，大量的個人信息被政府部門、科研機構(gòu)等有關(guān)組織存儲、發(fā)布，導(dǎo)致隱私信息被曝光，先進的數(shù)據(jù)挖掘算法在提高信息有效性的同時，也導(dǎo)致了隱私泄露的問題[1]。如何在數(shù)據(jù)共享的同時，實現(xiàn)有效合理的隱私保護方法[2]就顯得尤為重要。

早在20世紀80年代初，文獻[3]首次提出了匿名化的概念，并指出這種技術(shù)手段可應(yīng)用于隱私信息的保護。文獻[4]提出-匿名模型的數(shù)據(jù)匿名化隱私保護方法，通過泛化和抑制[5]、分解和排列[6]以及微聚集和凝聚[7]等方式對原始數(shù)據(jù)進行匿名化處理，有效地解決了鏈接攻擊問題。文獻[8]在-匿名模型的基礎(chǔ)上提出了一種新的隱私保護模型即l-多樣性模型，對數(shù)據(jù)表中的敏感屬性進行相關(guān)約束，提升發(fā)布的數(shù)據(jù)表對于同質(zhì)攻擊或背景知識攻擊等的防范。此后，(,)-匿名模型[9]使用閾值對敏感屬性進行約束；針對l-多樣性模型在一些特殊情況下不適用的問題提出了-closeness模型[10]，要求敏感屬性接近全局分布；而(,)-匿名模型[11]和(, l)-匿名模型[12]等模型為針對敏感屬性為數(shù)值型數(shù)據(jù)的近似攻擊提供了解決方案[13]。文獻[14]用信息熵模型刻畫屬性的隱私程度，進而為信息泄露風(fēng)險量化提供支撐。此外，匿名模型在多領(lǐng)域的應(yīng)用也成為現(xiàn)階段的研究熱點，文獻[15]將-匿名技術(shù)應(yīng)用到社會網(wǎng)絡(luò)圖的隱私保護，應(yīng)用位置服務(wù)數(shù)據(jù)[16]和快遞信息[17]等隱私保護也采用-匿名技術(shù)。

現(xiàn)有的-匿名模型研究主要集中于高效近似算法的設(shè)計和多領(lǐng)域的應(yīng)用，在模型算法實現(xiàn)中，沒有考慮取值最多的準標識符屬性不唯一的情況，以及選取的準標識符屬性一直被泛化，從而導(dǎo)致數(shù)據(jù)精度過低的問題。針對這一問題，本文討論泛化屬性選取方法，每次泛化操作之前通過準標識符屬性取值的種類及其近似度選定泛化屬性，有效避免單一屬性的過度泛化，提高泛化后數(shù)據(jù)集的可用性。

1 K-匿名模型相關(guān)定義

1.1 數(shù)據(jù)匿名

定義 3 泛化。在數(shù)據(jù)匿名處理過程中，對數(shù)據(jù)采用模糊的、抽象的值替代原始數(shù)據(jù)的方式，稱為泛化[19]，即用高層次的節(jié)點代替低層次的節(jié)點，泛化處理層次如圖1所示。

表1 K-匿名模型實例

a. 1層泛化 b. 2層泛化 c. 3層泛化

圖1 準標識符屬性泛化層次圖

定義 4 等價組。數(shù)據(jù)表中準標識符屬性取值完全相同的記錄組合在一起稱為一個等價組[20]。

1.2 數(shù)據(jù)精度

定義5 數(shù)據(jù)精度。數(shù)據(jù)精度是衡量經(jīng)過泛化后的數(shù)據(jù)與真實數(shù)據(jù)的逼近程度，即泛化后數(shù)據(jù)損失的度量。泛化后的數(shù)據(jù)與真實數(shù)據(jù)越接近，信息的損失量越少，泛化后的數(shù)據(jù)可用性越高。因此，數(shù)據(jù)精度是評價-匿名模型實現(xiàn)算法的一個重要指標。

1.3 Datafly算法分析

2 多屬性泛化的K-匿名算法

2.1 基本思想

在多屬性泛化的-匿名算法中，需要匿名化處理的準標識符屬性是由數(shù)據(jù)表中的準標識符屬性值的種類決定。選取取值種類最多的屬性作為優(yōu)先泛化的屬性，按其預(yù)先給定的泛化層次進行泛化。

首先，針對屬性過度泛化問題。多屬性泛化的-匿名算法在每次泛化和-匿名檢驗后都重新選取需要泛化的準標識符屬性。這樣降低了給定的數(shù)據(jù)表被過度泛化的可能性，加快關(guān)系型數(shù)據(jù)表滿足-匿名的要求，提高泛化后數(shù)據(jù)的可用性。

其次，針對屬性選取不唯一問題，Datafly算法在泛化的準標識符屬性選取這一環(huán)節(jié)中，都沒有考慮取值最多的準標識符屬性同時存在多個的情況。因此，引入屬性近似度這一概念，依據(jù)準標識符屬性近似度的值，選取近似度最大的準標識符屬性優(yōu)先進行泛化。

定義 6 屬性近似度。準標識符屬性的近似度即準標識符屬性的域值之間的離散程度。準標識符屬性的近似度越高，其屬性值分布越不均勻，對其進行泛化不僅可以降低背景知識攻擊等的威脅，還可以加快數(shù)據(jù)表滿足-匿名模型。

2.2 泛化屬性選取

在多屬性泛化的-匿名算法中，只對關(guān)系型數(shù)據(jù)表中的準標識符屬性進行泛化處理。實際的關(guān)系型數(shù)據(jù)表中通常存在多個準標識符屬性，需要進行如下分析來選取優(yōu)先泛化的屬性：

1) 取值最多的準標識符屬性只存在一個。

當取值最多的準標識符屬性只存在一個的時候，多屬性泛化的-匿名算法選取這一準標識符屬性進行泛化處理。

2) 屬性值種類最多的準標識符屬性不唯一。

當屬性值種類最多的準標識符屬性存在多個時，多屬性泛化的-匿名算法選取近似度值高的準標識符屬性作為泛化屬性，優(yōu)先進行泛化。近似度高的準標識符屬性的取值離散程度大，分布不均勻，使得某些等價組內(nèi)記錄條數(shù)過少，無法滿足-匿名要求。對近似度高的準標識符屬性進行泛化，可以增加等價組內(nèi)記錄的條數(shù)，減少包含記錄條數(shù)過少的等價組，進而加速實現(xiàn)-匿名模型。

根據(jù)前面對準標識符屬性近似度的定義，標準差反映一組數(shù)據(jù)的離散程度，故用標準差來描述準標識符屬性的近似度，計算步驟和公式如下：

3) 求出該準標識符屬性的方差為：

表2 醫(yī)療信息表

2.3 多屬性泛化的K-匿名算法

在算法運行前，需要輸入數(shù)據(jù)：泛化層次值和數(shù)據(jù)表中的準標識符屬性及其泛化層次。

根據(jù)初始的設(shè)定對所輸入的數(shù)據(jù)表進行-匿名檢驗。如果數(shù)據(jù)表滿足-匿名，那么系統(tǒng)會自動將所輸入的數(shù)據(jù)輸出。如果數(shù)據(jù)表不滿足-匿名，多屬性泛化的-匿名算法進入準標識符屬性分析選取階段，即計算各準標識符屬性的取值種類數(shù)。如果存在多個屬性值種類最多的準標識符屬性，那么計算種類最多的準標識符屬性的近似度，選取其近似度最大的屬性作為優(yōu)先泛化屬性。對該屬性進行一次泛化。泛化完畢后，再次對處理后的數(shù)據(jù)表進行檢驗，驗證數(shù)據(jù)表是否滿足-匿名要求。如果檢驗結(jié)果為“是”，那么系統(tǒng)將處理后的數(shù)據(jù)輸出；如果檢驗結(jié)果為“否”，那么表格將再次進入泛化屬性選取和-匿名檢驗的循環(huán)，直到其符合-匿名要求為止，步驟如下所示。

輸入：關(guān)系型數(shù)據(jù)表PT，準標識符屬性名稱，給定值，準標識符屬性的泛化層次

輸出：匿名處理后的數(shù)據(jù)表PT*

步驟：

=0;

if(關(guān)系型數(shù)據(jù)表滿足-匿名)

輸出匿名處理后的數(shù)據(jù)表;

else

計算每一個準標識符屬性值的種類數(shù)

and找到屬性取值種類數(shù)最多的準標識符屬性;

if(屬性值種類最多的準標識符屬性為1)

選取該準標識符屬性；

else計算屬性值種類最多的準標識符屬性近似度

and選擇近似度最高的屬性；

end if;

將該屬性按其泛化層次圖從層泛化至+1層，得到數(shù)據(jù)表;

return 關(guān)系型數(shù)據(jù)表;

end if。

3 實驗結(jié)果與分析

實驗?zāi)康氖菍Χ鄬傩苑夯?匿名算法性能進行評價，評價指標為算法運行時間和泛化后數(shù)據(jù)精度，并將本實驗的結(jié)果與經(jīng)典的Datafly算法運行結(jié)果進行對比，客觀地評價多屬性泛化的-匿名算法的性能。

3.1 實驗數(shù)據(jù)集

本文實驗選取了UCI Machine Learning Repository Adult數(shù)據(jù)集中的Adult.test文本文件作為實驗的數(shù)據(jù)樣本集[22]。采用文獻[23]中的數(shù)據(jù)預(yù)處理方法對原數(shù)據(jù)集進行預(yù)處理，得到實驗數(shù)據(jù)集中的16 008條數(shù)據(jù)作為最終的實驗數(shù)據(jù)。實驗數(shù)據(jù)囊括8個屬性作為準標識符屬性，1個屬性作為敏感屬性，實驗數(shù)據(jù)的情況如表3所示，其中，QID為準標識符屬性，SA為敏感屬性。

表3 數(shù)據(jù)結(jié)構(gòu)示意表

3.2 實驗環(huán)境

硬件環(huán)境：Intel(R) Core(TM) i7-6700 CPU @ 3.40 GHz；8.00 GB內(nèi)存；操作系統(tǒng)：Windows10；編程語言：C#。

3.3 實驗分析

在算法運行時間這一維度上，多屬性泛化的-匿名算法除了受軟硬件環(huán)境等一些客觀因素的影響外，還受取值和樣本數(shù)據(jù)大小的影響。因此，在有關(guān)算法運行時間的測算中，著重從的取值和樣本數(shù)據(jù)大小這兩個方面對該算法的運行時間進行測量。

1) 算法運行時間隨值變化情況

在樣本數(shù)據(jù)量一定，算法運行時間隨值變化趨勢的測量實驗中，樣本數(shù)據(jù)選定為處理后的數(shù)據(jù)集Adult.test中的所有數(shù)據(jù)(16 008條)。由于值表示等價組內(nèi)完全相同的記錄數(shù)，且避免數(shù)據(jù)表的鏈接攻擊，故值為大于等于2的正整數(shù)。

上述實驗結(jié)果中，當大于10時，值的增大對算法運行時間影響不大。因此值均從2～200中遞增選取，其中最小值為2，最大值為200，并將實驗的執(zhí)行結(jié)果以折線圖的形式進行輸出，如圖2所示。

實驗結(jié)果表明：當數(shù)據(jù)量一定時，-匿名模型實現(xiàn)算法的運行時間會隨著值的增大而增加。當值較小時，多屬性泛化的-匿名算法與Datafly算法的運行時間基本相同；但隨著值增大，多屬性泛化的-匿名算法的運行時間略微高于Datafly算法的運行時間。

圖2 算法運行時間隨K值變化情況

2) 算法運行時間隨數(shù)據(jù)量變化情況

在保持值不變，算法運行時間隨樣本數(shù)據(jù)量變化趨勢的測算試驗中，設(shè)定值為2，樣本數(shù)據(jù)是從處理后的數(shù)據(jù)集Adult.test(16 008條數(shù)據(jù))中依次選取10、20、50、100、500、1 000、10 000條數(shù)據(jù)作為實驗測算樣本，結(jié)果如圖3所示。

圖3 算法運行時間隨數(shù)據(jù)量的變化情況

實驗結(jié)果表明：當值一定時，-匿名模型實現(xiàn)算法的運行時間會隨著數(shù)據(jù)量的增大而增加。當數(shù)據(jù)量較小時，多屬性泛化的-匿名算法的運行時間與Datafly算法的運行時間基本相同。隨著數(shù)據(jù)量的不斷增大，多屬性泛化的-匿名算法的運行時間要略高于Datafly算法。原因是多屬性泛化的-匿名算法優(yōu)先選取近似度大的準標識符屬性進行泛化，增加等價組內(nèi)記錄條數(shù)，加快實現(xiàn)-匿名要求。但在每次泛化前，均需重新計算確定取值最多的準標識符屬性，選取近似度高的準標識符屬性進行泛化，故多屬性泛化的-匿名算法和Datafly算法的總體運行時間相仿。

3) 數(shù)據(jù)精度測算結(jié)果及分析

實驗選取Precision測算公式對泛化后數(shù)據(jù)進行精度測量。在-匿名算法中，各準標識符屬性的泛化程度是影響泛化后數(shù)據(jù)精度的最主要因素，而各準標識符屬性的泛化程度由實驗開始前所選取的值決定。樣本數(shù)據(jù)是經(jīng)處理后的Adult.test中的所有數(shù)據(jù)(16 008條)，值是從2～200中遞增選取，其中最小值為2，最大值為200，并和經(jīng)典Datafly算法進行對比，如圖4所示。

圖4 數(shù)據(jù)精度隨K值變化情況

實驗結(jié)果表明：當數(shù)據(jù)量一定時，經(jīng)-匿名模型實現(xiàn)算法處理后的數(shù)據(jù)精度會隨著值的增大而減小。在值為2時，兩種算法處理后的數(shù)據(jù)精度幾乎相同。不過，隨著值的不斷增大，多屬性泛化的-匿名算法處理后的數(shù)據(jù)精度要明顯高于Datafly算法處理后的數(shù)據(jù)精度。在多屬性泛化的-匿名算法中，每次泛化前均需重新選擇被泛化的屬性，有效解決Datafly算法中某一取值最多的準標識符屬性達到最高泛化等級時，數(shù)據(jù)表仍舊不能滿足-匿名要求而導(dǎo)致屬性被過度泛化的問題，故經(jīng)過多屬性泛化的-匿名算法泛化后的數(shù)據(jù)精度高于經(jīng)典Datafly算法泛化后的數(shù)據(jù)精度。

4 結(jié)束語

匿名算法的效率和處理后數(shù)據(jù)的可用性是衡量-匿名算法的兩個重要指標。針對經(jīng)典Datafly算法存在泛化屬性選取過于單一的問題，提出了多屬性泛化的-匿名算法。在該算法中，由準標識符屬性值的種類數(shù)量確定需要優(yōu)先泛化的準標識符屬性；并針對泛化過程中可能出現(xiàn)取值最多的準標識符屬性同時存在多個的情況，引入屬性近似度的概念，選取屬性近似度最大的準標識符屬性優(yōu)先泛化，有效地控制屬性過度泛化的問題，提高泛化后數(shù)據(jù)的可用性。通過與經(jīng)典Datafly算法進行實驗對比，多屬性泛化的-匿名算法泛化后數(shù)據(jù)精度更高，運算時間和Datafly算法相當，具有更好的實際應(yīng)用價值。

[1] LIN Chi, SONG Zi-hao, SONG Hou-bing, et al. Differential privacy preserving in big data analytics for connected health[J]. Journal of Medical Systems, 2016, 40(4): 1-9.

[2] CHEN De-yan, ZHAO Hong. Data security and privacy protection issues in cloud computing[C]//2012 International Conference on Computer Science and Electronics Engineering. Hangzhou, China: IEEE, 2012, 1: 647-651.

[3] COX L H. Suppression methodology and statistical disclosure control[J]. Journal of the American Statistical Association, 1980, 75(370): 377-385.

[4] SWEENEY L.-anonymity: a model for protecting privacy[J]. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2002, 10(5): 557-570.

[5] SWEENEY L. Achieving-anonymity privacy protection using generalization and suppression [J]. International Journal on Uncertainty, Fuzziness and Knowledge-based Systems, 2002,10(5): 571-588.

[6] SUN Xiao-xun, WANG Hua, LI Jiu-yong, et al. Publishing anonymous survey rating data[J]. Data Mining and Knowledge Discovery, 2011, 23(3): 379-406.

[7] SORIACOMAS J, DOMINGOFERRER J, SANCHEZ D and MARTINEZ S. Enhancing data utility in differential privacy via microaggregation-based-anonymity[J]. The VLDB Journal, 2014, 23(5): 771-794.

[8] MACHANAVAJJHALA A, KIFER D, GEHRKE J. L -diversity: Privacy beyond-anonymity[J]. ACM Transactions on Knowledge Discovery from Data, 2006, 1(1): 24.

[9] CHEN Rui, FUNG B C M, MOHAMMED N, et al. Privacy-preserving trajectory data publishing by local suppression[J]. Information Sciences, 2011, 231(1): 83-97.

[10] SORIACOMAS J, DOMINGOFERRER J, SANCHEZ D, et al. T-Closeness through microaggregation: Strict privacy with enhanced utility preservation[J]. IEEE Transactions on Knowledge & Data Engineering, 2015, 27(11): 3098- 3110.

[11] 夏贊珠, 韓建民, 于娟, 等. 用于實現(xiàn) (,)-匿名模型的 MDAV 算法[J]. 計算機工程, 2010, 36(15): 159-161. XIA Zan-zhu, HAN Jian-ming,YU Juan, et al. MDAV Algorithm for implementing (,)-Anonymity model[J]. Computer Engineering, 2010, 36(15): 159-161

[12] 楊高明, 李敬兆, 楊靜, 等. (,)-多樣性數(shù)據(jù)發(fā)布研究[J]. 計算機科學(xué), 2013, 40(8): 140-145.

YANG Gao-ming, LI Jing-zhao, YANG Jing, et al. Achieving(,)-diversity in privacy preserving data publishing[J]. Computer Science, 2013, 40(8): 140-145.

[13] LIU Qinghai, SHEN Hong, SANG Ying-peng. Privacy- preserving data publishing for multiple numerical sensitive attributes[J]. Tsinghua Science and Technology, 2015, 20(3): 246-254.

[14] 彭長根, 丁紅發(fā), 朱義杰, 等. 隱私保護的信息熵模型及其度量方法[J]. 軟件學(xué)報, 2016, 27(8): 1891-1903. PENG Chang-gen, DING Hong-fa, ZHU Yi-jie, et al. Information entropy models and privacy metrics methods for privacy protection[J]. Journal of Software, 2016, 27(8): 1891-1903.

[15] 劉向宇, 李佳佳, 安云哲, 等. 一種保持結(jié)點可達性的高效社會網(wǎng)絡(luò)圖匿名算法[J]. 軟件學(xué)報, 2016, 32(8): 1904-1921. LIU Xiang-yu, LI Jia-jia, AN Yun-zhe, et al. On reachability preserving graph anonymization in social networks[J]. Journal of Software, 2016, 32(8): 1904-1921.

[16] LI Xiu-hua, MIAO Mei-xia, LIU Hai, et al. An incentive mechanism for-anonymity in LBS privacy protection based on credit mechanism[J]. Soft Computing, 2017, 21(14): 3907-3917.

[17] 韋茜, 李星毅. 基于-匿名的快遞信息隱私保護應(yīng)用[J]. 計算機應(yīng)用研究, 2014, 31(2): 555-557. WEI Qian, LI Xing-yi. Express information protection application based on-anonymity[J]. Application Research of Computers, 2014, 31(2): 555-557.

[18] OLIVEIRA S R M, ZAIANE O R. Privacy preserving clustering by data transformation[J]. Journal of Information and Data Management, 2010, 1(1): 37-51.

[19] 呂品, 鐘珞, 王文兵, 等. MA-Datafly: 一種支持多屬性泛化的-匿名方法[J]. 計算機工程與應(yīng)用，2013，49(4): 138-139. Lü Pin, ZHONG Luo, WANG Wen-bing, et al. MA-Datafly:-anonymity approaches for supporting multi-attribute generalization[J]. Computer Engineering & Applications, 2013, 49(4): 138-139.

[20] HUNDEPOOL A, DOMINGOFERRER J, FRANCONI L, et al. Statistical disclosure control[M]. Chichester, UK: John Wiley & Sons Ltd, 2012.

[21] LI Tian-cheng, LI Ning-hui, ZHANG Jian, et al. Slicing: a new approach for privacy preserving data publishing[J]. IEEE Transactions on, Knowledge and Data Engineering, 2012, 24(3): 561-574.

[22] MURPHY P M, AHA D W. University of California Irvine machine learning repository[EB/OL]. (1996-02-15). http://archive.ics.uci. edu/ml/.

[23] 晏華, 劉貴松. 采用熵的多維-匿名劃分方法[J]. 電子科技大學(xué)學(xué)報, 2007, 36(6): 1228-1231. YAN Hua, LIU Gui-Song. Multidimensional-anonymity partition method using entropy[J]. Journal of University of Electronic Science and Technology of China, 2007, 36(6): 1228-1231.

編 輯 蔣 曉

-Anonymity Algorithm Based on Multi Attribute Generalization

SONG Ming-qiu, WANG Lin, JIANG Bao-yan, and DENG Gui-shi

(Institute of Systems Engineering, Dalian University of Technology Dalian Liaoning 116024)

Aiming at the major issues for data over-generalization and no unique attributes of-anonymity model, a modified-anonymity algorithm based on multiple attributes generalization is proposed in this paper. The conception of attribute approximation degree is introduced which describes the discrete degree of quasi-identifiers, and determines the candidate quasi-identifier attribute to be generalized. In the meantime, breadth-first generalization is exploited to avoid over-generalization and meets the-anonymity requirements ultimately. The experimental results show that the new-anonymity algorithm based on multiple attribute generalization can improve data precision and its efficiency is equal to Datafly algorithm. The proposed algorithm can effectively solve the issue of generalization attribute selecting when quasi-identifiers are not unique, the over-generalization of quasi-identifiers attributes can be avoided, and the usability of data can be improved.

generalization;-anonymity; privacy protecting; relational data

TP301.6

A

10.3969/j.issn.1001-0548.2017.06.018

2017-03-31；

2017-06-12

國家自然科學(xué)基金面上項目(71171028)；國家科技支撐計劃(2013BAH01B03)

宋明秋(1967-)，女，博士，副教授，主要從事信息安全、隱私保護方面的研究.