識別的基礎是認知
認知Cognition：獲取某種事物的特征——概念抽象
識別Re-cognition：根據(jù)特征決定某個具體的事物是不是某種事物——概念歸類
模式：一類事物的共同特征
識別：對事物進行概念歸類
模式識別：依據(jù)事物的特征進行概念歸類

特征
相似性
類
特征空間
向量空間
集合空間

通過訓練（學習）得到分類器模型參數(shù)

分類器如何學習分類決策規(guī)則饲常？

兩種模式：有監(jiān)督學習和無監(jiān)督學習——從訓練集中學習

對于每一個類別都給定一些樣本——形成一個具有類別標簽的訓練樣本集——分類器通過分析每一個樣本去尋找屬于同一類樣本具有哪些共同特征——從訓練集中學習到具體分類決策規(guī)則——有監(jiān)督的學習

分類器通過有監(jiān)督學習模式學習到的每個類別樣本的特征就是關于某個類別概念的知識—— 學習過程就是認知過程

樣本標簽如何得到寄症？——人來給定

有監(jiān)督學習——從人的經驗中學習分類知識——智能水平有上限

給定訓練樣本集但沒有給每一個樣本貼上類別標簽——屬于同一個類別的樣本之間的相似程度會大于屬于不同類別的樣本之間的相似程度——根據(jù)相似程度的大小癞谒，按照一些規(guī)則把相似程度高的一些樣本作為同一類——將訓練樣本集的一些樣本劃分成不同的類別——再從每一個類別的樣本中去尋找共同特征少漆，形成分類決策規(guī)則——無監(jiān)督學習

無監(jiān)督學習——自主地從數(shù)據(jù)所代表的自然規(guī)律中學習關于類別劃分的知識——分類器能達到更高的分類水平——未來模式識別發(fā)展的主要方向

2.1.3

屬于同一個類別的樣本之間的相似程度會大于屬于不同類別的樣本之間的相似程度——不同類樣本之間的相似度越小蟀拷，分類決策規(guī)則的裕量也就越大

這樣可以作為評判用于監(jiān)督學習的帶標簽訓練樣本集以及作為無監(jiān)督學習結果的樣本集制市，它的優(yōu)劣程度的一個指標，稱為“緊致性”準則暖庄，即：緊致性好的樣本集樣本的類內相似度遠大于類間相似度聊替。

緊致性——定性準則

若要進行定量評判——確定如何度量相似性——可以設置多種指標——如：距離指標（最常用，距離可以定義在任意集合上培廓，只要去計算滿足三條標準：1.正定性：距離是個大于等于0的正實數(shù)惹悄，當且僅當自己和自己計算距離時才為0；2.對稱性：樣本之間的距離值計算與計算順序無關肩钠；3.傳遞性：滿足三角關系——兩個樣本之間的距離一定小于等于分別于第三個樣本之間的距離之和泣港。||在向量空間中可以定義歐氏距離、曼哈頓距離价匠、切比雪夫距離等|| 非向量空間也可以定義距離当纱，如：兩個字符串之間的編輯距離也是一種合法的距離定義）非距離的相似度量標準（如：余弦相似度——使用向量空間中兩個向量之間的夾角來表達相似程度：cosθ=x^Ty/||x||·||y|| ;皮爾遜相關系數(shù)Pxy=cov(x,y)/?x?y;Jaccard相似系數(shù)）

如果我們希望有緊致性好的樣本集——那么就希望能有有效的信息能夠將不同類的樣本很好地區(qū)分開——增加特征的種類==增加特征的維度——特征的維度越多，用于識別的信息就越豐富踩窖，就有越多的細節(jié)信息可以將不同的樣本之間的相似度降低坡氯，提高樣本集的緊致性

特征的維度可以無限制地增加嗎？——

不需要無限制地增加毙石，只要不斷地增加模式識別問題中地特征維數(shù)會產生維數(shù)災難（cruse of dimensionality)——當一個問題描述地維度不斷增加時會帶來計算量劇增與解法性能下降等嚴重問題——模式識別中的維數(shù)災難：隨著特征維度的增加分類器的性能將在一段快速增加的區(qū)域后急速地下降并且最終無法使用

導致維數(shù)災難的根本原因：在于訓練集樣本的數(shù)量不不足

