高維數據特征降維研究綜述
2008-12-31 00:00:00胡潔
計算機應用研究 2008年9期
摘 要：特征降維能夠有效地提高機器學習的效率，特征子集的搜索過程以及特征評價標準是特征降維的兩個核心問題。綜述國際上關于特征降維的研究成果，總結并提出了較完備的特征降維模型定義；通過列舉解決特征降維上重要問題的各種方案來比較各種算法的特點以及優劣，并討論了該方向上尚未解決的問題和發展趨勢。
關鍵詞：降維；機器學習；特征選擇；特征抽取；評估準則
中圖分類號：TP181 文獻標志碼：A
文章編號：1001-3695(2008)09-2601-06
Survey on feature dimension reduction for highdimensional data
HU Jie
(a.Laboratory of Machine Perception， b.Dept. of Machine Intelligence， School of Electronics Engineering Computer Science， c.Institute of Digital Library， Peking University， Beijing 100871， China)Abstract:Feature dimension reduction is effective in improving machine learning，the point is how to search the subset and selection criteria.This paper defined general models for dimension reduction，compared different approaches， and discussed the unresolved topics and development trends.
Key words:dimension reduction; machine learning; feature selection; feature abstraction; selection criteria
特征降維（feature dimension reduction）是一個從初始高維特征集合中選出低維特征集合，以便根據一定的評估準則最優化縮小特征空間的過程，通常作為機器學習的預處理步驟。特征降維自20世紀70年代以來就獲得了廣泛的研究。近幾年以來，在許多應用（如基因染色體組工程、文本分類、圖像檢索、消費者關系管理）中，數據的實例數目和特征數目都急劇增加，這種數據的海量性使得大量機器學習算法在可測量性和學習性能方面產生嚴重問題。例如，高維數據即具有成百上千特征的數據集，會包含大量的無關信息和冗余信息，這些信息可能極大地降低學習算法的性能。因此，當面臨高維數據時，特征降維對于機器學習任務顯得十分必要。大量研究實踐證明，特征降維能夠有效地消除無關和冗余特征，提高挖掘任務的效率，改善預測精確性等學習性能，增強學習結果的易理解性。然而，數據在數量和維度上的劇增趨勢也對特征降維算法提出了更加嚴峻的挑戰。本文給出了特征降維的相關概念介紹，概括了目前國際上常用的特征降維模型、特征降維領域的重要問題——特征選取的評價標準，并且通過列舉不同的解決方案，比較這些方案的特點。
1 特征降維相關概念
通常，高維特征集合存在以下幾方面問題：大量的特征；許多與給定任務無關的特征，即存在許多與類別僅有微弱相關度的特征；許多對于給定任務冗余的特征，如特征相互之間存在強烈的相關度；噪聲數據。
特征降維是一種降低特征維度從而提高給定任務效率的方法，可以分為特征抽取和特征選擇兩種降維方式。
1.1 特征抽取
特征抽取也被稱為特征重參數化（feature reparameterization）[1]。由于自然語言中存在大量的多義詞、同義詞現象，特征集無法生成一個最優的特征空間對數據內容進行描述。特征抽取通過將原始特征空間進行變換，重新生成一個維數更小、各維之間更獨立的特征空間。可以按照表1對特征抽取算法進行分類。
表1 特征抽取方法分類
有無指導線性非線性
無主成分分析（PCA）Kohonen匹配
無獨立成分分析（ICA）非線性PCA網絡
無投影追蹤Sammon投影
有線性區別分析非線性區別分析
1.2 特征選擇
可以看出特征抽取涉及到語義上的分析，而目前自然語言語義處理技術尚不發達，用特征抽取方法進行特征降維的效果并不顯著。相比之下，特征選擇選出的特征集合是原始特征集的子集，所以更易實現，方法也更加多樣，典型的有DF、IG、MI、CHI。
1.3 特征降維策略
從策略上可以將特征降維劃分為局部降維和全局降維。局部降維是指對每個類別選擇若干個最能識別它的特征作為新特征，由所有這些新特征構成新的特征空間，從而達到對原始特征空間的降維。全局降維是指選擇對整個分類最有用的若干個特征構成新的特征空間，從而達到對原特征空間的降維。對于不同的降維方法，可采用的降維策略可能不同，但是通過特殊處理（如帶權均值、最大值）后，特征對特定類的重要性也可以轉換成特征對整個分類的重要性。
2 特征降維模型
特征降維是一個從初始高維特征集合中選出低維特征集合，以便根據一定的評估準則最優化縮小特征空間的過程。綜合國際上現有的特征降維模型，可以將特征降維模型作如下定義。定義1 特征降維模型是一個四元組{F，S，P，R(si，fj)}。其中：
a)F是特征集合中的一組特征邏輯視圖，稱為特征的表示；
b)S是一組目標特征需求的邏輯視圖，稱為降維目標；
c)P是一種機制，用于構建特征表示、降維目標及它們之間關系的模式；
d)R(si，fj)是排序函數，該函數輸出一個與降維si∈S和特征表示fj∈F有關的實數，這樣就在特征之間根據降維目標si定義了一個順序。
可以將現有的特征降維模型大致分為過濾模型、包裹模型及其他改進模型。
2.1 過濾模型
過濾模型（filter model）的基本思想是：根據訓練數據的一般特性進行特征選擇，在特征選擇的過程中并不包含任何學習算法。早期的過濾算法依賴于標記數據，通過分析標記數據來決定哪些特征在區分類標簽時最有用，因此傳統過濾模型只適用于有指導的學習。隨著應用領域的擴展，在很多數據挖掘應用中無法獲得類標簽，因此將傳統過濾模型結合聚類思想，如層次聚類[2，3]、分割聚類[4，5]、光譜聚類[6]、矩陣分解算法[7]，可以產生許多新的適合無指導學習的過濾模型。目前國際上常用的基于過濾模型的特征選擇算法主要有兩類，即特征權重和子集搜索。這兩類算法的不同之處在于是對單個特征進行評價還是對整個特征子集進行評價。
2.1.1 特征權重算法
特征權重算法為每個特征指定一個權值，并按照它與目標概念的相關度對其進行排序，如果一個特征的相關度權值大于某個閾值，則認為該特征優秀，并且選擇該特征。特征權重算法的缺點在于：它們可以捕獲特征與目標概念間的相關性，卻不能發現特征間的冗余性。經驗證明除了無關特征對學習任務的影響，冗余特征同樣影響學習算法的速度和準確性，也應盡可能消除冗余特征。
Kira和Rendell 提出的Relief算法[8]是一個比較著名的特征權重類方法，主要根據特征值在同類實例中以及相近的不同類實例中的區分能力來評價特征的相關度。首先從訓練集中隨機抽取m個實例，再根據被選實例與兩個最近實例（一個同類最近實例，一個相反類最近實例）的差異來更新每個特征的相關度評價，依賴相關度評價進行特征選擇。其對于含M個實例、N個特征的數據集Relief的時間復雜度為O(mMN)。因此，該算法很適合于處理具有大量實例的高維數據集。但是，Relief不能消除冗余特征，只要特征被認為與類概念相關即被選中，即使這些特征之間相互高度關聯。近幾年，許多學者紛紛就Relief的改進提出了各種建議，如Sun Yijun最新提出的IRelief算法[9]通過探索期望最大化算法的框架，認為迭代Relief算法能夠減輕Relief的不足，并使用新的多類別邊緣定義將IRelief擴展至多類別設置，同時減少計算開銷、發展在線學習算法。
2.1.2 子集搜索算法
子集搜索算法通過在一定的度量標準指導下遍歷候選特征子集，對每個子集進行優劣評價，當搜索停止時即可選出最優（或近似最優）的特征子集。現有子集搜索算法的時間復雜度至少為維度的平方，所以在處理高維數據時不具有強可量測性。Nakariyakui和Casasent最新提出的分支跳躍算法[10]通過避免對解決方案樹中某些節點不必要的評價函數計算來提高搜索速度。該算法包含以下新特性：a）在構造樹的過程中將節點按照特征重要性進行排序；b）通過一個流動搜索方法獲得一個較大的優秀初始范圍；c）使用新的決策方法在樹中選擇一個開始搜索層；d）使用新的適應性跳躍搜索策略來選擇下一步搜索層以避免多余的評價計算。
2.2 多層過濾模型
考慮到各種過濾方法各有優劣，可以使用多層過濾模型分別消除無關特征和冗余特征。多層過濾模型不僅能夠保留各種過濾算法的優點，而且該模型易于理解和執行。對于消除無關特征和冗余特征的次序，模型中沒有明確限定，可以根據數據集合的特點以及應用特性，選擇適合的過濾算法及過濾步驟。多層過濾模型的框架如圖1所示。
Li等人[11]提出的多層過濾模型中首先使用ReliefF[12]通過為每個特征指定相關權重來移除無關特征。ReliefF算法是針對Relief的改進算法，它具有魯棒性，能夠處理不完整數據、噪聲數據以及多重類別問題，然而在移除冗余數據方面效率較差。因此，Li等人又在系統中使用特征聚類算法KNNC[13]來消除冗余特征。假設訓練樣本數為s，原始特征數為n，則ReliefF和KNNC的時間復雜度分別為O(s2n)和O(n2s)。使用多層過濾模型對海量特征進行特征選擇時，應當將時間復雜度低的算法先于其他算法運行。如果n>>s，則KNNC應當在ReliefF之后運行（記為R+K），以ReliefF的輸出作為KNNC的輸入；如果s>>n，則KNNC應先于ReliefF運行（記為K+R），并將KNNC的輸出作為ReliefF的輸入。因為R+K時ReliefF過濾得到的特征具有權重，所以在KNNC進行特征選擇后，應當再對余下的未選中特征進行逐個檢查，以確定該特征是否基于局部有效而非基于全局判斷。如果某特征權重大于已選中特征子集的最大權重，則將該特征收入最終子集。通過對上述各種方式進行實驗，得出如表2所示的比較結果。
表2 實驗結果
數據集算法（參數）平均準確率/%標準偏差（k=3）降維率/%
IonosphereReliefF(0.01)84.80.3015.6
IonosphereKNNC(k=16)84.90.3048.5
IonosphereK+R(k=18)87.30.2766.8
IonosphereR+K(k=16)840.3060
Ionosphere原始特征集84.60.300
SonarReliefF(0.01)78.70.3021.7
SonarKNNC(k=16)76.30.3040.3
SonarK+R(k=10)78.70.3045
SonarR+K(k=8)77.70.3042.5
Sonar原始特征集78.90.310
SpectfReliefF(0.01)71.80.3218
SpectfKNNC(k=20)700.3351
SpectfK+R(k=14)710.3057
SpectfR+K(k=14)70.80.3155
Spectf原始特征集710.330
2.3 包裹模型
包裹模型（wrapper model）最早由Kohavi和John[14]提出，最初思想為依據一個有指導的歸納算法，搜索最佳特征子集；對于每一個新的特征子集，包裹模型都需要學習一個假設（或一個分類器、包裹器），即需要元學習者遍歷特征集合空間，并且利用該學習算法的性能來評價和決定選擇哪些特征。目前研究中包裹模型的搜索過程主要依據一個聚類算法（圖2 ）。在大多數聚類算法中都要求用戶給出簇的數目，并且只是通過簡單的排序選擇特征詞，而不考慮特征詞在聚類過程中的影響。包裹模型包含聚類過程反饋，將聚類執行效果量化為性能指數，通過最大化該性能指數更好地找出那些更適合預定學習算法的特征，具有較高的學習性能。基于模式選擇的聚類有效性算法[15]的主要思想是：首先從整個文檔集出現的所有詞匯中選擇活躍詞匯；然后對每一個可能的簇數目值，使用無指導的特征選取算法精煉活躍詞匯集；再利用sIB[16]等算法對簇結構進行評估，從中選擇最滿足簇有效性標準的特征子集和簇的個數。
包裹模型需要解決的兩個主要問題是：a）找出與特征選擇相關的簇的個數；b）規范化特征選擇標準與維度的偏差。在這方面比較著名的算法有基于期望值最大化的特征子集選擇FSSEM[17]。該算法使用前序搜索SFS對特征集合進行貪心選擇，從0個特征開始逐次增添新的特征，新添特征在用于結合已選特征時應能夠提供最大的評估值。雖然SFS不是最優搜索算法，但是因為其簡單有效性而被廣泛使用。可以針對不同的應用，選擇更加合適的搜索策略，如窮盡搜索[18]、完全搜索[19]、啟發式搜索[20]、概率搜索[21]、混合搜索，以及聚類和特征選擇評估標準用于包裹模型中。
通常包裹模型的計算復雜度要比過濾模型高得多，當處理現實問題時，特征數量變得非常大，因此通常為了計算效率而選擇過濾模型。近幾年來隨著對網絡信息資源的研究發展，包裹模型的應用主要集中在對Web數據等半結構化、無結構數據的信息抽取研究。Raposo等人[22]針對半結構化網絡資源提出一種新的啟發性算法用于在規范化包裹操作的過程中收集查詢結果并且以結構化方式返回結果；當資源發生變化時，將先前收集的結果作為輸入產生一系列資源標記樣本用于引導新的包裹過程。Zheng等人[23]提出利用網頁間的相似性來探測模板，通過區分具有顯著內部差異的頁面用于分別產生包裹器，以提高特征抽取的搜索效率。
2.4 混合模型
根據上述介紹可以看出，過濾模型與包裹模型的發展都經歷了一個由有指導學習向無指導學習轉變的過程，因此現代過濾模型與包裹模型的根本區別在于對學習算法的使用方式。過濾模型首先利用數據的內在特性(如詞頻、詞性)而不是聚類算法對原始特征集進行初步選擇；最后將選出的特征子集用于聚類。反之，包裹模型將聚類算法與特征搜索、選擇過程相結合，將無指導的學習算法應用于每個候選特征子集，利用聚類結果對特征子集進行評價，最終形成優化特征子集。
混合模型著眼于使用一種特殊的算法將過濾模型與包裹模型相結合以獲得盡可能好的性能，并且使得時間復雜度與過濾算法相近。可以首先通過一個基于特征內部特性的評價度量標準針對給定的集合勢選擇最優子集，然后利用交叉有效性等方法來決定不同勢間的最終最優子集。為了避免傳統過濾算法中對標記數據的要求以及包裹模型時間復雜度高的限制，Whiteson等人提出FSNEAT算法[24]將特征選擇與學習任務相結合。FSNEAT是對NEAT算法的擴展，它從最小拓撲網絡開始計算，在搜索優化特征集合的同時對接受這些特征的網絡進行訓練。通過同時學習網絡的輸入、拓撲、權重，FSNEAT可以不依賴于元學習或標記數據而自動為網絡的演化測定適當的輸入集，解決特征選取問題。Sebban等人[25]提出基于信息理論的混合過濾/包裹特征選擇方法將學習過程中建立的最小生成樹MST所包含的幾何信息轉換為相關度收益，以此對特征進行過濾選擇。
3 特征評價標準
如何評價待選特征與降維目標的相關度是特征降維的關鍵問題之一。特征評價方法從評測對象上可以分為單邊度量與雙邊度量兩種。單邊度量只考慮正特征，即最能標示其成員資格的特征，而忽略負特征即最能標示其非成員資格的特征，如相關性系數CC和幾率評測OR。雙邊度量將正負特征結合考慮，如信息增益IG和卡方檢測CHI（Chisquare）。事實上，因為負特征在數據中的出現，較大程度地說明了該數據的無關性，所以負特征有助于確定消除無關數據，在不平衡的數據集合中對負特征的分析顯得更為重要。Zheng等人[26]提出將正負特征優化相結合的思想，對每一個類別分別計算出該類對應的正特征集合和負特征集合，按照經驗將正負特征集以一定的比例組合，力圖使學習性能達到最優。
在特征子集的優化選擇過程中，使用不同的特征評價準則可能會得出不同的結果，可以將目前國際上常用的評價度量方法分為一致性度量和相關性度量兩個大類。本章將重點給出這兩類度量評測的介紹，并對其應用情況、相關改進算法進行分析比較。
能夠有效消除無關特征和冗余特征，同時還能將數據中的某些噪聲轉換為不一致性處理。
目前對一致性度量的研究應用主要集中在對圖像、聲音等多媒體的模式識別中。Kim等人[28]提出的外觀克隆方法可以從一系列以任意多鏡頭視角分布拍攝的照片中進行有效的照片一致性場景恢復，其中使用一種自我約束的貪心類優化方法迭代搜索圖像空間尋找最具有照片一致性的形狀，搜索過程基于概率形狀照片一致性度量對候選的形狀特征進行可能性比較。大量場景實驗表明，如果給出足夠多的外觀用于反映場景特征，則該外觀克隆方法能夠不依賴于任何場景算法而成功地恢復場景的幾何信息及光學信息。Pons等人[29]提出一種從多重視頻序列中評估多角度立體視角和非網格三維運動的新方法，通過計算輸入圖像與預期圖像間的全局圖像匹配值，而不是在每個表面獨立地計算匹配值，綜合利用鄰近和全局亮度信息來提高對非Lambertian原料以及光學變化產生的外觀變化的魯棒性。該方法可以完全解決投影扭曲和局部閉塞問題，最小化形狀和運行評估的預計誤差。
3.2 相關性度量
相關度也被稱為規范化相關性、相關系數、皮爾森關聯、余弦相似度，被廣泛用于描述模式分類和信號處理問題中兩個向量之間的相似性。相關性度量基于以下思想：如果一個特征與某個類的關聯性高到（或可預言到）使該特征與此類相關，同時此特征與其他相關特征的關聯性不能達到任何相關特征都可以預言該特征的水平，則認為這個特征是對該分類任務的優秀特征。可以將國際上常用的相關度度量分為傳統的線性相關性度量和基于信息理論的相關性度量。Yu和Liu提出的FCBF算法[30]以及Koller和Sahami提出的Markov Blanket過濾方法[31]均是典型的基于相關性度量對特征進行排序的過濾算法。實驗表明此類算法能夠有效地消除無關特征和冗余特征，并且具有較低的時間復雜度。
3.2.1 傳統線性相關性度量
在早期的研究中通常使用距離函數度量變量的相似性，例如歐氏距離和馬氏距離。對于二分類問題，如果特征x導致兩個類別條件概率的區別大于特征y，則特征x優于y；如果區別為0，則x和y不可辨別。歐氏距離是一個通常采用的距離定義，它是在m維空間中兩點之間的真實距離。歐氏距離雖然很有用，但也有明顯的缺點。它將樣品的不同屬性（即各指標或各變量）之間的差別等同看待，而實際研究中，經常遇到對個體的分析和判別，個體的不同屬性對于區分個體有著不同的重要性。因此，有時需要采用不同的距離函數。馬氏距離通過允許任意的線性縮放和特征空間旋轉將歐氏距離進行推的將線性相關系數依據具體應用環境作適當校正可產生各種新的評價準則，有效提高特征選取的準確率，如最小平方回歸誤差、最大信息壓縮指數。KNNC算法[13]使用最大信息壓縮指數作為特征相似性度量，實驗證明KNNC可有效消除冗余特征。該方法首先運用特征相關性將原始特征集分為許多個相似子集；然后從每個簇中選擇代表性特征，同時消除其他特征。由于KNNC算法并不基于檢索，具有較小的時間復雜度，但該算法在每次消除冗余特征時不對剩余特征進行無關性分類，在消除無關特征方面尚有不足。
選擇線性相關性作為分類中的特征評價準則有以下優點：a）有助于消除與類別相關度接近0的特征，即消除無關特征；b）有助于減小選中特征的冗余度，消除冗余特征。線性相關的缺點在于需要所有特征具有數值表示才能進行計算，并且不能捕獲現實世界中非線性的關聯。在簡單相關系數的基礎上又發展出了復相關系數、偏相關系數、典型相關系數等相關性度量方法。復相關又叫多重相關系數，是指因變量與多個自變量之間的相關關系，如某種商品的需求量與預期價格水平、職工收入水平等現象之間呈現多重相關關系。偏相關系數又被稱為部分相關系數，反映校正其他變量后某一變量與另一變量的相關關系。偏相關系數的假設檢驗等同于偏回歸系數的t檢驗；復相關系數的假設檢驗等同于回歸方程的方差分析。典型相關系數是指先對原來各組變量進行主成分分析，得到新的線性無關的綜合指標，再用兩組之間綜合指標的直線相關系數來研究原兩組變量間的相關關系。
3.2.2 基于信息理論的相關性度量
信息論是一門用數理統計方法研究信息度量、傳遞和變換規律的科學。基于信息理論的相關性度量關鍵在于評測從特征中獲取的信息，如果從特征X中獲取的信息比特征Y熵用于測量隨機變量的不確定性；度量的是消息中所含的信息量，其中去除了由消息固有結構所決定的部分，如語言結構的冗余性以及語言中字母、詞的使用頻度等統計特性。變量
互信息[32]是另一種常用的信息度量，用于評測隨機變量間的依賴性，它總是具有對稱、非負性，互信息的值越大說明變量間的依賴性越強。互信息取值為0當且僅當變量
B中刪除；d）重復進行以上貪心選擇步驟直到選完足夠數目的特征。實驗證明MIFS能夠有效地選取出相關特征，但是該算法只考慮了單個特征與目標類的相互依賴性而沒有對特征之間的相關度進行評測，因此MIFS算法不能解決冗余特征對神經網絡學習的影響。近幾年來諸多研究人員在MIFS的基礎上又提出了各種改進算法，如MIFSFS、MIF用互信息對變量間的相關度進行度量，但度量范圍從單個特征與目標類的MI計算擴展為特征空間與目標類的MI計算。此類算法的優點在于能夠同時消除冗余特征及無關特征，顯著改善訓練神經網絡分類器的效率和準確性，可將其應用于為識別高精度數字圖像中的潛在對象而自動構造特征；缺點是時間開銷較大。
特征評價標準本身并不受特征子集選取策略的影響，即上述度量方法可以用于有指導的特征選取，也適用于無指導的特征選取。其區別在于：有指導的選擇過程度量特征子集在分類中的能力；無指導的選擇過程度量特征子集在聚類中的能力。隨著特征評測研究的發展，如何借鑒融合各種度量的優點成為新的研究趨勢，如Davis等人[36]最新提出的利用信息理論學習馬氏距離函數，用于解決在距離函數約束下最小化兩個多元高斯量之間的微分相關熵。
4 結束語
根據上述分析，針對高維數據的特征降維研究，當前已經提出了許多有效的特征降維模型，總的來說可以分為過濾模型和包裹模型兩類，其區別在于是基于特征的內在特性還是基于學習算法的性能對特征進行選取。特征子集的搜索過程和選用的特征評價標準是特征降維的兩個關鍵問題，根據具體應用環境制定適當的搜索策略與一定特征度量準則相結合能夠有效地去除無關特征、冗余特征，實現高效的特征降維，提高機器學習的效率。隨著自然語言處理技術的發展，以語義分析為基礎的特征抽取技術必將得到進一步發展；如何捕捉現實世界中非線性的關聯，將特征判別從距離空間轉向相關度度量空間依然是機器學習的研究熱點。特征降維的應用領域也從傳統的靜態文本分類、聚類轉向對半結構化網絡資源的數據挖掘，對音頻、視頻等多媒體資源的機器學習，以及對生物基因特征的分析識別等。
參考文獻：
［1］SCHUTZE H，HULL D A，PEDERSEN J O.A comparison of classifiers and document representations for the routing problem[C]//Proc of the 18th ACM Int Conf on Research and Development in Information Retrieval.New York:ACM，1995:229-237.
［2］CUTTING D R，KARGER D R，PEDERSON J O，et al.Scatter/gather:a clusterbased approach to browsing large document collections[C]//Proc of the 15th Annual Int ACM SIGIR Conf on Research and Development in Information Retrieval.New York:ACM，1992:318-329.
［3］SCHUTEZ H，SILVERSTEIN C.Projections for efficient document clustering[C]//Proc of the 20th Annual Int ACM SIGIR Conf on Research and Development in Information Retrieval.New York:ACM，1997:74-81.
［4］DHILLON I S，MALLELA S，MODHA S.Information theoretic coclustering[C]//Proc of the 9th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining.New York:ACM，2003:89-98
［5］PANTEL P，LIN D.Document clustering with committees[C]//Proc of the 25th Annual Int ACM SIGIR Conf on Research and Development in Information Retrieval.2002:199-206.
［6］ZHA H，HE X，DING C，et al.Bipartite graph partitioning and data clustering[C]//Proc of the 10th ACM Conf on Information and Knowledge Management.New York:ACM，2001:25-32.
［7］XU W，LIN X，GONG Y.Document clustering based on nonnegative matrix factorization[C]//Proc of the 26th Annual Int ACM SIGIR Conf on Research and Development in Information Retrieval.New York:ACM，2003:267-273.
［8］KONONERKO I. Estimating attributes: analysis and extension of relief[C]//Proc of European Conf on Machine Learning.1994:171182.
［9］SUN Yijun.Iterative relief for feature weighting: algorithms， theories， and applications[J].IEEE Trans on Pattern Analysis and Machine Intelligence，2007，29(6):10351051.［10］NAKARIYAKUI S，CASASENT D P.Adaptive branch and bound algorithm for selecting optimal features[J].Pattern Recognition Letters，2007，28(12):14151427.
［11］LI Y，WU Z F，LIU J M，et al.Efficient feature selection for highdimensional data using twolevel filter[C]//Proc of Int Conf on Machine Learning and Cybernetics.[S.l.]:IEEE CNF，2004:17111716.
［12］SIKONJA M K，KONONENKO I.An adaptation of relief for attribute estimation in regression[C]//Proc of the 14th Int Conf on Machine Learning.San Francisco:Morgan Kaufmann Publishers，1997:296-304.
［13］MITRA P，MURTHY C A，PAL S K.Unsupervised feature selction using feature similarity[J].IEEE Trans on Pattern Recognition and Machine Intelligence，2002，24(3):301-312.
［14］KOHAVI R，JOHN G H.Wrappers for feature subset selection[J].Artificial Intelligence，1997，97(1-2):273-324.
［15］NIU Z Y，JI D H，TAN C L.Document clustering based on cluster validation[C]//Proc of the 13th ACM Conf on Information and Knowledge Management.New York:ACM，2004:501-506.
［16］SLONIM N，FRIEDMAN N，TISHBY N.Unsupervised document classification using sequential information maximization[C]//Proc of the 25th Annual Int ACM SIGIR Conf on Research and Development in Information Retrieval.New York:ACM，2002:129136.
［17］DY J，BRODLEY C.Feature subset selection and order identification for unsupervised learning[C]//Proc of the 17th Int Conf on Machine Learning.San Francisco:Morgan Kaufmann Publishers，2000:247-254.
［18］ALMUALLIM H，DIETTERICH T G.Learning Boolean concepts in the presence of many irrelevant features[J].Artificial Intelligence，1994，69(1-2):279-305.
［19］LIU H，MOTODA H，DASH M.A monotonic measure for optimal feature selection[C]//Proc of the 10th European Conf on Machine Learning.London:SpringerVerlag，1998:101106.
［20］DASH M.Feature selection via set cover[C]//Proc of IEEE Knowledge and Data Engineering Exchange Workshop.Washington DC:IEEE Computer Society，1997.
［21］LIU H，SETIONO R. Feature selection and classification: a probabilistic wrapper approach[C]//Proc of the 19th Int Conf on Industrial and Engineering Applications of AI and ES.1996.
［22］RAPOSO P，PAN P，ALVAREZ M，et al.Automatically maintaining wrappers for semistructured Web sources[J].Data Knowledge Engineering，2007，61(2):331-358.
［23］ZHENG S Y，SONG R H，WEN J R，et al.Joint optimization of wrapper generation and template detection[C]//Proc of the 13th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining.New York:ACM，2007:894-902.
［24］WHITESON S， STONE P， STANLEY K O，et al.Automatic feature selection in neuroevolution[C]//Proc of Conf on Genetic and Evolutionary Computation.New York:ACM，2005:12251232.
［25］SEBBAN M，NOCK R.A hybrid filter/wrapper approach of feature selection using information theory[J].Pattern Recognition，2002，35:835-846.
［26］ZHENG Z H，WU X Y，SRIHARI R.Feature selection for text categorization on imbalanced data[J].ACM SIGKDD Explorations Newsletter，2004，6(1):80-89.
［27］DASH M，LIU H，MOTODA H.Consistency based feature selection[C]//Proc of the 4th PacificAsia Conf on Knowledge Discovery and Data Mining， Current Issues and New Applications.London:SpringerVerlag，2000:98109.
［28］KIM H，KWEON I S.Appearancecloning:photoconsistent scene recovery from multiview images[J].International Journal of Computer Vision，2006，66(2):163192.
［29］PONS J P，KERIVEN R，FAUGERAS O.Multiview stereo reconstruction and scene flow estimation with a global imagebased matching score[J].International Journal of Computer Vision，2007，72(2):179193.
［30］YU L，LIU H.Feature selection for highdimensional data: a fast correlationbased filter solution[C]//Proc of the 20th Int Conf on Machine Learning， ICML2003.Washington DC:[s.n.]，2003.
［31］KOLLER D，SAHAMI M.Towards optimal feature selection[C]//Proc of the 13th Int Conference on Machine Learning.1996:284-292.
［32］HAYKIN S.Neural networks : a comprehensive foundation[M].2nd ed.[S.l.]: Prentice Hall，1998.
［33］BATTITI R.Using mutual information for selecting features in supervised neutral net learning[J].IEEE Trans on Neural Networks，1994，5:537-550.
［34］CANG S，YU H N.A new approach for detecting the best feature set[C]//Proc of Networking， Sensing and Control.[S.l.]:IEEE CNF，2005:74-79.
［35］KWAK N，CHOI C H.Input feature selection for classification problems[J].IEEE Trans on Neural Networks，2002，13(1):143159.
［36］DAVIS J V，KULIS B，JAIN P，et al.Informationtheoretic metric learning[C]//Proc of the 24th Int Conf on Machine Learning.New York:ACM，2007:209-216.
