樊佳錦 朱 焱

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

0 引 言

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

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

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

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

1 相關技術

1.1 k-prototypes算法

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

(1)

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

(2)

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

1.2 KACA技術

K-匿名通常采用泛化和隱匿技術，防止外界攻擊者通過鏈接攻擊的手段來獲得敏感屬性和個體身份間的關聯，以達到隱私保護的目的[1]。K-匿名將數據表屬性劃分為標識屬性(Identifiers)、準標識屬性(Quasi-Identifiers,QI)、敏感屬性(Sensitive-Attributes,SA)及其它屬性(Others)。其中準標識屬性是攻擊者能夠通過鏈式攻擊間接識別個體的屬性，也是K-匿名主要應用的屬性。

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

定義2(K-匿名)。對于數據表T(F1,F2,…,Fn)，T[QI]是指表中準標識屬性所在列的數據。由定義1可知，當T[QI]中的每個等價類所包含元組數大于等于K時則稱T表滿足K-匿名，表1為一個2-匿名的數據表實例。

表1 2-匿名數據表實例

由K-匿名的定義可知，K-匿名要求數據表中每條記錄在準標識符屬性取值上與其他至少K-1條記錄的準標識符屬性取值相同，即K值的大小決定了隱私泄露的風險，K值越大，隱私泄露風險越低，反之越高。

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

定義3(泛化的加權層次距離)。設h為準標識屬性泛化層次樹的高度，D1是值域，D2,…,Dh為某個準標識符的泛化域。由Da泛化至Db(a

(3)

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

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

(4)

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

(5)

(6)

1.3 特征分類性能重要性

本文通過構造分類器，計算單個特征的分類性能并進行排序得到排序結果。首先對原始數據集進行分類以獲得分類準確率Acc1，剔除一個特征A后，對新數據集進行分類獲得分類準確率Acc2，則該特征的分類性能計算式為：

PerfR(A)=Acc1-Acc2

(7)

1.4 基于特征相關度的隱私度定義

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

(8)

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

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

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

算法1IFP_KACA算法

輸入：數據集D，準標識屬性QI，其他屬性OR，K值，泛化層次dgh，閾值λ

輸出：信息損失，匿名數據集

Begin

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

2. 構建分類器計算每個特征的分類重要性并降序排序；

3. 得到QI與OR屬性排序序列F_QI_List，F_OR_List；

4. 對OR屬性按F_OR_List進行序列后向選擇得到sub1；

5. for F_QI_List中的每個特征x:

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

7. 定義x的隱私度px為S與QI個數的比值；

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上的投影數據集；

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

16. 使用SVM對D″進行分類得到AUC值；

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

18. end for

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

20. 輸出F_Best對應匿名數據集及其信息損失；

End

在IFP_KACA算法中使用k-prototypes-KACA[4]實現K-匿名。k-prototypes-KACA算法在KACA基礎上引入k-prototypes聚類算法，對原始數據集采用該算法得到多個較大簇再進行K-匿名，提高了算法效率。具體如算法2所示。

算法2k-prototypes-KACA算法

輸入:數據集D，準標識屬性QI，K值，泛化層次dgh

輸出:信息損失，匿名數據集

Begin

1.D′是D在QI上的投影數據集；

2. 對D′采用k-prototypes算法得到聚類結果k_result；

3. for eachk_resultiink_result

4. 從k_resulti劃分若干初始等價類；

5. while存在等價類元組數小于K

6. 隨機選取一個元組數小于K的等價類C；

7. 計算C與其他等價類的距離；

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

9. 依據dgh泛化C和C′；

10. end while

11. end for

12. if存在小于K的等價類C

13. 隱匿C中的元組；

14. end if

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

16. 返回信息損失和匿名數據集；

End

3 實驗設置

3.1 數據集與預處理

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

3.2 評價指標與實驗設置

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

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

4 實驗結果分析

4.1 分類挖掘性能分析

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

圖1 不同K值下CWBO數據集的挖掘性能對比

圖2 不同K值下Adult數據集的挖掘性能對比

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

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

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

4.2 信息損失分析

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

圖3 CWBO數據集在不同K值下的信息損失

圖4 Adult數據集在不同K值下的信息損失

5 結 語

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

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