第3章大數(shù)據(jù)的特征選擇3.1特征選擇的數(shù)學描述及其優(yōu)勢3.2特征選擇基本框架3.3-特征選擇算法分類3.4特征選擇的穩(wěn)定性

3.1特征選擇的數(shù)學描述及其優(yōu)勢

1.特征選擇的數(shù)學描述

特征選擇是指根據(jù)某種評估標準,選擇特征數(shù)量較少、評估效果較好的特征子集。它的主要任務就是刪除不重要的、不相關(guān)的、干擾性甚至破壞性的特征,不重要的特征是指對系統(tǒng)性能貢獻不大的特征,不相關(guān)的特征是指對系統(tǒng)性能沒有影響的特征,干擾性甚至破壞性的特征是指導破壞系統(tǒng)性能的特征。

2.特征選擇的優(yōu)勢

特征選擇就是從原始數(shù)據(jù)集中選擇與類別具有關(guān)聯(lián)的特征集從而降低數(shù)據(jù)維度的一個過程,如何尋找高維數(shù)據(jù)的“本征維數(shù)”對降低數(shù)據(jù)的維數(shù)及其后續(xù)信息處理起有重要的意義,也對后續(xù)的模式分類發(fā)揮重要的作用。其有如下優(yōu)勢:

(1)降低了特征空間維數(shù),減少了需求空間并且加快了算法的速度;

(2)去除了冗余的,無關(guān)的或“噪聲”數(shù)據(jù);

(3)進行數(shù)據(jù)分析,縮短了學習算法的運行時間;

(4)經(jīng)過選擇的特征更易理解;

(5)增加了分類模型的精確度;

(6)特征集的消減,為下一輪數(shù)據(jù)收集和利用節(jié)省了資源;

(7)分類性能的提高,從而提高了預測的準確性;

(8)數(shù)據(jù)分析,有利于揭示底層數(shù)據(jù)蘊含的信息。

3.2特征選擇基本框架

特征選擇是指在輸入的變量數(shù)據(jù)中運用相應的特征算法構(gòu)造一個特征子集的算法,而這個特征子集是在原變量中提取出來的,這些子集最符合設定的特征選取標準。通過特征選擇可以過濾原始數(shù)據(jù)中權(quán)重較輕的數(shù)據(jù),保留最能反映數(shù)據(jù)特征的數(shù)據(jù),特征選擇會使選擇的數(shù)據(jù)模型更加精確簡捷,提高處理效率。

對于這些語言描述可以建立一個簡單的數(shù)學模型:

給定樣本數(shù)據(jù)集S={F、C、D},其中F(feature)代表特征樣本集合,C(category)代表類別樣本集合,D(data)代表數(shù)據(jù)樣本集合。令特征算法J(X)∈(0,1)為特征評價函數(shù),其中J(X)的大小表示著對應數(shù)據(jù)的信息量大小(即權(quán)重),權(quán)重越大,數(shù)據(jù)就越重要。

在選取最優(yōu)特征子集時函數(shù)一般會有以下幾種類型:一是在特征集合F中選取子集,使J(X)最大;二是給定J(X)的取值范圍J0,選取函數(shù)值大于J0的子集;三是在F中找一個合適的子集使J(X)大并保證特征數(shù)盡量少。這幾種方法分別從特征數(shù)和權(quán)重方面采取不同的衡量選取方式,但是目的都是為了都得到對選擇最有利的數(shù)據(jù)。

特征選擇是指在輸入的變量數(shù)據(jù)中運用相應的特征算法構(gòu)造一個特征子集的算法,這是一個對數(shù)據(jù)特征的優(yōu)化選擇過程。

1997年Dash和Liu在對大量選擇方法進行分析后給出了一個通用的特征選擇技術(shù)框架。結(jié)構(gòu)框架圖如圖3-1所示,其中主要包含四個部分:子集產(chǎn)生、評價部分、停止條件和驗證部分,其中以子集產(chǎn)生和評價部分為核心部分,這兩個環(huán)節(jié)進行了對特征子集的主要篩選工作。圖3-1特征選擇的基本框架

(1)子集產(chǎn)生(SubsetGeneration)。這是一個搜索過程,通過一定的搜索策略產(chǎn)生候選的特征子集。

(2)評價部分(SubsetEvaluation)。該部分通過與選定的最優(yōu)子集比較來評價生成部分選取的特征子集的合理性,并可評價選用的算法針對問題的有效性和對達到目標的幫助。

(3)停止條件(StoppingCriterion)。算法結(jié)束所需要滿足的條件,它與子集的產(chǎn)生過程和評價準則的選用有關(guān)。經(jīng)常采用的停止條件有:搜索完成;某種給定的界限,如指定的特征維數(shù)或循環(huán)次數(shù)等已達到;再增加(或刪除)任何特征都已不能獲得更好的結(jié)果;對于給定的評價準則,已獲得足夠好的特征子集。

(4)驗證部分(ResultValidation)。本部分是經(jīng)過前幾步篩選過程在初始特征中選出的最優(yōu)子集,通過和已有最優(yōu)子集比較可以用來驗證選用算法的適用性,用以確定最優(yōu)算法和特征子集,本部分可通過學習和訓練,提高特征選擇系統(tǒng)選擇特征算法的熟練程度。

