一種基于整數(shù)規(guī)劃的無(wú)監(jiān)督特征選擇方法

姜賀云，張振宇，樊明宇

(1.溫州大學(xué)數(shù)理學(xué)院，浙江溫州 325035；2.溫州大學(xué)計(jì)算機(jī)與人工智能學(xué)院，浙江溫州 325035)

隨著信息技術(shù)的發(fā)展，高維數(shù)據(jù)在各個(gè)領(lǐng)域中呈爆炸式增長(zhǎng)，如視頻檢索[1]、生物信息[2]和文本挖掘[3]等.數(shù)據(jù)的高維特性不僅增加了時(shí)間和空間復(fù)雜度，而且?guī)в腥哂嗪筒幌嚓P(guān)的特征會(huì)使模型的訓(xùn)練效率降低.因此數(shù)據(jù)降維成為模式識(shí)別和數(shù)據(jù)挖掘領(lǐng)域的研究熱點(diǎn).特征選擇[4]和特征提取[5]通常是數(shù)據(jù)降維的兩種主要方式.特征選擇方法按照一定的準(zhǔn)則從原始特征集合中選擇一個(gè)使得模型評(píng)價(jià)效果最好的特征子集，對(duì)模型的可解釋性較高.研究表明，特征選擇方法能夠有效解決維數(shù)災(zāi)難問(wèn)題[6]，故在機(jī)器學(xué)習(xí)降維中的應(yīng)用也越來(lái)越廣泛.

根據(jù)樣本是否包含類(lèi)別信息，特征選擇方法可分為三類(lèi)：有監(jiān)督特征選擇①Song L,Smola A,Gretton A,et al.Supervised feature selection via dependence estimation [C]//Proceedings of the 24th International Conference on Machine Learning.New York: ACM Press,2007: 823-830.、半監(jiān)督特征選擇[7]和無(wú)監(jiān)督特征選擇[8].在實(shí)際的訓(xùn)練過(guò)程中，數(shù)據(jù)的類(lèi)別信息常常是未知的，且對(duì)數(shù)據(jù)進(jìn)行標(biāo)記時(shí)需要耗費(fèi)大量的人力和物力.近年來(lái)，國(guó)內(nèi)外學(xué)者對(duì)無(wú)監(jiān)督特征選擇方法進(jìn)行了大量研究.Krzanowski[8]提出的最大方差（Maxmum Variance）是一種簡(jiǎn)單而又直接的特征選擇方法，通過(guò)計(jì)算特征的方差值來(lái)評(píng)價(jià)其重要程度，但是由于沒(méi)有考慮到特征之間的關(guān)系，往往會(huì)造成局部極值的情況.針對(duì)這一問(wèn)題，一些學(xué)者采用聚類(lèi)分析策略獲得數(shù)據(jù)的偽標(biāo)簽信息，Cai等人②Cai D,Zhang C Y,He X F.Unsupervised feature selection for multi-cluster data [C]//Proceedings of the 16th International Conference on Knowledge Discovery and Data Mining.New York: ACM Press,2010: 333-342.提出的MCFS（Multi-cluster Feature Selection）方法采用流形學(xué)習(xí)保持?jǐn)?shù)據(jù)的結(jié)構(gòu)信息，通過(guò)譜嵌入學(xué)習(xí)樣本標(biāo)簽，然后再計(jì)算稀疏回歸系數(shù)矩陣的得分來(lái)評(píng)價(jià)特征的重要性.Qian等人①Q(mào)ian M J,Zhai C X.Robust unsupervised feature selection [C]//Proceedings of the 23th International Joint Conference on Artificial Intelligence.Barcelona: AAAI Press,2013: 1621-1627.提出的RUFS（Robust Unsupervised Feature Selection）方法通過(guò)魯棒的非負(fù)矩陣分解獲得偽聚類(lèi)標(biāo)簽，且將最小化l2,1范數(shù)特征學(xué)習(xí)過(guò)程和標(biāo)簽學(xué)習(xí)過(guò)程同時(shí)進(jìn)行來(lái)計(jì)算特征的得分.雖然這兩種模型已經(jīng)具有較好的性能，但是也存在參數(shù)不容易確定和K-means算法不能獲得精準(zhǔn)類(lèi)別信息的缺點(diǎn).Zhu等人[9]提出的SCUFS（Subspace Clustering Guided Unsupervised Feature Selection）方法基于稀疏自編碼方法能夠獲得數(shù)據(jù)的全局結(jié)構(gòu)信息，同時(shí)譜聚類(lèi)獲得的偽標(biāo)簽信息和相似矩陣通過(guò)迭代學(xué)習(xí)得到一個(gè)較好的數(shù)據(jù)分布.本文通過(guò)最小化特征重構(gòu)損失函數(shù)，引入投影矩陣的l2,0范數(shù)稀疏約束項(xiàng)指導(dǎo)特征子集的選擇.本文模型的等價(jià)轉(zhuǎn)換過(guò)程以及優(yōu)化問(wèn)題求解流程如圖1所示.

