混合式的K-匿名特征選擇算法

楊 柳，李 云*

（1.江蘇省大數(shù)據(jù)安全與智能處理重點實驗室（南京郵電大學），南京 210023；2.南京郵電大學計算機學院、軟件學院、網(wǎng)絡(luò)空間安全學院，南京 210023）

（?通信作者電子郵箱liyun@njupt.edu.cn）

0 引言

大數(shù)據(jù)時代，隨著數(shù)據(jù)分析技術(shù)的發(fā)展和各種各樣數(shù)據(jù)挖掘算法的提出，數(shù)據(jù)的共享和傳播更加頻繁。越來越多的研究機構(gòu)和商業(yè)公司會在大數(shù)據(jù)中提取想要的信息并挖掘數(shù)據(jù)帶來的價值，但隨著數(shù)據(jù)的發(fā)布，隨之而來的就是數(shù)據(jù)中的用戶隱私泄露問題。近年來，不適當?shù)臄?shù)據(jù)共享造成的隱私泄露事件頻發(fā)，例如Facebook 與數(shù)據(jù)分析公司Cambridge Analytica 的不當共享造成了8 700 萬用戶個人信息泄露［1］、NetFlex的推薦比賽中用戶觀影記錄泄露［2］。除了數(shù)據(jù)共享引起的隱私泄露，還有許多惡意的攻擊者會通過不同數(shù)據(jù)集之間的鏈接攻擊來推斷用戶的敏感信息［3］。例如數(shù)據(jù)的發(fā)布者一般會刪除用戶個體的姓名標識符，然而攻擊者還是可以通過比較不同數(shù)據(jù)集的郵編、年齡、籍貫等準標識符信息來獲取用戶的隱私信息［4］，因此關(guān)于隱私保護的研究逐漸受到廣泛關(guān)注，其中數(shù)據(jù)匿名化方法是隱私保護領(lǐng)域非常流行的一類方法。數(shù)據(jù)匿名化技術(shù)采用不同匿名策略對數(shù)據(jù)進行壓縮或者抽象，并保證隱私不被泄露的同時，又使得數(shù)據(jù)可用性最大化［5］。

K-匿名技術(shù)是最常用的數(shù)據(jù)匿名化技術(shù)之一。1998 年，Samarati等［6］首次提出K-匿名的概念，要求數(shù)據(jù)中需存在一定數(shù)量不可區(qū)分的個體，從而使攻擊者無法輕易判斷具體個體的隱私信息。2002年，Sweeney［7］正式提出了K-匿名隱私保護模型，將發(fā)布數(shù)據(jù)劃分成多個等價類且使每個等價類中至少有k個元組在準標識符屬性上相同，使攻擊者不能判別隱私信息所屬的個體。K-匿名模型自提出以來一直受到廣泛關(guān)注，在隱私保護領(lǐng)域取得了很好的效果，Iyengar［8］基于遺傳算法考慮隱私保護與數(shù)據(jù)信息損失的權(quán)衡，解決K-匿名在數(shù)據(jù)挖掘中的分類問題；Machanavajjhala 等［9］在K-匿名模型基礎(chǔ)上提出l-多樣性算法，保留數(shù)據(jù)更多的信息；Xiao等［10］在2006年的SIGMOD 會議上提出的基于人性化匿名的新泛化框架，實現(xiàn)了滿足個體需求的最小泛化，從而保留了更多數(shù)據(jù)信息。

