圖像分析及識(shí)別_課件_7

1、123如果沒(méi)有物體識(shí)別的幫助，即使是最簡(jiǎn)單的機(jī)器視覺(jué)問(wèn)題也無(wú)法解決。模式識(shí)別被用于區(qū)域和物體的分類(lèi)，為了學(xué)習(xí)更復(fù)雜的機(jī)器視覺(jué)操作，有必要先了解一些基本的模式識(shí)別方法。 4物體或區(qū)域分類(lèi)已經(jīng)被提到過(guò)多次，識(shí)別是自底向上圖像處理方法的最后步驟，此外它也經(jīng)常被用于圖像理解的其它控制策略。當(dāng)需要得到有關(guān)一個(gè)物體或區(qū)域的信息時(shí)，幾乎總是要用上某種模式識(shí)別方法。5沒(méi)有先驗(yàn)知識(shí)是無(wú)法進(jìn)行識(shí)別的。對(duì)于被分類(lèi)物體到底屬于哪一個(gè)類(lèi)別或群體的判斷根據(jù)的是那些對(duì)物體分類(lèi)提供了必要信息的關(guān)于物體及類(lèi)別的知識(shí)。既需要關(guān)于待處理物體的特殊信息，同時(shí)也需要關(guān)于物體類(lèi)別的高層次的一般知識(shí)。 6首先，我們將介紹常用的知識(shí)表示方法

2、。在計(jì)算機(jī)上用適當(dāng)?shù)男问奖磉_(dá)知識(shí)并不是一個(gè)簡(jiǎn)單明了的概念。78人工智能研究有關(guān)知識(shí)和知識(shí)表示的問(wèn)題，計(jì)算機(jī)視覺(jué)則利用這些研究的結(jié)果。在較高層次的處理中通常要用到人工智能的方法。為了完全掌握計(jì)算機(jī)視覺(jué)和圖像理解，有必要對(duì)人工智能有所了解。 9已有的經(jīng)驗(yàn)表明，一個(gè)好的知識(shí)表示設(shè)計(jì)是解決理解問(wèn)題的關(guān)鍵所在。并且，對(duì)一個(gè)人工智能系統(tǒng)來(lái)說(shuō)，如果假定已經(jīng)有了復(fù)雜的知識(shí)基礎(chǔ)，則通常只需要幾個(gè)相對(duì)簡(jiǎn)單的控制策略就能夠?qū)崿F(xiàn)很復(fù)雜的行為。10換句話(huà)說(shuō)，要表現(xiàn)出智能的行為并不需要非常復(fù)雜的控制策略，而是需要一個(gè)龐大的先驗(yàn)數(shù)據(jù)和假設(shè)集合，并且這些先驗(yàn)知識(shí)具有良好的結(jié)構(gòu)化表示。其它一些需要規(guī)范使用的術(shù)語(yǔ)還有語(yǔ)法和語(yǔ)義。

3、11q一個(gè)表示的語(yǔ)法是指可能用到的符號(hào)和這些符號(hào)的合法排列方式。q一個(gè)表示的語(yǔ)義是指語(yǔ)法允許的符號(hào)和符號(hào)排列所表達(dá)的含義。q一個(gè)表示則是一個(gè)可以描述事物的語(yǔ)法和語(yǔ)義的集合。12人工智能中的主要知識(shí)表示技術(shù)有形式語(yǔ)法和語(yǔ)言、謂詞邏輯、產(chǎn)生式規(guī)則、語(yǔ)義網(wǎng)絡(luò)和框架。知識(shí)表示數(shù)據(jù)結(jié)構(gòu)大都是常規(guī)數(shù)據(jù)結(jié)構(gòu)的擴(kuò)展，如鏈表、樹(shù)、圖、表、分級(jí)（分層）、集合、環(huán)、網(wǎng)、矩陣等。13描述和特征不能被看作是純粹的知識(shí)表示。但是，它們作為復(fù)雜表示結(jié)構(gòu)的一部分，可以用來(lái)描述知識(shí)。 描述通?？梢员硎疚矬w的某些標(biāo)量特性，稱(chēng)為特征。14一般來(lái)說(shuō)，僅僅一個(gè)描述不足以表示物體，因此可以聯(lián)合幾個(gè)描述形成特征向量。數(shù)值特征向量是統(tǒng)計(jì)模式

4、識(shí)別的輸入。15例如，大小特征可以用來(lái)表示面積特性，緊致度特征表示圓形度。如果假定已知關(guān)于大小和圓形度的信息，則采用特征向量x=(size, compactness)可以將物體分為如下幾類(lèi)：小、大、圓形、非圓形、小圓形、小非圓形等等。 16 當(dāng)描述一個(gè)物體的結(jié)構(gòu)時(shí)，特征描述不再適用。一個(gè)結(jié)構(gòu)化描述由現(xiàn)有基元和這些基元之間的關(guān)系生成。 基元由它們的類(lèi)型信息表示。最簡(jiǎn)單的結(jié)構(gòu)化表示形式有鏈、樹(shù)和廣義圖。 17一個(gè)物體可以用由符號(hào)構(gòu)成的鏈、樹(shù)或圖等來(lái)描述。然而，整個(gè)物體類(lèi)別卻不能僅僅用一個(gè)簡(jiǎn)單的鏈、樹(shù)等描述。如果一個(gè)類(lèi)別中的物體都已經(jīng)被結(jié)構(gòu)化描述了，則這個(gè)類(lèi)可以用語(yǔ)法和語(yǔ)言來(lái)表示。語(yǔ)法和語(yǔ)言提供了如

5、何由一個(gè)符號(hào)（基元）集合構(gòu)造鏈、樹(shù)或圖的規(guī)則。 18謂詞邏輯在知識(shí)表示中有著非常重要的作用它為從舊知識(shí)中通過(guò)演繹得到新知識(shí)提供了一種數(shù)學(xué)形式。謂詞邏輯的處理對(duì)象是邏輯變量、量詞和邏輯運(yùn)算符的組合。邏輯變量都是二值的。證明思想和推論規(guī)則，如假言法則和歸結(jié)法構(gòu)成了謂詞邏輯的主體。 19產(chǎn)生式規(guī)則代表了諸多基于條件行動(dòng)對(duì)的知識(shí)表示。一個(gè)基于產(chǎn)生式規(guī)則的系統(tǒng)所表現(xiàn)出的行為，從本質(zhì)上可以描述為如下模型： if 條件X 成立 then 采取行動(dòng) Y。何時(shí)采取怎樣的行動(dòng)的信息代表了知識(shí)。20 為了彌補(bǔ)數(shù)值或精確知識(shí)表示的明顯局限性，可以采用模糊邏輯。模糊規(guī)則有如下形式： if X 是 A then Y 是

6、BX和Y代表某種性質(zhì)，A和B為語(yǔ)言變量。if圓形度很高then物體有很大可能性是球。21 語(yǔ)義網(wǎng)絡(luò)是關(guān)系數(shù)據(jù)結(jié)構(gòu)的一個(gè)特殊變種。語(yǔ)義網(wǎng)絡(luò)由物體、物體的描述及它們之間的關(guān)系（通常是鄰近物體之間的關(guān)系）組成。22知識(shí)的邏輯形式可以被包含在語(yǔ)義網(wǎng)絡(luò)內(nèi)，謂詞邏輯可以用來(lái)表示或估計(jì)局部信息和局部知識(shí)。語(yǔ)義網(wǎng)絡(luò)采用的數(shù)據(jù)結(jié)構(gòu)是賦值圖，節(jié)點(diǎn)表示物體，弧表示物體間的關(guān)系。下面關(guān)于人臉的定義就是語(yǔ)義網(wǎng)絡(luò)的一個(gè)簡(jiǎn)單例子。 2324 框架提供了一種非常通用的知識(shí)表示方法。這種方法可以包含迄今為止所介紹的所有知識(shí)表示法則。有時(shí)也被稱(chēng)為腳本?？蚣苓m合表示特殊環(huán)境下的普通知識(shí)。 25框架可以用來(lái)代替缺失的信息，這些信息可

7、能在視覺(jué)問(wèn)題中至關(guān)重要。 從形式化的觀點(diǎn)來(lái)看，框架以一個(gè)廣義語(yǔ)義網(wǎng)絡(luò)加上一個(gè)相關(guān)變量、慨念和情景串聯(lián)的列表來(lái)表示。并不存在框架的標(biāo)準(zhǔn)形式。26框架代表一種利用基本類(lèi)型的物體組織知識(shí)，利用特定場(chǎng)合的典型行為描述物體間相互關(guān)系的工具?？蚣鼙豢醋魇且环N高層次知識(shí)表示。2728一個(gè)物體是一個(gè)物理單位，在圖像分析和計(jì)算機(jī)視覺(jué)中通常表示為分割后圖像中的一個(gè)區(qū)域。整個(gè)物體集合可以被分為幾個(gè)互不相交的子集合，子集合從分類(lèi)的角度來(lái)看具有某種共同特性，被稱(chēng)為類(lèi)。29物體識(shí)別從根本上說(shuō)就是為物體標(biāo)明類(lèi)別，而用來(lái)進(jìn)行物體識(shí)別的工具叫做分類(lèi)器。類(lèi)別的數(shù)目通常是事先已知的，一般可以根據(jù)具體問(wèn)題而定。但是，也有可以處理類(lèi)別

