邵曉晨+宋蕊

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

[關(guān)鍵詞] 稀疏表示；缺失數(shù)據(jù)填補；分類屬性

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

[中圖分類號] TP301.6 [文獻(xiàn)標(biāo)識碼] A [文章編號] 1673 - 0194（2016）23- 0159- 04

1 引 言

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

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

2 CSRimpute算法介紹

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

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

列向量xi∈Cm×1表示第個數(shù)據(jù)對象：

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

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

該算法的具體過程如下：

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

輸出，填補后的完整數(shù)據(jù)集X；

過程：

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

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

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

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

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

（8）算法結(jié)束，輸出填補后的數(shù)據(jù)矩陣X。

3 實驗分析

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

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

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

4 結(jié) 論

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

主要參考文獻(xiàn)

[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）.