一種針對異常點的自適應回歸特征選擇方法

郭亞慶 王文劍 蘇美紅

1(山西大學計算機與信息技術學院 太原 030006)2(計算智能與中文信息處理教育部重點實驗室(山西大學) 太原 030006)

一些實際學習任務的數據集中常含有大量不相關特征和冗余特征，特征數目巨大，如基因組分析、文本分類和圖像檢索等，故會導致維數災難和學習任務難度提高等問題，以至于學習效果不好或學得模型可解釋性差.此外，觀測某些特征代價昂貴，若這些特征為無關特征，則會造成大量不必要開銷.解決上述問題的一種有效途徑是特征選擇.特征選擇是將可以代表整體的含有關鍵性度量信息的部分特征挑選出來的過程，它使得后續學習過程僅需在一部分特征上構建模型[1-2].另外，現有針對回歸問題的特征選擇方法，當數據集含異常點時，對其敏感或自適應能力不佳，導致特征選擇和學習效果較差.故如何自適應地進行穩健回歸特征選擇仍然是一個挑戰性的課題.

針對分類問題的特征選擇方法已有很多，常用的方法可分為2類:一類為過濾式(如Relief(relevant features)、mRMR(max-relevancy, min-redundancy)和Relief-F等);另一類為包裹式(如LVM(Las Vegas wrapper)、SFFS(sequential floating forward selection)、SFS(sequential feature selection)和LRS(Plus-L-Minus-R search)等)[3-6].這些方法都是先對數據集進行特征選擇，再訓練學習器，其中過濾式方法特征選擇過程與后續學習器無關，導致最終學習器性能不好；包裹式方法雖然在選擇特征時考慮了學習器性能，但因為多次訓練學習器造成了大量時間開銷.

上述面向分類的特征選擇方法往往不能直接用于回歸問題或應用后效果不好.目前針對回歸問題的特征選擇方法較少，其代表性方法分為兩大類：

1) 先對數據集進行特征選擇，然后再訓練學習器，如向前選擇法(forward-stepwise selection)、向后剔除法(backward-stepwise selection)和逐步篩選法(forward-stagewise regression)等，這些方法不僅具有分類特征選擇方法的某些缺點，還不適用于特征數目巨大和有相關特征的數據集，適用范圍較小，故并不常用[7].

2) 將特征選擇過程與學習器訓練過程融為一體同時完成，提高了最終學習器的性能，降低了開銷，其典型方法有LASSO[8]、LAD-LASSO(least absolute deviation)[9]、L1/2正則化[10]、嶺回歸(ridge regression)[11]、Elastic Net[12]、Group Lasso[13]、SCAD(smoothly clipped absolute deviation)[14]和MCP(minimax concave penalty)[15]等.其中嶺回歸因使用L2正則項而不易于獲得稀疏解；L1/2正則化的實現算法效率較低；Elastic Net適用于特征之間相關性較高的數據集；Group Lasso適用于協變量之間存在組結構的回歸數據集；SCAD和MCP雖然降低了LASSO的泛化誤差，但正則項復雜，較難求解，故LASSO和LAD-LASSO這2種方法更為常用.LASSO可以較為準確地完成特征選擇，并且計算快捷，故被廣泛使用.

上述回歸特征選擇方法對異常點(數據集中與數據的一般行為或模型不一致的數據對象)極其敏感，導致對于含有異常點的數據集，其穩健性和稀疏性都有所下降.目前提出的穩健回歸特征選擇方法不多且大多針對含有噪聲的數據集，如分位數回歸及其改進方法[16-18]和LAD-LASSO等，其中分位數回歸及其改進方法模型復雜.針對異常點的穩健回歸估計方法有WLAD(weight least absolute deviation)[19]和LTS(least trimmed squares estimator)[20]等，在其基礎上WLAD-LASSO[19],LTS-LASSO[20],reweighted LTS-LASSO[20],WLAD-CATREG(categorical regres-sion model) adoptive elastic net[21]和WLAD-SCAD[22]等被相繼提出，這些方法增加了易于獲得稀疏解的正則項，可以同時完成特征選擇和學習器訓練.其中LTS-LASSO通過將訓練誤差較小的數據集子集作為訓練集來降低異常點影響，但其時間開銷較大；其余針對異常點的回歸特征選擇方法通過給損失函數加權來提高其穩健性，其中reweighted LTS-LASSO將LTS-LASSO求得的回歸系數作為參數初值，WLAD-LASSO,WLAD-CATREG和WLAD-SCAD根據數據集穩健位置估計量、數據集散點估計量和各樣本的穩健距離得樣本權重，上述通過加權來提高穩健性的回歸特征選擇方法都是先計算好樣本損失函數權重，再進行特征選擇和學習器訓練，樣本權重在整個算法執行過程中固定不變，故它們無法在特征選擇和學習器訓練過程中根據學習效果多次自主修改權重來進一步提高算法性能，算法自適應能力不佳.此外，針對現有回歸特征選擇方法當數據集含異常點時性能較差這一固有問題，近年來并沒有很好的研究成果.