8、數(shù)目不定情況的方法。 30分類(lèi)器（與人類(lèi)相似）并不是根據(jù)物體本身來(lái)做出判斷的而是根據(jù)物體被感知到的某些性質(zhì)。這些被感知到的物體特性稱(chēng)做模式。分類(lèi)器實(shí)際識(shí)別的不是物體，而是物體的模式。物體識(shí)別同模式識(shí)別被認(rèn)為是同一個(gè)意思。31 構(gòu)建形式描述模式分類(lèi)器分類(lèi)物體32q步驟“構(gòu)造形式化描述”基于設(shè)計(jì)者的經(jīng)驗(yàn)和直覺(jué)。q選擇一個(gè)基本性質(zhì)集合，用來(lái)描述物體的某些特征，這些性質(zhì)以適當(dāng)?shù)姆绞胶饬?，并?gòu)成物體的描述模式。這些性質(zhì)可以是定量的，也可以是定性的，形式也可能不同。33模式識(shí)別理論研究如何針對(duì)特定的（選擇的）基本物體描述集合設(shè)計(jì)分類(lèi)器。統(tǒng)計(jì)物體描述采用基本數(shù)值表述，這稱(chēng)為特征，x1, x2,xn。 特征來(lái)

9、自于物體描述。 34描述一個(gè)物體的模式（也稱(chēng)做模式向量，或特征向量）是一個(gè)基本描述的向量。所有可能出現(xiàn)的模式的集合即為模式空間X，也稱(chēng)為特征空間。 35如果基本描述選擇得合適的話(huà)，類(lèi)內(nèi)物體間的相似性會(huì)使得物體模式在模式空間中也相鄰。在特征空間中各類(lèi)會(huì)構(gòu)成不同的聚集，這些聚集可以用分類(lèi)曲線（或高維特征空間中的超曲面）分開(kāi)。36 37若存在一個(gè)分類(lèi)超曲面可以將特征空間分為若干區(qū)域，并且每個(gè)區(qū)域內(nèi)只包含同一類(lèi)物體，則這個(gè)問(wèn)題被稱(chēng)為是具有可分類(lèi)別的。若分類(lèi)超曲面是一個(gè)平面的話(huà)，則稱(chēng)為是線性可分的。若問(wèn)題具有可分類(lèi)別，則每個(gè)模式只能表示一類(lèi)物體。38直觀地，我們希望可分類(lèi)別能夠被準(zhǔn)確無(wú)誤地識(shí)別。然而大多

10、數(shù)物體識(shí)別問(wèn)題并不具有可分類(lèi)別，這種情況下在特征空間中不存在一個(gè)分類(lèi)超曲面可以將各類(lèi)無(wú)誤地分開(kāi)，肯定會(huì)有某些物體被錯(cuò)分。 39統(tǒng)計(jì)分類(lèi)器是一個(gè)具有n個(gè)輸入端和1個(gè)輸出端的裝置。每個(gè)輸入端接收從待分類(lèi)物體測(cè)量得到的n個(gè)特征x1, x2, , xn中的一個(gè)。40一個(gè)R-類(lèi)分類(lèi)器的輸出為R個(gè)符號(hào)1, 2, , R中的一個(gè)，用戶(hù)將這個(gè)輸出符號(hào)視為對(duì)待分類(lèi)物體的類(lèi)別判斷。輸出符號(hào)r就是類(lèi)別標(biāo)識(shí)符。41函數(shù)d(x)=r描述了分類(lèi)器輸入與輸出之間的關(guān)系，稱(chēng)為決策規(guī)則。決策規(guī)則將特征空間分成R個(gè)不相交的子集Kr，r=1,R，每個(gè)子集包含所有滿(mǎn)足d(x)= r 的物體特征表示向量x。42子集Kr，r=1,R間的

11、邊界構(gòu)成了前面提到的分類(lèi)超曲面。設(shè)計(jì)分類(lèi)器的目的就是要確定分類(lèi)超曲面（或定義決策規(guī)則）。 43分類(lèi)超曲面可以由R個(gè)標(biāo)量函數(shù)g1(x), g2(x), , gR(x)定義，這些函數(shù)被稱(chēng)為判別函數(shù)。物體模式x將被識(shí)別為判別函數(shù)具有最大輸出值的類(lèi)別： )(max)()(,.,1xgxgxdsRsrr44線性判別函數(shù)是最簡(jiǎn)單的判別函數(shù)，但應(yīng)用十分普遍。其一般形式為：其中r=l,R。若分類(lèi)器的所有判別函數(shù)都是線性的，則稱(chēng)此分類(lèi)器為線性分類(lèi)器。 nrnrrrxqxqqxg110)(45另一種方法基于最小距離準(zhǔn)則構(gòu)造分類(lèi)器。假設(shè)特征空間中定義了R個(gè)點(diǎn)，v1, v2, , vR為類(lèi)1, 2, , R的代表，或

12、稱(chēng)樣本模式。最小距離分類(lèi)器將待分類(lèi)模式x識(shí)別為距其最近的代表所在的類(lèi)別。xVxVxdsRsrr ,.,1min)(46若每類(lèi)僅由一個(gè)模式表示。則分類(lèi)器將是線性的。若一類(lèi)中可能具有多個(gè)模式，則分類(lèi)器為分段線性的分類(lèi)超平面。47非線性分類(lèi)器通常利用某些適當(dāng)?shù)姆蔷€性函數(shù)，將原始特征空間Xn變換到一個(gè)新的特征空間Xm，其中上標(biāo)n，m表示空間的維數(shù)。 mnmXX:,.,2148非線性變換后，在新的特征空間中就可以采用線性分類(lèi)器了函數(shù)的作用在于將原始特征空間中的非線性分類(lèi)超曲面“拉直”，變成變換特征空間中的超平面。這種利用特征空間變換的方法稱(chēng)為-分類(lèi)器。 49-分類(lèi)器的判別函數(shù)為： 其中r=l,R。 )(

13、)()(110 xqxqqxgmrmrrr50基于判別函數(shù)的分類(lèi)器是一種具有確定性的機(jī)器同一模式x總會(huì)被分到同一個(gè)類(lèi)。模式x可能表示來(lái)自不同類(lèi)別的物體。最優(yōu)分類(lèi)器的設(shè)置應(yīng)該是概率方式的。51錯(cuò)分情況會(huì)給用戶(hù)帶來(lái)某些損失，根據(jù)損失的定義，可以得出不同的最優(yōu)分類(lèi)器設(shè)置標(biāo)準(zhǔn)。從數(shù)學(xué)的角度來(lái)看，這些優(yōu)化標(biāo)準(zhǔn)表示了分類(lèi)損失的平均值。52將分類(lèi)器視為一種通用機(jī)，可以表示規(guī)則集合D中的任一決策規(guī)則。集合D可以根據(jù)某個(gè)與特定判別規(guī)則有關(guān)的參數(shù)向量q進(jìn)行排序。損失J(q)的平均值依賴(lài)于所采用的決策規(guī)則： =d(x, q)。53與上一節(jié)中采用的決策規(guī)則定義相比，增加了參數(shù)向量q，它表示分類(lèi)器使用的特定決策規(guī)則。使

14、得損失J(q)均值最小的決策規(guī)則： 稱(chēng)為最優(yōu)決策規(guī)則，q*稱(chēng)為最優(yōu)參數(shù)向量。 qxd,DqxdqJqJq),()(min*)(54q誤差最小準(zhǔn)則（Bayes準(zhǔn)則，最大似然度）；q最佳近似準(zhǔn)則：基本原理是用事先確定的一系列函數(shù) ，i=1, , n的線性組合對(duì)判別函數(shù)進(jìn)行最佳線性逼近，然后再構(gòu)造-分類(lèi)器。)(xi55能夠由一個(gè)樣本集合對(duì)分類(lèi)器進(jìn)行設(shè)置非常重要，這一過(guò)程被稱(chēng)為分類(lèi)器學(xué)習(xí)。分類(lèi)器設(shè)置根據(jù)的是一個(gè)已標(biāo)明正確類(lèi)別的物體（由特征向量表示）集合這一模式集合連同它們的類(lèi)別信息被稱(chēng)作訓(xùn)練集合。56分類(lèi)器的性能取決于訓(xùn)練集合的性質(zhì)和規(guī)模，而訓(xùn)練集合通常是有限的。不可能在設(shè)計(jì)分類(lèi)器時(shí)用到所有將來(lái)可能要

15、處理的物體；也就是說(shuō)除了訓(xùn)練集合中的模式外，分類(lèi)器還要面對(duì)那些在設(shè)計(jì)和設(shè)置分類(lèi)器時(shí)沒(méi)出現(xiàn)過(guò)的模式。 57分類(lèi)器設(shè)置方法應(yīng)該是歸納式的，因?yàn)閺挠?xùn)練集合的元素中獲取的信息將被推廣到整個(gè)特征空間，這就意味著分類(lèi)器設(shè)置應(yīng)該對(duì)所有可能的模式來(lái)說(shuō)都是（近似）最優(yōu)的，而不僅僅是針對(duì)訓(xùn)練集合。換言之，分類(lèi)器應(yīng)該能夠識(shí)別那些它沒(méi)有“見(jiàn)過(guò)”的物體。 58訓(xùn)練集合越大，得到正確分類(lèi)器的可能性也就越大分類(lèi)正確率和訓(xùn)練集合的大小密切相關(guān)。 一般訓(xùn)練集合大小將經(jīng)過(guò)幾次增加，直到得到正確的分類(lèi)設(shè)置為止。最初無(wú)法解決的問(wèn)題，隨著訓(xùn)練集合的增大，加入了更多的信息，直到求得問(wèn)題的解。 59逐漸增加訓(xùn)練集合大小的基本思想可以理解為

