基于極端梯度提升特征重要性的K-匿名特征選擇

王旭，萬長勝

〔1.東南大學網絡空間安全學院，江蘇南京 211189；2.網絡空間國際治理研究基地(東南大學)，江蘇南京211189〕

1 引言

隨著互聯網行業的迅速崛起，全球數據量呈指數級增長，數據的采集與發布越發頻繁，信息數據共享更加方便。然而在大數據帶來極高商業價值的同時，以共享信息和數據挖掘為目的的數據發布過程中出現的隱私泄露事件頻發，例如FaceBook與數據分析公司Cam-bridge Analytica的不當共享造成8,700萬用戶個人信息泄露[1]等。

為了避免數據發布時的隱私泄露問題，K-匿名模型在隱私保護領域得到了廣泛的應用。然而將部分數據匿名化，勢必會導致數據挖掘算法性能的下降，因此本文提出了一種基于極端梯度提升特征重要性的K-匿名特征選擇算法，并通過在真實數據集上的實驗，驗證了本文的算法無論在平衡隱私保護和數據挖掘性能方面還是在運行效率方面都優于文獻[2]中基于Greedy_Ha- -mdist的特征選擇算法。

2 基本概念和技術

2.1 隱私保護中的數據屬性定義

數據發布或共享時最常用的數據類型為關系型數據表，數據屬性一般可分為標識符、準標識符、敏感屬性和非敏感屬性4類。例如，表1所示某醫院的就診記錄表部分數據，當將此部分數據進行共享發布時，由于涉及到病人的隱私，一般需要將信息脫敏，最簡單的方法便是將姓名屬性去除。但是當攻擊者擁有某些患者的背景知識，通過一些屬性的組合也可以推斷出患者隱私，例如已知張三是一名郵編為102211的42歲女性患者，即使數據表中沒有姓名這一屬性，也可推測出張三患有感冒。其中，姓名即為標識符，疾病為敏感屬性，而性別、年齡以及郵編屬于準標識符，非敏感屬性即不屬于上述三類的特征。

表1 就診記錄表

2.2 K-匿名特征選擇

（1）K-匿名概念

K匿名模型常用于抵抗鏈接攻擊，為了便于討論，設待發布數據如表2所示，該數據表包含X1,...Xn共n條記錄，其中Ai（i=1，2，...m）為準標識屬性，AS為敏感屬性。

隱私模型要求每條記錄在公布的數據中與其他至少K-1條記錄無法被區分開來[3]。可見，K-匿名模型要求對匿名處理后的數據表中的每條記錄Xi，都應至少有K-1條記錄在準標識符上的取值與Xi相同。K值越大，說明無法區分的記錄越多，攻擊者由準標識符推斷出敏感信息的概率越低，即隱私泄露的風險越小。

表2 待發布數據表

（2）K-匿名特征選擇

對于給定的K值，待發布數據表不一定可以滿足K-匿名模型的要求，此時就需要對數據表中的準標識屬性進行選擇，使得選擇出來的特征子集構成的數據表滿足K-匿名模型的要求。如表3所示，Ai（i=1，2...5）為待匿名特征，假設K-匿名模型選取K為2，如果特征集為（A1，A4，A5），即表中灰色部分的數據，則該子集滿足2-匿名的條件。

表3 K-匿名特征選擇示例

2.3 極端梯度提升特征重要性

XGBoost (Extreme Gradient Boosting)也稱作極端梯度提升，算法的基本思想是選擇部分的特征和樣本生成一個簡單的模型（本文為決策樹）作為基本分類器，通過學習前一個模型的殘差并最小化目標函數來生成新模型，重復執行此過程直到滿足終止條件，最終生成大量簡單模型并組合為準確率較高的綜合模型。其核心在于新的模型在相應損失函數梯度方向建立，修正“殘差”的同時控制復雜度[4]。

（1）目標函數

XGBoost的目標函數由損失函數和正則項兩部分組成，損失函數：

其中，N為樣本個數，yi為第i個樣本的標簽，fm(xi)為第i個樣本在第m次迭代中的預測值。L（θ）以LogLoss為損失函數，設其關于fm(xi)一階導數和二階導數可分別表示為gi和hi，則通過泰勒展開式可以將L(θ)近似表示為：

本文所用的基本模型為回歸樹，正則項表達式為：

其中，T為葉子節點個數，w為每個葉子節點的權值，γ與λ分別為T和w的懲罰系數，二者控制樹的復雜度從而防止過擬合。經決策樹被歸至葉子節點Ij的樣本的損失函數的一階導數和二階導數之和可分別表示為Gi和Hi，去除常數項部分，對其關于w求導得到使目標函數最小的最優w，將其帶入目標函數，函數變為：

（2）特征重要性度量指標

重要性度量是衡量每個特征對樣本進行分類時貢獻程度的方法，XGBoost一般可以根據特征分裂的平均次數、特征平均覆蓋率和特征的平均增益對特征重要性進行度量。由于前兩者只是反映了特征在模型分裂過程中作為決定性特征出現的相對頻率和次數，而平均增益直接反映了以此特征分裂后帶來的準確率的提升程度，是解釋特征重要性的最相關屬性，因此本文主要通過特征平均增益來確定每個特征的重要性指標。

