基于隨機(jī)森林特征重要性的K-匿名特征優(yōu)選

黃 梅 朱 焱

(西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院 四川 成都 611756)

0 引 言

近年來，隨著互聯(lián)網(wǎng)技術(shù)和數(shù)據(jù)存儲(chǔ)技術(shù)的快速發(fā)展，從數(shù)據(jù)中提取隱含的、具有潛在價(jià)值的信息變得更加便捷。數(shù)據(jù)挖掘技術(shù)常用于決策支持和科學(xué)研究，數(shù)據(jù)在擁有者和使用者之間共享屢見不鮮。然而，這些數(shù)據(jù)中可能包含了某些敏感隱私信息，如個(gè)體隱私、政府機(jī)密及商業(yè)情報(bào)等。如果將這些數(shù)據(jù)不加處理的發(fā)布共享，就會(huì)造成隱私信息的泄露。近年來，隨著多起隱私數(shù)據(jù)泄露事件，如NetFlex的推薦比賽中用戶觀影記錄泄露[1]、FaceBook與數(shù)據(jù)分析公司Cambridge Analytica的不當(dāng)共享造成8 700萬用戶個(gè)人信息泄露[2]等，隱私保護(hù)技術(shù)得到極大關(guān)注，成為數(shù)據(jù)挖掘和信息安全領(lǐng)域的研究熱點(diǎn)。

自隱私保護(hù)數(shù)據(jù)挖掘(Privacy Preserving Data Mining，PPDM)作為知識(shí)發(fā)現(xiàn)應(yīng)用領(lǐng)域的一個(gè)核心問題，不斷有學(xué)者對(duì)其進(jìn)行研究，并試圖制定提供隱私保護(hù)的模型，經(jīng)典的包括K-匿名[3]、L-多樣性和T-接近及差分隱私等。其中，K-匿名因其靈活有效，在隱私保護(hù)領(lǐng)域得到廣泛研究。該模型最早由Sweeney等[3]提出，并提出使用MinGen[3]算法來選取最優(yōu)泛化操作，使待發(fā)布數(shù)據(jù)滿足K-匿名原則。韓建民等[5]針對(duì)隱私的敏感度提出了面向敏感值的個(gè)性化(a,K)-匿名隱私保護(hù)模型。這種方法對(duì)低敏感值的敏感屬性使用較低的K-匿名約束，對(duì)高敏感值的敏感屬性則用較高的K值進(jìn)行約束，降低了單敏感屬性因隱私保護(hù)而引起的信息損失。此外，許多研究者通過結(jié)合聚類實(shí)現(xiàn)K-匿名。Li等[6]應(yīng)用聚類思想，依據(jù)合并泛化信息損失量最小原則，每次隨機(jī)選取一個(gè)元組數(shù)小于K的類簇與另一個(gè)類簇進(jìn)行合并，直至所有類簇的元組數(shù)大于等于K。Zhang等[7]提出在K-匿名聚類中應(yīng)用信息熵，先將表數(shù)據(jù)聚類為不同的簇，然后將記錄數(shù)小于1K的簇合并，大于2K的簇拆分，使每個(gè)簇的記錄數(shù)在1K于2K之間，最后再對(duì)每個(gè)簇進(jìn)行泛化。文獻(xiàn)[8]根據(jù)泛化樹層次的類別分別度量元組間和等價(jià)類間的信息損失，按照K值每次選擇一條記錄加入類簇，實(shí)現(xiàn)等價(jià)類的均衡劃分。

