模式識(shí)別導(dǎo)論課件

2024/2/26模式識(shí)別導(dǎo)論

2024/2/26第一章概論

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

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

的事物，具有時(shí)間或空間分布的信息。

模式識(shí)別(PatternRecognition)------用計(jì)算機(jī)實(shí)現(xiàn)人對(duì)各種事物或現(xiàn)象的分析,描述,判斷,識(shí)別。模式識(shí)別與圖象識(shí)別，圖象處理的關(guān)系

模式識(shí)別是模擬人的某些功能

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

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/2/264.基元（鏈碼）表示：在右側(cè)的圖中八個(gè)基元分別表示0，1，2，3，4，5，6，7，八個(gè)方向和基元線段長(zhǎng)度。則右側(cè)樣本可以表示為

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

①要求臨界點(diǎn)很少

②集合內(nèi)的任意兩點(diǎn)的連線,在線上的點(diǎn)屬于同一集合

③集合內(nèi)的每一個(gè)點(diǎn)都有足夠大的鄰域,在鄰域內(nèi)只包含同一集合的點(diǎn)4.模式識(shí)別的要求:滿足緊致集，才能很好的分類；如果不滿足緊致集，就要采取變換的方法,滿足緊致集.2024/2/26三.相似與分類

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

①應(yīng)為非負(fù)值

②樣本本身相似性度量應(yīng)最大

③度量應(yīng)滿足對(duì)稱性

④在滿足緊致性的條件下，相似性應(yīng)該是點(diǎn)間距離的單調(diào)函數(shù)

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

①絕對(duì)值距離已知兩個(gè)樣本

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

2024/2/26②歐幾里德距離③明考夫斯基距離

其中當(dāng)q=1時(shí)為絕對(duì)值距離，當(dāng)q=2時(shí)為歐氏距離2024/2/26④切比雪夫距離

q趨向無(wú)窮大時(shí)明氏距離的極限情況⑤馬哈拉諾比斯距離

其中xi，xj為特征向量，為協(xié)方差。使用的條件是樣本符合正態(tài)分布2024/2/26⑥夾角余弦為xixj的均值即樣本間夾角小的為一類，具有相似性例：x1,x2,x3的夾角如圖：因?yàn)閤1,x2的夾角小，所以x1,x2最相似。x1x2x1x2x32024/2/26⑦相關(guān)系數(shù)為xixj的均值注意：在求相關(guān)系數(shù)之前，要將數(shù)據(jù)標(biāo)準(zhǔn)化3.分類的主觀性和客觀性①分類帶有主觀性：目的不同，分類不同。例如：鯨魚，牛，馬從生物學(xué)的角度來(lái)講都屬于哺乳類，但是從產(chǎn)業(yè)角度來(lái)講鯨魚屬于水產(chǎn)業(yè)，牛和馬屬于畜牧業(yè)。

②分類的客觀性：科學(xué)性判斷分類必須有客觀標(biāo)準(zhǔn)，因此分類是追求客觀性的，但主觀性也很難避免，這就是分類的復(fù)雜性。2024/2/26四.特征的生成

1.低層特征：

①無(wú)序尺度：有明確的數(shù)量和數(shù)值。

②有序尺度：有先后、好壞的次序關(guān)系，如酒分為上，中，下三個(gè)等級(jí)。

③名義尺度：無(wú)數(shù)量、無(wú)次序關(guān)系，如有紅，黃兩種顏色

2.中層特征：經(jīng)過(guò)計(jì)算，變換得到的特征

3.高層特征：在中層特征的基礎(chǔ)上有目的的經(jīng)過(guò)運(yùn)算形成例如：椅子的重量=體積*比重體積與長(zhǎng)，寬，高有關(guān)；比重與材料，紋理，顏色有關(guān)。這里低、中、高三層特征都有了。假設(shè)對(duì)一模式X已抽取n個(gè)特征，表示為：模式識(shí)別問(wèn)題就是根據(jù)模式X的n個(gè)特征來(lái)判別模式屬于ω1,ω2,

