基于概率矩陣分解的不完整數據集特征選擇方法

范林歌，武欣嶸，童 瑋，曾維軍

（中國人民解放軍陸軍工程大學 通信工程學院，南京 210007）

0 概述

高維數據在實際應用中普遍存在，這些數據通常被用來構建高質量的機器學習模型，隨后進行數據挖掘分析，但高維數據具有計算時間長、存儲成本高等問題［1-2］。為了解決這些問題，研究人員提出特征選擇、主成分分析等降維方法［3-4］。特征選擇是數據挖掘過程中的重要步驟，特別是在許多生物信息學任務中，有效的魯棒特征選擇方法可以提取有意義的特征并且消除有噪聲的特征。

現有的特征選擇方法大多以數據是完整的或幾乎完整的為前提。但在許多實際應用中，例如生物信息學［5］和遙感網絡普遍存在數據缺失，現有的特征選擇方法大部分不能直接用于包含缺失值的數據集。

對不完整數據集進行特征選擇，最直接的方法是對不完整數據集進行一定處理使其保持形式上的完整，然后再做特征選擇。處理缺失數據最簡單易行的方法是完整樣本分析（Complete Case Analysis，CCA），即刪除包含缺失值的樣本或特征［6］。該方法雖然簡單易行，但在缺失樣本比例較高和樣本總量較小時有很大的局限性，進而影響后續機器學習的準確性。對缺失位置進行填充是另一種較為直接的缺失數據處理方法，應用普遍的是均值填充。均值填充是指以特征觀測值的均值作為缺失值的估計值［7］，但該方法會使特征不確定性或方差減小。還有一種基于統計學的缺失填補方法是期望最大化（EM）填補法［8］，該方法利用現有數據的邊緣分布對缺失數據進行極大似然估計，從而得到相應的填補值。ZHANG 等［9］提出了k 近鄰填充，該方法基于近鄰樣本的特征值相近的假設，以近鄰樣本的均值作為缺失值的估計值。之后一些改進的k 近鄰填補方法被提出，其引入灰色關聯分析和互信息來更進一步地提高分類精度和填補效果［10-13］。近鄰填充的關鍵在于準確地度量近鄰關系，這也帶來了一些不足：不同的特征在相似度度量中的重要性是不同的，而k近鄰填充中的距離計算將所有特征同等對待；當數據特征數目較多即在高維特征空間中時，樣本分布趨于均勻，此時距離并不能反映樣本相似性。

在不填充直接進行特征研究方面，LOU 等［14］提出基于類間隔的不完整數據特征選擇（Feature Selection in Incomplete Data，SID）方法，定義了基于類間隔的目標函數，對其優化使每個樣本在其相關子空間中的類間隔最大化，以權重范數比為系數降低缺失樣本對于類間隔計算的貢獻，該方法不再將某個樣本的近鄰樣本當作是固定的，而是去計算所有樣本是某個樣本近鄰樣本的概率。SID 特征選擇最終學習出一個特征權重向量w，w中取值較大的分量對應重要特征，取值較小的分量對應次要特征，取值為零的分量對應無關特征甚至噪音特征。與基于常用預處理填充方法（如均值填充、EM 填充、k 近鄰填充）的特征選擇相比，SID 能夠篩除更多無關特征，以該算法選擇的特征建立的分類模型分類準確率更高，但其沒有考慮異常值的影響。

本文針對不完整數據中含有未被觀察信息和存在異常值的特點，提出一種基于概率矩陣分解（Probability Matrix Decomposition，PMF）技術的魯棒特征選擇方法，使用指示矩陣并利用不完整數據集中的所有信息進行缺失值近似估計。在特征選擇算法上基于魯棒特征選擇（Robust Feature Selection，RFS）方法，在損失函數和正則化項中聯合使用?2，1范數［15-16］，將?2，1范數作為損失函數可減輕異常值影響，提升特征選擇的魯棒性。

1 基于矩陣分解的缺失值填充方法

考慮不完整數據集X={(xn，yn|n=1，2，…，N)}∈RM，其中N為樣本數，M為特征數，xn為第n個給定實例，yn為其對應的標簽值，yn=1，2，…，T，xn(j)表示第n個樣本的第j個特征，其中j=1，2，…，M。

由于直接使用不完整數據集中所有實例來預估缺失值計算量較大，本文首先使用原始標簽將原始數據集分簇，將相似度較高的樣本分為一簇，假設第i簇數據集為Xi，每一簇數據集實例選擇如式（1）所示：

