帶組內(nèi)互斥信息的判別最小二乘特征選擇方法

鄭 蓉，魏碧劍，朱文龍（溫州大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，浙江溫州 325035）

?

帶組內(nèi)互斥信息的判別最小二乘特征選擇方法

鄭 蓉，魏碧劍，朱文龍
（溫州大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，浙江溫州 325035）

摘 要：帶組內(nèi)互斥信息的判別最小二乘特征選擇方法，通過考慮特征互斥信息，既保證了那些重要特征的選擇，又兼顧了特征表達(dá)的廣泛性．判別最小二乘模型能夠最大化異類數(shù)據(jù)的分布，使不同類別的距離被擴(kuò)大；另外，組內(nèi)特征互斥項(xiàng)可以使模型盡可能地選擇那些既重要、又互不相似的特征，從而獲得重要的特征子集．對在現(xiàn)實(shí)世界中采集的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，結(jié)果表明，帶組內(nèi)互斥信息的判別最小二乘特征選擇方法比已有的判別最小二乘特征選擇方法在數(shù)據(jù)分類問題中具有更好的效果．

關(guān)鍵詞：特征選擇方法；最小二乘回歸；特征相似度

在現(xiàn)實(shí)生活中，人們可以從互聯(lián)網(wǎng)上獲取圖像、文本、語音等多媒體信息，但是這些信息往往有很高的維數(shù)，可能包含著太多冗余的、無關(guān)的干擾信息，從而占用很大的存儲空間．特征選擇是一種數(shù)據(jù)預(yù)處理技術(shù)，可以將高維數(shù)據(jù)轉(zhuǎn)換成容易處理的低維數(shù)據(jù)，且能保留數(shù)據(jù)的大部分內(nèi)在信息．在模式識別和機(jī)器學(xué)習(xí)中，特征選擇也是分類算法中的一個(gè)主要步驟．一般地說，特征選擇通常是選擇與類別相關(guān)性較強(qiáng)、且特征彼此間相關(guān)性較弱的特征子集，這樣不僅可以節(jié)省存儲空間，消除噪聲，還有利于完成分類或者識別任務(wù)，提高分類器效率．目前關(guān)于特征選擇的研究成果已有很多［1］，但如何能更好地進(jìn)行特征選擇仍然是很有挑戰(zhàn)性的工作，對其研究仍有重要意義．

最小二乘回歸（Least Squares Regression）是廣泛使用的數(shù)據(jù)分析技術(shù)，它有很多變形算法，例如加權(quán)最小二乘回歸、偏最小二乘回歸［2］．另外，最小二乘回歸現(xiàn)已被成功用于解決許多機(jī)器學(xué)習(xí)的問題，例如流形學(xué)習(xí)［3］、聚類、半監(jiān)督學(xué)習(xí)［4-5］、多任務(wù)學(xué)習(xí)［6］、多分類學(xué)習(xí)等．給定數(shù)據(jù)集和目標(biāo)集合，若第i個(gè)輸入數(shù)據(jù)屬于第j類，則對應(yīng)的類別標(biāo)簽即輸出數(shù)據(jù)中只有第j個(gè)元素是1，其余都是0．一般地，最小二乘回歸可以寫成如下的形式：

1　已有的特征選擇方法

以是否將數(shù)據(jù)的類別標(biāo)簽考慮進(jìn)去為依據(jù)，特征選擇算法可以分為三類：無監(jiān)督特征選擇算法［7］、有監(jiān)督特征選擇算法［1， 8］、半監(jiān)督特征選擇算法［4］．具體如下．

1.1無監(jiān)督算法