16、：將一個(gè)很大的訓(xùn)練集合的一小部分用來(lái)設(shè)計(jì)分類(lèi)器，而用余下的部分測(cè)試分類(lèi)器的性能。所有分類(lèi)器設(shè)置方法的特性在有生命的生物體的學(xué)習(xí)過(guò)程中都可以找到相似之處，學(xué)習(xí)的基本性質(zhì)如下： 60q學(xué)習(xí)是一個(gè)基于樣本順序輸入的自動(dòng)的系統(tǒng)優(yōu)化過(guò)程。q學(xué)習(xí)的目標(biāo)是使優(yōu)化準(zhǔn)則最小。這一準(zhǔn)則可以用錯(cuò)分損失均值表示。61q訓(xùn)練集合有限，這就要求學(xué)習(xí)過(guò)程具有歸納的特點(diǎn)。q在所有可能的樣本都用來(lái)學(xué)習(xí)之前，通過(guò)推廣已有樣本信息達(dá)到學(xué)習(xí)目的。q樣本可能是隨機(jī)選取的。62對(duì)信息順序輸入的必然要求和系統(tǒng)存儲(chǔ)的有限性導(dǎo)致了學(xué)習(xí)的漸進(jìn)性。q因此，學(xué)習(xí)過(guò)程無(wú)法一步完成，而是一個(gè)循序漸進(jìn)的過(guò)程。 63學(xué)習(xí)過(guò)程根據(jù)樣本搜索最優(yōu)分類(lèi)器設(shè)置。分類(lèi)

17、器系統(tǒng)被構(gòu)造為一個(gè)通用機(jī)，這個(gè)通用機(jī)經(jīng)過(guò)對(duì)訓(xùn)練集合的處理完成優(yōu)化（有監(jiān)督學(xué)習(xí)）。學(xué)習(xí)方法獨(dú)立于應(yīng)用問(wèn)題。64分類(lèi)器性能與可得到的信息總量及其性質(zhì)密切相關(guān)。從這一角度來(lái)說(shuō)，模式應(yīng)該表示盡可能復(fù)雜的描述。但另一方面，這樣做會(huì)帶來(lái)大量的描述特征。因此，物體描述交際上是在允許分類(lèi)錯(cuò)誤率、分類(lèi)時(shí)間和分類(lèi)器構(gòu)造復(fù)雜度之間的一種折衷。 65兩個(gè)常用的學(xué)習(xí)策略：概率密度估計(jì)：對(duì)概率密度p(x|r)和概率P(r), r=1,R進(jìn)行估計(jì)。q判別函數(shù)根據(jù)誤差最小準(zhǔn)則計(jì)算得到。66直接損失最小化：并不估計(jì)概率和概率密度，而是通過(guò)直接對(duì)損失J(q)進(jìn)行最小化尋找決策規(guī)則 。q這種方法采用最佳近似準(zhǔn)則。qxd,67算法：

