《模式識別原理與應用》課件第5章

第5章特征提取和選擇5.1

基本概念5.2類的可分性判據(jù)5.3基于可分性判據(jù)的特征提取5.4

主分量分析(PCA)5.5獨立分量分析(ICA)5.6基于核函數(shù)的方法5.7特征選擇方法習題5.1基本概念5.1.1特征的特點

模式識別的主要功能在于利用計算機實現(xiàn)人的類識別能力,它是一個與領域?qū)ｉT知識有關的問題。在模式識別過程中,特征的確定比較復雜。研究領域不同,選擇的特征也不同,但不論采用什么樣的特征,都應該滿足以下條件:

(1)特征是可獲取的。因為模式識別系統(tǒng)的主要處理設備是計算機,所以作為觀察對象的數(shù)字化表達,觀察對象應該是可以通過數(shù)據(jù)采集設備輸入到計算機的。目前,市場上有各種傳感設備和數(shù)字化設備,如采集圖像信息的圖像卡和采集語音信息的聲卡等。作為特征,既可以是數(shù)字化表達的結(jié)果,也可以是在數(shù)字化表達基礎上形成的參數(shù)性質(zhì)的值,如圖像分割后的子目標特性表達。

(2)類內(nèi)穩(wěn)定。選擇的特征對同一類應具有穩(wěn)定性。由于模式類是由具有相似特性的若干個模式構(gòu)成的,因此它們同屬一類模式,其首要前提是特性相似,反映在取值上,就應該有較好的穩(wěn)定性。

(3)類間差異。選擇的特征對不同的類應該有差異。若不同類的模式的特征值差異很小,則說明所選擇的特征對于不同的類沒有什么差異,作為分類的依據(jù)時,容易使不同的類產(chǎn)生混淆,使誤識率增大。一般來講,特征的類間差異應該大于類內(nèi)差異。5.1.2特征的類別

特征是用于描述模式性質(zhì)的一種量,從形式上看可以分為三類:

1.物理特征物理特征是比較直接、人們?nèi)菀赘兄奶卣?一般在設計模式識別系統(tǒng)時容易被選用。如為了描述指定班級中的某個學生,可以用以下物理特征:性別、身高、胖瘦、膚色等外在特征。物理特征雖然容易感知,卻未必能非常有效地表征分類對象。

2.結(jié)構(gòu)特征結(jié)構(gòu)特征的表達能力一般要高于物理特征,如漢字識別的成功實現(xiàn)離不開結(jié)構(gòu)特征的選擇。結(jié)構(gòu)特征的表達是先將觀察對象分割成若干個基本構(gòu)成要素,再確定基本要素間的相互連接關系。通過要素和相互連接關系表達對象,可以較好地表達復雜的圖像圖形信息,在實際中已經(jīng)有較多的成功應用,如指紋的識別就是基于結(jié)構(gòu)信息完成的。結(jié)構(gòu)信息對對象的尺寸往往不太敏感,如漢字識別時,識別系統(tǒng)對漢字大小不敏感,只對筆劃結(jié)構(gòu)信息敏感。結(jié)構(gòu)特征比物理特征要抽象一些,但仍屬比較容易感知的特征,如人的指紋特征、人臉的五官結(jié)構(gòu)信息等,是認定人的身份的重要參數(shù)。

3.數(shù)字特征一般來說,數(shù)字特征是為了表征觀察對象而設立的特征,如給每個學生設立一個學號,作為標志每個學生的特征。由于學號是人為設定的,可以保證唯一性,但這種特征是抽象的,不容易被人感知。數(shù)字特征有時和觀察對象的固有特性沒有任何聯(lián)系,有時則是物理或結(jié)構(gòu)特征的計算結(jié)果。5.1.3特征的形成

在設計一個具體的模式識別系統(tǒng)時,往往是先接觸一些訓練樣本,由領域?qū)＜液拖到y(tǒng)工程師聯(lián)合研究模式類所包含的特征信息,并給出相應的表述方法。這一階段的主要目標是獲取盡可能多的表述特征。在這些特征中,有些可能滿足類內(nèi)穩(wěn)定、類間離散的要求,有的則可能不滿足,不能作為分類的依據(jù)。根據(jù)樣例分析得到一組表述觀察對象的特征值,而不論特征是否實用,稱這一步為特征形成,得到的特征稱為原始特征。在這些原始特征中,有的特征對分類有效,有的則不起什么作用。若在得到一組原始特征后,不加篩選,全部用于分類函數(shù)確定,則有可能存在無效特征,這既增加了分類決策的復雜度,又不能明顯改善分類器的性能。為此,需要對原始特征集進行處理,去除對分類作用不大的特征,從而可以在保證性能的條件下,通過降低特征空間的維數(shù)來減少分類方法的復雜度。實現(xiàn)上述目的的方法有兩種:特征提取和特征選擇。特征提取和特征選擇都不考慮針對具體應用需求的原始特征形成過程,而是假設原始特征形成工作已經(jīng)完成。然而在實際工作中,原始特征的獲得并不容易,因為人具有非常直觀的識別能力,有時很難明確描述用于分類的特性依據(jù)。如人臉的判定,人識別臉部特征非常容易,若用計算機來識別人臉,則需要得到多達上千個特征,難度很大。可以說,特征形成是模式識別過程中的重點和難點之一。5.1.4特征提取和選擇的作用特征選擇是指從一組特征中挑選出對分類最有利的特征,達到降低特征空間維數(shù)的目的。特征提取是指通過映射(或變換)的方法獲取最有效的特征,實現(xiàn)特征空間的維數(shù)從高維到低維的變換。經(jīng)過映射后的特征稱為二次特征,它們是原始特征的某種組合,最常用的是線性組合。從定義可以看出,實現(xiàn)特征選擇的前提是確定特征是否有效的標準,在這種標準下,尋找最有效的特征子集。用于特征選擇的特征既可以是原始特征,也可以是經(jīng)數(shù)學變換后得到的二次特征。需要注意,特征提取一定要進行數(shù)學變換,但數(shù)學變換未必就是特征提取。特征提取和特征選擇的主要目的都是,在不降低或很少降低分類結(jié)果性能的情況下,降低特征空間的維數(shù),其主要作用在于:

(1)簡化計算。特征空間的維數(shù)越高,需占用的計算機資源越多,設計和計算也就越復雜。

