杜政霖，李 云

(1.南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，南京 210003； 2.桂林電子科技大學(xué) 廣西高校云計(jì)算與復(fù)雜系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004) (*通信作者電子郵箱simondzl@163.com)

基于特征聚類集成技術(shù)的在線特征選擇

杜政霖1*，李 云1,2

(1.南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，南京 210003； 2.桂林電子科技大學(xué) 廣西高校云計(jì)算與復(fù)雜系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004) (*通信作者電子郵箱simondzl@163.com)

針對(duì)既有歷史數(shù)據(jù)又有流特征的全新應(yīng)用場(chǎng)景，提出了一種基于組特征選擇和流特征的在線特征選擇算法。在對(duì)歷史數(shù)據(jù)的組特征選擇階段，為了彌補(bǔ)單一聚類算法的不足，引入聚類集成的思想。先利用k-means方法通過(guò)多次聚類得到一個(gè)聚類集體，在集成階段再利用層次聚類算法對(duì)聚類集體進(jìn)行集成得到最終的結(jié)果。在對(duì)流特征數(shù)據(jù)的在線特征選擇階段，對(duì)組構(gòu)造產(chǎn)生的特征組通過(guò)探討特征間的相關(guān)性來(lái)更新特征組，最終通過(guò)組變換獲得特征子集。實(shí)驗(yàn)結(jié)果表明，所提算法能有效應(yīng)對(duì)全新場(chǎng)景下的在線特征選擇問(wèn)題，并且有很好的分類性能。

組特征選擇；聚類集成；流特征；在線特征選擇

0 引言

特征選擇是機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘中的關(guān)鍵問(wèn)題之一。特征選擇是通過(guò)去除數(shù)據(jù)集中不相關(guān)的和冗余的信息來(lái)獲得最優(yōu)特征子集的過(guò)程[1]，因此，特征選擇是維數(shù)約簡(jiǎn)的一個(gè)重要且常用的方法。特征選擇主要有三個(gè)方面的作用：提高算法對(duì)后續(xù)未知樣本的預(yù)測(cè)性能；通過(guò)選擇與任務(wù)相關(guān)的特征來(lái)解釋問(wèn)題和降低特征空間維度。特征選擇可應(yīng)用于諸多領(lǐng)域，尤其是對(duì)涉及高維數(shù)據(jù)的問(wèn)題[2-3]。

雖然對(duì)于特征選擇已經(jīng)有了深入的研究，但是目前對(duì)于特征選擇的研究大多受限于批量學(xué)習(xí)。在批量學(xué)習(xí)中，特征選擇以離線的形式進(jìn)行，并且訓(xùn)練樣本的所有特征都是提前給定的，因此，對(duì)于不知道訓(xùn)練數(shù)據(jù)的全部特征空間或者獲取全部特征空間的代價(jià)太大的情況下，批量學(xué)習(xí)的方法并不適用[4]。為此，近年來(lái)又提出了在線特征選擇。在線特征選擇與傳統(tǒng)特征選擇最大的區(qū)別就是訓(xùn)練數(shù)據(jù)的特征空間是動(dòng)態(tài)變化的?，F(xiàn)有關(guān)于在線特征選擇的突出工作是Wu等[5]提出的在線流特征選擇方法。在線流特征選擇所研究的應(yīng)用場(chǎng)景是特征逐個(gè)流入，新流入的特征即刻被在線處理，而不需要等待特征空間的全部信息。換言之，在線流特征選擇選擇在算法開(kāi)始時(shí)，并沒(méi)有任何訓(xùn)練數(shù)據(jù)，隨著時(shí)間的推移，流特征逐步到達(dá)，訓(xùn)練數(shù)據(jù)才會(huì)慢慢積累，并且這個(gè)過(guò)程可以是無(wú)休止的。

然而，現(xiàn)在本文所研究的在線特征選擇問(wèn)題面對(duì)的是一個(gè)全新的應(yīng)用場(chǎng)景。在該場(chǎng)景下，訓(xùn)練數(shù)據(jù)既包括歷史數(shù)據(jù)，又包含流特征數(shù)據(jù)。因?yàn)樵诂F(xiàn)實(shí)中的諸多應(yīng)用領(lǐng)域，對(duì)于在線特征選擇問(wèn)題，很多情況下已有了一定的歷史數(shù)據(jù)作為當(dāng)前訓(xùn)練數(shù)據(jù)集，同時(shí)，訓(xùn)練數(shù)據(jù)的特征空間又會(huì)隨著流特征的加入而動(dòng)態(tài)變化，因此，既要充分利用已有歷史數(shù)據(jù)，同時(shí)還要對(duì)包含流特征的新數(shù)據(jù)進(jìn)行在線特征選擇。例如，在新浪微博中，熱門話題每天都在變化，當(dāng)一個(gè)新的熱門話題出現(xiàn)時(shí)，它可能包含一些新的關(guān)鍵字(特征)，這些關(guān)鍵字可能是新穎的網(wǎng)絡(luò)詞語(yǔ)，也可能是某些詞語(yǔ)縮寫。雖然已有了大量的歷史數(shù)據(jù)，但是并不包含這些新特征，并且這些特征可能對(duì)確定話題來(lái)說(shuō)起著關(guān)鍵作用。再比如，對(duì)于垃圾郵件過(guò)濾系統(tǒng)，或許已經(jīng)根據(jù)已有歷史數(shù)據(jù)建模，但是垃圾郵件中的廣告可能是新產(chǎn)品的廣告，這些廣告所涉及的特征可能是歷史數(shù)據(jù)中未包含的新特征。此時(shí)，如果再建模中沒(méi)有包含對(duì)新特征的處理，那么必將對(duì)系統(tǒng)的預(yù)測(cè)性能產(chǎn)生嚴(yán)重影響。這就要求構(gòu)建一個(gè)有效的學(xué)習(xí)方法來(lái)解決既有歷史數(shù)據(jù)，又有流特征數(shù)據(jù)的特征選擇問(wèn)題。