圖1 本文模型的等價(jià)轉(zhuǎn)換以及優(yōu)化問(wèn)題求解方式結(jié)構(gòu)圖

1 相關(guān)內(nèi)容

1.1 稀疏約束項(xiàng)

已有研究表明稀疏性是數(shù)據(jù)的本質(zhì)屬性[10]，帶有稀疏約束項(xiàng)的優(yōu)化問(wèn)題能剔除與學(xué)習(xí)任務(wù)無(wú)關(guān)的列、降低學(xué)習(xí)任務(wù)難度、減少計(jì)算成本等，在特征選擇方法中常采用不同形式的稀疏約束項(xiàng).對(duì)于矩陣A=(a1,…,aD)∈ ?D×D，其lr,p范數(shù)定義為：

當(dāng)p→0時(shí)，矩陣的l2,0范數(shù)可看作是計(jì)算矩陣的非零列個(gè)數(shù)，與特征選擇評(píng)估最優(yōu)的若干個(gè)特征的目的一致，故帶有l(wèi)2,0范數(shù)約束的優(yōu)化問(wèn)題被認(rèn)為是一種理想的特征選擇方法，但是帶有l(wèi)2,0范數(shù)約束的優(yōu)化問(wèn)題也是離散的NP-hard（Non-deterministic Polynomial hard）問(wèn)題②Fan M Y,Chang X J,Zhang X Q,et al.Top-k Supervise Feature Selection via ADMM for Integer Programming [C]//Proceedings of the 26th International Joint Conference on Artificial Intelligence.2017: 1646-1653..鑒于1范數(shù)和0范數(shù)都能夠?qū)崿F(xiàn)對(duì)特征的評(píng)估和選擇，且1范數(shù)比0范數(shù)更易優(yōu)化求解，因此在滿足RIP（Restricted Isometry Property）性質(zhì)條件下[11]，很多研究學(xué)者依然基于1范數(shù)的形式進(jìn)行特征選擇，如：Donoho[12]采用l1范數(shù)作為l0范數(shù)的有效近似.

3.2 實(shí)驗(yàn)設(shè)置

由于本文是無(wú)監(jiān)督模型，我們將每個(gè)數(shù)據(jù)集的全部樣本作為訓(xùn)練數(shù)據(jù)進(jìn)行特征選擇.在給定特征數(shù)目時(shí)，將數(shù)據(jù)樣本由所選擇的特征來(lái)表示，然后進(jìn)行K-means聚類(lèi).對(duì)參與比較的無(wú)監(jiān)督特征選擇方法，設(shè)置參數(shù)的鄰域范圍為6，同時(shí)，特征選擇算法中的正則化參數(shù)值在范圍{10-6,10-3,10-1,1,101,103,106}中進(jìn)行測(cè)試，且采用最好的實(shí)驗(yàn)結(jié)果所對(duì)應(yīng)的參數(shù)值.對(duì)于每組實(shí)驗(yàn)的參數(shù)設(shè)置，我們都重復(fù)20次聚類(lèi)實(shí)驗(yàn)，并記錄聚類(lèi)ACC和NMI結(jié)果均值和標(biāo)準(zhǔn)差.

