?

基于稀疏圖表示的特征選擇方法研究*

通信地址：361024 福建省廈門市集美區(qū)廈門理工學(xué)院計算機與信息工程學(xué)院Address:College of Computer and Information Engineering,Xiamen University of Technology,Xiamen 361024,Fujian,P.R.China

王曉棟,嚴(yán)菲,謝勇,江慧琴

(廈門理工學(xué)院計算機與信息工程學(xué)院,福建 廈門 361024)

摘要：特征選擇旨在降低待處理數(shù)據(jù)的維度，剔除冗余特征，是機器學(xué)習(xí)領(lǐng)域的關(guān)鍵問題之一?，F(xiàn)有的半監(jiān)督特征選擇方法一般借助圖模型提取數(shù)據(jù)集的聚類結(jié)構(gòu)，但其所提取的聚類結(jié)構(gòu)缺乏清晰的邊界，影響了特征選擇的效果。為此，提出一種基于稀疏圖表示的半監(jiān)督特征選擇方法，構(gòu)建了聚類結(jié)構(gòu)和特征選擇的聯(lián)合學(xué)習(xí)模型，采用l1范數(shù)約束圖模型以得到清晰的聚類結(jié)構(gòu)，并引入l2，1范數(shù)以避免噪聲的干擾并提高特征選擇的準(zhǔn)確度。為了驗證本方法的有效性，選擇了目前流行的幾種特征方法進行對比分析，實驗結(jié)果表明了本方法的有效性。

關(guān)鍵詞：特征選擇；半監(jiān)督學(xué)習(xí)； l2，1范數(shù)；l1范數(shù)

1引言

進入21世紀(jì)以來，社交網(wǎng)絡(luò)、數(shù)字多媒體的爆發(fā)式發(fā)展，給人們的日常生活帶來了便利的同時也提供了前所未有的機遇。然而，隨之而產(chǎn)生的大量高維、復(fù)雜的數(shù)據(jù)，也給現(xiàn)有的多媒體應(yīng)用系統(tǒng)帶來了挑戰(zhàn)，如圖像內(nèi)容檢索、圖像理解等[1,2]。處理這些高維的數(shù)據(jù)不但需要消耗大量的計算時間和存儲空間，而且高維數(shù)據(jù)間往往存在較多的冗余特征，如果這些特征得不到處理，將影響到多媒體應(yīng)用系統(tǒng)的魯棒性和準(zhǔn)確性，因此有必要對這些高維數(shù)據(jù)進行降維處理。