為了有效解決上述全新場(chǎng)景下的在線特征選擇問(wèn)題，本文提出了一種基于特征聚類集成技術(shù)的在線特征選擇算法。該算法充分利用了歷史數(shù)據(jù)和流特征數(shù)據(jù)，并能有效解決上述全新場(chǎng)景下的在線特征選擇問(wèn)題。此外，本文所提出的算法在保證準(zhǔn)確率的同時(shí)考慮了算法的穩(wěn)定性?？傮w來(lái)說(shuō)，工作主要有以下幾個(gè)方面：1)為了提高算法對(duì)特征選擇的穩(wěn)定性，采用了基于組特征選擇的方法；2)將組特征選擇和流特征模型相結(jié)合，提出了一種新的去冗余策略；3)提出了一種基于特征聚類集成技術(shù)的在線特征選擇算法來(lái)解決全新場(chǎng)景下的特征選擇問(wèn)題。

1 相關(guān)工作

動(dòng)態(tài)特征空間下的特征選擇問(wèn)題即為在線特征選擇。有關(guān)在線特征選擇的相關(guān)工作早期是在2003年，Perkins等[6]把上述問(wèn)題歸結(jié)為在線特征選擇問(wèn)題。在線特征選擇與在線學(xué)習(xí)主要區(qū)別在于，在線特征選擇可用于動(dòng)態(tài)且未知的特征空間，而在線學(xué)習(xí)需要在算法開(kāi)始前知道訓(xùn)練數(shù)據(jù)的全部特征空間。為此，早期的主要工作有：Perkins等[6]在2003年提出的在線特征選擇算法Grafting，Zhou等[7-8]在2005年提出的Alpha-investing算法。Grafting算法將特征選擇的預(yù)測(cè)器融合到正則化框架下。Grafting面向二元分類，目標(biāo)函數(shù)是一個(gè)二元負(fù)對(duì)數(shù)釋然損失函數(shù)。Grafting有如下一些限制：首先，由于在線選擇過(guò)程中丟棄了某些特征，這將導(dǎo)致算法不能選擇出最優(yōu)結(jié)果；其次，對(duì)于已選特征再檢測(cè)將大幅度增加時(shí)間消耗；最后，算法中正則化參數(shù)值需要全部特征空間信息。對(duì)于Alpha-investing方法，總體來(lái)說(shuō)，能有效地通過(guò)調(diào)整閾值來(lái)進(jìn)行特征選擇，也能處理無(wú)限特征流問(wèn)題，但是并沒(méi)有對(duì)已包含的特征再次評(píng)價(jià)，這將對(duì)后續(xù)選擇產(chǎn)生影響。其后，在線特征選擇的相關(guān)研究工作主要分為兩個(gè)方向：在線特征選擇和在線流特征選擇。本文的相關(guān)研究也是針對(duì)其中的在線流特征選擇問(wèn)題。兩者的主要區(qū)別是，在線特征選擇的數(shù)據(jù)是以樣本流的形式動(dòng)態(tài)到來(lái)，而在線流特征選擇是以特征流的形式動(dòng)態(tài)產(chǎn)生。對(duì)于在線特征選擇中高維數(shù)據(jù)以樣本形式動(dòng)態(tài)產(chǎn)生的情況，Wang等[9]提出的在線特征選擇方法僅需固定少量的特征，根據(jù)在線梯度下降算法更新分類器，并通過(guò)L1范數(shù)實(shí)現(xiàn)稀疏，采用 L2范數(shù)來(lái)防止過(guò)擬合。其后，Nogueira等[10]為了進(jìn)一步提高性能，將Wang等[9]的在線特征選擇結(jié)合online bagging和online boosting提出了在線集成特征選擇方法。

