正交基低冗余無(wú)監(jiān)督特征選擇法

簡(jiǎn)彩仁，翁謙

(1.廈門大學(xué)嘉庚學(xué)院, 福建 漳州 363105; 2.福州大學(xué)計(jì)算機(jī)與大數(shù)據(jù)學(xué)院, 福建 福州 350108)

0 引言

高維數(shù)據(jù)廣泛存在于機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘和模式識(shí)別等領(lǐng)域.這些數(shù)據(jù)存在許多無(wú)用或者冗余的特征，從而影響高維數(shù)據(jù)的識(shí)別研究.此外, 大量的冗余特征會(huì)占用內(nèi)存空間，從而影響存儲(chǔ)和計(jì)算效率.高維數(shù)據(jù)往往帶來(lái)“維數(shù)災(zāi)難”[1-4].因此研究高維數(shù)據(jù)的降維具有重要的意義，而特征選擇是數(shù)據(jù)降維的一種常用手段，本研究分析數(shù)據(jù)集的特征選擇.

特征選擇旨在從原始數(shù)據(jù)集中選出具有判別特性且相關(guān)的特征子集，同時(shí)減少冗余、不相關(guān)、高噪聲的特征.許多研究人員提出了各種特征選擇法，并廣泛應(yīng)用于機(jī)器學(xué)習(xí)的各個(gè)領(lǐng)域.根據(jù)樣本的標(biāo)簽信息，特征選擇可以分為有監(jiān)督特征選擇、半監(jiān)督特征選擇和無(wú)監(jiān)督特征選擇[1].由于獲得樣本的類別信息需要大量的工作，因此研究無(wú)監(jiān)督的特征選擇具有重要意義.不僅如此, 無(wú)監(jiān)督特征選擇在發(fā)現(xiàn)數(shù)據(jù)集內(nèi)部隱含的信息也有一定的作用.基于此，本研究分析了無(wú)監(jiān)督特征選擇法.

一般地，無(wú)監(jiān)督特征選擇法可以分為過(guò)濾型特征選擇法、捆綁型特征選擇法和嵌入型特征選擇法[4].過(guò)濾型特征選擇法根據(jù)一定的規(guī)則給每一個(gè)特征打分排序選擇特征，其典型代表是最大方差特征選擇法(MV)和拉普拉斯特征選擇法(LS)[5]，MV選擇方差最大的特征增加區(qū)分度，而LS利用局部近鄰信息選擇保持局部信息的特征.捆綁型特征選擇法利用機(jī)器學(xué)習(xí)方法定義評(píng)價(jià)準(zhǔn)則，從模型的表達(dá)能力選擇特征，其典型代表是多簇特征選擇法(MCFS)[6]，利用保持多簇結(jié)構(gòu)為準(zhǔn)則選擇特征.得益于表示理論的發(fā)展，嵌入型特征選擇法得到了很好的發(fā)展.嵌入型特征選擇法通過(guò)數(shù)據(jù)表示和l2, 1范數(shù)的組稀疏性選擇特征.關(guān)于嵌入型特征選擇法的研究層出不窮，Han等[7]提出一種基于正則回歸的無(wú)監(jiān)督并行正交基聚類特征選擇法(SOCFS)，該方法基于正交基構(gòu)建目標(biāo)矩陣來(lái)捕獲投影數(shù)據(jù)的潛在簇中心進(jìn)而選擇具有更強(qiáng)識(shí)別能力的特征；Lim等[8]引入特征成對(duì)依賴的觀點(diǎn)改進(jìn)了該方法，提出特征依賴無(wú)監(jiān)督特征選擇法(DUFS)，該方法可以選擇更少的特征提高識(shí)別準(zhǔn)確率.Mohsen等[9]提出自適應(yīng)相似性學(xué)習(xí)與子空間聚類無(wú)監(jiān)督特征選擇法(SCFS)，該方法不僅通過(guò)子空間聚類保持樣本的相似性，同時(shí)也考慮了基于正則化回歸模型的數(shù)據(jù)底層結(jié)構(gòu).因?yàn)榍度胄吞卣鬟x擇法能全面考慮數(shù)據(jù)的內(nèi)部結(jié)構(gòu)，是較好的一類特征選擇方法，得到了研究學(xué)者的青睞.更多關(guān)于特征選擇的研究可以參考相關(guān)綜述 [3-4].