鑒于此，本文提出一種能不斷根據數據集和學習效果自主更新樣本權重的用于線性回歸的穩健特征選擇方法AWLASSO(adaptive weight LASSO)，其使用在[0,1]中連續變化的自適應權重以更好地提高自適應性.該方法將特征選擇與學習器訓練過程融為一體同時完成，以提高學習器性能和降低模型復雜度.AWLASSO算法通過閾值確定樣本的損失函數權重;一方面可以使迭代過程總朝著較好的回歸系數估計值方向進行；另一方面能保證訓練集含有足夠的樣本，同時可以排除異常點的影響.本文在構造數據和標準數據上驗證了提出方法的有效性.

1 預備知識

為便于理解本文提出方法及與LASSO和LAD-LASSO進行比較，本節簡要介紹LASSO和LAD-LASSO.

(1)

其中，正則化參數λ>0.求解LASSO的方法有Homotopy[23]、LARS(Least Angle RegresSion)[24]、坐標下降法[25-26]等.

與LASSO方法相比，LAD-LASSO方法以絕對值誤差為損失函數，其優化目標為

(2)

將其轉化成線性規劃問題即可求解[27].

2 針對異常點的自適應回歸特征選擇方法

2.1 AWLASSO模型

對于不含異常點的數據集，LASSO和LAD-LASSO方法都具有良好的性能，然而對于含有異常點的數據集，這2種方法沒有區別對待異常點，可能使得回歸系數估計值與真實回歸系數相差較大，導致特征選擇和學習器訓練效果不好.此外，LASSO使用平方誤差作為損失函數，相比LAD-LASSO以絕對值誤差為損失函數，可能會使異常點的影響被放大，故其穩健性和稀疏性被破壞更為嚴重.

本文提出的AWLASSO首先根據更新后的回歸系數更新樣本誤差，并通過自適應正則項將誤差大于當前閾值的樣本的損失函數賦予較小權重，誤差小于閾值的樣本的損失函數賦予較大權重，再在更新了權重的加權損失函數下重新估計回歸系數.通過不斷迭代上述過程，它每次在較優樣本權重估計值下完成回歸系數估計，在較優回歸系數估計值下完成樣本權重估計.多次自主修正權重后其在合適的加權損失函數下完成特征選擇和學習器訓練.本文在第1次迭代時隨機挑選部分樣本作為訓練集，該訓練集可能含有異常點，故為防止異常點進入下一次迭代，在下一輪迭代中得到較好的回歸系數估計值，AWLASSO閾值初始值取較小值.在上述迭代過程中，閾值不斷增大，被誤判為異常點的樣本有機會重新進入訓練集，以保證訓練集含有足夠的樣本和保留多種樣本信息.相比閾值由大到小進行迭代，上述閾值選取方式，大量異常點進入訓練集的可能性較小，不會出現即使減小閾值，由于各樣本誤差累積，仍無法對樣本損失函數準確賦權重，最終得到偏差較大的回歸系數估計值的情況.AWLASSO當達到最大閾值時迭代停止，此時它將誤差大于最大閾值，即學習代價較大，會嚴重影響學習效果的樣本視作異常點，令其損失函數權重為0，以降低異常點的影響.

AWLASSO具體模型為

(3)

1) 更新樣本權重.首先根據當前的回歸系數估計值更新各樣本誤差，然后更新自適應正則化參數，最后利用更新后的各參數和自適應正則項更新樣本權重，此時，誤差大于當前閾值的樣本的損失函數被賦予較小權重，誤差小于閾值的樣本的損失函數被賦予較大權重，并利用更新后的權重修正加權損失函數.

2) 更新回歸系數.求解更新后的目標函數，即完成特征選擇和學習器訓練，并反饋回歸系數估計值.

