PPDM 中面向k-匿名的MI Loss 評估模型

谷青竹，董紅斌

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

0 概述

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

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

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

1 匿名化

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

1.1 k-匿名模型

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

1.2 k-匿名算法

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

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

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

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

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

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

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

3 MI Loss 模型

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

3.1 MI Loss 評估模型

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

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

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

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

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

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

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

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

4 實驗評估

4.1 實驗目的及步驟

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

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

表1 Adult 數(shù)據(jù)集中的準標識符Table 1 Quasi-identifiers in Adult dataset

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

本文實驗步驟如下：

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

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

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

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

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

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

4.2 實驗結果與分析

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

圖3 3 種模型的分類器準確率Fig.3 Classification accuracy of three models

5 結束語

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