對于給定的數(shù)據(jù)集S,每個樣本用一個n維向量描述,算法從一個選定的特征子集fs開始,根據(jù)一定的搜索策略在特征空間中進行搜尋,根據(jù)選定的評價準則J對獲取的每一個特征子集進行評價,并與前面最好的特征子集進行比較。整個搜索過程一直持續(xù)到滿足特定的終止條件,算法的輸出是相對于評價準則J的最優(yōu)特征子集。

3.2.1子集生成

假設特征集中包含n維特征,那么搜索得到子集就有2n種狀態(tài),特征選擇過程就是尋優(yōu)搜索過程,要搜索的空間非常龐大,如果n非常大,再考慮特征評價過程的時間和空間開銷,這種窮盡式搜索通常是實現(xiàn)不了的。子集生成部分是由搜索方向和搜索策略組成。

1.搜索方向

搜索方向表明特征選擇是以何種起點和方向搜索特征,任意一個子集都可以作為搜索的起點,同時也決定著搜索特征子集的方向:

(1)前向搜索,搜索開始時已選特征子集初始化為空,然后在剩余的未選特征集中依次篩選每一個特征,將滿足使評價測度最大的那個特征加入特征子集,如此循環(huán)直到達到停止條件;

(2)后向搜索,與前向搜索相反,搜索開始時令已選特征集為整個全集,依次計算評價測度,然后去除一個使評價測度最大的特征,循環(huán)直到滿足停止條件;

(3)雙向搜索,同時從兩個方向搜索,先從當前的特征子集中刪除一部分特征,然后再選擇合適的若干特征加入當前子集;隨機搜索,隨機產(chǎn)生一個子集作為搜索起點,這樣的搜索算法多次運行可能會產(chǎn)生不同結(jié)果,隨機的方法避免了陷入局部最優(yōu)點。

2.搜索策略

搜索策略可以分為完全搜索、隨機搜索和啟發(fā)式搜索。

(1)完全搜索分為兩種,分別為窮舉搜索(Exhaustive)和非窮舉搜索(Non-Exhaustive)。在這兩種搜索方式中,窮舉搜索因其列舉出了所有的特征組合,有較高的精確度,但由于其時間復雜度高,在特征組合數(shù)量較大的情況下耗時較長,所以并沒有太高的應用價值。

(2)隨機搜索。

其特點是在搜索中加入隨機因素,在特征選擇上將問題化為對搜索組合的優(yōu)化問題,在搜索計算的過程中,將特征選擇與遺傳算法,模擬退火等算法相結(jié)合,基于特征對應的分類性能求解權(quán)重,然后根據(jù)用戶設定或自調(diào)節(jié)的閾值篩選特征。

(3)啟發(fā)式搜索。

該搜索方式的核心是一個評估函數(shù),該函數(shù)通過分析當前的有效信息得到,在該函數(shù)的指導下,搜索可以在眾多節(jié)點中擇優(yōu)選擇,并進行節(jié)點擴展。

在啟發(fā)式搜索的眾多方法中,序列前向選擇(SequentialForwardSelection,SFS)、序列后向選擇方法(SequentialBackwardSelection,SBS),因其選擇結(jié)果的最優(yōu)性而被廣泛應用。

①有結(jié)合兩者思想提出的增l去r選擇算法,但它的搜索速度比SBS快,搜索效果比SFS好;有隨之發(fā)展來的序列浮動選擇,該算法的l與r不是固定的,而是變化的。

②還有決策樹算法,將決策樹生成算法在訓練樣本集上執(zhí)行,為得到特征子集,在搜索前期讓決策樹充分生長,待其生長后,在樹上進行枝剪,則特征子集會在分支處生成。對于決策樹算法優(yōu)劣需要一個評價標準,通常使用信息增益法。

啟發(fā)式的搜索可以設計出非常實用的應用于特征選擇的次優(yōu)搜索方法,這種算法并不是搜索所有可能的特征組合,但是它可以估算出一組可用的、潛在的特征組合。當設計合理評價準則時,這類算法在實際應用中甚至可以匹敵前兩種搜索算法的效果,并且運算的速度更快。是一種可以實現(xiàn),并且效率高性能好的搜索算法,實際運用廣泛。

表3-1與表3-2分別列出了各種搜索策略的常用算法描述和一些基本特性。

3.2.2評價測度

對特征子集的評價測度是特征選擇中關(guān)鍵性問題,評價函數(shù)不同會產(chǎn)生不同的子集,評價測度的好壞直接影響最終的特征子集。常見的評價測度分為距離度量、一致性度量、信息度量、依賴性度量和分類錯誤率度量。

1.距離度量

在機器學習和數(shù)據(jù)挖掘中,我們經(jīng)常需要知道個體間差異的大小,進而評價個體的相似性和類別。最常見的是數(shù)據(jù)分析中的相關(guān)分析,數(shù)據(jù)挖掘中的分類和聚類算法,如K最近鄰(KNN)和K均值(K-Means)等。根據(jù)數(shù)據(jù)特性的不同,可以采用不同的度量方法。一般而言,定義一個距離函數(shù)d(x,y),需要滿足下面幾個準則:

(1)d(x,x)=0//到自己的距離為0

(2)d(x,y)≥0//距離非負

(3)d(x,y)=d(y,x)//對稱性:如果A到B距離是a,那么B到A的距離也應該是a

