高維數(shù)據(jù)特征降維研究綜述
2008-12-31 00:00:00胡潔
計算機應(yīng)用研究 2008年9期
摘 要：特征降維能夠有效地提高機器學(xué)習(xí)的效率，特征子集的搜索過程以及特征評價標(biāo)準(zhǔn)是特征降維的兩個核心問題。綜述國際上關(guān)于特征降維的研究成果，總結(jié)并提出了較完備的特征降維模型定義；通過列舉解決特征降維上重要問題的各種方案來比較各種算法的特點以及優(yōu)劣，并討論了該方向上尚未解決的問題和發(fā)展趨勢。
關(guān)鍵詞：降維；機器學(xué)習(xí)；特征選擇；特征抽取；評估準(zhǔn)則
中圖分類號：TP181 文獻(xiàn)標(biāo)志碼：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）是一個從初始高維特征集合中選出低維特征集合，以便根據(jù)一定的評估準(zhǔn)則最優(yōu)化縮小特征空間的過程，通常作為機器學(xué)習(xí)的預(yù)處理步驟。特征降維自20世紀(jì)70年代以來就獲得了廣泛的研究。近幾年以來，在許多應(yīng)用（如基因染色體組工程、文本分類、圖像檢索、消費者關(guān)系管理）中，數(shù)據(jù)的實例數(shù)目和特征數(shù)目都急劇增加，這種數(shù)據(jù)的海量性使得大量機器學(xué)習(xí)算法在可測量性和學(xué)習(xí)性能方面產(chǎn)生嚴(yán)重問題。例如，高維數(shù)據(jù)即具有成百上千特征的數(shù)據(jù)集，會包含大量的無關(guān)信息和冗余信息，這些信息可能極大地降低學(xué)習(xí)算法的性能。因此，當(dāng)面臨高維數(shù)據(jù)時，特征降維對于機器學(xué)習(xí)任務(wù)顯得十分必要。大量研究實踐證明，特征降維能夠有效地消除無關(guān)和冗余特征，提高挖掘任務(wù)的效率，改善預(yù)測精確性等學(xué)習(xí)性能，增強學(xué)習(xí)結(jié)果的易理解性。然而，數(shù)據(jù)在數(shù)量和維度上的劇增趨勢也對特征降維算法提出了更加嚴(yán)峻的挑戰(zhàn)。本文給出了特征降維的相關(guān)概念介紹，概括了目前國際上常用的特征降維模型、特征降維領(lǐng)域的重要問題——特征選取的評價標(biāo)準(zhǔn)，并且通過列舉不同的解決方案，比較這些方案的特點。
1 特征降維相關(guān)概念
通常，高維特征集合存在以下幾方面問題：大量的特征；許多與給定任務(wù)無關(guān)的特征，即存在許多與類別僅有微弱相關(guān)度的特征；許多對于給定任務(wù)冗余的特征，如特征相互之間存在強烈的相關(guān)度；噪聲數(shù)據(jù)。
特征降維是一種降低特征維度從而提高給定任務(wù)效率的方法，可以分為特征抽取和特征選擇兩種降維方式。
1.1 特征抽取
特征抽取也被稱為特征重參數(shù)化（feature reparameterization）[1]。由于自然語言中存在大量的多義詞、同義詞現(xiàn)象，特征集無法生成一個最優(yōu)的特征空間對數(shù)據(jù)內(nèi)容進(jìn)行描述。特征抽取通過將原始特征空間進(jìn)行變換，重新生成一個維數(shù)更小、各維之間更獨立的特征空間。可以按照表1對特征抽取算法進(jìn)行分類。
表1 特征抽取方法分類
有無指導(dǎo)線性非線性
無主成分分析（PCA）Kohonen匹配
無獨立成分分析（ICA）非線性PCA網(wǎng)絡(luò)
無投影追蹤Sammon投影
有線性區(qū)別分析非線性區(qū)別分析
1.2 特征選擇
可以看出特征抽取涉及到語義上的分析，而目前自然語言語義處理技術(shù)尚不發(fā)達(dá)，用特征抽取方法進(jìn)行特征降維的效果并不顯著。相比之下，特征選擇選出的特征集合是原始特征集的子集，所以更易實現(xiàn)，方法也更加多樣，典型的有DF、IG、MI、CHI。
1.3 特征降維策略
從策略上可以將特征降維劃分為局部降維和全局降維。局部降維是指對每個類別選擇若干個最能識別它的特征作為新特征，由所有這些新特征構(gòu)成新的特征空間，從而達(dá)到對原始特征空間的降維。全局降維是指選擇對整個分類最有用的若干個特征構(gòu)成新的特征空間，從而達(dá)到對原特征空間的降維。對于不同的降維方法，可采用的降維策略可能不同，但是通過特殊處理（如帶權(quán)均值、最大值）后，特征對特定類的重要性也可以轉(zhuǎn)換成特征對整個分類的重要性。
2 特征降維模型
特征降維是一個從初始高維特征集合中選出低維特征集合，以便根據(jù)一定的評估準(zhǔn)則最優(yōu)化縮小特征空間的過程。綜合國際上現(xiàn)有的特征降維模型，可以將特征降維模型作如下定義。定義1 特征降維模型是一個四元組{F，S，P，R(si，fj)}。其中：
a)F是特征集合中的一組特征邏輯視圖，稱為特征的表示；
b)S是一組目標(biāo)特征需求的邏輯視圖，稱為降維目標(biāo)；
c)P是一種機制，用于構(gòu)建特征表示、降維目標(biāo)及它們之間關(guān)系的模式；
d)R(si，fj)是排序函數(shù)，該函數(shù)輸出一個與降維si∈S和特征表示fj∈F有關(guān)的實數(shù)，這樣就在特征之間根據(jù)降維目標(biāo)si定義了一個順序。
可以將現(xiàn)有的特征降維模型大致分為過濾模型、包裹模型及其他改進(jìn)模型。
2.1 過濾模型
過濾模型（filter model）的基本思想是：根據(jù)訓(xùn)練數(shù)據(jù)的一般特性進(jìn)行特征選擇，在特征選擇的過程中并不包含任何學(xué)習(xí)算法。早期的過濾算法依賴于標(biāo)記數(shù)據(jù)，通過分析標(biāo)記數(shù)據(jù)來決定哪些特征在區(qū)分類標(biāo)簽時最有用，因此傳統(tǒng)過濾模型只適用于有指導(dǎo)的學(xué)習(xí)。隨著應(yīng)用領(lǐng)域的擴展，在很多數(shù)據(jù)挖掘應(yīng)用中無法獲得類標(biāo)簽，因此將傳統(tǒng)過濾模型結(jié)合聚類思想，如層次聚類[2，3]、分割聚類[4，5]、光譜聚類[6]、矩陣分解算法[7]，可以產(chǎn)生許多新的適合無指導(dǎo)學(xué)習(xí)的過濾模型。目前國際上常用的基于過濾模型的特征選擇算法主要有兩類，即特征權(quán)重和子集搜索。這兩類算法的不同之處在于是對單個特征進(jìn)行評價還是對整個特征子集進(jìn)行評價。
2.1.1 特征權(quán)重算法
特征權(quán)重算法為每個特征指定一個權(quán)值，并按照它與目標(biāo)概念的相關(guān)度對其進(jìn)行排序，如果一個特征的相關(guān)度權(quán)值大于某個閾值，則認(rèn)為該特征優(yōu)秀，并且選擇該特征。特征權(quán)重算法的缺點在于：它們可以捕獲特征與目標(biāo)概念間的相關(guān)性，卻不能發(fā)現(xiàn)特征間的冗余性。經(jīng)驗證明除了無關(guān)特征對學(xué)習(xí)任務(wù)的影響，冗余特征同樣影響學(xué)習(xí)算法的速度和準(zhǔn)確性，也應(yīng)盡可能消除冗余特征。
Kira和Rendell 提出的Relief算法[8]是一個比較著名的特征權(quán)重類方法，主要根據(jù)特征值在同類實例中以及相近的不同類實例中的區(qū)分能力來評價特征的相關(guān)度。首先從訓(xùn)練集中隨機抽取m個實例，再根據(jù)被選實例與兩個最近實例（一個同類最近實例，一個相反類最近實例）的差異來更新每個特征的相關(guān)度評價，依賴相關(guān)度評價進(jìn)行特征選擇。其對于含M個實例、N個特征的數(shù)據(jù)集Relief的時間復(fù)雜度為O(mMN)。因此，該算法很適合于處理具有大量實例的高維數(shù)據(jù)集。但是，Relief不能消除冗余特征，只要特征被認(rèn)為與類概念相關(guān)即被選中，即使這些特征之間相互高度關(guān)聯(lián)。近幾年，許多學(xué)者紛紛就Relief的改進(jìn)提出了各種建議，如Sun Yijun最新提出的IRelief算法[9]通過探索期望最大化算法的框架，認(rèn)為迭代Relief算法能夠減輕Relief的不足，并使用新的多類別邊緣定義將IRelief擴展至多類別設(shè)置，同時減少計算開銷、發(fā)展在線學(xué)習(xí)算法。
2.1.2 子集搜索算法
子集搜索算法通過在一定的度量標(biāo)準(zhǔn)指導(dǎo)下遍歷候選特征子集，對每個子集進(jìn)行優(yōu)劣評價，當(dāng)搜索停止時即可選出最優(yōu)（或近似最優(yōu)）的特征子集。現(xiàn)有子集搜索算法的時間復(fù)雜度至少為維度的平方，所以在處理高維數(shù)據(jù)時不具有強可量測性。Nakariyakui和Casasent最新提出的分支跳躍算法[10]通過避免對解決方案樹中某些節(jié)點不必要的評價函數(shù)計算來提高搜索速度。該算法包含以下新特性：a）在構(gòu)造樹的過程中將節(jié)點按照特征重要性進(jìn)行排序；b）通過一個流動搜索方法獲得一個較大的優(yōu)秀初始范圍；c）使用新的決策方法在樹中選擇一個開始搜索層；d）使用新的適應(yīng)性跳躍搜索策略來選擇下一步搜索層以避免多余的評價計算。
2.2 多層過濾模型
考慮到各種過濾方法各有優(yōu)劣，可以使用多層過濾模型分別消除無關(guān)特征和冗余特征。多層過濾模型不僅能夠保留各種過濾算法的優(yōu)點，而且該模型易于理解和執(zhí)行。對于消除無關(guān)特征和冗余特征的次序，模型中沒有明確限定，可以根據(jù)數(shù)據(jù)集合的特點以及應(yīng)用特性，選擇適合的過濾算法及過濾步驟。多層過濾模型的框架如圖1所示。
Li等人[11]提出的多層過濾模型中首先使用ReliefF[12]通過為每個特征指定相關(guān)權(quán)重來移除無關(guān)特征。ReliefF算法是針對Relief的改進(jìn)算法，它具有魯棒性，能夠處理不完整數(shù)據(jù)、噪聲數(shù)據(jù)以及多重類別問題，然而在移除冗余數(shù)據(jù)方面效率較差。因此，Li等人又在系統(tǒng)中使用特征聚類算法KNNC[13]來消除冗余特征。假設(shè)訓(xùn)練樣本數(shù)為s，原始特征數(shù)為n，則ReliefF和KNNC的時間復(fù)雜度分別為O(s2n)和O(n2s)。使用多層過濾模型對海量特征進(jìn)行特征選擇時，應(yīng)當(dāng)將時間復(fù)雜度低的算法先于其他算法運行。如果n>>s，則KNNC應(yīng)當(dāng)在ReliefF之后運行（記為R+K），以ReliefF的輸出作為KNNC的輸入；如果s>>n，則KNNC應(yīng)先于ReliefF運行（記為K+R），并將KNNC的輸出作為ReliefF的輸入。因為R+K時ReliefF過濾得到的特征具有權(quán)重，所以在KNNC進(jìn)行特征選擇后，應(yīng)當(dāng)再對余下的未選中特征進(jìn)行逐個檢查，以確定該特征是否基于局部有效而非基于全局判斷。如果某特征權(quán)重大于已選中特征子集的最大權(quán)重，則將該特征收入最終子集。通過對上述各種方式進(jìn)行實驗，得出如表2所示的比較結(jié)果。
表2 實驗結(jié)果
數(shù)據(jù)集算法（參數(shù)）平均準(zhǔn)確率/%標(biāo)準(zhǔn)偏差（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]提出，最初思想為依據(jù)一個有指導(dǎo)的歸納算法，搜索最佳特征子集；對于每一個新的特征子集，包裹模型都需要學(xué)習(xí)一個假設(shè)（或一個分類器、包裹器），即需要元學(xué)習(xí)者遍歷特征集合空間，并且利用該學(xué)習(xí)算法的性能來評價和決定選擇哪些特征。目前研究中包裹模型的搜索過程主要依據(jù)一個聚類算法（圖2 ）。在大多數(shù)聚類算法中都要求用戶給出簇的數(shù)目，并且只是通過簡單的排序選擇特征詞，而不考慮特征詞在聚類過程中的影響。包裹模型包含聚類過程反饋，將聚類執(zhí)行效果量化為性能指數(shù)，通過最大化該性能指數(shù)更好地找出那些更適合預(yù)定學(xué)習(xí)算法的特征，具有較高的學(xué)習(xí)性能。基于模式選擇的聚類有效性算法[15]的主要思想是：首先從整個文檔集出現(xiàn)的所有詞匯中選擇活躍詞匯；然后對每一個可能的簇數(shù)目值，使用無指導(dǎo)的特征選取算法精煉活躍詞匯集；再利用sIB[16]等算法對簇結(jié)構(gòu)進(jìn)行評估，從中選擇最滿足簇有效性標(biāo)準(zhǔn)的特征子集和簇的個數(shù)。
包裹模型需要解決的兩個主要問題是：a）找出與特征選擇相關(guān)的簇的個數(shù)；b）規(guī)范化特征選擇標(biāo)準(zhǔn)與維度的偏差。在這方面比較著名的算法有基于期望值最大化的特征子集選擇FSSEM[17]。該算法使用前序搜索SFS對特征集合進(jìn)行貪心選擇，從0個特征開始逐次增添新的特征，新添特征在用于結(jié)合已選特征時應(yīng)能夠提供最大的評估值。雖然SFS不是最優(yōu)搜索算法，但是因為其簡單有效性而被廣泛使用。可以針對不同的應(yīng)用，選擇更加合適的搜索策略，如窮盡搜索[18]、完全搜索[19]、啟發(fā)式搜索[20]、概率搜索[21]、混合搜索，以及聚類和特征選擇評估標(biāo)準(zhǔn)用于包裹模型中。
通常包裹模型的計算復(fù)雜度要比過濾模型高得多，當(dāng)處理現(xiàn)實問題時，特征數(shù)量變得非常大，因此通常為了計算效率而選擇過濾模型。近幾年來隨著對網(wǎng)絡(luò)信息資源的研究發(fā)展，包裹模型的應(yīng)用主要集中在對Web數(shù)據(jù)等半結(jié)構(gòu)化、無結(jié)構(gòu)數(shù)據(jù)的信息抽取研究。Raposo等人[22]針對半結(jié)構(gòu)化網(wǎng)絡(luò)資源提出一種新的啟發(fā)性算法用于在規(guī)范化包裹操作的過程中收集查詢結(jié)果并且以結(jié)構(gòu)化方式返回結(jié)果；當(dāng)資源發(fā)生變化時，將先前收集的結(jié)果作為輸入產(chǎn)生一系列資源標(biāo)記樣本用于引導(dǎo)新的包裹過程。Zheng等人[23]提出利用網(wǎng)頁間的相似性來探測模板，通過區(qū)分具有顯著內(nèi)部差異的頁面用于分別產(chǎn)生包裹器，以提高特征抽取的搜索效率。
2.4 混合模型
根據(jù)上述介紹可以看出，過濾模型與包裹模型的發(fā)展都經(jīng)歷了一個由有指導(dǎo)學(xué)習(xí)向無指導(dǎo)學(xué)習(xí)轉(zhuǎn)變的過程，因此現(xiàn)代過濾模型與包裹模型的根本區(qū)別在于對學(xué)習(xí)算法的使用方式。過濾模型首先利用數(shù)據(jù)的內(nèi)在特性(如詞頻、詞性)而不是聚類算法對原始特征集進(jìn)行初步選擇；最后將選出的特征子集用于聚類。反之，包裹模型將聚類算法與特征搜索、選擇過程相結(jié)合，將無指導(dǎo)的學(xué)習(xí)算法應(yīng)用于每個候選特征子集，利用聚類結(jié)果對特征子集進(jìn)行評價，最終形成優(yōu)化特征子集。
混合模型著眼于使用一種特殊的算法將過濾模型與包裹模型相結(jié)合以獲得盡可能好的性能，并且使得時間復(fù)雜度與過濾算法相近。可以首先通過一個基于特征內(nèi)部特性的評價度量標(biāo)準(zhǔn)針對給定的集合勢選擇最優(yōu)子集，然后利用交叉有效性等方法來決定不同勢間的最終最優(yōu)子集。為了避免傳統(tǒng)過濾算法中對標(biāo)記數(shù)據(jù)的要求以及包裹模型時間復(fù)雜度高的限制，Whiteson等人提出FSNEAT算法[24]將特征選擇與學(xué)習(xí)任務(wù)相結(jié)合。FSNEAT是對NEAT算法的擴展，它從最小拓?fù)渚W(wǎng)絡(luò)開始計算，在搜索優(yōu)化特征集合的同時對接受這些特征的網(wǎng)絡(luò)進(jìn)行訓(xùn)練。通過同時學(xué)習(xí)網(wǎng)絡(luò)的輸入、拓?fù)洹?quán)重，F(xiàn)SNEAT可以不依賴于元學(xué)習(xí)或標(biāo)記數(shù)據(jù)而自動為網(wǎng)絡(luò)的演化測定適當(dāng)?shù)妮斎爰鉀Q特征選取問題。Sebban等人[25]提出基于信息理論的混合過濾/包裹特征選擇方法將學(xué)習(xí)過程中建立的最小生成樹MST所包含的幾何信息轉(zhuǎn)換為相關(guān)度收益，以此對特征進(jìn)行過濾選擇。
3 特征評價標(biāo)準(zhǔn)
如何評價待選特征與降維目標(biāo)的相關(guān)度是特征降維的關(guān)鍵問題之一。特征評價方法從評測對象上可以分為單邊度量與雙邊度量兩種。單邊度量只考慮正特征，即最能標(biāo)示其成員資格的特征，而忽略負(fù)特征即最能標(biāo)示其非成員資格的特征，如相關(guān)性系數(shù)CC和幾率評測OR。雙邊度量將正負(fù)特征結(jié)合考慮，如信息增益IG和卡方檢測CHI（Chisquare）。事實上，因為負(fù)特征在數(shù)據(jù)中的出現(xiàn)，較大程度地說明了該數(shù)據(jù)的無關(guān)性，所以負(fù)特征有助于確定消除無關(guān)數(shù)據(jù)，在不平衡的數(shù)據(jù)集合中對負(fù)特征的分析顯得更為重要。Zheng等人[26]提出將正負(fù)特征優(yōu)化相結(jié)合的思想，對每一個類別分別計算出該類對應(yīng)的正特征集合和負(fù)特征集合，按照經(jīng)驗將正負(fù)特征集以一定的比例組合，力圖使學(xué)習(xí)性能達(dá)到最優(yōu)。
在特征子集的優(yōu)化選擇過程中，使用不同的特征評價準(zhǔn)則可能會得出不同的結(jié)果，可以將目前國際上常用的評價度量方法分為一致性度量和相關(guān)性度量兩個大類。本章將重點給出這兩類度量評測的介紹，并對其應(yīng)用情況、相關(guān)改進(jìn)算法進(jìn)行分析比較。
能夠有效消除無關(guān)特征和冗余特征，同時還能將數(shù)據(jù)中的某些噪聲轉(zhuǎn)換為不一致性處理。
目前對一致性度量的研究應(yīng)用主要集中在對圖像、聲音等多媒體的模式識別中。Kim等人[28]提出的外觀克隆方法可以從一系列以任意多鏡頭視角分布拍攝的照片中進(jìn)行有效的照片一致性場景恢復(fù)，其中使用一種自我約束的貪心類優(yōu)化方法迭代搜索圖像空間尋找最具有照片一致性的形狀，搜索過程基于概率形狀照片一致性度量對候選的形狀特征進(jìn)行可能性比較。大量場景實驗表明，如果給出足夠多的外觀用于反映場景特征，則該外觀克隆方法能夠不依賴于任何場景算法而成功地恢復(fù)場景的幾何信息及光學(xué)信息。Pons等人[29]提出一種從多重視頻序列中評估多角度立體視角和非網(wǎng)格三維運動的新方法，通過計算輸入圖像與預(yù)期圖像間的全局圖像匹配值，而不是在每個表面獨立地計算匹配值，綜合利用鄰近和全局亮度信息來提高對非Lambertian原料以及光學(xué)變化產(chǎn)生的外觀變化的魯棒性。該方法可以完全解決投影扭曲和局部閉塞問題，最小化形狀和運行評估的預(yù)計誤差。
3.2 相關(guān)性度量
相關(guān)度也被稱為規(guī)范化相關(guān)性、相關(guān)系數(shù)、皮爾森關(guān)聯(lián)、余弦相似度，被廣泛用于描述模式分類和信號處理問題中兩個向量之間的相似性。相關(guān)性度量基于以下思想：如果一個特征與某個類的關(guān)聯(lián)性高到（或可預(yù)言到）使該特征與此類相關(guān)，同時此特征與其他相關(guān)特征的關(guān)聯(lián)性不能達(dá)到任何相關(guān)特征都可以預(yù)言該特征的水平，則認(rèn)為這個特征是對該分類任務(wù)的優(yōu)秀特征。可以將國際上常用的相關(guān)度度量分為傳統(tǒng)的線性相關(guān)性度量和基于信息理論的相關(guān)性度量。Yu和Liu提出的FCBF算法[30]以及Koller和Sahami提出的Markov Blanket過濾方法[31]均是典型的基于相關(guān)性度量對特征進(jìn)行排序的過濾算法。實驗表明此類算法能夠有效地消除無關(guān)特征和冗余特征，并且具有較低的時間復(fù)雜度。
3.2.1 傳統(tǒng)線性相關(guān)性度量
在早期的研究中通常使用距離函數(shù)度量變量的相似性，例如歐氏距離和馬氏距離。對于二分類問題，如果特征x導(dǎo)致兩個類別條件概率的區(qū)別大于特征y，則特征x優(yōu)于y；如果區(qū)別為0，則x和y不可辨別。歐氏距離是一個通常采用的距離定義，它是在m維空間中兩點之間的真實距離。歐氏距離雖然很有用，但也有明顯的缺點。它將樣品的不同屬性（即各指標(biāo)或各變量）之間的差別等同看待，而實際研究中，經(jīng)常遇到對個體的分析和判別，個體的不同屬性對于區(qū)分個體有著不同的重要性。因此，有時需要采用不同的距離函數(shù)。馬氏距離通過允許任意的線性縮放和特征空間旋轉(zhuǎn)將歐氏距離進(jìn)行推的將線性相關(guān)系數(shù)依據(jù)具體應(yīng)用環(huán)境作適當(dāng)校正可產(chǎn)生各種新的評價準(zhǔn)則，有效提高特征選取的準(zhǔn)確率，如最小平方回歸誤差、最大信息壓縮指數(shù)。KNNC算法[13]使用最大信息壓縮指數(shù)作為特征相似性度量，實驗證明KNNC可有效消除冗余特征。該方法首先運用特征相關(guān)性將原始特征集分為許多個相似子集；然后從每個簇中選擇代表性特征，同時消除其他特征。由于KNNC算法并不基于檢索，具有較小的時間復(fù)雜度，但該算法在每次消除冗余特征時不對剩余特征進(jìn)行無關(guān)性分類，在消除無關(guān)特征方面尚有不足。
選擇線性相關(guān)性作為分類中的特征評價準(zhǔn)則有以下優(yōu)點：a）有助于消除與類別相關(guān)度接近0的特征，即消除無關(guān)特征；b）有助于減小選中特征的冗余度，消除冗余特征。線性相關(guān)的缺點在于需要所有特征具有數(shù)值表示才能進(jìn)行計算，并且不能捕獲現(xiàn)實世界中非線性的關(guān)聯(lián)。在簡單相關(guān)系數(shù)的基礎(chǔ)上又發(fā)展出了復(fù)相關(guān)系數(shù)、偏相關(guān)系數(shù)、典型相關(guān)系數(shù)等相關(guān)性度量方法。復(fù)相關(guān)又叫多重相關(guān)系數(shù)，是指因變量與多個自變量之間的相關(guān)關(guān)系，如某種商品的需求量與預(yù)期價格水平、職工收入水平等現(xiàn)象之間呈現(xiàn)多重相關(guān)關(guān)系。偏相關(guān)系數(shù)又被稱為部分相關(guān)系數(shù)，反映校正其他變量后某一變量與另一變量的相關(guān)關(guān)系。偏相關(guān)系數(shù)的假設(shè)檢驗等同于偏回歸系數(shù)的t檢驗；復(fù)相關(guān)系數(shù)的假設(shè)檢驗等同于回歸方程的方差分析。典型相關(guān)系數(shù)是指先對原來各組變量進(jìn)行主成分分析，得到新的線性無關(guān)的綜合指標(biāo)，再用兩組之間綜合指標(biāo)的直線相關(guān)系數(shù)來研究原兩組變量間的相關(guān)關(guān)系。
3.2.2 基于信息理論的相關(guān)性度量
信息論是一門用數(shù)理統(tǒng)計方法研究信息度量、傳遞和變換規(guī)律的科學(xué)。基于信息理論的相關(guān)性度量關(guān)鍵在于評測從特征中獲取的信息，如果從特征X中獲取的信息比特征Y熵用于測量隨機變量的不確定性；度量的是消息中所含的信息量，其中去除了由消息固有結(jié)構(gòu)所決定的部分，如語言結(jié)構(gòu)的冗余性以及語言中字母、詞的使用頻度等統(tǒng)計特性。變量
互信息[32]是另一種常用的信息度量，用于評測隨機變量間的依賴性，它總是具有對稱、非負(fù)性，互信息的值越大說明變量間的依賴性越強。互信息取值為0當(dāng)且僅當(dāng)變量
B中刪除；d）重復(fù)進(jìn)行以上貪心選擇步驟直到選完足夠數(shù)目的特征。實驗證明MIFS能夠有效地選取出相關(guān)特征，但是該算法只考慮了單個特征與目標(biāo)類的相互依賴性而沒有對特征之間的相關(guān)度進(jìn)行評測，因此MIFS算法不能解決冗余特征對神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)的影響。近幾年來諸多研究人員在MIFS的基礎(chǔ)上又提出了各種改進(jìn)算法，如MIFSFS、MIF用互信息對變量間的相關(guān)度進(jìn)行度量，但度量范圍從單個特征與目標(biāo)類的MI計算擴展為特征空間與目標(biāo)類的MI計算。此類算法的優(yōu)點在于能夠同時消除冗余特征及無關(guān)特征，顯著改善訓(xùn)練神經(jīng)網(wǎng)絡(luò)分類器的效率和準(zhǔn)確性，可將其應(yīng)用于為識別高精度數(shù)字圖像中的潛在對象而自動構(gòu)造特征；缺點是時間開銷較大。
特征評價標(biāo)準(zhǔn)本身并不受特征子集選取策略的影響，即上述度量方法可以用于有指導(dǎo)的特征選取，也適用于無指導(dǎo)的特征選取。其區(qū)別在于：有指導(dǎo)的選擇過程度量特征子集在分類中的能力；無指導(dǎo)的選擇過程度量特征子集在聚類中的能力。隨著特征評測研究的發(fā)展，如何借鑒融合各種度量的優(yōu)點成為新的研究趨勢，如Davis等人[36]最新提出的利用信息理論學(xué)習(xí)馬氏距離函數(shù)，用于解決在距離函數(shù)約束下最小化兩個多元高斯量之間的微分相關(guān)熵。
4 結(jié)束語
根據(jù)上述分析，針對高維數(shù)據(jù)的特征降維研究，當(dāng)前已經(jīng)提出了許多有效的特征降維模型，總的來說可以分為過濾模型和包裹模型兩類，其區(qū)別在于是基于特征的內(nèi)在特性還是基于學(xué)習(xí)算法的性能對特征進(jìn)行選取。特征子集的搜索過程和選用的特征評價標(biāo)準(zhǔn)是特征降維的兩個關(guān)鍵問題，根據(jù)具體應(yīng)用環(huán)境制定適當(dāng)?shù)乃阉鞑呗耘c一定特征度量準(zhǔn)則相結(jié)合能夠有效地去除無關(guān)特征、冗余特征，實現(xiàn)高效的特征降維，提高機器學(xué)習(xí)的效率。隨著自然語言處理技術(shù)的發(fā)展，以語義分析為基礎(chǔ)的特征抽取技術(shù)必將得到進(jìn)一步發(fā)展；如何捕捉現(xiàn)實世界中非線性的關(guān)聯(lián)，將特征判別從距離空間轉(zhuǎn)向相關(guān)度度量空間依然是機器學(xué)習(xí)的研究熱點。特征降維的應(yīng)用領(lǐng)域也從傳統(tǒng)的靜態(tài)文本分類、聚類轉(zhuǎn)向?qū)Π虢Y(jié)構(gòu)化網(wǎng)絡(luò)資源的數(shù)據(jù)挖掘，對音頻、視頻等多媒體資源的機器學(xué)習(xí)，以及對生物基因特征的分析識別等。
參考文獻(xiàn)：
［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，F(xiàn)RIEDMAN 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，F(xiàn)AUGERAS 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.I(xiàn)nformationtheoretic metric learning[C]//Proc of the 24th Int Conf on Machine Learning.New York:ACM，2007:209-216.