(2)簡化特征空間結(jié)構(gòu)。由于特征提取和選擇是去除類間差別小的特征,保留類間差別大的特征,因此,在特征空間中,每類所占據(jù)的子空間結(jié)構(gòu)可分離性更強,從而也簡化了類間分界面形狀的復雜度。5.2類的可分性判據(jù)在特征提取與選擇的過程中,高維特征變?yōu)榈途S特征的方法很多,究竟哪種方法最有效,需要通過某種標準來衡量,在數(shù)學上就是要構(gòu)造某種準則(或判據(jù))。這些準則應能很好地反映各類間的可分性以及各特征在分類識別中的重要性或貢獻,因此人們希望可分性判據(jù)滿足以下要求:

(1)與錯誤概率(或是錯誤概率的上、下界)有單調(diào)關系,使判據(jù)的極大值對應錯誤概率的最小值或較小值。

(2)非負性,即(5-1)其中,Jij表示第i,j兩類間的可分性判據(jù)。

(3)對稱性,即

Jij=Jji(5-2)該特性表明有效性判據(jù)對類別號沒有方向性,而只強調(diào)對區(qū)分兩類的貢獻。

(4)當特征獨立時,判據(jù)應具有可加性,即(5-3)

(5)單調(diào)性。對于特征向量而言,加入新的特征分量不會減少判據(jù)值,即(5-4)5.2.1基于距離的可分性判據(jù)

模式識別的結(jié)果實際上是將特征空間劃分為不同類的決策區(qū)域。為了有利于分類,我們總是希望不同類之間的距離大一些,而同類的樣本較集中,這樣類別的可分性才越好。因此,利用類間距離構(gòu)造類別的可分性判據(jù)是可行的。

1.兩類之間的距離設兩類為ωi、ωj,分別有Ni、Nj個樣本,即(5-5)(5-6)兩類間的距離可由下式給出:(5-7)其中,D(xir,xjs)為向量xir、xjs間的距離。由點間距離的對稱性可知,類間距離也具有對稱性。常用的點間距離有以下幾種:

(1)歐幾里德(Euclidean)距離:(5-8)其中,d為向量的維數(shù)。

(2)加權(quán)歐幾里德距離:(5-9)

(3)漢明(Hamming)距離:(5-10)(4)馬氏(Mahalanobis)距離:(5-11)其中,M為一正定陣,wij為矩陣M－1的元素。

(5)明可夫斯基(Minkowsky)距離:(5-12)其中:當q=1時,D(x,y)為漢氏距離;當q=2時,D(x,y)為歐氏距離。

(6)切比雪夫(Chebyshev)距離:(5-13)

2.各類樣本之間的平均距離設N個樣本分別屬于m類,ωi={xik,k=1,2,…,Ni},i=1,2,…,m,各類之間的平均距離為(5-14)其中,是先驗概率P(ωi)的估計,即N為樣本總數(shù),即若點間距離取歐氏距離的平方,以表示第i類的向量平均值,以表示的統(tǒng)計平均值,即(5-15)(5-16)(5-17)則式(5-14)可化為(5-18)且有關系式(5-19)令(5-20)(5-21)則(5-22)式(5-20)、式(5-21)和式(5-22)中的分別是利用有限樣本集得到的類均值μi、總體均值μ、類內(nèi)離散度矩陣Sw和類間離散度矩陣Sb的估計值,μi、μ,Sw、Sb的定義式如下:(5-23)(5-24)(5-25)(5-26)為了使所使用的特征能夠有效地進行分類,我們希望類間離散度盡量大,同時類內(nèi)離散度盡量小,從直觀上看可以構(gòu)造下面各種判據(jù):(5-27)(5-28)(5-29)(5-30)(5-31)為了有效地分類,它們的值越大越好?；诰嚯x的可分性判據(jù)雖然簡單直觀,但只是對于類間無重疊的情況效果較好,若類間存在重疊,則效果會受到影響?；诟怕实目煞中耘袚?jù)能夠較好地解決類間有重疊的問題。5.2.2基于概率密度函數(shù)的可分性判據(jù)基于概率密度函數(shù)的可分性判據(jù)主要考慮的是兩類的概率分布情況?？紤]如圖5-1所示兩種極端情況,容易看出,圖5-1(a)中兩類是完全可分的,圖5-1(b)中兩類是完全不可分的,兩類概率密度函數(shù)的重疊程度反映了兩類的可分性,因此,可以利用類條件概率密度函數(shù)構(gòu)造可分性判據(jù)。圖5-1一維情況下兩類類條件概率密度分布情況兩類概率密度函數(shù)完全分開；兩類概率密度函數(shù)完全重疊基于類條件概率密度函數(shù)p(x|ω1)、p(x|ω2)的可分性判據(jù)Jp應滿足以下四個條件:

(1)非負性:(5-32)(2)對稱性:(5-33)(3)最大值:當兩類完全可分時,Jp具有最大值。

(4)最小值:當兩類完全不可分時,Jp具有最小值,即Jp=0。下面介紹三種典型的基于概率密度函數(shù)的可分性判據(jù)。

1.巴氏(Bhattacharyya)距離

Bhattacharyya距離的定義式為(5-34)它與最小錯誤概率判決準則的錯誤概率Pe具有如下關系:(5-35)證明過程如下:

2.切諾夫(Chernoff)界限距離

Chernoff界限距離的定義式為(5-36)由定義式可見,當s=1/2時,Chernoff界限距離就是Bhattacharyya距離。一般情況下JC的計算比較困難,當ω1、ω２的類條件概率密度函數(shù)分別為正態(tài)分布密度函數(shù)(μi,Σi)和(μj,Σj)時,可以推導出(5-37)

3.散度

在第2章的討論中,對于兩類的分類問題,最大后驗概率判決準則可以通過似然比和某個閾值的比較實現(xiàn),顯然似然比對于分類來說是一個重要的度量。對于給定某個閾值,P(ω1|x)/P(ω2|x)越大,對類ω1來講可分性越好,該比值反映了兩類類條件概率密度函數(shù)的重疊程度。為了保證概率密度函數(shù)完全重疊時判據(jù)為零,應對該比值取對數(shù)。又因為x具有不同的值,應該考慮類ω1的均值。定義類ω1相對于類ω2的平均可分性信息為(5-38)類ω2相對于類ω1的平均可分性信息為(5-39)對于ω1和ω2兩類總的平均可分性信息稱為散度,其定義為(5-40)將式(5-38)、式(5-39)代入式(5-40)可得(5-41)5.2.3基于熵函數(shù)的可分性判據(jù)由信息論可知,對于一組概率分布而言,分布越均勻,平均信息量越大,分類的錯誤概率越大;分布越接近0-1分布,平均信息量越小,分類的錯誤概率越小,可分性越好。因此,可以建立基于熵函數(shù)的可分性判據(jù),其中熵函數(shù)表征平均信息量。對于后驗概率P(ωi|x)而言,分類效果最不好的情形為m類分布等概率的情形:(5-42)分類時任取一類判決,正確率為1/m,錯誤率為(m－1)/m。若后驗概率為0-1分布,即(5-43)則應判x對應的模式屬于第i類,錯誤概率等于0。從特征選擇與提取的角度看,人們希望采用具有最小不確定性的那些特征進行分類,也就是保留熵函數(shù)小的特征。為此可定義基于熵函數(shù)的可分性判據(jù):(5-4４)由上式可知,H是P(ω1|x),P(ω2|x),…,P(ωm|x)的函數(shù),它滿足以下幾個條件:

(1)非負性:H≥0(5-45)(2)對稱性:(5-46)(3)最小值:完全可分出現(xiàn)在后驗概率為0-1分布的情形:(5-47)此時信息熵具有最小值。

(4)最大值:最大值對應分類效果最不好的情形。在多類情況下,分類效果最差的出現(xiàn)條件是各類后驗概率相等,即(5-48)滿足上述性質(zhì)的廣義熵表達形式很多,作為一個廣義熵的表述,其定義為(5-49)其中α是一實的正參數(shù),α≠1。對應不同的α值可得到不同的可分性判據(jù)。當α→1時,根據(jù)洛必達法則可得Shannon熵(5-50)當α=2時,可以得到平方熵(5-51)由于需要考慮到特征空間中每個樣本點的熵函數(shù),因此用熵函數(shù)在整個特征空間的統(tǒng)計平均(5-52)作為可分性判據(jù)。5.3基于可分性判據(jù)的特征提取特征提取作為一種特征空間維數(shù)壓縮方法,其主要特點在于通過變換的方法實現(xiàn)對原始特征的計算,使變換后的二次特征可以去掉一些分量。從數(shù)學上看,任何定義在原始特征空間上的任何數(shù)學計算都是一種變換。本節(jié)主要討論線性變換。對于任何一種給定的線性變換而言,變換后的特征是否對分類有效,決定了變換方法的有效性?？紤]到特征的有效性是由可分性判據(jù)來表征的,因此,變換方法的有效性可以借助于變換結(jié)果的有效性表達?？煞中耘袚?jù)的基礎主要有三類:距離、概率密度函數(shù)和熵函數(shù),因此,基于可分性判據(jù)的特征提取方法也有相應的三種:基于距離可分性判據(jù)的特征提取方法、基于概率密度函數(shù)可分性判據(jù)的特征提取方法和基于熵函數(shù)可分性判決的特征提取方法。上述方法的基本思路如下:對于n個原始特征構(gòu)成的特征向量x=(x1,x2,…,xn)T,特征提取就是對x作線性變換,產(chǎn)生d維向量y=(y1,y2,…,yd)T,d≤n,即y=WTx

(5-53)式中,W=Wn×d稱為特征提取矩陣或簡稱變換矩陣?；诳煞中耘袚?jù)的特征提取就是在一定的可分性判據(jù)下,如何求最優(yōu)的變換矩陣W。5.3.1基于距離可分性判據(jù)的特征提取方法前面研究了基于距離的可分性判據(jù),得到了相應判據(jù),它們都反映了一個基本思想,即類內(nèi)距離小和類間距離大的要求。下面我們以J2準則為例討論特征提取的方法。設Sw和Sb為原始特征空間的類內(nèi)離散度矩陣和類間離散度矩陣,S*w和S*b為變換后特征空間的類內(nèi)離散度矩陣和類間離散度矩陣,W為變換矩陣。則有(5-54)(5-55)在變換域中,(5-56)為了求使J2(W)最大的變換,就要求J2(W)對W的各分量的偏導數(shù)為零。這里我們不做詳細的推導,只給出求解變換矩陣的解析解法。設矩陣S-1wSb的特征值為λ1,λ2,…,λn,按大小順序排列為相應的正交化、歸一化的特征向量為選前d個特征向量作為變換矩陣:此結(jié)論對于J4判據(jù)也適用。5.3.2基于概率密度函數(shù)可分性判據(jù)的特征提取方法基于概率密度函數(shù)的可分性判據(jù)的方法需要知道各類的概率密度函數(shù)的解析形式,難度較大,計算量也較大。一般地,只有當概率密度函數(shù)為某些特殊的函數(shù)形式時才便于使用,這里只研究多元正態(tài)分布的兩類問題。對于基于概率密度函數(shù)可分性判據(jù)的特征提取方法而言,通常選用的變換仍為線性變換,設n維原始特征向量x經(jīng)線性變換后的二次特征向量為y,即(5-57)在映射后的特征空間內(nèi)建立某種準則函數(shù),使得它為變換矩陣W的函數(shù):(5-58)其中,Jc為基于概率密度函數(shù)的可分性判據(jù),如前面介紹的Bhattacharyya距離和Chernoff距離等可分性判據(jù)。通過求解判據(jù)的極值點即可得到使映射后的特征組可分性最好的變換矩陣。在Jc(W)可微的情況下,就是求解偏微分方程:(5-59)下面以Chernoff距離為例,分析特征提取方法。當兩類都是正態(tài)分布時,兩類的分布函數(shù)分別為(5-60)(5-61)變換后的判據(jù)Jc是W的函數(shù),記為Jc(W)(5-62)式中,M=(μ1－μ2)(μ1－μ2)T。因為Jc(W)是標量,可以對W的各個分量求偏導,并令其為零,簡化后的矩陣方程為(5-63)上式是W的非線性函數(shù),只能采用數(shù)值優(yōu)化的方法得到近似最優(yōu)解。但是在以下兩種特殊情況下可以得到最優(yōu)的解析解。

1)Σ1=Σ2=Σ,μ1≠μ2

在此種情況下,最優(yōu)特征提取矩陣是由Σ-1M矩陣的特征向量構(gòu)成的。又因為矩陣M的秩為1,故Σ-1M只有一個非零特征值,對應于特征值為零的那些特征向量對Jc(W)沒有影響,因此可以舍去,所以最優(yōu)變換W是Σ-1M的非零特征值對應的特征向量v,不難得到W=v=Σ-1(μ1－μ2)(5-64)這個結(jié)果與Fisher的線性判別式的解相同。

2)Σ1≠Σ2,μ1=μ2

在此種情況下,最優(yōu)特征矩陣是由Σ-12Σ1滿足下列關系:(5-65)的前d個特征值所對應的特征向量構(gòu)成的,此時Jc(W)取最大值。5.3.3基于熵函數(shù)可分性判據(jù)的特征提取方法