…,

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

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

1.二維情況：取兩個(gè)特征向量這種情況下判別函數(shù):在兩類別情況，判別函數(shù)g

(x)

具有以下性質(zhì)：這是二維情況下判別由判別邊界分類.情況如圖：1.二維情況2.n維情況現(xiàn)抽取n個(gè)特征為：判別函數(shù)：

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

多類問(wèn)題對(duì)于多類問(wèn)題，模式有ω1,ω2,

…,

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

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

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

判別函數(shù)：判別邊界：判別條件：2。第二種情況：每個(gè)模式類和其它模式類間可分別用判別平面分開。判別函數(shù)性質(zhì)：假設(shè)判別函數(shù)為：判別邊界為：2。第二種情況（續(xù)）用方程式作圖：?jiǎn)?未知模式X=(x1,x2)T=(4,3)T屬于那一類代入判別函數(shù)可得:把下標(biāo)對(duì)換可得:因?yàn)榻Y(jié)論：所以X屬于ω3類結(jié)論：判別區(qū)間增大，不確定區(qū)間減小，比第一種情況小的多.2。第二種情況（續(xù)）3。第三種情況判別函數(shù)：

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

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

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

和g1(x)>g3(x)

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

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

(x2)=g

(x3)=g

(x4)=0，分別作出通過(guò)加權(quán)空間原點(diǎn)的平面②③④圖中用陰影表示的部分是各平面的正側(cè)。加權(quán)空間的構(gòu)造：設(shè)是加權(quán)空間分界面上的一點(diǎn)，代入上式得：1、模式空間與加權(quán)空間這是一個(gè)不等式方程組，它的解處于由ω1類所有模式?jīng)Q定的平面的正邊和由ω2類所有模式?jīng)Q定的平面的負(fù)邊，它的解區(qū)即為凸多面錐。如圖所示：(b)為加權(quán)空間，（c）為正規(guī)化后的加權(quán)空間。由上可以得到結(jié)論：加權(quán)空間的所有分界面都通過(guò)坐標(biāo)原點(diǎn)。這是加權(quán)空間的性質(zhì)。為了更清楚，下面用二維權(quán)空間來(lái)表示解向量和解區(qū)。1、模式空間與加權(quán)空間（續(xù)）在三維空間里，令w3

=0

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

與(x1-x2)

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

p：x在H

的投影向量，r是x

到H

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

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

③

②

④

⑤

⑦

（b）結(jié)論：N個(gè)樣品線性可分?jǐn)?shù)目(條件：樣本分布良好）：4。二分法能力（續(xù)）對(duì)N和n各種組合的D(N,n)值，表示在下表中，從表中可看出，當(dāng)N，n緩慢增加時(shí)D(N,n)卻增加很快。12345612222222444444368888848141616161651022303232324。二分法能力（續(xù)）線性可分概率：把上式用曲線表示成下圖：圖中橫坐標(biāo)用λ=N/n+1表示。由圖討論：4。二分法能力（續(xù)）結(jié)論：在實(shí)際工作中，分類的訓(xùn)練非常重要，由已知樣本來(lái)訓(xùn)練。因?yàn)橐阎獦颖居邢蓿粗獦颖緹o(wú)限。選擇已知類別的訓(xùn)練樣本數(shù)方法如下：4。二分法能力（續(xù)）①：如果訓(xùn)練樣本N<N0，設(shè)計(jì)分類器的分類能力太差，因?yàn)橛?xùn)練樣本太少。②：如果訓(xùn)練樣本N太多時(shí)，則樣本太多，運(yùn)算量、存儲(chǔ)量太大。③：因此實(shí)際工作中應(yīng)該?。孩?。二分法能力（續(xù)）§2-4、廣義線性判別函數(shù)這樣一個(gè)非線性判別函數(shù)通過(guò)映射，變換成線性判別函數(shù)。判別函數(shù)的一般形式：§2-4、廣義線性判別函數(shù)（續(xù)）例：如右圖?！?-4、廣義線性判別函數(shù)（續(xù)）要用二次判別函數(shù)才可把二類分開：ω2ω1ω2§2-4、廣義線性判別函數(shù)（續(xù)）從圖可以看出：在陰影上面是ω1類，在陰影下面是ω2類，結(jié)論：在X空間的非線性判別函數(shù)通過(guò)變換到Y(jié)空間成為線性的，但X變?yōu)楦呔S空間ω2ω1ω21.分段線性判別函數(shù)（用線性無(wú)法分開,可用分段線性判別函數(shù)）