當特征空間以同樣密度能夠容納的樣本總數(shù)呈指數(shù)增長時廉沮，而如果給定樣本集中的樣本數(shù)量沒有同步按照指數(shù)規(guī)律增加的話，那么問題越往高維度特征空間映射時樣本集中的樣本就越稀疏徐矩，從而使得樣本集的緊致性越來越差滞时，因此分類器的性能越來越差。

要解決維數(shù)災難問題或者要同步地大量增加樣本集樣本的數(shù)量滤灯，難以實現(xiàn)坪稽，或者盡可能減少問題所使用的特征維度。

在降低維度的同時盡可能地提升每一個維度在分類中的效能鳞骤，從而使模式識別問題在較低的維度下解決窒百。

特征生成+特征降維 重點領域——其結果直接影響分類器性能的好壞

2.1.4泛化能力與過擬合

我們期望分類器能夠從訓練集樣本中發(fā)現(xiàn)所要分類的各個類別的普遍特點即找到最優(yōu)的分類器，使分類器在經過訓練后不僅能將訓練集中的樣本正確分類豫尽，而且對于不在訓練集中的新樣本也能夠正確地分類

泛化能力：訓練好的分類器對未知新樣本正確分類的能力

因為有誤差所以不能同時滿足【正確分類樣本集】和【正確分類未知新樣本】

采集數(shù)據(jù)時由于數(shù)據(jù)采集方法的問題或者存在噪聲干擾得到的樣本特征會存在誤差甚至會出現(xiàn)“異常數(shù)據(jù)”

如果我們要求分類器必須正確分類則會在分類規(guī)則上出現(xiàn)“失真”篙梢，從而在面對新的未知樣本進行分類時出現(xiàn)錯誤（使分類器泛化能力降低）====稱為分類器訓練過程中的“過擬合”

“結構風險最小化準則”

2.1.5 模式識別系統(tǒng)

模式識別系統(tǒng)

分類決策規(guī)則是從自動計算中獲取的而不是人工設定的

設計模式識別系統(tǒng)就是設計分類器的模型、所使用的的特征和分類器參數(shù)的調整算法

第一個環(huán)節(jié)：

通過采集轉換得到計算機能接受和處理的數(shù)據(jù)

模式采集：傳感器美旧、變送器渤滞、模數(shù)轉換

得到的數(shù)據(jù)：待識別樣本的原始信息（包含大量干擾和無用數(shù)據(jù)）

第二個環(huán)節(jié)：

通過各種濾波降噪措施降低干擾的影響贬墩，增強有用的信息，在此基礎上生成在分類上具有意義的各種特征

得到的特征：可以仍然用數(shù)值來表示妄呕，也可以用拓撲關系陶舞、邏輯結構等其他形式表示

第三個環(huán)節(jié)：

經過一、二環(huán)節(jié)獲得的模式特征維數(shù)都是很大的

主要方法：特征選擇和特征提取

特征選擇：從已有的特征中選擇一些特征绪励，拋棄其他特征

特征提戎追酢：是對原始的高維特征進行映射變換，生成一組維數(shù)更少的特征

第四環(huán)節(jié)——分類器訓練過程==分類器學習的過程

分類器訓練是由計算機根據(jù)樣本的情況自動進行的疏魏，分類有監(jiān)督學習和無監(jiān)督學習

第五環(huán)節(jié)——分類決策

在分類器訓練結束后停做，對待分類的樣本按照已建立起來的分類決策規(guī)則進行分類的過程，在待分類的樣本在進行分類決策之前蠢护，與訓練樣本一樣要完成模式采集雅宾、預處理與特征生成、特征降維等環(huán)節(jié)的處理葵硕，還要持續(xù)不斷地對分類決策的結果進行評估眉抬，已改進分類器的性能。

2.2模式識別的算法體系

模式識別算法

模式識別算法：統(tǒng)計模式識別（主流）懈凹、結構模式識別

統(tǒng)計模式識別：將樣本轉換成多維特征空間中的點蜀变，再根據(jù)樣本的特征取值情況和樣本集的特征值分布情況確定分類決策規(guī)則。

線性分類器：是最基本的統(tǒng)計分類器介评，它通過尋找線性分類決策邊界來實現(xiàn)特征空間中的類別劃分

貝葉斯分類器：它的決策規(guī)則是基于不同類樣本在特征空間中的概率分布以逆概率推理的貝葉斯公式來得到類別劃分的決策結果

最近鄰分類器：把學習過程隱藏到了分類決策中库北，通過尋找訓練集中與待分類樣本最相似的子集來實現(xiàn)分類決策