K-匿名作為常用的隱私保護(hù)模型，泛化和隱藏是實(shí)現(xiàn)該模型的主要手段。上述方法均是采用泛化，即采用一個(gè)域更廣的新值代替原始具體值，如年齡值24和34都可以泛化到區(qū)間(20,40]。泛化需要預(yù)先制定泛化層次，而不同的泛化層次對(duì)結(jié)果的影響較大。例如年齡24可以泛化到(20,30]，也可以直接泛化到(20,40]。而隱藏一般在確定無法泛化到更高層級(jí)后才使用。比如性別特征取值只有“男”和“女”，沒有更高的域值包含這兩個(gè)值，那么直接從數(shù)據(jù)集中刪除該特征或用“*”代替。不同于以往，文獻(xiàn)[9]提出的Greedy_Hamdist算法，無需預(yù)先制定泛化層次，而是通過隱藏分類性能低的特征使特征子集對(duì)應(yīng)數(shù)據(jù)集滿足K-匿名，擴(kuò)展了K-匿名實(shí)現(xiàn)的新思路。

本文受文獻(xiàn)[9]的啟發(fā)，提出一種基于隨機(jī)森林特征重要性的分類性能度量方法，并結(jié)合K-匿名要求，用于選擇滿足K-匿名的特征子集，具體工作流程如圖1所示。通過在兩個(gè)真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，并與基于Greedy_Hamdist的特征選擇算法比較可知，本文算法更有效地保證了隱私保護(hù)與數(shù)據(jù)挖掘性能之間的平衡，運(yùn)行效率也更優(yōu)。

圖1 工作流程

1 相關(guān)技術(shù)

1.1 K-匿名特征選擇

K-匿名模型常用于抵抗鏈接攻擊，該模型可以消除個(gè)體與敏感隱私信息之間的關(guān)聯(lián)關(guān)系[3]。為方便討論，假定待發(fā)布的數(shù)據(jù)表包含n個(gè)記錄，屬性集合由d個(gè)準(zhǔn)標(biāo)識(shí)屬性和1個(gè)敏感屬性構(gòu)成。設(shè)T=(t1,t2,…,tn)為待發(fā)布的數(shù)據(jù)表，tj(j=1,2,…,n)為表中第j個(gè)元組。記A=(A1,A2,…,Ad)為表中所有準(zhǔn)標(biāo)識(shí)屬性，Ai(i=1,2,…,d)為表中第i個(gè)準(zhǔn)標(biāo)識(shí)屬性，AS為敏感屬性，則數(shù)據(jù)表可以用表1表示。

表1 數(shù)據(jù)表

定義1(等價(jià)類) 在數(shù)據(jù)表中，具有相同A取值的若干記錄組成的集合稱為一個(gè)等價(jià)類，記為Ci，則有?ti,tj∈Cw，有ti[A]=tj[A],i≠j,w∈[1,m]。其中m為等價(jià)類的個(gè)數(shù)。

定義2(K-匿名) 將數(shù)據(jù)表T經(jīng)匿名技術(shù)處理后，劃分為多個(gè)等價(jià)類，每個(gè)等價(jià)類包含至少K條記錄，則稱數(shù)據(jù)表T滿足K-匿名。

可見，K-匿名要求對(duì)數(shù)據(jù)表中任一元組，至少存在K-1個(gè)其他元組，它們?cè)跍?zhǔn)標(biāo)識(shí)屬性上的取值相同，理論上侵犯者最多只有1/K的概率能夠定位出個(gè)體用戶所屬的記錄并獲得敏感屬性，即K值的大小決定了隱私泄露的風(fēng)險(xiǎn)，K值越大，隱私泄露風(fēng)險(xiǎn)越低，反之越高。

假設(shè)表2為待匿名數(shù)據(jù)集，由于每條記錄與其他記錄在準(zhǔn)標(biāo)識(shí)符屬性上不具有相同的特征取值，所以數(shù)據(jù)集不滿足2-匿名。但如果特征集為(A1,A2,A5)時(shí)，即表中灰色部分，數(shù)據(jù)集中的任意一條記錄都存在至少1條其他記錄與其取值相同，滿足2-匿名。

表2 特征選擇實(shí)現(xiàn)2-匿名示例

