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