神經網(wǎng)絡分類器：來源于對生物神經網(wǎng)絡系統(tǒng)的模擬，它的本質是高度非線性的統(tǒng)計分類器并且隨著計算機技術的發(fā)展從淺層網(wǎng)絡向深層網(wǎng)絡不斷演化

統(tǒng)計聚類分析：是無監(jiān)督學習的典型代表

聚類分析：是無監(jiān)督學習的典型代表们陆，目前多采用統(tǒng)計學習的方法寒瓦。

模糊模式識別：不是一獨立的方法，而是將模糊數(shù)學引入模式識別技術后對現(xiàn)有算法的模糊化改造坪仇，它在更精確地描述問題和更有效地得出模式識別結果方面都有許多有價值的思路杂腰。

特征降維：也不是獨立的模式識別算法，但是是完成模式識別任務的流程中不可缺少的一個步驟椅文，特征降維通過尋找數(shù)量更少對分類更有效的特征來提升整個模式識別系統(tǒng)的性能喂很。

結構模式識別：

結構聚類算法：將樣本結構上某些特點作為類別和個體的特征通過結構上的相似性來完成分類任務。

句法模式識別：利用了形式語言理論中的語法規(guī)則皆刺，將樣本的結構特征轉化為句法類型的判定少辣，從而實現(xiàn)模式識別的功能。

2.3.1問題：手寫數(shù)字識別

一個典型的基于視覺的模式識別工程問題

多分類問題

2.3.2算法：從模板匹配開始

模板匹配基本原理：為每一個類別建立一個或多個標準的模板羡蛾，分類決策時將待識別的樣本與每個類別的模板進行比對漓帅，根據(jù)與模板的匹配程度將樣本劃分到最相似的類別中。

建立模板時依賴人的經驗所以適應性差

2.4算法實例演示：模板匹配

3.1.1線性判別和廣義線性判別

“分類決策邊界”

判別函數(shù)G(x)=0

如果判別函數(shù)是線性函數(shù)則稱為線性判別函數(shù)

線性判別函數(shù)+對應的分類規(guī)則=線性分類器

如果特征空間是一維的，線性分類器的分類決策邊界就是一個點

如果特征空間是二維的忙干，線性分類器的分類決策邊界是一條直線

如果特征空間是三維的屯伞，線性分類器的分類決策邊界是一個平面

如果維度很高，從數(shù)學上可以得到分類決策邊界是一個超平面

是不是任何一個模式識別問題都可以找到線性分類決策邊界呢豪直？

給定一個樣本集，它是線性可分的嗎珠移？

涉及問題：樣本集的線性可分性

如果一個樣本集弓乙，它的各個類別樣本的分布區(qū)域是相交的，那么肯定是線性不可分的钧惧；如果各個類別樣本的分布區(qū)域是互不相交的暇韧，并且都是凸集，那么它一定是線性可分的浓瞪；如果互不相交但有的是凹集懈玻，也不一定是線性可分的，需要找出凹集區(qū)域最小的凸集包絡線稱為凸包乾颁，如果凸包都不想交涂乌，那么樣本集才是可分的，否則不可分英岭。

線性可分性——異或問題

非線性分類問題轉化為線性分類問題：

當我們將一個模式識別問題從低維特征空間映射到高維特征空間時湾盒，就將一個非線性分類問題轉化為一個線性分類問題。======》這種方法被稱為“廣義線性化”

3.1.2多分類線性判別

需要多個線性判別函數(shù)——用二分類問題的組合來確定多分類的分類決策規(guī)則

根據(jù)一定的邏輯關系構成多分類的線性分類器

絕對可分：對于樣本集中的每一個類都有一個線性判別函數(shù)诅妹，可以把屬于這一類和不屬于這一類的樣本分開罚勾。——帶來的不可識別區(qū)域很多吭狡，整體分類器的性能不好尖殃。

兩兩可分：判別函數(shù)并不是用于判別屬于某一個或者不屬于某一個類的樣本，而是在兩個特定的類別中選邊站划煮。減少了不可識別區(qū)域送丰，提升了線性分類器的性能。

如果有k個分類般此，兩兩可分的線性判別一共需要C2k個判別函數(shù)蚪战，絕對可分的線性判別需要k個判別函數(shù)

最大值可分：樣本集中每一個類別對應有一個判別函數(shù)，而一個樣本將被劃分到取值最大的那個判別函數(shù)所對應的類別中铐懊⊙＃——不可識別區(qū)域消失，判別函數(shù)的數(shù)量也僅僅與樣本集中的類別數(shù)量一樣科乎。

