模式识别导论课件

2024-1-25模式識別導論

2024-1-25第一章概論

§1-1模式識別的基本概念一.模式識別的基本定義

模式(pattern)------存在於時間，空間中可觀察

的事物，具有時間或空間分佈的資訊。

模式識別(PatternRecognition)------用電腦實現人對各種事物或現象的分析,描述,判斷,識別。模式識別與圖象識別，圖象處理的關係

模式識別是模擬人的某些功能

模擬人的視覺:電腦+光學系統模擬人的聽覺:電腦+聲音感測器模擬人的嗅覺和觸覺:電腦+感測器2024-1-25二.模式識別的發展史1929年G.Tauschek發明閱讀機，能夠閱讀0-9的數字。30年代Fisher提出統計分類理論,奠定了統計模式識別的基礎。因此，在60～70年代，統計模式識別發展很快，但由於被識別的模式愈來愈複雜，特徵也愈多，就出現“維數災難”。但由於電腦運算速度的迅猛發展，這個問題得到一定克服。統計模式識別仍是模式識別的主要理論。2024-1-2550年代NoamChemsky提出形式語言理論美籍華人付京蓀提出句法結構模式識別。60年代L.A.Zadeh提出了模糊集理論，模糊模式識別理論得到了較廣泛的應用。80年代Hopfield提出神經元網路模型理論。近些年人工神經元網路在模式識別和人工智慧上得到較廣泛的應用。90年代小樣本學習理論，支持向量機也受到了很大的重視。2024-1-25三.關於模式識別的國內、國際學術組織1973年IEEE發起了第一次關於模式識別的國際會議“ICPR”，成立了國際模式識別協會---“IAPR”，每2年召開一次國際學術會議。1977年IEEE的電腦學會成立了模式分析與機器智能（PAMI）委員會，每2年召開一次模式識別與圖象處理學術會議。國內的組織有電子學會，通信學會，自動化協會，中文資訊學會….。2024-1-25§1-2模式識別系統資訊的獲取：是通過感測器，將光或聲音等資訊轉化為電信息。資訊可以是二維的圖象如文字，圖象等；可以是一維的波形如聲波，心電圖，腦電圖；也可以是物理量與邏輯值。預處理：包括A\D,二值化，圖象的平滑，變換，增強，恢復，濾波等,主要指圖象處理。2024-1-25特徵抽取和選擇：在模式識別中，需要進行特徵的抽取和選擇，例如，一幅64x64的圖象可以得到4096個數據，這種在測量空間的原始數據通過變換獲得在特徵空間最能反映分類本質的特徵。這就是特徵提取和選擇的過程。分類器設計：分類器設計的主要功能是通過訓練確定判決規則，使按此類判決規則分類時，錯誤率最低。把這些判決規則建成標準庫。分類決策：在特徵空間中對被識別對象進行分類。2024-1-25§1-3模式識別的應用1.字元識別：包括印刷體字元的識別；手寫體字元的識別（脫機），各種OCR設備例如信函分揀、檔處理、卡片輸入、支票查對、自動排板、期刊閱讀、稿件輸入；線上手寫字元的識別（聯機），各種書寫輸入板。2.醫療診斷：心電圖，腦電圖，染色體，癌細胞識別，疾病診斷，例如關幼波肝炎專家系統。3.遙感：資源衛星照片，氣象衛星照片處理，數位化地球，圖象解析度可以達到1米。2024-1-254.指紋識別臉形識別5.檢測污染分析，大氣，水源，環境監測。6.自動檢測：產品品質自動檢測7.語聲識別，機器翻譯，電話號碼自動查詢，偵聽，機器故障判斷。8.軍事應用2024-1-25§1-4模式識別的基本問題一.模式(樣本)表示方法向量表示:假設一個樣本有n個變數(特徵)Ⅹ=(X1,X2,…,Xn)T2.矩陣表示:N個樣本，n個變數(特徵)2024-1-253.幾何表示一維表示

X1=1.5X2=3

二維表示

X1=(x1,x2)T=(1,2)T

X2=(x1,x2)T=(2,1)T

三維表示

X1=(x1,x2,x3)T=(1,1,0)T

X2=(x1,x2,x3)T=(1,0,1)T2024-1-254.基元（鏈碼）表示：在右側的圖中八個基元分別表示0，1，2，3，4，5，6，7，八個方向和基元線段長度。則右側樣本可以表示為

X1=006666這種方法將在句法模式識別中用到。2024-1-25二.模式類的緊致性1.緊致集：同一類模式類樣本的分佈比較集中，沒有或臨界樣本很少，這樣的模式類稱緊致集。2024-1-252.臨界點(樣本)：在多類樣本中，某些樣本的值有微小變化時就變成另一類樣本稱為臨界樣本（點）。3.緊致集的性質

①要求臨界點很少

②集合內的任意兩點的連線,線上上的點屬於同一集合

③集合內的每一個點都有足夠大的鄰域,在鄰域內只包含同一集合的點4.模式識別的要求:滿足緊致集，才能很好的分類；如果不滿足緊致集，就要採取變換的方法,滿足緊致集.2024-1-25三.相似與分類

1.兩個樣本xi，xj之間的相似度量滿足以下要求：

①應為非負值

②樣本本身相似性度量應最大

③度量應滿足對稱性

④在滿足緊致性的條件下，相似性應該是點間距離的單調函數

2.用各種距離表示相似性：

①絕對值距離已知兩個樣本

xi=(xi1,xi2,xi3,…,xin)Txj=(xj1,xj2,xj3,…,xjn)T

2024-1-25②歐幾裏德距離③明考夫斯基距離

其中當q=1時為絕對值距離，當q=2時為歐氏距離2024-1-25④切比雪夫距離