K-匿名模型需要將數(shù)據(jù)部分屬性通過泛化或隱藏等方式匿名化，這樣得到的數(shù)據(jù)雖然滿足K匿名隱私保護的條件，但忽視了數(shù)據(jù)在分類模型上的分類性能。實現(xiàn)K-匿名常用的隱藏特征的操作往往只考慮了操作后數(shù)據(jù)的隱私性而沒有考慮數(shù)據(jù)在分類任務(wù)中的可用性和有效性，而這類操作可以視為一種以保護隱私為目的的特征選擇方法［11］。特征選擇方法作為機器學習與數(shù)據(jù)挖掘領(lǐng)域經(jīng)典的數(shù)據(jù)預(yù)處理方法，可以通過特定的評價標準獲得，可有效保證數(shù)據(jù)分類性能的特征子集從而受到了廣泛研究［12］。如果使用特征選擇剔除特征、挑選特征的方式來實現(xiàn)數(shù)據(jù)的K-匿名，從而既保證數(shù)據(jù)的隱私性又保證數(shù)據(jù)的分類性能，這類特征選擇方法可以統(tǒng)稱為K-匿名特征選擇方法。然而國內(nèi)外對K-匿名特征選擇的研究相對較少。一些研究者結(jié)合特征選擇的思想，采用“多維抑制”的方式在隱私保護數(shù)據(jù)挖掘任務(wù)中實現(xiàn)了K-匿名模型［13-14］；Zhang等［15］將K-匿名隱私保護作為特征選擇的約束條件，提出了一種用于隱私保護的特征選擇方法，使特征選擇后的數(shù)據(jù)滿足K-匿名條件；王旭等［16］使用XGBoost（Extreme Gradient Boosting）對特征進行重要性排序，按照特征重要程度的順序逐個判斷K-匿名條件，選出滿足K-匿名的特征子集?？梢奒-匿名特征選擇從實現(xiàn)K-匿名的一種技巧已經(jīng)演變?yōu)橐活愲[私保護特征選擇方法。

已知的K-匿名特征選擇方法大多是過濾式方法，在特征選擇領(lǐng)域，過濾式方法以便捷、高效、不依賴于特定分類器、可解釋性好等優(yōu)點得到廣泛研究，文獻［15］與文獻［16］提出的算法對單個特征按照特征重要性進行排序，從特征排序中選取當前最重要的特征開始搜索K-匿名特征子集。因為每個特征并不是獨立地對分類器輸出結(jié)果產(chǎn)生作用［17］，這種搜索策略沒辦法保證最終選擇的特征子集在分類性能和隱私保護之間達到很好的平衡。過濾式方法獨立于分類算法，對分類器的分類性能影響有限，而另外一種特征選擇形式是封裝式特征選擇方法，根據(jù)后續(xù)模型的性能來評價特征子集的優(yōu)劣，時間成本較大。

針對過濾式方法獨立于分類器的限制與封裝式搜索成本高等問題，本文結(jié)合過濾式與封裝式的特點，設(shè)計了一種混合式K-匿名特征選擇算法HKFS，基于前向搜索策略和K-匿名條件產(chǎn)生更多的K-匿名特征候選子集，再根據(jù)分類器分類性能選出最優(yōu)子集。

1 背景知識

1.1 基本定義

二維表是發(fā)布信息的主要形式，為了方便討論，本文主要研究這類表格數(shù)據(jù)。假設(shè)T={t1，t2，…，tn}是一個待發(fā)布的數(shù)據(jù)表，數(shù)據(jù)的行項包含n個元組，也叫記錄，列項稱為屬性。

定義1屬性。屬性是表格數(shù)據(jù)的列項，根據(jù)屬性的特性，所有屬性可以分為四類：

1）顯標識符ID（IDentifier）：顯標識符能標識個體的身份，唯一確定一條元組（即用戶記錄），為保護用戶隱私顯標識符一般都需要刪除，例如用戶的姓名。

2）準標識符QI（Quasi-Identifier）：準標識符屬性聯(lián)合起來可以以較大概率確定一條元組，一般需要做匿名化處理，例如用戶的年齡、性別。

3）敏感屬性SA（Sensitive Attribute）：敏感屬性是需要保護的屬性，包含個體的隱私信息，沒有關(guān)聯(lián)到個體時不會泄露隱私，例如患病情況、收入，不同個體對隱私定義不同，敏感屬性的選擇也可能不同。

4）其他屬性：不屬于上面三類，不需要做特殊處理。

對于表格T={t1，t2，…，tn}，用d來表示準標識符的數(shù)量，n表示用戶記錄的數(shù)量，Ai表示第i個準標識符屬性，As表示敏感屬性，tj表示表中第j條記錄。

定義2等價類（Equivalence class）。在準標識符屬性A1，A2，…，Ad上，具有完全相同取值的若干條記錄組成一個等價類。

定義3K-匿名（K-anonymity）。如果數(shù)據(jù)表T中的任意記錄t，都能找到至少k-1 條記錄與t在準標識符上無法區(qū)分，則稱該數(shù)據(jù)表T滿足K-匿名。

K-匿名模型常用于抵御鏈接攻擊，要求對匿名處理后的數(shù)據(jù)表中的每條記錄，都應(yīng)至少有k-1條記錄在準標識符上的取值相同，使得觀察者無法以高于1/k的置信度通過準標識符來識別用戶。k值的大小決定了隱私保護的程度，k越大等價類中記錄數(shù)目越多，越不易確定用戶，隱私泄露的風險越低。

定義4泛化與隱藏（Generalization and Suppression）。泛化與隱藏是K-匿名模型處理數(shù)據(jù)的兩種主要手段。泛化是把數(shù)據(jù)泛化到一個更大的區(qū)間，比如年齡18 可以泛化到（15，20］，這樣年齡分別為18 和20 的兩個用戶在年齡這一屬性下的取值就是相同的；隱藏，也叫隱匿、抑制，可以針對一些難以泛化或者不能公開的屬性進行隱匿或刪除操作，例如個體的姓名。

1.2 K-匿名特征選擇

一般情況下，數(shù)據(jù)中的等價類大部分都不滿足K-匿名。為了達到數(shù)據(jù)匿名化的目的，需要通過泛化與隱藏等手段對原始數(shù)據(jù)進行轉(zhuǎn)化，以達到數(shù)據(jù)K-匿名模型保護隱私的要求。如表1 所示，表格數(shù)據(jù)清楚表達了用戶的各項信息，其中病人的病情就是敏感屬性。在沒有數(shù)據(jù)匿名化的情況下，只需要一點信息就可以準確定位到某個用戶并了解他/她的隱私信息，例如知道這個表格中某病人是27 歲就能知道該病人患的是癌癥。

通過簡單的匿名化泛化手段，表1 變成表2 的形式，表2中所有用戶分為了3 個等價類，最小的等價類數(shù)目為2，所以這是一個2-匿名表格。

表1 病人數(shù)據(jù)Tab.1 Data of patients

表2 病人數(shù)據(jù)匿名化Tab.2 Anonymization of patient data

如表3 是一個只包含0 或1 的二值化數(shù)據(jù)表格，{X1，X2，X3，X4，X5}是準標識屬性，Y是敏感屬性，不滿足K-匿名條件，如果隱藏屬性{X4，X5}，保留{X1，X2，X3}，即可使得數(shù)據(jù)達成2-匿名，這一操作相當于對數(shù)據(jù)進行特征選擇，把使得數(shù)據(jù)達成K-匿名條件的一系列特征選擇方法統(tǒng)稱為K-匿名特征選擇方法，所以K-匿名特征選擇可以歸類為K-匿名模型兩大主要手段之一的隱藏操作。

表3 2-匿名特征選擇Tab.3 Two-anonymous feature selection

文獻［15］中將K-匿名條件作為特征選擇的約束條件，平衡數(shù)據(jù)的分類性能與隱私保護能力。如表3 所示，除了特征子集{X1，X2，X3}，特征子集{X3，X4，X5}也可以使表3數(shù)據(jù)達成2-匿名，然而使用不同的特征子集，降維后的數(shù)據(jù)在模型中的分類表現(xiàn)也不同，選擇既具有隱私保護能力又能保證數(shù)據(jù)分類性能的K-匿名特征子集是K-匿名特征選擇問題的關(guān)鍵任務(wù)。借鑒文獻［15］中的概念將本文的K-匿名特征選擇問題形式化描述為：

其中：DS表示數(shù)據(jù)D在特征子集S上映射的數(shù)據(jù)；f是衡量特征子集分類性能的函數(shù)；EC()表示數(shù)據(jù)中等價類包含的記錄數(shù)目；k是K-匿名模型的k值。

2 混合式K-匿名特征選擇算法

本章主要介紹本文提出的混合式K-匿名特征選擇算法HKFS。

2.1 過濾式評價準則

1）特征重要性排序：為了保證候選子集具有一定的分類性能并減少最優(yōu)特征子集的搜索空間，本文對預(yù)處理后的數(shù)據(jù)使用XGBoost 計算每個特征的重要性程度，并按照重要性從大到小的順序?qū)λ刑卣鬟M行排序［18］。