如何求最大值可分的判別函數(shù)壁畸？——工作量大

3.1.3線性判別函數(shù)的幾何意義

判別函數(shù)是樣本到決策超平面距離遠近的一種度量

樣本x到決策邊界的距離r正比于判別函數(shù)G(x)的值，判別函數(shù)的符號代表了距離r的符號，表示該模式位于決策邊界的正側還是負側

權向量w僅代表決策超平面的法向方向捏萍，長度不會影響決策邊界在特征空間中的位置太抓，可以取w為1，此時判別函數(shù)的值就是樣本到決策邊界的距離令杈。

3.2.1線性分類器訓練的一般思路

線性分類器——由線性判別函數(shù)及相應道德分類決策規(guī)則構成的

線性判別函數(shù)如何得到走敌？——如何設計線性分類器？——訓練問題

線性分類器學習/訓練的一般思路：

G_ij(x)=w^Tx+w₀

w^T 權向量

w₀ 偏置量

解區(qū)域中尋找最優(yōu)解

1.設定一個標量的準則函數(shù)J(w,w₀),使其值能夠代表解的優(yōu)劣程度逗噩，準則函數(shù)值越小掉丽，說明解越符合要求，越好异雁。

2.通過尋找準則函數(shù)J(w,w₀)的極小值捶障，就能找到最優(yōu)的一個解，是準則函數(shù)取得極小值的增廣權向量w纲刀，這就是最優(yōu)解项炼。 （w,w₀）^*

訓練集數(shù)據(jù)的規(guī)范化

3.2.2感知器算法的原理

1.了解感知器模型

感知器（perception）模型是一種神經元模型

多路輸入+單路輸出

將所有輸入信號加權求和后于一個閾值相比較，如果大于閾值示绊，則神經元輸出為1锭部；小于等于閾值，則神經元輸出為0

沒有反饋與內部狀態(tài)

只能依靠輸入信號是否超過閾值來決定是否激活神經元的輸出

如果把感知器的輸入信號看作是一個待識別樣本的特征向量面褐，感知器的數(shù)學模型就構成了一個典型的線性分類器空免，可以做出非常明確的二分類決策

通過樣本集使感知器能夠學習到輸入權重值和輸出的閾值

感知器是一個通過輸入加權和與閾值的比較來決定是否激活輸出的神經元模型，這是一個線性分類器盆耽，輸入的權構成了線性分類決策邊界的權向量蹋砚，激活輸出的閾值\theta就是分類決策邊界的偏置量w₀

求解目標：對所有樣本，都有w^Tx > 0

感知器算法設定準則函數(shù)的依據(jù)：最終分類器要能正確分類所有的樣本

所以J設定為所有錯分樣本的判別函數(shù)值之和

X₀是所有錯分樣本的集合

只要存在錯分樣本摄杂，準則函數(shù)一定大于0坝咐，只有當所有樣本正確分類了，準則函數(shù)值才能取得極小值0

梯度下降法

w(k+1)=w(k)-p(k+1)?J(w(k))

3.3算法實例演示：線性分類器

3.4.1線性分類器的松弛求解

3.4.2H-K算法

3.5.1支持向量機的原理

對于線性可分的兩類問題其分類決策邊界為一n維特征空間中的超平面H

一般情況下會有無窮多個解析恢，當我們確定一個解所對應的權向量w墨坚，超平面的斜率和朝向就是確定的了，可以在一定范圍內平移超平面H映挂，只要不達到或者越過兩類中距離H最近的樣本泽篮，分類決策邊界都可以正確地實現(xiàn)線性分類，所以任何一個求解得到的權向量w都會帶來一系列平行的分類決策邊界柑船，其可平移的范圍具有一定的寬度帽撑，稱為分類間隔（Marigin of Classification）。

當我們改變w鞍时，使分類決策邊界的斜率和朝向隨之變化時亏拉，我們得到的分類間隔是不同的扣蜻。

分類間隔越大，兩類樣本做決策時的裕量也就越大

找到可以使分類間隔最大的最優(yōu)權向量 w*——支持向量機的出發(fā)點

分類間隔是由距離分類決策邊界最近的少量樣本決定的及塘，這些樣本被稱為“支持向量 support vector”_支撐起了線性分類器在最大分類間隔意義下的最優(yōu)解

支持向量機的優(yōu)化求解目標是求取能帶來最大分類間隔的權向量w

