谷青竹，董紅斌

（武漢大學(xué)國家網(wǎng)絡(luò)安全學(xué)院，武漢 430000）

0 概述

k-匿名作為隱私保護數(shù)據(jù)挖掘（Privacy Preserving Data Mining，PPDM）研究中的一項關(guān)鍵技術(shù)，具有計算開銷低、數(shù)據(jù)形變小、能抵御鏈接攻擊等優(yōu)點［1］。在一些追求高數(shù)據(jù)可用性的k-匿名算法中，通常會提出度量數(shù)據(jù)集信息損失的數(shù)據(jù)可用性評估模型，但這些評估模型在屬性的可用性權(quán)重設(shè)置上存在缺陷，導(dǎo)致算法選擇出的最優(yōu)匿名數(shù)據(jù)集在后續(xù)的分類問題中表現(xiàn)較差。

目前數(shù)據(jù)集的發(fā)布共享越來越普遍，為避免在數(shù)據(jù)使用過程中造成的隱私泄露，研究人員希望通過修改原始數(shù)據(jù)集來保護隱私信息。但是，轉(zhuǎn)化原始數(shù)據(jù)可能會導(dǎo)致信息損失和數(shù)據(jù)挖掘結(jié)果不準(zhǔn)確。為此，隱私保護數(shù)據(jù)挖掘技術(shù)旨在保護隱私信息的前提下，最大化數(shù)據(jù)可用性，使得轉(zhuǎn)化后的數(shù)據(jù)仍然可以被有效用于數(shù)據(jù)挖掘［2-3］。隱私保護數(shù)據(jù)挖掘是一項在數(shù)據(jù)挖掘整個過程中實現(xiàn)隱私保護的研究，從數(shù)據(jù)的產(chǎn)生、發(fā)布，以及到挖掘的各個階段，都需要依靠PPDM 技術(shù)防止隱私泄露。數(shù)據(jù)發(fā)布階段的PPDM 技術(shù)主要包括匿名化、擾動和加密，這些技術(shù)適用的場景各不相同。匿名化主要用在數(shù)據(jù)集被公開發(fā)布的場景下，擾動多用于防止統(tǒng)計泄露的數(shù)據(jù)庫查詢中，加密則是不同地點的數(shù)據(jù)所有者在協(xié)同計算時應(yīng)用［1］。

本文構(gòu)建一種面向k-匿名的互信息損失（Mutual Information Loss，MI Loss）評估模型，該模型利用互信息計算屬性的可用性權(quán)重，使與標(biāo)簽相關(guān)性高的屬性可被較低程度泛化，從而減少關(guān)鍵屬性的信息損失，以提升匿名數(shù)據(jù)集在后續(xù)分類問題中的準(zhǔn)確率。

1 匿名化

匿名化是指在匿名化算法的指導(dǎo)下對原始數(shù)據(jù)集執(zhí)行一系列數(shù)據(jù)轉(zhuǎn)化操作，使其滿足相應(yīng)的匿名化模型。其中，只有數(shù)據(jù)轉(zhuǎn)化操作是對數(shù)據(jù)集的具體轉(zhuǎn)化，而匿名化算法和匿名化模型只提供理論的指導(dǎo)和約束。

1.1 k-匿名模型

k-匿名模型由SWEENEY 等［4］于1998 年提出，由于能抵御鏈接攻擊，已經(jīng)成為使用最廣泛的匿名化模型之一。k-匿名模型要求在發(fā)布的數(shù)據(jù)集中，每條記錄至少要與k-1 條記錄擁有相同的準(zhǔn)標(biāo)識符值，這樣攻擊者推測一條記錄所關(guān)聯(lián)個人的可能性被降低，達到了匿名化的效果。準(zhǔn)標(biāo)識符是指可以聯(lián)合起來標(biāo)識一個個人的屬性，例如當(dāng)用＜性別，職業(yè)，郵編＞這樣一個屬性組合就能識別出一個個體時，“性別”“職業(yè)”“郵編”就被稱為是準(zhǔn)標(biāo)識符。參數(shù)k越大，數(shù)據(jù)失真程度越高，隱私保護的效果越好，但相應(yīng)的信息損失也越大。經(jīng)過二十多年的發(fā)展，在k-匿名模型的基礎(chǔ)上，l-diversity［5］、t-closeness［6］、（alpha，k）-anonymity 等［7］眾多匿名化模型被相繼提出。這些模型通常使用一個或多個隱私參數(shù)來降低發(fā)布數(shù)據(jù)中一個個體被重標(biāo)識的風(fēng)險。

1.2 k-匿名算法