對(duì)于在線流特征選擇，Wu等[5]在2010年提出了在線流特征選擇(Online Streaming Feature Selection, OSFS)方法和它的快速版本(Fast-OSFS),來(lái)解決動(dòng)態(tài)且未知特征空間下的特征選擇問(wèn)題。為了無(wú)需等待訓(xùn)練數(shù)據(jù)的全部特征空間信息，則需要即刻處理逐個(gè)流入的特征，因此，提出了流特征模型，即將動(dòng)態(tài)且未知的特征空間建模為流特征，并根據(jù)特征相關(guān)性理論，提出了一種用于處理流特征模型的特征選擇框架。該框架對(duì)于流特征的處理主要分為兩個(gè)階段：相關(guān)特征的動(dòng)態(tài)鑒別和冗余特征的動(dòng)態(tài)剔除，同時(shí)通過(guò)所提出的在線流特征選擇算法和其加速版本驗(yàn)證了所提出框架的有效性。為了提高算法的準(zhǔn)確性和可擴(kuò)展性來(lái)應(yīng)對(duì)更高維數(shù)據(jù)， Yu等[11]在2014年又提出了SAOLA(towards Scalable and Accurate OnLine Approach)算法，這也是在線特征選擇最新并且最有效的方法。在SAOLA算法中，每當(dāng)流入一個(gè)新特征，首先判斷該特征是否是相關(guān)特征。如果是相關(guān)特征，則判斷該特征相對(duì)于當(dāng)前最優(yōu)特征子集是否是冗余特征。如果該特征不是冗余特征，則判斷如果將該特征加入到當(dāng)前最優(yōu)特征子集中，是否會(huì)導(dǎo)致子集中的其他特征會(huì)因此變成冗余特征。如果沒(méi)有的話才會(huì)保留該特征。其中冗余分析是通過(guò)探討兩兩特征間的相關(guān)性來(lái)實(shí)現(xiàn)，這也替代了OSFS和FAST-OSFS算法中的搜索特征子集來(lái)去除冗余的過(guò)程，從而大幅度提高了時(shí)間效率。對(duì)于SAOLA算法，存在如下問(wèn)題：1)SAOLA沒(méi)有明顯地考慮到特征選擇算法的穩(wěn)定性；2)在冗余分析階段， SAOLA中探討兩兩特征之間的冗余性，即1∶1的冗余性，沒(méi)有考慮1∶m的分析；3)不能有效應(yīng)用于既有歷史數(shù)據(jù)，又有包含流特征的新數(shù)據(jù)的場(chǎng)景。為此，本文結(jié)合組特征選擇和在線流特征選擇，提出了一種新的在線特征選擇方法。首先通過(guò)聚類集成的組特征選擇來(lái)提高算法的穩(wěn)定性，并且對(duì)于流特征的冗余分析中，采用一對(duì)多的去冗余策略，在聚類集成的組特征選擇中生成的每個(gè)特征組中選擇出最終特征的同時(shí)去除冗余特征。

2 基于聚類集成的在線特征選擇

針對(duì)既有歷史數(shù)據(jù)又有流特征數(shù)據(jù)的全新場(chǎng)景下的在線特征選擇問(wèn)題，提出基于特征聚類集成技術(shù)的在線特征選擇方法。該方法在對(duì)歷史數(shù)據(jù)特征分組中，采用基于聚類集成技術(shù)的組特征選擇[12-13]，并將原算法中的組變換策略加以調(diào)整，通過(guò)特征與類別的相關(guān)性最大的原則來(lái)進(jìn)行組變換，以適應(yīng)本文場(chǎng)景。所提算法的基本框架如圖1所示，主要包括兩個(gè)部分：1)對(duì)歷史數(shù)據(jù)進(jìn)行基于聚類集成的組特征選擇。該階段主要目的是構(gòu)造出初始特征組，包括聚類和集成兩個(gè)關(guān)鍵步驟。2)對(duì)流特征數(shù)據(jù)進(jìn)行在線特征選擇。該階段主要是對(duì)流特征分組，并通過(guò)組變換得到最終特征子集。

圖1 基于特征聚類集成技術(shù)的在線特征選擇框架

2.1 組特征選擇

由于在高維數(shù)據(jù)中，通常存在高度相關(guān)的特征組，稱作固有特征組。每個(gè)組內(nèi)的特征對(duì)于類標(biāo)簽具有相同的相關(guān)性，并且特征組并不會(huì)受訓(xùn)練樣本變化的影響[14]，因此，可以通過(guò)確定特征組的方式來(lái)提高特征選擇的穩(wěn)定性。換言之，可以通過(guò)尋找一些特征組來(lái)近似固有特征組，然后在這些特征組描述的特征空間上執(zhí)行特征選擇?，F(xiàn)有的組特征選擇的通用算法框架如圖2所示。組特征選擇包括特征組構(gòu)造和特征組變換兩個(gè)關(guān)鍵步驟。