特征選擇方法旨在選擇數(shù)據(jù)集中最具代表性的特征，進而降低數(shù)據(jù)源的維度，是近年來的研究熱點[2~5]。根據(jù)所處理的數(shù)據(jù)集是否具有類別標(biāo)簽，特征選擇方法一般可以分為監(jiān)督、無監(jiān)督和半監(jiān)督的特征選擇方法。在監(jiān)督特征選擇方法中[3]，首先利用已知數(shù)據(jù)集及其類別標(biāo)簽訓(xùn)練學(xué)習(xí)模型，然后根據(jù)所計算出的模型將待處理數(shù)據(jù)集進行特征選擇。由于已知類別標(biāo)簽中包含較多可區(qū)分(Discriminative)信息，因此監(jiān)督特征選擇方法能夠取得較好的識別效果。然而，獲取大量的類別標(biāo)簽需要消耗大量的人力成本，且當(dāng)已知類別標(biāo)簽數(shù)據(jù)較少時，該類方法將會失效。無監(jiān)督特征選擇方法假設(shè)待處理數(shù)據(jù)集服從某種分布，如流形結(jié)構(gòu)，進而自動提取數(shù)據(jù)的類別標(biāo)簽，無需提前獲取訓(xùn)練數(shù)據(jù)的類別標(biāo)簽。最大方差MaxVar(Maximum Variance)[4]為最簡單的無監(jiān)督特征選擇方法，它根據(jù)數(shù)據(jù)方差來評價特征的重要性并進行特征篩選。LS(Laplacian Score)[5]對最大方差進行了擴展，在其基礎(chǔ)上引入了對數(shù)據(jù)空間局部結(jié)構(gòu)的分析。但是，MaxVar和LS都僅考慮到了特征本身的特點，而忽略了各個特征之間的相關(guān)性，從而導(dǎo)致其缺乏魯棒性且易陷入局部最優(yōu)。為了解決特征之間的相關(guān)性問題，許多學(xué)者提出借助圖模型提取數(shù)據(jù)的底層流形結(jié)構(gòu)，并在多種應(yīng)用場景下取得了較好的效果。譜聚類是基于圖模型的典型方法，例如，MCFS(Multi-Cluster Feature Selection)[6]采用譜聚類和l1范數(shù)獲取數(shù)據(jù)的稀疏子空間。與MCFS思想相似，MRFS(Minimize the feature Redundancy for spectral Feature Selection)[7]在采用譜聚類的同時引入了l2，1范數(shù)，使其所獲得的數(shù)據(jù)子空間不但具有稀疏特性，還能有效地消除離群點的干擾。NDFS(Nonnegative Discriminative Feature Selection)[8]利用K階最近鄰方法來描述特征類別間的相關(guān)性，并與線性分類器相結(jié)合，在對特征進行降維的同時可得到特征分類的類別標(biāo)簽。無監(jiān)督特征選擇方法克服了監(jiān)督方法人力成本高的問題，但由于缺少人工類別標(biāo)簽導(dǎo)致其可區(qū)分性不高，影響了該類方法的特征選擇效果。因此，為了克服監(jiān)督方法人力成本高、無監(jiān)督方法可區(qū)分性不高的問題，研究者們提出了半監(jiān)督的特征選擇方法，是監(jiān)督方法和無監(jiān)督方法的一種折衷。在LS的基礎(chǔ)上，文獻(xiàn)[9]提出一種半監(jiān)督的特征選擇方法，和LS一樣采用逐個篩選特征的方式，但忽略了特征之間的相關(guān)性。文獻(xiàn)[10]提出一種基于Trace Ratio的半監(jiān)督特征選擇方法TRCFS(Trace Ratio Criterion for Feature Selection)，該方法建立在圖模型的基礎(chǔ)上，但其對噪聲不敏感，且同樣忽略了特征之間的相關(guān)性。SFSS(Structural Feature Selection with Sparsity)[11]提出一種基于譜聚類的半監(jiān)督特征選擇方法，由于該方法在模型求解過程往往需要將離散解松弛化為連續(xù)解，模糊化了各個分類之間分界線，從而影響到特征選擇的效果。

為了解決以上問題，本文利用l1-范數(shù)和l2，1-范數(shù)構(gòu)建了聚類結(jié)構(gòu)和特征選擇的聯(lián)合學(xué)習(xí)模型，提出一種基于稀疏圖的半監(jiān)督特征選擇方法SSFS(Semi-supvervised Spectral Feature Selection withl1-norm graph)。相對于現(xiàn)有特征選擇方法，該方法具有如下幾個優(yōu)點：

(1)采用聚類結(jié)構(gòu)和特征選擇聯(lián)合學(xué)習(xí)模型，在對多媒體數(shù)據(jù)進行特征選擇的同時，并能得到數(shù)據(jù)的類別標(biāo)簽；

(2)引入l2，1范數(shù)過濾冗余特征，克服現(xiàn)有的特征選擇模型中l(wèi)2-范數(shù)約束模型容易受到孤立點(Outlier)的干擾的缺點，有效地避免了數(shù)據(jù)集中噪聲的干擾；

(3)引入l1-范數(shù)約束圖模型，能夠得到更為清晰的聚類結(jié)構(gòu)，提高特征選擇的準(zhǔn)確度。

2相關(guān)方法介紹

