劉中鋒

(南京郵電大學(xué) 計算機學(xué)院、軟件學(xué)院、網(wǎng)絡(luò)空間安全學(xué)院，江蘇 南京 210000)

0 引 言

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

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

1 基于局部學(xué)習(xí)的差分隱私集成特征選擇算法

1.1 基于局部學(xué)習(xí)的特征選擇

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

(1)

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

(2)

其中，λ為正則化參數(shù)。

基于局部學(xué)習(xí)的特征權(quán)重算法FWELL的內(nèi)容見文獻[14]。

1.2 差分隱私模型和敏感度

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

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

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

(3)

則算法F滿足差分隱私。

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

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

(4)

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

(5)

式4和式5的區(qū)別在于，敏感度的定義旨在改變一個樣本，而穩(wěn)定性的定義旨在移除一個樣本。根據(jù)三角不等式，能得到兩者之間的關(guān)系，結(jié)論如下：

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

F(D/i)‖=2ΔSt

(6)

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

(7)

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

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

(8)

故在數(shù)據(jù)集D(r)上，根據(jù)式5得到FWELL-EN的穩(wěn)定性是‖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無關(guān)，也就意味著樣本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)

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

(12)

其中，a為一個常量。

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

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

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

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

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

(13)

(14)

根據(jù)式11、13、14，可以得到：

(15)

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

2 實 驗

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

2.1 隱私度實驗

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

圖1 隱私度實驗結(jié)果3NN-SVM

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

2.2 特征維數(shù)實驗

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

圖2 特征維數(shù)實驗結(jié)果3NN-SVM

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

3 結(jié)束語

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