18、最小距離分類(lèi)器的學(xué)習(xí)和分類(lèi) 學(xué)習(xí)：對(duì)于所有類(lèi)，由訓(xùn)練集合計(jì)算類(lèi)代表Vi： 其中xi(ki+1)為第i類(lèi)的物體，ki表示目前第i類(lèi)被學(xué)習(xí)過(guò)程使用的物體總數(shù)。) 1()(11) 1(iiiiiiiikxkvkkkv68分類(lèi)：對(duì)一個(gè)物體描述向量x，計(jì)算x到所有類(lèi)代表vi的距離。若其中x到vj的距離最短，則將此物體分為第j類(lèi)。69存在不需要學(xué)習(xí)訓(xùn)練集合的分類(lèi)算法。特別地，這類(lèi)分類(lèi)算法不需要學(xué)習(xí)階段中關(guān)于物體類(lèi)別的信息，沒(méi)有指導(dǎo)它們也可以通過(guò)學(xué)習(xí)得到這種信息（無(wú)監(jiān)督學(xué)習(xí)）。這種方法中的一類(lèi)稱(chēng)為聚類(lèi)分析。 70當(dāng)出于某種原因無(wú)法得到訓(xùn)練集合或無(wú)法得到標(biāo)有類(lèi)別的樣本時(shí)，就可以采用聚類(lèi)分析方法。 聚類(lèi)分析方法

19、根據(jù)待處理模式集合中各元素間的相似度將其分為若干子集合（聚類(lèi)）。71每個(gè)聚類(lèi)所包含的模式代表了在被選特征及相似準(zhǔn)則意義下比較相近的物體。不相似的物體分屬不同類(lèi)別。 主要的聚類(lèi)分析方法有兩類(lèi)：第一類(lèi)為分級(jí)式的，第二類(lèi)為非分級(jí)式的。72分級(jí)方法構(gòu)造一棵聚類(lèi)樹(shù)，模式集合被分為差別最大的兩個(gè)子集，每個(gè)子集再被分為不同的子集，等等。非分級(jí)方法順序地將每個(gè)模式分到一個(gè)聚類(lèi)中。 73非分級(jí)聚類(lèi)分析方法要么是參數(shù)化的要么是非參數(shù)化的。參數(shù)化方法基于已知的類(lèi)條件分布，需要對(duì)分布參數(shù)進(jìn)行估計(jì)。74非參數(shù)聚類(lèi)分析是一種應(yīng)用普遍、簡(jiǎn)單實(shí)用的非分級(jí)式聚類(lèi)分析方法。MacQueen k-均值（MacQueen k-mea

20、n）聚類(lèi)分析法是這類(lèi)方法中的一個(gè)著名實(shí)例。 75我們需要假設(shè)聚類(lèi)總數(shù)k已知若k未知，則可令其等于有最大置信度的類(lèi)別總數(shù)，或采用其它不需要這一信息的更復(fù)雜的聚類(lèi)方法。 聚類(lèi)的初始點(diǎn)在第一步中構(gòu)造，由n維特征空間中的k個(gè)點(diǎn)表示。76這些點(diǎn)可以以隨機(jī)方式選取，或直接取集合中的前k個(gè)模式。若聚類(lèi)的代表已如，即使這些代表并不可靠，將它們作為聚類(lèi)初始點(diǎn)也是非常有用的。 77方法主要有兩個(gè)階段：在第一階段中，模式分配到已有聚類(lèi)中的一個(gè)，依據(jù)就是模式到各聚類(lèi)代表的距離，選擇距離最小的類(lèi)。1.然后，計(jì)算該聚類(lèi)所有模式的重心，作為該類(lèi)新的代表。78q若集合中的所有模式都已經(jīng)處理完畢，則當(dāng)前聚類(lèi)代表被最終采用，將每

21、個(gè)模式分到一個(gè)聚類(lèi)中，這些聚類(lèi)由第一階段確定的代表表示。q然后，根據(jù)模式到代表的距離將它們重新分類(lèi)，模式被分到最近的類(lèi)中。79第二階段中不再新計(jì)算代表?？梢钥闯?，各聚類(lèi)的初始點(diǎn)可能最終不在該聚類(lèi)中。80算法：MacQueen k-均值聚類(lèi)分析 定義聚類(lèi)總數(shù)。選擇聚類(lèi)初始點(diǎn)（代表，初始猜測(cè)）v1,v2,vk。通常選擇某些模式作為聚類(lèi)初始點(diǎn)，也可以隨機(jī)選取。 81第一輪：對(duì)每個(gè)模式?jīng)Q定其屬于哪個(gè)聚類(lèi)，選擇距離最近者（初始化聚類(lèi)所用的模式不再處理）。每向一個(gè)聚類(lèi)中加入新物體后重新計(jì)算該類(lèi)代表，可以采用如下公式。) 1()(11) 1(iiiiiiiikxkvkkkv82第二輪：令最終代表為結(jié)果聚類(lèi)的

22、代表。根據(jù)第一輪得到的最終代表對(duì)所有物體分類(lèi)（包括初始化聚類(lèi)所用的模式）。與第一輪采用相同的距離準(zhǔn)則。 8384自從80年代神經(jīng)元網(wǎng)絡(luò)重新受到矚目并成為一種模式識(shí)別的典型方法以來(lái)，這種方法引起了人們的極大興趣。神經(jīng)元網(wǎng)絡(luò)在許多公認(rèn)的“困難”領(lǐng)域，特別是語(yǔ)音和視覺(jué)中的模式識(shí)別問(wèn)題，都是一種強(qiáng)大的工具。85大多數(shù)神經(jīng)元方法都源于基本處理器（神經(jīng)元）的組合，每個(gè)基本處理器接收若干輸入，產(chǎn)生單個(gè)輸出。對(duì)每個(gè)輸入都有一個(gè)權(quán)值與其相關(guān)聯(lián)，于是輸出（大多數(shù)情況下）就是關(guān)于輸入加權(quán)和的一個(gè)函數(shù)。86v1w1v2w2vnwnF(v,w)輸出y輸入由v1,v2,vn表示，權(quán)值為w1,w2, wn，于是神經(jīng)元的整個(gè)

23、輸入為:niiiwvx187或者，更一般的：其中為與該神經(jīng)元相關(guān)的閾值。與神經(jīng)元相關(guān)聯(lián)的還有一個(gè)輸出函數(shù)f(x)，輸出由此函數(shù)產(chǎn)生。niiiwvx188神經(jīng)元集合（網(wǎng)絡(luò)）的主要思想是神經(jīng)元之間相互連接（于是一個(gè)神經(jīng)元的輸出也是另一個(gè)或另一些神經(jīng)元的輸入）。這一思想模仿了大腦中基本神經(jīng)元的高度互連狀態(tài)。89這種互連可能會(huì)接收若干來(lái)自外部的輸入，并產(chǎn)生一些（數(shù)量上可能與外部輸入不同）外部輸出。這些外部輸入與輸出之間的關(guān)系即規(guī)定了網(wǎng)絡(luò)。90基于反向傳播算法的前饋網(wǎng)絡(luò)假定輸入與輸出端之間至少存在一層神經(jīng)元。在前饋網(wǎng)絡(luò)中輸入端接收數(shù)據(jù)，并且數(shù)據(jù)總是沿一個(gè)方向傳遞到輸出端，輸出端最終給出“答案”。 91使

24、用這種網(wǎng)絡(luò)的標(biāo)準(zhǔn)方法是收集一個(gè)訓(xùn)練數(shù)據(jù)集一個(gè)”答案”已知的向量集合。采用這個(gè)訓(xùn)練集再加上某種訓(xùn)練算法就可以讓網(wǎng)絡(luò)進(jìn)行學(xué)習(xí)了，最終得到的網(wǎng)絡(luò)能夠進(jìn)行正確的聯(lián)想。于是，在分類(lèi)模式下，未知模式被送入網(wǎng)絡(luò)。然后網(wǎng)絡(luò)基于對(duì)已有知識(shí)的推廣給出一個(gè)答案。 9293反向傳播算法將網(wǎng)絡(luò)的輸出與希望值進(jìn)行比較，并計(jì)算某種基于差別平方和的誤差測(cè)度，然后再利用梯度下降法調(diào)整網(wǎng)絡(luò)權(quán)重，使得誤差最小化。94另一類(lèi)不同的網(wǎng)絡(luò)是自學(xué)習(xí)的就是說(shuō)無(wú)需一個(gè)已知類(lèi)別信息的訓(xùn)練集合，它們也可以進(jìn)行自組織，達(dá)到自動(dòng)識(shí)別模式的目的。這一大類(lèi)網(wǎng)絡(luò)中又有許多變形，其中最著名的是Kohonen特征圖。 95Kohonen圖的輸入為n維數(shù)據(jù)向量，

25、輸出也是n維的，代表了在鄰近問(wèn)題域內(nèi)對(duì)特定輸入的“最佳表示”。更精確地說(shuō)，網(wǎng)絡(luò)包含一層神經(jīng)元，每個(gè)神經(jīng)元都與輸入向量的所有n個(gè)元素相連，并計(jì)算其自己的輸入，具有最大輸入值的被認(rèn)為是“勝者”。96與輸入弧相關(guān)聯(lián)的n個(gè)權(quán)值就是最后的輸出向量。權(quán)值的更新采用一種尋找自身數(shù)據(jù)結(jié)構(gòu)（就是說(shuō)不需要或真正知道先驗(yàn)類(lèi)別知識(shí)）的學(xué)習(xí)算法實(shí)現(xiàn)。97 98 Hopfield網(wǎng)大多用于優(yōu)化問(wèn)題，然而，可以將識(shí)別問(wèn)題表示為優(yōu)化問(wèn)題，即尋找待識(shí)別模式x和現(xiàn)有代表v之間的最大相似性。 99以上慨述只涉及到了神經(jīng)元網(wǎng)絡(luò)的主要原理和它們同傳統(tǒng)統(tǒng)計(jì)模式識(shí)別的關(guān)系，對(duì)諸多神經(jīng)元網(wǎng)絡(luò)技術(shù)、方法及實(shí)現(xiàn)都未涉及。 100101統(tǒng)計(jì)模式識(shí)

26、別采用定量的物體描述，這類(lèi)描述具有數(shù)值參數(shù)（特征向量）。而句法模式識(shí)別的特點(diǎn)則是定性的物體描述。 物體結(jié)構(gòu)包含于句法描述中。 102當(dāng)特征描述無(wú)法表示被描述物體的復(fù)雜程度時(shí)，或當(dāng)物體可以被表示成由簡(jiǎn)單部件構(gòu)成的分級(jí)結(jié)構(gòu)時(shí)，就應(yīng)該采用句法物體描述。句法描述的物體的最基本性質(zhì)稱(chēng)為基元。 103第6.2.4節(jié)中提到了采用邊界基元的物體邊界的句法描述，這些邊界基元表示邊界上具有特定形狀的片段。物體的圖或關(guān)系描述是一個(gè)很好的例子，其中基元表示具有特定形狀的子區(qū)域。104為所有基元賦一個(gè)符號(hào)后，就可以描述物體各個(gè)基元間的關(guān)系了，最終將得到一個(gè)關(guān)系結(jié)構(gòu)。對(duì)基元描述和它們之間關(guān)系的設(shè)計(jì)不是算法化的，而是基于對(duì)

27、問(wèn)題的分析、設(shè)計(jì)者的經(jīng)驗(yàn)和能力。105基元類(lèi)型不要太多。被選中基元應(yīng)該能形成正確的物體表示?；獞?yīng)該能較容易地從圖像中分割出來(lái)?；獞?yīng)該能夠由某種統(tǒng)計(jì)模式識(shí)別方法較容易地識(shí)別出來(lái)?；獞?yīng)該與待描述物體（圖像）結(jié)構(gòu)的重要的自然部件相對(duì)應(yīng)。 106假定物體已經(jīng)由一些基元和它們之間的關(guān)系正確地描述了。并且，假定對(duì)每一類(lèi)來(lái)說(shuō)其語(yǔ)法都已知，該語(yǔ)法能夠生成特定類(lèi)別中所有物體的描述。107句法識(shí)別決定一個(gè)描述詞語(yǔ)對(duì)于特定類(lèi)的語(yǔ)法是否在句法上是正確的，也就是說(shuō)每個(gè)類(lèi)只包含其句法描述能夠由該類(lèi)語(yǔ)法生成的物體。句法識(shí)別是一個(gè)搜索語(yǔ)法的過(guò)程，目標(biāo)語(yǔ)法能夠產(chǎn)生描述待處理物體的句法詞語(yǔ)。108算法：句法識(shí)別學(xué)習(xí)：根據(jù)對(duì)

