楊常清

(西安航空學(xué)院 材料工程學(xué)院, 陜西 西安 710077)

0 引言

高維特征雖然可以準(zhǔn)確多樣化地表現(xiàn)物體特性，但使用高維數(shù)據(jù)不僅增大存儲(chǔ)空間，還增加運(yùn)算復(fù)雜度。對高維數(shù)據(jù)進(jìn)行屬性約簡，降低數(shù)據(jù)維度，挖掘數(shù)據(jù)內(nèi)部具有代表性的低維屬性，已成為機(jī)器學(xué)習(xí)的一個(gè)研究熱點(diǎn)[1-2]。

屬性約簡的優(yōu)點(diǎn)包括能降低處理時(shí)間和得到更具有泛化能力和更堅(jiān)實(shí)的學(xué)習(xí)模型等[3-4]。常見的屬性約簡方法包含子空間學(xué)習(xí)和屬性選擇兩種方法。子空間學(xué)習(xí)是把高維屬性從高維空間投影到低維空間，并保持?jǐn)?shù)據(jù)間的關(guān)聯(lián)結(jié)構(gòu)，而屬性選擇是從原始屬性集中選擇最能代表整個(gè)屬性集的屬性。利用多方向理論，學(xué)者們提出了各種屬性選擇算法。文獻(xiàn)[5]將知覺理論赫姆霍茲原理作為特征選擇的度量，用于文本分類的特征選擇中，取得了較好的效果。文獻(xiàn)[6]將類特定變換的新型語義平滑核融入支持向量機(jī)模型中, 提出了一種使用語義分類方法來構(gòu)建高性能的半監(jiān)督文本分類算法。文獻(xiàn)[7] 將皮爾森相關(guān)系數(shù)(RRPC)的最大相關(guān)和最小冗余準(zhǔn)則用于半監(jiān)督學(xué)習(xí)方法中，利用增量搜索技術(shù)來選擇最優(yōu)特征子集，平衡了文本特征提取中冗余特征與計(jì)算量間的矛盾。文獻(xiàn)[8]提出了一種基于圖稀疏的自表達(dá)屬性選擇算法。文獻(xiàn)[9]提出了一種基于稀疏學(xué)習(xí)的低秩屬性選擇算法，通過嵌入子空間學(xué)習(xí)方法來調(diào)整屬性選擇結(jié)果。文獻(xiàn)[10]在經(jīng)典粗糙集絕對約簡增量算法的基礎(chǔ)上，提出了一種快速屬性選擇算法，快速有效地對大規(guī)模數(shù)據(jù)集進(jìn)行屬性選擇。文獻(xiàn)[11]提出了一種多變量時(shí)間序列的無監(jiān)督屬性選擇算法，有效解決了大數(shù)據(jù)集無類別信息問題。文獻(xiàn)[12]在卷積神經(jīng)網(wǎng)絡(luò)算法中引入無監(jiān)督特征學(xué)習(xí)方法，實(shí)現(xiàn)了無監(jiān)督的特征學(xué)習(xí)方法。文獻(xiàn)[13]提出了一種基于蟻群優(yōu)化的無監(jiān)督特征選擇方法,該方法試圖通過幾次迭代找到最優(yōu)特征子集，而不使用任何學(xué)習(xí)算法，并根據(jù)特征之間的相似性來計(jì)算特征相關(guān)性，從而導(dǎo)致冗余度的最小化。文獻(xiàn)[14]從無標(biāo)注藏文語料中抽取邊界熵、鄰接變化數(shù)、無監(jiān)督間隔標(biāo)注等特征，并融入有監(jiān)督的序列標(biāo)注藏文分詞系統(tǒng),實(shí)現(xiàn)了無監(jiān)督特征的藏文分詞。如何在無監(jiān)督屬性選擇中利用類別信息選擇屬性是當(dāng)前需要解決的難題。本文借鑒聚類算法、子空間學(xué)習(xí)和屬性選擇各自的優(yōu)點(diǎn)，提出一種有效的屬性選擇算法。

1 算法描述及推演

1.1 算法描述

本文算法在線性回歸的模型框架中有效地嵌入自表達(dá)方法,同時(shí)利用K均值聚類產(chǎn)生偽類標(biāo)簽最大化類間距以更好地稀疏的結(jié)構(gòu)；其次，在新模型中有效融合低秩約束的屬性選擇，即利用稀疏學(xué)習(xí)方法中的l2,p-范數(shù)參數(shù)p靈活控制結(jié)果的稀疏性。