特征組構(gòu)造主要有兩種方法，即數(shù)據(jù)驅(qū)動(dòng)和知識(shí)驅(qū)動(dòng)方法;其中知識(shí)驅(qū)動(dòng)方法是根據(jù)領(lǐng)域知識(shí)來(lái)識(shí)別特征組,而數(shù)據(jù)驅(qū)動(dòng)方法產(chǎn)生特征組的過(guò)程與領(lǐng)域知識(shí)無(wú)關(guān)，僅考慮數(shù)據(jù)本身的特性。常用來(lái)識(shí)別特征組的數(shù)據(jù)驅(qū)動(dòng)方法有聚類分析[15]和密度估計(jì)[16]。雖然許多聚類分析中許多經(jīng)典的劃分方法都能用于產(chǎn)生特征組，例如k均值或?qū)哟尉垲惖龋坏?，若?duì)特征組的穩(wěn)定性有一定的要求，那么這些方法都不能很好地適用。數(shù)據(jù)驅(qū)動(dòng)方法由于充分利用了原始數(shù)據(jù)的特性，因此得到了廣泛的應(yīng)用，但也正因?yàn)檫@樣，數(shù)據(jù)驅(qū)動(dòng)方法有一個(gè)不足之處，便是不能很好地解釋所識(shí)別出的特征組。本文采用的是數(shù)據(jù)驅(qū)動(dòng)的方法，主要是基于特征聚類集成技術(shù)的組構(gòu)造方法。

特征組變換是根據(jù)組構(gòu)造階段產(chǎn)生的特征組集合，在每一個(gè)特征組中選擇出一個(gè)代表特征。從高度相關(guān)的特征組中選出一個(gè)代表特征，相當(dāng)于降低特征冗余性。常用的特征組變換方法可以是特征值平均〖17〗等較簡(jiǎn)單的方法，也可以是組成分析〖18〗等復(fù)雜的方法。本文采用的是求特征與類別標(biāo)簽的相關(guān)性最大的策略。

圖2 組特征選擇框架

Fig. 2 Group feature selection framework

2.2 特征聚類集成方法

圖3 聚類集成框架

聚類集成算法要解決的問(wèn)題主要有兩個(gè)：一是如何產(chǎn)生一個(gè)聚類集體，該集體包括多個(gè)不同的聚類結(jié)果；二是通過(guò)何種方法從這多個(gè)不同的聚類中得到一個(gè)統(tǒng)一的聚類結(jié)果，即為集成問(wèn)題。對(duì)于第一個(gè)問(wèn)題，可以采用聚類分析這一無(wú)監(jiān)督特征選擇的重要方法，但由于聚類分析的不可能性定理〖19〗，即任何一個(gè)聚類算法不可能同時(shí)滿足尺度不變性、豐富性和一致性。為此，需要根據(jù)集成學(xué)習(xí)〖20〗的思想來(lái)解決第二個(gè)問(wèn)題，即通過(guò)對(duì)多個(gè)不同的弱基類模型組合來(lái)得到一個(gè)性能較好的集成模型，因此本文采用一個(gè)新的組構(gòu)造策略，即聚類集成的方法，由于它在聚類分析的基礎(chǔ)上結(jié)合了集成策略，因此有更好的平均性能，并且能獲得單個(gè)聚類算法無(wú)法得到的組構(gòu)造結(jié)果〖21〗，其中，聚類集成首先要做的就是產(chǎn)生多個(gè)不同的聚類結(jié)果，組成一個(gè)聚類集體，常用的方法有：

1)數(shù)據(jù)集相同，采用的聚類算法也相同，但是設(shè)置不同的算法參數(shù)，來(lái)構(gòu)成多個(gè)聚類結(jié)果〖22〗。

2)在相同數(shù)據(jù)集上采用不同的聚類算法，從而得到多個(gè)不同的聚類結(jié)果〖23〗。

3)首先對(duì)原始數(shù)據(jù)集進(jìn)行多次抽樣得到多個(gè)不同的子數(shù)據(jù)集，然后采用相同的聚類算法在這多個(gè)子數(shù)據(jù)集上進(jìn)行聚類，從而構(gòu)成多個(gè)聚類結(jié)果〖24〗。

4)首先獲得原始數(shù)據(jù)集的多個(gè)特征子集，然后在這多個(gè)特征子集上采用相同的聚類算法，從而得到多個(gè)聚類結(jié)果〖25〗。

本文在組構(gòu)造階段，使用相同的聚類算法在數(shù)據(jù)集的不同采樣子集上聚類，從而得到多個(gè)聚類結(jié)果〖26〗。具體實(shí)現(xiàn)如下：首先，采用bagging方法[27]的思想來(lái)訓(xùn)練基分類器，即通過(guò)有放回的抽樣來(lái)獲得不同的樣本子集。假設(shè)通過(guò)bagging方法得到個(gè)不同的樣本子集，其中單個(gè)聚類器采用基于特征相似性的k-means方法，需要注意的是，此處k-means方法與傳統(tǒng)k-means不同之處是本文對(duì)特征聚類，具體實(shí)現(xiàn)如下：

1)初始化k個(gè)特征作為聚類中心。

2)分別計(jì)算其他所有特征與這k個(gè)中心的相關(guān)系數(shù)，并加入到相關(guān)系數(shù)最大的簇中。

3)更新中心特征。取簇中與中心特征的相關(guān)系數(shù)的平均值最接近的特征作為新的聚類中心。

4)將全部特征按照新的中心重新聚類。

5)迭代一定次數(shù)或中心不再變化。

其中特征之間的相似性度量策略選用相關(guān)系數(shù)。兩個(gè)隨機(jī)變量u和v之間的相關(guān)系數(shù)ρ定義如下：

(1)