(4)d(x,k)+d(k,y)≥d(x,y)//三角形法則:(兩邊之和大于第三邊)

距離度量(Distance)用于衡量個體在空間上存在的距離,距離越遠說明個體間的差異越大。

1)歐幾里得距離(EuclideanDistance)

歐氏距離是最常見的距離度量,衡量的是多維空間中各個點之間的絕對距離。公式如下:

這里的p值是一個變量,當p=2的時候就得到了上面的歐氏距離。

3)曼哈頓距離(ManhattanDistance)

曼哈頓距離來源于城市區(qū)塊距離,是將多個維度上的距離進行求和后的結(jié)果,即當上面的明氏距離中p=1時得到的距離度量公式,如下:

4)切比雪夫距離(ChebyshevDistance)

切比雪夫距離起源于國際象棋中國王的走法,我們知道國際象棋國王每次只能往周圍的8格中走一步,那么如果要從棋盤中A格(x1,y1)走到B格(x2,y2)最少需要走幾步?擴展到多維空間,其實切比雪夫距離就是當p趨向于無窮大時的明氏距離:

其實上面的曼哈頓距離、歐氏距離和切比雪夫距離都是明氏距離在特殊條件下的應用。

2.相似度度量

相似度度量(Similarity),即計算個體間的相似程度,與距離度量相反,相似度度量的值越小,說明個體間相似度越小,差異越大。

1)向量空間余弦相似度(CosineSimilarity)余弦相似度用向量空間中兩個向量夾角的余弦值作為衡量兩個個體間差異的大小。相比距離度量,余弦相似度更加注重兩個向量在方向上的差異,而非距離或長度上。公式如下:

2)皮爾森相關(guān)系數(shù)(PearsonCorrelationCoefficient)

皮爾森相關(guān)系數(shù)即相關(guān)分析中的相關(guān)系數(shù)r,分別對X和Y基于自身總體標準化后計算空間向量的余弦夾角。公式如下:

3)Jaccard相似系數(shù)(JaccardCoefficient)

Jaccard系數(shù)主要用于計算符號度量或布爾值度量的個體間的相似度,因為個體的特征屬性都是由符號度量或者布爾值標識,因此無法衡量差異具體值的大小,只能獲得“是否相同”這個結(jié)果,所以Jaccard系數(shù)只關(guān)心個體間共同具有的特征是否一致這個問題。如果比較X與Y基的Jaccard相似系數(shù),只比較xi和yi和中相同的個數(shù),公式如下:

4)調(diào)整余弦相似度(AdjustedCosineSimilarity)

雖然余弦相似度對個體間存在的偏見可以進行一定的修正,但是因為只能分辨?zhèn)€體在維之間的差異,沒法衡量每個維數(shù)值的差異,會導致這樣一個情況:比如用戶對內(nèi)容評分,5分制,X和Y兩個用戶對兩個內(nèi)容的評分分別為(1,2)和(4,5),使用余弦相似度得出的３結(jié)果是0.98,兩者極為相似,但從評分上看X似乎不喜歡這2個內(nèi)容,而Y比較喜歡,余弦相似度對數(shù)值的不敏感導致了結(jié)果的誤差,需要修正這種不合理性,就出現(xiàn)了調(diào)整余弦相似度,即所有維度上的數(shù)值都減去一個均值,比如X和Y的評分均值都是3,那么調(diào)整后為(-2,-1)和(1,2),再用余弦相似度計算,得到-0.8,相似度為負值并且差異不小,但顯然更加符合現(xiàn)實。

5)馬氏距離

馬氏距離是由印度統(tǒng)計學家馬哈拉諾比斯(P.C.Mahalanobis)提出的,表示數(shù)據(jù)的協(xié)方差距離。它是一種有效地計算兩個未知樣本集的相似度的方法。與歐氏距離不同的是它考慮到各種特性之間的聯(lián)系(例如:一條關(guān)于身高的信息會帶來一條關(guān)于體重的信息,因為兩者是有關(guān)聯(lián)的)并且是尺度無關(guān)的(scale-invariant),即獨立于測量尺度。對于一個均值為μ=(μ1,μ2,…,μD)T,協(xié)方差矩陣為Σ的多變量向量X=(x1,x2,…,xD)T和Y=(y1,y2,…,yD

)T,其馬氏距離為

如果協(xié)方差矩陣為單位矩陣,馬氏距離就簡化為歐氏距離;如果協(xié)方差矩陣為對角陣,其也可稱為正規(guī)化的歐氏距離。

式中,σi2是xi的標準差。

6)歐氏距離與余弦相似度

歐氏距離是最常見的距離度量,而余弦相似度則是最常見的相似度度量,很多的距離度量和相似度度量都是基于這兩者的變形和衍生,所以下面重點比較下兩者在衡量個體差異時實現(xiàn)方式和應用環(huán)境上的區(qū)別。

借助三維坐標系來看下歐氏距離和余弦相似度的區(qū)別:

從圖3-2可以看出距離度量衡量的是空間各點間的絕對距離,跟各個點所在的位置坐標(即個體特征維度的數(shù)值)直接相關(guān);而余弦相似度衡量的是空間向量的夾角,更加的是體現(xiàn)在方向上的差異,而不是位置。如果保持A點的位置不變,B點朝原方向遠離坐標軸原點,那么這個時候余弦相似度cosθ是保持不變的,因為夾角不變,而A、B兩點的距離顯然在發(fā)生改變,這就是歐氏距離和余弦相似度的不同之處。圖3-2歐氏距離和余弦相似度的區(qū)別

