基于分類重要性與隱私約束的K-匿名特征選擇

樊佳錦 朱 焱

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

0 引 言

社交網(wǎng)絡(luò)為用戶交流和分享信息提供了良好的平臺(tái)，也為知識(shí)發(fā)現(xiàn)和數(shù)據(jù)挖掘創(chuàng)造了新的機(jī)會(huì)。然而，在對(duì)社交網(wǎng)絡(luò)進(jìn)行數(shù)據(jù)挖掘時(shí)，社交網(wǎng)絡(luò)數(shù)據(jù)集中所包含用戶的隱私信息不經(jīng)保護(hù)可能會(huì)造成用戶隱私泄露。例如在新浪微博中，用戶所填寫的個(gè)人信息可能幫助用心不良者刻畫用戶肖像；用戶使用微博的行為習(xí)慣可能暴露用戶生活習(xí)慣或行蹤；微博內(nèi)容則很可能破解出用戶個(gè)人信息圖譜和關(guān)系網(wǎng)。近年來(lái)，隱私泄露事件頻發(fā)，如2018年媒體披露政治數(shù)據(jù)公司“劍橋分析”在未經(jīng)用戶許可的情況下，利用了社交軟件Facebook上超過(guò)5 000萬(wàn)用戶的個(gè)人信息。由此可見(jiàn)，隱私保護(hù)對(duì)于社交網(wǎng)絡(luò)數(shù)據(jù)挖掘具有重要意義。

隱私保護(hù)數(shù)據(jù)挖掘(Privacy Preserving Data Mining,PPDM)研究數(shù)據(jù)挖掘與隱私保護(hù)技術(shù)的融合。PPDM領(lǐng)域經(jīng)典技術(shù)有匿名化及隨機(jī)擾動(dòng)等。K-匿名由Sweeney等[1]首次提出，因其靈活有效，在隱私保護(hù)領(lǐng)域得到廣泛研究。Li等[2]在傳統(tǒng)K-匿名模型上利用聚類劃分思想,提出一種聚類K匿名方法(K-Anonymity by Clustering in Attribute,KACA)，算法始終選取距離最小的元組進(jìn)行合并泛化，以確?？偟男畔p失趨于最小化。為了更好地保護(hù)敏感屬性，文獻(xiàn)[3]在KACA算法上引入了敏感屬性隱私保護(hù)度，提出了S-KACA(Sensitivity-KACA)算法，對(duì)敏感屬性設(shè)置不同隱私保護(hù)度，使等價(jià)類中敏感屬性的隱私保護(hù)度更加多樣化。文獻(xiàn)[4]在S-KACA算法中引入聚類算法k-prototypes，在有效保護(hù)敏感屬性的基礎(chǔ)上提高了算法效率。

特征選擇作為應(yīng)用廣泛的降維技術(shù)，是數(shù)據(jù)挖掘的重要手段之一，其主要原理是通過(guò)某種評(píng)價(jià)準(zhǔn)則從原始特征集中挑選最優(yōu)特征子集。此環(huán)節(jié)因其對(duì)特征的加工處理而成為隱私特征保護(hù)的關(guān)鍵時(shí)機(jī)。Jafer等[5]在特征選擇中引入多維隱私感知評(píng)估條件，能夠根據(jù)用戶期望的效能來(lái)選擇發(fā)布最佳子集。此外，該文還提出一種基于隱私感知過(guò)濾的特征選擇方法PF-IFR[6]，通過(guò)計(jì)算特征間的相關(guān)性，返回最相關(guān)特征及其相關(guān)性，再根據(jù)設(shè)定閾值對(duì)相關(guān)性高的特征進(jìn)行剔除來(lái)實(shí)現(xiàn)特征選擇；Zhang等[8]利用貪心思想并通過(guò)隱藏分類性能低的特征使特征子集對(duì)應(yīng)數(shù)據(jù)集滿足K-匿名，但其只適用于二值屬性。

