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