其包含L個實例，Xi具體表示如式（2）所示：

其中：q=1，2，…，L，表示第i簇數據集中第q個實例的第j個特征。

本文基于這樣一個假設：同一簇內兩個樣本相似度比不同簇的兩個樣本高，以達到在減少計算量的基礎上不降低填充準確性的目的，之后分別對每簇中的缺失值進行估計。

在計算過程中利用指示矩陣對未觀察到的信息進行過濾，從而達到利用完整和不完整樣本中所有有效信息的目的。對于給定的不完整數據集X，定義指示矩陣I，其中In（j）反映第n個實例的第j個特征的缺失情況，元素取值如式（3）所示，當xn(j)可觀測時對應位置取1，當xn(j)缺失時對應位置取0。

則第i簇數據集Xi對應的指示矩陣為Ii。

1.1 矩陣分解

尋找第i簇數據集Xi的一個近似矩陣，通過求解近似矩陣來代替原始數據簇中缺失的值，定義如式（4）所示：

其中：U∈RL×K；V∈RM×K，矩陣U和V分別表示數據集實例和特征特定的潛在特征向量。比如在一個用戶對多部電影評分的數據集中，xq(j)表示第q個用戶對第j部電影的評分，此時U和V分別描述用戶的特征（比如年齡段等）和電影的特征（比如年份、中英文等）。

均方根誤差（RMSE）可以用來衡量真實值與預估值之前的差距，本文通過計算目標矩陣Xi與近似矩陣的RMSE 來評估模型性能，Xi與的RMSE定義如式（6）所示：

由式（5）得：

代入式（6）得：

RMSE 值越小則表示填補效果越好。本文通過求解一組U和V使相似矩陣與目標矩陣Xi的RMSE 最小，至此該優化問題可以表示為：

至此，將上述問題轉化為一個無約束優化問題，本文采用梯度下降法［18］迭代計算U和V，首先固定V，對U求導，如式（10）所示：

更新uq，如式（11）所示：

其中：α為更新速率，表示迭代的步長。

固定U，對V求導得：

更新vj，如式（13）所示：

重復式（11）與式（13），迭代優化U和V，直到RMSE<ξ，ξ為自定義誤差。

遍歷所有i，對每一簇數據進行如上操作，直到Iο等于0 即數據集無缺失為止。至此，求出Xi的近似矩陣，用中的數據填充Xi中對應位置的缺失值。Iο定義如式（14）所示：

1.2 概率矩陣分解

為提升算法精度以及降低算法運算復雜度，本文將上述的矩陣分解擴展為概率矩陣分解。假設數據集第i簇數據集Xi，歸一化后服從均值為μ=0，方差為σ2的高斯分布。因此，可定義U和V為一個多變量的零均值球面高斯分布，如式（15）、式（16）所示：

該先驗概率可使式（11）和式（13）最終的收斂值不會遠離0，從而避免了矩陣U和V出現幅度較大的值。若無該先驗知識，1.1 節中的矩陣概率分解迭代運算次數將增加，運算復雜度提升。

綜合上述兩個先驗概率，可將數據集X上的取值條件概率分布定義為：

基于式（15）、式（16）、式（17）的概率密度函數，利用經典的后驗概率推導可以得到p(U，V|X)=p(X|U，V)p(U)p(V)，最大化該后驗概率，就可以通過已有的近似矩陣估計出系統參數U和V。

為了計算方便，對后驗概率取對數，在觀測噪聲方差和先驗方差保持固定的情況下，最大化該對數后驗分布等價于使用二次正則化項使誤差平方和最小。最后，為了限制數據集中數據的取值范圍，對高斯函數的均值施加logistic 函數g(x)=1/(1+exp(-x))，其取值在（0，1）之間。最終的能量函數為：

至此，可以使用梯度下降方法，求解Ui、Vj中的每一個元素。

2 魯棒特征選擇算法

2.1 魯棒特征選擇

為增強算法面對異常值時的魯棒性，本文采用基于?2，1范數的損失函數來去除異常值，而不使用對異常值敏感的?2范數損失函數。以最小二乘回歸為例，使用?2，1魯棒損失函數后目標函數如式（19）所示：

其中：γ為正則化項參數；W∈RM×C。

將上述目標函數變為帶約束的形式，如式（20）所示：

將上述的問題改寫為：