2.1　l1-范數(shù)和l2，1-范數(shù)

在統(tǒng)計學(xué)領(lǐng)域中，l1-范數(shù)常常被用于稀疏表達(dá)，在通信領(lǐng)域中也稱為壓縮感知，給定任意向量v∈Rn，l1-范數(shù)可以表示為：

(1)

矩陣的l2，1范數(shù)[12,13]是在特征選擇領(lǐng)域最新被提出的一種范數(shù)，取任意矩陣M∈Rr×p，其l2，1范數(shù)的表示形式如下所示：

(2)

從公式(2)可以看出，l2，1范數(shù)能夠?qū)仃嘙的整行進行約束，確保矩陣M能夠按行稀疏，因此，該范數(shù)有利于排除噪聲的干擾，非常適合于特征選擇的相關(guān)應(yīng)用場景。

2.2　譜聚類

給定一個具有c個分類和n組數(shù)據(jù)的數(shù)據(jù)集X={x1，x2，…，xn}，其中xi∈Rd(1≤i≤n)是第i組數(shù)據(jù)，設(shè)Y={y1，y2，…，yn}T∈Rn×c，其中yi∈{0，1}c×1為數(shù)據(jù)集X的類別標(biāo)簽。譜聚類的目的是將數(shù)據(jù)集X分為c類，使得屬于同一類別的數(shù)據(jù)之間距離最小，而類之間的數(shù)據(jù)間的距離最大。

傳統(tǒng)的譜聚類算法為在數(shù)據(jù)集上構(gòu)建一個加權(quán)圖，進而將數(shù)據(jù)的分類轉(zhuǎn)化為圖分割問題。設(shè)G={X，A}為數(shù)據(jù)集X所構(gòu)建的加權(quán)圖，X為圖G的頂點，A∈Rn×n為相似矩陣，用于描述各頂點之間的相似關(guān)系，如Aij描述了頂點xi與xj的相似度。相似矩陣的構(gòu)造可以采用ε近鄰圖、K-近鄰圖、全連通圖[14]等方法。本文采用K-近鄰圖，其模型表示為：

(3)

其中,knearest(·)是K-近鄰函數(shù)，xi∈knearest(xj)表示xi屬于xj的K-近鄰，δ用于控制近鄰節(jié)點的范圍。

基于以上所構(gòu)造的加權(quán)圖，傳統(tǒng)譜聚類的目標(biāo)函數(shù)可以表示為：

(4)

其中，tr(·)表示跡操作，F(xiàn)=[f1，f2，…，fn]=Y(YTY)-1/2，L=D-A為拉普拉斯(Laplacian)矩陣，其中D為對角矩陣，其每一個對象元素Dii=∑jAij。

3基于稀疏圖和l2，1正則化模型的特征選擇方法(SSFS)

3.1　問題提出及本文函數(shù)的構(gòu)建

在傳統(tǒng)譜聚類方法中，半監(jiān)督學(xué)習(xí)模型可表示為[11]：

(5)

其中，F(xiàn)為待求解的類別標(biāo)簽，fi和fj是類別標(biāo)簽F的第i列和第j列，Sij為相似矩陣，Y為已有的類別標(biāo)簽，U為權(quán)重矩陣(一般而言，有監(jiān)督數(shù)據(jù)的權(quán)重要大于無監(jiān)督數(shù)據(jù)的權(quán)重，本文設(shè)置有監(jiān)數(shù)據(jù)權(quán)重為1010，無監(jiān)督數(shù)據(jù)權(quán)重為1)。

在式(5)的模型求解過程中，往往需要借助松弛方法才能得到具有連續(xù)值的類別標(biāo)簽[11]，并且這些類別標(biāo)簽并不能直接用于數(shù)據(jù)分類，還需進一步借助聚類算法才能得到離散的類別標(biāo)簽，因此很大程度上增加了模型的計算復(fù)雜度，影響了可擴展性。為了解決這個問題，本文借助l1-范數(shù)，認(rèn)為在理想情況下當(dāng)鄰接圖中屬于同一類別的兩個節(jié)點xi和xj應(yīng)該具有相同的類別標(biāo)簽[12]，即fi=fj，從而使得所建立的鄰接圖具有稀疏特性，即：

