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

杜政霖，李 云

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

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

杜政霖1*，李 云1,2

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

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

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

0 引言

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

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

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

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

1 相關工作

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

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

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

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

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

2.1 組特征選擇

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

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

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

圖2 組特征選擇框架

Fig. 2 Group feature selection framework

2.2 特征聚類集成方法

圖3 聚類集成框架

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

1)數據集相同，采用的聚類算法也相同，但是設置不同的算法參數，來構成多個聚類結果〖22〗。

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

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

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

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

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

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

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

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

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

其中特征之間的相似性度量策略選用相關系數。兩個隨機變量u和v之間的相關系數ρ定義如下：

(1)

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

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

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

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

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

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

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

2.3 在線特征選擇

對于流特征數據，本文提出了一種新的在線特征選擇方法進行處理。該方法基于組特征選擇，利用了組構造產生的特征組。下面首先給出流特征的定義：

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

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

1)相關特征動態鑒別。

2)冗余特征動態剔除。

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

在所提方法中，假設根據前一階段的聚類集成方法對歷史數據進行處理，并且已經產生了s個特征組{G1,G2,…,Gs}，那么，對于在線特征選擇階段流入的特征f，本文要判斷流特征f和每個組的相關性，并將流特征f加入到相關性最大的組中。其中流特征f與組之間的相關性通過計算流特征f與該組代表特征的相關性來實現，對于離散值數據，相關性計算方法采用互信息。給定兩個變量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時的后驗概率。

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

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

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

2)重復步驟1)，直到沒有新特征流入；

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

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

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

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

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

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

3 實驗分析

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

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

表1 實驗數據集描述

3.1 分類準確率實驗

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

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

3.2 運行時間實驗

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

通過以上運行時間的實驗可以發現，本文提出的CEOFS算法的時間效率很高。

表2 不同分類器的分類準確率實驗結果

表3 CEOFS算法運行時間實驗結果

3.3 相關性閾值實驗

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

由圖4可得，相關性閾值對預測的準確性的影響不大。

圖4 Isolet數據集上相關性閾值對準確率的影響實驗

4 結語

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

References)

[1] 邊肇祺,張學工.模式識別[M].2版.北京：清華大學出版社,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] 李志杰,李元香,王峰,等.面向大數據分析的在線學習算法綜述[J].計算機研究與發展,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] 黃莎莎.穩定的特征選擇算法研究[D].南京:南京郵電大學,2014.(HUANG S S. Stable feature selection algorithm [D]. Nanjing: Nanjing University of Posts and Telecommunications, 2014.)

[13] 黃莎莎.基于特征聚類集成技術的組特征選擇方法[J].微型機與應用,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] 羅會蘭.聚類集成關鍵技術研究[D].杭州:浙江大學,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。

江蘇省自然科學基金資助項目(BK20131378, BK20140885)；廣西高校云計算與復雜系統重點實驗室資助項目(15206)。

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

1001- 9081(2017)03- 0866- 05

10.11772/j.issn.1001- 9081.2017.03.866

TP391.1

A