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

?

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

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

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

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

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

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

1　已有的特征選擇方法

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

1.1無監(jiān)督算法

無監(jiān)督特征選擇算法沒有考慮數(shù)據(jù)的類別標簽，而是通過特征之間內(nèi)在相互關(guān)系或結(jié)構(gòu)特征，或者運用數(shù)據(jù)的方差或分離性特征對各個特征的重要性進行判斷，從中篩選出重要的特征．在無監(jiān)督特征選擇中，因為沒有根據(jù)類別信息進行特征選擇，所以因而失去了一個重要的判別依據(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)點，并且有很好的魯棒性．拉普拉斯評分是一種基于相關(guān)系數(shù)的特征選擇算法，目前已得到比較廣泛的應用．拉普拉斯評分以保持流形局部近鄰信息為目標，可以反映數(shù)據(jù)集嵌入低維流形的內(nèi)在幾何結(jié)構(gòu)，能夠比較準確地找到重要的特征，但對于帶有類別信息的數(shù)據(jù)則不能較好地識別出來．方差法是一種比較成熟的算法，該算法的評價準則比較簡單，根據(jù)方差得分進行特征重要性排序．方差法已經(jīng)得到廣泛應用，但該算法容易受到噪聲數(shù)據(jù)的干擾，從而使其準確性受到了影響．

1.2有監(jiān)督算法

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

1.3半監(jiān)督算法

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

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

2.1符號介紹

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

2.2判別最小二乘算法DLSR

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

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

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

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

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

3.1特征相似度

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

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

3.2分組進行特征選擇

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

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

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

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

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

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

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

記為：

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

這樣可以運用梯度下降法在MATLAB程序中求出最優(yōu)解．先初始化，通過計算得到初始，第一步迭代利用公式（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　實 驗

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

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

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

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

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

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

用十折交叉驗證在每一個數(shù)據(jù)集上進行測試，同時用帶組內(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ù)集進行測試，用分類的準確度來衡量算法的實驗效果．實驗結(jié)果見下圖．

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

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

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

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

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

6　結(jié) 論

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

參考文獻

［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］. 計算機工程， 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- ），女，福建龍巖人，碩士研究生，研究方向：計算機數(shù)學與復雜系統(tǒng)控制

收稿日期：2015-07-12

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

中圖分類號：TP391

文獻標志碼：A

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