根據(jù)歐氏距離和余弦相似度各自的計算方式和衡量特征,分別適用于不同的數(shù)據(jù)分析模型:歐氏距離能夠體現(xiàn)個體數(shù)值特征的絕對差異,所以更多的用于需要從維度的數(shù)值大小中體現(xiàn)差異的分析,如使用用戶行為指標分析用戶價值的相似度或差異;而余弦相似度更多的是從方向上區(qū)分差異,而對絕對的數(shù)值不敏感,更多的用于使用用戶對內(nèi)容評分來區(qū)分用戶興趣的相似度和差異,同時修正了用戶間可能存在的度量標準不統(tǒng)一的問題(因為余弦相似度對絕對數(shù)值不敏感)

3.條件概率度量

上面討論的是樣本在特征空間的分布距離作為特征提取的依據(jù)。該種原理直觀,計算簡便。但是這種原理沒有考慮概率分布,因此當不同類樣本中有部分在特征空間中交疊分布時,簡單地按距離劃分,無法表明與錯誤概率之間的聯(lián)系?；诟怕史植嫉目煞中耘袚?jù)則依據(jù)如下觀察到的現(xiàn)象。

如果我們不考慮各類的先驗概率,或假設兩類樣本的先驗概率相等,那么從兩類條件概率分布可以看出,如果兩類條件概率分布互不交疊,即對p(X|w2)≠0處都有p(X|w1)=0,如圖3-3(a)所示,則這兩類就完全可分;另一種極端情況是對所有X都有p(X|w1)=p(X|w2),如圖3-3(b)所示,則兩類就完全不可分。因此人們設計出與概率分布交疊程度有關(guān)的距離度量方法,這些距離Jp有以下幾個共同點:

(1)Jp是非負,即Jp≥0;

(2)當兩類完全不交疊時Jp達到其最大值;

(3)當兩類分布密度相同時,Jp=0。

這種函數(shù)的一般式可表示為圖3-3-條件概率分布

下面列出一些常用的概率距離度量。

1)Bhattacharyya距離和Chernoff界限

Bhattacharyya距離的定義用下式表示:

顯然,當p(X|w1)=p(X|w2)對所有X值成立時JB=0,而當兩者完全不交疊時JB

為無窮大。

Chernoff界限的定義與其相似,為

式中,S為[0,1]區(qū)間的一個參數(shù),顯然式(3-13)在S=0.5時就變?yōu)槭?3-12),因此Bhattacharyya是Chernoff的一個特例。

2)散度

另一種常用的基于概率距離度量的判據(jù)是利用似然比或?qū)?shù)似然比。對兩類問題,其對數(shù)似然比為

如果對某個X,p(X|wi)=p(X|wj),則Iij=0,反之若兩者差異越大,則Iij的絕絕對值也大。

以上只是對某一X值而言,為了對整個特征空間概率分布的差異程度作出評價,將對wi類及wj對的可分性信息分別定義為

與

而總的平均可分信息則可表示成

被稱為散度。

3)正態(tài)分布時基于概率分布距離度量

顯然在一般情況下由于概率分布本身的復雜形式,以上這些基于概率分布的距離相當復雜。這些判據(jù)在概率分布具有某種參數(shù)形式,尤其是正態(tài)分布時可以得到進一步簡化。下面討論兩類別正態(tài)分布時散度判據(jù)的表達式。

設兩類別分別表示為wi~N(μi,Σi),wj~N(μj,Σj)則,

設兩類分別表示為

在正態(tài)分布時,Bhattacharyya距離JB可表示成:

它與散度JD的表達式只差一個常系數(shù)。

4)x2(CHI)統(tǒng)計量CHI統(tǒng)計特征項w和類別c之間的相關(guān)程度,并假設特征項w和類別c之間符合具有一階自由度的x2分布。特征項w對于某類的x2統(tǒng)計值越高,它與該類之間的相關(guān)性越大,攜帶的類別信息也越多。反之,x2統(tǒng)計量也能反映特征項w和類別c之間的獨立程度。當x2值為0時,特征項w和類別c完全獨立。

令N表示樣本總數(shù),c為某一特定類別,w表示特征項,A表示屬于類別c且包含特征w的頻數(shù),B為不屬于類別c且包含特征w的頻數(shù),C表示屬于類別c且但不包含特征w的頻數(shù),D表示既不屬于類別c且也不包含特征w的頻數(shù)。如表3-3所示。

特征項w對于類別c的CHI值由如下公式計算:

且有:N=A+B+C+D

對于多類問題,分別計算特征項w對于每個類別的CHI值,再用式(3-28)或式(3-29)計算特征項w所對的CHI值。CHI值也有最大值和平均值兩種方法進行檢驗。

最大值法:

平均值法:

χ2統(tǒng)計量和互信息的區(qū)別在于,它是一個歸一化的統(tǒng)計量。它對于低頻特征項的區(qū)分效果仍然不是很好。

5)期望交叉熵

期望交叉熵(ExpectedCrossEntropy,ECE)與信息增益相似,也是一種基于概率的方法。所不同的是信息增益要求計算所有特征項的值,而期望交叉熵則只計算出現(xiàn)特征項的值。