基于熵函數(shù)的可分性判據(jù)的提出,主要是考慮不同分布特性對判決的影響。當多類的分布呈均勻分布時,信息熵為最大值,此時具有最差的可分性。當多類呈0-1分布時,信息熵達到最小值,此時,具有最好的可分性。基于信息熵的可分性判據(jù)和信息熵呈反比關系,為了提取出熵函數(shù)可分性判據(jù)意義上的最佳特征組,也是選擇線性變換,可將變換矩陣帶入判據(jù)表達式:(5-66)(5-67)通過求解判據(jù)的極值點即可得到使映射后的特征組可分性最好的變換矩陣。在JH(W)可微的情況下,就是求解偏微分方程:(5-68)求出極值點即為所求的線性變換,在本書中不展開討論,有需要者可參看有關參考文獻。5.4主分量分析(PCA)一種處理多維的方法是采用組合特征的方法來降低維數(shù),其中,特征的線性組合計算簡單且能夠進行解析分析。從本質(zhì)上來說,線性變換就是將高維空間的數(shù)據(jù)投影到低維空間的過程。主分量分析是一種有效的特征線性變換方法,也稱為K－L變換。K－L變換是一種基于目標統(tǒng)計特性的最佳正交變換,它的最佳性體現(xiàn)在變換后產(chǎn)生的新的分量正交或不相關。設n維隨機向量x=(x1,x2,…,xn)T,x經(jīng)標準正交矩陣A正交變換后成為向量y=(y1,y2,…,yn)T,即(5-69)y的相關矩陣為(5-70)其中,Rx為x的相關矩陣,是對稱矩陣。選擇矩陣A=(a1,a2,…,an),且滿足(5-71)這里,λi為Rx的特征根,并且λ1≥λ2≥…≥λn,ai為λi的正交化、歸一化特征向量,即aTiai=1,aTiaj=0(i≠j;i,j=1,2,…,n)。Ry是對角矩陣:(5-72)若Rx是正定的,則它的特征值是正的。此時變換式(5-69)稱為K-L變換。由式(5-69)可得(5-73)我們選擇x關于ai的展開式的前m項在最小均方誤差準則下估計x,這時估計式表示為(5-74)估計的均方誤差為(5-75)我們希望選擇使估計的均方誤差最小的特征向量,因此要選擇相關矩陣Rx的m個最大的特征值對應的特征向量構(gòu)成變換矩陣A,這樣得到的均方誤差將會最小,是n－m個極小特征值之和?？梢宰C明,與m維向量中的其他x逼近值相比,這個結(jié)果是最小均方誤差解。這就是K-L變換也稱為主分量分析(PCA)的原因。上述分析中采用的是樣本的相關矩陣,也可以采用樣本的協(xié)方差矩陣進行分析。例如,在人臉識別中,PCA是一種常用的特征提取方法。設一幅p×q大小的人臉圖像,可以將它看成是一個矩陣(fij)p×q,fij正比于圖像在該點的灰度級。若將該矩陣按列相連構(gòu)成一個p×q維向量x=(f11,f21,…,fp1,f21,f22,…,fp2,…,f1q,f2q,…,fpq)T

。設訓練樣本集為X={x1,x2,…,xN},包含N個圖像。其協(xié)方差矩陣為(5-76)其中，(5-77)求出矩陣R的前m個最大特征值λ1,λ2,…,λm及其對應的正交化、歸一化特征向量α1,α2,…,αm。分別將這m個特征向量化為p行q列矩陣,得到m幅圖像,稱為“特征臉”。圖5-2顯示的是對應前30個最大特征值的特征向量的圖像。圖5-2“特征臉”圖像將每一幅人臉圖像投影到由a1,a2,…,am張成的子空間中,對應于該子空間的一個點,該點的坐標系數(shù)對應于圖像在子空間的位置,可以作為識別人臉的依據(jù)。對于任意待識別樣本y,可通過向“特征臉”子空間投影獲得系數(shù)向量y′=(a1,a2,…,am)Ty。5.5獨立分量分析(ICA)獨立分量分析(IndependentComponentAnalysis,ICA)的基本思路是在特征空間上尋找到最能使數(shù)據(jù)相互獨立的方向。5.5.1

ICA概述

1.ICA的定義為了給出ICA的嚴格定義,我們可以使用統(tǒng)計上的“隱變量”模型。假設觀測變量x=(x1,x2,…,xn)T可由n個獨立分量y1,y2,…,yn線性組合得到:(5-78)式中,aij(i,j=1,2,…,n)是實系數(shù)。令y=(y1,y2,…,yn)T,A=(aij),式(5-78)可寫成矩陣形式:x=Ay(5-80)例如,ICA可以用于提取人臉圖像的獨立特征,圖5-3是人臉臉譜合成和分解模型。由模型可知,人臉圖像集X={x1,x2,…,xN}被認為是由一個未知的統(tǒng)計獨立圖像集Y={y1,y2,…,yN}和未知的混合矩陣A線性合成的。ICA的目的就是在只給出觀察樣本集時,求出解混合矩陣W和人臉圖像的獨立圖像集Y。圖5-3

ICA人臉圖像合成與分解過程

ICA所提取的人臉圖像的特征向量是每個人臉圖像在這些獨立圖像上的投影系數(shù)V=(v1,v2,…,vN)T,如圖5-4所示圖5-4

ICA提取人臉特征向量

2.ICA的約束為了保證上面給出的ICA模型能夠被估計出來,我們必須給出一定的假設和約束。

(1)獨立分量是統(tǒng)計獨立的。該假設是ICA能夠成立的前提,為保證模型能夠被估計,這個約束已經(jīng)基本足夠,這也是ICA能夠在許多領域的應用中成為強有力的方法的原因。

(2)混合矩陣A是方陣并且可逆。這個假設說明獨立分量的個數(shù)與樣本的個數(shù)是相同的。這個假設在某些情況下是不嚴謹?shù)?但該假設可以大大簡化估計過程。

(3)獨立分量必須具有非高斯分布。高斯分布是非常簡單的一種統(tǒng)計分布,其所有高階累計量都為零,但這樣的高階信息對于估計ICA模型卻是必需的?？梢酝ㄟ^一個例子來解釋:考慮一個只有兩個觀測的ICA模型,假定混合矩陣是正交的,獨立分量yi為高斯分布,具有單位方差,因為觀察變量x1和x2是獨立源的線性組合,故x1和x2也是不相關的具有單位方差的高斯隨機變量,那么它們的聯(lián)合概率密度函數(shù)為(5-81)從圖5-5可以看出,分布是完全對稱的,因此,它不提供任何混合矩陣A各列的方向信息,也就是說無法估計出A。在多個獨立成分是高斯的,其他獨立成分是非高斯的情況下,可以估計出所有的非高斯成分,但是無法估計出其中的高斯成分,因為估計出的高斯成分可能是那些高斯成分的某種線性組合。因此,在獨立分量分析中,應該假設至多只有一個獨立分量為高斯分布,否則就無法估計出ICA模型。圖5-5式（5-81）圖解