2）K-匿名條件：本文將K-匿名條件作為特征選擇的一種評價準則。假設(shè)數(shù)據(jù)T是d維數(shù)據(jù)，特征子集s(||s≤d)，數(shù)據(jù)T按照特征子集s進行特征選擇，保留s中的特征，刪除其他特征，如果特征選擇之后的數(shù)據(jù)T含有q個不同的等價類，且每個等價類包含的樣本數(shù)量都不小于給定的閾值k，則這個特征子集滿足K-匿名條件。因為獨立于分類器，只考慮數(shù)據(jù)內(nèi)部關(guān)系，所以K-匿名條件是一種典型的過濾式特征評價準則。

2.2 生成候選子集

如算法1（過濾式模塊）所示，它的輸入數(shù)據(jù)D只含有準標識符屬性，不包含敏感屬性，原始數(shù)據(jù)D在數(shù)據(jù)預(yù)處理階段進行泛化操作，將數(shù)據(jù)二值化，在經(jīng)過特征排序后，再將預(yù)處理過的數(shù)據(jù)送入K-匿名判別模塊。

算法2 是K-匿名判別模塊K-test，第2）～9）行找出所有等價類，并記錄它們的長度，存入字典record；第10）～14）行判斷每個等價類的長度，即字典record 存入的每個值大小，只要有一個值小于k，就表明這個數(shù)據(jù)D′不滿足K-匿名。在判別K匿名條件時，第一輪從當前最重要特征開始搜索到最后一個特征，第二輪從次重要特征開始搜索到最后一個特征……以此類推。每輪初始化一個空特征子集，依次把每輪搜索到的每個特征放入候選子集，在K-匿名判別模塊里判斷此時數(shù)據(jù)是否符合K-匿名條件。如果加入該特征使得數(shù)據(jù)具有K-匿名性，則將該特征留在候選子集中，否則剔除出候選子集，這種方法可以保證最終輸出所有候選子集都是滿足K-匿名隱私保護條件的K-匿名特征子集。