使A=[XTγH]，B=，其中H∈RN×N為單位矩陣，則目標函數進一步改寫成式（22）：

RFS 使用一個非常簡單的方法來求解式（22），同時這種方法也很容易應用到其他一般的?2，1范數最小化問題中。

該算法主要基于拉格朗日方法，構造拉格朗日函數如下：

求上式對B的偏導并令其為0，得到式（24）：

其中：D是對角矩陣。

第n個元素為：

在式（24）兩邊同乘AD-1，并有AB=Y，得式（26）：

將式（26）代入式（24），得：

由于式（22）中的問題是一個凸問題，當且僅當滿足式（27）時，B是該問題的全局最優解。其中，D依賴于B，因此也是一個未知變量。依然使用迭代算法來獲得滿足式（27）的解B：在每次迭代中，用當前的D計算B，然后根據當前計算的B更新D。不斷重復迭代過程，直到算法收斂。具體描述如算法1所示。

2.2 算法分析

本文提出的算法在每次迭代計算中都單調地減少式（22）中問題的目標。

引入以下引理對其進行證明：

引理1對于任意非零向量b，bt∈Rc，以下不等式成立：

算法的收斂性總結為以下定理：

將式（29）中的v和vt分別帶入，可以得到式（28）。

定理1算法每次迭代都會單調地降低式（22）中問題的目標，并收斂于問題的全局最優。

證明可以驗證式（27）是以下問題的解：

因此在t次迭代中：

這表明：

即：

根據引理1，對每個i有：

因此，以下不等式成立：

結合式（33）和式（35）可以得到：

即：

因此，本文提出的算法在每次迭代中將單調地降低式（22）中問題的目標。在收斂性上，Bt和Dt滿足式（27），又因為式（22）是一個凸問題，所以滿足等式（27）表示B是式（22）的全局最優解，因此，算法將收斂于問題式（22）的全局最優。

3 實驗與結果分析

為了檢驗所提算法的有效性，本節分別在合成數據集和真實數據集上進行實驗，在不完整數據集中比較了本文提出的PMF、SID 算法、傳統的先填充再進行特征選擇算法，其中傳統方法中的填充算法分別為概述中介紹的均值填充（mean）、KNN 填充、EM 填充，特征選擇算法為本文使用的魯棒特征選擇算法RFS 和兩種基于邊緣的特征選擇算法：Simba［19］和Relief［20］，分別將以上幾種算法交叉組合形成9 套完整的針對不完整數據集進行特征選擇的流程，以評估本文所提算法在高維數據上的分類性能。

本節使用分類精度（ACC）作為評估指標。ACC表示樣本分類正確的百分比，即：

其中：N是樣本總數；Nc為正確被分類的樣本個數。

3.1 實驗設置

本實驗環境為MATLAB2019a，為了觀察缺失率對算法的影響，本節人工隨機地向數據集注入不同比例的缺失值。缺失率范圍為5%～65%，以10%為間隔遞增，本文缺失率定義為缺失值占所有值的百分比。在此僅考慮缺失機制為完全隨機缺失的情況。為了體現特征選擇算法的效果，具體地，本文會向特征較少的數據集中添加一些無關特征，實驗中向數據中添加的無關特征并不被注入缺失。

如前所述，K為矩陣U和V的維度，當其取不同值時均方根誤差的收斂速度如圖1 所示，這里分別取K=1，5，10，15，20，可以看到：當K=1，5 時收斂速度較慢并且無法收斂到0，當K=10，15，20 時均方根誤差收斂較快，并且可以收斂到0，可見，K的取值不光影響均方根誤差收斂速度，還會影響最終收斂結果。為了不增加計算量并且防止過擬合，本文所有實驗均設置K值取10。

圖1 不同K 值時均方根誤差隨迭代次數的變化Fig.1 Variation of root mean square error with iteration times at different K values

不止K的取值，學習速率α的取值不同也會影響均方根誤差的收斂速度，如圖2 所示，α分別取0.1、0.01、0.001、0.000 1，由圖2 可見，α取0.01 時收斂速度最快，α取0.000 1 時收斂速度最慢，可見步長越小，損失函數到達底部的時間越長，步長越大，損失函數收斂越快，但步長并不能無限大，經過實驗發現當α取0.1 時，目標函數不會收斂，所以在該合成數據集上α取0.01。經過在不同數據集上的實驗也發現，同一個步長并不適用于所有數據集，所以要通過多次實驗發現最適合本數據集的步長，本文中所有數據集步長設置均經過多次實驗，設其為最恰當的數值。