28、問(wèn)題的分析，定義基元及它們之間可能的關(guān)系。對(duì)句法描述進(jìn)行人工分析，或利用自動(dòng)語(yǔ)法推導(dǎo)，為每類(lèi)物體構(gòu)造一個(gè)描述語(yǔ)法。109識(shí)別：首先，提取每個(gè)物體的基元，識(shí)別基元所屬類(lèi)別，并描述它們之間的關(guān)系。構(gòu)造代表物體的描述詞語(yǔ)?；趯?duì)描述詞語(yǔ)的句法分析結(jié)果，對(duì)物體進(jìn)行分類(lèi)，若某類(lèi)的語(yǔ)法（在第2步中構(gòu)造）能夠產(chǎn)生該物體的描述詞語(yǔ)，則物體被判定為該類(lèi)。110可以看出統(tǒng)計(jì)識(shí)別和句法識(shí)別的主要區(qū)別在于學(xué)習(xí)過(guò)程。利用目前的技術(shù)，語(yǔ)法構(gòu)造過(guò)程很難算法化，需要大量的人工干預(yù)。111通?；綇?fù)雜，則語(yǔ)法越簡(jiǎn)單，句法分析也越簡(jiǎn)單迅速。但是，復(fù)雜的集元描述使得上述算法中的第3步更加困難、更耗時(shí)間，而且，基元提取和關(guān)系估計(jì)也

29、變得不容易處理。112假設(shè)已經(jīng)成功地提取了基元，則所有內(nèi)部基元關(guān)系都可以從句法上描述為n元關(guān)系，這些關(guān)系構(gòu)成的結(jié)構(gòu)（鏈、樹(shù)、圖）稱(chēng)為詞語(yǔ)，用來(lái)表示物體或模式。113因此每個(gè)模式由一個(gè)詞語(yǔ)描述。特定類(lèi)中所有模式構(gòu)成的集合對(duì)應(yīng)于一個(gè)詞語(yǔ)的集合。這個(gè)詞語(yǔ)集合稱(chēng)為形式語(yǔ)言，并且由一個(gè)語(yǔ)法描述。 114若已存在一個(gè)適當(dāng)?shù)恼Z(yǔ)法可以用來(lái)表示各類(lèi)別的所有模式，則最后一步就是設(shè)計(jì)一個(gè)能夠正確判斷模式（詞語(yǔ)）類(lèi)別的句法分類(lèi)器。 115顯然最簡(jiǎn)單的方法是為每個(gè)類(lèi)分別構(gòu)造一個(gè)語(yǔ)法。未知模式x被輸入一個(gè)由若干黑箱構(gòu)成的平行結(jié)構(gòu)，這個(gè)裝置可以判斷是否xL(Gj)，其中j=1, 2, , R，R為類(lèi)別總數(shù)；L(Gj)為由第

30、j個(gè)語(yǔ)法產(chǎn)生的語(yǔ)言。116如果第j個(gè)黑箱的決定為正，則模式被認(rèn)為是來(lái)自于第j類(lèi)，分類(lèi)器將這個(gè)模式判定為屬于第j類(lèi)。判斷一個(gè)詞語(yǔ)是否能由某個(gè)語(yǔ)法產(chǎn)生是在句法分析過(guò)程中進(jìn)行的。117為了為某類(lèi)模式的語(yǔ)言構(gòu)造盡可能貼切的模型，需要從一個(gè)樣本詞語(yǔ)的訓(xùn)練集合中提取語(yǔ)法規(guī)則。這一從樣本中構(gòu)造語(yǔ)法的過(guò)程稱(chēng)為語(yǔ)法推導(dǎo)。118119本節(jié)將討論基于圖匹配的識(shí)別方法。節(jié)點(diǎn)和弧都賦值的圖將是我們考慮的對(duì)象，這種圖出現(xiàn)在利用關(guān)系結(jié)構(gòu)的圖像描述中。圖匹配的目的是判斷一幅圖像所表示的實(shí)際物體是否與圖模型中關(guān)于這幅圖像的先驗(yàn)知識(shí)相符。120如果將這一任務(wù)表示為模式識(shí)別問(wèn)題，則物體的表示圖應(yīng)該與物體的模型圖完全匹配。若問(wèn)題是在

31、圖像的圖表示中尋找某個(gè)物體（由模型圖表示），則模型圖應(yīng)該與圖像表示圖中的某個(gè)子圖完全匹配。圖之間的完全匹配稱(chēng)為同構(gòu)。121圖同構(gòu)和子圖同構(gòu)的判定是圖論中的經(jīng)典問(wèn)題，在應(yīng)用和理論上都有很大的價(jià)值。 現(xiàn)實(shí)中的問(wèn)題要復(fù)雜得多，因?yàn)樵谧R(shí)別問(wèn)題中完全匹配的要求通常是非常嚴(yán)格的。 122由于物體描述的不準(zhǔn)確、圖像的噪聲、物體間的遮擋、不同光照條件等因素，物體圖通常不能與模型圖完全匹配。圖匹配和圖相似度估計(jì)是一個(gè)非常困難的問(wèn)題。圖相似度估計(jì)中的一個(gè)重要問(wèn)題是設(shè)計(jì)一個(gè)衡量?jī)煞鶊D是否相似的尺度。 123無(wú)論所要求的是圖同構(gòu)還是子圖同構(gòu)，問(wèn)題可以被分為三種主要類(lèi)型：圖同構(gòu)；子圖同構(gòu)：尋找圖G1與另一個(gè)圖G2的子圖

32、間的同構(gòu)； 1.雙重子圖同構(gòu) ：尋找圖G1的子圖與圖G2的子圖間的同構(gòu)。124同構(gòu)的判定對(duì)于未賦值圖和賦值圖來(lái)說(shuō)計(jì)算量都十分龐大。賦值圖在識(shí)別和圖像理解中更常用，其節(jié)點(diǎn)的取值根據(jù)所代表的區(qū)域的性質(zhì)而定，而弧的取值根據(jù)所連接的節(jié)點(diǎn)間的關(guān)系而定。 125上面所提到的所有方法都用來(lái)檢測(cè)圖和或子圖之間是否完全匹配。在實(shí)際應(yīng)用中這些算法無(wú)法區(qū)別兩幅十分相似但有少許差別的圖和兩幅根本不一樣的圖。若要檢測(cè)圖的相似度，則要研究如何量化相似性。 126兩個(gè)字符串（鏈）的相似度可以用Levenshtein距離表示，該距離定義為將一個(gè)串變?yōu)榱硪粋€(gè)串所需的最少操作步數(shù)，可能的操作有刪除、插入、替換。同樣的原理也可以用

33、在圖相似度的計(jì)算上。127先定義可能的節(jié)點(diǎn)和弧的變換（插入、刪除、替換、重新標(biāo)注）集合，再給每種變換賦一個(gè)變換代價(jià)。任一變換序列的代價(jià)用單個(gè)步驟代價(jià)的組合表示。將一個(gè)圖變?yōu)榱硪粋€(gè)圖的所有變換集合中具有最小代價(jià)值的那個(gè)集合就定義了這兩幅圖間的距離。128129考慮圖像識(shí)別和理解問(wèn)題，需要搜索最佳圖像表示（要求圖像和模型間的最佳匹配，目的是得到最佳圖像理解）。一定會(huì)有某種刻畫(huà)優(yōu)良程度的目標(biāo)函數(shù)，也就意味著可以采用某種優(yōu)化技術(shù)，尋找目標(biāo)函數(shù)的最大值，即尋找“最佳”。130一個(gè)函數(shù)優(yōu)化問(wèn)題可以這樣定義：給定某個(gè)有限集合D和一個(gè)函數(shù)f: DR，R為實(shí)數(shù)集，在D中尋找f的最佳值。在D中尋找最佳值可以理解為

34、尋找xD，使得f取到最小值（函數(shù)最小化）或最大值（函數(shù)最大化）。)(min)(minxfxfDx)(max)(maxxfxfDx131函數(shù)f被稱(chēng)為目標(biāo)函數(shù)。在此我們僅考慮目標(biāo)函數(shù)的最大化，因?yàn)樗菆D像解釋?xiě)?yīng)用中的典型問(wèn)題。搜索最大值和最小值的優(yōu)化方法在邏輯上是等價(jià)的，無(wú)論要求目標(biāo)函數(shù)最大化還是最小化，都可以使用優(yōu)化技術(shù)。 132應(yīng)該注意，若目標(biāo)函數(shù)沒(méi)有反應(yīng)結(jié)果的優(yōu)良程度，則無(wú)論什么優(yōu)化算法也不能保證找到正確的解。因此，目標(biāo)函數(shù)的設(shè)計(jì)是決定優(yōu)化算法性能的關(guān)鍵因素（就好比選擇合適的特征是設(shè)計(jì)成功分類(lèi)器的關(guān)鍵）。 133大多數(shù)傳統(tǒng)的優(yōu)化技術(shù)都采用微積分的方法，如爬山算法（求最大值時(shí)）目標(biāo)函數(shù)的梯度給