算法1 過濾式模塊。

算法2 K-test。

2.3 獲取最優(yōu)子集

在2.2 節(jié)中得到了若干個K-匿名特征候選子集，這些候選子集映射數(shù)據(jù)即匿名化后的數(shù)據(jù)都滿足K-匿名條件，具有隱私保護能力。需要在所有K-匿名候選子集中選擇一個最優(yōu)子集，本文將每個候選子集映射數(shù)據(jù)按照3∶7 的比例分為測試集與訓(xùn)練集，在每個訓(xùn)練集上都訓(xùn)練一個分類器，最后把分類準確率最高的特征子集作為特征選擇結(jié)果。本文在這一環(huán)節(jié)設(shè)計了一個封裝式模塊來選擇最優(yōu)子集，具體偽代碼如算法3 所示，其中評價函數(shù)J就是封裝在算法內(nèi)部的分類器，用于評價特征子集的分類準確率。

算法3 封裝式模塊。

3 實驗與結(jié)果

通過多項實驗來驗證本文所提出的混合式K-匿名特征選擇算法HKFS的性能。

3.1 數(shù)據(jù)預(yù)處理

本文在UCI 機器學習數(shù)據(jù)庫中選擇了6 個真實數(shù)據(jù)集［19］，分別是隱私保護領(lǐng)域常用的成人數(shù)據(jù)集Adult、垃圾郵件分類數(shù)據(jù)集Spambase，以及與人類疾病相關(guān)的乳腺癌數(shù)據(jù)集Breast Cancer、心臟病數(shù)據(jù)集Heart Disease、糖尿病數(shù)據(jù)集Pima Indians Diabetes 和肝炎病毒數(shù)據(jù)集HCV，每個數(shù)據(jù)集的樣本數(shù)量與特征數(shù)見表4。

表4 數(shù)據(jù)集屬性Tab.4 Attributes of datasets