①、基于距離的分段線性判別函數(shù)。（用均值代表一類，通過(guò)均值連線中點(diǎn)的垂直線分開）把ωi類可以分成li個(gè)子類:∴分成l個(gè)子類。現(xiàn)在定義子類判別函數(shù)：在同類的子類中找最近的均值。判別規(guī)則：這是在M類中找最近均值。則把x歸于ωj類完成分類?！?-5、非線性判別函數(shù)Ⅱ

Ⅲ

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

§3-1線性分類器的設(shè)計(jì)

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

其中

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

W=(W1,W2…

Wn,Wn+1)n維權(quán)向量

通常通過(guò)特征抽取可以獲得n維特征向量，因此n維權(quán)向量是要求解的。求解權(quán)向量的過(guò)程就是分類器的訓(xùn)練過(guò)程，使用已知類別的有限的學(xué)習(xí)樣本來(lái)獲得分類器的權(quán)向量被稱為有監(jiān)督的分類。利用已知類別學(xué)習(xí)樣本來(lái)獲得權(quán)向量的訓(xùn)練過(guò)程如下已知x1∈ω1,通過(guò)檢測(cè)調(diào)整權(quán)向量，最終使x1∈ω1已知x2∈ω2,通過(guò)檢測(cè)調(diào)整權(quán)向量，最終使x2∈ω2這樣就可以通過(guò)有限的樣本去決定權(quán)向量x1x2…….xn1w1w2wnwn+1∑

>0x∈ω1

檢測(cè)(已知類別)

W1X1

W2X2

WnXn

Wn+1<0x∈ω2

g(x)=wTx

利用方程組來(lái)求解權(quán)向量對(duì)二類判別函數(shù)g(x)=W1X1+W2X2+W3已知訓(xùn)練集：Xa,Xb,Xc,Xd且當(dāng)(Xa,Xb)∈W1時(shí)

g(x)＞0

當(dāng)(Xc,Xd)∈W2時(shí)

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

X1aW1+X2aW2+W3＞0①

X1bW1+X2bW2+W3＞0②

X1cW1+X2cW2+W3＜0③

X1dW1+X2dW2+W3＜0④

求出W1,W2,W3

將③④式正規(guī)化，得

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

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

為各模式增1矩陣