35、出了最陡峭的攀爬方向。微積分方法的主要局限在于其局部行為，搜索很容易止于一個(gè)局部極大值，而未找到全局最大值。 134有幾種方法用來(lái)增加找到全局最大值的可能性。遺傳算法和模擬退火就屬于這類(lèi)技術(shù)。 135遺傳算法（GA）模擬自然界的進(jìn)化機(jī)制來(lái)尋找目標(biāo)函數(shù)的最大值。遺傳算法不保征找到全局最優(yōu)，但來(lái)自大量應(yīng)用的經(jīng)驗(yàn)顯示最終解通常很接近全局最優(yōu)。這一點(diǎn)在圖像理解的應(yīng)用中十分重要。136在圖像理解或匹配中幾乎總是存在幾個(gè)局部最優(yōu)的穩(wěn)定（合理的）解，但這些可能的解中只有一個(gè)是真正最優(yōu)的，表示了全局最大值。遺傳算法與其他優(yōu)化方法的主要區(qū)別有以下幾個(gè)方面：137GA的作用對(duì)象是參數(shù)集合的編碼，而不是參數(shù)本身。遺

36、傳算法要求將優(yōu)化問(wèn)題的自然參數(shù)集合編碼為有限字符集上的有限長(zhǎng)字符串。這就意味著任何優(yōu)化問(wèn)題表示都要轉(zhuǎn)換成字符串表示，通常采用二值字符中。將問(wèn)題表示設(shè)計(jì)成字符串是GA方法的一個(gè)重要部分。138GA搜索一群點(diǎn)，而不是單個(gè)的點(diǎn)。每一步中被處理的解的代規(guī)模很大。q也就是說(shuō)最優(yōu)搜索是在搜索空間的許多位置同時(shí)進(jìn)行的。這就增加了找到全局最優(yōu)的可能性。 139GA直接利用目標(biāo)函數(shù)，無(wú)需再進(jìn)行其它演化和輔助知識(shí)。對(duì)新的更好的解的搜索只依賴(lài)于評(píng)價(jià)函數(shù)本身的值。GA只負(fù)責(zé)找到評(píng)價(jià)函數(shù)的（近似）全局最優(yōu)。但不保證評(píng)價(jià)函數(shù)與問(wèn)題相關(guān)。評(píng)價(jià)函數(shù)描述了特定字符串的優(yōu)良程度。在GA中，評(píng)價(jià)函數(shù)的值被稱(chēng)為適合度。140GA采用

37、概率方式的變換規(guī)則，而不是確定式的。采用當(dāng)前字符串代生成更優(yōu)一代的變換規(guī)則。即有較高適合度的串將獲得更大的機(jī)會(huì)，而那些適合度較低的串將被淘汰。這是遺傳算法的關(guān)鍵思想。最好的字符串將在進(jìn)化過(guò)程中以更高的概率存活下來(lái)，它就代表了最優(yōu)解。 141q字符串編碼的優(yōu)勝劣汰是通過(guò)三種基本操作實(shí)現(xiàn)的：復(fù)制、交叉和突變。 q字符串的代由GA當(dāng)前正在處理的所有串構(gòu)成。q復(fù)制、交叉和突變的序列作用于上一個(gè)字符串代，從而生成新的一代。 142復(fù)制操作負(fù)責(zé)以慨率的方式保證適者淘汰劣者。復(fù)制機(jī)制將具有很高適合度的字符串拷貝到下一代中。選擇過(guò)程通常是慨率方式的，一個(gè)字符串被復(fù)制到下一代的概率由它在當(dāng)前代中的相對(duì)適合度決定

38、這就是它們的生存法則。 143這就使得一些具有很高適合度的字符符可能在下一代中會(huì)有多個(gè)拷貝。各代字符串的總數(shù)通常保持不變，新一代的平均適合度要高于以前的代。 144交叉的基本思想是令新一代中的字符串進(jìn)行交叉，為一個(gè)字符對(duì)串隨機(jī)地選擇一個(gè)邊界位置，然后交換這兩個(gè)字符串從開(kāi)始到邊界位置的所有字符，以生成兩個(gè)新的字符串。145146并不是所有新生成的字符串都來(lái)自交叉。有一個(gè)概率參數(shù)用來(lái)控制進(jìn)行交叉操作的字符串對(duì)數(shù)。另外，還可以令復(fù)制得到的最佳串保持不變。 147交叉操作和復(fù)制操作構(gòu)成了GA的主要功能。即使字符串本身并不是一個(gè)好的解，也可以在其中找到具有局部較好結(jié)構(gòu)的字符片段。這些字符片段稱(chēng)為圖式。圖

39、式是那些可以作為字符串構(gòu)造部件的子串，可以理解為字符的局部模式。148顯然，若圖式可以被作為局部正確的片段進(jìn)行處理的話(huà)，就可以比將所有字符單獨(dú)考慮更快地找到最優(yōu)解。包含n個(gè)字符串的一代中，大約要處理n3個(gè)圖式。這種處理稱(chēng)為遺傳算法的隱含并行性。 149突變操作在GA中起到輔助作用。其原理是偶爾隨機(jī)地改變一代中某些字符串的一個(gè)字符例如，突變發(fā)生的概率可以是約一千個(gè)位轉(zhuǎn)換中出現(xiàn)一個(gè)（即在代代間轉(zhuǎn)換時(shí)，轉(zhuǎn)換一千個(gè)位就有一位發(fā)生突變）。 150突變的主要原因是字符串中的一些局部的字符組合可能由于復(fù)制操作和交叉操作而完全丟失。突變操作可以防止GA因這種無(wú)法恢復(fù)的丟失而找不到較好的解特征的情況發(fā)生。 15

40、1最少需要多少代達(dá)到收斂是一個(gè)重要的問(wèn)題。對(duì)于應(yīng)用目的來(lái)說(shuō)，這一問(wèn)題變?yōu)楹螘r(shí)可以停止生成新的字符串代。一個(gè)普遍的同時(shí)也由實(shí)踐證明的標(biāo)準(zhǔn)表示當(dāng)連續(xù)幾代中的最大適合度都沒(méi)有實(shí)質(zhì)性提高時(shí)，就可以考慮停止算法了。 152到此為止我們都還沒(méi)有討論如何創(chuàng)建初始代，通常初始代包含大量字符串，具體數(shù)目根據(jù)應(yīng)用問(wèn)題而定。假定已知字符集和字符串長(zhǎng)度，則可以隨機(jī)生成初始代。153若已知一些關(guān)于解的先驗(yàn)知識(shí)（可能的局部字符模式，字符在字符串中出現(xiàn)的概率，等等），則可以利用這些信息生成初始代，令適合度盡可能地大。初始代越好，搜索最優(yōu)的過(guò)程將越快、越簡(jiǎn)單。154算法：遺傳算法創(chuàng)建字符串編碼的初始代，計(jì)算它們的目標(biāo)函數(shù)值。

41、以概率方式將具有較高適合度的字符串復(fù)制到新一代中，淘汰適合度較低的串（復(fù)制）。組合從上一代拷貝來(lái)的字符串編碼，構(gòu)造新的串（交叉）。155偶爾隨機(jī)地改變一些字符串中的某個(gè)字符（突變）。根據(jù)當(dāng)前代中字符串的目標(biāo)函數(shù)值（適合度）對(duì)它們進(jìn)行排序。156若最大字符串適合度在連續(xù)的幾代中都沒(méi)有明顯增加，則停止。q當(dāng)前具有最大適合度的串即表示所求最優(yōu)解。否則，跳到第2步。157模擬退火代表了另一類(lèi)魯棒的優(yōu)化方法。與遺傳算法相同，模擬退火也對(duì)表示復(fù)雜系統(tǒng)好壞的目標(biāo)函數(shù)（代價(jià)函數(shù)）進(jìn)行最小值搜索。 模擬退火不保證找到全局最優(yōu)解，但通常可以得到近似最優(yōu)解。 158模擬退火綜合了兩個(gè)基本的優(yōu)化原理，分而治之和迭代改