設(shè)給定訓(xùn)練集A=[a1,a2,...,an]∈Rn×d，類標(biāo)簽矩陣B∈Rn×k，回歸系數(shù)矩陣C∈Rd×k，采用線性回歸模型如式(1)所示。

(1)

C=(ATA)-1ATB

(2)

任何數(shù)據(jù)集或多或少都有冗余屬性，而頗具代表性的屬性往往蘊(yùn)含數(shù)據(jù)的空間和類別信息，為了著重凸顯數(shù)據(jù)的獨(dú)特屬性，本文引入低秩來滿足實(shí)際數(shù)據(jù)集合中的非滿秩需求。線性回歸模型可對每類響應(yīng)變量分別求解，這種求解忽略了響應(yīng)變量間的相關(guān)性，為此，利用低秩約束回歸系數(shù)矩陣C,如式(3)所示。

rank(C)=r,r≤min(d,k)

(3)

在式(3)上，利用屬性自表達(dá)方法把A作為響應(yīng)矩陣，將問題轉(zhuǎn)化為式(4):

(4)

為了使算法獲得較好的分類效果，本算法利用K均值聚類將樣本聚類到偽類標(biāo)簽中，以最小化類內(nèi)距離和最大化類間距離。

假定m個(gè)類中心，變換后的聚類中心矩陣G=[g1,...,gm]∈Rd×m，利用K均值聚類最小化如下目標(biāo)函數(shù)，如式(5)所示。

(5)

根據(jù)bi=aiC，通過回歸系數(shù)矩陣C的線性轉(zhuǎn)化，可得類內(nèi)最小間距。把式(5)代入式(4)中可得式(6):

s.t. rank(C)≤min(d,k)

(6)

式(6)回歸系數(shù)矩陣C∈Rd×k具有低秩約束結(jié)構(gòu)，所以式(6)具有監(jiān)督分類功能。

lF-范數(shù)對噪聲和離群數(shù)據(jù)較為敏感，因此可將lF-范數(shù)嵌入到模型中作為正則化項(xiàng)，以此來去除噪聲和冗余屬性，如式(7)所示。

(aiCi-uiGT)

rank(C)=r≤min(d,k)

(7)

式(7)中β為正參數(shù)，調(diào)節(jié)正則化項(xiàng)對模型的懲罰。通過調(diào)節(jié)參數(shù)，在使回歸系數(shù)矩陣C中不相關(guān)或弱相關(guān)屬性收縮為零的同時(shí)，能使重要屬性獲得更大的系數(shù)權(quán)重。

秩最小化是一個(gè)非凸優(yōu)化且NP問題，但秩約束目標(biāo)函數(shù)是可解的，即全局解能夠得到[15]。為了更好地優(yōu)化低秩結(jié)構(gòu)和有效考慮類別間關(guān)聯(lián)結(jié)構(gòu)，算法令C=XY，并且有低秩r，則目標(biāo)函數(shù)為:

s.t. rank(XY)≤min(m,k)

(8)

式(8)中，A∈Rn×d,X∈Rd×r,Y∈Rr×d，重構(gòu)的回歸系數(shù)矩陣C、矩陣X、Y都是低秩結(jié)構(gòu)。U、G分別表示聚類指示矩陣、聚類中心矩陣，‖.‖F(xiàn)表示矩陣弗羅貝尼烏斯范數(shù)。

1.2 目標(biāo)函數(shù)優(yōu)化

由于式(8)的前半部分是凸的，lF-范數(shù)雖然對噪聲和離群數(shù)據(jù)較為敏感，但作為正則化項(xiàng)它是非光滑的，為了高效率地求解目標(biāo)函數(shù)(8),本文通過固定不同矩陣依次優(yōu)化的方法來最優(yōu)目標(biāo)函數(shù)(8)。首先將式(8)化簡，如式(9)所示。

βTr(YTXTDXY)

(9)

式(9)中D∈Rd×d為對角矩陣，其每個(gè)元素定義如式(10)所示。

(10)

ci表示矩陣C*=X*Y*的第i行，X*、Y*、C*分別為X、Y、C的最優(yōu)解。

