基于局部學習的差分隱私集成特征選擇算法

劉中鋒

(南京郵電大學 計算機學院、軟件學院、網絡空間安全學院，江蘇 南京 210000)

0 引 言

特征選擇是機器學習和數據挖掘等領域的一個關鍵問題，是從一組特征中挑選出一些最有效的特征以降低特征空間維數的過程。特征選擇不僅能夠降低特征維數，也能夠加快機器學習或者特征選擇算法的執行速度，同時提高算法的準確率，使算法更具有可理解性。在之前的工作中，對于特征選擇的研究主要集中在特征選擇算法的穩定性[1]以及分類準確率等方面[2-3]，然而隱私保護也是一個非常重要的研究方向，比如醫院電子病歷記錄病人基本信息、疾病信息以及藥品購買記錄等，這些信息的泄露會對人身安全造成威脅[4]。雖然關于隱私保護的分類和回歸等應用[5]都已著重研究過，但是對于隱私保護的特征選擇算法的研究卻很少[6-7]。已研究過的隱私保護僅僅是單特征選擇算法，未涉及多個算法的領域。

與集成學習類似，集成特征選擇算法也分為兩個步驟：第一步是構造基特征選擇器[8]，第二步是通過某種組合集成每個基特征選擇器的輸出結果。文中采取Bagging集成策略，利用bootstrap抽樣方法對原始數據集進行抽樣，在抽樣后的數據集上基于局部學習來訓練基特征選擇器[9]，并且采取線性組合的方式對結果進行集成。為了使集成特征選擇具有隱私保護的效果，利用輸出干擾策略，提出了先對結果集成后添加噪聲的集成特征選擇算法FELP。證明該算法滿足差分隱私模型[10-11]的定義，并通過實驗證明其效用性。

1 基于局部學習的差分隱私集成特征選擇算法

1.1 基于局部學習的特征選擇

l(wTzi)=log(1+exp(-wTzi))

(1)

其中，w為特征權重向量；zi=|xi-NM(xi)|-|xi-NH(xi)|。zi可以看作是xi的變換點，wTzi可以看作是局部間隔，屬于假設間隔[12]。此外，為了防止過擬合，在公式中加入了正則化項。由于L2正則化項具有旋轉不變性[13]，同時也具有很強的穩定性，所以評價準則定義為：

(2)

其中，λ為正則化參數。

基于局部學習的特征權重算法FWELL的內容見文獻[14]。

1.2 差分隱私模型和敏感度

文中采用差分隱私模型[10-11]作為隱私風險的一個度量。差分隱私算法定義如下：

定義1(ε-差分隱私)：對于任意給定的數據集D和Di(其中D和Di最多只有一個元素不同)，以及任意的輸出子集S?Range(F)，如果有：

P[F(D)∈S]≤eε×P[F(Di)∈S]

(3)

則算法F滿足差分隱私。

因為加入噪聲的多少會影響算法的性能，所以基于差分隱私算法的輸出干擾策略和算法的敏感度相關。文獻[4,15]中對敏感度進行了定義。

定義2：對于任意帶有n個輸入值的算法F，全局敏感度ΔQ定義為對所有的輸入值，當算法F的某個輸入值變化時函數值的最大變化的L2范數，即：

(4)

式4的敏感度定義和文獻[16]中算法穩定性的定義類似，該穩定性定義為：

(5)

式4和式5的區別在于，敏感度的定義旨在改變一個樣本，而穩定性的定義旨在移除一個樣本。根據三角不等式，能得到兩者之間的關系，結論如下：

ΔQ=‖F(D)-F(D/i)-(F(Di)-F(D/i))‖≤‖F(D)-F(D/i)‖+‖F(Di)-

F(D/i)‖=2ΔSt

(6)

1.3 先集成后擾動策略的差分隱私特征選擇算法(FELP)

(7)

因為r1,r2,…,rk是獨立同分布的，所以r1,r2,…,rk與r有相同的分布，根據三角不等式，則

2‖wD(r)-wD/i(r)‖

(8)