如果令m表示類別數(shù),P(ci/w)表示出現(xiàn)在特征項w時,屬于ci類別的概率。P(ci

)表示ci類別的概率,則期望交叉熵可由式(3-30)計算:

如果特征項w和類別ci

強相關(guān),也就是P(ci/w)大,且相應的類別出現(xiàn)概率又小的話,則說明該特征項對分類影響大,相應的函數(shù)值越大,就可能被選中作為特征項。

4.后驗概率分布度量

如果對某些特征,各類后驗概率都相等,即

式中,c為類別數(shù),則樣本的類屬就無法確定,或者只能任意指定樣本所屬類別。此時

這也就是錯誤率最大的情況。

如果考慮另一極端,假設能有一組特征使得

且

那么此時的X肯定可劃分為wj,而錯誤率為零。由此可看出,后驗概率越集中,錯誤概率就越小,反之后驗概率分布越平緩,即接近均勻分布,則分類錯誤概率就越大。

為了衡量后驗概率分布的集中程度,可以借助于信息論中熵的概念,制訂定量指標。例如Shannon熵為

另一常用的平方熵

這兩者都有熵函數(shù)的以下共性。

5.一致性度量

一致性度量就是計算一個特征子集對應的樣本中“不一致”的樣本所占的比例,不一致的樣本就是說兩個樣本上所有特征取值都相等,但是它們卻屬于不同的類別,則稱這兩個樣本為不一致樣本。

6.信息度量

信息度量是基于信息論中信息熵和互信息為理論依據(jù)的。信息度量標準的優(yōu)勢是它能很好地度量特征與類別之間的非線性相關(guān)程度。并且,它不依賴于特征的具體取值,是一種無參數(shù)的評價標準,它只取決于特征值的分布,所以能有效地避免噪聲的干擾。通過信息熵計算特征與類別的不確定性程度,或通過互信息計算特征與類別的非線性相關(guān)度,選出有重要意義的特征。

1)信息熵

熵(Entropy)是一個來自于統(tǒng)計熱力學的概念,它表示一個系統(tǒng)混亂的程度,如果系統(tǒng)越混亂熵值就越高;反之,若是系統(tǒng)越有序,那么它所對應的熵值就越低。熵是描述隨機變量的不確定度的,通常也被稱為信息熵或Shannon。假設X為一個隨機變量,它可能取值為x的概率為p(x),那么它的信息熵H(x)定義為

由式(3-36)可知,信息熵H(x)和變量X的概率分布密切相關(guān),而與其具體值無關(guān)。這在某種程度上說明信息熵有效地避免噪聲數(shù)據(jù)的干擾。研究發(fā)現(xiàn),若隨機變量X的概率分布越大,即不確定性的程度越高,那么信息熵值就越大,表明它所需要的信息量也大。用信息熵表示變量的隨機性,也表示隨機變量X的不確定度;H(x)值越小,表示不確定性越小,則該變量分布越不均勻,數(shù)據(jù)集越純。

2)條件熵和聯(lián)合熵

除此還引入了條件熵和聯(lián)合熵的概念,聯(lián)合熵主要用來描述多個變量之間共同擁有的信息量。

式中,p(x,y)為隨機變量X和Y的聯(lián)合概率分布;(py|x)為在給定變量X的條件下Y的概率分布。

條件熵H(Y|X)表示在隨機變量X已知的情況下隨機變量Y的不確定性度,聯(lián)合熵H(X,Y)表示隨機變量X和隨機變量Y共同擁有的信息量,且通過變換可知

3)互信息(mutualinformation)

在信息論中,互信息描述兩個變量的相互依賴程度,假設隨機變量X和變量Y存在某種聯(lián)系,則用互信息給出兩者的共有的信息量,定義為

I(X;Y)越大,說明X和Y的相關(guān)性越大,說明變量X和變量Y相關(guān)性越大,反之,兩者依賴程度越低。

可以推導得到以下幾種互信息的形式:

也就是說在一個隨機變量已知的情況下,另一個變量的不確定性的減少程度。且當X、Y相互獨立時,互信息值為零。

4)信息增益

信息增益(InformationGain,IG)是信息論中的一個重要概念,是基于信息熵的測評方法,普遍應用于機器學習中。它表示了某一個特征的存在與否對類別預測的影響,定義為特征在數(shù)據(jù)集中出現(xiàn)前后的信息量大小。信息增益的特征選擇算法的指導思想是:對每一個特征的信息增益值進行計算,并按照信息增益值的大小排序,刪除小于預定義閾值的特征,保留信息增益值大于預定閾值的特征,那么對于信息增益值的特征而言,它們對分類的重要性是與其對分類的貢獻成正比的。

7.依賴性度量

依賴性度量實際上是計算特征與類別之間的統(tǒng)計相關(guān)性,在面對龐大的特征集時,如何快速定位那些和類別相關(guān)的特征而忽略其他無關(guān)或影響不大的特征。定義特征與目標函數(shù)C相關(guān):實例空間中存在樣本A和樣本B,C(A)≠C(B),其中樣本A和B其余特征均相同僅屬性xi不同,則稱特征xi與類別C相關(guān)。在實際應用中,很多情況下不存在兩個樣本間只有一個特征屬性不一致,因而無法使用這種嚴格的定義,所以有了強相關(guān)和弱相關(guān)的定義。當去掉強相關(guān)特征后,特征xi變?yōu)閺娤嚓P(guān)特征,則稱xi為弱相關(guān)特征。特征選擇的目的就是從原始特征集中選擇出強相關(guān)特征和部分弱相關(guān)特征。