無監(jiān)督特征選擇算法沒有考慮數(shù)據(jù)的類別標(biāo)簽，而是通過特征之間內(nèi)在相互關(guān)系或結(jié)構(gòu)特征，或者運(yùn)用數(shù)據(jù)的方差或分離性特征對各個(gè)特征的重要性進(jìn)行判斷，從中篩選出重要的特征．在無監(jiān)督特征選擇中，因?yàn)闆]有根據(jù)類別信息進(jìn)行特征選擇，所以因而失去了一個(gè)重要的判別依據(jù)，這也就增加了技術(shù)研究的難度．目前關(guān)于無監(jiān)督特征選擇方面的研究相對較少，常見的無監(jiān)督特征選擇方法有：主成分分析法（PCA）、拉普拉斯評分法（Laplacian Score）［9］、方差法等．主成分分析也稱主分量分析，是特征提取中最經(jīng)典的算法之一．主成分分析是基于數(shù)據(jù)之間是線性關(guān)系的假設(shè)，通過線性投影得到低維表示，并且保持原始數(shù)據(jù)協(xié)方差結(jié)構(gòu)．所得的低維表示則是算法所選擇的主成分，可以反映原始數(shù)據(jù)的大部分信息，揭示隱藏在原始數(shù)據(jù)中的簡單結(jié)構(gòu)．主成分分析具有簡單、無參數(shù)限制的優(yōu)點(diǎn)，并且有很好的魯棒性．拉普拉斯評分是一種基于相關(guān)系數(shù)的特征選擇算法，目前已得到比較廣泛的應(yīng)用．拉普拉斯評分以保持流形局部近鄰信息為目標(biāo)，可以反映數(shù)據(jù)集嵌入低維流形的內(nèi)在幾何結(jié)構(gòu)，能夠比較準(zhǔn)確地找到重要的特征，但對于帶有類別信息的數(shù)據(jù)則不能較好地識別出來．方差法是一種比較成熟的算法，該算法的評價(jià)準(zhǔn)則比較簡單，根據(jù)方差得分進(jìn)行特征重要性排序．方差法已經(jīng)得到廣泛應(yīng)用，但該算法容易受到噪聲數(shù)據(jù)的干擾，從而使其準(zhǔn)確性受到了影響．

1.2有監(jiān)督算法

有監(jiān)督特征選擇算法，利用特征與類別信息之間的關(guān)系，選擇出一個(gè)最具類別區(qū)分能力的特征子集，是目前廣泛使用的一種機(jī)器學(xué)習(xí)方法．一般情況下，與無監(jiān)督特征選擇算法相比，有監(jiān)督特征選擇算法的效果要好一些，且算法的計(jì)算復(fù)雜度較低．有監(jiān)督學(xué)習(xí)算法主要包括：支持向量機(jī)（SVM）、人工神經(jīng)網(wǎng)絡(luò)（ANNs）、決策樹學(xué)習(xí)［10］等．支持向量機(jī)是一種基于統(tǒng)計(jì)學(xué)習(xí)理論的機(jī)器學(xué)習(xí)方法，最初是針對線性問題提出的，只能用于解決線性分類問題．對于非線性問題，SVM成功引入了核函數(shù)，可以將非線性分類問題投影到高維空間變成線性可分問題，但由于SVM求解的是一個(gè)二次規(guī)劃問題，樣本維數(shù)越高，計(jì)算復(fù)雜度和耗時(shí)也越大．人工神經(jīng)網(wǎng)絡(luò)是20世紀(jì)80年代以來人工智能領(lǐng)域興起的研究熱點(diǎn)，它從信息處理的角度對人腦神經(jīng)元網(wǎng)絡(luò)進(jìn)行抽象，建立某種簡單模型，按不同的連接方式組成不同的網(wǎng)絡(luò)．決策樹是一種常用于預(yù)測模型的算法，它通過將大量數(shù)據(jù)有目的地分類，從中找到一些具有價(jià)值的、潛在的信息．

1.3半監(jiān)督算法