設該模型最終共有X個決策樹，對每個特征的重要性度量指標計算，需要將其在每棵樹（即每個基分類器）中的增益相加并取平均，即：

3 實驗算法與思路

3.1 問題引入

通過特征選擇的方法可以實現數據集的K-匿名從而保護數據隱私，但是從全部特征中得到最佳匿名特征子集是NP完全問題，如表3所示，其中除了（A1，A4，A5）滿足2-匿名要求，（A2，A4，A5）也滿足2-匿名的條件。在對不同的特征對應的子集進行數據挖掘時，其分類性能是不同的，為了使得在隱私得到保護的前提下數據挖掘分類性能較高，本文提出了利用極端梯度提升算法度量特征重要性，按照特征重要性對原始數據集特征進行排序，并采用序列前向搜索的貪心策略，進行K-匿名特征選擇[5]。

3.2 實驗算法

根據實驗思路，通過極端梯度提升算法衡量每個特征重要性，并根據其重要性將特征降序排序，特征子集初始化為空集，并依次把分類性能最高（特征重要性指標最大）的特征加入特征子集，并判斷數據在特征子集上是否符合K-匿名條件，若具有K-匿名性，則將該特征留下，否則剔除，具體算法如算法1所示。

算法1：XGB-KA(D,K)

算法第8行K-anonymity_test(D′)用來判斷數據集D′是否滿足K-匿名條件，即任一條記錄都至少有K-1條記錄在準標識特征上與其具有相同的取值（即有相同的準標識符），具體實現過程如算法2所示，其中2～9行實現了等價類的劃分（每個q為一個等價類，字典中q對應的取值表示該等價類中包含多少條記錄）。

4 實驗流程與結果分析

4.1 數據集介紹

為了驗證本文提出的XGB-KA算法可以有效地平衡數據分類挖掘性能和隱私保護程度，本次實驗選取了兩個UCI常用的真實數據集—Adult以及Breast-Cancer-Wisconsin數據集進行特征選擇和數據挖掘，由于文獻[2]中Greedy-Hamdist算法整體思路與本文類似，只是衡量特征重要性所用算法不同，因此將本文算法與Greedy-Hamdist算法在挖掘分類性能和運行效率兩個方面進行對比。

算法2：K-anonymity_test(D′)

Breast-Cancer-Wisconsin數據集共699條記錄，11個特征；Adult數據集共32,561條記錄，14個特征，本次實驗按照原數據集正負樣本比例隨機抽取了1,500條記錄。

4.2 實驗流程

本次實驗首先對數據集進行預處理，然后利用極端梯度提升特征重要性進行K-匿名特征選擇，最后通過SVM模型對匿名后的子數據集進行分類。算法性能采用Precision和Recall兩個指標進行測評，算法效率則通過運行時間進行對比分析。

本次實驗環境為：Intel（R） Core（TM）i5-5200U CPU @2.20GHZ 2.20GHZ；4.00GB（RAM）內存；Windows 10 64位操作系統。算法均通過Python3.7.5實現。

4.3 數據分類挖掘性能分析

在不同的K值下，對本文提出的XGB-KA算法和文獻[2]提出的Greedy-Hamdist算法在兩個數據集上分別進行分類實驗，得到的結果如圖1-圖4所示。當K=0時，數據集隱私完全沒有受到隱私保護，隨著K值的增大，隱私保護程度越來越高，但由于只保留較重要的特征，分類性能在可接受的范圍內有所下降。除此之外，無論K值為多少，本文提出的XGB-KA算法性能都優于Greedy-Hamdist算法，可見在同等隱私保護程度的前提下，XGB-KA的分類性能優于Greedy-Hamdist算法。

圖1 兩種算法在不同K值下的Precision1

圖2 兩種算法在不同K值下的Recall1

4.4 算法效率分析

通過統計不同K之下兩個算法運行的時間來比較其效率，實驗結果如圖5和圖6所示，由于不同的K值下需要剔除的特征數量不同，兩種算法在不同K值的運行時間均有一定的波動，但本文提出的XGB-KA算法運行時間均短于Greedy-Hamdist算法，這表明XGB-KA算法運行效率更優。

圖3 兩種算法在不同K值下的Precision2

圖4 兩種算法在不同K值下的Recall2

圖5 兩種算法在不同K值下的運行效率1

圖6 兩種算法在不同K值下的運行效率2

5 結束語

本文利用極端梯度提升特征重要性衡量特征對分類結果的貢獻度，并結合K-匿名條件對數據集進行特征選擇，使得經過選擇后的特征子集在原始數據集上投影得到的子數據集在得到隱私保護的同時保持了較好的分類性能。實驗結果證明，無論在分類性能還是在實現效率上，本文提出的XGB-KA算法都優于文獻[2]中的Greedy-Hamdist算法。

未來可以考慮將特征選擇方法與其他隱私保護模型相結合或者利用其它更加高效的特征重要性度量方法，更好地實現隱私保護程度和數據挖掘性能之間的平衡。