AWLASSO算法多次迭代上述2個階段，不斷根據數據集和學習效果自主更新樣本權重.在上述迭代過程中，閾值不斷增大，當達到最大閾值時迭代停止，此時AWLASSO將誤差大于最大閾值的樣本視作異常點，令其損失函數權重為0，以降低異常點的影響，提高算法性能.其在處理異常點時，不僅不需要較好地回歸系數參數初值，也不只依賴數據集，算法具有較好的自適應能力.

2.2 樣本權重確定

(4)

通過優化

可得自適應向量各分量為

(5)

2.3 模型求解

本文使用交替迭代方法求解AWLASSO模型，每次迭代先固定v求β，再固定β求v，直到獲得較為滿意的結果為止.固定v求β時，AWLASSO的優化目標為

(6)

與常規的LASSO相同，本文也選用坐標下降法[25]求解該優化目標，即：

對βj求導得：

(7)

其中,βj∈[0,z)或(z,0]，且當z≠0時βj與λ有關，當λ值較大時，βj有可能成為0.

在下次迭代過程中，通過式(5)更新v.

2.4 算法描述

求解AWLASSO的主要步驟如算法1所示.

算法1.AWLASSO模型求解算法.

輸入：訓練集X∈Rn×p和Y∈Rn、自適應參數初始值k0、自適應參數終止值kend、正則化參數λ,且k0>kend,μ>1;

輸出：回歸系數β.

Step1. 初始化自適應向量v為一個固定值(一般隨機令v一半分量為0，另一半分量為1)，自適應參數k=k0；

Step2. 當自適應參數k>kend時，循環執行以下步驟：

Step2.1. 更新回歸系數β；

Step2.3. 將各參數帶入式(5)，更新v；

3 實驗結果及分析

3.1 數據集及評價指標

為驗證本文提出方法AWLASSO的有效性，分別在2個構造數據集和4個標準數據集上進行實驗，并與LASSO和LAD-LASSO進行對比.

Table 1 Artificial Datasets表1 構造數據集

Table 2 Benchmark Datasets表2 標準數據集

Fig. 1 Feature selection results on D1圖1 在D1數據集上的特征選擇結果

實驗中AWLASSO方法的參數γ=0.4，μ=1.2，k初始值為2.5，終止值為0.000 1.在構造數據集上，實驗重復進行100次，取平均值作為最終結果.

本文用平均平方誤差(MSE)作為評價算法穩健性的性能指標，用MSE1表示回歸系數估計值β*與βtrue的差別，即：

(8)

用MSE2表示回歸系數估計值β*與βfalse的差別，即：

(9)

(10)

其中,w表示實驗重復次數，Yt表示第t次實驗得到的回歸向量預測值.如果某種方法的MSE1較小且MSE2較大或MSE3較小，說明該方法估計出的回歸系數與真實回歸系數相差較小，與干擾回歸系數相差較大，其穩健性較好，反之穩健性較差.同時本文用無關特征選擇正確個數的平均表現來評估這3種方法的稀疏性，其值越接近真實回歸系數含0總數，對應方法稀疏性越好，反之則越差.

所有實驗用MATLABR2014a實現.實驗環境為4 GB內存，Intel?CoreTM2 Quad處理器，2.66 GHz，Windows10操作系統.

3.2 構造數據集上的實驗結果

3.2.1 特征選擇結果

首先比較LASSO，LAD-LASSO和AWLASSO這3種方法特征選擇的結果.由于這3種方法在構造數據集D1和D2上特征選擇結果基本一致，故本文只給出構造數據集D1上的實驗結果.圖1為構造數據集D1上的特征選擇結果，圖1(a)是選出無關特征的個數的平均結果，圖1(b)給出了無關特征選擇正確個數的平均結果與選出無關特征的個數的平均結果的比例r.在D1數據集上，真實回歸系數有4個分量為0，即有4個無關特征，故在圖1(a)中選出無關特征的個數的平均結果越接近4，對應方法特征選擇效果越好.由于LASSO在各污染率下無關特征選擇正確個數的平均結果和選出無關特征的個數的平均結果皆為0，且LAD-LASSO和AWLASSO在各污染率下當λ>25時，得到的回歸系數估計值各分量皆為0或極小的數，方法失效，故未在圖1中給出上述實驗特征選擇結果.從圖1(a)中可以看出，在不同污染率下，LASSO和LAD-LASSO在不同λ值下選出無關特征的個數的平均結果都接近于0，嚴重偏離4；AWLASSO當λ取值較小時接近于4.由于LAD-LASSO并未完成特征選擇，圖1(b)只給出AWLASSO方法的r，r值應介于0到1之間.由圖1(b)可知AWLASSO方法當選出無關特征的個數的平均結果接近于4時其r都接近于1，即它正確選出了無關特征，特征選擇結果較好，但它對參數λ較為敏感，當λ值增大到一定程度后，其得到的回歸系數估計值各分量都為0，r=1/2，無法完成特征選擇.