按照K-匿名隱私保護的實現(xiàn)步驟，把K-匿名特征選擇也分為泛化和隱藏兩個階段。泛化階段作為第一個階段，在數(shù)據(jù)預(yù)處理步驟中完成，將數(shù)據(jù)泛化到不同區(qū)間，以原有特征值不同的區(qū)間作為新的特征，新的特征值取0 或1，從而使得數(shù)據(jù)0-1 二值化，并具有初步的保護數(shù)據(jù)隱私的效果，也方便接下來的K-匿名特征選擇或隱藏操作。以隱私保護領(lǐng)域最常用的成人數(shù)據(jù)集Adult 為例，將Adult 數(shù)據(jù)集按照正負類原始比例隨機抽5 000 條樣本進行實驗，正類為年收入大于5 萬的用戶記錄，負類為年收入小于等于5 萬的用戶記錄。原始特征包括6 個連續(xù)特征如年齡、教育程度等，以及8 個離散特征如性別、職業(yè)、婚姻狀況等。將連續(xù)特征進行OneHot編碼，與離散化特征一起泛化，根據(jù)不同泛化范圍，將數(shù)據(jù)進行0-1 二值化，例如年齡值泛化到（0，20］、（20，40］、（40，60］、（60，80］、（80，∞）。

3.2 實驗設(shè)置

為了驗證本文算法HKFS 的有效性，選擇了最新的K-匿名特征選擇算法XGB-KA［16］作為對比方法，為了清楚表達本文算法的優(yōu)勢，把XGB-KA 作為過濾式對比方法（Filter method），把基于本文算法同樣搜索策略但沒有進行過濾式特征排序的方法作為封裝式對比方法（Wrapper method）：

1）Filter method（過濾式K-匿名特征選擇算法XGB-KA）：計算特征重要性分數(shù)并根據(jù)特征重要性程度由大到小進行排序，按順序判斷特征子集是否滿足K-匿名條件選擇K-匿名特征子集。

2）Wrapper method：所有特征不進行過濾式排序，按照自然順序依次判斷K-匿名條件，采用與本文HKFS 算法相同的搜索策略選擇多個候選子集，最后從中選擇出分類性能最優(yōu)的特征子集。

首先對數(shù)據(jù)進行數(shù)據(jù)預(yù)處理，經(jīng)過3.1 節(jié)中數(shù)據(jù)預(yù)處理與泛化操作之后，數(shù)據(jù)已具有初步的隱私性。然后使用K-匿名特征選擇方法對預(yù)處理過的數(shù)據(jù)進行特征選擇，即隱藏操作，從而得到K-匿名特征子集與匿名化的數(shù)據(jù)集，選用線性支持向量機（Support Vector Machine，SVM）作為分類器，采用十折交叉驗證（10-fold cross-validation）來測試分類準確率Acc（Accuracy），結(jié)果的平均值作為分類器分類性能的估計。準確率的計算公式如下：

其中：TP是正確分為正類的樣本數(shù)，TN是正確分為負類的樣本數(shù)，F(xiàn)P是錯誤地分為正類的樣本數(shù)，F(xiàn)N是錯誤地分為負類的樣本數(shù)。

由于本文提出的HKFS 算法目的是權(quán)衡數(shù)據(jù)的隱私保護能力與分類性能，K-匿名特征選擇算法既可以作為一種數(shù)據(jù)預(yù)處理方法也可以作為一種隱私保護K-匿名化算法，所以選用K-匿名算法經(jīng)典度量指標［20］——平均等價類大?。–AVG）。CAVG指標基于K-匿名化以后的等價類的大小來衡量數(shù)據(jù)的匿名化程度，如果所有等價組中平均包含的樣本數(shù)量越接近k值則表明信息損失度越低，匿名化質(zhì)量越高。計算公式如下：

其中：Total_records表示整個數(shù)據(jù)的記錄條數(shù)（或數(shù)據(jù)集的樣本總數(shù)量）；Total_equivalence_classes表示匿名化以后等價類的個數(shù)。

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

實驗環(huán)境：AMD Ryzen5-4600H @3.00 GHz CPU；16 GB內(nèi)存；Windows 10（64 位）操作系統(tǒng)；實驗代碼基于Python 3.8實現(xiàn)。對本文的HKFS算法進行了兩組實驗：1）在6個數(shù)據(jù)集上比較不同k值情況下各個特征選擇算法的分類性能；2）比較不同數(shù)據(jù)集下，本文算法與其他算法不同k值情況下平均等價類大小度量指標的差異。

3.3.1 不同算法在各數(shù)據(jù)集下的分類準確率