3.ICA的預處理

在應用ICA之前,通常要對數(shù)據(jù)作些預處理,使得ICA估計更加簡單,更符合前面約定的條件。

1)中心化不失一般性,我們可以假定所有混合變量與獨立分量均具有零均值,這樣可以在一定程度上簡化理論和算法。如果實際情況不滿足零均值假設,則我們可以通過中心化處理使其滿足要求。中心化其實就是去均值,將隨機變量的中心移向零點。去均值是為了簡化ICA的估計算法。用經(jīng)過去均值處理的數(shù)據(jù)估計獨立分量y,再把y的均值A-1m加回去即可,其中m為x的均值。

2)白化給定一組樣本,通過線性變換將它們轉(zhuǎn)變?yōu)橄嗷o關的方法稱為白化。將樣本x通過一個白化濾波器,得到白色的,其目的是為了加快收斂速度。的元素是不相關的,而且具有單位方差。也就是說,的協(xié)方差矩陣是一個單位陣,即(5-82)通常白化處理采用特征值分解的辦法。假定E(xxT)=QΛQT,其中Q為E(xxT)的特征向量陣,Λ為特征值對角陣,則下式可完成對數(shù)據(jù)的白化處理:(5-83)這里,，。為白化變換矩陣,它不是唯一的。容易看出,任何矩陣UM(U為正交矩陣)也是白化矩陣。顯然,也是白化矩陣。5.5.2基于累積量的ICA估計

ICA有多種不同的估計原理和算法,但就其本質(zhì)而言,都是先設計一個目標函數(shù),然后選擇某種優(yōu)化算法使目標函數(shù)達到極值。我們可以用下面的“方程”來表達這一點:ICA方法=目標函數(shù)+優(yōu)化算法在目標函數(shù)明確的情況下,我們可以使用任何經(jīng)典的優(yōu)化算法,比如(隨機)梯度法和牛頓法等。ICA方法的性質(zhì)依賴于目標函數(shù)和優(yōu)化算法,特別地,ICA的統(tǒng)計特性(如一致性、漸進方差、魯棒性)取決于目標函數(shù)的選擇;算法的性質(zhì)(如收斂速度、存儲需求、數(shù)值穩(wěn)定性)取決于優(yōu)化算法。常用的ICA估計方法有極大化非高斯性的ICA估計方法、ICA的極大似然估計方法、極小化互信息的ICA估計方法、基于高階累積張量的ICA估計方法、基于非線性去相關和非線性PCA的ICA估計方法等。這里主要介紹基于2階和4階累積量的ICA估計以及ICA的極大似然估計方法,其他方法可以參考相關文獻。

ICA方法是根據(jù)PCA方法直接生成的。K-L變換使用2階統(tǒng)計量,變換后特征之間的交叉相關性為零,相應地,變換后樣本的相關矩陣是對角矩陣。在ICA中,變換后特征之間是統(tǒng)計獨立的,也就是說,要求所有高次的交叉累積量為零。交叉累積量是指累積量中至少有兩個變量不同,例如k2(y1y2);若累積量中所有變量都相同,則稱為自累積量,例如k4(yiyiyiyi)=k4(yi)為4階自累積量。將運算限制在4階對很多應用已經(jīng)足夠了,因此,我們只討論4階累積量。y的4個累積量分別為(5-84)(5-85)(5-86)(5-87)在實際應用中,經(jīng)常會遇到均值為零且概率密度函數(shù)是對稱的情況,在這種情況下，所有奇數(shù)階累積量為零,所以,問題可以簡化為尋找一個矩陣W,使得變換后特征之間的2階和4階交叉累積量為零。具體的計算步驟如下:

(1)對輸入數(shù)據(jù)進行PCA變換,即(5-88)其中B是K-L變換中的正交矩陣。因此變換后的各分量之間是不相關的。

(2)計算另一個正交矩陣,使得變換后的樣本各分量的4階交叉累積量為零(5-89)這等同于尋找一個矩陣，使得4階自累積量的平方和最大,即(5-90)上面兩個步驟完成后,最后逼近的獨立分量的特征向量可以由下式得到(5-91)5.5.3ICA的極大似然估計方法估計ICA模型的一個常用方法是極大似然估計方法,其基本思想是采用那些使所得觀測量具有最大概率的參數(shù)估計值。混合向量x=Ay的概率密度函數(shù)可以寫為(5-92)式中,W=A-1,pi表示獨立分量的概率密度函數(shù)。上式可以表示為矩陣W=(w1,w2,…,wn)T和向量x的函數(shù)(5-93)假設有x的T個觀測值x(1),x(2),…,x(T),那么似然函數(shù)可以通過將T個點密度估計相乘得到,似然函數(shù)記為L,將它作為W的函數(shù)(5-94)在實際中普遍使用對數(shù)似然函數(shù)以方便運算，對數(shù)似然函數(shù)可由下式給出：(5-95)式(5-94)和式(5-95)表明,要進行極大似然估計,先要估計出獨立分量的概率密度函數(shù),這是非常困難的。為了得到極大似然估計,需要能夠極大化似然函數(shù)的數(shù)值算法。這里介紹廣泛使用的自然梯度法和FastICA算法。

1.自然梯度法利用梯度法求解極大似然估計的算法為(5-96)其中:期望運算E是從觀測數(shù)據(jù)中計算的平均值,并非理論上的數(shù)學期望;y=Wx;g(y)是一個逐元素的向量函數(shù),即(5-97)也可以使用該算法的隨機版本,即忽略其中的期望運算,且在算法中每次只使用一個數(shù)據(jù)點,即(5-98)這種算法經(jīng)常稱為Bell-Sejnowski算法。梯度法收斂速度非常緩慢,改進措施是對數(shù)據(jù)作白化處理,以及采用自然梯度。自然梯度方法也稱為相對梯度方法,它在相當程度上簡化了原來的梯度方法。自然梯度的原理比較復雜,拋開數(shù)學原理,具體實施辦法相當于在式(5-98)右邊乘以WT=W,這樣得到(5-99)該算法可以解釋為非線性去相關。在梯度法的運行過程中,g(y)=［g1(y1),g2(y2),…,gn(yn)］T中函數(shù)gi(i=1,2,…,n)在兩種非線性函數(shù)之間選擇,根據(jù)下面矩的值來確定:(5-100)若γi>0,則=