因此通過特征選擇的方式，可以使數(shù)據(jù)滿足K-匿名以達(dá)到隱私保護(hù)的目的?；谝陨纤枷?，可以使用特征選擇得到合適的特征子集，使對(duì)應(yīng)的數(shù)據(jù)集滿足K-匿名。但是從全部特征中得到最佳匿名特征子集是NP完全問題[13]，表2除了(A1,A2,A5)滿足2-匿名條件外，(A2,A3,A4)也是滿足2-匿名的。不同的特征子集具有不同的分類挖掘性能，為了使?jié)M足K-匿名的特征子集具有較好的分類性能，本文提出使用隨機(jī)森林特征重要性度量特征的分類性能，并采用前向序列搜索策略選擇特征。

1.2 隨機(jī)森林特征重要性

隨機(jī)森林(Radom Forest,RF)是一種基于Bagging的集成分類器，由多棵完全生長的決策樹組成。在分類預(yù)測(cè)中，樣本的類標(biāo)由這些決策樹輸出類標(biāo)的眾數(shù)決定[10]。

(1)

式中：pk表示第k個(gè)類標(biāo)在數(shù)據(jù)中所占比例。|y|表示類標(biāo)取值種類數(shù)。Gini(D)反映了從數(shù)據(jù)集D中抽取兩個(gè)樣本，其類別不一樣的概率。所以，Gini(D)越小，數(shù)據(jù)集D的純度越高。數(shù)據(jù)集D根據(jù)屬性a分裂得到的Gini增益可由下式計(jì)算得到：

(2)

式中:V表示a的取值種類數(shù)，|Dv|則表示第v種取值對(duì)應(yīng)的樣本數(shù)。Gini增益最大化原理就是計(jì)算節(jié)點(diǎn)所有屬性的Gini增益，并選擇Gini增益最大的屬性作為分裂屬性。根據(jù)該原理得到的分裂屬性可以使子節(jié)點(diǎn)數(shù)據(jù)集純度最高，說明該屬性的分類性能最好。分類性能越好的屬性在特征集中越重要，因此特征的重要性可以根據(jù)決策樹節(jié)點(diǎn)的劃分體現(xiàn)。然而，由于隨機(jī)森林的雙重隨機(jī)機(jī)制，僅使用屬性在隨機(jī)森林決策樹中的出現(xiàn)頻率來體現(xiàn)特征重要性不可取，因此為了更準(zhǔn)確地反映出特征的重要性，本文選擇基于OOB data分類正確率的方法度量特征的重要性。假設(shè)RF中有k棵決策樹，則特征a的重要性可由以下步驟得出：

1) 初始時(shí)令k=1，采用自助重采樣生成訓(xùn)練集和袋外數(shù)據(jù)集OOB，在訓(xùn)練集上構(gòu)建決策樹Tk；

2) 基于Tk對(duì)OOB數(shù)據(jù)進(jìn)行預(yù)測(cè)分類，統(tǒng)計(jì)分類正確的樣本數(shù)，記為Rk；

4) 令k=2,3,…,K，重復(fù)步驟1至步驟3；

5) 特征a的重要性可由下式計(jì)算得出：

(3)

2 算法設(shè)計(jì)

為了保證數(shù)據(jù)匿名后還能保持較高的分類性能，本文提出使用選擇隨機(jī)森林度量特征的分類性能，對(duì)原始集的特征進(jìn)行排序，并采用序列前向搜索的貪心策略，進(jìn)行K-匿名特征選擇。初始化特征子集為空，每次選擇分類性最高的特征加入，并判斷數(shù)據(jù)的匿名性，留下滿足K-匿名的特征，否則剔除，直到?jīng)]有特征可加入，最終得到滿足K-匿名的特征子集。具體如算法1所示。

算法1RFKA(D,k)

輸入：數(shù)據(jù)集D，隱私值K

輸出：滿足K-匿名的數(shù)據(jù)集D′

Begin:

1. 構(gòu)建隨機(jī)森林計(jì)算每個(gè)特征的重要性

2. 根據(jù)特征重要性對(duì)特征降序排序，得到F_IMP_List

3. 初始化特征子集sub={}

4. for F_IMP_List中的每個(gè)特征X：

5. sub=sub.append(X)