故在數據集D(r)上，根據式5得到FWELL-EN的穩定性是‖wD(r)-wD/i(r)‖。因此可以得到：

ΔQ≤2‖wD(r)-wD/i(r)‖(I(i∈r)+I(i?r))=2[‖wD(r)-wD/i(r)‖I(i∈r)+‖wD(r)-wD/i(r)‖I(i?r)]

(9)

如果該索引r與i無關，也就意味著樣本xi不在樣本子集D(r)中，即滿足D(r)=D/i(r)，于是有wD(r)=wD/i(r)和‖wD(r)-wD/i(r)‖I(i?r)=0。因此可得：

ΔQ≤2‖wD(r)-wD/i(r)‖I(i∈r)

(10)

(11)

根據文獻[11]中的噪聲定義可知，敏感度為2/nλ的FWELL-EN算法的噪聲向量bD定義如下：

(12)

其中，a為一個常量。

FELP算法的偽代碼如下所述。

第一步：采取bootstrap抽樣策略重復抽取k次(抽樣參數為β)，得到k個不同的樣本子集，并且每個樣本子集的大小是「βn?。

第二步：在每個樣本子集上，根據算法FWELL得到k個輸出結果wD。

因為FELP算法是基于差分隱私的算法，所以該算法一定要滿足差分隱私的定義，見定理1。

定理1：FELP算法滿足差分隱私。

(13)

(14)

根據式11、13、14，可以得到：

(15)

由上可知，算法FELP滿足差分隱私。

2 實 驗

文中采用FWELL-EN算法和FELP算法進行實驗對比。整個實驗包括兩部分：驗證隱私度參數ε的影響以及在某個特定隱私度的情況下，驗證不同特征數量時的分類性能。在該實驗中，選取支持向量機(SVM)和k近鄰(kNN)作為分類器，SVM中參數C=1,k近鄰分類器中的參數K=3。采用十次交叉驗證，將數據集分為10等份，9份作為訓練數據，1份作為測試數據。使用bootstrap抽樣策略將訓練數據集分為20個樣本子集(k=20)，并且每份抽樣比例是β=0.9，所有實驗中使用的參數λ將根據交叉驗證調節。選取四個不同大小、不同維度的數據集作為實驗數據，包括Arcene、Soybean、Wdbc和Breast，其中Arcene是一個典型的高維度的小樣本數據集。

2.1 隱私度實驗

該實驗中選定的特征維數是原始數據集中特征維數的10%。FELP算法中的隱私度由ε衡量，ε值的增加意味著隱私度的降低，保護效果也越差。實驗結果見圖1。為了節省空間，兩個分類器的結果共同顯示在一張圖中。

圖1 隱私度實驗結果3NN-SVM

從實驗結果可以看出，在沒有隱私保護的情況下(即ε=100),FWELL-EN算法的分類準確率和具有隱私保護效果的FELP算法有相同的值。但是隨著隱私度ε的減小，算法FELP的分類準確率也隨之減小，而隱私保護性能逐步提高。并且從整體上看，SVM分類器的準確率比3NN要高。雖然當隱私度越小時，隱私保護效果越好，但同樣也面臨可用性的降低，所以考慮到隱私保護和可用性的平衡，ε=0.01是一個效果不錯的選擇。

2.2 特征維數實驗

該實驗主要研究的是特征維數和分類準確率的情況，此時選定的隱私度ε=0.01。特征維數是根據數據集的特征維數來選取的。分類結果見圖2。

圖2 特征維數實驗結果3NN-SVM

從實驗結果可以看出，在特定的隱私度ε=0.01時，算法FELP的分類準確率接近算法FWELL-EN，說明算法FELP的分類性能和算法FWELL-EN非常接近，證明了算法FELP的有效性。

3 結束語

在安全類機器學習中，具有隱私保護性能的特征選擇是一個熱門話題。文中提出了一種基于局部學習的帶有輸出干擾策略的差分隱私集成特征選擇算法FELP，并且從理論上證明了該算法滿足差分隱私，同時通過實驗也證明在特定隱私度下，該算法是有效實用的。