q趨向無窮大時明氏距離的極限情況⑤馬哈拉諾比斯距離

其中xi，xj為特徵向量，為協方差。使用的條件是樣本符合正態分佈2024-1-25⑥夾角余弦為xixj的均值即樣本間夾角小的為一類，具有相似性例：x1,x2,x3的夾角如圖：因為x1,x2的夾角小，所以x1,x2最相似。x1x2x1x2x32024-1-25⑦相關係數為xixj的均值注意：在求相關係數之前，要將數據標準化3.分類的主觀性和客觀性①分類帶有主觀性：目的不同，分類不同。例如：鯨魚，牛，馬從生物學的角度來講都屬於哺乳類，但是從產業角度來講鯨魚屬於水產業，牛和馬屬於畜牧業。

②分類的客觀性：科學性判斷分類必須有客觀標準，因此分類是追求客觀性的，但主觀性也很難避免，這就是分類的複雜性。2024-1-25四.特徵的生成

1.低層特徵：

①無序尺度：有明確的數量和數值。

②有序尺度：有先後、好壞的次序關係，如酒分為上，中，下三個等級。

③名義尺度：無數量、無次序關係，如有紅，黃兩種顏色

2.中層特徵：經過計算，變換得到的特徵

3.高層特徵：在中層特徵的基礎上有目的的經過運算形成例如：椅子的重量=體積*比重體積與長，寬，高有關；比重與材料，紋理，顏色有關。這裏低、中、高三層特徵都有了。假設對一模式X已抽取n個特徵，表示為：模式識別問題就是根據模式X的n個特徵來判別模式屬於ω1,ω2,

…,

ωm類中的那一類。§2-1判別函數

例如下圖：三類的分類問題，它們的邊界線就是一個判別函數§2.1判別函數（續）判別函數包含兩類：一類是線性判別函數：線性判別函數廣義線性判別函數（所謂廣義線性判別函數就是把非線性判別函數映射到另外一個空間變成線性判別函數）分段線性判別函數另一類是非線性判別函數§2.1判別函數（續）§2-2線性判別函數我們現在對兩類問題和多類問題分別進行討論。(一)兩類問題即:

1.二維情況：取兩個特徵向量這種情況下判別函數:在兩類別情況，判別函數g

(x)

具有以下性質：這是二維情況下判別由判別邊界分類.情況如圖：1.二維情況2.n維情況現抽取n個特徵為：判別函數：

另外一種表示方法：模式分類：當g1(x)=WTX=0為判別邊界。當n=2時，二維情況的判別邊界為一直線。當n=3時，判別邊界為一平面，n>3時，則判別邊界為一超平面。2.n維情況(二)

多類問題對於多類問題，模式有ω1,ω2,

…,

ωm個類別。可分三種情況：1。第一種情況：每一模式類與其它模式類間可用單個判別平面把一個類分開。這種情況，M類可有M個判別函數，且具有以下性質：右圖所示，每一類別可用單個判別邊界與其它類別相分開。如果一模式X屬於ω1，則由圖可清楚看出:這時g1(x)>0而g2(x)<0，g3(x)<0。ω1類與其它類之間的邊界由g1(x)=0確定.1。第一種情況例：已知三類ω1,ω2,ω3的判別函數分別為：因此三個判別邊界為：1。第一種情況（續）作圖如下：1。第一種情況（續）對於任一模式X如果它的g1(x)>0，g2(x)<0，g3(x)<0則該模式屬於ω1類。相應ω1類的區域由直線-x2+1=0

的正邊、直線-x1+x2-5=0和直線-x1+x2=0的負邊來確定。1。第一種情況（續）必須指出，如果某個X使二個以上的判別函數gi(x)>0。則此模式X就無法作出確切的判決。如圖中

IR1,IR3，IR4區域。另一種情況是IR2區域，判別函數都為負值。IR1，IR2，IR3，IR4。都為不確定區域。1。第一種情況（續）問當x=(x1,x2)T=(6,5)T時屬於那一類結論：g1(x)<0，g2(x)>0，g3(x)<0所以它屬於ω2類1。第一種情況（續）這樣有M(M_1)/2個判別平面。對於兩類問題，M=2，則有一個判別平面。同理，三類問題則有三個判別平面。

判別函數：判別邊界：判別條件：2。第二種情況：每個模式類和其他模式類間可分別用判別平面分開。判別函數性質：假設判別函數為：判別邊界為：2。第二種情況（續）用方程式作圖：問:未知模式X=(x1,x2)T=(4,3)T屬於那一類代入判別函數可得:把下標對換可得:因為結論：所以X屬於ω3類結論：判別區間增大，不確定區間減小，比第一種情況小的多.2。第二種情況（續）3。第三種情況判別函數：

判別規則：判別邊界：gi(x)=gj(x)

或gi(x)-gj(x)=0就是說，要判別模式X屬於那一類，先把X代入M個判別函數中，判別函數最大的那個類別就是X所屬類別。類與類之間的邊界可由gi(x)=gj(x)

或gi(x)-gj(x)=0來確定。每類都有一個判別函數,存在M個判別函數右圖所示是M=3的例子。對於ω1類模式，必然滿足g1(x)>g2(x)

和g1(x)>g3(x)

。假設判別函數為：則判別邊界為：3。第三種情況（續）結論：不確定區間沒有了，所以這種是最好情況。用上列方程組作圖如下：3。第三種情況（續）問假設未知模式x=(x1,x2)T=(1,1)T

，則x屬於那一類。把它代入判別函數：得判別函數為：因為所以模式x=(1,1)T屬於類。3。第三種情況（續）§2-3、線性判別函數的性質1、模式空間與加權空間模式空間：由構成的n維歐氏空間。W是此空間的加權向量，它決定模式的分界面H，W與H正交。加權空間：以為變數構成的歐氏空間模式空間與加權空間的幾何表示如下圖：模式空間1、模式空間與加權空間（續）該式表示一個通過加權空間原點的平面，此平面就是加權空間圖中的平面①,同樣令g

