摘 要： 提出了一種過(guò)濾冗余特征的算法框架，利用組特征選擇算法去除冗余特征。在組構(gòu)造階段為了彌補(bǔ)單一聚類(lèi)算法的不足，引入聚類(lèi)集成的思想，先利用k-means方法通過(guò)多次聚類(lèi)得到一個(gè)聚類(lèi)集體，在集成階段再利用層次聚類(lèi)算法對(duì)聚類(lèi)集體進(jìn)行集成得到最終的結(jié)果。實(shí)驗(yàn)結(jié)果表明，這種算法框架能有效消除冗余特征，在保證算法穩(wěn)定性的同時(shí)還能獲得很好的性能。
關(guān)鍵詞： 穩(wěn)定性；組特征選擇；聚類(lèi)集成；層次聚類(lèi)
特征選擇[1]指從一組特征中挑選出一些最有效的特征以達(dá)到降低特征空間維數(shù)的目的的過(guò)程，是模式識(shí)別和機(jī)器學(xué)習(xí)領(lǐng)域中一項(xiàng)必不可少的技術(shù)，在數(shù)據(jù)預(yù)處理中發(fā)揮重要作用，它廣泛應(yīng)用于文本分類(lèi)、生物信息學(xué)和信息檢索等方面。尤其在海量高維數(shù)據(jù)不斷涌現(xiàn)的今天，許多機(jī)器學(xué)習(xí)算法受不相關(guān)和冗余特征的影響，而通過(guò)選擇合適的特征選擇算法，可以有效地去除不相關(guān)、冗余特征，加速數(shù)據(jù)挖掘的過(guò)程，提高學(xué)習(xí)算法的泛化性能和運(yùn)行效率，得到更加簡(jiǎn)單和容易理解的學(xué)習(xí)模型[2-3]。
圍繞提高分類(lèi)性能和降低特征維數(shù)已經(jīng)提出了很多算法，但是人們往往忽視特征選擇的穩(wěn)定性即特征選擇算法的結(jié)果對(duì)于訓(xùn)練集變化的敏感程度，用于度量訓(xùn)練集的細(xì)微變化對(duì)最優(yōu)特征子集的影響[4]。這個(gè)問(wèn)題在很多應(yīng)用中是很重要的，例如在分析微陣列數(shù)據(jù)時(shí)，由于訓(xùn)練數(shù)據(jù)的微小變化，同一個(gè)特征選擇算法可能會(huì)選擇出差異很大的特征子集，雖然大多數(shù)的特征子集在分類(lèi)性能方面同樣優(yōu)秀[5-6]。這種不穩(wěn)定性挫傷了領(lǐng)域?qū)＜覍?duì)于生物標(biāo)志物識(shí)別的信心。
目前，穩(wěn)定性問(wèn)題已成為特征選擇的一個(gè)研究熱點(diǎn)，吸引了眾多學(xué)者的研究。提高特征選擇穩(wěn)定性的方法主要有3種：（1）借鑒集成學(xué)習(xí)的思想，利用集成特征選擇有效地提高特征選擇的穩(wěn)定性；（2）樣本注入的方式；（3）組特征選擇[7]。
本文將集成方法和組特征選擇方法進(jìn)行結(jié)合，提出了一種基于特征聚類(lèi)集成技術(shù)的組特征選擇方法，用于提高算法的穩(wěn)定性。在組構(gòu)造階段利用聚類(lèi)集成的思想對(duì)特征進(jìn)行聚類(lèi)，彌補(bǔ)單一聚類(lèi)方法的不足。在組變換階段，從每個(gè)特征組中選出一個(gè)特征來(lái)代表這個(gè)組，最終就得到了最優(yōu)的特征子集。
1 組特征選擇
相關(guān)的特征組通常存在于高維數(shù)據(jù)中，并且這樣的特征組對(duì)于訓(xùn)練樣本的改變存在抵抗作用[8]。如果把每個(gè)特征組看作是一個(gè)相關(guān)的單獨(dú)實(shí)體，這樣既可以去除冗余特征，也可以起到提高特征選擇穩(wěn)定性的效果?，F(xiàn)有的組特征選擇算法的通用算法框架如圖1所示。組特征選擇包括組構(gòu)造和組變換兩個(gè)關(guān)鍵步驟。
1.1 特征組構(gòu)造
組構(gòu)造是識(shí)別相關(guān)特征組的過(guò)程，特征組的識(shí)別包括知識(shí)驅(qū)動(dòng)方法和數(shù)據(jù)驅(qū)動(dòng)方法兩類(lèi)不同的方法。知識(shí)驅(qū)動(dòng)方法利用領(lǐng)域知識(shí)使得特征組的產(chǎn)生變得容易；而數(shù)據(jù)驅(qū)動(dòng)方法僅考慮原始的數(shù)據(jù)，并不考慮領(lǐng)域相關(guān)的信息。
數(shù)據(jù)驅(qū)動(dòng)方法利用聚類(lèi)分析[9]或者密度估計(jì)[6]來(lái)識(shí)別特征簇（組）。在聚類(lèi)分析方法中通常采用經(jīng)典的劃分算法，例如層次聚類(lèi)或者k均值等方法來(lái)產(chǎn)生特征組。需要注意的是，大多數(shù)現(xiàn)有的聚類(lèi)方法沒(méi)有明顯地考慮特征組的穩(wěn)定性。
數(shù)據(jù)驅(qū)動(dòng)方法充分地利用了目標(biāo)數(shù)據(jù)的特性，因此現(xiàn)在被廣泛應(yīng)用。它的一個(gè)最主要的缺點(diǎn)就是不容易解釋和驗(yàn)證所選擇的特征組。
1.2 特征組變換
特征組變換即從每個(gè)特征組中產(chǎn)生一個(gè)單獨(dú)的相關(guān)特征來(lái)代表這個(gè)特征組。通過(guò)從每個(gè)組中選擇一個(gè)代表特征，這樣就解決了特征冗余的問(wèn)題。變換方法從簡(jiǎn)單的特征值平均[10]到復(fù)雜的組成分分析方法[11]等。本文采用的是求中心點(diǎn)的策略。
2 特征聚類(lèi)集成方法
假設(shè)給定一個(gè)訓(xùn)練樣本D，它包括n個(gè)樣本，D={X，Y}={xi，yi}，該數(shù)據(jù)集中的第i個(gè)元素xi為一個(gè)d維向量xi=（xi1，xi2，…，xid）∈Rd。
聚類(lèi)集成算法要解決的主要問(wèn)題有兩個(gè)，一是如何產(chǎn)生不同的聚類(lèi)從而形式一個(gè)聚類(lèi)集體，二是如何從這個(gè)聚類(lèi)中得到一個(gè)統(tǒng)一的聚類(lèi)結(jié)果，也可稱(chēng)為集成問(wèn)題。
2.1 聚類(lèi)集體生成
在知識(shí)驅(qū)動(dòng)方法中采用的聚類(lèi)分析方法，是無(wú)監(jiān)督特征選擇的一個(gè)重要方法。但由于聚類(lèi)分析的不可能性定理[12]，即任何一個(gè)聚類(lèi)算法不可能同時(shí)滿(mǎn)足尺度不變性、豐富性和一致性，這樣就導(dǎo)致沒(méi)有一個(gè)聚類(lèi)算法可以很好地適用于任何問(wèn)題。為了解決這個(gè)問(wèn)題，借鑒集成學(xué)習(xí)[13]的思想，通過(guò)組合不同的弱基類(lèi)模型得到一個(gè)性能好的集成模型。因此本文提出一個(gè)新的組構(gòu)造策略，即聚類(lèi)集成的方法，它可以在不同領(lǐng)域和數(shù)據(jù)集上有更好的平均性能，能發(fā)現(xiàn)任何單個(gè)聚類(lèi)算法無(wú)法得到的結(jié)合解答[14]。
在組構(gòu)造階段，使用相同的算法在數(shù)據(jù)集的不同采樣集合上聚類(lèi)，從而得到多個(gè)聚類(lèi)結(jié)果[15]?；赽agging[16]方法，通過(guò)可放回抽樣獲取不同的訓(xùn)練樣本子集來(lái)訓(xùn)練基聚類(lèi)器。假設(shè)通過(guò)bagging方法得到m個(gè)不同的訓(xùn)練子集{D1，D2，…，Dm}，單個(gè)聚類(lèi)器采用k-means方法，其中特征之間的相似性度量策略選用相關(guān)系數(shù)。
在m個(gè)訓(xùn)練子集上進(jìn)行多次k-means聚類(lèi)，得到m個(gè)聚類(lèi)結(jié)果，每個(gè)聚類(lèi)結(jié)果包括多個(gè)特征組，即{F，F(xiàn)，…，F(xiàn)，…，F(xiàn)}，F(xiàn)代表在i次k-means聚類(lèi)得到的第j個(gè)特征組，F(xiàn)代表第m次聚類(lèi)得到Lm個(gè)特征組。
2.2 特征聚類(lèi)集成策略
在組構(gòu)造階段得到聚類(lèi)集體后，就需要設(shè)計(jì)合適的集成方法對(duì)多個(gè)聚類(lèi)結(jié)果進(jìn)行集成，這也是聚類(lèi)集成中的關(guān)鍵問(wèn)題。本文采用基于互聯(lián)合矩陣[17]的方法，即在得到的聚類(lèi)集體{F，F(xiàn)，…，F(xiàn)，…，F(xiàn)}中，計(jì)算在所有的特征組F中每對(duì)特征被分到一個(gè)組的次數(shù)，除以集成的次數(shù)m，得到每個(gè)特征對(duì)的相似性Wi，j，再利用凝聚的層次聚類(lèi)將所有的特征進(jìn)行聚類(lèi)得到集成的特征組{EF1，EF2，…，EFL}。為了降低異常值的影響，采用類(lèi)平均法利用兩組特征的相似性來(lái)決定是否將它們合并。合并的過(guò)程一直持續(xù)只要兩個(gè)特征組的相似性>閾值?茲。?茲是一個(gè)用戶(hù)參數(shù)，可以根據(jù)不同的數(shù)據(jù)集進(jìn)行調(diào)整。
層次聚類(lèi)算法需要計(jì)算簇與簇之間的距離，目前常用的計(jì)算簇間距離的方法有：最短距離法、最長(zhǎng)距離法和類(lèi)平均法。其中類(lèi)平均法很好地利用所有樣本之間的信息，它傾向于合并差異小的兩個(gè)類(lèi)，考慮到類(lèi)的結(jié)構(gòu)，產(chǎn)生的分類(lèi)具有相對(duì)的魯棒性。
本文中提出的算法使用類(lèi)平均法，兩個(gè)簇間的距離等于所有分別來(lái)自?xún)蓚€(gè)簇的點(diǎn)對(duì)間的距離的平均值，給定要聚類(lèi)的對(duì)象即d個(gè)特征以及d×d的相似行矩陣W，具體的層次聚類(lèi)方法的步驟如下：
?。?）將每個(gè)特征歸為一簇，共得到d簇，每簇僅包含一個(gè)特征。簇與簇之間的距離就是兩個(gè)特征間的相似性。
?。?）根據(jù)相似性矩陣W，若兩簇的相似性Wi，j大于閾值?茲，則將這兩簇合并成一簇，于是總的簇?cái)?shù)少了一個(gè)。
?。?）重新計(jì)算新的簇與所有舊簇之間的相似性，計(jì)算方法采用類(lèi)平均法。
?。?）重復(fù)（2）、（3）步，直到類(lèi)之間的相似性全都小于閾值?茲，則聚類(lèi)結(jié)束。
經(jīng)過(guò)以上步驟得到組構(gòu)造階段產(chǎn)生的集成特征組{EF1，EF2，…，EFL}，在組變換階段，需要從每個(gè)特征組中產(chǎn)生一個(gè)單獨(dú)的相關(guān)特征來(lái)代表這個(gè)特征組。先對(duì)組構(gòu)造階段產(chǎn)生的特征組中的所有特征求平均，得到每個(gè)組的中心點(diǎn)，再計(jì)算組中的所有點(diǎn)到中心點(diǎn)的距離，最后將距離中心點(diǎn)最近的那個(gè)點(diǎn)作為特征組的代表特征。這樣在組特征選擇階段就得到去除了冗余特征的特征子集{f1，f2，…，fL}。算法的偽代碼如下：
基于特征聚類(lèi)集成技術(shù)的組特征選擇方法
輸入：數(shù)據(jù)集D，m個(gè)子樣本
輸出：選擇出的特征{f1，f2，…，fL}
//組構(gòu)造階段
for i=1，2，…，m
從D中可放回抽樣得到訓(xùn)練樣本Di
調(diào)用k-means方法得到特征組
end for
for對(duì)每一個(gè)特征對(duì)xi，xj∈D
令Wij=xi和xj分到一組的次數(shù)/m
end for
基于Wij將所有的特征進(jìn)行層次聚類(lèi)，得到集成特征組{EF1，EF2，…，EFL}
//組變換階段
for i=1，2，…，L
從EFi中獲取代表特征xi
end for
3 實(shí)驗(yàn)
為了驗(yàn)證所提算法的性能，將在不同的基準(zhǔn)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)以此來(lái)驗(yàn)證算法的穩(wěn)定性和分類(lèi)性能。實(shí)驗(yàn)所用數(shù)據(jù)集為：Sonar，Toy，Hill-Valley，Spect Heart，Madelon，Genes均來(lái)自UCI數(shù)據(jù)庫(kù)[18]，Colon cancer diagnosis數(shù)據(jù)集來(lái)自參考文獻(xiàn)[19]。各個(gè)數(shù)據(jù)集的詳細(xì)信息如表1所示。
實(shí)驗(yàn)選取兩種集成特征選擇方法和一種樣本加權(quán)方法，用來(lái)和本文提出的EFC算法進(jìn)行對(duì)比。它們分別是集成Relief算法（En-relief）、集成fisher score[20]算法（En-fisher score）和樣本加權(quán)算法VR-Lmba。
3.1 穩(wěn)定性實(shí)驗(yàn)
為了驗(yàn)證本文所提算法的穩(wěn)定性，采取基于bagging方法的可放回抽樣。首先，對(duì)于非集成方法VR-Lmba，對(duì)原始數(shù)據(jù)集進(jìn)行10次可放回抽樣，每次隨機(jī)抽取90%（觀察樣本的微小變化）的樣本構(gòu)成新的訓(xùn)練樣本子集，計(jì)算VR-Lmba算法的平均穩(wěn)定性；其次，計(jì)算En-relief、En-fisher score兩個(gè)集成算法的穩(wěn)定性，利用集成思想在訓(xùn)練子集上進(jìn)行二次抽樣，采樣比例為90%，在得到的樣本子集上進(jìn)行集成特征選擇，得到m個(gè)不同的特征權(quán)重向量。再利用線(xiàn)性加權(quán)集成方法，獲取每個(gè)訓(xùn)練子集的集成結(jié)果，最后計(jì)算特征子集間的平均穩(wěn)定性；對(duì)于EFC算法，與上述集成方法的實(shí)驗(yàn)方法相同，不同的是EFC算法的輸出是10個(gè)特征子集，無(wú)需線(xiàn)性集成的過(guò)程。其中，計(jì)算一對(duì)特征子集穩(wěn)定性的方法是杰卡德系數(shù)[21]，最終的穩(wěn)定性是所有不同特征子集對(duì)的平均穩(wěn)定性。算法的穩(wěn)定性對(duì)比實(shí)驗(yàn)結(jié)果如圖2所示。X軸代表基特征選擇器的個(gè)數(shù)m。VR-Lmba算法不是集成算法，因此它的穩(wěn)定性不會(huì)隨m值變化。
通過(guò)以上穩(wěn)定性的對(duì)比實(shí)驗(yàn)，可以觀察到EFC算法的穩(wěn)定性與其他算法相比有相似或者高于它們的穩(wěn)定性。而且隨著基特征選擇器數(shù)目的增加，穩(wěn)定性也隨之提高，當(dāng)基特征選擇器到達(dá)一定數(shù)目后，穩(wěn)定性基本保持不變。
3.2 分類(lèi)準(zhǔn)確率實(shí)驗(yàn)
由于不存在普遍接受的聚類(lèi)性能的評(píng)價(jià)指標(biāo)，本文將利用分類(lèi)準(zhǔn)確率來(lái)驗(yàn)證所提算法的性能。實(shí)驗(yàn)采用10次交叉驗(yàn)證，分類(lèi)器選取k（k=3）近鄰分類(lèi)器和線(xiàn)性SVM（C=1）分類(lèi)器，集成特征選擇基分類(lèi)器的個(gè)數(shù)m=20。4種算法的分類(lèi)準(zhǔn)確率實(shí)驗(yàn)結(jié)果如表2和表3所示，分別對(duì)應(yīng)3NN和SVM分類(lèi)器。
本文提出了一種過(guò)濾冗余特征的算法框架，利用組特征選擇算法去除冗余特征，在組構(gòu)造階段引入聚類(lèi)集成的思想，集成方法采用基于互聯(lián)合矩陣的方法，利用基于相似性的層次聚類(lèi)算法對(duì)聚類(lèi)集體進(jìn)行集成。
實(shí)驗(yàn)結(jié)果表明所提算法能有效消除冗余特征，保證算法穩(wěn)定性的同時(shí)還能獲得很好的性能，能有效地處理高維和噪聲數(shù)據(jù)。算法的不足之處就是集成階段，由于層次聚類(lèi)中使用距離矩陣，所以它的時(shí)間和空間復(fù)雜性都是二次以上的，這也是未來(lái)對(duì)本論文所提算法的一個(gè)改進(jìn)方向。
參考文獻(xiàn)
[1] 張學(xué)工.模式識(shí)別（第三版）[M].北京：清華大學(xué)出版社，2010.
[2] DASH M， LIU H. Feature selection for classification[J]. Intelligent data analysis， 1997， 1（1-4）：131-156.
[3] KOHAVI R， JOHN G H. Wrappers for feature subset selection[J]. Artificial intelligence，1997，97（1）：273-324.
[4] K P， K J， H V. Improving stability of feature selection methods[C]. Proceedings of the 12th International Conference on Computer Analysis of Images and Patterns， 2007：929-936.
[5] KALOUSIS A， PRADOS J， HILARIO M. Stability of feature selection algorithms： a study on high-dimensional spaces[J]. Knowledge and Information Systems， 2007（12）：95-116.
[6] YU L， DING C， LOSCALZO S. Stable feature selection via dense feature groups[J]. Proceedings of the 14th ACM International Conference on Knowledge Discovery and Data Mining， 2008：803-811.
[7] AWADA W， KHOSHGOFTAAR T M， DITTMAN D， et al. A review of the stability of feature selection techniques for bioinformatics data[C]. 2012 IEEE 13th International Conference on， Information Reuse and Integration， IEEE， 2012： 356-363.
[8] 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， 2009： 567-576.
[9] 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 （TCBB）， 2005， 2（2）： 83-101.
[10] 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）：58.
[11] RAPAPORT F， ZINOVYEV A， DUTREIX M， et al. Classification of microarray data using gene networks[J]. BMC Bioinformatics， 2007，8（1）：35.
[12] KLEINBERGJ. An impossibility theorem for clustering[C]. Advances in Neural Information Processing Systems， 2002：446-453.
[13] DIETTERICH T G. Ensemble methods in machine learning[C]. Proceedings of the 1st International Workshop on Multiple Classifier Systems， Cagliari， Italy， 2000：1-15.
[14] 羅會(huì)蘭.聚類(lèi)集成關(guān)鍵技術(shù)研究[D].浙江：浙江大學(xué)，2007.
[15] STREHL A， GHOSH J. Cluster ensembles-a knowledge reuse framework for combining multiple partitions[J]. Journal of Machine Learning Research， 2002（3）：583-617.
[16] GAO J， FAN W， HAN J. On the power of ensemble： Supervised and unsupervised methods reconciled[C]. Tutorial on SIAM Data Mining Conference （SDM），2010.
[17] FRED ALN. Finding consistent clusters in data partitions[C]. Multiple Classifier Systems，2001：309-318.
[18] FRANK A， ASUNCION A. UCI machine learning repository[DB]. http：//archive.ics.uci.edu/ml.2010.
[19] ALON U， BARKAI N， NOTTERMAN D A， et al. Broad patterns of gene expression revealed by clustering analysis of tumor and normal colon cancer tissues probed by oligonucleotide arrays[J]. Proceedings of the National Academy of Sciences of the United States of America， 1999： 6745-6750.
[20] TSUDA K， KAWANABE M， MＯ?譈LLER K R. Clustering with the fisher score[J]. Advances in Neural Information Processing Systems， 2002（15）：729-736.
[21] HE Z Y， YU W C. Stable feature selection for biomarker discovery[J]. Computational Biology and Chemistry， 2010,
34（4）:215-225.