本文提出一種基于分類重要性與隱私約束的K-匿名特征選擇方法IFP_KACA。受文獻(xiàn)[5]啟發(fā)，算法定義了特征分類重要性及特征隱私度，結(jié)合K-匿名來(lái)選擇分類性能較高且滿足隱私約束的特征子集。將本文方法與PF-IFR及k-prototypes-KACA方法進(jìn)行對(duì)比實(shí)驗(yàn)可得，所提算法能夠有效地平衡隱私保護(hù)度和分類挖掘性能。將本文算法應(yīng)用于微博垃圾用戶檢測(cè)任務(wù)，優(yōu)選出的特征子集能夠在保護(hù)用戶敏感信息的條件下檢測(cè)垃圾用戶。

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

1.1 k-prototypes算法

k-prototypes[9]是處理混合屬性聚類的典型算法，其繼承了k-means和k-modes算法的思想。給定一個(gè)含有n條樣本、m個(gè)屬性的數(shù)據(jù)集X，其中包含數(shù)值屬性mr個(gè)，分類屬性mc個(gè)。k-prototypes算法旨在找到k個(gè)使目標(biāo)函數(shù)最小化的分組：

(1)

式中：pil∈{0,1}，代表在聚類l中有無(wú)該樣本i；Ql為集群的原型；d(xi,Ql)為相異度距離。

(2)

式中：xir,xic分別代表樣本xi的數(shù)值屬性值和分類屬性值；qlr為數(shù)值屬性r與聚類l的均值；qlc為分類屬性c與聚類l的眾數(shù)；γ為分類屬性的權(quán)重；δ為分類屬性的相異度。

1.2 KACA技術(shù)

K-匿名通常采用泛化和隱匿技術(shù)，防止外界攻擊者通過(guò)鏈接攻擊的手段來(lái)獲得敏感屬性和個(gè)體身份間的關(guān)聯(lián)，以達(dá)到隱私保護(hù)的目的[1]。K-匿名將數(shù)據(jù)表屬性劃分為標(biāo)識(shí)屬性(Identifiers)、準(zhǔn)標(biāo)識(shí)屬性(Quasi-Identifiers,QI)、敏感屬性(Sensitive-Attributes,SA)及其它屬性(Others)。其中準(zhǔn)標(biāo)識(shí)屬性是攻擊者能夠通過(guò)鏈?zhǔn)焦糸g接識(shí)別個(gè)體的屬性，也是K-匿名主要應(yīng)用的屬性。

定義1(等價(jià)類)。假設(shè)有數(shù)據(jù)表T(F1,F2,…,Fn)，準(zhǔn)標(biāo)識(shí)屬性QI(Fi,…,Fj)(i≤j)，等價(jià)類為在準(zhǔn)標(biāo)識(shí)屬性QI取值上完全相同的元組組成的若干集合。

定義2(K-匿名)。對(duì)于數(shù)據(jù)表T(F1,F2,…,Fn)，T[QI]是指表中準(zhǔn)標(biāo)識(shí)屬性所在列的數(shù)據(jù)。由定義1可知，當(dāng)T[QI]中的每個(gè)等價(jià)類所包含元組數(shù)大于等于K時(shí)則稱T表滿足K-匿名，表1為一個(gè)2-匿名的數(shù)據(jù)表實(shí)例。

表1 2-匿名數(shù)據(jù)表實(shí)例

由K-匿名的定義可知，K-匿名要求數(shù)據(jù)表中每條記錄在準(zhǔn)標(biāo)識(shí)符屬性取值上與其他至少K-1條記錄的準(zhǔn)標(biāo)識(shí)符屬性取值相同，即K值的大小決定了隱私泄露的風(fēng)險(xiǎn)，K值越大，隱私泄露風(fēng)險(xiǎn)越低，反之越高。

KACA算法是一種局域泛化的方法，它改進(jìn)了傳統(tǒng)K-匿名屬性間距離的度量方法。為了減小數(shù)據(jù)匿名化所造成的信息損失，KACA算法定義了與傳統(tǒng)K-匿名不同的屬性泛化的加權(quán)層次距離和泛化失真度。