3.2.2 穩健性比較

本文還比較了3種方法的穩健性.由于這3種方法在構造數據集D1和D2上實驗結果基本一致，故本文只給出構造數據集D2上的實驗結果.圖2是構造數據集D2在不同污染率下MSE1和MSE2的比較結果，其中不含空心圓的曲線表示各方法的MSE1，含空心圓的曲線表示各方法的MSE2.從圖2中可以看出，在不同污染率下，無論是MSE1還是MSE2，LASSO方法都較大，說明其對含有異常點的數據處理能力較差.對于MSE1，AWLASSO方法在一定的λ值之下，都小于LAD-LASSO，當λ值繼續增大時，LAD-LASSO的MSE1才減小至與AWLASSO的相同.對于MSE2，在絕大多數情況下AWLASSO要高于LAD-LASSO，當λ大于一定值之后，2種方法的MSE2才相同.實驗結果表明，AWLASSO方法估計出的回歸系數都與回歸系數真實值相差較小(MSE1較小)，與干擾回歸系數相差較大(MSE2較大)，它不會像LAD-LASSO方法那樣受干擾回歸系數的影響，故AWLASSO方法的穩健性更好.

Fig. 2 Comparisons of MSE1 and MSE2 on D2圖2 3種方法在D2數據集上的MSE1和MSE2比較結果

為了更好地說明AWLASSO方法與LAD-LASSO方法的穩健性，通過對比圖2各分圖可得它們在構造數據集D2上污染率取不同值時MSE1的比較結果.從中可以看出，當其他參數取值相同時，LAD-LASSO方法對應的MSE1隨著污染率的增大而顯著增大，AWLASSO方法對應的MSE1并沒有隨著污染率的增大而顯著增大，而是一直處于某一值附近，其性能不會隨著數據集中被污染數據的增加而顯著變差，即AWLASSO方法相比LAD-LASSO方法更穩健.

在構造數據集上的所有實驗結果表明：無論數據分布如何，異常點分布如何，AWLASSO都比LASSO和LAD-LASSO更穩健更稀疏.

3.3 標準數據集上的實驗結果

Table 3 Experiment Results of Three Methods on Benchmark Datasets表3 3種方法在標準數據集上的實驗結果

Note: “↓” represents the most robust method is the one having the lowestSE3.

1) 原始數據集上的實驗結果

由表3知，LASSO在上述標準數據集上的32個回歸系數估計值中有10個不含無關特征，LAD-LASSO的有16個不含無關特征，AWLASSO的有6個不含無關特征.AWLASSO在Eunite2001數據集上，當λ=70時，選出了9個無關特征；在Housing數據集上，當λ=80時，選出了9個無關特征；在Mpg數據集上，當λ=50時，選出了5個無關特征；在Tiazines據集上，當λ=30時，選出了58個無關特征，即其在各數據集上選出無關特征最多，且沒有將所有特征視作無關特征.在各數據集上，AWLASSO方法對參數λ較為敏感，它只在某些λ值下特征選擇效果好，學習器訓練效果中等；LAD-LASSO方法在各λ值下學習器訓練效果都好，但特征選擇效果都不好；LASSO方法在數據集Eunite2001,Housing和Triazines上，特征選擇和學習器訓練效果都不好，但在數據集MPG上，當參數λ取某些值時，其特征選擇和學習器訓練效果較好.

由于LASSO方法整體表現不穩定，所以后邊實驗只比較了LAD-LASSO和AWLASSO方法的性能.表4給出了這2種方法在各自較優參數范圍內的實驗結果比較，“0”表示在較優參數范圍內求得的各回歸系數估計值無重疊無關特征.由表4知，當參數λ在較優參數范圍內時，LAD-LASSO方法在4個數據集上都沒有重疊無關特征，它在各較優參數λ下只有少數回歸系數估計值含有少量0分量，其選出的無關特征較少.AWLASSO在所有的數據集上都有大量重疊無關特征，其在較優參數范圍內得到的各回歸系數都含大量的0分量，它選出了大量無關特征且不會將所有特征視作無關特征.AWLASSO方法的最小SE3和最大SE3要稍大于LAD-LASSO方法的.故在標準數據集上AWLASSO沒有LAD-LASSO穩健，但比LAD-LASSO稀疏.