(x2)=g

(x3)=g

(x4)=0，分別作出通過加權空間原點的平面②③④圖中用陰影表示的部分是各平面的正側。加權空間的構造：設是加權空間分界面上的一點，代入上式得：1、模式空間與加權空間這是一個不等式方程組，它的解處於由ω1類所有模式決定的平面的正邊和由ω2類所有模式決定的平面的負邊，它的解區即為凸多面錐。如圖所示：(b)為加權空間，（c）為正規化後的加權空間。由上可以得到結論：加權空間的所有分界面都通過座標原點。這是加權空間的性質。為了更清楚，下麵用二維權空間來表示解向量和解區。1、模式空間與加權空間（續）在三維空間裏，令w3

=0

則為二維權空間。如圖：給定一個模式X，就決定一條直線：即分界面H，W與H正交，W稱為解向量。解向量的變動範圍稱為解區。因x1,x2∈ω1，x3,x4∈ω2由圖可見x1,x3離的最近，所以分界面H可以是x1,x3之間的任一直線，由垂直於這些直線的W就構成解區，解區為一扇形平面，即陰影區域。如右圖:2、解向量和解區把不等式方程正規化：正規化：2、解向量的解區（續）g(x)=WTX=0決定一個決策介面，當g(x)為線性時，這個決策介面便是一個超平面H，並有以下性質：性質①：W與H正交（如圖所示）假設x1,x2是H上的兩個向量所以W

與(x1-x2)

垂直，即W與H正交。一般說，超平面H把特徵空間分成兩個半空間。即Ω1,Ω2空間，當x在Ω1空間時g(x)>0,W指向Ω1，為H的正側，反之為H的負側.3、超平面的幾何性質Ω1Ω2g(x)>0g(x)<03、超平面的幾何性質向量到H的正交投影與值成正比其中：x

p：x在H

的投影向量，r是x

到H

的垂直距離。是W方向的單位向量。3、超平面的幾何性質（續）性質②：另一方面:3、超平面的幾何性質（續）這是超平面的第二個性質，向量x到超平面的正交投影正比與g(x)的函數值。性質③：3、超平面的幾何性質（續）性質④：3、超平面的幾何性質（續）一組模式樣本不一定是線性可分的，所以需要研究線性分類能力的方法，對任何容量為N的樣本集，線性可分的概率多大呢？（如下圖（a），線性不可分）例：4個樣本有幾種分法。圖（b）①直線把x1分開，每條直線可把4個樣本分成ω1

ω2類，4個樣本分成二類的總的可能的分法為24=16類，其中有二種是不能用線性分類實現的線性可分的是14。即概率為14/16。4。二分法能力（a）x1x2x3x4⑥

③

②

④

⑤

⑦

（b）結論：N個樣品線性可分數目(條件：樣本分佈良好）：4。二分法能力（續）對N和n各種組合的D(N,n)值，表示在下表中，從表中可看出，當N，n緩慢增加時D(N,n)卻增加很快。12345612222222444444368888848141616161651022303232324。二分法能力（續）線性可分概率：把上式用曲線表示成下圖：圖中橫坐標用λ=N/n+1表示。由圖討論：4。二分法能力（續）結論：在實際工作中，分類的訓練非常重要，由已知樣本來訓練。因為已知樣本有限，而未知樣本無限。選擇已知類別的訓練樣本數方法如下：4。二分法能力（續）①：如果訓練樣本N<N0，設計分類器的分類能力太差，因為訓練樣本太少。②：如果訓練樣本N太多時，則樣本太多，運算量、存儲量太大。③：因此實際工作中應該取：②4。二分法能力（續）§2-4、廣義線性判別函數這樣一個非線性判別函數通過映射，變換成線性判別函數。判別函數的一般形式：§2-4、廣義線性判別函數（續）例：如右圖。§2-4、廣義線性判別函數（續）要用二次判別函數才可把二類分開：ω2ω1ω2§2-4、廣義線性判別函數（續）從圖可以看出：在陰影上面是ω1類，在陰影下麵是ω2類，結論：在X空間的非線性判別函數通過變換到Y空間成為線性的，但X變為高維空間ω2ω1ω21.分段線性判別函數（用線性無法分開,可用分段線性判別函數）

①、基於距離的分段線性判別函數。（用均值代表一類，通過均值連線中點的垂直線分開）把ωi類可以分成li個子類:∴分成l個子類。現在定義子類判別函數：在同類的子類中找最近的均值。判別規則：這是在M類中找最近均值。則把x歸於ωj類完成分類。§2-5、非線性判別函數Ⅱ

Ⅲ

§2-5、非線性判別函數（續）例：未知x,如圖：先與ω1類各子類的均值比較，即，找一個最近的與ω2各子類均值比較取最近的因g2(x)<g1(x)，所以x∈ω2類。設ω＝ω1,ω2,……ωm而每一類又可以分為子類。對每個子類定義一個線性判別函數為：則定義ωi類的線性判別函數為：②、基於函數的分段線性判別函數利用均值代表一類有時有局限性，如圖所示。若用線性判別函數代表一類，就會克服上述情況。1、分段線性判別函數在各子類中找最大的判別函數作為此類的代表，則對於M類，可定義M個判別函數gi(x),i=1,2,…..M,因此，決策規則：對未知模式x，把x先代入每類的各子類的判別函數中，找出一個最大的子類判別函數，M類有M個最大子類判別函數，在M個子類最大判別函數中，再找一個最大的，則x就屬於最大的子類判別函數所屬的那一類。1、分段線性判別函數（續）③、基於凹函數的並分段線性判別函數（針對多峰情況）設li子類判別函數，i=1,2,…..r則分段線性判別函數有如下特性：1、分段線性判別函數（續）(a)：l1,l2,……lr都是分段線性判別函數(b)：若A,B都是分段線性判別函數，則：A∧B，A∨B也是分段線性判別函數。A∧B取最小，A∨B取最大。(c)：對任何分段線性函數都可以表示成如下二種形式：1)、析取範式(這是經常採用的形式)P=(L11∧L12∧…∧L1m)∨…∨(Lq1∧Lq2∧…∧Lqm)2)、合取範式Q=(L11∨L12∨…∨L1m)∧…∧(Lq1∨Lq2∨…∨Lqm)每個(L11∨L12∨…∨L1m)都稱為凹函數。1、分段線性判別函數（續）對於多峰二類問題：設第一類有q個峰，則有q個凹函數。即P=P1∨P2∨……∨Pq每個凹函數Pi由m個線性判別函數來構成。∴Pi=Li1∧Li2∧…∧Lim假設對於每個子類線性判別函數Lij都設計成：例、設如圖1、分段線性判別函數（續）∴P=(L11∧L12∧L13∧L14∧L15)∨(L21∧L22∧L23∧L24)∨(L31∧L32∧L33∧L34)2、二次判別函數二次判別函數一般可表示成：2、二次判別函數(續)