SOCFS基于正交基重構(gòu)數(shù)據(jù)集從而選擇具有判別能力的信息，然而沒有考慮選擇特征之間的相關(guān)信息，容易選擇冗余特征.針對(duì)這一不足，借鑒最大互信息系數(shù)(MIC)，提出正交基低冗余無(wú)監(jiān)督特征選擇法.

1 相關(guān)工作

1.1 符號(hào)說(shuō)明

1.2 SOCFS

因?yàn)檫@種基于正則化回歸的特征選擇方法已被證明在有監(jiān)督和無(wú)監(jiān)督的情況下都能有效地處理數(shù)據(jù)，形如下式的特征選擇方法被廣泛應(yīng)用. 在有監(jiān)督的特征選擇中，Y可以通過(guò)給定的標(biāo)簽信息來(lái)定義. 然而，在無(wú)監(jiān)督特征選擇中，由于標(biāo)簽信息不可用，聚類結(jié)果(如k-means)通常被用來(lái)代替Y.目標(biāo)矩陣的因式分解在機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘中表現(xiàn)出了良好的性能. 此外，矩陣分解在無(wú)監(jiān)督特征選擇中有顯著的效果. SOCFS將隱式Y(jié)分解為A∈Rc×c和H∈Rn×c，得到如下的目標(biāo)函數(shù)：

(1)

其中，I是單位矩陣，正交約束ATA=I使得A的列向量是獨(dú)立的.H的正交性和非負(fù)約束使得H的每一行只有一個(gè)非零元. 約束條件使投影數(shù)據(jù)WTX進(jìn)行正交聚類.最小化問題意味著W選擇的特征子集實(shí)現(xiàn)正交聚類[7].

2 正交基低冗余無(wú)監(jiān)督特征選擇法

2.1 目標(biāo)函數(shù)

特征選擇矩陣W在去除不相關(guān)特征的同時(shí)，也會(huì)選擇有區(qū)別的特征.然而，同時(shí)選擇具有高冗余率的特征可能會(huì)導(dǎo)致機(jī)器學(xué)習(xí)算法的性能退化.例如，訓(xùn)練具有冗余特征的分類器可能會(huì)降低分類的準(zhǔn)確率.因此，有必要施加一個(gè)懲罰項(xiàng)來(lái)最小化所選特征的冗余程度.最大互信息系數(shù)(maximal information coefficient, MIC)[10]適用于測(cè)量線性和非線性數(shù)據(jù)的相關(guān)性，本研究采用最大互信息系數(shù)作為相關(guān)性評(píng)價(jià)標(biāo)準(zhǔn).基于MIC的低冗余懲罰項(xiàng)定義如下：

(2)

利用SOCFS得到的W可以選擇具有判別能力的特征，然而容易導(dǎo)致選擇的特征子集具有高冗余率.最大互信息系數(shù)(MIC)能降低選擇特征子集的冗余性，因此利用MIC改進(jìn)SOCFS，將公式(1)～(2)合并得到如下的目標(biāo)函數(shù)：

(3)

其中，β≥0是正則參數(shù)，目標(biāo)函數(shù)的第三項(xiàng)是低冗余懲罰項(xiàng)，用于選擇冗余度較低的特征.

公式(3)通過(guò)低冗余懲罰項(xiàng)改進(jìn)SOCFS得到具有選擇低冗余特征子集的無(wú)監(jiān)督特征選擇法，將這種方法稱為正交基低冗余無(wú)監(jiān)督特征選擇法(orthogonal basis minimization redundancy unsupervised feature selection method，OBMRFS).

2.2 模型求解

(4)

其中，γ>0是另一個(gè)正則化參數(shù)，用于控制其他項(xiàng)之間的比例.當(dāng)其他變量不變時(shí)，這個(gè)公式在每個(gè)變量上都是凸的.因此，可以用一次求解一個(gè)變量的方式求解公式(4)[7-8].將公式(4)的目標(biāo)函數(shù)記為：

(5)

W=(XXT+αD+βT)-1XHAT

(6)

2) 更新A.目標(biāo)函數(shù)關(guān)于A的部分為：

(7)

其中：P=WTX.

定理1最優(yōu)的A可以通過(guò)奇異值向量得到A=UVT,PHT=UΣVT,Σ=diag(w)，其中(U,Σ,V)是PHT的SVD分解.

證明 公式(7)可以轉(zhuǎn)化為：

根據(jù)定理1，可得A的最優(yōu)解為：

A=UVT

(8)

其中：WTXHT=UΣVT. 式(3)更新H，目標(biāo)函數(shù)關(guān)于H的部分為：