2) 含異常點數據集上的實驗結果

Table 4 Experiment Results with Fitted Parameter λ on Benchmark Datasets表4 較優參數λ下的標準數據集實驗結果

由表5可知，在上述標準數據集上，LAD-LASSO在各θ下的50個回歸系數估計值都沒有重疊無關特征.它在各數據集上所有參數組合下的200個回歸系數估計值，在Eunite2001上有174個不含無關特征，有26個有無關特征但無重疊無關特征；在Housing數據集上有193個不含無關特征，有7個有無關特征但無重疊無關特征；在Triazines數據集上有75個不含無關特征，有125個有無關特征但無重疊無關特征；在MPG數據集上有197個不含無關特征，有3個有無關特征但無重疊無關特征.而AWLASSO只在MPG數據集上當污染率θ=0.5時沒有重疊無關特征，剩余情況下，其皆有大量重疊無關特征，而且它重疊無關特征數小于數據集特征總數，即AWLASSO沒有將所有特征視作無關特征.

Table 5 Feature Selection Results on Benchmark Datasets with Outliers表5 含異常點的標準數據集特征選擇結果

Fig. 3 Comparisons of MSE3 on benchmark datasets with outliers圖3 含異常點的標準數據集上MSE3的比較結果

由圖3可知當異常點含量為20%時，AWLASSO方法只在MPG數據集上MSE3比LAD-LASSO的小，但在Triazines數據集上兩者MSE3相差不大.當異常點含量為30%～50%時，AWLASSO方法的MSE3要比LAD-LASSO的小很多，且它不會像LAD-LASSO那樣其MSE3隨著污染率的增大而顯著增大.在標準數據集上的實驗結果表明當數據集含異常點時，AWLASSO方法的特征選擇能力更強、穩健性更好.

3.4 高維數據集上的實驗結果

為驗證AWLASSO方法在特征數量較多的數據集上的性能，本文構造高維數據集D3和D4，其構造方法與構造數據集的構造方法相同.高維數據集的真實回歸系數βtrue=(1,2.5,1.5,2,0,…,0)T，數據集如表6所示：

Table 6 High Dimensional Datasets表6 高維數據集

高維數據集上LASSO，LAD-LASSO和AWL-ASSO這3種方法特征選擇的結果如圖4所示.由于LASSO未完成特征選擇，故在圖中未給出其結果.由圖4(a)(b)可知，當λ取合適值時，LAD-LASSO幾乎沒有選出無關特征，AWLASSO在D3和D4數據集上選出無關特征數目的均值接近于數據集所含無關特征總數，且它正確選出了無關特征.

圖5和圖6分別是3種模型在不同污染率下MSE1和MSE2的比較結果.從圖5和圖6中可以看出，在不同污染率下，相比LASSO和LAD-LASSO，絕大多數情況下AWLASSO方法MSE1都較小，MSE2都較大，且其對應的MSE1并沒有隨著污染率的增大而顯著增大.高維數據集上的實驗結果表明，當數據集含大量特征時，AWLASSO方法仍有較好的穩健性和特征選擇能力.

Fig. 4 Feature selection results on high dimensional data sets圖4 在高維數據集上的特征選擇結果

Fig. 5 Comparisons of MSE1 and MSE2 on D3圖5 3種方法在D3數據集上的MSE1和MSE2比較結果

Fig. 6 Comparisons of MSE1 and MSE2 on D4圖6 3種方法在D4數據集上的MSE1和MSE2比較結果

4 結 語

目前針對回歸問題的特征選擇方法研究較少，特別地，當數據集含有異常點時，現有的特征選擇方法幾乎都不能很好地選出有效特征.本文提出的面向異常點的穩健回歸特征選擇方法AWLASSO，通過自適應正則項自主更新損失函數權重，進而迭代估計回歸系數.AWLASSO的迭代過程總是朝著較好的回歸系數估計值方向進行，在迭代后期其訓練集含有足夠的樣本，因而其獲得了較好的實驗結果.此外算法可以排除異常點的影響，故其能較好地同時完成特征選擇和學習器訓練.與經典的LASSO和LAD-LASSO相比，本文提出方法更穩健、更稀疏，即使異常點含量較多該方法依然有效.然而該方法中的正則參數λ對方法性能有一定影響，如何進一步提高方法的穩健性是我們未來的研究工作.