【文章內(nèi)容簡介】 e(KL)變換。 PCA方法的核心過程是計算特征值和特征向量，有很多不同的數(shù)值計算方法。一種常采用的方法是根據(jù)如下的推導(dǎo) : TXC AA? (N N維 ) 其中 ? ?1,sA d K d? 考慮 TAA (s s 維 )的特征向量 iv T i i iA Av v?? （ 311） 上式兩邊左乘 A得到 T i i iAA Av Av?μ （ 312） 可見 iAv 就是 TXC AA? 的特征向量。 由于通常 SN，這種方法將求高階矩陣的特征向量轉(zhuǎn)化為求較低階矩陣的特征向量的過程在圖象數(shù)據(jù)分析中是很實用的。 PCA 方法提取車型特征 KL 變換是一種最優(yōu)正交變換 [9]，是圖象分析與模式識別中的重要工具，人們將其應(yīng)用于特征提取，降低特征數(shù)據(jù)的維數(shù)。形成了子空間法模式識別的基礎(chǔ)，本文將它應(yīng)用于車型識別。 該方法以歸一化的標(biāo)準(zhǔn)圖像作為訓(xùn)練樣本集，以該樣本集的總體散布矩陣為產(chǎn)生矩陣，即 : {( )( ) }Tx u x? ? ?? μ (313) 或 1 T01 ( ) ( )M iii xxM??? ? ??? μ μ (314) 其中： ix 為第 i個訓(xùn)練樣本的圖像向量， ? 訓(xùn)練樣本集的平均圖向量， M 為訓(xùn)練樣本的總數(shù)。 將∑表示為 1 T011( ) ( )M Tiii x x X XMM??? ? ? ??? μ μ (315) 其中 0 1 1[] MX x x x ?? μ , μ , . . . μ 構(gòu)造矩陣： TR X X? 容易求出矩陣 R的特征值 i? 及相應(yīng)的正交歸一特征向量 ( 0,1, 2, , 1)iv i M??從而易得∑的正交歸一特征向量 iu 為 第 9 頁 共 22 頁 iii?１ｕ ＝ Ｘ ｖ 1,2,1,0 ?? Mi ? （ 317） 這就是圖像的特征向量。 我們總共得到了 M 個特征向量。雖然 M 比 2N 小很多，但通常情況下， M 仍然會太大。而事實上，根據(jù)應(yīng)用的要求，并非所有的 iu 都有很大的保留意義。 考慮到使用 KL 變換作為對車輛圖像的壓縮手段，可以選取最大的前 k 個特征向量，使得 : 010kiifii?????????? （ 318） 在上式中，我們選取 a=98%。這說明樣本集在前 k 個軸上的能量占整個能量的 98%以上。 這樣每一幅車輛圖像都可以投影到由 0 1 1, , , Mu u u ? 張成的子空間中。因此每幅車輛圖像對應(yīng)于子空間中的一個點。同樣，子空間中的任一點也對應(yīng)于一幅圖像一一特征車 (圖 31顯示的是 01,uu所對應(yīng)的圖像 )。 圖 31“特征車”圖像 有了這樣一個由“特征車”張成的降維子空間，任何一幅車輛圖像都可以向其做投影并獲得一組坐標(biāo)系數(shù)，這組系數(shù)表明了該圖像在子空間中的位置，就是我們用 PCA方法提取出來的車型特征。 4 基于支持向量機的車型識別分類器 訓(xùn)練方法和分類算法是分類系 統(tǒng)的核心部分，目前存在多種基于向量空間模型的訓(xùn)練算法和分 第 10 頁 共 22 頁 類算法，例如，最近 K 近鄰方法、神經(jīng)網(wǎng)絡(luò)方法和支持向量機算法等等。 KNN(K 最近鄰 )算法 該算法的基本思路是：在給定新樣本后，考慮在訓(xùn)練樣本集中與該新樣本距離最近 (最相似 )的K 個樣本，根據(jù)這 K 個樣本所屬的類別判定新樣本所屬的類別，具體的算法步驟如下： 第一步：根據(jù)特征項集合重新描述訓(xùn)練樣本向量 第二步：在新樣本到達(dá)后，確定新樣本的向量表示 第三步：在訓(xùn)練樣本集中選出與新樣本最相似的 K 個樣本 第四步：在新樣本的 K 個鄰居中，依次計算每類的權(quán)重，計算公 式如下： ( , ) ( , ) ( , )ij i i jd K N Np x C S im x d y d C?? ?rrrrr 其中， xr 為新樣本的特征向量， ( , )iSimxdrr 為相似度計算公式，與上一步驟的計算公式相同，而( , )ijydCr 為類別屬性函數(shù)，即，如果 idr 屬于類 jC 那么函數(shù)值為 1，否則為 0。 第五步：比較類的權(quán)重，將樣本分到權(quán)重最大的那個 類別中。 神經(jīng)網(wǎng)絡(luò)算法 神經(jīng)網(wǎng)絡(luò)算法采用感知算法進(jìn)行分類。在這種模型中，分類知識被隱式地存儲在連接的權(quán)值上，使用迭代算法來確定權(quán)值向量。當(dāng)網(wǎng)絡(luò)輸出判別正確時，權(quán)值向量保持不變，否則進(jìn)行增加或降低的調(diào)整，因此也稱為獎懲法。傳統(tǒng)神經(jīng)網(wǎng)絡(luò)如 BP 算法存在以下缺點 :存在局部極小問題，學(xué)習(xí)算法收斂速度慢。 支持向量機 支持向量機的基本思想是使用簡單的線性分類器劃分樣本空間。對于在當(dāng)前特征空間中線性不可分的模式，則使用一個核函數(shù)把樣本映射到一個高維空間中，使得樣本能夠線性可分。 支持向量機 (Support Vector Machine， SVM)起源于統(tǒng)計學(xué)習(xí)理論，它研究如何構(gòu)造學(xué)習(xí)機，實現(xiàn)模式分類問題。由于支持向量機方法有幾個主要優(yōu)點： ，其目標(biāo)是得到現(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)計學(xué)習(xí)理論為人們系統(tǒng)研究有限樣本情況下機器學(xué)習(xí)問題提供了有力的理論基礎(chǔ)，本文采用了支持向量機分類算法進(jìn)行車型識別。 支持向量機 統(tǒng)計學(xué)在解決機器學(xué)習(xí)問題中起著基礎(chǔ)性的作用。但是，傳統(tǒng)的統(tǒng)計學(xué)所研究的主要是漸近理論，即當(dā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ò)過學(xué)習(xí)問題就是一個典型的代表 :當(dāng)樣本數(shù)有限時，本來很不錯的一個學(xué)習(xí)機器卻可能表現(xiàn)出很差的推廣能力。 人們對于解決此類問題的努力實際上一直在進(jìn)行。但是，其中多數(shù)工作集中在對己有 (基于傳統(tǒng)統(tǒng)計學(xué)原則的 )方法的改進(jìn)和修正，或者利用啟發(fā)式方法設(shè)計某些巧妙的算法。在人類即將邁進(jìn)一個新世紀(jì)的時候，人們開始逐漸頻繁地接觸到一個詞，就是“統(tǒng)計學(xué)習(xí)理論”。這實際上是早在 20 世紀(jì) 70 年代就已經(jīng)建立了其基本體系 的一門理論，它系統(tǒng)地研究了機器學(xué)習(xí)的問題，尤其是有限樣本情況下的統(tǒng)計學(xué)習(xí)問題。 在 90 年代，這一理論框架下產(chǎn)生出了“支持向量機 (SVM)”這一新的通用機器學(xué)習(xí)方法?；蛟S是由于統(tǒng)計學(xué)習(xí)理論為人們系統(tǒng)研究有限樣本情況下機器學(xué)習(xí)問題提供了有力的理論基礎(chǔ)，或許更是因為在這一基礎(chǔ)上的支持向量機方法所表現(xiàn)出的令人向往的優(yōu)良特性，人們開始迅速重視起這一早在 20 年前就該重視的學(xué)術(shù)方向。 現(xiàn)在，越來越多的學(xué)者認(rèn)為，關(guān)于統(tǒng)計學(xué)習(xí)理論和支持向量機的研究，將很快出現(xiàn)像在 80年代后期人工神經(jīng)網(wǎng)絡(luò)研究那樣的飛速發(fā)展階段。然而，所不同的 是，統(tǒng)計學(xué)習(xí)理論有完備的理論基礎(chǔ) 第 11 頁 共 22 頁 和嚴(yán)格的理論體系 (相比之下神經(jīng)網(wǎng)絡(luò)有更多的啟發(fā)式成分 )，而且其出發(fā)點是更符合實際情況的有限樣本假設(shè)。 支持向量機使用結(jié)構(gòu)風(fēng)險最小化 (Structural Risk Minimization， SRM 準(zhǔn)則 )原理構(gòu)造決策超平面使每一類數(shù)據(jù)之間的分類間隔 (Margin)最大。 SRM 準(zhǔn)則認(rèn)為 :學(xué)習(xí)機對未知數(shù)據(jù)分類所產(chǎn)生的實際風(fēng)險是由兩部分組成的，以 0η 1滿足如下關(guān)系： ( l o g ( 2 / ) 1 ) l o g ( / 4 )e m p h n hRR n ?????，其中，R 是實際風(fēng)險，不等式的右邊叫做風(fēng)險邊界， empR 稱為經(jīng)驗風(fēng)險， (lo g (2 / ) 1) lo g ( / 4 )h n hn ???叫做“ VC置信值”， n 是訓(xùn)練樣本個數(shù)， h 是學(xué)習(xí)機的 VC 維 (h 反映了學(xué)習(xí)機的復(fù)雜程度 )。 SVM 的思想就是在樣本數(shù)目適宜的前提下，選取比較好的 VC 維 h，使經(jīng)驗風(fēng)險 empR 和置信值達(dá)到一個折中，使每一類別數(shù)據(jù)之間的分類間隔 (Margin)最大，最終使實際風(fēng)險 R 變小。 支持向量機的討論是從最簡單的模式識別問題開始，即用超平面進(jìn)行二分類的 問題。 先考慮兩類線性可分情況。設(shè) 12, , , nX X X 其中 , 1, ,diX R i n?? ， n 是 n 個 d 維訓(xùn)練樣本，每個樣本對應(yīng)的標(biāo)一記為 12, , , ny y y ，其中 ? ?1, 1 , 1, ,iy i n? ? ? 標(biāo)明該向量屬于兩類中的哪一類。若超平面 Tw x+b? 能將訓(xùn)練樣本分開，則有： Tw x + b 0 y 1i??若 (42) Tw x + b 0 y 1i? ? ?若 (43) 適當(dāng)調(diào)整 w 和 b 進(jìn)行歸一化，可將上兩式改寫成 Tw x + b 1 y 1i? ? ?若 (44) Tw x+ b 1 y 1i? ? ? ?若 (45) 或者 T(w x + b ) 1 , i= 1 ,2 , ,n?? (46) 圖 41 如圖所示，如果兩類是線性可分的，則將有無限多個分類面可以把這個兩類問題進(jìn)行分類。我們的目標(biāo)是選擇其中最優(yōu)的那個分類面 (如圖 41 所示 )。 H 為把兩類沒有錯誤地分開的分類線， Hl， H2 分別為過各類樣本中離分類線最近的點且平行于分類線的直線， HI 和 H2 之間的距離叫做兩類的分類空隙或分類間隔 (margin)。所謂最優(yōu)分類線就是要求分類線不但能將兩類無錯誤地分開，而 且要使兩類的分類空隙最大。前者是保證經(jīng)驗風(fēng)險最小(為 0)，而使分類空隙最大實際上就是使推廣性的界中的置信范圍最小，從而使真實風(fēng)險最小。推廣到高維空間，最優(yōu)分類線就成為最優(yōu)分類面。 對于上述 d 維線性可分樣本集為 ( x ,y ) ,i = 1 , ,n ,x R , y ( + 1 , 1 )dii ??是類別標(biāo)號。線性判別函數(shù)的一般形式為 g(x)=w x+b，分類面方程為 :w x+b=0 將判別函數(shù)進(jìn)行歸一化后，兩類所有樣本都滿足 ( ) 1gx? ， (即使離分類面最近的樣本的 ( ) 1gx? )，這樣分類間隔就為： ? ? ? ?1 1 1 1 2m in m a xii iiiixy xyw x b w x bw w w w w? ?? ? ? ? ?? ? ? ? （ 47） 第 12 頁 共 22 頁 因此使間隔最大等價于使 w （或 2w ）最?。欢蠓诸惥€對所有樣本正確分類，就是要求它滿足 ( ) 1 , 1 , 2 , ,iiy w x b i n? ? ? ? （ 48） 因此，滿足上述條件且 2w 最小的分類面就是最優(yōu)分類面。過兩類樣本中離分類面最近的點且平行于最優(yōu)分類面的超平面 Hl、 H2 上的訓(xùn)練樣本就是式 48中使等號成立的那些樣本，它們叫做支持向量 (Support Vectors)。因為它們支撐了最優(yōu)分類面。如圖中用 *標(biāo)出的點所示。 那么具體如何求最優(yōu)分類面呢 ?如上所述易知，最優(yōu)分類面問題可以表示成如下的約束優(yōu)化問題，即在條件 (48)的約束下，求函數(shù) 211( ) ( )22w w w w? ? ? ? (49) 的最小值。為此，我們定義拉格朗日函數(shù)如下： ? ??