類似于定理1，最優(yōu)的H可以通過(guò)奇異值向量得到H=UVT，XTWA+γG=UΣVT，Σ=diag(w)，其中(U,Σ,V)是XTWA+γG的SVD分解. 因此，H的最優(yōu)解為：

H=UVT

(9)

其中，XTWA+γG=UΣVT.

式(4)更新G，輔助矩陣G滿足：

(10)

則不難得到：

(11)

2.3 正交基低冗余無(wú)監(jiān)督特征選擇算法

將2.2的算法流程總結(jié)成本研究提出的正交基低冗余無(wú)監(jiān)督特征選擇法.

算法1: 正交基低冗余無(wú)監(jiān)督特征選擇法(OBMRFS)Input: 數(shù)據(jù)集X, 最大互信息系數(shù)矩陣M, 參數(shù)α, β, γ, 類別數(shù)量c, 選擇特征數(shù)量pInitialize: t=0, D, T, A, H當(dāng)t≤maxIter 執(zhí)行:利用公式(6)更新W; 利用公式(8)更新A; 利用公式(9)更新H; 利用公式(10)更新G; 更新D和T: Dii=12wi2, Tii=∑mj=1wj2Mij2wi2, i=1, 2, …, m; 結(jié)束while循環(huán)Output: 將wi2按降序排列, 選擇前p個(gè)特征為特征子集.

2.4 收斂性與計(jì)算復(fù)雜度分析

定理2當(dāng)固定A，H和G時(shí)，用公式(6)更新W，目標(biāo)函數(shù)都是單調(diào)不增的.

定理2說(shuō)明每次更新W目標(biāo)函數(shù)都是單調(diào)不增的.當(dāng)W和H固定時(shí)，有：

上式是一個(gè)具有等式約束的二次函數(shù)優(yōu)化問題，基于KKT條件[11]，利用拉格朗日乘數(shù)法得到A的最優(yōu)解，因此更新A，目標(biāo)函數(shù)是單調(diào)不增的. 當(dāng)W，A和G固定時(shí)，則：

上式是一個(gè)具有等式約束的二次函數(shù)優(yōu)化問題，基于KKT條件[11]，利用拉格朗日乘數(shù)法得到H的最優(yōu)解，因此更新H，目標(biāo)函數(shù)是單調(diào)不增的.

固定Ht利用公式(10)更新G，有：

根據(jù)文獻(xiàn)[8]，顯然有L(Ht,Gt+1)≤L(Ht,Gt)，于是利用公式(10)更新G，目標(biāo)函數(shù)是單調(diào)不增的. 因此，通過(guò)以上分析，保證了算法1的收斂性.

公式(3)的求解過(guò)程，主要運(yùn)行時(shí)間消耗在計(jì)算矩陣W、A、H和G上，其中，W的計(jì)算量主要涉及矩陣乘法和矩陣求逆，時(shí)間復(fù)雜度為O(m3)；A和H的計(jì)算時(shí)間復(fù)雜度主要表現(xiàn)在奇異值分解上，SVD的時(shí)間復(fù)雜度為O(mcn)；G的計(jì)算主要涉及矩陣加法，時(shí)間復(fù)雜度為O(cn). 一般地，m>n>c，因此本研究提出的求解方法的一次迭代的時(shí)間復(fù)雜度為O(m3).

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

3.1 實(shí)驗(yàn)數(shù)據(jù)與參數(shù)設(shè)置

沿用文獻(xiàn)[12]研究的FERET、PIE、ORL和Yale 4個(gè)圖像數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，其基本信息如表1所示.

表1 數(shù)據(jù)信息

為驗(yàn)證OBMRFS選擇的特征子集的有效性，將選擇的特征子集用k-means進(jìn)行聚類.對(duì)比方法為最大方差特征選擇法(MV)，拉普拉斯特征選擇法(LS)，多簇特征選擇法(MCFS)，正交基聚類特征選擇法(SOCFS)，特征依賴無(wú)監(jiān)督特征選擇法(DUFS)，自適應(yīng)相似性學(xué)習(xí)與子空間聚類無(wú)監(jiān)督特征選擇法(SCFS).計(jì)算所有方法選擇的特征子集的聚類準(zhǔn)確率，對(duì)給定樣本，令ri和si分別為聚類方法得到的標(biāo)簽和樣本自帶標(biāo)簽，定義聚類準(zhǔn)確率[13]為：