6.D′=D在sub上的投影數(shù)據(jù)集

7. if privacy_test(D′)：

8. sub=sub.delete(X)

9.D′=D在sub上的投影數(shù)據(jù)集

10. 輸出數(shù)據(jù)集D′

End

注意，數(shù)據(jù)集D只包含準(zhǔn)標(biāo)識(shí)屬性，不包括敏感屬性。算法第7行privacy_test(D′)對(duì)數(shù)據(jù)集D′進(jìn)行了是否違反K-匿名的判斷，判斷條件是根據(jù)K-匿名的定義設(shè)計(jì)的，即任意一條數(shù)據(jù)都至少存在K-1條數(shù)據(jù)與其具有相同的準(zhǔn)標(biāo)識(shí)符。本文中的準(zhǔn)標(biāo)識(shí)符即樣本在特征子集上的取值，所以privacy_test(D′)的具體實(shí)現(xiàn)如算法2所示，其中2～9行為等價(jià)類劃分過程。

算法2privacy_test(D′)輸入：數(shù)據(jù)集D′，隱私值k

輸出：True或False

//True：滿足，F(xiàn)alse：不滿足

Begin

1. 初始化字典record={}

2. forD′中的每一個(gè)樣本t:

3. 準(zhǔn)標(biāo)識(shí)符q=t的取值

4. ifq在字典中：

5. record[q]++

6. else

7. record[q]=1

8. end if

9. end for

10. for record字典中每一個(gè)等價(jià)類C：

11. if len(C)

12. return false

13. end if

14. end for

15. return true

End

3 實(shí)驗(yàn)設(shè)置

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

為了驗(yàn)證本文算法能有效地平衡數(shù)據(jù)隱私保護(hù)程度與分類挖掘性能，本文選用了UCI兩個(gè)經(jīng)典真實(shí)數(shù)據(jù)集——乳腺癌數(shù)據(jù)集(Breast-Cancer)和Adult數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，并將本文算法與文獻(xiàn)[9]中的Greedy_Hamdist從分類性能和運(yùn)行效率兩個(gè)方面進(jìn)行對(duì)比。乳腺癌數(shù)據(jù)集總計(jì)699條數(shù)據(jù)，本文將病態(tài)為良性的記錄作為正類，惡性則為負(fù)類。將包括Clump Thickness、Bare Nuclei、Uniformity of Cell Size等在內(nèi)的8個(gè)離散型屬性均作為準(zhǔn)標(biāo)識(shí)符屬性。Adult數(shù)據(jù)集為隱私保護(hù)領(lǐng)域常用的經(jīng)典數(shù)據(jù)集，本文按正負(fù)類原始比例隨機(jī)抽取2000條樣本進(jìn)行實(shí)驗(yàn)，正類為年收入大于5萬的記錄，負(fù)類為年收入小于等于5萬的記錄。屬性集包括6個(gè)連續(xù)性屬性，如Age、fnlwgt、education-num等，8個(gè)離散型屬性，例workclass、marital-status、relationship等，本文將這14個(gè)屬性均作為準(zhǔn)標(biāo)識(shí)符屬性。兩個(gè)數(shù)據(jù)集均不含有缺失值，分類的類標(biāo)即為敏感屬性。

由于Greedy_Hamdist只能處理二值數(shù)據(jù)，為了使本文算法與其更具有可比性，需要對(duì)原始數(shù)據(jù)中的連續(xù)型數(shù)據(jù)進(jìn)行離散，然后進(jìn)行OneHot處理。離散化采用常用的等距處理，如年齡值離散到(0,20]、(20,40]、(40,60]、(60,80]、(80,∞)。

3.2 評(píng)價(jià)指標(biāo)與實(shí)驗(yàn)設(shè)置

為了驗(yàn)證本文算法選擇的特征子集優(yōu)于Greedy_Hamdist，本文使用ROC曲線下的面積AUC值分類指標(biāo)客觀地評(píng)價(jià)特征子集對(duì)應(yīng)數(shù)據(jù)集的分類挖掘性能，此外，還會(huì)從運(yùn)行時(shí)間對(duì)兩個(gè)算法進(jìn)行比較。