(6)

其中,q為n2維向量，該向量的第((i-1)×n+j)個元素為Sij‖fi-fj‖2。

需要注意的是，相對于文獻(xiàn)[11]中的半監(jiān)督學(xué)習(xí)模型，本文所提出的半監(jiān)督學(xué)習(xí)模型借助l1-范數(shù)約束類別標(biāo)簽項，從而無需借助松弛方法便可得到清晰的類別標(biāo)簽，其學(xué)習(xí)模型的完整表示如下：

(7)

基于正則化模型的機器學(xué)習(xí)方法已經(jīng)被廣泛應(yīng)用于特征降維、多任務(wù)學(xué)習(xí)等研究領(lǐng)域，并取得了較好的效果?；谡齽t化模型的特征選擇方法可以采用以下形式描述：

(8)

其中，W為特征選擇矩陣，loss(·)為損失函數(shù)，Ω(·)為正則化模型(可以選擇不同的正則化模型，如l1范數(shù)、l2范數(shù)等)，參數(shù)λ為正則化參數(shù)。

為了有效避免噪聲的干擾和選擇有效的數(shù)據(jù)特征，本文采用正則化模型l2，1范數(shù)[12,13]。將公式(8)引入l2，1范數(shù)后，該正則化學(xué)習(xí)模型可表示：

(9)

在損失函數(shù)方面可選的方法有最小二乘法、hinge等，考慮到模型的簡單性、高效性，本文選擇最小二乘法作為損失函數(shù)。最后，本文結(jié)合式(7)、式(9)所提出的目標(biāo)函數(shù)可表示為：

(10)

3.2　學(xué)習(xí)模型求解

求解上一小節(jié)所提出的模型(10)主要有兩個難點：(1)由于該學(xué)習(xí)模型引入的l2，1和l1范數(shù)是非光滑的函數(shù)，不能直接對其進行求解；(2)盡管該學(xué)習(xí)模型中有關(guān)W和F的模型都是凸函數(shù)的，但其聯(lián)合模型是非凸函數(shù)的。本文提出以下方法求解所提出的學(xué)習(xí)模型：

(1) 首先為了便于算法求解，經(jīng)過簡單的推導(dǎo)，可將目標(biāo)函數(shù)(10)轉(zhuǎn)換為如下形式：

(11)

(12)

(2)鎖定W不變，令(?Θ(W，F(xiàn)))/?F=0，計算式(11)可得：

(13)

轉(zhuǎn)換式(13)，得到:

(14)

F=PQ

(15)

(3)將公式(15)代入式(11)后，令(?Θ(W，F(xiàn)))/?W=0，可得:

(16)

基于以上推導(dǎo)過程，本文提出的學(xué)習(xí)模型求解算法描述如下：

算法1SSFS

輸出：特征選擇矩陣W。

第1步計算初始相似矩陣S與拉普拉斯矩陣L；

第2步設(shè)置權(quán)重矩陣U；

第3步設(shè)置t=0，隨機初始化特征選擇矩陣W0；

第5步根據(jù)式(15)計算Ft+1；

第8步t=t+1，轉(zhuǎn)至第4步直到算法收斂。

4實驗結(jié)果及分析

4.1　對比算法介紹及實驗數(shù)據(jù)選擇

為了驗證算法的有效性，本文將算法SSFS應(yīng)用到多種開源數(shù)據(jù)庫，包括wine[15]、breast[15]、vehicle[15]、YALE[16]、ORL[17]和jaffe[18]。表1給出了所選有關(guān)數(shù)據(jù)集的詳細(xì)描述。

Table 1　Database description