隨著數(shù)據(jù)采集和存儲技術(shù)的發(fā)展，很容易獲取大量的未標(biāo)簽樣例，但獲取大量已標(biāo)簽樣例則比較困難，需要耗費(fèi)大量人力和物力．很多實(shí)際數(shù)據(jù)集包含少量已標(biāo)簽樣例和大量未標(biāo)簽樣例，如果采用只利用少量已標(biāo)簽樣例的有監(jiān)督學(xué)習(xí)，那么訓(xùn)練得到的學(xué)習(xí)模型不會具有很好的泛化能力，同時(shí)也會由于沒有使用未標(biāo)簽樣例而造成浪費(fèi)，而如果采用無監(jiān)督學(xué)習(xí)，又會忽視了已標(biāo)簽樣例的價(jià)值．針對這類數(shù)據(jù)集，半監(jiān)督學(xué)習(xí)有更好的學(xué)習(xí)性能．半監(jiān)督學(xué)習(xí)能夠同時(shí)利用已標(biāo)簽和未標(biāo)簽數(shù)據(jù)，結(jié)合無監(jiān)督特征選擇算法和有監(jiān)督特征選擇算法的優(yōu)點(diǎn)，通過一些分布上的假設(shè)，來預(yù)測未標(biāo)記數(shù)據(jù)的標(biāo)記并將其添加到已標(biāo)記的數(shù)據(jù)集中，訓(xùn)練新的分類器，提高分類器效果．目前，常用的半監(jiān)督學(xué)習(xí)方法有：產(chǎn)生式混合模型［11］、EM算法［12］、自我訓(xùn)練（self-training）、協(xié)同訓(xùn)練（co-training）［13］、直推式支持向量機(jī)（transductive support vector machines）［14］等．

2　判別最小二乘特征選擇算法

2.1符號介紹

為了避免混淆，在此給出本文所使用的主要符號．文中矩陣用大寫字母表示，數(shù)據(jù)點(diǎn)都是列向量形式并用小寫字母表示，實(shí)數(shù)也是以小寫字母表示．矩陣的Frobenius范數(shù)定義為：

2.2判別最小二乘算法DLSR

可以獲得n個(gè)訓(xùn)練樣本的關(guān)系：

B中的每個(gè)元素代表牽引（dragging）方向．可以看出相同類別牽引方向是一致的，不同類別朝不同方向牽引．

注意到L2，1是一個(gè)范數(shù)，所以是一個(gè)凸函數(shù)．另外約束條件也是凸的，所以上式是凸的，結(jié)果只有一個(gè)全局最小值［15］．

基于最小二乘回歸模型改進(jìn)后的判別最小二乘回歸模型可以最大化異類數(shù)據(jù)的分布，擴(kuò)大不同類別的距離，但由于判別最小二乘特征選擇算法并沒有考慮原始數(shù)據(jù)特征之間的相關(guān)性信息，而保留這些相關(guān)性很高的特征又會影響分類器效率，所以不利于機(jī)器學(xué)習(xí)．針對該問題，本文提出了一種考慮特征之間相關(guān)性的判別最小二乘特征選擇算法．

3　帶組內(nèi)互斥信息的判別最小二乘特征選擇算法

3.1特征相似度

對原始數(shù)據(jù)的所有特征，先利用特征的相似度進(jìn)行特征分組處理，并在各組內(nèi)進(jìn)行特征選擇來達(dá)到組內(nèi)稀疏的效果．經(jīng)過以上處理可以排斥掉相似程度高的特征，使得保留下來的特征相似程度較低．第s個(gè)特征和第t個(gè)特征的相似度計(jì)算公式為：

這里，Rst表示第s個(gè)特征和第t個(gè)特征的相似度，Xis表示第i個(gè)樣本的第s個(gè)特征，同理Xit表示第i個(gè)樣本的第t個(gè)特征．由此可得到原始數(shù)據(jù)的特征之間的相似度矩陣為：

3.2分組進(jìn)行特征選擇