(5-101)否則=或=(5-102)其中(5-103)在迭代過程中,可以對γi進行更新,利用γi的更新值,結(jié)合式(5-101)和式(5-102)選擇函數(shù)gi,得到進而更新W,再更新y,即(5-104)(5-105)(5-106)其中:μ和μγ為學習速率;W和γi(i=1,2,…,n)的初始值可以隨機選取,或利用先驗信息選取。

2.

FastICA算法在許多不需要自適應地調(diào)整參數(shù)的場合,梯度法反而會出現(xiàn)問題,而且梯度法的收斂速度經(jīng)常是比較慢。astICA算法正是針對這種情況而提出的,也是各種文獻中提的較多的一種算法。FastICA算法的學習準則就是找到一個單位向量,以便投影向量的非高斯性最大。

FastICA的基本迭代公式如下:(5-107)式中：，，，，g′是g的導數(shù),，，這里所有的gi都固定為tanh函數(shù)。每步迭代后,矩陣W必須投影為白化矩陣:(5-108)式中:C=E(xxT)是數(shù)據(jù)相關矩陣;矩陣(WCWT)-1/2可以通過求矩陣平方根的經(jīng)典方法來實現(xiàn)。具體方法如下。矩陣WCWT的特征值分解為(5-109)其中:E為WCWT的正交化、歸一化特征向量組成的正交矩陣;D=diag(d1,d2,…,dn)為對角矩陣,di為WCWT的特征根。令，可得(5-110)容易驗證,(WCWT)-1/2W是白化矩陣。5.6基于核函數(shù)的方法

5.6.1基于核函數(shù)方法的基本思想前面幾節(jié)討論的特征提取方法所采用的變換都是線性變換,然而,實際中遇到的問題往往較復雜,呈現(xiàn)出非線性特性,對于這種非線性問題,我們可以利用核函數(shù)加以解決?；诤撕瘮?shù)的特征提取方法的基本思想是,通過一個映射將輸入樣本映射到高維特征空間中,使之變?yōu)榫€性問題,然后在高維空間中利用前面提到的線性特征提取方法間接地解決非線性特征提取問題。設非線性映射為:Φ:Rd→H,x→Φ(x),其中,H為某個Hilbert空間。如果在高維空間H中只涉及Φ(xi)的內(nèi)積運算,即〈Φ(xi),Φ(xj)〉,而沒有單獨的Φ(xi)出現(xiàn),則可以用原始空間的函數(shù)實現(xiàn)這種內(nèi)積運算,而沒有必要知道非線性映射Φ的具體形式。統(tǒng)計學習理論指出,根據(jù)HilbertSchmidt原理,只要一種運算滿足Mercer條件,它就可以作為這里的內(nèi)積使用。

定理5.1(Mercer條件)對于任意的對稱函數(shù)K(x,y),它是某個Hilbert空間H的內(nèi)積函數(shù)的充分必要條件是,對于任意的Φ(x)≠0且有(5-111)其中,函數(shù)K(x,y)稱為核函數(shù),K(x,y)=〈Φ(x),Φ(y)〉。核函數(shù)方法逐步成為一種重要的,將非線性問題線性化的普適方法,例如:

(1)將核函數(shù)方法用于主分量分析(PCA)得到基于核函數(shù)的主分量分析方法(KPCA),從而將原本用于線性相關分析的PCA方法擴展到了非線性相關分析的領域;

(2)將核函數(shù)方法用于獨立分量分析(ICA)得到基于核函數(shù)的獨立分量分析(KICA),使得原本用于分解獨立信號線性疊加的ICA方法也可以用于獨立信號的非線性混疊;

(3)將核函數(shù)方法用于線性判別分析(LDA)得到核線性判別分析(KLDA);

(4)支持向量機通過引入核函數(shù),有效地解決了模式分類中的線性不可分問題?？梢?以前解決線性問題時的許多技術(shù)手段,都可以嘗試通過核函數(shù)方法擴展到非線性領域。5.6.2基于核函數(shù)的主分量分析在5.4節(jié)中討論的PCA方法是在最小均方誤差準則下,找到一個d維子空間,使其能夠最好地表達原始的高維數(shù)據(jù)。如果原始數(shù)據(jù)存在復雜的非線性關系,那么線性子空間的表示性能將很差。為了使PCA方法能夠處理非線性問題,將核函數(shù)方法的思想引入PCA,得到基于核函數(shù)的主分量分析(KPCA)。

KPCA算法的基本思想是,對于一個非線性問題,先通過一個非線性映射函數(shù)Φ:Rd→H,將原空間Rd中每個向量x映射到一個高維線性特征空間H中,然后,在高維空間H中進行線性PCA。高維空間的線性PCA對于原始空間來說就是進行非線性PCA。設Φ(xi)(i=1,2,…,N)已經(jīng)去均值,即，則Ｈ空間上樣本集的協(xié)方差矩陣為(5-112)這時,高維空間H中的PCA就是求解(5-113)將高維空間中的每個樣本與式(5-113)作內(nèi)積可得(5-114)假設特征空間H中的所有向量都可由Φ(xi)(i=1,2,…,N)線性表示,即(5-115)合并式(5-112)、式(5-113)和式(5-115),可得(5-116)定義一個N×N核矩陣K=(Kij),其中(5-117)則式(5-116)可簡化為(5-118)因為滿足(5-119)的解必然滿足式(5-118)。通過求解式(5-119)可獲得要求的特征值和特征向量。結(jié)合式(5-115)可知,由矩陣K的特征向量α=(α1,α2,…,α/N)T可以求出C的特征向量v,得到特征空間的主元方向。矩陣K可以通過選擇核函數(shù)來確定。對矩陣K實行對角化,用λΦ1≥λΦ2≥…≥λΦN表示其特征值,α(1),α(2),…,α(N)為相應的正交化、歸一化特征向量,選擇前m個非零特征根λΦ1,λΦ2,…,λΦm及其特征向量α(k)=(α(k)1,α(k)2,…,α(k)N)(k=1,2,…,m)。由式(5-116)可(5-120)為了提取主元特征,計算測試樣本在H空間中向量v(k)上的投影系數(shù)為(5-121)其中:x為原始空間的輸入向量;Φ(x)為高維空間的映射向量。上述算法是在假設映射數(shù)據(jù)均值為零的情況下推導的,但實際上由于沒有顯示的映射函數(shù)Φ,所以不能直接去除均值。一種方法是直接用H空間上樣本集的相關矩陣代替C;另一種方法是先不去均值求得K,然后求(5-122)其中:K為去均值前的核矩陣;為去均值后的核矩陣;IN是所有元素為1/N的矩陣。5.6.3基于核函數(shù)的獨立分量分析和主分量分析法一樣,獨立分量分析(ICA)也是一種基于線性模型的方法,將核函數(shù)的思想應用于ICA,將其擴展到非線性的形式就得到基于核函數(shù)的獨立分量分析(KICA)。與KPCA算法一樣,首先進行一個非線性映射Φ:Rd→H,將原空間Rd中每個向量x映射到一個高維線性特征空間H中,然后在高維特征空間中進行ICA變換。在高維特征空間中首先要對Φ(xi)進行白化處理,這里的白化過程就是要在高維特征空間中求解協(xié)方差矩陣的特征值和對應的特征向量。這個問題在KPCA算法中已得到解決。在KPCA算法中,通過求解特征方程NλΦα=Kα得到特征值和對應的特征向量,這里的矩陣K的元素為k(xi,xj)=〈Φ(xi),Φ(xj)〉。由此求出的特征向量為和相應的特征值λΦ1,λΦ2,…,λΦm。設VΦ=(v(1),v(2),…,v(m)),這樣高維空間中的白化變換矩陣為(5-123)高維特征空間中白化后的樣本為。的計算不涉及非線性映射Φ的具體形式,只與兩個函數(shù)的內(nèi)積有關,即核函數(shù)。得到后,再通過FastICA算法求出相應的分離矩陣WΦ。5.6.4基于核函數(shù)的Fisher線性判別在第4章介紹的Fisher線性判別方法適用于樣本線性可分的條件,但是實際的很多模式識別問題并不具備線性可分性,這時Fisher線性判別就顯得無能為力,因此必須尋找另一種途徑,解決更為復雜的問題。一個可行性的方法就是利用核函數(shù)的思想先把樣本數(shù)據(jù)采用某一非線性映射進行預處理,然后應用線性方法解決問題。將核方法的思想引入Fisher線性判別,得到基于核的Fisher線性判別方法(KFDA)。

