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

杜政霖，李 云

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

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

杜政霖1*，李 云1,2

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

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

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

0 引言

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

2.1 組特征選擇

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

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

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

圖2 組特征選擇框架

Fig. 2 Group feature selection framework

2.2 特征聚類集成方法

圖3 聚類集成框架

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

1)開始時每個特征為單獨的一個組，則共有d個組。

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

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

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

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

2.3 在線特征選擇

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

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

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

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

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

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

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

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

(2)

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

(3)

對已知變量B時，變量A的條件熵定義為：

(4)

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

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

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

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

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

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

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

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

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

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

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

3 實驗分析

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

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

表1 實驗數(shù)據(jù)集描述

3.1 分類準(zhǔn)確率實驗

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

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

3.2 運行時間實驗

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

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

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

表3 CEOFS算法運行時間實驗結(jié)果

3.3 相關(guān)性閾值實驗

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

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

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

4 結(jié)語

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

References)

[1] 邊肇祺,張學(xué)工.模式識別[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ī)研究與發(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] 羅會蘭.聚類集成關(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é)基金資助項目(BK20131378, BK20140885)；廣西高校云計算與復(fù)雜系統(tǒng)重點實驗室資助項目(15206)。

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

1001- 9081(2017)03- 0866- 05

10.11772/j.issn.1001- 9081.2017.03.866

TP391.1

A