為N*(n+1）矩陣N為樣本數(shù)，n為特征數(shù)訓(xùn)練過(guò)程就是對(duì)已知類別的樣本集求解權(quán)向量w，這是一個(gè)線性聯(lián)立不等式方程組求解的過(guò)程。求解時(shí)：①

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

聯(lián)立方程的解是非單值，在不同條件下，有不同的解，所以就產(chǎn)生了求最優(yōu)解的問(wèn)題③求解W的過(guò)程就是訓(xùn)練的過(guò)程。訓(xùn)練方法的共同點(diǎn)是，先給出準(zhǔn)則函數(shù)，再尋找使準(zhǔn)則函數(shù)趨于極值的優(yōu)化算法，不同的算法有不同的準(zhǔn)則函數(shù)。算法可以分為迭代法和非迭代法。一梯度下降法—迭代法欲對(duì)不等式方程組WTX>0求解，首先定義準(zhǔn)則函數(shù)(目標(biāo)函數(shù))J(W)，再求J(W)的極值使W優(yōu)化。因此求解權(quán)向量的問(wèn)題就轉(zhuǎn)化為對(duì)一標(biāo)量函數(shù)求極值的問(wèn)題。解決此類問(wèn)題的方法是梯度下降法。方法就是從起始值W1開始，算出W1處目標(biāo)函數(shù)的梯度矢量▽J(W1)，則下一步的w值為：W2=W1-ρ1▽J(W1)W1為起始權(quán)向量ρ1為迭代步長(zhǎng)J(W1)為目標(biāo)函數(shù)▽J(W1)為W1處的目標(biāo)函數(shù)的梯度矢量在第K步的時(shí)候Wk+1=Wk-ρk▽J(Wk)ρk為正比例因子這就是梯度下降法的迭代公式。這樣一步步迭代就可以收斂于解矢量，ρk取值很重要

ρk太大，迭代太快，引起振蕩，甚至發(fā)散。

ρk太小，迭代太慢。應(yīng)該選最佳ρk。選最佳ρk

目標(biāo)函數(shù)J(W)二階臺(tái)勞級(jí)數(shù)展開式為

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

其中D為當(dāng)W=Wk時(shí)J(W)的二階偏導(dǎo)數(shù)矩陣

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

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

其中▽J=▽J(Wk)

對(duì)ρk求導(dǎo)數(shù)，并令導(dǎo)數(shù)為零有最佳步長(zhǎng)為ρk=||▽J||2/▽JTD▽J這就是最佳ρk的計(jì)算公式，但因二階偏導(dǎo)數(shù)矩陣D的計(jì)算量太大，因此此公式很少用。

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

對(duì)Wk+1求導(dǎo)，并令導(dǎo)數(shù)為零可得：最佳迭代公式：Wk+1=Wk-D-1▽J—牛頓法的迭代公式

D-1是D的逆陣討論：牛頓法比梯度法收斂的更快，但是D的計(jì)算量大并且要計(jì)算D-1。當(dāng)D為奇異時(shí)，無(wú)法用牛頓法。二感知器法感知器的原理結(jié)構(gòu)為：通過(guò)對(duì)W的調(diào)整，可實(shí)現(xiàn)判別函數(shù)g(x)=WTX>RT

其中RT為響應(yīng)閾值定義感知準(zhǔn)則函數(shù)：只考慮錯(cuò)分樣本定義：其中x0為錯(cuò)分樣本當(dāng)分類發(fā)生錯(cuò)誤時(shí)就有WTX<0，或－WTX>0,所以J(W)總是正值，錯(cuò)誤分類愈少，J(W)就愈小。理想情況為即求最小值的問(wèn)題。求最小值對(duì)W求梯度代入迭代公式中Wk+1=Wk-ρk▽J

由J(W)經(jīng)第K+1次迭代的時(shí)候，J(W)趨于0，收斂于所求的W值W的訓(xùn)練過(guò)程：例如:x1,x2,x3∈ω1作

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

假設(shè)起始權(quán)向量w1=0ρk=11.x1,x2,x3三個(gè)矢量相加得矢量2,垂直于矢量2的超平面H將x3錯(cuò)分.2.x3與矢量2相加得矢量3,垂直于矢量3的超平面H1,將x1錯(cuò)分.3.依上法得矢量4,垂直于矢量4做超平面,H2將x3錯(cuò)分

4.x3與矢量4相加得矢量5,矢量5在解區(qū)內(nèi),垂直于矢量5的超平面可以把

x1,x2,x3分成一類。x1x2x32H3H14H25W區(qū)間+感知器算法：

1.錯(cuò)誤分類修正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權(quán)值修正過(guò)程ρk選擇準(zhǔn)則

①

固定增量原則

ρk固定非負(fù)數(shù)

②

絕對(duì)修正規(guī)則

ρk>

③

部分修正規(guī)則

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

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

x1=(1,0,1,1)x2=(0,1,1,1)x3=(1,1,0,1)x4=(0,1,0,1)假設(shè)初始權(quán)向量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)第一次迭代后,權(quán)向量w3=(0,-1,1,-1),再進(jìn)行第2,3,…次迭代如下表