圖2 不同α 值均方根誤差隨迭代次數變化Fig.2 Variation of root mean square error with iteration times at different α values

3.2 數據集合成

本節通過設計合成數據集來評價本文算法在存在大量不相關變量的不完整數據中填充缺失值后選擇出相關特征的能力。合成數據集包含500 個實例和100 維特征。其中兩維特征是隨機產生的0、1 序列，將這兩維特征做異或運算，產生結果即為合成數據集的標簽，剩下的98 個特征服從于以0 為均值、1為方差的標準正態分布。

本節以所選擇的無關特征數目為標準評價特征選擇方法。為了簡便期間，只比較本文提出的算法與SID 算法，以及使用LBFS 算法作為特征選擇算法的3 種傳統方法，實驗結果如圖3 所示。

圖3 無關特征數隨缺失率的變化Fig.3 Variation of irrelevant feature number with deletion rate

由圖3 可以看出，在該數據集上，KNN 填充的方法選擇出的無關特征數目最多，效果最差，本文提出的算法PMF 效果最好，在缺失比例較高的情況下依然能選擇出較少的無關特征。SID 算法在缺失率較低的情況下效果較好，但在缺失率較高時不如PMF。

3.3 真實數據集

本節分別從LIBSVM 數據網站、UCI website［21］、肯特崗生物醫學數據集等網站下載DLBCL、Mnist、Splice、Wpbc、USPS、Arcene 6 個真實數據集。由于生物醫學方面數據集往往包含大量冗余特征，更能體現出特征選擇的作用，本節選用的數據集大部分與生物醫學有關。DLBCL 為彌漫大B 細胞淋巴瘤基因的相關數據集，Splice 是關于識別DNA 序列中兩種類型的剪接點的數據集，Wpbc 數據集則取自威斯康辛大學校醫院的乳腺癌病例數據庫，Arcene 原始數據來自于美國國家癌癥研究中心和東維多利亞醫學院，收集了通過SELDI 技術采集的癌癥病人和健康人的質譜信息，用于癌癥預測。由于Splice 和Wpbc 數據集特征較少，這里人為的向其添加2 000 個無關特征，無關特征的特征值均通過從正態分布N（0，1）中抽樣得到。數據集詳細信息如表1所示。

表1 數據集詳細信息Table 1 Datasets detailed information

對于真實數據集，因為無法預知其中特征的重要性，所以使用分類準確率為標準評價特征選擇方法。在訓練集上先進行特征選擇，之后對所選特征進行分類，分類準確率高說明特征選擇的效果越好。

使用交叉驗證方式［22］選擇最佳參數組合，將原始數據集分為70%的訓練集和30%的測試集，其中訓練集的類標簽是已知的，假設測試集的類標簽未知，通過在訓練集上訓練得到分類器來預測測試實例的類標簽，比較預測得到的類標簽與真實的類標簽就可以得到該分類器的分類精度。本實驗使用SVM 分類器進行訓練。對于基于KNN 填充進行的特征選擇，本文選取k=5。

各算法在DLBCL 數據集上的分類效果柱狀圖如圖4 所示，其中縱坐標為分類準確率，橫坐標依次展示11 種不同的算法，不同底紋代表不同的缺失率，這里選取了缺失率為25%、35%和55%時的分類結果，可以看到，本文提出的算法在不同缺失率時準確率都高于其他10 個算法，均值填充的3 種算法在該數據集上的整體表現略高于KNN 填充和EM 填充，并且3 種不同的特征選擇算法效果相差不大，SID算法效果僅次于PMF，因為其利用了不完整數據集中的全部信息，但該算法沒有考慮異常值的影響。

圖4 不同缺失率下DLBCL 數據集的分類準確率Fig.4 Classification accuracy of DLBCL dataset under different miss rates

各算法在Mnist 數據集上的分類效果如圖5 所示，可以看到，在缺失率較高的情況下，本文提出的算法依然能達到90%的準確率，在該數據集中用KNN 填充的3 種算法效果較差，可能是該數據集比較稀疏導致近鄰關系度量不夠準確，EM 填充與SID算法效果相差不大，略高于均值填充。

圖5 不同缺失率下Mnist 數據集的分類準確率Fig.5 Classification accuracy of Mnist dataset under different miss rates