42、進(jìn)（爬山算法）。這樣結(jié)合使用可以避免停止在局部最優(yōu)上。統(tǒng)計(jì)力學(xué)和熱力學(xué)之間的密切關(guān)系和多元或組合優(yōu)化是退火優(yōu)化的基礎(chǔ)。 159在統(tǒng)計(jì)力學(xué)中，實(shí)驗(yàn)只觀察到特定溫度下系統(tǒng)熱平衡時(shí)最可能的狀態(tài)改變，每個(gè)狀態(tài)都由系統(tǒng)的原子位置集合x(chóng)i定義，并用Boltzmann常數(shù)概率因子賦給權(quán)值， TkxEBiexp160其 中 E ( xi) ) 為 狀 態(tài) 的 能 量 ， kB是Boltzmann常數(shù)，T是溫度。Boltzmann概率密度的一個(gè)主要特點(diǎn)是在溫度很高時(shí)，所有的狀態(tài)幾乎有同樣的可能性成為下一個(gè)狀態(tài)，但在溫度較低時(shí)具有低能量的狀態(tài)更有可能成為新的狀態(tài)。 161優(yōu)化可以比喻為物質(zhì)形成晶體結(jié)構(gòu)的能力，若物

43、質(zhì)被熔化后再以很慢的速度冷卻的話(huà)，晶體結(jié)構(gòu)將是能量最小的狀態(tài)。這一最小值可以看作是能量函數(shù)的優(yōu)化最小值，而能量函數(shù)的作用與目標(biāo)函數(shù)相同。162結(jié)晶過(guò)程依賴(lài)于冷卻熔化液體的速度，若冷卻速度太快，則晶體將包含許多局部瑕疵，因此也就沒(méi)達(dá)到全局最小能量。模擬退火由迭代的下山步驟和有控制的上山步驟組成，使得它有可能跳出局部極小點(diǎn)。 163上山步驟使得它可以跳出局部極小點(diǎn)；虛線表示可能的收斂路經(jīng) 164這一過(guò)程的物理模型為，對(duì)物質(zhì)加熱直至熔化，然后將熔液在保持準(zhǔn)熱平衡的條件下慢慢冷卻。冷卻算法包括反復(fù)隨機(jī)地替換物質(zhì)中的原子（狀態(tài)改變），及每次狀態(tài)改變后計(jì)算能量的改變E。165若E0（更低的能量），則狀態(tài)改

44、變被接受，新?tīng)顟B(tài)作為下一輪步驟的起始狀態(tài)。若E0，則狀態(tài)以如下概率被接受： TkEEPBexp166為了將這個(gè)物理模型應(yīng)用于優(yōu)化問(wèn)題，應(yīng)該在優(yōu)化過(guò)程中將溫度參數(shù)T以可控制的方式降低。算法的隨機(jī)部分可以通過(guò)生成在(0,1)上滿(mǎn)足平均分布的隨機(jī)數(shù)實(shí)現(xiàn)，選擇這樣一個(gè)隨機(jī)數(shù)并與P(E)進(jìn)行比較。 167算法：模擬退火優(yōu)化 令x為優(yōu)化參數(shù)的向量，計(jì)算目標(biāo)函數(shù)J(x)的值。將第3步和第4步重復(fù)n(T)次。對(duì)參數(shù)向量x做輕微擾動(dòng)，得到新向量xnew，計(jì)算新的優(yōu)化函數(shù)值J(xnew)。168生成一個(gè)隨機(jī)數(shù)r(0,1)，滿(mǎn)足區(qū)間(0, 1)上的平均分布。若 則令x=xnew且J(x)=J(xnew) 。TKxJ

45、xJrBnew)()(exp169重復(fù)第2步和第4步直到滿(mǎn)足收斂標(biāo)準(zhǔn)。這時(shí)參數(shù)向量x表示優(yōu)化問(wèn)題的解。 170注意，事先并不知道需要多少次迭代步驟，怎樣的參數(shù)擾動(dòng)（狀態(tài)改變），選擇什么溫度T，采用多快的冷卻速度才能得到最好（或僅僅是較好）的結(jié)果。雖然有一些一般性的原則可供參考，但對(duì)于特定的問(wèn)題有特定的合適的參數(shù)。 171目前只知道對(duì)任一溫度來(lái)說(shuō)，退火過(guò)程都應(yīng)該用足夠長(zhǎng)的時(shí)間來(lái)達(dá)到穩(wěn)定狀態(tài)。溫度序列和每個(gè)溫度達(dá)到熱平衡所需的迭代步數(shù)n稱(chēng)為退火進(jìn)度。172較大的迭代步數(shù)n和較小的溫度T變化步長(zhǎng)可以產(chǎn)生的最終優(yōu)化函數(shù)值也更低（解更接近于全局最?。?，但需要較長(zhǎng)的計(jì)算時(shí)間。 較小的迭代步數(shù)n和較大的溫度

46、T變化步長(zhǎng)可以更快結(jié)束，但結(jié)果也可能離全局最小比較遠(yuǎn)。173因此需要仔細(xì)設(shè)置T和n的值，使得在可以接受的時(shí)間內(nèi)得到比較接近全局最小的解。然而目前還沒(méi)有設(shè)計(jì)出退火進(jìn)度的實(shí)用方法。 很多應(yīng)用問(wèn)題都用到退火算法，如模式識(shí)別、圖的分割等，退火算法有著極大的實(shí)用價(jià)值。174175模糊系統(tǒng)可以表示多變的、不精確的、不確定的和不準(zhǔn)確的知識(shí)或信息。同人類(lèi)表達(dá)知識(shí)的方式類(lèi)似，模糊系統(tǒng)采用修飾語(yǔ)，如明亮的、比較暗的、暗的，等等。176模糊系統(tǒng)可以表示復(fù)雜的知識(shí)，甚至是來(lái)源矛盾的知識(shí)。模糊系統(tǒng)基于模糊邏輯，后者代表了一類(lèi)強(qiáng)大的決策方法。177 人描述物體時(shí)通常會(huì)采用不精確的描述，如明亮的、巨大的、圓形的、長(zhǎng)條的，等

47、等。 模糊邏輯使得同一區(qū)域可以同時(shí)屬于不同的模糊集合。 178模糊空間X中的一個(gè)模糊集合S為一個(gè)有序?qū)Φ募希?其中S(x)表示x在集合S中的隸屬程度。通常模糊集合僅用其隸屬函數(shù)表示。XxxxSS|)(,179下圖中所示對(duì)暗色區(qū)域的描述是一個(gè)經(jīng)典的模糊集合的例子，體現(xiàn)了模糊空間的性質(zhì)。 模糊集合的定義域畫(huà)在x軸上，取值從黑到白（0255）。垂直坐標(biāo)軸表示隸屬度(x)。隸屬度可以取0到1間的值，0表示不屬于，l表示完全屬于。180一塊平均灰度值為255的白色區(qū)域關(guān)于模糊集合DARK的隸屬度為0，而一塊黑色區(qū)域（平均灰度值為0）關(guān)于模糊集合DARK具有完全隸屬度。隸屬度函數(shù)可以是線性的，見(jiàn)圖b。也

48、可以采用其它形式的曲線（見(jiàn)圖c和圖d）。181 精確集合表達(dá)了集合DARK的布爾性質(zhì)；模糊集合DARK；與模糊集合DARK相關(guān)的另一種可能的隸屬函數(shù)；再一種隸屬函數(shù)。 182考慮晴天云和積雨云的平均灰度值，下圖畫(huà)出了可能與模糊集合DARK、MEDIUM_DARK和BRIGHT相關(guān)的隸屬函數(shù)。模糊集合的最大隸屬度取值稱(chēng)為模糊集合的高度。183一個(gè)具有特定平均灰度值g的區(qū)域可能同時(shí)屬于多個(gè)模糊集合。隸屬度DARK(g)，MEDIUM-DARK(g)和BRIGHT(g)表示了描述的模糊性。因?yàn)樗鼈児烙?jì)了區(qū)域?qū)儆谔囟：系拇_定程度。184 與模糊集合DARK、MEDIUM_DARK和BRIGHT相

49、關(guān)的隸屬函數(shù)。注意可能有幾個(gè)隸屬度取值與同一特定平均灰度值g相關(guān)聯(lián)。 185在模糊系統(tǒng)的設(shè)計(jì)中采用規(guī)一化的隸屬函數(shù)。最小正規(guī)形式要求在模糊集合的定義域中至少有一個(gè)元素的隸屬度為1。最大正規(guī)形式是定義域中至少有一個(gè)元素的隸屬度為0的最小正規(guī)形式。 186在模糊推理系統(tǒng)中，模糊隸屬函數(shù)通常被設(shè)計(jì)為最小正規(guī)形式。 模糊隸屬函數(shù)的形狀可以通過(guò)模糊集合限制進(jìn)行調(diào)整。限制可以對(duì)模糊集合中元素的隸屬度進(jìn)行加強(qiáng)、減緩、求補(bǔ)、精細(xì)或大體上近似，等等。187 模糊集合VERY_DARK。模糊集合SOMEWHAT_DARK。模糊集合NOT_VERY_DARK188 很少有某個(gè)識(shí)別問(wèn)題可以?xún)H僅用一個(gè)模糊集合及其隸屬函

