【正文】 。 第 13 頁 共 22 頁 由拉格朗日乘數(shù)法，問題等價于在約束條件 1 0niii ya? ?? (419) 0 iaC?? (420) 之下對 ia 求解下列函數(shù)的最大值： ? ? ? ?1n i j i j i jiQ a a a y y x x???? (421) 至此，對支持向量機的討論都僅限于線性分界面的情況。在目標(biāo)函數(shù)中加入一項對錯分類進(jìn)行懲罰，折衷考慮最大分類間隔和最少錯分樣本，即改求 ? ?2 /2iwC?? ?最小，就得到了線性不可分情況下的支持向量機。如果訓(xùn)練樣本線性不可分，那么前述優(yōu)化問題將 變得無解。而 b*是分類的域值，可以由任意一個支持向量用式 48 求得 (因為支持向量滿足其中的等式 )，或通過兩類中任意一對支持向量取中值求得。 將解上述問題后得到的最優(yōu)分類函數(shù)是 ? ? ? ?? ? ? ?* * * *1s g n s g n n i i iif x w x b a y x x b???? ? ? ? ? ?????? (416) sgn( )為符號函數(shù)。 這是一個不等式約束下二次函數(shù)極值問題，存在唯一解。為此，我們定義拉格朗日函數(shù)如下： ? ?? ?11( , , ) ( ) 12 n i i iiL w b a w w a y w x b?? ? ? ? ? ?????? (410) 其中， 0ia? 為拉格朗日系數(shù)，我們的問題是對 w 和 b 求拉格朗日函數(shù)的極小值。如圖中用 *標(biāo)出的點所示。過兩類樣本中離分類面最近的點且平行于最優(yōu)分類面的超平面 Hl、 H2 上的訓(xùn)練樣本就是式 48中使等號成立的那些樣本，它們叫做支持向量 (Support Vectors)。 x+b，分類面方程為 :w 對于上述 d 維線性可分樣本集為 ( x ,y ) ,i = 1 , ,n ,x R , y ( + 1 , 1 )dii ??是類別標(biāo)號。前者是保證經(jīng)驗風(fēng)險最小(為 0)，而使分類空隙最大實際上就是使推廣性的界中的置信范圍最小，從而使真實風(fēng)險最小。 H 為把兩類沒有錯誤地分開的分類線， Hl， H2 分別為過各類樣本中離分類線最近的點且平行于分類線的直線， HI 和 H2 之間的距離叫做兩類的分類空隙或分類間隔 (margin)。若超平面 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)行分類。 先考慮兩類線性可分情況。 SVM 的思想就是在樣本數(shù)目適宜的前提下，選取比較好的 VC 維 h，使經(jīng)驗風(fēng)險 empR 和置信值達(dá)到一個折中，使每一類別數(shù)據(jù)之間的分類間隔 (Margin)最大，最終使實際風(fēng)險 R 變小。 支持向量機使用結(jié)構(gòu)風(fēng)險最小化 (Structural Risk Minimization， SRM 準(zhǔn)則 )原理構(gòu)造決策超平面使每一類數(shù)據(jù)之間的分類間隔 (Margin)最大。 現(xiàn)在，越來越多的學(xué)者認(rèn)為，關(guān)于統(tǒng)計學(xué)習(xí)理論和支持向量機的研究，將很快出現(xiàn)像在 80年代后期人工神經(jīng)網(wǎng)絡(luò)研究那樣的飛速發(fā)展階段。 在 90 年代，這一理論框架下產(chǎn)生出了“支持向量機 (SVM)”這一新的通用機器學(xué)習(xí)方法。在人類即將邁進(jìn)一個新世紀(jì)的時候，人們開始逐漸頻繁地接觸到一個詞，就是“統(tǒng)計學(xué)習(xí)理論”。 人們對于解決此類問題的努力實際上一直在進(jìn)行。然而，相反的情況是很容易出現(xiàn)的。在現(xiàn)實的問題中，我們所面對的樣本數(shù)目通常是有限的，有時還十分有限。 支持向量機 統(tǒng)計學(xué)在解決機器學(xué)習(xí)問題中起著基礎(chǔ)性的作用。 (Feature Space)，在高維空間中構(gòu)造線性判別函數(shù)來實現(xiàn)原空間中的非線性判別函數(shù)，特殊性質(zhì)能保證 機器有較好的推廣能力，同時它巧妙地解決了維數(shù)問題，其算法復(fù)雜度與樣本維數(shù)無關(guān) 。由于支持向量機方法有幾個主要優(yōu)點： ，其目標(biāo)是得到現(xiàn)有信息下的最優(yōu)解而不僅僅是樣本數(shù)趨于無窮大時的最優(yōu)值 。對于在當(dāng)前特征空間中線性不可分的模式，則使用一個核函數(shù)把樣本映射到一個高維空間中，使得樣本能夠線性可分。傳統(tǒng)神經(jīng)網(wǎng)絡(luò)如 BP 算法存在以下缺點 :存在局部極小問題，學(xué)習(xí)算法收斂速度慢。在這種模型中，分類知識被隱式地存儲在連接的權(quán)值上，使用迭代算法來確定權(quán)值向量。 第五步：比較類的權(quán)重，將樣本分到權(quán)重最大的那個 類別中。 4 基于支持向量機的車型識別分類器 訓(xùn)練方法和分類算法是分類系 統(tǒng)的核心部分，目前存在多種基于向量空間模型的訓(xùn)練算法和分 第 10 頁 共 22 頁 類算法，例如，最近 K 近鄰方法、神經(jīng)網(wǎng)絡(luò)方法和支持向量機算法等等。同樣，子空間中的任一點也對應(yīng)于一幅圖像一一特征車 (圖 31顯示的是 01,uu所對應(yīng)的圖像 )。 這樣每一幅車輛圖像都可以投影到由 0 1 1, , , Mu u u ? 張成的子空間中。 考慮到使用 KL 變換作為對車輛圖像的壓縮手段，可以選取最大的前 k 個特征向量，使得 : 010kiifii?????????? （ 318） 在上式中，我們選取 a=98%。雖然 M 比 2N 小很多，但通常情況下， M 仍然會太大。 將∑表示為 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） 這就是圖像的特征向量。形成了子空間法模式識別的基礎(chǔ)，本文將它應(yīng)用于車型識別。 由于通常 SN，這種方法將求高階矩陣的特征向量轉(zhuǎn)化為求較低階矩陣的特征向量的過程在圖象數(shù)據(jù)分析中是很實用的。 PCA方法的核心過程是計算特征值和特征向量，有很多不同的數(shù)值計算方法。通常，特征值幅度差別很大，忽略一些較小的值不會引起很大的誤差。例如，丟棄底下 NM 行得到 M N 的矩陣 B，并為簡單起見假定均值 m=0，則有 : ?y Bx? （ 39） 而 x 仍可通過 ? Tx By? 來近似。 設(shè) : 1, ,ix i n? ??? 是 N 維向量的數(shù)據(jù)集合， m 是其均值向量 : 11 n iimxn ?? ? （ 31） 差別向量 id 是： iid x m?? （ 32） 協(xié)方差矩陣是： 11 n Tx i iiC d dn ?? ? (33) 求出其從大到小排列的特征值兄、及滿足下列條件的特征向量 ku ： 1, 0 ,{T l kl k l k l kuu ? ???? （ 34） 有了特征向量集合，任何數(shù)據(jù) x可以投影到特征空間（以特征向量為基向量 )中的表示： ()Tkky u x m?? , 12( , ..., )TNy y y y? (35) 相反地，任何數(shù)據(jù) x可以表示成如下的線性組合形式： 1nkkkx m y u???? （ 36） 第 8 頁 共 22 頁 如果用 A代表以特征向量為列向量構(gòu)成的矩陣，則 TA 定義了一個線性變： ()Ty A x m?? (37) x m Ay?? (A是正交矩陣 ) 變換后的協(xié)方差矩陣為 : 1 00[ ... ]NTyxC A C A ? ??? (38) 上述去相關(guān)的主分量分析方法可以用于降低數(shù)據(jù)的維數(shù)。相應(yīng)的基向量組滿足正交性且由它定義的子空間最優(yōu)地考慮了數(shù)據(jù)的相關(guān)性。 考慮到任何單個特征所包含的鑒別信息可能有限，而不同的特征往往具有互補性，將它們?nèi)诤掀饋砜梢蕴峁┴S富的鑒別信息。 PCA方法 (主元分析方法 )是特征提取的常用方法。 經(jīng)過預(yù)處理，得到了所謂的“標(biāo)準(zhǔn)圖像” (如圖 23 所示 )。若像素點的原灰度為 r，變換后的灰度為 s，需要注意的是 r、 s 是歸一化后的灰度值，其灰度變換函數(shù) T( )為： 00( ) ( )kk jrjjj ns T R P P n??? ? ??? (26) 01JRl? ? ? 0,1....k? 第 7 頁 共 22 頁 式中， ()rjPP 是第 j 級灰度值的概率， jn 是圖像中 j級灰度的像素總數(shù)， l 是圖像中灰度級的總數(shù)目， n 是圖象中像素的總數(shù)。第二 個條件則保證了映射變換后的像素灰度值在允許的范圍內(nèi)。 2)對于 0≤ r≤ 1，有 0≤ T(r)≤ 1。 可以對 [0， 1]區(qū)間內(nèi)的任一個 r 值進(jìn)行如下灰度變換 : ()s Tr? (25) 也就是說，通過上述變換，每個原始圖像的像素灰度值 r 都對應(yīng)產(chǎn)生一個 s 值。從圖像灰度級的分布可以看出一幅圖像的灰度分布特性。 設(shè)變量 r 代表圖像中像素灰度級。這里用以下映射進(jìn)行 : ln( 2 5 5 0 ) M a xout M a x M in?? ? ? ? （ 23） 其中 Max為原圖像中的最大灰度值， Min 則為原圖像中的最小灰度值。 灰度拉伸 由于圖像的亮度范圍不足或非線性會使圖像的對比度不理想，可用像素幅值重新分配的方法來改善圖像對比度。在線性插值法中，非網(wǎng)格點 (, )?? 的灰度值 ( , )f ?? ，的用其周圍四個網(wǎng)格點(x， y)， (x， y+l)， (x+l， y)， (x+1， y+l)的灰度值按下式近似計算 : ( , ) ( , ) ( 1 ) ( 1 ) ( 1 , ) ( 1 ) ( , 1 ) ( 1 ) ( 1 , 1 )f f x y a b f x y a b f x y a b f x y a b?? ? ? ? ? ? ? ? ? ? ? ? ? (22) 其中 ??x ?? ， ??y ?? ， ax???， by???([ ]是高斯符號 ) 該方法精度高，但速度慢。后者處理效果要好些，但是運算量也相應(yīng)增加很多。 對灰度圖像實行實數(shù)倍大小變換 (x方向 p 倍， y 方向 p 倍 )，該操作產(chǎn)生的像素可能在原圖中找不到相應(yīng)的像素點，這樣就必須進(jìn)行近似處理。后一種方法則對原始的 (離