現(xiàn)有的k-匿名算法大致可以分為兩類：一類是基于泛化的k-匿名算法［8］；另一類是基于微聚合的k-匿名算法［9］。泛化是指使用一個更一般化的值替換原始的精確值［10］。在泛化操作中，數(shù)值型準(zhǔn)標(biāo)識符往往被泛化成一個區(qū)間，例如年齡17 可以被泛化成（15，20］；而類別型準(zhǔn)標(biāo)識符則需要定義泛化層級關(guān)系樹，樹的葉子節(jié)點是原始值，越往上層值的泛化程度越大。職業(yè)的泛化層級樹如圖1 所示。抑制（suppression）是程度最高的泛化，指使用特定符號（例如*，&等）來代替原始值，使原始值失效。

圖1 職業(yè)的泛化層級關(guān)系樹Fig.1 Generalized hierarchical tree of occupation

由于基于泛化的k-匿名算法更適合運用于類別型準(zhǔn)標(biāo)識符，對于數(shù)值型準(zhǔn)標(biāo)識符會丟失更多的語義［11］，一些研究便將SDC（Statistical Disclosure Control）中的微聚合技術(shù)運用到匿名化算法中［12］。微聚合的主要思想是給定一個參數(shù)k，然后將數(shù)據(jù)集劃分成多個組，每個組至少包含k條記錄，組內(nèi)記錄最大程度的相似，而組間記錄最大程度的不同。最后每個組內(nèi)原始的準(zhǔn)標(biāo)識符值會被替換成所在組的準(zhǔn)標(biāo)識符質(zhì)心［13］。因此，每條記錄會與k-1 條記錄相似，滿足了k-匿名模型要求。

2 評估模型研究現(xiàn)狀

k-匿名算法在保證數(shù)據(jù)集安全發(fā)布的同時，會不可避免地導(dǎo)致數(shù)據(jù)可用性降低。根據(jù)可用性指導(dǎo)匿名化過程，得出可用性最高的匿名化數(shù)據(jù)集（即最優(yōu)匿名數(shù)據(jù)集），研究人員提出了評估數(shù)據(jù)可用性模型［14-15］。在可用性模型中，數(shù)據(jù)集的信息損失等于所有加權(quán)后的準(zhǔn)標(biāo)識符信息損失之和。這里的權(quán)重是指準(zhǔn)標(biāo)識符的可用性權(quán)重，權(quán)重越大，該準(zhǔn)標(biāo)識符在匿名化時被泛化程度越低。

目前，可用性權(quán)重的設(shè)定方式主要分為三類：一類是假設(shè)所有準(zhǔn)標(biāo)識符的可用性權(quán)重相等，如文獻［16］提出的評估模型Loss，顯然這種方式并不符合使用數(shù)據(jù)時的實際情況；另一類是由使用數(shù)據(jù)的人指定，如文獻［17］提出評估模型UC，這類方式很大程度上依賴于操作者的個人能力，且不具有普遍適用性；最后一類是依靠特定指標(biāo)自動計算出權(quán)重因子，如文獻［18］提出的Entropy Loss 模型，首先計算出準(zhǔn)標(biāo)識符的信息熵，然后將信息熵標(biāo)準(zhǔn)化之后作為可用性權(quán)重。但是信息熵僅描述了屬性所包含的信息量，并不能反映屬性在后續(xù)挖掘中的重要程度，有些信息熵低的屬性反而更應(yīng)該被較低程度泛化。例如性別，雖然信息熵低，但是在分析一個人的興趣愛好時卻十分重要。

上述評估模型中可用性權(quán)重的設(shè)置方式均存在缺陷，直接影響了k-匿名算法選取最優(yōu)解。為此，本文提出使用互信息計算可用性權(quán)重的互信息損失評估模型。該模型可適用于PPDM 研究，指導(dǎo)k-匿名算法在后續(xù)分類問題中選擇出可用性更高的匿名數(shù)據(jù)集。

3 MI Loss 模型

MI Loss 評估模型通過準(zhǔn)標(biāo)識符和標(biāo)簽之間的互信息計算可用性權(quán)重，利用Loss 公式計算各個準(zhǔn)標(biāo)識符的信息損失，最后將所有加權(quán)后的準(zhǔn)標(biāo)識符信息損失之和作為數(shù)據(jù)集的信息損失。

3.1 MI Loss 評估模型