直到在一個(gè)迭代過(guò)程中權(quán)向量相同，訓(xùn)練結(jié)束。w6=w=(0,1,3,0)判別函數(shù)g(x)=-x2+3x3感知器算法只對(duì)線性可分樣本有收斂的解,對(duì)非線性可分樣本集會(huì)造成訓(xùn)練過(guò)程的振蕩,這是它的缺點(diǎn).

訓(xùn)練樣本wkTx修正式修正后的權(quán)值wk＋1迭代次數(shù)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線性不可分樣本集的分類解(取近似解)

對(duì)于線性可分的樣本集，可以用上述方法解到正確分類的權(quán)向量。當(dāng)樣本集線性不可分時(shí)，用上述方法求權(quán)值時(shí)算法不收斂。如果我們把循環(huán)的權(quán)向量取平均值作為待求的權(quán)向量，或就取其中之一為權(quán)向量，一般可以解到較滿意的近似結(jié)果。例：在樣本ω1:

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

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

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

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

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

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

要求編寫程序上機(jī)運(yùn)行，寫出判別函數(shù)，并打出圖表。三最小平方誤差準(zhǔn)則(MSE法)---非迭代法

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

則有聯(lián)立方程XW=b這是矛盾方程組，方程數(shù)大于未知數(shù)，所以沒有精確解的存在。每個(gè)樣本有n個(gè)特征定義誤差向量：e=XW-b≠0把平方誤差作為目標(biāo)函數(shù)

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

MSE準(zhǔn)則函數(shù)只要計(jì)算出X+就可以得到W?。?/p>

最小平方誤差法同F(xiàn)isher法是一致的。（MSE解）其中N/N1有N1個(gè)，N/N2有N2個(gè)

四韋—霍氏法（LMS法）迭代法上節(jié)得到MSE法的W解為：W=X+b在計(jì)算X+時(shí)，

1．

要求XTX矩陣為非奇異

2．

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

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

此法可收斂于W值。W滿足:XT(XW-b)=0計(jì)算量很大因此下降算法不論XTX是否奇異，總能產(chǎn)生一個(gè)解。若訓(xùn)練樣本無(wú)限的重復(fù)出現(xiàn)，則簡(jiǎn)化為

W1任意

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

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

（判斷迭代過(guò)程中是否線性可分）

若訓(xùn)練樣本線性可分時(shí)，感知器法可求出界面，但對(duì)不可分問(wèn)題不收斂只能取平均。最小平方誤差法不論樣本是否線性可分都能給出一加權(quán)矢量，但不能保證此矢量就是分界矢量，下面介紹一種方法可以檢測(cè)迭代過(guò)程中是否線性可分。因最小平方誤差法的J(W)的解為因?yàn)閄W=bb應(yīng)為正值c為矯正系數(shù)當(dāng)（XWk-bk）≤0時(shí)

當(dāng)（XWk-bk）＞

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

W1=X+b1并且b1>0迭代時(shí)檢測(cè)如果ek≥0時(shí)，XW

>b，系統(tǒng)線性可分，迭代收斂如果ek<0時(shí)，XW

<b，系統(tǒng)線性不可分，迭代不收斂我們用下面的例子來(lái)說(shuō)明ek的作用因此上式可以寫成例題：

ω1={(0,0)T,(0,1)T}ω2={(1,0)T,(1,1)T}解：正規(guī)化對(duì)ω2取負(fù)，有

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

所以W1為所求解e1=XW1-b1=0系統(tǒng)線性可分因?yàn)?/p>

若四個(gè)樣本變成：ω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

系統(tǒng)線性不可分

C為校正系數(shù),取0＜C≤1在算法進(jìn)行過(guò)程中，應(yīng)在每一次迭代時(shí)，檢測(cè)ek的值。只要出現(xiàn)ek<0，迭代就應(yīng)立即停止。

x2x1

1

1六Fisher分類準(zhǔn)則

現(xiàn)在討論通過(guò)映射投影來(lái)降低維數(shù)的方法。

X空間

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

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

映射Y空間

Y=WTX-W0>0X∈ω1

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

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

投影樣本類內(nèi)離散度:

i=1,2i=1,2