本文通過固定不同矩陣，依次優(yōu)化對應(yīng)矩陣，逐步實(shí)現(xiàn)最優(yōu)目標(biāo)函數(shù)的目的，其具體操作過程如下。

(1) 固定矩陣X、Y、G，優(yōu)化矩陣U

(11)

根據(jù)式(11)可知，經(jīng)AXY原始數(shù)據(jù)轉(zhuǎn)換后，再K均值處理，可使轉(zhuǎn)換后的數(shù)據(jù)都分配到標(biāo)簽。

(2) 固定矩陣U、X、Y,優(yōu)化矩陣G

當(dāng)固定矩陣U、X、Y后，對式(9)的優(yōu)化矩陣G求偏導(dǎo)數(shù)，并令所得偏導(dǎo)數(shù)為零。

(12)

(3) 固定矩陣U、G,優(yōu)化矩陣X、Y

固定矩陣U、G，將式(12)代入式(9)中，并令式(9)等于E，可得:

(13)

通過上述化簡，目標(biāo)函數(shù)(8)就轉(zhuǎn)化為:

(14)

令H=ATA-αATU[(UTU)-1]TUTA+αATA+βD，通過優(yōu)化矩陣X、Y，同時(shí)證明本文算法具有執(zhí)行線性判別分析[16](linear discriminant analysis, LDA)的特點(diǎn)。

1.3 目標(biāo)函數(shù)推理

經(jīng)過1.2節(jié)的目標(biāo)函數(shù)優(yōu)化，將式(8)轉(zhuǎn)化為式(14)，但通過式(14)無法求解函數(shù)的最優(yōu)值，本節(jié)通過對式(14)繼續(xù)推理，以期證明式(14)具有執(zhí)行LDA過程的特點(diǎn)，構(gòu)建全局最優(yōu)與屬性向量間的橋梁。

固定聚類指示矩陣U和聚類中心矩陣G，對式(14)中的Y求偏導(dǎo)數(shù)，并令偏導(dǎo)數(shù)為零，如式(15)所示。

(15)

由式(15)可得YT=ATAX[(XTHX)-1]T，把得到的矩陣YT和Y代入式(14)中，有:

(16)

根據(jù)式(16)的推導(dǎo)，目標(biāo)函數(shù)E只含有變量X，優(yōu)化問題轉(zhuǎn)化如下:

其中Qt和Qb分別表示LDA類內(nèi)矩陣和類間離散度矩陣。通過求解式(17)可得矩陣X的最終表達(dá)式如式(19)所示。

(19)

由于系數(shù)矩陣最優(yōu)解C*=X*Y*的列空間和X的列空間相同，所以本文提出方法與正則化LDA具有同樣的列空間。

2 本文算法及其收斂性

本文借鑒聚類算法、子空間學(xué)習(xí)和屬性選擇各自的優(yōu)點(diǎn)，提出一種有效的屬性選擇算法。在線性回歸的模型框架中有效地嵌入自表達(dá)方法,利用K均值聚類產(chǎn)生偽類標(biāo)簽最大化類間距以更好地對結(jié)構(gòu)進(jìn)行稀疏化處理；運(yùn)用l2,p-范數(shù)考慮屬性及其對應(yīng)響應(yīng)變量間的相關(guān)性，利用低秩約束來考慮不同類別間的相關(guān)性，消除數(shù)據(jù)冗余和不相關(guān)屬性，以實(shí)現(xiàn)最優(yōu)屬性子集的選擇。算法偽代碼如下:

算法1: 本算法偽代碼Input: 訓(xùn)練數(shù)據(jù)集A;正則化參數(shù)α,β;支持向量機(jī)參數(shù)(m,g)∈[-10: 2: 10];步驟1: 初始化分類器,類型選擇線性模式;步驟2: 通過自表達(dá)方法得到自表達(dá)矩陣A;步驟3: 根據(jù)模型(8): 調(diào)用算法2求解全局最優(yōu)解,以求自表征矩陣C*=X*Y*;步驟4: 利用最優(yōu)解C*對原始屬性集A進(jìn)行屬性選擇,利用得到屬性集更新樣本屬性集;步驟5: 采用支持向量機(jī)對新屬性樣本分類;Output: 分類準(zhǔn)確率。