互信息通常被用來描述兩個變量之間的相關(guān)性，若兩個變量之間不存在相關(guān)性，則它們的互信息為零，否則它們的互信息大于零。通過計算數(shù)據(jù)集中每個準(zhǔn)標(biāo)識符與標(biāo)簽的互信息，可以判斷出它們與標(biāo)簽的相關(guān)性大?。?9］。若相關(guān)性大，則說明該準(zhǔn)標(biāo)識符應(yīng)該被較低程度泛化，以保留其后續(xù)在數(shù)據(jù)挖掘中的可用性。因此，相較于信息熵，互信息反映了準(zhǔn)標(biāo)識符對標(biāo)簽信息量的影響，更適合作為k-匿名過程中計算準(zhǔn)標(biāo)識符的可用性權(quán)重指標(biāo)。

利用互信息計算準(zhǔn)標(biāo)識符的可用性權(quán)重方法如下：首先計算出每個準(zhǔn)標(biāo)識符與標(biāo)簽之間的互信息，然后將所有互信息值標(biāo)準(zhǔn)化得到權(quán)重。如式（1）所示，假設(shè)在數(shù)據(jù)集D中，準(zhǔn)標(biāo)識符的個數(shù)為q，依次表示為X1,X2,…,Xq，標(biāo)簽表示為Y，將式（2）、式（3）代入式（1）計算出準(zhǔn)標(biāo)識符Xi與標(biāo)簽Y之間的互信息MI(Y,Xi)，最后通過標(biāo)準(zhǔn)化式（4）得到準(zhǔn)標(biāo)識符Xi的可用性權(quán)重wi。

在匿名化的過程中，準(zhǔn)標(biāo)識符的原始值會被替換為經(jīng)過泛化的值，MI Loss 評估模型使用文獻［16］提出的信息損失公式Loss 來估計準(zhǔn)標(biāo)識符的信息損失Loss(Xi)。Loss 公式用一個值被泛化后的區(qū)間度量除以其泛化前的區(qū)間度量作為該值的信息損失。對于數(shù)值型屬性，區(qū)間度量為泛化區(qū)間最大值和最小值之差，對于類別型屬性，區(qū)間度量為泛化層級關(guān)系樹的同層節(jié)點數(shù)目。

根據(jù)所有準(zhǔn)標(biāo)識符Xi的信息損失Loss(Xi)和其相應(yīng)的可用性權(quán)重wi，MI Loss 模型計算數(shù)據(jù)集D的信息損失公式如下：

式（5）可用于指導(dǎo)k-匿名算法尋找最優(yōu)解。

3.2 基于MI Loss 模型的k-匿名算法

基于MI Loss 模型的k-匿名算法流程如圖2 所示。在搜索階段，依據(jù)一定規(guī)則轉(zhuǎn)化原始數(shù)據(jù)，并將所有滿足k-匿名模型的數(shù)據(jù)集加入解空間。建立解空間后，根據(jù)MI Loss 評估模型計算每個解的信息損失，最后從中選出信息損失最低的一個匿名數(shù)據(jù)集作為最優(yōu)解輸出。若原始數(shù)據(jù)集體積過大，維數(shù)過多，則搜索階段可能會遭遇維數(shù)災(zāi)難［20］，這時要依靠MI Loss 模型計算當(dāng)前數(shù)據(jù)集的信息損失來剪枝，達到降低計算量及優(yōu)化算法性能的目的。

圖2 基于MI Loss 模型的k-匿名算法流程Fig.2 Procedure of k-anonymity algorithm based on MI Loss model

4 實驗評估

4.1 實驗?zāi)康募安襟E

為證明在PPDM 的研究中利用MI Loss 評估模型指導(dǎo)k-匿名算法得到的最優(yōu)匿名數(shù)據(jù)集能有更好的分類表現(xiàn)，本文將其與Loss 模型［16］和Entropy Loss模型［18］進行了對比。比較3 種模型選擇出的最優(yōu)匿名數(shù)據(jù)集在分類問題中的準(zhǔn)確率，分類準(zhǔn)確率越高則說明對應(yīng)的匿名數(shù)據(jù)集在分類方面的可用性降低越少［21］。

本文實驗中使用的數(shù)據(jù)集是UCI Machine Learning Repository 中的Adult 數(shù)據(jù)集，Adult 數(shù)據(jù)集經(jīng)常被用來研究二分類問題和隱私保護機制，通過一個人的年齡、受教育年限、性別等屬性預(yù)測其薪資是否超過50K，該數(shù)據(jù)集中包含了14 個特征和1 個標(biāo)簽。為最大程度地模擬真實環(huán)境，保證數(shù)據(jù)安全，實驗從14 個特征中選出11 個作為準(zhǔn)標(biāo)識符，準(zhǔn)標(biāo)識符的具體描述如表1 所示。

表1 Adult 數(shù)據(jù)集中的準(zhǔn)標(biāo)識符Table 1 Quasi-identifiers in Adult dataset