§3-1線性分類器的設計

上一章我們討論了線性判別函數形式為:g(x)=WTX

其中

X=(X1,X2…Xn)n維特徵向量

W=(W1,W2…

Wn,Wn+1)n維權向量

通常通過特徵抽取可以獲得n維特徵向量，因此n維權向量是要求解的。求解權向量的過程就是分類器的訓練過程，使用已知類別的有限的學習樣本來獲得分類器的權向量被稱為有監督的分類。利用已知類別學習樣本來獲得權向量的訓練過程如下已知x1∈ω1,通過檢測調整權向量，最終使x1∈ω1已知x2∈ω2,通過檢測調整權向量，最終使x2∈ω2這樣就可以通過有限的樣本去決定權向量x1x2…….xn1w1w2wnwn+1∑

>0x∈ω1

檢測(已知類別)

W1X1

W2X2

WnXn

Wn+1<0x∈ω2

g(x)=wTx

利用方程組來求解權向量對二類判別函數g(x)=W1X1+W2X2+W3已知訓練集：Xa,Xb,Xc,Xd且當(Xa,Xb)∈W1時

g(x)＞0

當(Xc,Xd)∈W2時

g(x)＜0設Xa=(X1a,X2a)TXb=(X1b,X2b)TXc=(X1c,X2c)TXd=(X1d,X2d)T判別函數可聯立成：

X1aW1+X2aW2+W3＞0①

X1bW1+X2bW2+W3＞0②

X1cW1+X2cW2+W3＜0③

X1dW1+X2dW2+W3＜0④

求出W1,W2,W3

將③④式正規化，得

-X1cW1-X2cW2-W3>0-X1dW1-X2dW2-W3>0所以g(x)=WTX>0

其中W=(W1,W2,W3)T

為各模式增1矩陣