50、數(shù)就能解決。因此，需要有一個(gè)工具能夠?qū)⒉煌：辖Y(jié)合起求，并確定這種聯(lián)合后的隸屬度。 189對(duì)于模糊集合有三個(gè)基本運(yùn)算：模糊交、模糊并和模糊補(bǔ)。令A(yù)(x)和B(y)為兩個(gè)隸屬函數(shù)，分別與模糊集合A和B相關(guān)，這兩個(gè)集合的定義域分別為X和Y。于是對(duì)所有xX，yY，交、并和補(bǔ)逐點(diǎn)定義為 ： 190注意，模糊集合運(yùn)算可以同限制相結(jié)合，從而構(gòu)造新的模糊集合。 )(),(min,:yxyxBABABA交)(),(max,:yxyxBABABA并)(1)(:xxAACAC補(bǔ)191在模糊推理中，將一些含有信息的單個(gè)模糊集合結(jié)合起來(lái)做出決策。決定相關(guān)模糊隸屬度的函數(shù)關(guān)系被稱(chēng)為合成方法（混合辦法），并且定義了模

51、糊解空間。192為了做出決策，采用一個(gè)逆模糊（分解）過(guò)程確定模糊解空間和決策間的函數(shù)關(guān)系。合成和逆模糊過(guò)程構(gòu)成了模糊推理的基礎(chǔ)。193限制模糊規(guī)則模糊變量解空間模糊合成決策逆模糊194模糊模型使用了一系列無(wú)條件和有條件的命題，稱(chēng)為模糊規(guī)則。無(wú)條件模糊規(guī)則的形式為：x是A有條件模糊規(guī)則的形式為： if x 是 A then w 是 B1.其中A和B是語(yǔ)言變量，z和w表示分別屬于各自定義域的標(biāo)量。195與一個(gè)無(wú)條件規(guī)則相關(guān)聯(lián)的隸屬度就是A(x)。無(wú)條件模糊命題用于限制解空間，或定義默認(rèn)解空間。由于這些規(guī)則是無(wú)條件的，因此采用模糊集運(yùn)算可以直接將它們作用于解空間。考慮條件模糊規(guī)則，有幾種方法可以對(duì)其

52、做出決策。196單調(diào)模糊推理是其中最簡(jiǎn)單的一種，不用合成及逆模糊就可以生成解。 令x為表示描述云彩暗度的一個(gè)標(biāo)量灰度值，w表示雷雨的激烈程度。則下列模糊規(guī)則可以表達(dá)我們關(guān)于雷雨激烈程度的知識(shí)。if x是DARK then w是SEVERE197根據(jù)對(duì)云彩灰度的判斷（在例子中x=80），確定隸屬度DARK(80)=0.35。這個(gè)值就表示隸屬度SEVERE(w)=DARK(x)，據(jù)此可以對(duì)雷雨激烈程度做出判斷。 在如下例子中w=4.8，其定義域?yàn)?到10。198基于一條模糊規(guī)則的單調(diào)模糊推理：若云的灰度值為DARK，則雷雨為SEVERE199這個(gè)方法同樣適用于具有如下形式的復(fù)雜的斷言：if (x是

53、A)(y是B) (u是F) then w是Z其中表示合取AND或析取OR運(yùn)算?？梢越Y(jié)合模糊交和模糊并來(lái)實(shí)現(xiàn)復(fù)雜斷言，AND對(duì)應(yīng)模糊交，OR對(duì)應(yīng)模糊并。 200單調(diào)方法體現(xiàn)了模糊推理的根本概念，但它只能用于由一條模糊規(guī)則控制的單個(gè)單調(diào)模糊變量（可能還有一個(gè)復(fù)雜斷言）。當(dāng)謂詞命題的復(fù)雜度增加時(shí)，判斷的合理性會(huì)有所下降 。 201為完成決策過(guò)程所需的知識(shí)通常包含在若干條模糊規(guī)則中。許多模糊規(guī)則將參與到?jīng)Q策過(guò)程中，并且所有決策規(guī)則將在這一過(guò)程中被平行地激活。202顯然，不是所有模糊規(guī)則對(duì)最終解都有同樣的貢獻(xiàn)，前提根本就不會(huì)成立的那些規(guī)則對(duì)結(jié)果就不會(huì)有任何影響。有幾條合成機(jī)制來(lái)幫助我們進(jìn)行規(guī)則組合，在此

54、將討論其中一種最常用的方法，稱(chēng)為最小最大規(guī)則。203最小最大規(guī)則在最小最大合成方法中，采用一系列最小化和最大化操作。首先，采用謂詞真值的最小化（相關(guān)性最小化）Ai(x)約束結(jié)果模糊隸屬函數(shù)Bi(w)。令規(guī)則具有如下的形式，i表示第i條規(guī)則。 if x 是 A then w 是 B204于是，結(jié)果模糊隸屬函數(shù)B，逐點(diǎn)地被更新，形成新的模糊隸屬函數(shù)Bi+。2.由這些最小化后的模糊集合的逐點(diǎn)最大值構(gòu)造解模糊隸屬函數(shù)。 )(),(min)(xwwiiiABBmax)(wwiBiS205 206上面所介紹的相關(guān)最小化是最常采用的用來(lái)完成最小最大合成第一步的方法。另一種可選的方法稱(chēng)為相關(guān)乘積，這種方法對(duì)原

55、結(jié)果模糊隸屬函數(shù)乘一個(gè)尺度因子，而不是對(duì)其進(jìn)行截?cái)嗖僮鳌?07相關(guān)最小化只需要較少的計(jì)算量并且容易被逆模糊。而相關(guān)乘積在很多方面都代表了一種更好的最小化方法，因?yàn)槟：系脑行螤顩](méi)有被改變。208 209模糊合成對(duì)每一個(gè)解變量生成一個(gè)解模糊隸屬函數(shù)。為了找到用于做出決策的真正的準(zhǔn)確解，需要先找到一個(gè)最佳表示了解模糊集合中信息的標(biāo)量向量（每個(gè)標(biāo)量分量對(duì)應(yīng)一個(gè)解變量）。這一過(guò)程對(duì)每個(gè)解變量獨(dú)立地進(jìn)行，稱(chēng)為逆模糊。 210常用的逆模糊方法有兩種，分別稱(chēng)為力矩合成和最大值合成，此外還有許多其它方法。力矩合成尋找解模糊隸屬函數(shù)的質(zhì)心c下圖a演示了質(zhì)心方法如何將解模糊隸屬函數(shù)轉(zhuǎn)換為明確解變量c。 211

56、最大值合成將定義域點(diǎn)等同于取到解模糊隸屬函數(shù)最大隸屬度值的那一點(diǎn)。若這一點(diǎn)不確定（在一個(gè)平臺(tái)上或存在幾個(gè)相同的全局最大值點(diǎn)），則平臺(tái)的中心（或最左和最右全局最大值點(diǎn)的中點(diǎn)）將作為明確解c，參見(jiàn)下圖b。 212由力矩合成產(chǎn)生的結(jié)果對(duì)所有規(guī)則都敏感，而最大值合成方法確定的解只對(duì)有最高斷言真值的那條規(guī)則生成的隸屬函數(shù)敏感。力矩合成大多用在控制應(yīng)用中，而最大值合成則用于識(shí)別應(yīng)用中。 213 (a) 力矩合成 (b) 最大值合成214 模糊系統(tǒng)設(shè)計(jì)主要由如下算法中的幾個(gè)步驟組成。 215算法：模糊系統(tǒng)設(shè)計(jì)設(shè)計(jì)系統(tǒng)的功能和運(yùn)轉(zhuǎn)特性確定系統(tǒng)輸入、基本處理方法、系統(tǒng)輸出。在物體識(shí)別中，輸入為模式，輸出表示判定。 通過(guò)將模糊系統(tǒng)的輸入和輸出分解為一個(gè)模糊隸屬函數(shù)的集合，定義模糊集。216q與每個(gè)變量相關(guān)聯(lián)的模糊隸屬函數(shù)數(shù)目依賴(lài)于具體問(wèn)題。q通常每個(gè)變量關(guān)聯(lián)的模糊隸屬函數(shù)總數(shù)為3到9間的一個(gè)奇數(shù)。q建議相鄰模糊隸屬函數(shù)相互重疊l050。重疊部分的隸屬度總和最好小于1。 217將特定問(wèn)題的知識(shí)轉(zhuǎn)變?yōu)閕f-then形式的模糊規(guī)則，這些規(guī)則代表了模糊聯(lián)想記憶。q規(guī)則的數(shù)目與輸入變量的數(shù)目有關(guān)。對(duì)于分到M個(gè)模糊隸屬函數(shù)的N個(gè)變量來(lái)說(shuō)，需要MN條規(guī)則來(lái)覆蓋所有可能的輸入組合