KFDA克服了線性Fisher判別法的局限性,利用非線性映射實現(xiàn)輸入空間Rd到高維空間H的映射,即Φ:Rd→H。設輸入空間的樣本集合共有N個樣本{x1,x2,…,xN},這些樣本通過非線性映射形成高維空間的樣本集合{Φ(x1),Φ(x2),…,Φ(xN)}。在高維空間中定義Fisher線性判別的各參數(shù)如下:各類樣本均值向量:(5-124)樣本類內(nèi)離散度矩陣SΦi和總類內(nèi)離散度矩陣Sw:(5-125)(5-126)樣本類間離散度矩陣SΦb:(5-127)設KFDA在高維空間H中尋找最優(yōu)投影方向為w,則Fisher線性判別函數(shù)化為(5-128)使上式最大化的最佳投影方向為(5-129)根據(jù)核函數(shù)理論,w可表示為Φ(x1),Φ(x2),…,Φ(xN)的線性組合,即有(5-130)根據(jù)式(5-124)和式(5-130)可得(5-131)其中，(5-132)結(jié)合式(5-127)和式(5-130)可得(5-133)式(5-133)中,定義(5-134)結(jié)合式(5-126)和式(5-130)可得(5-135)式（5-135）中，定義(5-136)其中:Ki(i=1,2)是N×Ni矩陣,矩陣元素(Ki)jk=K(xj,xk)(xk∈ωi;j=1,2,…,N);I為Ni×Ni單位矩陣;INi為Ni×Ni矩陣,它的所有元素均為1/Ni。因此,KFDA的目標函數(shù)變?yōu)?5-137)最終,高維空間中的Φ(x)在w上的投影變換為(5-138)基于核函數(shù)的Fisher判決方法的分界點可選為(5-139)或(5-140)其中,為高維空間H中投影后的各類的平均值,(5-141)5.7特征選擇方法根據(jù)特征選擇的定義,要從n個特征分量中選出d個最有效的特征。一般情況下,原始特征向量的維數(shù)是已知的,在保證分類效果的前提下,壓縮后的特征空間維數(shù)d未知。因此,特征選擇的目的,不僅在于選出所要保留的特征,而且需確定保留多少個特征,即需要解決兩個問題:什么是有效特征組;尋找有效特征組的方法。特征組可以通過上節(jié)介紹的各種可分性判據(jù)來判斷其有效性。對于特征選擇問題,由于選擇后的特征維數(shù)未知,即d的選擇范圍在1~n之間的任何一個自然數(shù),因此可以有的特征組合為(5-142)當n=100,d=10時,100個里面選10的組數(shù)為17310309456440。若d遍取1~99,則需計算的可分性判據(jù)的個數(shù)為(5-143)可見,選擇范圍是非常大的。因此人們提出了一系列搜索技術(shù),其中一些是次優(yōu)的,一些是最優(yōu)的。5.7.1最優(yōu)搜索算法

分支界定法是一種不包括窮舉搜索的最優(yōu)搜索方法,它的搜索過程可以用一個樹結(jié)構(gòu)來描述,它是一種自上而下的方法。這種方法主要利用了特征選擇可分性判據(jù)的單調(diào)性,即對于兩個特征子集X和Y,有。下面用一個例子來描述這種方法。假設希望從5個特征中選擇最好的3個特征,整個搜索過程采用樹結(jié)構(gòu)表示出來,節(jié)點所標的數(shù)字是剩余特征的標號。每一級在上一級的基礎上去掉1個特征。5個特征中選3個,兩級即可。為了使子集不重復,僅允許按增序刪除特征,這樣就避免了計算中不必要的重復。假定已獲得樹結(jié)構(gòu)如圖5-6所示,我們從分支數(shù)量不密集的部分到分支數(shù)最密集的部分(圖5-6中的從右到左)搜索樹結(jié)構(gòu)。搜索過程在總體上是由上至下,從右至左地進行。在這個過程中包含幾個子過程:向下搜索、更新界值、向上回溯、停止回溯再向下搜索。圖5-6分支界定法樹型圖圖5-7中將計算出的每個節(jié)點的可分性判據(jù)值標于相應節(jié)點。開始時置界值B=0,首先從樹的根節(jié)點沿最右邊的一支自上而下搜索,直接到達葉節(jié)點,得到特征集(1,2,3),可分性判據(jù)值為J=77.2,此時更新界值B=77.2,搜索回溯到最近的分支節(jié)點,并向下行進到該節(jié)點下一個最右的分支,計算J({1,2,4,5}),然后計算J({1,2,4}),發(fā)現(xiàn)該值比當前界值小,因此拋棄該特征組合,并回溯到上一級節(jié)點,再向下搜索到節(jié)點(1,2,5)并計算J({1,2,5}),該值大于界值,則更新界值B=80.1。圖5-7分支界定法搜索回溯示意圖類似地計算J({1,3,4,5}),由于其值小于界值,因此中止對該節(jié)點以下部分的樹結(jié)構(gòu)搜索,因為根據(jù)單調(diào)性,該特征集合的所有子集的可分性判據(jù)都低于其自身的可分性判據(jù)。這時該算法回溯到最近的分支節(jié)點并向下進行到下一個最右分支(2,3,4,5)。計算J({2,3,4,5}),同樣,由于其值低于界值,該節(jié)點以下的其余部分也無需計算。這樣,盡管并沒有計算所有三個變量的可能組合的可分性判據(jù),但該算法仍然是最優(yōu)的。該算法高效的原因在于:(1)利用了判據(jù)J值的單調(diào)性;(2)樹的右邊比左邊結(jié)構(gòu)簡單,而搜索過程正好是從右至左進行的5.7.2次優(yōu)搜索算法