類間散布矩陣上式就是n維x空間向一維y空間的最好投影方向，它實(shí)際是多維空間向一維空間的一種映射。其中Sw為類內(nèi)散布矩陣,Sb為類間散布矩陣現(xiàn)在我們已把一個(gè)n維的問(wèn)題轉(zhuǎn)化為一維的問(wèn)題?，F(xiàn)在一維空間設(shè)計(jì)Fisher分類器:W0的選擇

Yki表示第i類中第k個(gè)樣本的投影值

N1為ω1樣本數(shù)

N2為ω2樣本數(shù)

當(dāng)W0選定后，對(duì)任一樣本X，只要判斷Y=WTX>0則X∈ω1;Y=WTX<0則X∈ω2。分類問(wèn)題就解決了

§3-2分段線形分類器的設(shè)計(jì)先求子類的權(quán)向量Wil，再求總的權(quán)向量Wi

1.

已知子類劃分時(shí)的設(shè)計(jì)方法把每一個(gè)子類作為獨(dú)立類，利用每個(gè)子類的訓(xùn)練樣本，求每個(gè)子類的線性判別函數(shù)，總的判別函數(shù)就可獲得。

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

①

用先驗(yàn)知識(shí)直接劃分

②

用聚類分析，聚成多個(gè)子類

2.

已知子類的數(shù)目的設(shè)計(jì)方法①

設(shè)各個(gè)子類的初始權(quán)向量：Wi1,Wi2…Wili

i=1,2,…MWi中有Li個(gè)子類②

若第K步迭代時(shí)ωj

類樣本Xj同ωj類某個(gè)子類的權(quán)向量Wj

n(k)的內(nèi)積值最大，即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

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

(k)不影響分類，

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

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

設(shè)Win(k)lxj=

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

重復(fù)以上迭代,直到收斂,此法類似于固定增量法.3.未知子類數(shù)目時(shí)的設(shè)計(jì)方法當(dāng)每類應(yīng)分成的子類數(shù)也不知時(shí)，這是最一般情況，方法很多，舉例如下。樹狀分段線性分類器:

設(shè)兩類情況ω1，ω2。如圖所示

①

先用兩類線性判別函數(shù)求出W1,超平面H1分成兩個(gè)區(qū)間,每個(gè)區(qū)間包含兩類。

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

③

如果每個(gè)部分仍包含兩類,

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

ω1

ω2ω2

NYω1

樹狀決策框圖§3-3非線性分類器的設(shè)計(jì)電位函數(shù)分類器,用非線性判別函數(shù)區(qū)分線性不可分的類別電位函數(shù)分類器:每個(gè)特征作為一個(gè)點(diǎn)電荷,把特征空間作為能量場(chǎng).電位分布函數(shù)有下面三種形式。

α為系數(shù)xk為某一特定點(diǎn)上圖是這些函數(shù)在一維時(shí)的圖形，第三條是振蕩曲線，只有第一周期才是可用范圍。xK(x)x321電位函數(shù)算法的訓(xùn)練過(guò)程是在逐個(gè)樣本輸入時(shí)，逐漸積累電位的過(guò)程，對(duì)于二類問(wèn)題，經(jīng)過(guò)若干循環(huán)后，如積累電位方程的運(yùn)算結(jié)果能以正、負(fù)來(lái)區(qū)分二類樣本，則訓(xùn)練就可結(jié)束。算法:

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

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

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

設(shè)ω1為正電荷,ω2為負(fù)電荷在K0(x)=0時(shí)

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

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

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

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個(gè)樣本