最后為了評(píng)價(jià)特征子集對(duì)應(yīng)數(shù)據(jù)集分類挖掘性能，本文采用sklearn中默認(rèn)設(shè)置的SVM分類器對(duì)特征選擇后的數(shù)據(jù)進(jìn)行分類，核函數(shù)設(shè)置為徑向基函數(shù)，并使用五折交叉驗(yàn)證方式來保證分類的穩(wěn)定性。隨機(jī)森林的決策樹數(shù)量n_estimators設(shè)置為1 000，使用袋外數(shù)據(jù)衡量訓(xùn)練集特征重要性oob_score為True，其余采用sklearn中隨機(jī)森林的默認(rèn)設(shè)置。實(shí)驗(yàn)環(huán)境為：Intel(R) Core(TM) i5-6200U CPU @2.30 GHz 2.40 GHz；4.00 GB(RAM)內(nèi)存；Windows 10 64位操作系統(tǒng)。 算法均采用Python實(shí)現(xiàn)。

4 結(jié)果與分析

4.1 分類挖掘性能分析

使用本文提出的RFKA算法與文獻(xiàn)[9]中的Greedy_Hamdist算法分別在Adult數(shù)據(jù)集和Breast-Cancer數(shù)據(jù)集上進(jìn)行不同K值下的分類實(shí)驗(yàn)，得到如圖2和圖3所示的實(shí)驗(yàn)結(jié)果。當(dāng)K=0時(shí)，表示不對(duì)原始數(shù)據(jù)做隱私保護(hù)。隨著K值越來越大，對(duì)應(yīng)數(shù)據(jù)集的隱私泄露風(fēng)險(xiǎn)越來越低，隱私保護(hù)程度越高。由于剔除了原始數(shù)據(jù)中不滿足K-匿名要求、但重要性高的特征，所以分類性能會(huì)降低，但本文的算法無論在K值為多少時(shí)，AUC都是大于等于Greedy_Hamdist算法的，說明使用隨機(jī)森林度量特征重要性比Hamdist方法更優(yōu)，更適合用于K-匿名的實(shí)現(xiàn)。

圖2 Adult數(shù)據(jù)集在不同K值下的AUC值

圖3 Breast-Cancer數(shù)據(jù)集在不同K值下的AUC值

4.2 運(yùn)行時(shí)間分析

在運(yùn)行時(shí)間方面得到的實(shí)驗(yàn)結(jié)果如圖4和圖5所示。在兩個(gè)數(shù)據(jù)集上，不同K值下，本文的RFKA算法所用時(shí)間均比Greedy_Hamdist更短，表明本文算法在實(shí)現(xiàn)K-匿名時(shí)的運(yùn)行效率更優(yōu)。

圖4 Adult數(shù)據(jù)集在不同K值下的運(yùn)行時(shí)間

圖5 Breast-Cancer數(shù)據(jù)集在不同K值下的運(yùn)行時(shí)間

5 結(jié) 語

本文借助隨機(jī)森林特征重要性度量特征的分類性能，并結(jié)合K-匿名約束對(duì)數(shù)據(jù)實(shí)現(xiàn)特征選擇，使得特征子集對(duì)應(yīng)的數(shù)據(jù)集滿足K-匿名隱私保護(hù)條件。實(shí)驗(yàn)結(jié)果證明，無論是從挖掘性能還是運(yùn)行效率上，本文提出的算法都優(yōu)于Greedy_Hamdist。

在隱私保護(hù)領(lǐng)域，K-匿名只是基礎(chǔ)的隱私保護(hù)模型，因此可以考慮將特征選擇結(jié)合其他模型實(shí)現(xiàn)隱私保護(hù)作為未來工作擴(kuò)展，也可以提出更優(yōu)的特征分類性能度量方法，進(jìn)一步優(yōu)化隱私保護(hù)與挖掘性能之間的平衡。