用特征相似度矩陣對特征進(jìn)行分組，可以手動設(shè)定或者由計(jì)算機(jī)隨機(jī)給出一個(gè)閾值，當(dāng)兩個(gè)特征相似度大于時(shí)，應(yīng)該保留該組特征，并將保留下來的各組依次命名為．通過投影矩陣W實(shí)現(xiàn)特征選擇，原始數(shù)據(jù)X的每個(gè)列代表一個(gè)特征對應(yīng)到W的每一行．本文的算法在進(jìn)行挑選組內(nèi)特征時(shí)就可以通過投影矩陣W的行向量的二范數(shù)來實(shí)現(xiàn)．因?yàn)橥唤M內(nèi)的兩個(gè)特征具有較大的相似度，所以最好選擇其中一個(gè)特征而排斥掉另一個(gè)特征來達(dá)到組內(nèi)特征稀疏的效果，這個(gè)效果可以通過極小化以下公式來達(dá)到：

（12）又可以命名為組內(nèi)特征互斥項(xiàng)，用來在各分組的組內(nèi)進(jìn)行特征選擇．其中jw表示W(wǎng)的第j個(gè)行向量，表示原始數(shù)據(jù)中第j個(gè)特征在Gk這個(gè)組內(nèi)．例如：當(dāng)，，時(shí)，則有：

這樣，在進(jìn)行特征選擇的時(shí)候，就可以排除掉相似度很高的特征，而選擇那些彼此不相似且比較重要的特征，從而達(dá)到更好的特征選擇效果．

3.3添加組內(nèi)特征互斥項(xiàng)到DLSR中

組內(nèi)特征互斥項(xiàng)添加到DLSR后可以表示為：

一般地，對（14）式中的第三項(xiàng)即組內(nèi)特征互斥項(xiàng)直接處理比較困難，目前存在的算法能夠計(jì)算，但是計(jì)算代價(jià)高．通過變形處理，可以把目標(biāo)函數(shù)的最后一項(xiàng)轉(zhuǎn)化為容易求偏導(dǎo)的形式．轉(zhuǎn)化后的形式如下：

最終，可以獲得帶組內(nèi)互斥信息的判別最小二乘特征選擇算法的目標(biāo)函數(shù)為：

記為：

因?yàn)镈LSR的目標(biāo)函數(shù)（10）是一個(gè)凸函數(shù)，添加的組內(nèi)特征互斥項(xiàng)也是凸的，所以最終的目標(biāo)函數(shù)（17）也是一個(gè)凸函數(shù)．換句話說，對目標(biāo)函數(shù)（17）極小化這個(gè)問題對變量矩陣來說是一個(gè)凸問題，因此可以考慮通過對其求偏導(dǎo)并令其等于零來求解，以下是求完偏導(dǎo)之后的表達(dá)式：

這樣可以運(yùn)用梯度下降法在MATLAB程序中求出最優(yōu)解．先初始化，通過計(jì)算得到初始，第一步迭代利用公式（22）算出，再按照這種步驟不斷迭代，最后就可以收斂到最優(yōu)解．

4　帶組內(nèi)互斥信息的DLSR算法

算法：帶組內(nèi)互斥信息的DLSR算法

1）定義偏移量矩陣M，轉(zhuǎn)換矩陣W，初始化矩陣W0，轉(zhuǎn)化后的轉(zhuǎn)換矩陣，選擇出來的特征組集合G，特征相似度矩陣R，迭代次數(shù)l．

19）結(jié)束．

26）停止，

27）否則，

29）結(jié)束．

5　實(shí) 驗(yàn)

實(shí)驗(yàn)中采用COIL-20、USPS手寫數(shù)字?jǐn)?shù)據(jù)集、CBCL人臉對非人臉圖像分類數(shù)據(jù)集、來自UCI數(shù)據(jù)庫的Segment 1這四個(gè)數(shù)據(jù)集，這四個(gè)數(shù)據(jù)集的主要屬性見表1．

表1　數(shù)據(jù)集的特征信息

COIL-20包含20個(gè)對象，每個(gè)對象在水平上旋轉(zhuǎn)360°，每隔5°拍攝一張照片，因此每個(gè)對象共72幅圖，每幅圖大小是32×32．