算法2: 優(yōu)化求解式(8)的偽代碼Input: 數(shù)據(jù)集A;參數(shù)α,β,r聚類中心數(shù)m;控制參數(shù)p;步驟1: 初始化 t=0,矩陣X(t)和Y(t),得到初始化C(t)=X(t)Y(t);步驟2: 利用K均值算法初始化矩陣U(t),初始化D(t)∈Rd×d; Do 步驟3: 通過公式(11)計(jì)算U(t+1); 步驟4: 通過公式(12)計(jì)算G(t+1); 步驟5: 通過公式(15)計(jì)算Y(t+1); 步驟6: 通過公式(19)計(jì)算X(t+1); 步驟7: 更新對角矩陣D(t+1),利用公式(10)計(jì)算第i個(gè)對角元素,ci=[X(t+1)Y(t+1)]i,t=t+1;While 目標(biāo)函數(shù)(8)收斂;Output: 矩陣X,Y,聚類指示矩陣U。

對于迭代算法，收斂性是算法是否健壯有解的性能指標(biāo)，對于本文提出的目標(biāo)函數(shù)式(8)和其中的正則化項(xiàng)都非平滑，并且式中需要優(yōu)化四個(gè)變量，求解目標(biāo)函數(shù)最優(yōu)解難度頗大，但首先要證明本算法是否收斂。

當(dāng)?shù)螖?shù)為t時(shí)，根據(jù)算法2中的步驟可知:

當(dāng)?shù)螖?shù)為t+1時(shí)，根據(jù)式(11)規(guī)則固定矩陣更新優(yōu)化U(t+1)，可得如下不等式:

(22)

當(dāng)?shù)螖?shù)為t+1時(shí)，根據(jù)公式(14)規(guī)則固定矩陣U(t+1)，優(yōu)化更新矩陣X(t+1)、Y(t+1)、G(t+1)可得如下不等式:

(23)

聯(lián)合不等式(22)和(23)可得:

(24)

通過式(24)可知，目標(biāo)函數(shù)是單調(diào)遞減的，因此多次迭代后可收斂。

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

3.1 實(shí)驗(yàn)數(shù)據(jù)集

將本文算法、NFS(non feature selection)算法、LDA算法[16]、RFS算法[17]和RSR算法[18]等五種算法在BASEHOCK、PCMAC、Smk-can、ecoli-uni、CNAE-9、warpPIE10六個(gè)數(shù)據(jù)集上進(jìn)行仿真，其中數(shù)據(jù)集ecoli-uni和CNAE-9屬于UCI[19]，Smk-can、PCMAC、BASEHOCK、warpPIE10來自數(shù)據(jù)集[20]，數(shù)據(jù)集詳見表1。

表1 數(shù)據(jù)集信息統(tǒng)計(jì)

仿真實(shí)現(xiàn)的環(huán)境及配置如下: 仿真是在Windows 7系統(tǒng)下，CPU: i3-3240@3.4GHz,RAM: 4GB，使用Matlab 2014a軟件進(jìn)行編程實(shí)現(xiàn)。

3.2 實(shí)驗(yàn)結(jié)果和分析

本文采用十折交叉驗(yàn)證法將原始數(shù)據(jù)分成訓(xùn)練集和測試集，再利用SVM進(jìn)行分類，同時(shí)，把需要定義作為評(píng)價(jià)指標(biāo)，即分類準(zhǔn)確率越高表示算法效果越好。所有算法均保證在同一實(shí)驗(yàn)環(huán)境下進(jìn)行，最后提取十次運(yùn)行的實(shí)驗(yàn)結(jié)果的均值加減均方差來評(píng)估各算法的性能，以此評(píng)估實(shí)驗(yàn)的穩(wěn)定性，各算法在數(shù)據(jù)集上的結(jié)果如圖1所示。

通過圖1(a)～(f)可以得出: 隨著交叉驗(yàn)證次數(shù)的增加，本文算法在有些數(shù)據(jù)集上的分類準(zhǔn)確率并不是最好的，但經(jīng)過十次實(shí)驗(yàn)得到的平均準(zhǔn)確率要比其他四種算法高。為了更直觀地對比各算法的分類準(zhǔn)確率，將各算法的分類準(zhǔn)確率(均值±方差)統(tǒng)計(jì)結(jié)果列表，如表2所示。通過分析表2可以發(fā)現(xiàn)在所測試的六個(gè)數(shù)據(jù)集上，本文算法分類準(zhǔn)確率均好于其他四種對比算法。與NFS算法、文獻(xiàn)[16]、文獻(xiàn)[17]和文獻(xiàn)[18]相比，分類準(zhǔn)確率平均提高了17.04%、13.95%、3.6%和9.39%。