其中：n為樣本總數(shù)；map(ri)將每一個(gè)標(biāo)簽ri映射成與樣本自帶的標(biāo)簽等價(jià)的類標(biāo)簽. 即有

因?yàn)镺BMRFS、SOCFS、DUFS和SCFS等方法都涉及參數(shù)的選擇問題，因此統(tǒng)一將參數(shù)的搜索空間設(shè)置為{10-3, 10-2, 10-1, 100, 101, 102, 103, 104, 105, 106}, 選擇特征數(shù)量設(shè)置為{30, 60, 90, 120, 150, 180, 210, 240, 270, 300}.

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

對(duì)比4個(gè)數(shù)據(jù)集在不同特征選擇方法下選擇的特征子集其使用k-means聚類得到的聚類準(zhǔn)確率.圖1給出了各種方法選出的特征子集下的聚類準(zhǔn)確率，表2給出了其平均聚類準(zhǔn)確率.其中，ALL表示不進(jìn)行特征選擇，對(duì)原始數(shù)據(jù)集聚類得到的聚類準(zhǔn)確率.

(a) FERET

(b) PIE

(c) ORL

(d) Yale

表2 不同方法的平均聚類準(zhǔn)確率

圖1表明OBMRFS選擇的特征子集可以得到較高的聚類準(zhǔn)確率.除了在ORL數(shù)據(jù)集上，OBMRFS都取得了最高的聚類準(zhǔn)確率.表2的平均聚類準(zhǔn)確率說(shuō)明OBMRFS選擇的特征子集是有效的，可以提高聚類方法識(shí)別的準(zhǔn)確率.盡管在ORL數(shù)據(jù)集上，OBMRFS的聚類準(zhǔn)確率沒有超過(guò)ALL，但是OBMRFS在選擇120個(gè)特征時(shí)的聚類準(zhǔn)確率優(yōu)于ALL方法.不僅如此，在4個(gè)數(shù)據(jù)集上，OBMRFS的聚類準(zhǔn)確率都優(yōu)于其他特征選擇方法.對(duì)比OBMRFS和SOCFS，不難發(fā)現(xiàn)，OBMRFS有明顯的優(yōu)勢(shì)，因此本研究提出的改進(jìn)方法是有效的.利用低冗余懲罰項(xiàng)可以降低選擇特征子集的冗余性，選擇更有效的特征子集.

3.3 參數(shù)分析

(a) FERET

(b) PIE

(c) ORL

(d) Yale

圖2的實(shí)驗(yàn)結(jié)果表明，α和β的選擇對(duì)OBMRFS的影響是明顯的，但是不難發(fā)現(xiàn)較小的α和較大的β可以得到較好的聚類準(zhǔn)確率.因此，在使用OBMRFS進(jìn)行特征選擇時(shí)可以選擇較小的α和較大的β，從圖2的實(shí)驗(yàn)結(jié)果，不難發(fā)現(xiàn)α在10-3到1取值，β在104到105取值時(shí)，OBMRFS選擇的特征子集得到的聚類準(zhǔn)確率較為理想.不僅如此，較大的β說(shuō)明低冗余懲罰項(xiàng)對(duì)特征選擇有重要的作用，加大這一項(xiàng)可以選擇有效的特征子集，進(jìn)而提高聚類準(zhǔn)確率.這一發(fā)現(xiàn)，表明本研究提出的方法可以降低選擇特征子集的冗余度.

3.4 收斂性分析

通過(guò)實(shí)驗(yàn)分析驗(yàn)證算法的收斂性，固定參數(shù)α=0.1，β=107，γ=10時(shí)，50次迭代下目標(biāo)函數(shù)的取值情況如圖3所示.圖3的收斂曲線表明了本研究提出的算法是收斂的，驗(yàn)證了2.4小節(jié)的收斂性分析.此外，從圖中可以發(fā)現(xiàn)本研究所提的算法可以快速收斂.

(a)FERET

(b) PIE

(c) ORL

(d)Yale

4 結(jié)論

本文提出正交基低冗余無(wú)監(jiān)督特征選擇法，該方法在正交基下選擇具有判別能力的特征，并用最大互信息系數(shù)矩陣選擇低冗余性的特征子集.在4個(gè)圖像數(shù)據(jù)集上的實(shí)驗(yàn)表明，該方法可以選擇有效的特征子集提高聚類準(zhǔn)確率.所提的最大互信息系數(shù)矩陣的構(gòu)造需要較大的運(yùn)行時(shí)間開銷，如何更高效地去除冗余特征將在以后的研究中給出.