CSRimpute算法填補(bǔ)效果的正則化參數(shù)靈敏度分析

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

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

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

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

1 引 言

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

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

2 CSRimpute算法介紹

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

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

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

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

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

該算法的具體過(guò)程如下：

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

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

過(guò)程：

（1）將原始數(shù)據(jù)集X轉(zhuǎn)化為二進(jìn)制矩陣A。在xi的第j個(gè)分類屬性行所對(duì)應(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個(gè)數(shù)據(jù)對(duì)象都是完整的；

（3）應(yīng)用K最近鄰作為字典構(gòu)造方法，針對(duì)AM中的每個(gè)缺失數(shù)據(jù)對(duì)象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）計(jì)算am*和AN（m）*中每個(gè)數(shù)據(jù)對(duì)象的歐幾里得距離，根據(jù)公式，

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

3 實(shí)驗(yàn)分析

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

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

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

4 結(jié) 論

本文針對(duì)CSRimpute算法中的正則化參數(shù)該如何選擇的角度出發(fā)，通過(guò)4個(gè)數(shù)據(jù)集驗(yàn)證分析了 λ1和λ2對(duì)算法填補(bǔ)效果的影響。實(shí)驗(yàn)結(jié)果表明，缺失數(shù)據(jù)的填補(bǔ)效果隨著正則化參數(shù)在最優(yōu)值附近較為平穩(wěn)的變化，即CSRimpute算法受正則化參數(shù) λ1和λ2變化的影響并不明顯，在實(shí)際應(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）.