各算法在Splice 數據集上的分類效果柱狀圖如圖6 所示，可以看到，基于KNN 填充的算法效果較差，在缺失率為25%時只可以達到70%左右的準確率，PMF 在相同缺失率時可以達到80%以上的準確率，可見PMF 在該數據集上效果有了較大的提升。基于均值填充的算法和SID 算法效果較為接近。

圖6 不同缺失率下Splice 數據集的分類準確率Fig.6 Classification accuracy of Splice dataset under different miss rates

各算法在Wpbc 數據集上的分類效果柱狀圖如圖7 所示，可以看到，在該數據集上各個算法的分類準確率普遍較低。在該數據集上基于KNN 填充的算法效果較差，均值填充在25%缺失率時的效果較好，在KNN 填充和均值填充上RFS 特征選擇算法的效果比Simba 和Relief 略高。相比其他算法，本文提出的算法在該數據集上效果依然是最好的。

圖7 不同缺失率下Wpbc 數據集的分類準確率Fig.7 Classification accuracy of Wpbc dataset under different miss rates

各算法在USPS 數據集上的分類效果柱狀圖如圖8 所示，可以看到，本文提出的算法在該數據集上效果較好。在缺失率為5%時，所有算法的分類準確率都高達92%左右，但是隨著缺失率增大到55%，其他算法的分類效果有了明顯下降，此時本文提出的算法優勢更加明顯。相比之前的基于填充的算法，SID 算法在該數據集上并不具有明顯的優勢。

圖8 不同缺失率下USPS 數據集的分類準確率Fig.8 Classification accuracy of USPS dataset under different miss rates

各算法在Arcene 數據集上的分類效果如圖9 所示，可以看到，本文提出的算法在該數據集上的優勢非常明顯，其他10 種算法在所有缺失比例時的準確率基本都在60%左右，然而PMF 算法可以達到90%左右的準確率，可見本文提出的算法非常適用于該數據集，這應該與數據集本身有關。

圖9 不同缺失率下Arcene 數據集的分類準確率Fig.9 Classification accuracy of Arcene dataset under different miss rates

3.4 異常值檢測

本節使用3.2 節中的合成數據集進行異常值檢測，為了方便展示，人工隨機地向數據集注入不同比例的異常值，這里使用固定值來模擬異常值。分別在異常值比率為1%、2%、3%時進行實驗求無關特征，異常值比率定義為注入異常值的數量占整個數據集的百分比，結果如表2 所示，本文固定缺失值比率為5%。從表2 的數據可以看出，在異常值比例較低時，本算法能篩選出所有的重要特征，隨著異常值比率增加，篩選出的無關特征數目有所增加，但仍然保持較低的數量，可見本文算法可以在一定程度上應對不完整數據集中異常值帶來的影響。

表2 不同比例異常值與無關特征數目Table 2 Different proportion outliers and irrelevant features number

綜上所述，基于KNN 填充算法在Mnist 和Splice數據集上效果較差，雖然該算法利用樣本近鄰關系來進行填充，在一定程度上更多地利用了不完整數據集的信息，但是近鄰關系度量的準確性也會對填充效果造成影響。基于均值填充算法與EM 填充算法效果略高于KNN 填充算法、SID 算法效果僅次于本文算法，因為該算法使用指示矩陣利用了不完整數據集中的全部信息，但是它沒有考慮數據集中異常值的影響。PMF 算法效果最好，因為其不僅充分利用了不完整數據集中的所有有效信息，還使用?2，1范數作為損失函數，增強了其應對異常值的魯棒性，所以與其他算法相比，在所有數據集上分類準確率都有所提升。

4 結束語

高維數據集中通常包含缺失值和離群值，對其進行降維是數據挖掘的重要步驟之一。本文針對不完整數據中含有未被觀察信息和存在異常值的特點，提出一種基于概率矩陣分解技術的魯棒特征選擇方法。該方法引入指示矩陣利用數據集中全部信息，對不完整數據集進行近似估計，在考慮異常值情形下，利用?2，1范數對數據點中異常值具有魯棒性的特點，將其作為回歸損失函數，實現魯棒特征選擇。實驗結果表明，該方法能夠充分利用不完整數據集中的所有信息，避免繁瑣的距離運算，可有效應對不完整數據集中異常值帶來的影響。下一步考慮將概率矩陣分解填充拓寬到半監督或無監督的特征選擇流程上，在數據集標簽有缺失甚至無標簽的情況下，提升特征選擇的效果。