CSRimpute算法填補效果的正則化參數靈敏度分析

[摘 要] 傳統的數據挖掘研究開展的前提是數據對象各個屬性擁有確定值，而在一般的高維數據研究中，人們所能收集到的數據往往是不完全的，即存在缺失數據。現有主要方法大多是將缺失數據填補問題擴展為對象之間的相似度計算問題。其中，分類屬性有別于數值屬性，難以直接進行數學計算衡量相似度。 CSRimpute算法引入稀疏表示理論完成對分類屬性缺失數據的填補，其在分類屬性數據集上相比其他傳統方法具有一定的優勢。文章重點分析了CSRimpute算法在4個數據集中的缺失數據填補效果是如何受到l1范數和l2范數正則化項的影響，實驗結果表明CSRimpute算法對正則化參數的選擇并不十分敏感。

[關鍵詞] 稀疏表示；缺失數據填補；分類屬性

doi ： 10 . 3969 / j . issn . 1673 - 0194 . 2016. 23. 084

[中圖分類號] TP301.6 [文獻標識碼] A [文章編號] 1673 - 0194（2016）23- 0159- 04

1 引 言

稀疏表示理論[1]是機器學習領域近幾年出現的新方法，其應用最小化l1范數[2]的優化方法獲得基于過完備字典特征表示的稀疏向量，是獲取、表示數據的有效工具。在現有的分類研究應用中，稀疏表示獲得了比傳統方法更好的分類性能，已成功應用于人臉識別、語音識別等信號和圖像識別領域[3]。另一方面，傳統的數據挖掘理論研究需要數據完整而確定，但在實際應用中，由于數據測量誤差、獲取限制、存儲介質故障等原因，人們所能收集到的數據往往存在缺失現象。應對數據缺失現象的常規做法是尋求合適的算法進行缺失數據填補。相較于能夠直接進行數值計算的數值型屬性，在處理分類屬性時，由于其不具備直接進行數值計算的原理，需要進行相應處理后方可進行填補[4]。

基于上述情況，Shao，et.al提出了基于K最近鄰局部約束稀疏表示的分類屬性缺失數據填補方法CSRimpute（Categorical Sparse Representation imputation）[5]。該方法針對分類屬性缺失數據的特點，利用完整數據設計字典，在保留局部結構特征的同時改善分類屬性缺失數據的填補效果。

2 CSRimpute算法介紹

CSRimpute算法是在局部約束稀疏表示的基礎上，結合K最近鄰算法設計字典，力圖解決缺失數據的填補問題。 該算法可以適用于包含一個缺失值或被推廣到包含多個缺失值的數據對象上。為了方便說明，需要定義一些概念如下：

X=[x1，x2，…，xi，…，xn]∈Cm×n表示一個包含n個數據對象的分類屬性數據集。

列向量xi∈Cm×1表示第個數據對象：

xi=[xi1，x12，…，xim]T∈Cm

第i個數據對象在第j個屬性上的缺失值成為缺失屬性值，記做：X（j，i）=xi（j）=xij =“*”。分類數據集共有m個屬性行，每個屬性行分別有cj種取值，且c1+c2+…+cm=M。

該算法的具體過程如下：

輸入：含有缺失數據對象的數據矩陣X=[x1，x2，…，xi，…， xn]∈Cm×n；正則化約束參數λ1，λ2>0；字典包含原子數據對象數量k；

輸出，填補后的完整數據集X；

過程：

（1）將原始數據集X轉化為二進制矩陣A。在xi的第j個分類屬性行所對應的cj行中，僅在代表其取值的屬性行取值為1，其他取值為0；若屬性缺失，則cj行取值均為0；

（2）將A劃分為A=[AC AM] 兩部分，其中完整數據集AC =[a1，a2，…，ac，…，anc]∈Cm×nc，缺失數據集AM =[anc+1，anc+2，…， am，…，anc+nm]∈Cm×nm，假設A中前nc個數據對象都是完整的；

（3）應用K最近鄰作為字典構造方法，針對AM中的每個缺失數據對象am分別構造字典AN（m）=[aN（1），…，aN（k），…，aN（K）]∈ CM×K，重復步驟4至步驟7；

（4）將am和AN（m）在所有am非缺失屬性上進行投影得到am*和AN（m）*，即去除am中的所有的缺失屬性并在AN（m）中移除相應的屬性；

（5）計算am*和AN（m）*中每個數據對象的歐幾里得距離，根據公式，

（8）算法結束，輸出填補后的數據矩陣X。

3 實驗分析

本實驗從UCI機器學習數據庫中選擇了4個經典的分類屬性數據集（Soybean，ZOO，SPECT Heart，Chess）。為了將原始數據值和填補估計值進行對比，針對每個數據集，首先刪除其中包含缺失屬性值的數據對象，得到完整數據集。然后，隨機選取數據集中的部分數據對象構成缺失對象數據集，對于每個被選取的數據對象，從中隨機選擇一定數量的屬性值，人為地將這些屬性值設定為缺失屬性值。

設計本試驗的目的是測試正則化參數l1和l2的敏感性。為了便于操作，將缺失屬性比率和缺失數據集的比率均設定為20%。對于設定的正則化參數，分別選取它們的2n倍計算缺失填補正確率，結果如表1、表5所示。

從前3張表中可以看出，在4個數據集中，無論如何變化，算法的填補正確率相對都比較平穩，沒有出現大幅度增加或減少的情況。兩個正則化參數 λ1和λ2的變化使得CSRimpute的填補效果略有浮動，但浮動的范圍較小，并未過度偏離最優結果。最后的統計表顯示，Soybean和Chess數據集的極差和標準差較小，而ZOO和SPECT Heart數據集的極差和標準差相對較大。這在一定程度上說明正則化參數 λ1和λ2對填補效果的影響在較大數據集的情況下反而較小，這是因為在較大數據集中能夠更容易找到與目標數據對象更相似的數據，從而能夠得到更加理想的稀疏表示。

4 結 論

本文針對CSRimpute算法中的正則化參數該如何選擇的角度出發，通過4個數據集驗證分析了 λ1和λ2對算法填補效果的影響。實驗結果表明，缺失數據的填補效果隨著正則化參數在最優值附近較為平穩的變化，即CSRimpute算法受正則化參數 λ1和λ2變化的影響并不明顯，在實際應用中能夠比較容易確定。

主要參考文獻

[1]Wright J， Yang A Y， Ganesh A， et al. Robust Face Recognition via Sparse Representation[J]. Pattern Analysis and Machine Intelligence， IEEE Transactions on， 2009， 31（2）： 210-227.

[2]Candès E J， Romberg J， Tao T. Robust Uncertainty Principles： Exact Signal Reconstruction from Highly Incomplete Frequency Information[J]. Information Theory， IEEE Transactions on，2006，52（2）：489-509.

[3]Duan C H， Chiang C K， Lai S H. Face Verification with Local Sparse Representation[J]. Signal Processing Letters， IEEE，2013，20（2）： 177-180.

[4]Shekhar S， Patel V M， Nasrabadi N M， et al. Joint Sparse Representation for Robust Multimodal Biometrics Recognition[J]. Pattern Analysis and Machine Intelligence， IEEE Transactions on，2014，36（1）：113-126.

[5]Shao X， Wu S， Feng X， et al. Categorical Missing Data Imputation Approach via Sparse Representation[J]. International Journal of Services Technology and Management，2016，22（1）.