從方差上看，本文算法的方差在大多數(shù)數(shù)據(jù)集上是最小的，說明算法分類準(zhǔn)確率是穩(wěn)定的。但在數(shù)據(jù)集CNAE-9上，文獻(xiàn)[18]的方差要比本文算法的方差小4.2%，但分類準(zhǔn)確率卻高出文獻(xiàn)[18] 9.39%，總體上好于文獻(xiàn)[18]。作為有監(jiān)督屬性選擇算法的文獻(xiàn)[17]，因其利用現(xiàn)有的類標(biāo)簽在類少數(shù)據(jù)集上取得了較好的分類結(jié)果，平均分類準(zhǔn)確率為84.17%，尤其在多類數(shù)據(jù)集上，文獻(xiàn)[17]相比其他三種算法不僅利用偽類標(biāo)簽進(jìn)行分類，還利用線性判別分析數(shù)據(jù)間相關(guān)性，利用數(shù)據(jù)相關(guān)性甄別最優(yōu)屬性子集。文獻(xiàn)[18]利用原始數(shù)據(jù)得到的自表達(dá)系數(shù)矩陣嵌入稀疏學(xué)習(xí)模型中進(jìn)行屬性選擇，但由于算法為無監(jiān)督屬性選擇，實(shí)際分類效果一般，平均分類準(zhǔn)確率僅為79.32%。本文算法在線性回歸的模型框架中有效地嵌入自表達(dá)方法,同時(shí)利用K均值聚類產(chǎn)生偽類標(biāo)簽最大化類間距，以更好地對結(jié)構(gòu)進(jìn)行稀疏化處理，并利用稀疏學(xué)習(xí)方法中的l2,p-范數(shù)參數(shù)p靈活控制結(jié)果的稀疏性，取得了較高的分類準(zhǔn)確率，實(shí)際平均分類準(zhǔn)確率為87.54%。

圖1 各算法在不同數(shù)據(jù)集上的結(jié)果

表2 分類準(zhǔn)確率(均值±方差)的統(tǒng)計(jì)結(jié)果單位: %

不同數(shù)據(jù)集有不同的數(shù)據(jù)分布和干擾因素，像ecoli-uni、CNAE-9、warpPIE10等多類數(shù)據(jù)集，可通過控制秩大小來得到分類識(shí)別率，本文在數(shù)據(jù)集上的分類結(jié)果如下:

通過圖2(a)～(c)結(jié)果可知，具有低秩約束的本文算法相比滿秩得到的分類結(jié)果更優(yōu)，結(jié)合表2綜合分類結(jié)果可以看出，在多類數(shù)據(jù)集上，本文算法具有更佳的分類準(zhǔn)確率和穩(wěn)定的識(shí)別率，這是由于本文算法不僅能提取到數(shù)據(jù)集的重要屬性，還能利用子空間學(xué)習(xí)對重要屬性進(jìn)一步微調(diào)，保證了數(shù)據(jù)自身結(jié)構(gòu)。

圖2 多類數(shù)據(jù)集分類結(jié)果

4 結(jié)束語

對無監(jiān)督屬性選擇算法無類別信息和未考慮屬性的低秩問題，本文提出一種新屬性選擇算法。算法使用原始數(shù)據(jù)構(gòu)建自表達(dá)矩陣，并融合K均值聚類、低秩屬性選擇和子空間于模型中，利用K均值聚類補(bǔ)充無監(jiān)督選擇的缺陷，同時(shí)擴(kuò)展子空間學(xué)習(xí)在回歸模型上的應(yīng)用，彌補(bǔ)屬性選擇在數(shù)據(jù)調(diào)整中的不足。經(jīng)實(shí)驗(yàn)驗(yàn)證，與其他四種屬性選擇算法相比，本文算法不僅有較高的分類準(zhǔn)確率，并且分類結(jié)果也最為穩(wěn)定，特別相比滿秩得到的分類結(jié)果更優(yōu)。