var()代表變量的方差，cov()代表兩個(gè)變量的協(xié)方差。如果u和v之是完全相關(guān)的，也就是存在確切的線性關(guān)系，ρ(u,v)是1或-1。如果u和v是完全不相關(guān)，ρ(u,v)是0，因此，可用|1-ρ(u,v)|來(lái)度量?jī)蓚€(gè)變量u和v的相似性。

通過(guò)上述基于特征相似性的k-means方法得到多個(gè)聚類結(jié)果組成的聚類集體后，下面就需要采用合適的集成策略來(lái)對(duì)聚類結(jié)果集成。本文采用的是基于互聯(lián)矩陣[22]的方法。首先，對(duì)m個(gè)聚類結(jié)果，計(jì)算每一對(duì)特征被分在同一組中的次數(shù)，再除以聚類次數(shù)m，由此構(gòu)成相似度矩陣W。W(q,r)表示特征q和特征r之間的相似度。然后，采用凝聚型層次聚類，對(duì)所有特征合并，合并原則是特征組間的相似性大于θ，θ為用戶自定義的參數(shù)。其中特征組間的相似性采用類平均法計(jì)算，以此來(lái)降低異常值的影響。例如對(duì)于給定的d維數(shù)據(jù)，通過(guò)多次聚類，并得到相似度矩陣W后，具體的集成方法如下:

1)開(kāi)始時(shí)每個(gè)特征為單獨(dú)的一個(gè)組，則共有d個(gè)組。

2)根據(jù)合并原則，如果兩組之間的相似性大于給定閾值θ，則兩組合并，特征組總數(shù)減一。

3)合并后，重新計(jì)算新產(chǎn)生的組和其他所有組間的相似性，采用類平均法。

4)重復(fù)2)、3)步，直到所有組之間的相似性都小于θ。

通過(guò)以上聚類，可以構(gòu)造出多個(gè)特征組 {G1,G2,…,Gs}。至此，基于聚類集成的組特征選擇已完成組構(gòu)造階段。接下來(lái)便是對(duì)于包含流特征的數(shù)據(jù)進(jìn)行在線流特征選擇。

2.3 在線特征選擇

對(duì)于流特征數(shù)據(jù)，本文提出了一種新的在線特征選擇方法進(jìn)行處理。該方法基于組特征選擇，利用了組構(gòu)造產(chǎn)生的特征組。下面首先給出流特征的定義：

定義1 流特征。流特征定義為在訓(xùn)練數(shù)據(jù)的樣本空間不變的情況下，數(shù)據(jù)的特征空間隨時(shí)間而變化，且特征逐個(gè)流入(或連續(xù)產(chǎn)生)。

基于流特征的定義，Wu等[5]提出了在線流特征選擇的基本框架，對(duì)于新流入特征的處理主要分為兩個(gè)階段：

1)相關(guān)特征動(dòng)態(tài)鑒別。

2)冗余特征動(dòng)態(tài)剔除。

對(duì)于在線流特征選擇，其目標(biāo)根據(jù)已經(jīng)流入的特征，能選出一個(gè)當(dāng)前最優(yōu)特征子集。本文的在線特征選擇階段便是基于在線流特征選擇框架，結(jié)合聚類集成技術(shù)的組特征選擇產(chǎn)生的特征組，提出了一種全新的在線流特征選擇方法。該方法在冗余去除階段避免了Yu等[11]提出的SAOLA算法中對(duì)于特征冗余分析僅考慮兩兩特征間一對(duì)一的冗余分析，而是采用單個(gè)特征相對(duì)于特征組的冗余分析。

在所提方法中，假設(shè)根據(jù)前一階段的聚類集成方法對(duì)歷史數(shù)據(jù)進(jìn)行處理，并且已經(jīng)產(chǎn)生了s個(gè)特征組{G1,G2,…,Gs}，那么，對(duì)于在線特征選擇階段流入的特征f，本文要判斷流特征f和每個(gè)組的相關(guān)性，并將流特征f加入到相關(guān)性最大的組中。其中流特征f與組之間的相關(guān)性通過(guò)計(jì)算流特征f與該組代表特征的相關(guān)性來(lái)實(shí)現(xiàn)，對(duì)于離散值數(shù)據(jù)，相關(guān)性計(jì)算方法采用互信息。給定兩個(gè)變量A和B，則A和B之間的互信息定義如下：

I(A;B)=H(A)-H(A|B)

(2)

其中，變量A的熵定義為：

(3)

對(duì)已知變量B時(shí)，變量A的條件熵定義為：

(4)

其中：P(ai)是變量A=ai的先驗(yàn)概率，P(ai|bi)是ai在B=bi時(shí)的后驗(yàn)概率。

由于互信息用于處理離散值數(shù)據(jù)，因此對(duì)于連續(xù)值數(shù)據(jù)的數(shù)據(jù)集，本文采用Fisher’sZ-test[23]來(lái)計(jì)算特征間的相關(guān)性。