8.分類錯誤率度量

分類錯誤率度量和上述四種度量是截然不同的,以上幾種算法都是考察特征與類別、特征與特征之間的度量函數(shù),是典型的Filter式特征選擇模型,而分類錯誤率度量是一種Wrapper型特征選擇模型,直接用分類錯誤率作為特征子集評價的標準。顯然這種方法選擇的特征子集有很好的分類性能,受到很多研究者的推崇,缺點就是計算量頗大,通用性差。表3-4中簡單比較了上述5種評價測度的優(yōu)缺點。

3.2.3-停止條件

特征子集的搜索是一個循環(huán)的過程,所以必須設定一個停止條件,避免搜索過程無盡的進行下去。一般的停止條件設置如下:

(1)已選特征子集的數(shù)目達到預先的設定值;

(2)通過當前的已選特征集,達到了要求的分類率,或者提高了分類率;

(3)特征的增加或減少,不再對評價函數(shù)值有影響;

(4)評價函數(shù)的值已經(jīng)達到預先設定的閾值,或者是達到拐點臨界值;

(5)當前的已選特征子集就是評價函數(shù)的最優(yōu)解。

3.2.4結(jié)果驗證

子集有效性驗證是特征選擇的最后一個步驟,在實際應用中必不可少。有效性驗證通過常用經(jīng)過特征選擇處理后的數(shù)據(jù)集進行訓練和預測,將訓練和預測的結(jié)果與在原始數(shù)據(jù)集上的結(jié)果進行比較,比較的內(nèi)容包括預測性的準確性、模型的復雜度等。

3.3-特征選擇算法分類

3.3.1按樣本是否標記分類根據(jù)訓練集中樣本是否標記或者部分標記,該分類方法可以基于三種學習模式:有監(jiān)督學習(supervisedlearning)模式、半監(jiān)督學習(semi-supervisedlearning)模式和無監(jiān)督學習(unsupervisedlearning)模式。

有監(jiān)督模式特征選擇算法是通過計算特征與類別之間的關(guān)系,選擇最具類別區(qū)分能力的特征子集,大多數(shù)衡量準則中都包含類別變量。由于充分利用了類別信息,它能獲得很高的分類性能,缺點是通用性不高,由于該特征選擇算法要求必須預先知道訓練樣本的類標簽,故其在實際應用中存在一定的局限。

無監(jiān)督模式特征選擇算法的目的是通過利用特征間內(nèi)在關(guān)系或結(jié)構(gòu)特征,運用數(shù)據(jù)的方差或分離性對各個特征的重要性進行判斷,在無需經(jīng)驗指導的條件下篩選出有意義的數(shù)據(jù)類簇。

一般,無監(jiān)督特征選擇性能不如有監(jiān)督特征選擇,而且算法的復雜度也高于有監(jiān)督特征選擇,所以結(jié)合了兩者的優(yōu)點,產(chǎn)生了半監(jiān)督特征選擇。半監(jiān)督特征選擇是利用少數(shù)已知類別的樣本數(shù)據(jù)作為指導信息,來提高未知類別樣本的特征選擇性能。

3.3.2按與學習算法的結(jié)合方式分類

1.Filter特征選擇

Filter模型通過某個適應函數(shù)(FitnessFuction)的值來估計某個特征子集的有效性,與具體的分類器無關(guān)?；贔ilter過濾式的特征選擇算法使用某種度量去分類特征,不依賴于分類器的種類,主要基于數(shù)據(jù)本身的特征獨立作為分類學習算法的預處理步驟,圖3-4是Filter特征選擇流程圖。圖3-4Filter特征選擇流程圖

通過訓練樣本所具有的特征評價標準,低等級的特征被淘汰,數(shù)據(jù)中固有特征被考慮去評估特征子集。由于Filter過濾式的特征選擇沒有用到學習算法,而且在整個過程中不需要建模。Filter方法計算簡潔且快速,可以評價特征子集,并且獨立于分類算法,因此計算資源要求少,適用于大規(guī)模的高維數(shù)據(jù)集而且方法簡單。缺點就是該類型的方法大多數(shù)是基于變量的排序算法,忽略了特征與特征之間的相互作用,選擇的特征子集也許不能很好地匹配學習算法,所以性能不太高。

2.Wrapper特征選擇

Wrapper模型用某個特定分類器的性能作為特征子集選擇的準則,這種直接優(yōu)化分類器的策略可改進分類器的泛化性,但計算代價相對較高,且不具備通用性?；赪rpper包裹式學習算法,與Filter過濾式的特征選擇算法相反,它使用了學習算法去預測特征子集,圖3-5是Wrapper特征選擇流程圖。圖3-5Wrapper特征選擇流程圖

3.Embedded特征選擇