本文挑選了幾種目前流行的半監(jiān)督特征選擇算法進行比對分析，分類器選擇SVM，相關(guān)算法描述如下：

All-features：使用所有特征作為SVM分類器的輸入，其分類結(jié)果將作為本文實驗的基準(zhǔn)線。

TRCFS[10]：該方法通過引入具有抗噪聲的Trace Ratio準(zhǔn)則提高特征選擇的效率。

SFSS[11]：該方法實現(xiàn)了特征選擇和半監(jiān)督學(xué)習(xí)算法的聯(lián)合學(xué)習(xí)，并以數(shù)據(jù)特征之間的相關(guān)性作為特征選擇的依據(jù)。

本文參照文獻(xiàn)[11]中的參數(shù)設(shè)置方式，對于每一種算法所有涉及到的參數(shù)(如果有的話)的范圍設(shè)定為{10-3，10-2，…，102，103}。對于每一種數(shù)據(jù)集，隨機選取5×c個樣本作為訓(xùn)練集，剩余樣本作為測試集。最后，選擇LIBSVM(Library for Support Vector Machines)作為分類工具，其中LIBSVM的最優(yōu)參數(shù)采用5-fold交叉檢驗得到其最優(yōu)值作為最終參數(shù)。每組實驗數(shù)據(jù)重復(fù)五次，最后計算五次結(jié)果的平均值和標(biāo)準(zhǔn)方差。

4.2　分類準(zhǔn)確性分析

表2為各種算法分類準(zhǔn)確度的對比結(jié)果，圖1詳細(xì)給出了分類準(zhǔn)確度隨特征選擇數(shù)量的變化情況。從表2和圖1的實驗結(jié)果可以看出，所有半監(jiān)督的特征選擇方法分類結(jié)果都要優(yōu)于All-features，從而證明特征選擇方法不但可以有效降低數(shù)據(jù)集的維度，同時也能提高數(shù)據(jù)分類的準(zhǔn)確度。另外，本文方法要優(yōu)于TRCFS和SFSS特征選擇方法，從而說明對數(shù)據(jù)的類別標(biāo)簽進行稀疏性約束將有助于提高分類的準(zhǔn)確度。

4.3　收斂性分析

圖2表示本文算法SSFS的收斂性分析，實驗中將本文算法涉及到的兩個參數(shù)α和β均設(shè)置為1。從圖2可以看出，本文算法經(jīng)過20次左右的迭代可以達(dá)到收斂狀態(tài)，從而表明本文算法具有較高的執(zhí)行效率。

4.4　參數(shù)對數(shù)據(jù)集的敏感性分析

本小節(jié)對所提算法涉及到的參數(shù)α和β進行具體分析，為了節(jié)省篇幅，本文僅針對vehicle、wine和Yale等三組數(shù)據(jù)集進行分析。首先設(shè)置α=1，對數(shù)據(jù)分類結(jié)果就β和特征數(shù)量的變化情況進行分析，如圖3(第一行)所示。從分析的結(jié)果可以看出，參數(shù)β的選擇依賴于所選數(shù)據(jù)集，不同的數(shù)據(jù)集需要設(shè)置不同的參數(shù)。然后設(shè)置β=1并對α和特征數(shù)量的變化進行分析，如圖3(第二行)所示。分析的結(jié)果表明，對于所展示的三組數(shù)據(jù)集，當(dāng)參數(shù)α≤1時，可以取得較好的分類結(jié)果，由于本文目標(biāo)函數(shù)的第一項用于控制數(shù)據(jù)集類別結(jié)構(gòu)的稀疏度，該參數(shù)的最優(yōu)取值也再次說明了稀疏的類別結(jié)構(gòu)將有助于提高數(shù)據(jù)分類準(zhǔn)確度。

Table 2　Performance comparison (ACC%±STD) of different feature selection algorithms

Figure 1　Classification accuracies vs. the numbers of selected features of our approach and other approaches on several datasets圖1　各種算法在多種數(shù)據(jù)集上的準(zhǔn)確度分析隨特征選擇數(shù)據(jù)的變化