在上述的流特征的分組過(guò)程中，同時(shí)還伴隨著新建特征組和刪除不相關(guān)特征組的過(guò)程。新建特征組是當(dāng)流特征與所有特征組的相關(guān)性都小于閾值θ2，θ2為用戶指定參數(shù)，主要是為了避免僅對(duì)歷史數(shù)據(jù)進(jìn)行組構(gòu)造產(chǎn)生的特征組不全面。而刪除不相關(guān)特征組是為了避免最終選出的特征子集中包含不相關(guān)的特征。通過(guò)重復(fù)對(duì)流特征的分組以及特征組的添加和刪除操作，直到?jīng)]有新特征流入，最終形成了t個(gè)特征組{G1,G2,…,Gt}。接下來(lái)便是對(duì)這t個(gè)特征組進(jìn)行組變換，從每個(gè)組中選出一個(gè)特征組成最終的最優(yōu)特征子集。具體的實(shí)現(xiàn)步驟如下：

1)流入新特征，計(jì)算新特征和每個(gè)組的相關(guān)性，如果最大相關(guān)性大于θ2,則加入到相關(guān)性最大的組中；否則，新建組并將其加入；

2)重復(fù)步驟1)，直到?jīng)]有新特征流入；

3)刪除代表特征與類別相關(guān)性小于θ3所在的組；

4)輸出每個(gè)組的代表特征作為最終特征子集。

本文提出的基于聚類集成的在線特征選擇(Online Feature Selection based on feature Clustering Ensemble, CEOFS)算法的偽代碼如下：

算法1 基于聚類集成的在線特征選擇(CEOFS)算法。

輸入：歷史數(shù)據(jù)集D(m個(gè)子樣本集),流特征數(shù)據(jù)D′。

輸出：特征子集{f1,f2,…,ft}。

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

為了驗(yàn)證所提算法的性能，本文將在多個(gè)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，來(lái)測(cè)試算法的分類性能和時(shí)間效率。實(shí)驗(yàn)所用到的數(shù)據(jù)集有：Hill-valley、Urban、Madelon、Isolet、Colon、Arcene。這些數(shù)據(jù)集均來(lái)自UCI數(shù)據(jù)庫(kù)[28]，其中Urban數(shù)據(jù)集多分類數(shù)據(jù)集，其他數(shù)據(jù)集均為二元分類數(shù)據(jù)集。各個(gè)數(shù)據(jù)集的詳細(xì)信息如表1所示。

由于本算法是針對(duì)一個(gè)從未研究過(guò)的全新應(yīng)用場(chǎng)景下的特征選擇問(wèn)題，因此實(shí)驗(yàn)中選取非集成的基于聚類的在線特征選擇方法(COFS)和本文提出的基于聚類集成的在線特征(CEOFS)算法做分類準(zhǔn)確率的比較實(shí)驗(yàn)。實(shí)驗(yàn)中所使用的分類器是支持向量機(jī)(SVM)和K近鄰分類器，SVM中參數(shù)C=1，K近鄰分類器中K=3(后文直接使用3NN表示)。

表1 實(shí)驗(yàn)數(shù)據(jù)集描述

3.1 分類準(zhǔn)確率實(shí)驗(yàn)

在這部分實(shí)驗(yàn)中，主要研究的是分類準(zhǔn)確率的情況。對(duì)于本文所提出的CEOFS算法，其中集成次數(shù)為10次;同時(shí)為了模擬真實(shí)場(chǎng)景，假設(shè)訓(xùn)練數(shù)據(jù)的80%作為歷史數(shù)據(jù)，20%作為流特征數(shù)據(jù)。對(duì)于原始數(shù)據(jù)集Isolet未指定訓(xùn)練和測(cè)試樣本，使用十次交叉驗(yàn)證，將數(shù)據(jù)集分成10份，其中9份作為訓(xùn)練數(shù)據(jù)集，1份作為測(cè)試數(shù)據(jù)集。

通過(guò)表2的分類準(zhǔn)確率實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn)，CEOFS算法的準(zhǔn)確率相似或高于非集成的在線特征選擇算法。對(duì)于Arcene數(shù)據(jù)集上的結(jié)果，由于數(shù)據(jù)維度過(guò)高，層次聚類方法并不能完美應(yīng)對(duì)，因此性能受到影響。這也是以后工作要改進(jìn)的地方。

3.2 運(yùn)行時(shí)間實(shí)驗(yàn)

由于現(xiàn)實(shí)應(yīng)用中，對(duì)于在線特征選擇部分的時(shí)間效率有一定的要求，因此本文對(duì)CEOFS算法的在線特征選擇部分的運(yùn)行時(shí)間做了實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如表3所示。

通過(guò)以上運(yùn)行時(shí)間的實(shí)驗(yàn)可以發(fā)現(xiàn)，本文提出的CEOFS算法的時(shí)間效率很高。

表2 不同分類器的分類準(zhǔn)確率實(shí)驗(yàn)結(jié)果

表3 CEOFS算法運(yùn)行時(shí)間實(shí)驗(yàn)結(jié)果

3.3 相關(guān)性閾值實(shí)驗(yàn)

