【文章內(nèi)容簡(jiǎn)介】 Tiiv?上式兩邊左乘 A 得到 （312）iiA?μ可見(jiàn) 就是 的特征向量。ivTXC?由于通常 SN，這種方法將求高階矩陣的特征向量轉(zhuǎn)化為求較低階矩陣的特征向量的過(guò)程在圖象數(shù)據(jù)分析中是很實(shí)用的。 PCA 方法提取車型特征KL 變換是一種最優(yōu)正交變換 [9]，是圖象分析與模式識(shí)別中的重要工具，人們將其應(yīng)用于特征提取，降低特征數(shù)據(jù)的維數(shù)。形成了子空間法模式識(shí)別的基礎(chǔ)，本文將它應(yīng)用于車型識(shí)別。該方法以歸一化的標(biāo)準(zhǔn)圖像作為訓(xùn)練樣本集，以該樣本集的總體散布矩陣為產(chǎn)生矩陣，即: (313){()}Txu???μ或 (314)10)Miii?μ μ其中： 為第 i 個(gè)訓(xùn)練樣本的圖像向量， 訓(xùn)練樣本集的平均圖向量，M 為訓(xùn)練樣本的總數(shù)。ix?將∑表示為 (315)1T01()TiiixX???μ μ其中 011[ ]MXx?μ ,μ ,.μ構(gòu)造矩陣： TR容易求出矩陣 R 的特征值 及相應(yīng)的正交歸一特征向量 從而易得∑的正交i?(0,2)ivM??歸一特征向量 為iu 第 9 頁(yè) 共 22 頁(yè) （317）ii?１ｕ ＝ Ｘ ｖ 1,20??Mi?這就是圖像的特征向量。我們總共得到了 M 個(gè)特征向量。雖然 M 比 小很多，但通常情況下， M 仍然會(huì)太大。而事實(shí)N上，根據(jù)應(yīng)用的要求，并非所有的 都有很大的保留意義。iu考慮到使用 KL 變換作為對(duì)車輛圖像的壓縮手段，可以選取最大的前 k 個(gè)特征向量，使得: （318）01kiifii??????在上式中，我們選取 a=98%。這說(shuō)明樣本集在前 k 個(gè)軸上的能量占整個(gè)能量的 98%以上。這樣每一幅車輛圖像都可以投影到由 張成的子空間中。因此每幅車輛圖像對(duì)應(yīng)于01,Mu??子空間中的一個(gè)點(diǎn)。同樣，子空間中的任一點(diǎn)也對(duì)應(yīng)于一幅圖像一一特征車(圖 31 顯示的是所對(duì)應(yīng)的圖像) 。01,u?圖 31“特征車”圖像有了這樣一個(gè)由“特征車”張成的降維子空間，任何一幅車輛圖像都可以向其做投影并獲得一組坐標(biāo)系數(shù)，這組系數(shù)表明了該圖像在子空間中的位置，就是我們用 PCA 方法提取出來(lái)的車型特征。 第 10 頁(yè) 共 22 頁(yè)4 基于支持向量機(jī)的車型識(shí)別分類器 現(xiàn)有的幾種分類方法訓(xùn)練方法和分類算法是分類系統(tǒng)的核心部分，目前存在多種基于向量空間模型的訓(xùn)練算法和分類算法，例如，最近 K 近鄰方法、神經(jīng)網(wǎng)絡(luò)方法和支持向量機(jī)算法等等。KNN(K 最近鄰) 算法該算法的基本思路是：在給定新樣本后，考慮在訓(xùn)練樣本集中與該新樣本距離最近 (最相似)的 K 個(gè)樣本，根據(jù)這 K 個(gè)樣本所屬的類別判定新樣本所屬的類別，具體的算法步驟如下：第一步：根據(jù)特征項(xiàng)集合重新描述訓(xùn)練樣本向量第二步：在新樣本到達(dá)后，確定新樣本的向量表示第三步：在訓(xùn)練樣本集中選出與新樣本最相似的 K 個(gè)樣本第四步：在新樣本的 K 個(gè)鄰居中，依次計(jì)算每類的權(quán)重，計(jì)算公式如下： (,)(,),)ij iijdKNpxCSmxdyC???rrr其中， 為新樣本的特征向量， 為相似度計(jì)算公式，與上一步驟的計(jì)算公式相同，xr ,iS而 為類別屬性函數(shù)，即，如果 屬于類 那么函數(shù)值為 1，否則為 0。(,)ijydCij第五步：比較類的權(quán)重，將樣本分到權(quán)重最大的那個(gè)類別中。神經(jīng)網(wǎng)絡(luò)算法神經(jīng)網(wǎng)絡(luò)算法采用感知算法進(jìn)行分類。在這種模型中，分類知識(shí)被隱式地存儲(chǔ)在連接的權(quán)值上，使用迭代算法來(lái)確定權(quán)值向量。當(dāng)網(wǎng)絡(luò)輸出判別正確時(shí)，權(quán)值向量保持不變，否則進(jìn)行增加或降低的調(diào)整，因此也稱為獎(jiǎng)懲法。傳統(tǒng)神經(jīng)網(wǎng)絡(luò)如 BP 算法存在以下缺點(diǎn) :存在局部極小問(wèn)題，學(xué)習(xí)算法收斂速度慢。支持向量機(jī)支持向量機(jī)的基本思想是使用簡(jiǎn)單的線性分類器劃分樣本空間。對(duì)于在當(dāng)前特征空間中線性不可分的模式，則使用一個(gè)核函數(shù)把樣本映射到一個(gè)高維空間中，使得樣本能夠線性可分。支持向量機(jī)(Support Vector Machine，SVM)起源于統(tǒng)計(jì)學(xué)習(xí)理論，它研究如何構(gòu)造學(xué)習(xí)機(jī)，實(shí)現(xiàn)模式分類問(wèn)題。由于支持向量機(jī)方法有幾個(gè)主要優(yōu)點(diǎn)：，其目標(biāo)是得到現(xiàn)有信息下的最優(yōu)解而不僅僅是樣本數(shù)趨于無(wú)窮大時(shí)的最優(yōu)值。，從理論上說(shuō)，得到的將是全局最優(yōu)點(diǎn)，解決了在神經(jīng)網(wǎng)絡(luò)方法中無(wú)法避免的局部極值問(wèn)題。(Feature Space) ，在高維空間中構(gòu)造線性判別函數(shù)來(lái)實(shí)現(xiàn)原空間中的非線性判別函數(shù)，特殊性質(zhì)能保證機(jī)器有較好的推廣能力，同時(shí)它巧妙地解決了維數(shù)問(wèn)題，其算法復(fù)雜度與樣本維數(shù)無(wú)關(guān)。又由于統(tǒng)計(jì)學(xué)習(xí)理論為人們系統(tǒng)研究有限樣本情況下機(jī)器學(xué)習(xí)問(wèn)題提供了有力的理論基礎(chǔ)，本文采用了支持向量機(jī)分類算法進(jìn)行車型識(shí)別。 支持向量機(jī)統(tǒng)計(jì)學(xué)在解決機(jī)器學(xué)習(xí)問(wèn)題中起著基礎(chǔ)性的作用。但是，傳統(tǒng)的統(tǒng)計(jì)學(xué)所研究的主要是漸近理論，即當(dāng)樣本趨向于無(wú)窮多時(shí)的統(tǒng)計(jì)性質(zhì)。在現(xiàn)實(shí)的問(wèn)題中，我們所面對(duì)的樣本數(shù)目通常是有限的，有時(shí)還十分有限。雖然人們實(shí)際上一直知道這一點(diǎn)，但傳統(tǒng)上仍以樣本數(shù)目無(wú)窮多為假設(shè)來(lái)推導(dǎo)各種算法，希望這樣得到的算法在樣本較少時(shí)也能有較好的( 至少是可接受的) 表現(xiàn)。然而，相反的情況是很容易出現(xiàn)的。其中，近年來(lái)經(jīng)?？梢月?tīng)到人們談?wù)摰乃^神經(jīng)網(wǎng)絡(luò)過(guò)學(xué)習(xí)問(wèn)題就是一個(gè)典型的代表:當(dāng)樣本數(shù)有限時(shí)，本來(lái)很不錯(cuò)的一個(gè)學(xué)習(xí)機(jī)器卻可能表現(xiàn)出很差的推廣能力。人們對(duì)于解決此類問(wèn)題的努力實(shí)際上一直在進(jìn)行。但是，其中多數(shù)工作集中在對(duì)己有(基于傳統(tǒng)統(tǒng)計(jì)學(xué)原則的)方法的改進(jìn)和修正，或者利用啟發(fā)式方法設(shè)計(jì)某些巧妙的算法。在人類即將邁進(jìn)一個(gè)新世紀(jì)的時(shí)候，人們開(kāi)始逐漸頻繁地接觸到一個(gè)詞，就是“統(tǒng)計(jì)學(xué)習(xí)理論” 。這實(shí)際上是早在20 世紀(jì) 70 年代就已經(jīng)建立了其基本體系的一門理論，它系統(tǒng)地研究了機(jī)器學(xué)習(xí)的問(wèn)題，尤其是有限樣本情況下的統(tǒng)計(jì)學(xué)習(xí)問(wèn)題。在 90 年代，這一理論框架下產(chǎn)生出了“支持向量機(jī)(SVM)”這一新的通用機(jī)器學(xué)習(xí)方法?；蛟S是由于統(tǒng)計(jì)學(xué)習(xí)理論為人們系統(tǒng)研究有限樣本情況下機(jī)器學(xué)習(xí)問(wèn)題提供了有力的理論基礎(chǔ)，或許 第 11 頁(yè) 共 22 頁(yè)更是因?yàn)樵谶@一基礎(chǔ)上的支持向量機(jī)方法所表現(xiàn)出的令人向往的優(yōu)良特性，人們開(kāi)始迅速重視起這一早在 20 年前就該重視的學(xué)術(shù)方向?，F(xiàn)在，越來(lái)越多的學(xué)者認(rèn)為，關(guān)于統(tǒng)計(jì)學(xué)習(xí)理論和支持向量機(jī)的研究，將很快出現(xiàn)像在 80 年代后期人工神經(jīng)網(wǎng)絡(luò)研究那樣的飛速發(fā)展階段。然而，所不同的是，統(tǒng)計(jì)學(xué)習(xí)理論有完備的理論基礎(chǔ)和嚴(yán)格的理論體系(相比之下神經(jīng)網(wǎng)絡(luò)有更多的啟發(fā)式成分) ，而且其出發(fā)點(diǎn)是更符合實(shí)際情況的有限樣本假設(shè)。支持向量機(jī)使用結(jié)構(gòu)風(fēng)險(xiǎn)最小化(Structural Risk Minimization，SRM 準(zhǔn)則)原理構(gòu)造決策超平面使每一類數(shù)據(jù)之間的分類間隔(Margin) 最大。SRM 準(zhǔn)則認(rèn)為 :學(xué)習(xí)機(jī)對(duì)未知數(shù)據(jù)分類所產(chǎn)生的實(shí)際風(fēng)險(xiǎn)是由兩部分組成的，以 0η1 滿足如下關(guān)系： ，其(log2/1)log(/4)emphnR?????中，R 是實(shí)際風(fēng)險(xiǎn)，不等式的右邊叫做風(fēng)險(xiǎn)邊界， 稱為經(jīng)驗(yàn)風(fēng)險(xiǎn)， 叫做(l/l/h“VC 置信值” ， n 是訓(xùn)練樣本個(gè)數(shù)，h 是學(xué)習(xí)機(jī)的 VC 維(h 反映了學(xué)習(xí)機(jī)的復(fù)雜程度) 。SVM 的思想就是在樣本數(shù)目適宜的前提下，選取比較好的 VC 維 h，使經(jīng)驗(yàn)風(fēng)險(xiǎn) 和置信值達(dá)到一個(gè)折empR中，使每一類別數(shù)據(jù)之間的分類間隔(Margin) 最大，最終使實(shí)際風(fēng)險(xiǎn) R 變小。 線性支持向量機(jī)支持向量機(jī)的討論是從最簡(jiǎn)單的模式識(shí)別問(wèn)題開(kāi)始，即用超平面進(jìn)行二分類的問(wèn)題。先考慮兩類線性可分情況。設(shè) 其中 ，n 是 n 個(gè) d 維訓(xùn)練樣本，12,nX? ,1,diX???每個(gè)樣本對(duì)應(yīng)的標(biāo)一記為 ，其中 標(biāo)明該向量屬于兩類中的哪一類。若12,ny? ??1,iy??超平面 能將訓(xùn)練樣本分開(kāi)，則有：Twx+b? (42)Twx+b0 i??若 (43)i若適當(dāng)調(diào)整 w 和 b 進(jìn)行歸一化，可將上兩式改寫(xiě)成 (44)T1 yi??若 (45)x+bi???若或者 (46)T(), =,2n??圖 41如圖所示，如果兩類是線性可分的，則將有無(wú)限多個(gè)分類面可以把這個(gè)兩類問(wèn)題進(jìn)行分類。我們的目標(biāo)是選擇其中最優(yōu)的那個(gè)分類面(如圖 41 所示)。H 為把兩類沒(méi)有錯(cuò)誤地分開(kāi)的分類線， Hl，H2 分別為過(guò)各類樣本中離分類線最近的點(diǎn)且平行于分類線的直線，HI 和 H2 之間的距離叫做兩類的分類空隙或分類間隔(margin) 。所謂最優(yōu)分類線就是要求分類線不但能將兩類無(wú)錯(cuò)誤地分開(kāi)，而且要使兩類的分類空隙最大。前者是保證經(jīng)驗(yàn)風(fēng)險(xiǎn)最小( 為 0)，而使分類空隙最大實(shí)際上就是使推廣性的界中的置信范圍最小，從而使真實(shí)風(fēng)險(xiǎn)最小。推廣到高維空間，最優(yōu)分類線就成為最優(yōu)分類面。對(duì)于上述 d 維線性可分樣本集為 是類別標(biāo)號(hào)。線性判別函數(shù)的(x,y)i=1,nxR,y(+1,)di ??一般形式為 g(x)=wx+b，分類面方程為:wx+b=0 第 12 頁(yè) 共 22 頁(yè)將判別函數(shù)進(jìn)行歸一化后，兩類所有樣本都滿足 ，(即使離分類面最近的樣本的 )，)1gx?(1gx?這樣分類間隔就為： （47）????112minaxii ixyywbwbw?????????因此使間隔最大等價(jià)于使 （或 ）最?。欢蠓诸惥€對(duì)所有樣本正確分類，就是要求它2滿足 （48）(),2,iiyxbin????因此，滿足上述條件且 最小的分類面就是最優(yōu)分類面。過(guò)兩類樣本中離分類面最近的點(diǎn)且2w平行于最優(yōu)分類面的超平面 Hl、H2 上的訓(xùn)練樣本就是式 48 中使等號(hào)成立的那些樣本，它們叫做支持向量(Support Vectors)。因?yàn)樗鼈冎瘟俗顑?yōu)分類面。如圖中用*標(biāo)出的點(diǎn)所示。那么具體如何求最優(yōu)分類面呢?如上所述易知，最優(yōu)分類面問(wèn)題可以表示成如下的約束優(yōu)化問(wèn)題，即在條件(48)的約束下，求函數(shù) (49)21()()w???的最小值。為此，我們定義拉格朗日函數(shù)如下： (410)????1(,)() 12niiLbaaywxb???????????其中， 為拉格朗日系數(shù)，我們的問(wèn)題是對(duì) w 和 b 求拉格朗日函數(shù)的極小值。0ia?把式(410) 分別對(duì) w 和 b 求導(dǎo)并令它們等于 0，就可以把原問(wèn)題轉(zhuǎn)化為如下這種較簡(jiǎn)單的對(duì)偶問(wèn)題：在約束條件 （411）1niiya? (412)0,i n??之下對(duì) 求解下列函數(shù)的最大值：ia (413)1,1() ()2nniijijijiijQaayx?????若 為最優(yōu)解，則*i (414)**1niiiwayx?即最優(yōu)分類而的權(quán)系數(shù)向量是訓(xùn)練樣本向量的線性組合。這是一個(gè)不等式約束下二次函數(shù)極值問(wèn)題，存在唯一解。且根據(jù) KuhnTucker 條件，這個(gè)優(yōu)化問(wèn)題的解須滿足 (415)??10,iiayxbin????因此，對(duì)多數(shù)樣本 將為零，取值不為零的 對(duì)應(yīng)于使式 48 等號(hào)成立的樣本即支持向量，*i *ia它們通常只是全體樣本中的很少一部分。將解上述問(wèn)題后得到的最優(yōu)分類函數(shù)是 (416)???????****1sgnsgni