由于聚類(lèi)實(shí)驗(yàn)不能完全衡量所選擇特征的判別性能，進(jìn)一步采用最近鄰分類(lèi)器在所選特征上進(jìn)行分類(lèi)實(shí)驗(yàn)來(lái)驗(yàn)證特征的判別性.我們對(duì)于每組實(shí)驗(yàn)設(shè)置參數(shù)，采用十折交叉驗(yàn)證的方法，即將數(shù)據(jù)集隨機(jī)分成10份，其中9份作為有標(biāo)簽數(shù)據(jù)，剩下的1份作為測(cè)試數(shù)據(jù)，有標(biāo)簽和無(wú)標(biāo)簽數(shù)據(jù)均由算法選擇的特征表示，然后作圖給出10次分類(lèi)實(shí)驗(yàn)的結(jié)果.

在分類(lèi)實(shí)驗(yàn)中，將基于最近鄰分類(lèi)器1NN（1-Nearest-Neighbor）的ACC作為評(píng)價(jià)指標(biāo)，其中ACC越大，模型效果越好；對(duì)于聚類(lèi)實(shí)驗(yàn)，采用聚類(lèi)準(zhǔn)確度（Accuracy,ACC）和歸一化互信息（Normalized Mutual Information,NMI）作為指標(biāo)來(lái)衡量聚類(lèi)效果好壞，與Zhu等人[15]一文中聚類(lèi)ACC和NMI評(píng)價(jià)指標(biāo)的定義一致，其中聚類(lèi)ACC和NMI取值越大，模型的聚類(lèi)效果越好.

3.3 實(shí)驗(yàn)結(jié)果及分析

本文在指定特征數(shù)目時(shí)評(píng)價(jià)模型的聚類(lèi)和分類(lèi)效果.對(duì)于COIL20，Yale-B和ORL數(shù)據(jù)集，本文將特征數(shù)目設(shè)置為{5,15,50,80,100,150,200,250}，同時(shí)，USPS和Isolet數(shù)據(jù)集的特征數(shù)目設(shè)置為{5,15,50,80,100,150,170,200}.為了充分體現(xiàn)模型的性能，在聚類(lèi)實(shí)驗(yàn)圖2和圖3中給出ACC和NMI兩種評(píng)價(jià)指標(biāo)的實(shí)驗(yàn)結(jié)果.

圖2 各個(gè)算法在不同特征數(shù)目時(shí)的聚類(lèi)ACC

圖3 各個(gè)算法在不同特征數(shù)目時(shí)的聚類(lèi)NMI

圖2和圖3中分別顯示了在各個(gè)數(shù)據(jù)集上的聚類(lèi)ACC和NMI的實(shí)驗(yàn)效果.由圖2和圖3可知，本文模型在大部分?jǐn)?shù)據(jù)集以及維度上，無(wú)論是ACC和NMI哪一種評(píng)價(jià)指標(biāo)，相比于其他的無(wú)監(jiān)督特征選擇模型都具有顯著效果，而且，與 SEFSL21模型的對(duì)比實(shí)驗(yàn)，說(shuō)明采用圓盒模型求解更具有優(yōu)勢(shì).另外，本文模型在較少的特征數(shù)目時(shí)就可以達(dá)到較高的ACC和NMI值，更有利于評(píng)估特征的重要性.