分類間隔是支持向量到分類決策邊界的2倍

Max d = max 2|G_ij(x)|/||w|| 支持向量機采用令|G_ij(x)|=1 =>min ||w|| 將求取最大的d的問題轉化為求取權向量的長度最短的問題——為了方便進行二次優(yōu)化——=>min 1/2 ||w||²

求取優(yōu)化目標要求兩類中的所有樣本到分類決策邊界的距離都應該比支持向量更大莽使，其他樣本的判別函數(shù)絕對值都需要大于1，即不等式約束條件為：圖

支持向量機采用拉格朗日乘子法將其轉化為無約束優(yōu)化問題來求解笙僚，即通過將所有約束條件與拉格朗日乘子相乘后添加到優(yōu)化目標中芳肌，在求取拉格朗日乘子最大值的條件下，求取最短的權向量w——凸規(guī)劃問題——存在唯一解——其充要條件可以通過拉格朗日函數(shù)分別對權向量w和偏置值w0求偏導來得到肋层，即滿足這樣的條件——得到權向量的表達公式

KKT條件

3.5.2結構風險最小化準則

經驗風險:訓練之后的分類器的錯誤分類樣本比例

經驗風險最小化 R_emp==o

只有當訓練集的樣本數(shù)趨近于無窮庇勃，訓練集中樣本的分布趨近于樣本的真實分布時，經驗風險才會趨近于真實樣本分類的風險

為了從根本上解決“過擬合”問題——提出“結構風險最小化SRM”min(R(w))

結構風險：在一個訓練好的分類器面對未知樣本時分類錯誤的概率

泛化誤差界：R(w)<=Remp(w)+φ(h/l) 置信風險 l是訓練集中的樣本數(shù)槽驶，h為分類器形式的vc維，而φ置信風險的具體計算公式：圖

如果分類器函數(shù)形式已經確定鸳兽，則樣本數(shù)越大掂铐，置信風險也就越小揍异；如果訓練集中的樣本數(shù)量不夠多全陨，那么結構風險的大小就受置信風險大小的很大影響，而此時置信風險的大小取決于分類器函數(shù)形式本身具有的VC維衷掷，函數(shù)的VC維h越大辱姨，則置信風險也就越大，則相應的結構風險也就越大戚嗅，分類器的泛化能力越差雨涛。

什么是VC維？一類函數(shù)所具有的分類能力

它的值是一類函數(shù)能打散兩類樣本集中最大樣本數(shù)量

分類器函數(shù)形式的階次越低懦胞，其VC維也就越小替久，在樣本集數(shù)量有限的情況下，訓練后的分類器結構風險就越小躏尉，泛化能力越強蚯根。

（支持向量機是階次最低的線性函數(shù)）——是支持向量機在不需要大量訓練樣本的情況下也能取得泛化能力特別強的分類器訓練結果的主要原因

所以支持向量機是應用結構風險最小化準則的一個結果

3.5.3線性不可分時的SVM之一——軟間隔支持向量機

線性不可分問題：1.異常點干擾 2.非線性分類

線性支持向量機是把具有最大分類間隔的最優(yōu)線性判別函數(shù)的求解轉化為求解最短權向量的二次規(guī)劃問題

1. 異常點干擾

異常點的判別函數(shù)值距離一定小于1

可以在約束條件中減去一項正數(shù)kesei，使判別函數(shù)的絕對值允許小于1胀糜，kesei就稱為松弛變量

把kesei也作為優(yōu)化目標颅拦，希望kesei越少越好，越小越好教藻。

最理想的情況：絕大多數(shù)支持向量外側的樣本包括支持向量對應的松弛變量都該為0.只有少數(shù)支持向量內側才有一個盡可能小的松弛變量距帅。

因此，可以把所有松弛變量的和值也作為優(yōu)化目標的一個分項括堤，即在原來的最短權向量的二次優(yōu)化目標基礎上再加上一項C乘以所有松弛變量的和锥债。C為懲罰因子，表示對分類器中存在異常點的容忍程度。C越小哮肚，松弛變量的存在對整體優(yōu)化過程的影響越小登夫，對異常點的容忍度越高。如果C取0允趟，約束條件被破壞恼策。

軟間隔的支持向量機：使用松弛變量和懲罰因子的支持向量機

3.5.4線性不可分時的SVM之二——非線性支持向量機

2. 非線性分類——本質上不可分

采用——廣義線性化（把低維空間中的非線性問題往高維映射，從而轉化為一個線性分類問題）