Classifylabel 300是一個(gè)手寫數(shù)字?jǐn)?shù)據(jù)集，包含5個(gè)數(shù)字，每個(gè)數(shù)字對應(yīng)300幅圖，也就是300個(gè)數(shù)據(jù)樣本，每幅圖大小為28×28．

CBCL 3000包含1 500張人臉圖片和1 500張非人臉圖片，每張圖片達(dá)到19×19分辨率并且被轉(zhuǎn)化成一個(gè)361維的向量．

Segment 1來自UCI數(shù)據(jù)庫，數(shù)據(jù)點(diǎn)是從7個(gè)戶外圖片中隨機(jī)選取的，一共有2 310個(gè)數(shù)據(jù)點(diǎn)，每個(gè)數(shù)據(jù)點(diǎn)維數(shù)是19．

用十折交叉驗(yàn)證在每一個(gè)數(shù)據(jù)集上進(jìn)行測試，同時(shí)用帶組內(nèi)互斥信息的判別最小二乘特征選擇算法（New-DLSR-FS）、判別最小二乘特征選擇算法（DLSR-FS）、Fisher score（FS）和Efficient and Robust Feature Selection via Joint L21-Norms Minimization（ERFS）這四種有監(jiān)督的算法對同一數(shù)據(jù)集進(jìn)行測試，用分類的準(zhǔn)確度來衡量算法的實(shí)驗(yàn)效果．實(shí)驗(yàn)結(jié)果見下圖．

圖1　數(shù)據(jù)集COIL-20上的實(shí)驗(yàn)結(jié)果

圖2　數(shù)據(jù)集classifylable1 300上的實(shí)驗(yàn)結(jié)果

圖3　數(shù)據(jù)集CBCL 3000上的實(shí)驗(yàn)結(jié)果

圖4　數(shù)據(jù)集segment 1上的實(shí)驗(yàn)結(jié)果

從上圖可以看出，在前兩個(gè)數(shù)據(jù)集COIL20、Classifylabel 300上，帶組內(nèi)互斥信息的判別最小二乘特征選擇算法始終優(yōu)于原算法即判別最小二乘特征選擇算法，同時(shí)也優(yōu)于另外兩個(gè)有監(jiān)督特征選擇算法．判別最小二乘特征選擇算法在這兩個(gè)數(shù)據(jù)集上的效果非常好，改進(jìn)后的新算法準(zhǔn)確度較原算法有一些提高，但是提高幅度不是很大．在數(shù)據(jù)集CBCL 3000和Segment 1上的實(shí)驗(yàn)效果則表明了新算法用很少的特征就可以得到非常高的準(zhǔn)確度，并證明了新算法的性能較好．

6　結(jié) 論

本文主要介紹了基于判別最小二乘特征選擇算法提出的帶組內(nèi)互斥信息的判別最小二乘特征選擇算法．在四個(gè)真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明了，加入組內(nèi)特征互斥項(xiàng)之后的新算法較原算法有較大改進(jìn)，也比Fisher score、Efficient and Robust Feature Selection via Joint L21-Norms Minimization這兩種有監(jiān)督算法要好．原DLSR優(yōu)化是一個(gè)凸優(yōu)化，加入了組內(nèi)特征互斥項(xiàng)之后的新的優(yōu)化問題依然是一個(gè)凸優(yōu)化問題，新算法收斂性可以得到保證．在有監(jiān)督學(xué)習(xí)中，將組內(nèi)和組間特征選擇一起考慮將是未來研究的方向．

參考文獻(xiàn)

［1］Guyon I， Elisseeff A. An introduction to variable and feature selection ［J］. Journal of Machine Learning Research，2003， 3﹕ 1157-1182.

［2］Wold S， Ruhe H， Wold H， et al. The collinearity problem in linear regression， the partial least squares （PLS） approach to generalized inverse ［J］. Journal on Scientific and Statistical Computing， 1984， 5（3）﹕ 735-743.

［3］Lin T， Zha H. Riemannian manifold learning ［J］. Pattern Analysis and Machine Intelligence﹕ IEEE Transactions， 2008，30（5）﹕ 796-809.