為N*(n+1）矩陣N為樣本數，n為特徵數訓練過程就是對已知類別的樣本集求解權向量w，這是一個線性聯立不等式方程組求解的過程。求解時：①

只有對線性可分的問題，g(x)=WTX才有解②

聯立方程的解是非單值，在不同條件下，有不同的解，所以就產生了求最優解的問題③求解W的過程就是訓練的過程。訓練方法的共同點是，先給出準則函數，再尋找使準則函數趨於極值的優化演算法，不同的演算法有不同的準則函數。演算法可以分為迭代法和非迭代法。一梯度下降法—迭代法欲對不等式方程組WTX>0求解，首先定義準則函數(目標函數)J(W)，再求J(W)的極值使W優化。因此求解權向量的問題就轉化為對一標量函數求極值的問題。解決此類問題的方法是梯度下降法。方法就是從起始值W1開始，算出W1處目標函數的梯度向量▽J(W1)，則下一步的w值為：W2=W1-ρ1▽J(W1)W1為起始權向量ρ1為迭代步長J(W1)為目標函數▽J(W1)為W1處的目標函數的梯度向量在第K步的時候Wk+1=Wk-ρk▽J(Wk)ρk為正比例因數這就是梯度下降法的迭代公式。這樣一步步迭代就可以收斂於解向量，ρk取值很重要

ρk太大，迭代太快，引起振盪，甚至發散。

ρk太小，迭代太慢。應該選最佳ρk。選最佳ρk

目標函數J(W)二階臺勞級數展開式為

J(W)≈J(Wk)+▽JT(W-Wk)+(W-Wk)TD(W-Wk)T/2①

其中D為當W=Wk時J(W)的二階偏導數矩陣

將W=Wk+1=Wk-ρk▽J(Wk)代入①式得：

J(Wk+1)≈J(Wk)-ρk||▽J||2+ρk2▽JTD▽J

其中▽J=▽J(Wk)

對ρk求導數，並令導數為零有最佳步長為ρk=||▽J||2/▽JTD▽J這就是最佳ρk的計算公式，但因二階偏導數矩陣D的計算量太大，因此此公式很少用。

若令W=Wk+1上式為J(Wk+1)=J(Wk)+▽JT(Wk+1-Wk)+(Wk+1-Wk)TD(Wk+1-Wk)T/2

對Wk+1求導，並令導數為零可得：最佳迭代公式：Wk+1=Wk-D-1▽J—牛頓法的迭代公式

D-1是D的逆陣討論：牛頓法比梯度法收斂的更快，但是D的計算量大並且要計算D-1。當D為奇異時，無法用牛頓法。二感知器法感知器的原理結構為：通過對W的調整，可實現判別函數g(x)=WTX>RT

其中RT為回應閾值定義感知準則函數：只考慮錯分樣本定義：其中x0為錯分樣本當分類發生錯誤時就有WTX<0，或－WTX>0,所以J(W)總是正值，錯誤分類愈少，J(W)就愈小。理想情況為即求最小值的問題。求最小值對W求梯度代入迭代公式中Wk+1=Wk-ρk▽J

由J(W)經第K+1次迭代的時候，J(W)趨於0，收斂於所求的W值W的訓練過程：例如:x1,x2,x3∈ω1作

x1,x3的垂直線可得解區(如圖)

假設起始權向量w1=0ρk=11.x1,x2,x3三個向量相加得向量2,垂直於向量2的超平面H將x3錯分.2.x3與向量2相加得向量3,垂直於向量3的超平面H1,將x1錯分.3.依上法得向量4,垂直於向量4做超平面,H2將x3錯分

4.x3與向量4相加得向量5,向量5在解區內,垂直於向量5的超平面可以把

x1,x2,x3分成一類。x1x2x32H3H14H25W區間+感知器演算法：

1.錯誤分類修正wk

如wkTx≤0並且x∈ω1wk+1=wk-ρkx

如wkTx≥0并且x∈ω2

wk+1=wk-ρkx2.正確分類，wk不修正如wkTx＞0並且x∈ω1

如wkTx＜0並且x∈ω2wk+1=wk

+-Hwk+1ρkxwk權值修正過程ρk選擇準則

①

固定增量原則

ρk固定非負數

②

絕對修正規則

ρk>

③

部分修正規則

ρk=λ0＜λ≤2例題：有兩類樣本

ω1=（x1,x2）={(1,0,1),(0,1,1)}ω2=（x3,x4）={(1,1,0),(0,1,0)}解：先求四個樣本的增值模式

x1=(1,0,1,1)x2=(0,1,1,1)x3=(1,1,0,1)x4=(0,1,0,1)假設初始權向量w1=(1,1,1,1)ρk=1第一次迭代：

w1Tx1=(1,1,1,1)(1,0,1,1)T=3>0所以不修正

w1Tx2=(1,1,1,1)(0,1,1,1)T=3>0所以不修正

w1Tx3=(1,1,1,1)(1,1,0,1)T=3>0所以修正w1w2=w1-x3=(0,0,1,0)w2Tx4=(0,0,1,0)T(0,1,0,1)=0所以修正w2w3=w2-x4=(0,-1,1,-1)第一次迭代後,權向量w3=(0,-1,1,-1),再進行第2,3,…次迭代如下表

直到在一個迭代過程中權向量相同，訓練結束。w6=w=(0,1,3,0)判別函數g(x)=-x2+3x3感知器演算法只對線性可分樣本有收斂的解,對非線性可分樣本集會造成訓練過程的振盪,這是它的缺點.

訓練樣本wkTx修正式修正後的權值wk＋1迭代次數x11011x20111x31101x40101+++0w1w1w1-x3w2-x41111111100100–11-1

1x11011x20111x31101x401010+0-w3+x1w4w4-x3w51–1201–1200–22–10–22-1

2x11011x20111x31101x40101+---w5w5+x2w6w60–22–10–1300–1300–130

3x11011x20111x31101x40101++--w6w6w6w60–1300–1300–1300–130

4線性不可分樣本集的分類解(取近似解)

對於線性可分的樣本集，可以用上述方法解到正確分類的權向量。當樣本集線性不可分時，用上述方法求權值時演算法不收斂。如果我們把迴圈的權向量取平均值作為待求的權向量，或就取其中之一為權向量，一般可以解到較滿意的近似結果。例：在樣本ω1:

X1=（0,2）X3=（2,0）

X5=（-1,-1）ω2:

X2=（1,1）X4=（0,-2）

X6=（-2,0）求權向量的近似解x2x1x6x1x3－2x5－2x4x211H解：此為線性不可分問題，利用感知器法求權向量權向量產生迴圈(-1,2,0),(0,2,2),(-1,1,1),(-1,1,1)(-1,1,1),(0,0,0),(-1,2,0)因此演算法不收斂，我們可以取迴圈中任一權值，例如取W=(0,2,2)T則判別函數為：g(x)=2x1+2x2判別面方程為：g(x)=2x1+2x2＝0所以x1+x2＝0由圖看出判別面H把二類分開，但其中x2錯分到ω1類，而x1錯分到ω2類，但大部分分類還是正確的。作業：已知四個訓練樣本

w1={(0,0),(0,1)}w2={(1,0),(1,1)}

使用感知器固定增量法求判別函數設w1=(1,1,1,1)ρk=1

要求編寫程式上機運行，寫出判別函數，並打出圖表。三最小平方誤差準則(MSE法)---非迭代法

前面我們研究了線性不等式方程組g(x)=WTX>0的解法。它們共同點是企圖找一個權向量W，使錯分樣本最小。現在我們把不等式組變成如下形式：WTXi=bi>0

則有聯立方程XW=b這是矛盾方程組，方程數大於未知數，所以沒有精確解的存在。每個樣本有n個特徵定義誤差向量：e=XW-b≠0把平方誤差作為目標函數

W的優化就是使J(W)最小。求J(W)的梯度並為0。解上方程得XTXW=XTb這樣把求解XW=b的問題，轉化為對XTXW=XTb求解，這一有名的方程最大好處是因XTX是方陣且通常是非奇異的，所以可以得到W的唯一解。

MSE準則函數只要計算出X+就可以得到W取：

最小平方誤差法同Fisher法是一致的。（MSE解）其中N/N1有N1個，N/N2有N2個

四韋—霍氏法（LMS法）迭代法上節得到MSE法的W解為：W=X+b在計算X+時，

1．

要求XTX矩陣為非奇異

2．

由於計算量太大而引入比較大誤差所以要用迭代法來求求J(W)的梯度▽J(W)=2XT(XW-b)代入迭代公式W1任意設定

Wk+1=Wk-ρkXT(XWk-b)

此法可收斂於W值。W滿足:XT(XW-b)=0計算量很大因此下降演算法不論XTX是否奇異，總能產生一個解。若訓練樣本無限的重複出現，則簡化為

W1任意

Wk+1=Wk+ρk(bk-WkTXk)Xk

ρk隨迭代次數k而減少，以保證演算法收斂於滿意的W值五何—卡氏法

（判斷迭代過程中是否線性可分）

若訓練樣本線性可分時，感知器法可求出界面，但對不可分問題不收斂只能取平均。最小平方誤差法不論樣本是否線性可分都能給出一加權向量，但不能保證此向量就是分界向量，下麵介紹一種方法可以檢測迭代過程中是否線性可分。因最小平方誤差法的J(W)的解為因為XW=bb應為正值c為矯正係數當（XWk-bk）≤0時

當（XWk-bk）＞

0時引入誤差向量ekek=XWk-bk判斷是否線性可分所以J(W)的解為初始條件

W1=X+b1並且b1>0迭代時檢測如果ek≥0時，XW

>b，系統線性可分，迭代收斂如果ek<0時，XW

<b，系統線性不可分，迭代不收斂我們用下麵的例子來說明ek的作用因此上式可以寫成例題：

ω1={(0,0)T,(0,1)T}ω2={(1,0)T,(1,1)T}解：正規化對ω2取負，有

X的規範矩陣為x2x1x1x2x3x4取b1=(1,1,1,1)Tc=1W1=X+b1=(-2,0,1)T

所以W1為所求解e1=XW1-b1=0系統線性可分因為

若四個樣本變成：ω1={(0,0)T,(1,1)T}ω2={(0,1)T,(1,0)T}解：

取b1=(1,1,1,1)Tc=1W1=X+b1=(0,0,0)Te1=XW1-b1=(-1,-1,-1,-1)T<0

系統線性不可分

C為校正係數,取0＜C≤1在演算法進行過程中，應在每一次迭代時，檢測ek的值。只要出現ek<0，迭代就應立即停止。

x2x1

1

1六Fisher分類準則

現在討論通過映射投影來降低維數的方法。

X空間

X=-WTX-W0>0X∈ω1

X=-WTX-W0<0X∈ω2

映射Y空間

Y=WTX-W0>0X∈ω1

Y=WTX-W0<0X∈ω2把X空間各點投影到Y空間得一直線上，維數由2維降為一維。若適當選擇W的方向，可以使二類分開。下麵我們從數學上尋找最好的投影方向，即尋找最好的變換向量W的問題。w(y)wy1y2x2x1ω1ω2

投影樣本之間的分離性用投影樣本之差表示

投影樣本類內離散度:

i=1,2i=1,2

類間散佈矩陣上式就是n維x空間向一維y空間的最好投影方向，它實際是多維空間向一維空間的一種映射。其中Sw為類內散佈矩陣,Sb為類間散佈矩陣現在我們已把一個n維的問題轉化為一維的問題。現在一維空間設計Fisher分類器:W0的選擇

Yki表示第i類中第k個樣本的投影值

N1為ω1樣本數

N2為ω2樣本數

當W0選定後，對任一樣本X，只要判斷Y=WTX>0則X∈ω1;Y=WTX<0則X∈ω2。分類問題就解決了

§3-2分段線形分類器的設計先求子類的權向量Wil，再求總的權向量Wi

1.

已知子類劃分時的設計方法把每一個子類作為獨立類，利用每個子類的訓練樣本，求每個子類的線性判別函數，總的判別函數就可獲得。

子類的劃分可用以下方法：

①

用先驗知識直接劃分

②

用聚類分析，聚成多個子類

2.

已知子類的數目的設計方法①

設各個子類的初始權向量：Wi1,Wi2…Wili

i=1,2,…MWi中有Li個子類②

若第K步迭代時ωj

類樣本Xj同ωj類某個子類的權向量Wj

n(k)的內積值最大，即Wj

n(k)lxj=

max{Wj

n(k)lxj}n=1,2,…lj

並且滿足條件Wjn(k)xj>Win(k)lxji=1,2,…M類

j=1,2,…li子類i≠j

則權向量Wi1(k)，Wi2(k)，…,Wili

(k)不影響分類，

所以權向量不需要修正。若有某個或某幾個子類不滿足條件即：存在Win(k)使Wjn(k)xj

≤Win(k)lxji≠j所以xj錯分類，要修改權向量。

設Win(k)lxj=

max{Win(k)lxj}n=1,2,…lii≠j則修改權向量Wjn(k+1)=Wjn(k)±ρkxj③

重複以上迭代,直到收斂,此法類似於固定增量法.3.未知子類數目時的設計方法當每類應分成的子類數也不知時，這是最一般情況，方法很多，舉例如下。樹狀分段線性分類器:

設兩類情況ω1，ω2。如圖所示

①

先用兩類線性判別函數求出W1,超平面H1分成兩個區間,每個區間包含兩類。

②再利用二類分類求出W2(H2),W3(H3)。

③

如果每個部分仍包含兩類,

繼續上面的過程。關鍵是初始權向量W1的選擇:一般先選兩類中距離最近的兩個子類的均值連線做垂直線作為H1(w1)初始值再求最優解。w1Tx>0w4Tx≥0w3Tx≥0w2Tx≥0YNYYNNω1

ω1

ω2ω2

NYω1

樹狀決策框圖§3-3非線性分類器的設計電位函數分類器,用非線性判別函數區分線性不可分的類別電位函數分類器:每個特徵作為一個點電荷,把特徵空間作為能量場.電位分佈函數有下麵三種形式。

α為係數xk為某一特定點上圖是這些函數在一維時的圖形，第三條是振盪曲線，只有第一週期才是可用範圍。xK(x)x321電位函數演算法的訓練過程是在逐個樣本輸入時，逐漸積累電位的過程，對於二類問題，經過若干迴圈後，如積累電位方程的運算結果能以正、負來區分二類樣本，則訓練就可結束。演算法:

設初始電位為K0(x)=01.輸入樣本x1計算積累電位K1(x)

若x∈ω1K1(x)=K0(x)+K(xx1)

若x∈ω2K1(x)=K0(x)-K(xx1)

設ω1為正電荷,ω2為負電荷在K0(x)=0時

若x1∈ω1K1(x)=K(xx1)

若x1∈ω2K1(x)=-K(xx1)

2.輸入樣本x2計算積累電荷有以下幾種情況

a.若x2∈ω1並且K1(x2)>0

若x2∈ω2並且K1(x2)<0K1(x)=K2(x)不修正

b.若x2∈ω1並且K1(x2)≤0

若x2∈ω2並且K1(x2)≥0K2(x)=K1(x)±K(xx2)=±K1(xx1)±K(xx2)修正直到第k+1步,已輸入x1,x2,….xk個樣本

積累電荷Kk+1(x)有三種情況:1.若xk+1∈ω1並且Kk(xk+1)>0或xk+1∈ω2並且Kk(xk+1)<0

則Kk+1(x)=Kk(x)不修正2.若xk+1∈ω1並且Kk(xk+1)≤0

則Kk+1(x)=Kk(x)+K(xxk)3.若xk+1∈ω2並且Kk(xk+1)≥0

則Kk+1(x)=Kk(x)-K(xxk)綜合式：Kk+1(x)=Kk(x)+rk+1K(x,xk)

其中：xk+1∈ω1並且Kk(xk+1)>0時rk+1=0xk+1∈ω1並且Kk(xk+1)≤0時rk+1=1xk+1∈ω2並且Kk(xk+1)<0時rk+1=0xk+1∈ω2並且Kk(xk+1)≥0時rk+1=-1例題.設有兩類樣本ω1={(0,0)T,(2,0)T}ω2={(1,1)T,(1,-1)

T}如下圖線性不可分特徵為二維的，所以電位函數為：K(xx2)=exp{-[(x1-xk1)2+(x2-xk2)2]}①輸入x1=(xk1,xk2)T=(0,0)Tx1∈ω1K1(x)=K1(xx1)=exp{-(x12+x22)}②輸入x2=(2,0)Tx2∈ω1代入

K1(x2)=exp{-(02+22)}>0不修正

K2(x)=K1(x)=exp{-(x12+x22)}③輸入x3=(1,1)Tx3∈ω2代入

K2(x3)=exp{-(12+12)}>0所以需要修正

K3(x)=K2(x)-K(xx3)=exp{-(x12+x22)}-exp{-[(x1-1)2+(x2-1)2]}④輸入x4=(1,-1)Tx3∈ω2代入K3(x4)=e-2-e-4>0所以需要修正K4(x)=K3(x)-K(xx4)=exp{-(x12+x22)}-exp{-[(x1-1)2+(x2-1)2]}-exp{-[(x1-1)2+(x2+1)2]}

第二次迭代

⑤輸入x5=x1=(0,-0)Tx5∈ω1代入K4(x5)=1-e-2-e-4>0K5(x)=K4(x)⑥輸入x6=x2=(2,0)Tx6∈ω1代入

K5(x6)=e-4-e-2-e-2=0所以需要修正

K6(x)=K5(x)+K(xx6)=exp{-(x12+x22)}-exp{-[(x1-1)2+(x2-1)2]}-exp{-[(x1-1)2+(x2+1)2]}+-exp{-[(x1-2)2+x22]}

⑦輸入x7=x3=(1,1)Tx7∈ω2代入

K6(x7)=e-2-e0

-e-4+e-2<0所以不需要修正

K7(x)=K6(x)⑧輸入x8=x4=(1,-1)Tx8∈ω2代入

K7(x8)=e-2-e-2-e0

+e-2<0所以不需要修正

K8(x)=K7(x)⑨輸入x9=x1=(0,0)Tx9∈ω1代入

K8(x9)=1-e-2-e-2+e-4>0所以不需要修正

K9(x)=K8(x)

g(x)<0g(x)<0g(x)>0g(x)>0對x再觀察：有細胞光密度特徵,有類條件概率密度:P(x/ωί)ί=1,2,…。如圖所示利用貝葉斯公式：通過對細胞的再觀察，就可以把先驗概率轉化為後驗概率，利用後驗概率可對未知細胞x進行識別。§4-1Bayes分類器—最優分類器、最佳分類器一、兩類問題例如：細胞識別問題ω1正常細胞，ω2異常細胞某地區，經大量統計獲先驗概率P(ω1),P(ω2)。若取該地區某人細胞x屬何種細胞，只能由先驗概率決定。設N個樣本分為兩類ω1，ω2。每個樣本抽出n個特徵，

x=（x1，x2，x3，…，xn）T通過對細胞的再觀察，就可以把先驗概率轉化為後驗概率，利用後驗概率可對未知細胞x進行識別。1、判別函數：若已知先驗概率P(ω1),P(ω2)，類條件概率密度P(x/ω1)，

P(x/ω2)。則可得貝葉斯判別函數四種形式：2、決策規則：3、決策面方程：

x為一維時，決策面為一點，x為二維時決策面為曲線，x為三維時，決策面為曲面，x大於三維時決策面為超曲面。例：某地區細胞識別；P(ω1)=0.9，P(ω2)=0.1未知細胞x，先從類條件概率密度分佈曲線上查到：解：該細胞屬於正常細胞還是異常細胞，先計算後驗概率：P(x/ω1)=0.2，

P(x/ω2)=0.4g(x)閾值單元4、分類器設計：二、多類情況：ωί=(ω1,ω2,…,ωm)，x=(x1,x2,…,xn)

1.判別函數：M類有M個判別函數g1(x),g2(x),…,gm(x).每個判別函數有上面的四種形式。

2.決策規則：另一種形式：3、決策面方程：4、分類器設計：g1(x)Maxg(x)g2(x)gn(x)§4-2正態分佈決策理論

一、正態分佈判別函數

1、為什麼採用正態分佈：

a、正態分佈在物理上是合理的、廣泛的。

b、正態分佈數學上簡單，N(μ,σ²)只有均值和方差兩個參數。

2、單變數正態分佈：3、（多變量）多維正態分佈（1）函數形式：(2)、性質：

①、μ與∑對分佈起決定作用P(χ)=N(μ,∑),μ由n個分量組成，∑由n(n+1)/2元素組成。∴多維正態分佈由n+n(n+1)/2個參數組成。

②、等密度點的軌跡是一個超橢球面。區域中心由μ決定，區域形狀由∑決定。

③、不相關性等價於獨立性。若xi與xj互不相關,則xi與xj一定獨立。

④、線性變換的正態性Y=AX，A為線性變換矩陣。若X為正態分佈，則Y也是正態分佈。

⑤、線性組合的正態性。判別函數：類條件概率密度用正態來表示：二、最小錯誤率(Bayes)分類器：從最小錯誤率這個角度來分析Bayes分類器

1.第一種情況：各個特徵統計獨立，且同方差情況。(最簡單情況)決策面方程：

判別函數：最小距離分類器：未知x與μi相減，找最近的μi把x歸類如果M類先驗概率相等：討論：未知x，把x與各類均值相減，把x歸於最近一類。最小距離分類器。2、第二種情況：Σi＝Σ相等，即各類協方差相等。討論：針對ω1，ω2二類情況，如圖：3、第三種情況(一般情況)：Σί為任意，各類協方差矩陣不等，二次項xT

Σίx與i有關。所以判別函數為二次型函數。§4-3關於分類器的錯誤率分析

1、一般錯誤率分析：2、正態分佈最小錯誤率(在正態分佈情況下求最小錯誤率)§4-4最小風險Bayes分類器假定要判斷某人是正常(ω1)還是肺病患者(ω2),於是在判斷中可能出現以下情況：第一類，判對(正常→正常)λ11

；第二類，判錯(正常→肺病)λ21

；第三類，判對(肺病→肺病)λ22；第四類，判錯(肺病→正常)λ12

。在判斷時，除了能做出“是”ωi類或“不是”ωi類的動作以外，還可以做出“拒識”的動作。為了更好地研究最小風險分類器，我們先說明幾個概念：在整個特徵空間中定義期望風險,期望風險：行動αi：表示把模式x判決為ωi類的一次動作。損耗函數λii=λ(αi/ωi)表示模式X本來屬於ωi類而錯判為ωi所受損失。因為這是正確判決，故損失最小。損耗函數λij=λ(αi/ωj)表示模式X本來屬於ωj類錯判為ωi所受損失。因為這是錯誤判決，故損失最大。風險R（期望損失）：對未知x採取一個判決行動α(x)所付出的代價（損耗）條件風險（也叫條件期望損失）：條件風險只反映對某x取值的決策行動αi所帶來的風險。期望風險則反映在整個特徵空間不同的x取值的決策行動所帶來的平均風險。最小風險Bayes決策規則：二類問題：把x歸於ω1時風險：把x歸於ω2時風險：§4-5Bayes分類的演算法（假定各類樣本服從正態分佈）1.輸入類數M；特徵數n，待分樣本數m.2.輸入訓練樣本數N和訓練集資料矩陣X(N×n)。並計算有關參數。3.計算矩陣y中各類的後驗概率。4.若按最小錯誤率原則分類，則可根據3的結果判定y中各類樣本的類別。5.若按最小風險原則分類，則輸入各值，並計算y中各樣本屬於各類時的風險並判定各樣本類別。例1、有訓練集資料矩陣如下表所示，現已知，N=9、N1=5、N2=4、n=2、M=2，試問，X=(0,0)T應屬於哪一類？解1、假定二類協方差矩陣不等（∑1≠∑2）則均值:訓練樣本號k123451234特徵x1特徵x2110-1-1

010-1

01110-1-2-2-2類別ω1

ω

2解2、假定兩類協方差矩陣相等∑=∑1+∑2訓練樣本號k123123123特徵x1012-2-1-201-1特徵x210-110-1-1-2-2類別ω1ω2ω3解1、假定三類協方差不等；例2：有訓練集資料矩陣如下表所示，現已知，N=9、N1=N2=3、n=2、M=3，試問，未知樣本X=(0,0)T應屬於哪一類？可得三類分界線如圖所示：解2、設三類協方差矩陣相等可得三類分界線如圖所示：作業：①在下列條件下，求待定樣本x=(2,0)T的類別，畫出分界線，編程上機。1、二類協方差相等，2、二類協方差不等。訓練樣本號k123123特徵x1112-1-1-2特徵x210-110-1類別ω1ω2作業：②有訓練集資料矩陣如下表所示，現已知，N=9、N1=N2=N3=3、n=2、M=3，試問，X=(-2,2)T應屬於哪一類？要求：用兩種解法a、三類協方差不等；b、三類協方差相等。編程上機，畫出三類的分界線。訓練樣本號k123