本文在安裝了JDK 11.0.7 的Windows10 環(huán)境中進行了實驗，使用開源的匿名化軟件ARX3.8.0［22］對數(shù)據(jù)匿名化，該工具可以由用戶自定義匿名化模型、數(shù)據(jù)轉(zhuǎn)化規(guī)則以及評估數(shù)據(jù)可用性的模型。

本文實驗步驟如下：

步驟1預(yù)定義匿名化模型及規(guī)則。在ARX 中設(shè)置匿名數(shù)據(jù)集須滿足的匿名模型為k-匿名，k分別取2、3、5、10，并且針對不同類型的數(shù)據(jù)設(shè)置了相應(yīng)的數(shù)據(jù)轉(zhuǎn)化規(guī)則和泛化層級關(guān)系。數(shù)值型準(zhǔn)標(biāo)識符的原始值會被轉(zhuǎn)化為泛化區(qū)間端點的算術(shù)平均值；類別型準(zhǔn)標(biāo)識符則會根據(jù)預(yù)定義的泛化層級關(guān)系樹來轉(zhuǎn)化。

步驟2搜索所有解，建立解空間。ARX 會對所有準(zhǔn)標(biāo)識符按照泛化層級關(guān)系自底向上逐級泛化，每遇到一個滿足k-匿名的匿名數(shù)據(jù)集就將其加入解空間，直至滿足搜索終止條件。

步驟3使用3 種評估模型分別對解空間中的匿名數(shù)據(jù)集進行評估。Loss 模型、Entropy Loss 模型和MI Loss 模型中準(zhǔn)標(biāo)識符的可用性權(quán)重如表2所示。

表2 3 種評估模型中屬性的可用性權(quán)重Table 2 Utility weights of attributes in three evaluation models

3種模型利用不同的權(quán)重通過式（5）計算數(shù)據(jù)集的信息損失，最后從所有滿足k-匿名模型的數(shù)據(jù)集中搜索出信息損失最低的一個作為該模型得到的最優(yōu)匿名數(shù)據(jù)集輸出。

步驟4當(dāng)k取不同值時，用3種模型得到的最優(yōu)解分別訓(xùn)練分類器，并比較分類器的分類準(zhǔn)確率。分類準(zhǔn)確率越高，說明對應(yīng)的匿名數(shù)據(jù)集在分類問題中的信息損失越低，相應(yīng)的可用性評估模型也越能有效地指導(dǎo)k-匿名算法選擇出最優(yōu)解。

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

使用線性回歸在3種模型選擇出的最優(yōu)匿名數(shù)據(jù)集上分別訓(xùn)練分類器，并采用三折交叉驗證計算分類器的準(zhǔn)確率，結(jié)果如圖3 所示。當(dāng)k=0 時，即為原始數(shù)據(jù)集，數(shù)據(jù)沒有形變，因此訓(xùn)練出的分類器的分類準(zhǔn)確率最高為89.23%，這也是所有分類器準(zhǔn)確率的上界。隨著k值的增加，滿足k-匿名模型的難度也隨之增大，數(shù)據(jù)的形變程度加大，因此分類器的表現(xiàn)都隨著數(shù)據(jù)可用性的降低有所下降，但不論k取何值，用MI Loss 評估模型選擇得到的最優(yōu)解訓(xùn)練出的分類器分類準(zhǔn)確率始終最高，比使用其他兩種模型高0.73%～3.00%，而且隨著k值的增加，MI Loss 模型的優(yōu)勢愈加明顯。這說明在k-匿名算法中，用MI Loss 模型指導(dǎo)匿名化過程并選擇最優(yōu)解，能顯著降低最優(yōu)匿名數(shù)據(jù)集在分類問題中的可用性丟失，從而取得更高的分類準(zhǔn)確率。

圖3 3 種模型的分類器準(zhǔn)確率Fig.3 Classification accuracy of three models

5 結(jié)束語

本文分析了隱私保護數(shù)據(jù)挖掘研究中k-匿名算法所采用的數(shù)據(jù)可用性評估模型在可用性權(quán)重設(shè)置上的缺陷，提出一種使用互信息計算權(quán)重的MI Loss評估模型。該模型將準(zhǔn)標(biāo)識符和標(biāo)簽之間的互信息標(biāo)準(zhǔn)化后作為權(quán)重，并與Loss 模型、Entropy Loss 模型進行對比。實驗結(jié)果表明，MI Loss 模型選擇出的最優(yōu)解在分類問題中有更高的可用性，分類準(zhǔn)確率優(yōu)于另外兩種模型。本文僅對MI Loss 模型選擇出的最優(yōu)解在分類問題中的表現(xiàn)進行了實驗分析，下一步將研究該模型在回歸問題中的可用性。