Embedded模型同時進行特征選擇和學習器設計?；贓mbedded嵌入式特征選擇方法結(jié)合了學習算法和特征選擇機制去評價學習過程中被考慮的特征。特征選擇算法嵌入到學習和分類算法,也就是學習訓練和特征選擇同時進行,互相結(jié)合,如圖3-6所示。構(gòu)造分類模型的過程就是選擇特征的過程,重復循環(huán)迭代,當分類模型構(gòu)造結(jié)束時,此時分類模型用到的特征子集就是最終特征選擇的結(jié)果。圖3-6Embedded特征選擇流程圖

4.Hybrid特征選擇

Hybrid特征選擇方法使用結(jié)合學習算法的獨立措施去評價子集有效性。Filter模型執(zhí)行效率高,但是分類性能較差,而Wrapper模型能獲得很好的分類性能,但是計算復雜、耗時且占用資源。所以考慮集合兩種特征選擇模型,兩者互補克服各自的限制,如圖3-7所示。圖3-7Hybrid特征選擇流程圖

3.3.3-Filter方法

1.特征選擇中的相關(guān)性

特征選擇的研究離不開對自變量X和因變量y之間相關(guān)關(guān)系以及自變量X自身內(nèi)部變量之間關(guān)系的定義,前者表明了一種正向的相關(guān)關(guān)系,即相關(guān)度越高,包含的潛在信息越多;后者則是冗余程度的反映,自變量內(nèi)部相關(guān)程度越高,說明二者的替代性越強,可以進行取舍,實現(xiàn)特征選擇的目的。

在自變量X和因變量y之間相關(guān)關(guān)系的定義方面,許多文獻將其分為強相關(guān)關(guān)系(strongrelevance)、弱相關(guān)關(guān)系(weakrelevance)和非相關(guān)關(guān)系(irrelevance),他們各自的表達形式有差異,并且都可以找出反例證明各自的相關(guān)性定義在某種情況下失效?，F(xiàn)在針對特征相關(guān)性研究領域常采用的定義是由Kohavi中給出的。

令F表示全體特征集合,Fi為其中第i個特征,Si=F-{Fi},C表示全體因變量y的集合,因此自變量X和因變量y之間的相關(guān)關(guān)系可以表示如下:

給定一個特征Fi,令特征子集Mi?F(Fi?Mi),則當且僅當

時,則稱Mi為特征Fi的“馬爾科夫毯”。Mi中包含了能夠表征因變量集合C的足夠特征,Koller和Sahami在統(tǒng)計理論上提出采用后向消除算法過程最優(yōu)特征子集,消除過程中以特征是否存在馬爾科夫毯為標準,故又稱作馬爾科夫毯特征過濾。

令G是一個給定的特征集合,當且僅當特征Fi具有弱相關(guān)性并且在G中存在關(guān)于Fi的馬爾科夫毯Mi時,稱Fi是集合G中的一個冗余特征,可以被剔除掉。

上述三種強相關(guān)、弱相關(guān)和不相關(guān)特征是自變量與因變量關(guān)系的反映;冗余特征是自變量內(nèi)部之間關(guān)系的反映,相互冗余的兩個變量xi和xj很可能都是強相關(guān)特征變量,也可能都是弱相關(guān)特征變量,還可能都是不相關(guān)特征變量,有些特征選擇算法可以找到強相關(guān)特征,但無法剔除其中的冗余特征。相

2.Filter方法

1)Filter方法基本原理Filter方法通過某種準則考察每個變量的顯著性,過濾掉不顯著的變量,剩余的構(gòu)成變量子集?？紤]包含有m個樣本的數(shù)據(jù)集{Xk

yk}(k=1,2,…,m),其中Xk包括N個變量Xk,i(i=1,2,…,N),對應的輸出為yk。Filter方法就是考察每個輸入變量Xk,i與輸出變量yk相關(guān)程度,據(jù)此選擇或過濾掉某些變量。因此,只要該變量與yk的相關(guān)度強,就有可能被選中。即使真正的變量集合只有一小部分,而其余的無關(guān)變量都與yk具有一定的相關(guān)度時,則大多數(shù)變量都可能會被選中。

2)Filter方法分類

Filter模型依據(jù)數(shù)據(jù)內(nèi)在的結(jié)構(gòu)特征如樣本類間距離或相關(guān)性選擇最相關(guān)的特征。

(1)基于距離準則的典型算法是RELIEF,作者認為重要的特征將增大樣本與非同類近鄰距離和樣本與同類最近鄰距離的差異,因此在加權(quán)特征子空間中樣本集會呈現(xiàn)出較好的類間分離性質(zhì)。

(2)基于相關(guān)性度量的特征選擇方法評估特征與類別之間的相關(guān)度,以及特征彼此之間的相關(guān)度。目前使用最廣泛的相關(guān)度準則是Pearson統(tǒng)計量(correlation)、熵(entropy)、對稱不確定準則(SymmetryUncertainty)與互信息(MutualInformation)準則,Pearson統(tǒng)計量用來衡量特征之間的線性依賴關(guān)系,熵、對稱不確定準則與互信息準則都來自于信息理論,既可以衡量線性相關(guān),又能夠衡量非線性相關(guān)關(guān)系。

(3)相關(guān)度準則也可用于無監(jiān)督特征選擇,由于這種情形下樣本不含標記,難以計算特征與類別的相關(guān)度,因此無監(jiān)督特征選擇研究算法重點放在如何消除冗余特征。例

3.3.4Wrapper方法

1.Wrapper方法的概念