［4］Xu Z L ， Jin R， Lyu M R， et al. Discriminative semisupervised feature selection via manifold regularization ［J］. IEEE Transactions on Neural Networks and Learning Systems， 2010， 21（7）﹕ 1033-1047.

［5］Grandvalet Y， Bengio Y. Semi-supervised Learning by Entropy Minimization ［C］ // Saul L K， Weiss Y， Bot-to U L. Advances in Neura l Information Processing System 17. Cambridge﹕ The MIT Press， 2005， 529-536.

［6］Caruana R. Multitask Learning ［J］. Machine Learning， 1997， 28（1）﹕ 41-75.

［7］He X， Cai D， Niyogi P. Laplacian score for feature selection ［J］. Advances in Neural Information Processing Systems，2006， 18﹕ 507-514.

［8］Zhou L， Wang L， Shen C. Feature selection with redundancy constrained class separability ［J］. IEEE Transactions on Neural Networks and Learning Systems， 2010， 21（5）﹕ 853-858.

［9］He X， Cai D， Niyogi P. Laplacian score for feature selection ［J］. Advances in Neural Information Processing Systems，2006， 18﹕ 507-514.

［10］親麗華， 吉根林. 決策樹分類技術(shù)研究［J］. 計(jì)算機(jī)工程， 2004， 30（9）﹕ 94-96.

［11］Jaakkola T， Haussler D. Exploiting generative models in discriminative classifiers ［C］ // Kearns M J， Solla S A，Cohn D A， et al. Advances in Neural Information Processing Systems 11. Cambridge﹕ The MIT Press， 1999， 487-489.

［12］Dempster A P， Laird N M， Rubin D B. Maximum likelihood from incomplete data via the EM algorithm ［J］. Journal of the Royal Statistical Society﹕ Series B （Methodological）， 1977， 39（1）﹕ 1-38.

［13］Blum A， Mitchell T. Combining labeled and unlabeled data with co-training ［C］ // Bartlett P， Mansour Y.Proceedings of the Eleventh Annual Conference on Computational Learning Theory. New York﹕ ACM Press， 1998，92-100.

［14］Collobert R， Sinz F， Weston J， et al. Largescale transductive SVMs ［J］. Journal of Machine Learning Research， 2006，7﹕ 1687-1712.

［15］Xiang S M， Nie F P， Meng G F， et al. Discriminative least squares regression for multiclass classification and feature selection ［J］. IEEE transactions on neural networks and learning systems， 2012， 23（11）﹕ 1738-1754.

（編輯：王一芳）

The Study of Selection Method to Discriminate Least Square Regression with Intra-group Mutual Exclusion Information

ZHENG Rong， WEI Bijian， ZHU Wenlong
（College of Mathematics and Information science， Wenzhou University， Wenzhou， China 325035）

Abstract：This paper introduces the method of discriminative least square regression of intra-group mutual exclusion information. The selection of those important features is guaranteed by considering mutual exclusion information， meanwhile， combining the universality of the feature expression. The distribution of discriminative least square regression is maximized in order to enlarge the distribution of the heterogeneous data. Thus， the distance of different categories has been expanded. In addition， intra-group mutual exclusion items enable the model as much as possible to choose those features more important and different from each other so as to obtain the significant character subsets. The experiment on the data from the real world is also made to demonstrate that the new algorithm is much better than the existing discriminative least square regression on the problem of data classification.

Key words：Feature Selection Approach； Least Square Regression； Feature-similarity Degree

作者簡介：鄭蓉（1988- ），女，福建龍巖人，碩士研究生，研究方向：計(jì)算機(jī)數(shù)學(xué)與復(fù)雜系統(tǒng)控制

收稿日期：2015-07-12

DOI：10.3875/j.issn.1674-3563.2016.02.003 本文的PDF文件可以從xuebao.wzu.edu.cn獲得

中圖分類號：TP391

文獻(xiàn)標(biāo)志碼：A

文章編號：1674-3563（2016）02-0017-10