定義3(泛化的加權(quán)層次距離)。設(shè)h為準(zhǔn)標(biāo)識(shí)屬性泛化層次樹(shù)的高度，D1是值域，D2,…,Dh為某個(gè)準(zhǔn)標(biāo)識(shí)符的泛化域。由Da泛化至Db(a

(3)

式中：wj,j-1為Dj～Dj-1(2≤j≤h)之間的泛化權(quán)重，其計(jì)算式為：

wj,j-1=1/(j-1)β(2≤j≤h,β≥1)

(4)

式中：β由數(shù)據(jù)發(fā)布者設(shè)置，本文中β=1。該方法體現(xiàn)出泛化到不同層級(jí)時(shí)所造成的數(shù)據(jù)變形的不同程度。

(5)

(6)

1.3 特征分類性能重要性

本文通過(guò)構(gòu)造分類器，計(jì)算單個(gè)特征的分類性能并進(jìn)行排序得到排序結(jié)果。首先對(duì)原始數(shù)據(jù)集進(jìn)行分類以獲得分類準(zhǔn)確率Acc1，剔除一個(gè)特征A后，對(duì)新數(shù)據(jù)集進(jìn)行分類獲得分類準(zhǔn)確率Acc2，則該特征的分類性能計(jì)算式為：

PerfR(A)=Acc1-Acc2

(7)

1.4 基于特征相關(guān)度的隱私度定義

特征相關(guān)度代表了兩個(gè)特征的相關(guān)性，在特征選擇中常對(duì)高相關(guān)度的特征進(jìn)行剔除以減少特征冗余。對(duì)于隱私保護(hù)而言，計(jì)算隱私特征之間的相關(guān)度并根據(jù)相關(guān)度定義隱私度，隱私度越大代表泄露隱私的風(fēng)險(xiǎn)越高。通過(guò)設(shè)定閾值，進(jìn)行基于隱私約束的K-匿名特征選擇，減少隱私特征的個(gè)數(shù)，降低泄露隱私的風(fēng)險(xiǎn)。準(zhǔn)標(biāo)識(shí)屬性中包含用戶的個(gè)人隱私信息，是本文要保護(hù)的對(duì)象。對(duì)于每個(gè)準(zhǔn)標(biāo)識(shí)屬性，首先計(jì)算其與其他準(zhǔn)標(biāo)識(shí)屬性的相關(guān)度，再設(shè)置相關(guān)度之和與準(zhǔn)標(biāo)識(shí)屬性總個(gè)數(shù)的比值為該準(zhǔn)標(biāo)識(shí)屬性的隱私度。其中，特征相關(guān)度的計(jì)算采用SU系數(shù)[6]，其計(jì)算式為：

(8)

式中：H(X)和H(Y)分別表示屬性X和Y的信息熵，H(X,Y)為X和Y的聯(lián)合信息熵。

2 基于分類重要性與隱私約束的K-匿名特征選擇算法

本文算法首先構(gòu)造分類器對(duì)所有特征分類性能進(jìn)行排序，通過(guò)計(jì)算每個(gè)準(zhǔn)標(biāo)識(shí)屬性的相關(guān)度來(lái)設(shè)置隱私度；對(duì)于準(zhǔn)標(biāo)識(shí)屬性，選擇特征分類重要性較高且滿足隱私約束的特征子集使用k-prototypes-KACA算法進(jìn)行K-匿名操作；對(duì)于其他屬性，按照排序順序進(jìn)行序列后向選擇；最后，對(duì)所選特征子集對(duì)應(yīng)數(shù)據(jù)集使用SVM進(jìn)行分類，評(píng)價(jià)信息損失及分類性能，選擇最優(yōu)特征子集。具體如算法1所示。

算法1IFP_KACA算法

輸入：數(shù)據(jù)集D，準(zhǔn)標(biāo)識(shí)屬性QI，其他屬性O(shè)R，K值，泛化層次dgh，閾值λ

輸出：信息損失，匿名數(shù)據(jù)集

Begin

1. 初始化sub1={},sub2={},temp={},F_List={},priv=0；

2. 構(gòu)建分類器計(jì)算每個(gè)特征的分類重要性并降序排序；

3. 得到QI與OR屬性排序序列F_QI_List，F(xiàn)_OR_List；

4. 對(duì)OR屬性按F_OR_List進(jìn)行序列后向選擇得到sub1；

5. for F_QI_List中的每個(gè)特征x:

6. 根據(jù)式(8)計(jì)算x與其他QI屬性的相關(guān)度之和S；

7. 定義x的隱私度px為S與QI個(gè)數(shù)的比值；

8. priv+=px；

9. if priv<λ

10. sub2=sub2.append(x)；

11. else

12. Break；

13. F_List=sub1∪sub2；

14.D′是D在F_List上的投影數(shù)據(jù)集；

15. 采用k-prototypes-KACA(D′,QI,K,dgh)得到當(dāng)前匿名數(shù)據(jù)集D″及其信息損失；

16. 使用SVM對(duì)D″進(jìn)行分類得到AUC值；

17. temp=temp.append((F_List,信息損失,AUC))；

18. end for

19. 評(píng)價(jià)信息損失與AUC值，選擇最優(yōu)特征子集F_Best；

20. 輸出F_Best對(duì)應(yīng)匿名數(shù)據(jù)集及其信息損失；

End

在IFP_KACA算法中使用k-prototypes-KACA[4]實(shí)現(xiàn)K-匿名。k-prototypes-KACA算法在KACA基礎(chǔ)上引入k-prototypes聚類算法，對(duì)原始數(shù)據(jù)集采用該算法得到多個(gè)較大簇再進(jìn)行K-匿名，提高了算法效率。具體如算法2所示。

算法2k-prototypes-KACA算法

輸入:數(shù)據(jù)集D，準(zhǔn)標(biāo)識(shí)屬性QI，K值，泛化層次dgh

輸出:信息損失，匿名數(shù)據(jù)集

Begin

1.D′是D在QI上的投影數(shù)據(jù)集；

2. 對(duì)D′采用k-prototypes算法得到聚類結(jié)果k_result；

3. for eachk_resultiink_result

4. 從k_resulti劃分若干初始等價(jià)類；

5. while存在等價(jià)類元組數(shù)小于K

6. 隨機(jī)選取一個(gè)元組數(shù)小于K的等價(jià)類C；

7. 計(jì)算C與其他等價(jià)類的距離；

8. 找出與C距離最近的等價(jià)類C′；

9. 依據(jù)dgh泛化C和C′；

10. end while

11. end for

12. if存在小于K的等價(jià)類C

13. 隱匿C中的元組；

14. end if

15. 根據(jù)式(6)計(jì)算信息損失；

16. 返回信息損失和匿名數(shù)據(jù)集；

End

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

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

本文采用Adult數(shù)據(jù)集和構(gòu)建的中文微博數(shù)據(jù)集CWBO驗(yàn)證IFP_KACA算法在數(shù)據(jù)隱私保護(hù)度和分類挖掘上的性能。CWBO選取了6 000個(gè)資料完整度較高的用戶，爬取用戶微博數(shù)據(jù)，對(duì)數(shù)據(jù)集進(jìn)行擴(kuò)充。根據(jù)微博垃圾用戶的行為特點(diǎn)，多人投票標(biāo)注垃圾用戶與正常用戶。從微博內(nèi)容、用戶個(gè)人信息和用戶行為三方面提取了新特征，并對(duì)數(shù)據(jù)集進(jìn)行了數(shù)據(jù)清洗、數(shù)據(jù)標(biāo)準(zhǔn)化等操作。最終構(gòu)建成實(shí)驗(yàn)所用中文微博數(shù)據(jù)集，包括5 740條數(shù)據(jù)、27個(gè)特征，垃圾用戶與正常用戶的比例約為2 ∶3。本文從27個(gè)屬性中選取了年齡、學(xué)歷等11個(gè)屬性作為準(zhǔn)標(biāo)識(shí)屬性，這些屬性中包含用戶個(gè)人隱私信息，也是本文所需要保護(hù)的敏感屬性。對(duì)Adult數(shù)據(jù)集按正負(fù)類原始比例隨機(jī)抽取2 000條樣本，從原始14個(gè)屬性中選取11個(gè)作為準(zhǔn)標(biāo)識(shí)屬性進(jìn)行實(shí)驗(yàn)。

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

為了驗(yàn)證本文算法能有效平衡隱私保護(hù)度與分類性能，將本文算法與PF-IFR及k-prototypes-KACA算法從分類性能、信息損失兩個(gè)方面進(jìn)行對(duì)比。其中分類性能采用ROC曲線下的面積AUC值進(jìn)行評(píng)估。

本文采用SVM分類器對(duì)特征選擇后的數(shù)據(jù)進(jìn)行分類，并使用五折交叉驗(yàn)證方式來(lái)保證分類的穩(wěn)定性。實(shí)驗(yàn)環(huán)境為：Intel(R) Core(TM) i7- 4700MQ CPU @2.40 GHz；8 GB(RAM)內(nèi)存；Windows 8.1 64位操作系統(tǒng)。算法均采用Python3.6實(shí)現(xiàn)。

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

4.1 分類挖掘性能分析

分別針對(duì)中文微博(CWBO)和Adult數(shù)據(jù)集，本文算法IFP_KACA與k-prototypes-KACA[4]、PF-IFR[6]算法所得特征子集，基于不同的特征集設(shè)計(jì)了分類對(duì)比實(shí)驗(yàn)，結(jié)果如圖1-圖2所示。實(shí)驗(yàn)中，隱私度閾值決定了加入特征子集的準(zhǔn)標(biāo)識(shí)屬性的個(gè)數(shù)，由用戶自行設(shè)置。隱私度閾值越小，隱私保護(hù)力度越大，但可能造成分類性能的急劇下降。本文通過(guò)取多個(gè)隱私度閾值并比較其分類性能變化情況，設(shè)置CWBO的隱私度閾值為0.5，Adult為0.7。

圖1 不同K值下CWBO數(shù)據(jù)集的挖掘性能對(duì)比

圖2 不同K值下Adult數(shù)據(jù)集的挖掘性能對(duì)比

K值大小決定了K-匿名的隱私保護(hù)程度，K=0時(shí)表示未加隱私保護(hù)的特征優(yōu)選集的分類結(jié)果。隨著K值的增大，對(duì)于特征的隱私保護(hù)度增高，分類性能呈下降趨勢(shì)。

相比k-prototypes-KACA算法，本文算法一方面設(shè)置隱私約束，使優(yōu)選特征集盡可能少地包含準(zhǔn)標(biāo)識(shí)屬性，減少了隱私泄露的風(fēng)險(xiǎn)；另一方面，算法根據(jù)特征分類重要性排序，每次選擇加入分類性能較好的準(zhǔn)標(biāo)識(shí)屬性進(jìn)行匿名，提高了分類挖掘性能。

PF-IFR算法同樣通過(guò)相關(guān)度來(lái)定義敏感屬性的隱私度，但特征選擇過(guò)程未結(jié)合K匿名。本文算法相比PF-IFR，通過(guò)K匿名操作進(jìn)一步保護(hù)了準(zhǔn)標(biāo)識(shí)屬性值，由于按照特征分類性能重要性優(yōu)先選擇分類性能較高的特征加入特征集，減少了K匿名所帶來(lái)的信息損失。故本文算法相較PF-IFR增加了對(duì)于隱私屬性的保護(hù)力度，同時(shí)分類性能比較接近。

4.2 信息損失分析

對(duì)于不同K值下k-prototypes-KACA算法及本文算法所得匿名數(shù)據(jù)集的信息損失情況如圖3和圖4所示。在兩個(gè)數(shù)據(jù)集上，不同K值下，本文算法設(shè)置隱私約束使優(yōu)選特征集盡可能少地包含準(zhǔn)標(biāo)識(shí)屬性，再進(jìn)行K匿名，故信息損失要小于k-prototypes-KACA算法。

圖3 CWBO數(shù)據(jù)集在不同K值下的信息損失

圖4 Adult數(shù)據(jù)集在不同K值下的信息損失

5 結(jié) 語(yǔ)

本文提出的IFP_KACA算法定義特征分類重要性和特征隱私度，并結(jié)合K-匿名進(jìn)行特征選擇。優(yōu)選出的特征集滿足兩個(gè)條件：所含的敏感特征盡可能少，分類性能盡可能不受影響，從而較好地平衡隱私保護(hù)與分類的雙重要求。將本文方法應(yīng)用于中文微博垃圾用戶檢測(cè)，實(shí)驗(yàn)結(jié)果表明其能夠兼顧敏感信息隱藏和垃圾用戶檢測(cè)的綜合目標(biāo)。

K-匿名只是隱私保護(hù)模型中的一種，未來(lái)的工作可以考慮將隱私保護(hù)的其他模型，如L-多樣性、T-接近等與特征選擇相結(jié)合。除此之外，也可以在特征選擇算法上進(jìn)行改進(jìn)，集成其他的隱私保護(hù)技術(shù)，如隨機(jī)擾動(dòng)、差分隱私等。