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

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

?

多屬性泛化的-匿名算法

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

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

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

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

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

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

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

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

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

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

表1 K-匿名模型實(shí)例

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

圖1 準(zhǔn)標(biāo)識(shí)符屬性泛化層次圖

定義 4 等價(jià)組。數(shù)據(jù)表中準(zhǔn)標(biāo)識(shí)符屬性取值完全相同的記錄組合在一起稱為一個(gè)等價(jià)組[20]。

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

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

1.3 Datafly算法分析

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

2.1 基本思想

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

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

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

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

2.2 泛化屬性選取

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

1) 取值最多的準(zhǔn)標(biāo)識(shí)符屬性只存在一個(gè)。

當(dāng)取值最多的準(zhǔn)標(biāo)識(shí)符屬性只存在一個(gè)的時(shí)候，多屬性泛化的-匿名算法選取這一準(zhǔn)標(biāo)識(shí)符屬性進(jìn)行泛化處理。

2) 屬性值種類最多的準(zhǔn)標(biāo)識(shí)符屬性不唯一。

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

根據(jù)前面對(duì)準(zhǔn)標(biāo)識(shí)符屬性近似度的定義，標(biāo)準(zhǔn)差反映一組數(shù)據(jù)的離散程度，故用標(biāo)準(zhǔn)差來(lái)描述準(zhǔn)標(biāo)識(shí)符屬性的近似度，計(jì)算步驟和公式如下：

3) 求出該準(zhǔn)標(biāo)識(shí)符屬性的方差為：

表2 醫(yī)療信息表

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

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

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

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

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

步驟：

=0;

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

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

else

計(jì)算每一個(gè)準(zhǔn)標(biāo)識(shí)符屬性值的種類數(shù)

and找到屬性取值種類數(shù)最多的準(zhǔn)標(biāo)識(shí)符屬性;

if(屬性值種類最多的準(zhǔn)標(biāo)識(shí)符屬性為1)

選取該準(zhǔn)標(biāo)識(shí)符屬性；

else計(jì)算屬性值種類最多的準(zhǔn)標(biāo)識(shí)符屬性近似度

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

end if;

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

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

end if。

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

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

3.1 實(shí)驗(yàn)數(shù)據(jù)集

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

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

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

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

3.3 實(shí)驗(yàn)分析

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

1) 算法運(yùn)行時(shí)間隨值變化情況

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

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

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

圖2 算法運(yùn)行時(shí)間隨K值變化情況

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

[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] 夏贊珠, 韓建民, 于娟, 等. 用于實(shí)現(xiàn) (,)-匿名模型的 MDAV 算法[J]. 計(jì)算機(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]. 計(jì)算機(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] 彭長(zhǎng)根, 丁紅發(fā), 朱義杰, 等. 隱私保護(hù)的信息熵模型及其度量方法[J]. 軟件學(xué)報(bào), 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é)點(diǎn)可達(dá)性的高效社會(huì)網(wǎng)絡(luò)圖匿名算法[J]. 軟件學(xué)報(bào), 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] 韋茜, 李星毅. 基于-匿名的快遞信息隱私保護(hù)應(yīng)用[J]. 計(jì)算機(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]. 計(jì)算機(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é)報(bào), 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

國(guó)家自然科學(xué)基金面上項(xiàng)目(71171028)；國(guó)家科技支撐計(jì)劃(2013BAH01B03)

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