有指導學習中,將特征子集的選擇算法看作是對有指導學習過程的“封裝”,有指導學習作為每一步特征子集選擇結(jié)果的評估,最終得到的特征子集可以實現(xiàn)分類準確率的最大化。有指導學習過程既作為一個對檢驗樣本的學習過程,又在特征選擇中作為特征子集好壞的評判標準(見圖3-8)。圖3-8Wrapper方法特征選擇流程圖

2.Filter和Wrapper方法的比較

理解Filter和Wrapper方法的關(guān)鍵點在于首先明確特征選擇的輸出將作為新的特征集(設計矩陣),成為另一個機器學習算法的輸入,通過該算法完成機器學習過程,達成用戶預期的數(shù)據(jù)分析目的。為區(qū)別于特征選擇算法中可能用到的機器學習算法概念,我們稱之為目標學習器。其次,在特征子集的評估過程中,又必須用到一個專門的中間算法來產(chǎn)生評估值,這個中間算法可能是一個簡單的單映射函數(shù)(如費舍爾判據(jù)或皮爾森相關(guān)系數(shù)等),也可能是與目標學習器相同的機器學習算法,也可能是與之不同的其他學習算法。Filter和Wrapper方法的區(qū)別就在于對中間算法的選取。

Wrapper方法的主要缺點是:

①特征選擇過程的計算效率低于Filter方法,因為每一步選擇出的特征子集都需要通過運行學習算法進行交叉驗證才能確定其優(yōu)良性;

②所選擇的特征子集是有偏的,選擇不同的學習器在同一數(shù)據(jù)集上進行訓練,所得到的最優(yōu)特征子集很可能是不同的,這種有偏性一方面會導致過擬合(over-fitting)的發(fā)生,另一方面,特征選擇的不穩(wěn)定性會給研究者解釋試驗數(shù)據(jù)造成困擾。

3.3.5Embeded方法

Embeded方法同時解決了特征選擇與分類、回歸或聚類問題,即將特征選擇視為學習算法的子系統(tǒng)。這類算法計算復雜度介于Wrapper方法與Filter方法之間,選擇出的特征也比Filter模型更準確,但需要與新設計的算法相結(jié)合。

Embeded方法與上述兩種方法的區(qū)別在于,它不需要將訓練樣本分為訓練集(TrainingSet)和驗證集(ValidationSet),也就是說,在Embeded方法中不需要對中間結(jié)果進行驗證,特征選擇與訓練過程同步進行。

3.3.6Hybrid方法

Hybrid方法是通過在Filter方法框架下引入目標學習器作為每一輪迭代的最終驗證標準來構(gòu)造的,它兼具Filter方法的快捷特性和Wrapper方法的擬合精度優(yōu)勢,同時避免了Filter方法需要人為設定特征選擇閾值和Wrapper方法低效且易于過擬合的缺點。

3.4特征選擇的穩(wěn)定性

3.4.1特征選擇方法的穩(wěn)定性特征選擇方法的穩(wěn)定性是指特征選擇結(jié)果對訓練樣本變化的不敏感性。也就是說,如果一個特征選擇算法不具有穩(wěn)定性,則當加入或者減少一些樣本后它的結(jié)果是不可重復的,甚至訓練集沒有發(fā)生變動它的結(jié)果也不同。

這里,訓練樣本的變化可以分為不同的層面:樣本層面(去掉或者添加樣本)、特征層面(增加噪聲)或者將兩者相結(jié)合。不穩(wěn)定性在高維小樣本數(shù)據(jù)集上表現(xiàn)得尤為明顯,比如文本挖掘、計算化學、生物信息學等領域。實際應用中,被選出的這些特征隨之將被分析,需要大量的時間和精力,若選出的特征子集不具有重現(xiàn)性,將會使研究者對研究工作喪失熱情和信心。不過僅僅考慮穩(wěn)定性是不夠的,穩(wěn)定性和分類性能一起考慮才有意義。

通常造成特征選擇不穩(wěn)定的原因主要有以下兩個方面:

(1)算法設計本身就沒有考慮到穩(wěn)定性問題。經(jīng)典的特征選擇方法旨在選擇一個最小的特征子集,該子集能構(gòu)造出具有最佳分類精度的分類器,但在算法設計中往往忽略了它的穩(wěn)定性,所以我們應該明確:特征選擇的穩(wěn)定性和高分類精度同樣重要。

(2)高維小樣本問題。在基因表達數(shù)據(jù)和蛋白質(zhì)數(shù)據(jù)的分析中,有幾百個樣本卻有幾千個特征,這是典型的高維小樣本數(shù)據(jù)集。實驗表明,高維小樣本問題是造成特征選擇方法不穩(wěn)定的重要原因之一。

3.4.2穩(wěn)定的特征選擇方法

目前,針對高維數(shù)據(jù)特征選擇的穩(wěn)定性問題,研究者已提出了多種解決方法,主要有集成的特征選擇方法、先驗特征相關(guān)性的方法、組的特征選擇方法和樣本注入的方法,如圖3-9所示。圖3-9穩(wěn)定的特征選擇方法

1.集成的特征選擇方法

該方法是解決特征選擇穩(wěn)定性問題最常用的方法,這種思想的提出和分類器集成的思想類似。

(1)不同的特征選擇算法得到不同的特征子集。

(2)一個建立在弱假設上的模型通常比一個建立