Figure 2　Convergence analysis of the SSFS圖2　SSFS算法收斂性分析

Figure 3　Results of parameter sensitivity of the SSFS on different datasets圖3　SSFS算法在多種數(shù)據(jù)集上的參數(shù)分析

5結(jié)束語

本文提出一種基于稀疏圖表示的半監(jiān)督特征選擇方法，構(gòu)建了類別標(biāo)簽和特征選擇聯(lián)合學(xué)習(xí)模型，并引入l2，1范數(shù)和l1范數(shù)以避免噪聲的干擾和提高特征選擇的準(zhǔn)確度。由于所提出的聯(lián)合學(xué)習(xí)模型具有非光滑的特點，本文還設(shè)計了一套有效的迭代方法求解模型。最后，本文將所提出的算法應(yīng)用到多種開源數(shù)據(jù)集，并與目前流行的幾種特征方法進行了對比分析，實驗結(jié)果表明了算法的有效性。在下一步的工作中，將針對復(fù)雜事件檢測的應(yīng)用領(lǐng)域?qū)λ岢鏊惴ㄟM行深入研究。

參考文獻(xiàn):附中文

[1]Xie Juan-ying, Xie Wei-xin. Several feature selection algorithms based on the discernibility of a feature subset and support vector machines[J].Chinese Journal of Computer,2014，37(8):1704-1718. (in Chinese)

[2]Jian Cai-ren,Chen Xiao-yun. Unsupervised feature selection based on locality preserving projection and sparse representation [J]. Pattern Recognition and Artificial Intelligence,2015，28(3):247-252. (in Chinese)

[3]Yang Y,Ma Z G,Hauptmann A G,et al. Feature selection for multimedia analysis by sharing information among multiple tasks[J]. IEEE Transactions on Multimedia,2013,15(3):661-669.

[4]Ren Y Z,Zhang G J,Yu G X,et al. Local and global structure preserving based feature selection[J]. Neurocomputing,2012,89:147-157.

[5]He X F,Cai D,Niyogi P. Laplacian score for feature selection[M]∥Advances in Neural Information Processing Systems. Cambridge:MIT Press,2006:507-514．

[6]Cai D,Zhang C,He X F. Unsupervised feature selection for multi-cluster data[C]∥Proc of the 16th International Conference on Knowledge Discovery and Data Mining ACM SIGKDD,2010:333-342.

[7]Zhao Z,Wang L,Liu H. Efficient spectral feature selection with minimum redundancy[C]∥Proc of the 24th Conference on Artificial Intelligence AAAI,2010:673-678．

[8]Li Z C,Yang Y,Liu J,et al. Unsupervised feature selection using nonnegative spectral analysis[C]∥Proc of the 26th Conference on Artificial Intelligence AAAI，2012:1026-1032．

[9]Doquire G,Verleysen M. A graph Laplacian based approach to semi-supervised feature selection for regression problems[J]. Neurocomputing,2013，121:5-13．

[10]Liu Y,Nie F,Wu J,et al. Efficient semi-supervised feature selection with noise insensitive trace ratio criterion[J]. Neurocomputing,2013,105:12-18．

[11]Ma Z,Nie F,Yang Y,et al. Discriminating joint feature analysis for multimedia data understanding[J]. IEEE Transactions on Multimedia，2012,14(6):1662-1672．

[12]Shuman D I,Wiesmeyr C,Holighaus N，et al. Spectrum-adapted tight graph wavelet and vertex-frequency frames[J]. IEEE Transactions on Signal Processing,2015,63:4223-4235．

[13]Yang Y,Shen H T,Ma Z G,et al.l2，1-norm regularized discriminative feature selection for unsupervised learning[C]∥Proc of the 22nd International Joint Conference on Artificial Intelligence,2011:1589-1594．