對(duì)于CEOFS算法，不論是連續(xù)值數(shù)據(jù)還是離散值數(shù)據(jù)，都需要設(shè)定一個(gè)相關(guān)性閾值θ來(lái)判斷兩個(gè)特征是否相關(guān)，以此來(lái)決定流特征分組情況。本文在數(shù)據(jù)集Isolet上，設(shè)定6個(gè)不同的閾值來(lái)比較不同閾值對(duì)預(yù)測(cè)性能的影響。

由圖4可得，相關(guān)性閾值對(duì)預(yù)測(cè)的準(zhǔn)確性的影響不大。

圖4 Isolet數(shù)據(jù)集上相關(guān)性閾值對(duì)準(zhǔn)確率的影響實(shí)驗(yàn)

4 結(jié)語(yǔ)

本文提出了一個(gè)基于聚類集成技術(shù)的在線特征選擇算法。該算法通過(guò)聚類集成的組特征選擇來(lái)對(duì)歷史數(shù)據(jù)進(jìn)行組構(gòu)造，并根據(jù)特征的相關(guān)性來(lái)對(duì)流特征進(jìn)行在線特征選擇和組變換。實(shí)驗(yàn)結(jié)果表明所提算法能有效應(yīng)對(duì)既有歷史數(shù)據(jù)又有包含流特征的新數(shù)據(jù)這個(gè)全新場(chǎng)景下的在線特征選擇問(wèn)題。算法在保證分類準(zhǔn)確率的同時(shí)時(shí)間效率也很高，并且該算法考慮了特征選擇的穩(wěn)定性。算法的不足之處在于集成階段，由于采用層次聚類，因此復(fù)雜度較高。這也是在以后工作中需要改進(jìn)的地方。

References)

[1] 邊肇祺,張學(xué)工.模式識(shí)別[M].2版.北京：清華大學(xué)出版社,2000:176-178.(BIAN Z Q, ZHANG X G. Pattern Recognition[M]. 2nd ed. Beijing: Tsinghua University Press, 2000: 176-178.)

[2] DASH M, LIU H. Feature selection for classification [J]. Intelligent Data Analysis, 1997, 1(3): 131-156.

[3] KOHAVI R, JOHN G H. Wrappers for feature subset selection [J]. Artificial Intelligence, 1997, 97(1/2): 273-324.

[4] 李志杰,李元香,王峰,等.面向大數(shù)據(jù)分析的在線學(xué)習(xí)算法綜述[J].計(jì)算機(jī)研究與發(fā)展,2015,52(8):1707-1721.(LI Z J, LI Y X, WANG F, et al. Online learning algorithms for big data analytics: a survey [J]. Journal of Computer Research and Development, 2015, 52(8): 1707-1721.)