在K-匿名隱私保護模型中，k值越大表示等價類包含的樣本數(shù)目越多，也就意味著數(shù)據(jù)發(fā)布時具備的隱私性更高。由圖1可以看到，三種特征選擇算法的分類性能都會受k值的大小影響，在大多數(shù)情況下特征選擇分類性能都會隨著k值的增大而下降，因為k值增大需要等價類包含的樣本數(shù)量更多，隨著k值的逐漸增大，達到K-匿名的條件也越來越苛刻，三種K-匿名特征選擇算法即使都會平衡數(shù)據(jù)分類性能與隱私保護能力，也無法避免在一些數(shù)據(jù)集上因為k值增大而引起的分類性能下降。在大多數(shù)情況下，如圖1（a）、（c）、（d）、（f），只要數(shù)據(jù)開始匿名化(k＞1)分類性能都會下降，而本文的HKFS 算法在多數(shù)數(shù)據(jù)集上都要好于過濾式方法與封裝式方法，可以更好地平衡數(shù)據(jù)隱私保護能力與分類性能。

圖1 三種特征選擇算法分類準確率比較Fig.1 Comparison of classification accuracy of three feature selection algorithms

如實驗結(jié)果圖1（b）、（e）所示，在數(shù)據(jù)集Adult 與Pima Indians Diabetes上，HKFS的分類準確率與Filter method（XGBKA）在分類性能上幾乎相同，這是因為：1）XGB-KA 作為過濾式特征選擇方法對特征排序后，每次將最重要的特征選入最終的特征子集，在很多數(shù)據(jù)集（尤其是小樣本數(shù)據(jù)）中對分類結(jié)果影響最大的就是特征排序后最重要的第一個特征；2）本文HKFS算法選用與XGB-KA相同的特征重要性計算方法，采用了相同的特征排序，在第一個特征起決定性作用的數(shù)據(jù)集上，會產(chǎn)生相同或相類似的結(jié)果。同樣在所有數(shù)據(jù)集上，封裝式方法Wrapper method 表現(xiàn)都較差，并且在實現(xiàn)匿名化以后結(jié)果十分穩(wěn)定，也與特征排序有關(guān)，因為Wrapper method 采用自然特征排序，而搜索策略的搜索空間有限，最終得到的特征子集效果會比較差。

3.3.2 數(shù)據(jù)匿名化質(zhì)量評價

本文提出的HKFS 算法既可以作為一種特征選擇數(shù)據(jù)降維方法，也可以作為一種K-匿名隱私保護算法模型。K-匿名模型是為了數(shù)據(jù)匿名化以后每個等價類中包含的記錄數(shù)目至少為k，而為了數(shù)據(jù)質(zhì)量與匿名化數(shù)據(jù)信息可用性，理想狀態(tài)下希望每個等價類包含的記錄數(shù)目都盡可能接近k。所以，CAVG越小越好。在6個UCI數(shù)據(jù)集上進行實驗，將性能較好的過濾式K-匿名特征選擇算法XGB-KA 作為Baseline 與本文HKFS算法在CAVG指標上作對比，結(jié)果如圖2所示。

圖2 平均等價類大小對比Fig.2 Average equivalence class size comparison

從圖2 可以看出，當k比較小，CAVG值一般會比較大，總體來說CAVG值隨著k值增大而呈減小的趨勢。如圖2（a）、（c）、（d）、（e）、（f）所示，在大多數(shù)情況下，HKFS 算法的CAVG值都要小于Baseline，表示HKFS 算法得到的匿名化數(shù)據(jù)質(zhì)量相對更高。在圖2（b）、（e）上，與3.3.1 節(jié)圖1 結(jié)果類似，HKFS 算法依舊表現(xiàn)與Baseline結(jié)果相同。

4 結(jié)語

本文提出了一種混合式的K-匿名特征選擇算法HKFS，結(jié)合過濾式特征選擇與封裝式特征選擇的特點，把K-匿名判斷條件作為特征選擇的評價標準，將K-匿名特征選擇歸類為K-匿名隱私保護中的隱藏手段。搜索盡可能多的候選子集，使用封裝式分類器評價候選子集分類性能，從而選出高效且具有隱私保護能力的特征子集。本文K-匿名特征選擇算法僅考慮了特征子集分類性能與隱私保護能力的平衡性，未來還可以考慮特征子集的其他性能與隱私保護能力的平衡，設(shè)計更多樣化的隱私保護特征選擇方法。