1.單獨最優(yōu)特征組合從n個特征中直接選出d個特征,若要直接計算,需要計算所有可能特征組合的可分性判據(jù)以尋找其中最優(yōu)的一組特征,計算量相對較大,單獨最優(yōu)特征組合方法提出了一種較簡單的方法。單獨最優(yōu)特征組合方法的基本思路是,計算每個特征單獨使用時的有效性判據(jù)值,并根據(jù)該值對特征進行排序,使選擇前d個分類效果最好的特征作為特征集。這種方法在特征之間不相關時,能夠得到合理的特征集,然而,如果特征之間是相關的,則選擇的特征集將是次優(yōu)的,其原因是該方法忽略了各特征之間的相關性。

2.順序前進法順序前進法(SequentialForwardSelection,SFS)的基本思路是從空集開始,每次從未選入的特征中選擇一個特征,使它與已選入的特征組合在一起的有效性判據(jù)最大,直到選入特征數(shù)目達到指定維數(shù)為止。該方法是一種自下而上的搜索方法。

SFS法考慮了所選特征與已入選特征之間的相關性,因此其性能優(yōu)于單獨最優(yōu)特征組合方法,但這種方法的主要缺點是一旦某個特征被選入特征組合,即使加入新的特征使它變得多余,也無法再將其剔除。

SFS法每次增加一個特征,它沒有考慮未入選特征之間的相關性,為了克服這一缺點,人們將SFS算法進行推廣,在增加特征時每次增加r個特征,即每次從未入選的特征中選擇r個特征,使r個特征加入后有效性判據(jù)最大,這種方法稱為廣義順序前進法(GeneralizedSequentialForwardSelection,GSFS)。

3.順序后退法順序后退法(SequentialBackwardSelection,SBS)的基本思路是從全部特征開始,每次剔除一個特征,所剔除的特征應使保留下的特征組合的有效性判據(jù)最大。該方法是一種自上而下的搜索方法。順序后退法的計算是在高維空間中進行的,因此計算量比順序前進法要大。此方法也可以推廣到每次剔除r個特征的廣義順序后退法(GeneralizedSequentialBackwardSelection,GSBS)。

4.增l減r法

增l減r

法(l－r法)克服了前面方法中一旦特征被選入(或剔除)就不能再剔除(或選入)的缺點,在特征選擇過程中允許回溯。該算法步驟如下(假設已經(jīng)選入k個特征,達到特征組Xk):

(1)用SFS法在未選入的特征中逐個選入l個特征,形成新的特征組Xk+l,置k=k+l,Xk=Xk+l。

(2)用SBS法從Xk中逐個剔除r個特征,形成新的特征組Xk－r,置k=k－r,Xk=Xk－r。若k=d,則結(jié)束;否則轉(zhuǎn)至(1)步。需要指出的是,若l>r,則l－r法是自下而上的算法,先執(zhí)行(1),然后執(zhí)行(2),起始時置

;若l<r,則l－r法是自上而下的算法,先執(zhí)行(2),然后執(zhí)行(1),起始時置k=N,X0={x1,x2,…,xN}。5.7.3遺傳算法特征的選擇是一個組合優(yōu)化問題,因此可以使用解決優(yōu)化問題的方法解決特征選擇問題。遺傳算法作為一種通用的優(yōu)化算法,由于其編碼技術(shù)和遺傳操作比較簡單,優(yōu)化不受限制性條件約束以及其并行性和全局解空間搜索,越來越受到人們的重視。遺傳算法主要從達爾文的生物進化論得到啟迪。生物在自然界中的生存繁衍,顯示出了其對自然環(huán)境優(yōu)異的自適應能力。受其啟發(fā),人們致力于對生物各種生存特性的機理研究和行為模擬,為人工自適應系統(tǒng)的設計和開發(fā)提供了廣闊的前景。基于對生物遺傳和進化過程的計算機模擬,產(chǎn)生了遺傳算法,它使得各種人工系統(tǒng)有優(yōu)良的自適應能力和優(yōu)化能力。我們習慣上把Holland在1975年提出的基本遺傳算法稱為經(jīng)典遺傳算法或者叫做傳統(tǒng)遺傳算法(CanonicalGeneticAlgorithm,CGA)。運用基本遺傳算法進行問題求解的過程如下:

(1)編碼:GA在進行搜索之前先將解空間的可行解數(shù)據(jù)表示成遺傳空間的基因型結(jié)構(gòu)數(shù)據(jù),這些結(jié)構(gòu)數(shù)據(jù)的不同組合就構(gòu)成了不同的可行解。

(2)初始群體的生成:隨機產(chǎn)生N個初始結(jié)構(gòu)數(shù)據(jù),每個結(jié)構(gòu)數(shù)據(jù)稱為一個個體,N個個體構(gòu)成了一個群體。GA以這N個結(jié)構(gòu)數(shù)據(jù)作為初始點開始迭代。

(3)適應度評估檢測:適應度函數(shù)表明個體或者解的優(yōu)劣性。不同的問題,適應度函數(shù)的定義方式不同。

(4)選擇:是為了從當前群體中選出優(yōu)良的個體,使它們有機會作為父代為下一代繁殖子孫。遺傳算法通過選擇過程體現(xiàn)這一思想,進行選擇的原則是適應度強的個體為下一代貢獻一個或者多個后代的概率大。選擇實現(xiàn)了達爾文的適者生存原則。

(5)交叉:是遺傳算法中最主要的遺傳操作。通過交叉操作可以得到新一代個體,新個體繼承了父代個體的特性。交叉體現(xiàn)了信息交換的思想