積累電荷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時(shí)rk+1=0xk+1∈ω1并且Kk(xk+1)≤0時(shí)rk+1=1xk+1∈ω2并且Kk(xk+1)<0時(shí)rk+1=0xk+1∈ω2并且Kk(xk+1)≥0時(shí)rk+1=-1例題.設(shè)有兩類樣本ω1={(0,0)T,(2,0)T}ω2={(1,1)T,(1,-1)

T}如下圖線性不可分特征為二維的，所以電位函數(shù)為：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對(duì)x再觀察：有細(xì)胞光密度特征,有類條件概率密度:P(x/ω?)?=1,2,…。如圖所示利用貝葉斯公式：通過(guò)對(duì)細(xì)胞的再觀察，就可以把先驗(yàn)概率轉(zhuǎn)化為后驗(yàn)概率，利用后驗(yàn)概率可對(duì)未知細(xì)胞x進(jìn)行識(shí)別?！?-1Bayes分類器—最優(yōu)分類器、最佳分類器一、兩類問(wèn)題例如：細(xì)胞識(shí)別問(wèn)題ω1正常細(xì)胞，ω2異常細(xì)胞某地區(qū)，經(jīng)大量統(tǒng)計(jì)獲先驗(yàn)概率P(ω1),P(ω2)。若取該地區(qū)某人細(xì)胞x屬何種細(xì)胞，只能由先驗(yàn)概率決定。設(shè)N個(gè)樣本分為兩類ω1，ω2。每個(gè)樣本抽出n個(gè)特征，

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

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

x為一維時(shí)，決策面為一點(diǎn)，x為二維時(shí)決策面為曲線，x為三維時(shí)，決策面為曲面，x大于三維時(shí)決策面為超曲面。例：某地區(qū)細(xì)胞識(shí)別；P(ω1)=0.9，P(ω2)=0.1未知細(xì)胞x，先從類條件概率密度分布曲線上查到：解：該細(xì)胞屬于正常細(xì)胞還是異常細(xì)胞，先計(jì)算后驗(yàn)概率：P(x/ω1)=0.2，

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

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

2.決策規(guī)則：另一種形式：3、決策面方程：4、分類器設(shè)計(jì)：g1(x)Maxg(x)g2(x)gn(x)§4-2正態(tài)分布決策理論

一、正態(tài)分布判別函數(shù)

1、為什么采用正態(tài)分布：

a、正態(tài)分布在物理上是合理的、廣泛的。

b、正態(tài)分布數(shù)學(xué)上簡(jiǎn)單，N(μ,σ2)只有均值和方差兩個(gè)參數(shù)。

2、單變量正態(tài)分布：3、（多變量）多維正態(tài)分布（1）函數(shù)形式：(2)、性質(zhì)：

①、μ與∑對(duì)分布起決定作用P(χ)=N(μ,∑),μ由n個(gè)分量組成，∑由n(n+1)/2元素組成?！喽嗑S正態(tài)分布由n+n(n+1)/2個(gè)參數(shù)組成。

②、等密度點(diǎn)的軌跡是一個(gè)超橢球面。區(qū)域中心由μ決定，區(qū)域形狀由∑決定。

③、不相關(guān)性等價(jià)于獨(dú)立性。若xi與xj互不相關(guān),則xi與xj一定獨(dú)立。

④、線性變換的正態(tài)性Y=AX，A為線性變換矩陣。若X為正態(tài)分布，則Y也是正態(tài)分布。

⑤、線性組合的正態(tài)性。判別函數(shù)：類條件概率密度用正態(tài)來(lái)表示：二、最小錯(cuò)誤率(Bayes)分類器：從最小錯(cuò)誤率這個(gè)角度來(lái)分析Bayes分類器

1.第一種情況：各個(gè)特征統(tǒng)計(jì)獨(dú)立，且同方差情況。(最簡(jiǎn)單情況)決策面方程：

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

Σ?x與i有關(guān)。所以判別函數(shù)為二次型函數(shù)。§4-3關(guān)于分類器的錯(cuò)誤率分析

1、一般錯(cuò)誤率分析：2、正態(tài)分布最小錯(cuò)誤率(在正態(tài)分布情況下求最小錯(cuò)誤率)§4-4最小風(fēng)險(xiǎn)Bayes分類器假定要判斷某人是正常(ω1)還是肺病患者(ω2),于是在判斷中可能出現(xiàn)以下情況：第一類，判對(duì)(正?！?λ11

；第二類，判錯(cuò)(正?！尾?λ21

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

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

010-1

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

ω

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