[5] WU X, YU K, DING W, et al. Online feature selection with streaming features [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(5): 1178-1192.

[6] PERKINS S, THEILER J. Online feature selection using grafting [EB/OL]. [2016- 01- 22]. http://public.lanl.gov/jt/Papers/perkins_icml03.pdf.

[7] ZHOU J, FOSTER D, STINE R, et al. Streaming feature selection using alpha-investing [EB/OL]. [2016- 02- 06]. http://www.cis.upenn.edu/～ungar/Datamining/Publications/p384-zhou.pdf.

[8] ZHOU J, FOSTER D P, STINE R A, et al. Streamwise feature selection [J]. Journal of Machine Learning Research, 2006, 7: 1861-1885.

[9] WANG J, ZHAO P, HOI S C H, et al. Online feature selection and its applications [J]. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(3): 698-710.

[10] NOGUEIRA S, BROWN G. Measuring the stability of feature selection with applications to ensemble methods [EB/OL]. [2016- 02- 03]. http://xueshu.baidu.com/s?wd=paperuri%3A%281a009adab91ad944631001ba336f4e25%29&filter=sc_long_sign&tn=SE_xueshusource_2kduw22v&sc_vurl=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.728.549%26rep%3Drep1%26type%3Dpdf&ie=utf-8&sc_us=5540872035374925413.

[11] YU K, WU X, DING W, et al. Towards scalable and accurate online feature selection for big data [C]// Proceedings of the 2014 IEEE International Conference on Data Mining. Washington, DC: IEEE Computer Society, 2014: 660- 669.

[12] 黃莎莎.穩(wěn)定的特征選擇算法研究[D].南京:南京郵電大學(xué),2014.(HUANG S S. Stable feature selection algorithm [D]. Nanjing: Nanjing University of Posts and Telecommunications, 2014.)

[13] 黃莎莎.基于特征聚類集成技術(shù)的組特征選擇方法[J].微型機(jī)與應(yīng)用,2014(11):79-82.(HUANG S S. Group feature selection based on feature clustering ensemble [J]. Microcomputer and its Applications, 2014(11): 79-82.)

[14] LOSCALZO S, YU L, DING C. Consensus group stable feature selection [C]// Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2009:567-576.

[15] AU W H, CHAN K C C, WONG A K C, et al. Attribute clustering for grouping, selection, and classification of gene expression data [J]. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2005, 2(2): 83-101.

[16] YU L, DING C, LOSCALZO S. Stable feature selection via dense feature groups [C] // Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2008: 803-811.

[17] GUO Z, ZHANG T, LI X, et al. Towards precise classification of cancers based on robust gene functional expression profiles [J]. BMC Bioinformatics, 2005, 6(1): 1-12.

[18] RAPAPORT F, ZINOVYEV A, DUTREIX M, et al. Classification of microarray data using gene networks [J]. BMC Bioinformatics, 2007, 8(1): 1-15.

[19] KLEINBERG J. An impossibility theorem for clustering . 〖2016- 02- 15〗. http://www.cc.gatech.edu/～isbell/classes/reading/papers/kleinberg-nips15.pdf.

[20] DIETTERICH T G. Ensemble methods in machine learning [M] // Multiple Classifier Systems, LNCS 1857. Berlin: Springer, 2000: 1-15.

[21] 羅會(huì)蘭.聚類集成關(guān)鍵技術(shù)研究[D].杭州:浙江大學(xué),2007.(LUO H L. Research on key technologies of clustering ensemble [D]. Hangzhou: Zhejiang University, 2007.)

[22] FRED A. Finding consistent clusters in data partitions [EB/OL]. [2016- 02- 01]. http://xueshu.baidu.com/s?wd=paperuri%3A%284b1317d334fc32b2cec0dde7e8a4ca2b%29&filter=sc_long_sign&tn=SE_xueshusource_2kduw22v&sc_vurl=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Bjsessionid%3D444EE0EED4CB34E00254EB7CB735820B%3Fdoi%3D10.1.1.97.1296%26rep%3Drep1%26type%3Dpdf&ie=utf-8&sc_us=5845832111985885344.

[23] STREHL A, GHOSH J. Cluster ensembles—a knowledge reuse framework for combining multiple partitions [J]. Journal of Machine Learning Research, 2003, 3: 583-617.

[24] FERN X Z, BRODLEY C. Random projection for high-dimensional data clustering: a cluster ensemble approach [C]// Proceedings of the 20th International Conference on Machine Learning. Menlo Park, CA: AAAI Press, 2003: 186-193.

[25] GAO J, FAN W, HAN J. On the power of ensemble: supervised and unsupervised methods reconciled—an overview of ensemble methods [C] // Proceedings of the 2010 SIAM International Conference on Data Mining. Columbus, Ohio: SIAM, 2010: 2-14.

[26] FRED A. Finding consistent clusters in data partitions [M]// Multiple Classifier Systems, LNCS 2096. Berlin: Springer, 2001: 309-318.

[27] PENA J M. Learning Gaussian graphical models of gene networks with false discovery rate control [C]// Proceedings of the 6th European Conference on Evolutionary Computation, Machine Learning and Data Mining in Bioinformatics. Berlin: Springer, 2008: 165-176.

[28] UCI. Machine learning repository [DB/OL]. [2016- 01- 11]. http://archive.ics.uci.edu/ml/.

This work is partially supported by the Natural Science Foundation of Jiangsu Province (BK20131378, BK20140885), the Funds of Guangxi Colleges and Universities Key Laboratory of Cloud Computing and Complex Systems (15206).

DU Zhenglin, born in 1991, M. S. candidate. His research interests include online feature selection.

LI Yun, born in 1974, Ph. D., professor. His research interests include machine learning, pattern recognition.

Online feature selection based on feature clustering ensemble technology

DU Zhenglin1*, LI Yun1,2

(1.CollegeofComputer,NanjingUniversityofPostsandTelecommunications,NanjingJiangsu210003,China; 2.GuangxiCollegesandUniversitiesKeyLaboratoryofCloudComputingandComplexSystems,GuilinUniversityofElectronicTechnology,GuilinGuangxi541004,China)

According to the new application scenario with both historical data and stream features, an online feature selection based on group feature selection algorithm and streaming features was proposed. To compensate for the shortcomings of single clustering algorithm, the idea of clustering ensemble was introduced in the group feature selection of historical data. Firstly, a cluster set was obtained by multiple clustering usingk-means method, and the final result was obtained by integrating hierarchical clustering algorithm in the integration stage. In the online feature selection phase of the stream feature data, the feature group generated by the group structure was updated by exploring the correlation among the features, and finally the feature subset was obtained by group transformation. The experimental results show that the proposed algorithm can effectively deal with the online feature selection problem in the new scenario, and has good classification performance.

group feature selection; clustering ensemble; streaming feature; online feature selection

2016- 08- 17;

2016- 10- 24。

江蘇省自然科學(xué)基金資助項(xiàng)目(BK20131378, BK20140885)；廣西高校云計(jì)算與復(fù)雜系統(tǒng)重點(diǎn)實(shí)驗(yàn)室資助項(xiàng)目(15206)。

杜政霖(1991—)，男，江蘇徐州人，碩士研究生，主要研究方向：在線特征選擇； 李云(1974—)，男，安徽望江人，教授，博士， CCF會(huì)員，主要研究方向：機(jī)器學(xué)習(xí)、模式識(shí)別。

1001- 9081(2017)03- 0866- 05

10.11772/j.issn.1001- 9081.2017.03.866

TP391.1

A