[14]Nie F,Wang H,Huang H,et al. Unsupervised and semi-supervised learning vial1-norm graph[C]∥Proc of IEEE International Conference on Computer Vision,2011:2268-2273．

[15]Asuncion A,Newman D. UCI machine learning repository. University of California,Irvine,School of Information and Computer Sciences,2007[EB/OL].[2015-06-01].http://www.ics.uci.edu/～mlearn/MLRepository.html.

[16]Han Y,Xu Z,Ma Z,et al. Image classification with manifold learning for out-of-sample data[J]. Signal Processing,2013,93(8):2169-2177.

[17]He X F, Cai D,Yan S C,et al. Neighborhood preserving embedding[C]∥Proc of the 10th IEEE International Conference on Computer Vision,2005:1208-1213.

[18]Lyons M J,Budynek J,Akamatsu S. Automatic classification of single facial images[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，1999，21(12):1357-1362.

[1]謝娟英,謝維信. 基于特征子集區(qū)分度與支持向量機的特征選擇算法[J]. 計算機學(xué)報,2014,37(8):1704-1718.

[2]簡彩仁,陳曉云. 基于局部保持投影和稀疏表示的無監(jiān)督特征選擇方法[J]. 模式識別與人工智能,2015,28(3):247-252.

王曉棟(1983-),男，山西平遙人，碩士，講師，CCF會員(22248M)，研究方向為模式識別和圖像處理。E-mail:xdwangjsj@xmut.edu.cn

WANG Xiao-dong,born in 1983,MS,lecturer,CCF member(22248M)，his research interests include pattern recognition, and image processing.

嚴(yán)菲(1985-),女，湖南岳陽人，碩士，實驗師，研究方向為數(shù)據(jù)挖掘和數(shù)據(jù)隱藏。E-mail:fyan@xmut.edu.cn

YAN Fei,born in 1985,MS,experimentalist,her research interests include data mining, and data hiding.

謝勇(1985-),男，湖南衡山人，博士，講師，研究方向為嵌入式系統(tǒng)和CPS。E-mail:yongxie@xmut.edu.cn

XIE Yong,born in 1985,PhD,lecturer,his research interests include embedded system, and cyber-physical system.

江慧琴(1979-),女，福建邵武人，博士，講師，研究方向為嵌入式系統(tǒng)和模式識別。E-mail:hqjiang@nudt.edu.cn

JIANG Hui-qin,born in 1979,PhD,lecturer,her research interests include embedded system, and pattern recognition.

A feature selection method based on sparse graph representation

WANG Xiao-dong,YAN Fei,XIE Yong,JIANG Hui-qin

(College of Computer and Information Engineering,Xiamen University of Technology,Xiamen 316024,China)

Abstract:Feature selection, which aims to reduce data’s dimensionality by removing redundant features, is one of the main issues in the field of machine learning. Most of existing graph-based semi-supervised feature selection algorithms are suffering from neglecting clear cluster structure. We propose a semi-supervised algorithm based on l1-norm graph in this paper. A joint learning framework is built upon cluster structure and feature selection; l1-norm is imposed to guarantee the sparsity of the cluster structure, which is suitable for feature selection. To select the most relevant features and reduce the effect of outliers, the l2，1-norm regularization is added into the objective function. We evaluate the performance of the proposed algorithm over several data sets and compare the results with state-of-the-art semi-supervised feature selection algorithms. The results demonstrate the effectiveness of the proposed algorithm.

Key words:feature selection;semi-supervised learning;l2，1-norm;l1-norm

作者簡介:

doi:10.3969/j.issn.1007-130X.2015.12.027

中圖分類號：TP391.4

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

基金項目：國家自然科學(xué)基金資助項目(61502405)；福建省教育廳中青年教師教育科研資助項目(JA15385，JA15368);廈門理工學(xué)院對外科技合作專項資助項目(E201400400)

收稿日期：修回日期：2015-10-11

文章編號：1007-130X(2015)12-2372-07