在Yale-B數(shù)據(jù)集上，雖然特征數(shù)目在小于100時(shí)實(shí)驗(yàn)效果不顯著，但是，當(dāng)特征數(shù)目大于100時(shí)實(shí)驗(yàn)效果較為突出，在USPS數(shù)據(jù)集上，聚類(lèi)準(zhǔn)確度的整體效果也可以表明模型處于一種較穩(wěn)定的狀態(tài).因此，實(shí)驗(yàn)?zāi)軌蜃C明模型具有明顯的有效性.

對(duì)選取的特征使用 1NN分類(lèi)器進(jìn)行分類(lèi)實(shí)驗(yàn)，并用分類(lèi)準(zhǔn)確度衡量所選的特征子集判別力.圖4顯示了在各個(gè)數(shù)據(jù)集上的分類(lèi)實(shí)驗(yàn)效果.從圖4可知，本文所提出的模型相比于其他的模型具有較好的分類(lèi)準(zhǔn)確度.隨著維度的增加，分類(lèi)精度也在逐漸上升，但在COIL20，Isolet，USPS，ORL以及Yale-B數(shù)據(jù)集上，當(dāng)特征數(shù)目分別為80，100，50，80和100時(shí)就基本趨于穩(wěn)定狀態(tài).實(shí)驗(yàn)結(jié)果說(shuō)明模型在一個(gè)較小的特征值時(shí)就可以達(dá)到收斂的狀態(tài)，提高了分類(lèi)性能.

對(duì)本文模型所涉及到的參數(shù)λA以及特征數(shù)目的選擇進(jìn)行具體分析，我們只在典型的COIL20和Isolet數(shù)據(jù)集上判斷是否會(huì)影響聚類(lèi)ACC和NMI的效果.由圖5可知，實(shí)驗(yàn)效果依賴(lài)于參數(shù)的設(shè)置和特征數(shù)目的選擇.其中，聚類(lèi)結(jié)果隨著特征數(shù)目的增加逐漸上升，并且在特征數(shù)目分別達(dá)到80和100時(shí)逐漸趨于穩(wěn)定，參數(shù)λA一般在{10-3,10-1,1}范圍時(shí)聚類(lèi)效果比較好.因此，對(duì)于不同的數(shù)據(jù)集，如何選擇一個(gè)合適的特征值和參數(shù)值是值得研究的問(wèn)題.

圖4 各個(gè)算法在不同特征數(shù)目時(shí)的最近鄰分類(lèi)ACC

圖5 本文模型在不同特征數(shù)目和參數(shù)下的聚類(lèi)ACC和NMI

4 結(jié) 論

本文通過(guò)最小化特征的重構(gòu)誤差以及聯(lián)合投影矩陣的l2,0范數(shù)約束項(xiàng)，提出了一種新的無(wú)監(jiān)督特征選擇模型.這種直接求得最稀疏解的模型無(wú)需對(duì)所有的特征進(jìn)行評(píng)分，就能夠選擇出最優(yōu)的k個(gè)特征來(lái)保留樣本的最有效信息.在5個(gè)數(shù)據(jù)集上與9種模型的對(duì)比實(shí)驗(yàn)結(jié)果，表明了本文模型能夠有效消除冗余和不相關(guān)的特征，本文的主要貢獻(xiàn)如下.

1）基于特征與特征之間的自重構(gòu)關(guān)系提出一種選擇模型，使所選擇的特征子集能夠較好保留原數(shù)據(jù)特征中的有效信息.

2）與傳統(tǒng)的稀疏特征選擇方法相比，采用帶有l(wèi)2,0范數(shù)約束的選擇方法獲得最優(yōu)的k個(gè)特征而不是k個(gè)最優(yōu)的特征.

3）本文實(shí)驗(yàn)結(jié)果說(shuō)明采用圓盒模型求解具有一定的優(yōu)勢(shì)，因此可以為涉及矩陣l2,0范數(shù)約束的優(yōu)化問(wèn)題直接求得全局最優(yōu)解提供一種思路.