第三章-線性判別分析非參數(shù)判別分類方法第四次課課件

第三章線性判別分析——非參數(shù)判別分類方法第三章線性判別分析本章內(nèi)容3.1

線性判別函數(shù)3.2線性分類器Fisher線性判決感知準(zhǔn)則函數(shù)3.3分段線性分類器3.4近鄰分類器總結(jié)習(xí)題本章內(nèi)容3.1線性判別函數(shù)3.2.2Fisher線性判決

Fisher線性判決的基本思想是尋找一個(gè)最好的投影方向,當(dāng)特征向量x從d維空間映射到這個(gè)方向上時(shí),兩類能最好地分開(kāi)。這個(gè)方法實(shí)際上涉及特征維數(shù)的壓縮問(wèn)題。3.2線性分類器3.2.2Fisher線性判決3.2線性分類器分析w1方向之所以比w2方向優(yōu)越,可以歸納出這樣一個(gè)準(zhǔn)則：即向量w的方向選擇應(yīng)能使兩類樣本投影的均值之差盡可能大些,而使類內(nèi)樣本的離散程度盡可能小。這就是Fisher準(zhǔn)則函數(shù)的基本思路。分析w1方向之所以比w2方向優(yōu)越,可以歸納出這樣一個(gè)第一步：計(jì)算參量。(1)各類樣本的均值向量μi:

(2)樣本類內(nèi)離散度矩陣Si：總類內(nèi)離散度矩陣Sw:第二步：計(jì)算最優(yōu)投影方向，并將樣本往該方向上投影。第三步：決策。在投影空間內(nèi)的決策準(zhǔn)則為:若y>y0,則x∈ω1,否則x∈ω2。Fisher線性判決步驟第一步：計(jì)算參量。(2)樣本類內(nèi)離散度矩陣Si：總類采用類似于人認(rèn)知錯(cuò)誤、糾正錯(cuò)誤、通過(guò)自學(xué)習(xí)改善自己認(rèn)識(shí)事物本領(lǐng)的過(guò)程，隨意確定判別函數(shù)初始值，該值在對(duì)樣本分類訓(xùn)練過(guò)程中逐步修正直至最終確定?；舅枷耄簩ふ乙粋€(gè)權(quán)向量，使規(guī)范化增廣樣本向量集的錯(cuò)分類樣本數(shù)最少。

3.2.3感知準(zhǔn)則函數(shù)

采用類似于人認(rèn)知錯(cuò)誤、糾正錯(cuò)誤、通過(guò)自學(xué)習(xí)改善自己認(rèn)識(shí)事物本一、基本概念1.線性可分性已知來(lái)自ω1和ω2兩類的樣本集{x1,x2,…,xN},兩類的線性判決函數(shù)為yi為增廣樣本向量,v為增廣權(quán)向量。線性可分：如果存在一個(gè)線性分類器能把每個(gè)樣本正確分類,即若存在一個(gè)權(quán)向量v,使得對(duì)于任何yi∈ω1,都有vTyi>0,而對(duì)于任何yi∈ω2,都有vTyi<0,

則稱這組樣本集線性可分;否則稱為線性不可分。反過(guò)來(lái),若樣本集是線性可分的,則必然存在一個(gè)權(quán)向量v,能將每個(gè)樣本正確地分類。

一、基本概念yi為增廣樣本向量,v為增廣權(quán)向量。線性可分

2.樣本的規(guī)范化如果樣本集{y1,y2,…,yN}線性可分,則一定存在某個(gè)或某些權(quán)向量v,使如果令，則vTzi>0。規(guī)范化增廣樣本向量

經(jīng)過(guò)這樣的變換后,我們可以不考慮樣本原來(lái)的類別標(biāo)志,只要找到一個(gè)對(duì)全部樣本zi都滿足vTzi>0(i=1,2,…,N)的權(quán)向量即可。樣本的規(guī)范化2.樣本的規(guī)范化如果令，則vTzi>0。規(guī)范化

3.解向量和解區(qū)

滿足vTzi>0(i=1,2,…,N)的權(quán)向量稱為解向量。若把v看成是權(quán)向量空間中的一點(diǎn),對(duì)于任一zi,vTzi=0在權(quán)向量空間確定了一個(gè)超平面,這個(gè)超平面把權(quán)空間分為兩個(gè)半空間,該超平面的法向量為zi,超平面正側(cè)的向量滿足vTzi>0。3.解向量和解區(qū)

相應(yīng)地,N個(gè)樣本確定了N個(gè)超平面,每個(gè)超平面把權(quán)空間分為兩個(gè)半空間。所以,滿足vTzi>0(i=1,2,…,N)的權(quán)向量必在這N個(gè)超平面正側(cè)的交疊區(qū),稱這一交疊區(qū)為解區(qū),解區(qū)中的任意向量都是解向量v*。相應(yīng)地,N個(gè)樣本確定了N個(gè)超平面,每二、感知準(zhǔn)則函數(shù)感知準(zhǔn)則函數(shù)方法利用錯(cuò)分類對(duì)現(xiàn)決策權(quán)向量進(jìn)行修正直至收斂。這種方法只對(duì)線性可分情況適用，并且只適用于兩類判決。感知準(zhǔn)則函數(shù)方法的思路是：先隨意找一個(gè)初始向量v，寫(xiě)作v(0)，然后用訓(xùn)練樣本集中的每個(gè)樣本來(lái)計(jì)算。一旦發(fā)現(xiàn)有的zi，使vTzi<0，則說(shuō)明當(dāng)前的廣義權(quán)向量v(0)不適合還需要進(jìn)一步修正。

二、感知準(zhǔn)則函數(shù)感知準(zhǔn)則函數(shù)方法利用錯(cuò)分類對(duì)現(xiàn)決策權(quán)向量進(jìn)行

設(shè)Z={z1,z2,…,zN}是經(jīng)過(guò)規(guī)范化的一組樣本集,定義感知準(zhǔn)則函數(shù):其中,Zk是被權(quán)向量v錯(cuò)分類的樣本集合,當(dāng)z∈Zk時(shí),有顯然,Jp(v)≥0。梯度下降算法求Jp(v)準(zhǔn)則函數(shù)的極小值。迭代公式為其中即Zk為第k步被錯(cuò)分的樣本集。ρk為正，是步長(zhǎng)系數(shù)。設(shè)Z={z1,z2,…,zN}是經(jīng)過(guò)規(guī)兩點(diǎn)說(shuō)明：感知準(zhǔn)則函數(shù)方法只是對(duì)線性可分樣本集有效，而對(duì)線性不可分的樣本集，該算法不能收斂。這一節(jié)對(duì)感知準(zhǔn)則函數(shù)的討論，只是很初步的。但這種利用錯(cuò)誤提供的信息，進(jìn)行自修正的思想意義是十分深遠(yuǎn)的。這種只解決線性分類的感知器稱為單層感知器，在此基礎(chǔ)上發(fā)展起來(lái)的多層感知器在原理上能解決非線性分類、多類劃分，以及非線性擬和非線性映射等多種問(wèn)題。兩點(diǎn)說(shuō)明：3.2.4最小平方誤差準(zhǔn)則函數(shù)

設(shè)由X={x1,x2,…,xN}得到的規(guī)范化增廣向量集合為{z1,z2,…,zN},分類器設(shè)計(jì)的任務(wù)就在于尋找一個(gè)矢量v,滿足:引入余量bi,用超平面:代替zTiv>0,則引入余量后的解區(qū)在原解區(qū)之內(nèi)。將上式寫(xiě)成矩陣形式即為3.2.4最小平方誤差準(zhǔn)則函數(shù)引入余量bi,用超平面定義誤差向量:定義平方誤差準(zhǔn)則函數(shù):Js(v)是一個(gè)非負(fù)函數(shù),當(dāng)有解時(shí),Js(v)達(dá)到最小值0,

此時(shí)的矢量v*滿足:v*能將所有樣本正確分類。若v*不能使某個(gè)樣本zj正確分類,即(v*)Tzj≠bj,則e2j=(vTzj－bj)2。錯(cuò)分樣本的結(jié)果是使Js(v)增大,因此,Js(v)越小越好,其最小值0為理想分類結(jié)果,實(shí)現(xiàn)所有樣本的正確分類。

求使Js(v)最小的v*有兩種方法:梯度下降法和解析法。定義誤差向量:定義平方誤差準(zhǔn)則函數(shù):Js(v)是一個(gè)非負(fù)

1.梯度下降法對(duì)Js(v)求梯度(3-78)相應(yīng)地,梯度下降算法為其中，ρk為學(xué)習(xí)速率;初值v(0)可任意選取。1.梯度下降法(3-78)相應(yīng)地,梯度下降算法為其

2.解析法解析法得到的是偽逆解。令Js(v)=0得(3-79)其中(3-80)ZTZ為(d+1)×(d+1)方陣,一般是滿秩的,因此有唯一解:(3-81)是Z的左逆矩陣,Z的右逆矩陣定義為(3-82)b的典型值為2.解析法(3-79)其中(3-80)ZTZ為(d+3.3分段線性分類器

線性分類器的分界面是一個(gè)超平面。當(dāng)類與類之間不能用任何一個(gè)超平面實(shí)現(xiàn)劃分時(shí),類間的分界面應(yīng)是一個(gè)超曲面。曲線可以由多個(gè)線段近似表達(dá),曲面可以由多個(gè)平面逼近,因此,可以用多個(gè)超平面近似表達(dá)超曲面,分段線性分類器正是基于這種思路而設(shè)計(jì)的一種分類器。3.3分段線性分類器

線性分類器的分界面是一線性判決函數(shù)只能解決線性可分問(wèn)題。在線性不可分的情況下，可以采用分段線性判別或二次函數(shù)判別等方法。分段線性判決函數(shù)確定的決策面是由若干段超平面組成的。

3.3.1分段線性分類器的定義線性判決函數(shù)只能解決線性可分問(wèn)題。3.3.1分段線性分類器

與線性判別函數(shù)相比，分段線性判別函數(shù)設(shè)計(jì)中首先要解決的問(wèn)題是分段線性判別函數(shù)的分段段數(shù)問(wèn)題。分段段數(shù)過(guò)少，其分類效果必然要差；但段數(shù)又要盡可能少，以免分類判別函數(shù)過(guò)于復(fù)雜，增加分類決策的計(jì)算量。在有些實(shí)際的分類問(wèn)題中，同一類樣本可以用若干個(gè)子類來(lái)描述，這些子類的數(shù)目就可作為確定分段段數(shù)的依據(jù)。在有些情況下樣本分布及合適子類劃分并不知道，往往需要采用一種聚類的方法，設(shè)法將樣本劃分成相對(duì)密集的子類，然后用各種方法設(shè)計(jì)各段判別函數(shù)。與線性判別函數(shù)相比，分段線性判別函數(shù)把屬于類ωi的樣本區(qū)域Ri分為li個(gè)兩兩不相交的子區(qū),對(duì)每個(gè)子類定義一個(gè)線性判決函數(shù):定義類ωi的判別函數(shù):判決準(zhǔn)則為若，則x∈ωj

稱gi(x)(i=1,2,…,m)為分段線性判決函數(shù),相應(yīng)的分類器稱為分段線性分類器。把屬于類ωi的樣本區(qū)域Ri分為li個(gè)兩兩不相交的子區(qū),當(dāng)類由多個(gè)子類構(gòu)成時(shí),其決策面方程是由各子類的判決函數(shù)確定的,若第i類的第n個(gè)子類和第j類的第k個(gè)子類相鄰,則該段決策面方程為其中,n∈{1,2,…,li},k∈{1,2,…,lj},li和lj分別表示第i類和第j類的子類數(shù)目。當(dāng)類由多個(gè)子類構(gòu)成時(shí),其決策面方程是由各子類的判決函數(shù)3.3.2分段線性距離分類器

正態(tài)分布條件下，兩類別問(wèn)題在各特征統(tǒng)計(jì)獨(dú)立、同方差、且先驗(yàn)概率相等情況下，最小錯(cuò)誤率決策可按最小距離決策，最小距離分類器的判決函數(shù)為

即這時(shí)類間的決策面為

它是兩類均值點(diǎn)連線的垂直平分面。<><>3.3.2分段線性距離分類器正態(tài)分布條件下顯然最小距離判別方法只有在各類別密集地分布在其均值附近時(shí)才有效。最小距離分類器兩類物體在特征空間的分布

對(duì)右圖所示的情況按最小距離計(jì)算，就會(huì)將原來(lái)ω１類的x決策成ω2類，如不對(duì)ω１類進(jìn)行子類劃分，或采用別的決策就不會(huì)取得好的效果。顯然最小距離判別方法只有在各類別密集地分布在其均值附近時(shí)才有右圖所示情況，若企圖再用每類一個(gè)均值代表點(diǎn)產(chǎn)生最小距離分類器，就會(huì)產(chǎn)生很明顯的錯(cuò)誤率。在這種情況下，可以將各類別劃分成相對(duì)密集的子類，每個(gè)子類以它們的均值作為代表點(diǎn)，然后按最小距離分類，可以有比較滿意的效果。對(duì)樣本進(jìn)行子類的合適劃分是分段線性距離分類器性能好壞的一個(gè)關(guān)鍵問(wèn)題。分段線性距離分類器示意圖右圖所示情況，若企圖再用每類一個(gè)均值代表點(diǎn)產(chǎn)生最小距離分類器歸納起來(lái)，如果對(duì)于ωi有l(wèi)i個(gè)子類，則有l(wèi)i個(gè)代表點(diǎn)，或者說(shuō)將類ωi的樣本區(qū)域Ri分為li個(gè)子區(qū):其中,。用mli表示Rli中的均值向量,并以此作為該子區(qū)的代表點(diǎn),確定判別函數(shù):則判決準(zhǔn)則為若，則x∈ωj

稱這種分類器為分段線性距離分類器。歸納起來(lái)，如果對(duì)于ωi有l(wèi)i個(gè)子類，則有l(wèi)i個(gè)代表點(diǎn)，或

注意：

線性距離分類器使用的是馬氏距離,分段線性距離分類器使用的則是歐幾里德距離,由最小距離分類器的導(dǎo)出過(guò)程可知,僅當(dāng)所有子區(qū)的協(xié)方差陣相同且等于σ2I時(shí),才具有較好的分類效果。注意：線性距離分類器使用的是馬氏距離,分段線性距離分設(shè)計(jì)分段線性分類器的前提條件是有一組已知類別的樣本集,其關(guān)鍵在于解決以下兩個(gè)問(wèn)題:(1)根據(jù)樣本集確定子類數(shù)目及各子類的劃分;

(2)利用樣本集計(jì)算各子類判別函數(shù)的權(quán)向量和閾值權(quán)。根據(jù)已知條件的不同,可以分別采取不同的方法。3.3.3分段線性分類器設(shè)計(jì)的一般考慮

(1)子類數(shù)目及各子類劃分已知；(2)子類數(shù)目已知,各子類劃分不知；(3)子類數(shù)目未知。設(shè)計(jì)分段線性分類器的前提條件是有一組已知類別的樣本集,其最初的近鄰法是由Cover和Hart于1968年提出的，是非參數(shù)法中最重要的方法之一。最小距離分類器將各類訓(xùn)練樣本劃分成若干子類，并在每個(gè)子類中確定代表點(diǎn)，一般用子類的均值或鄰近均值的某一樣本為代表點(diǎn)。實(shí)質(zhì)就是將樣本判屬于與代表點(diǎn)距離最近的類。該法的缺點(diǎn)是所選擇的代表點(diǎn)并不一定能很好地代表各類，其后果將使錯(cuò)誤率增加。3.4近鄰分類器最初的近鄰法是由Cover和Hart于1968年提出的，是非3.5.1最近鄰法一、最近鄰法的原理及判決準(zhǔn)則

近鄰法的基本思想：以全部訓(xùn)練樣本作為“代表點(diǎn)”，計(jì)算測(cè)試樣本與這些“代表點(diǎn)”，即所有樣本的距離，并以最近鄰者的類別作為決策。其主要特點(diǎn)就是將樣本判屬它的最近鄰（和它距離最近的代表點(diǎn)）所在的類。3.5.1最近鄰法一、最近鄰法的原理及判決準(zhǔn)則

假定有m個(gè)類別ω1,ω2,…,ωm的模式識(shí)別問(wèn)題,每類有Ni(i=1,2,…,m)個(gè)樣本,規(guī)定類ωi的判別函數(shù)為其中,表示第i類的第k個(gè)元素。判決準(zhǔn)則:

若，則x∈ωj

假定有m個(gè)類別ω1,ω2,…,第三章-線性判別分析非參數(shù)判別分類方法第四次課課件二、錯(cuò)誤率分析最近鄰法的錯(cuò)誤概率比最小錯(cuò)誤概率判決準(zhǔn)則的錯(cuò)誤概率要大，但是當(dāng)樣本數(shù)目無(wú)限時(shí)，它的錯(cuò)誤概率不會(huì)超過(guò)后者的錯(cuò)誤概率的一倍。假設(shè)近鄰分類器的漸近平均錯(cuò)誤概率為P∞,最小錯(cuò)誤概率判決準(zhǔn)則的錯(cuò)誤概率為P*e,那么它們之間存在如下關(guān)系:其中m為類別數(shù),PN(e)是當(dāng)樣本數(shù)為N時(shí)近鄰分類器的平均錯(cuò)誤概率。二、錯(cuò)誤率分析最近鄰法的錯(cuò)誤概率比最小錯(cuò)誤概率判決準(zhǔn)則的錯(cuò)誤圖中曲線與直線分別是近鄰法分類器當(dāng)N→∞時(shí)漸近平均錯(cuò)誤概率的上、下界,具體的P∞落在圖中陰影區(qū)內(nèi)。P∞的上、下界圖中曲線與直線分別是近鄰法分類器當(dāng)N→∞時(shí)漸近平均錯(cuò)誤概率的3.5.2k近鄰法一、k近鄰法的原理及判決準(zhǔn)則最近鄰分類器的判決思想是將樣本判屬與它距離最小的樣本所屬的類。這種方法的特點(diǎn)是概念容易理解，最近鄰樣本和待分類樣本在距離意義下是最相似的。其缺點(diǎn)在于受隨機(jī)噪聲影響較大，尤其是在兩類的交疊區(qū)內(nèi)。3.5.2k近鄰法一、k近鄰法的原理及判決準(zhǔn)則例如下圖有兩類樣本點(diǎn)。圖中有兩個(gè)待識(shí)別樣本，其中點(diǎn)1落在第一類較密集的區(qū)域內(nèi)，它屬于第一類的可能性較大，但點(diǎn)1的最近鄰為第二類的樣本，而該樣本對(duì)于第二類的區(qū)域而言屬于因較大的隨機(jī)誤差引起的樣本；點(diǎn)2落在第二類較密集的區(qū)域內(nèi)，屬于第二類的可能性較大，但點(diǎn)2的最近鄰為第一類的樣本，而該樣本對(duì)于第一類的區(qū)域而言屬于因較大的隨機(jī)誤差引起的樣本。隨機(jī)噪聲對(duì)最近鄰分類結(jié)果的影響例如下圖有兩類樣本點(diǎn)。圖中有兩個(gè)待識(shí)別樣本，其中點(diǎn)1落在第一對(duì)于待分類樣本x,在N個(gè)樣本集中找出它的k個(gè)近鄰,設(shè)k個(gè)樣本中屬于第i類的為ki個(gè)(i=1,2,…,m),即定義判別函數(shù):

判決準(zhǔn)則為若，則x∈ωj稱這種方法為k近鄰法,相應(yīng)的分類器稱為k近鄰分類器。

對(duì)于待分類樣本x,在N個(gè)樣本集中找出它的k個(gè)近鄰,設(shè)8近鄰示意圖

對(duì)于下圖中的樣本點(diǎn),若按8近鄰方法判決,則點(diǎn)1的8近鄰中,k1=6,k2=2,所以應(yīng)判屬第一類；點(diǎn)2的8近鄰中,k1=2,k2=6,所以應(yīng)判屬第二類。8近鄰示意圖對(duì)于下圖中的樣本點(diǎn),若按8近鄰方法判二、錯(cuò)誤率分析

k近鄰一般采用k為奇數(shù)，跟投票表決一樣，避免因兩種票數(shù)相等而難以決策。

k近鄰分類器的漸近平均錯(cuò)誤概率也滿足:其中,P*e為最小錯(cuò)誤概率的貝葉斯分類器的錯(cuò)誤概率。二、錯(cuò)誤率分析k近鄰一般采用k為奇數(shù)，跟投票表決一樣近鄰法優(yōu)點(diǎn)：在模板數(shù)量很大時(shí)其錯(cuò)誤率指標(biāo)還是相當(dāng)不錯(cuò)的。缺點(diǎn)：需要存儲(chǔ)全部訓(xùn)練樣本，另外有繁重的距離計(jì)算量，即計(jì)算量大，存儲(chǔ)量大。剪輯近鄰法與壓縮近鄰法就是兩種有代表性的改進(jìn)方法。

3.5.3近鄰法的改進(jìn)方法近鄰法3.5.3近鄰法的改進(jìn)方法剪輯近鄰法，其基本原理是在原有樣本集中挑選出對(duì)分類計(jì)算有效的樣本，將不同類別交界處的樣本以適當(dāng)方式進(jìn)行篩選，把處于交界處的訓(xùn)練樣本給剪輯掉，使樣本總數(shù)合理地減少，以同時(shí)達(dá)到既減少計(jì)算量，又減少存儲(chǔ)量的雙重效果。壓縮近鄰法，其基本原理是對(duì)樣本集進(jìn)行組織與整理，分群分層，盡可能將計(jì)算壓縮到在接近測(cè)試樣本鄰域的小范圍內(nèi)，避免盲目地與訓(xùn)練樣本集中每個(gè)樣本進(jìn)行距離計(jì)算。第三章-線性判別分析非參數(shù)判別分類方法第四次課課件一、剪輯近鄰法

剪輯近鄰法著眼于如何減少模板樣本數(shù)目，從而可同時(shí)減少分類時(shí)的計(jì)算量及模板樣本的存儲(chǔ)量，同時(shí)還能進(jìn)一步改進(jìn)分類器的性能，如降低錯(cuò)誤率等要求。剪輯近鄰法的基本思想是從這樣一個(gè)現(xiàn)象出發(fā)的，即當(dāng)不同類別的樣本在分布上有交迭部分，分類的錯(cuò)誤率主要來(lái)自處于交迭區(qū)中的樣本。當(dāng)我們得到一個(gè)作為識(shí)別用的參考樣本集時(shí)，由于不同類別交迭區(qū)域中不同類別的樣本彼此穿插，導(dǎo)致用近鄰法分類出錯(cuò)。因此如果能將不同類別交界處的樣本以適當(dāng)方式篩選，可以實(shí)現(xiàn)既減少樣本數(shù)又提高正確識(shí)別率的雙重目的。為此可以利用現(xiàn)有樣本集對(duì)其自身進(jìn)行剪輯。

第三章-線性判別分析非參數(shù)判別分類方法第四次課課件

用近鄰法容易出錯(cuò)的區(qū)域是在兩類的交界處，這時(shí)某個(gè)訓(xùn)練樣本存在與否就會(huì)影響到某些測(cè)試分類的結(jié)果。因此剪輯的效果往往把這些處于交界的訓(xùn)練樣本給剪輯掉了。用近鄰法容易出錯(cuò)的區(qū)域是在兩類的交界處，這時(shí)某個(gè)二、壓縮近鄰法

剪輯近鄰法所得到的剪輯樣本集在樣本數(shù)量的壓縮方面并不十分明顯，它的作用在于將原樣本集中處于邊界處的樣本刪除掉，但靠近兩類中心的大部分樣本仍被保留下來(lái)。然而按近鄰規(guī)則來(lái)看，這些樣本中的大多數(shù)對(duì)分類決策沒(méi)什么用處，如能在剪輯的基礎(chǔ)上再去掉一部分這樣的樣本，將有助于進(jìn)一步縮短計(jì)算時(shí)間與壓縮存儲(chǔ)量。其實(shí)處于同一類樣本密集區(qū)的測(cè)試樣本并不一定要全部保留，幾乎絕大部分都可去掉，只要保留若干個(gè)訓(xùn)練樣本即可。問(wèn)題是保留哪些好。壓縮近鄰法采用了用測(cè)試集測(cè)試的辦法，采用只要分類有錯(cuò)，在出錯(cuò)處添加一個(gè)訓(xùn)練樣本的做法。二、壓縮近鄰法

壓縮近鄰法壓縮樣本的思想很簡(jiǎn)單，它利用現(xiàn)有樣本集，逐漸生成一個(gè)新的樣本集。使該樣本集在保留最少量樣本的條件下,仍能對(duì)原有樣本的全部用最近鄰法正確分類，那末該樣本集也就能對(duì)待識(shí)別樣本進(jìn)行分類,并保持正常識(shí)別率。該算法的作法也十分簡(jiǎn)單，它定義兩個(gè)存儲(chǔ)器，一個(gè)用來(lái)存放即將生成的樣本集，稱為Store；另一存儲(chǔ)器則存放原樣本集，稱為Grabbag。壓縮近鄰法壓縮樣本的思想很簡(jiǎn)單，它利用現(xiàn)有樣本集，逐漸生成一1.［初始化］Store是空集，原樣本集存入Grabbag；從Grabbag中任意選擇一樣本放入Store中作為新樣本集的第一個(gè)樣本。

2.［樣本集生成］在Grabbag中取出第i個(gè)樣本用Store中的當(dāng)前樣本集按最近鄰法分類。若分類錯(cuò)誤，則將該樣本從Grabbag轉(zhuǎn)入Store中，若分類正確，則將該樣本放回Grabbag中，對(duì)Grabbag中所有樣本重復(fù)上述過(guò)程。

3.［結(jié)束過(guò)程］若Grabbag中所有樣本在執(zhí)行第二步時(shí)沒(méi)有發(fā)生轉(zhuǎn)入Store的現(xiàn)象，或Grabbag已成空集，則算法終止，否則轉(zhuǎn)入第二步。在算法終止后，Store中的樣本集作為壓縮樣本集，可用來(lái)對(duì)待識(shí)別樣本按最近鄰法分類。壓縮近鄰法算法步驟：1.［初始化］Store是空集，原樣本集存入Grabba本章小結(jié)參數(shù)判別分類方法與非參數(shù)判別分類方法線性判別函數(shù)和決策面方程Fisher線性判決準(zhǔn)則感知準(zhǔn)則函數(shù)最小平方誤差準(zhǔn)則函數(shù)分段線性分類器近鄰分類器本章小結(jié)參數(shù)判別分類方法與非參數(shù)判別分類方法參數(shù)判別分類方法與非參數(shù)判別分類方法參數(shù)判別方法：適用條件：前提是清楚特征空間中的各類樣本的分布，一旦待分類樣本的特征向量值x已知，就可以確定x對(duì)各類的后驗(yàn)概率，也就可按相應(yīng)的準(zhǔn)則計(jì)算與分類。參數(shù)分類判別方法一般只能用在有統(tǒng)計(jì)知識(shí)的場(chǎng)合，或能利用訓(xùn)練樣本估計(jì)出參數(shù)的場(chǎng)合。

判別函數(shù)類型如何確定？判別函數(shù)及決策面方程的類別確定是由樣本分布規(guī)律決定的，例如，符合某種條件就可使用線性分類器，正態(tài)分布條件下一般適合用二次函數(shù)決策面。參數(shù)判別分類方法與非參數(shù)判別分類方法參數(shù)判別方法：參數(shù)判別分類方法與非參數(shù)判別分類方法非參數(shù)分類判別方法：直接利用訓(xùn)練樣本集，省去參數(shù)估計(jì)這一環(huán)節(jié)，根據(jù)一些準(zhǔn)則(如Fisher準(zhǔn)則、感知準(zhǔn)則函數(shù))來(lái)設(shè)計(jì)分類器。

判別函數(shù)類型如何確定？在非參數(shù)判別方法的設(shè)計(jì)中，使用什么典型的分類決策方法預(yù)先由設(shè)計(jì)者確定，然后利用訓(xùn)練樣本集提供的信息確定這些函數(shù)中的參數(shù)。這是參數(shù)與非參數(shù)判別方法的一個(gè)重要不同點(diǎn)。參數(shù)判別分類方法與非參數(shù)判別分類方法非參數(shù)分類判別方法：非參數(shù)分類判別方法的基本做法：

使用非參數(shù)分類判別方法進(jìn)行分類器設(shè)計(jì)主要包含兩個(gè)步驟：選擇函數(shù)類型與確定參數(shù)。確定使用的判別函數(shù)類型或決策面方程類型，如線性分類器、非線性分類器、分段線性分類器或近鄰法等。在選定的函數(shù)類型條件下，確定相應(yīng)的參數(shù)，從而完成整個(gè)分類器設(shè)計(jì)。非參數(shù)分類判別方法的基本做法：

其中wi是權(quán)向量,wi0是一個(gè)常數(shù)，稱為閾值權(quán)。設(shè)樣本在d維特征空間中描述，兩類問(wèn)題線性判別函數(shù)的一般形式可表示成判決準(zhǔn)則的可以表示為

線性判別函數(shù)和決策面方程其中wi是權(quán)向量,wi0是一個(gè)常數(shù)，稱為閾值權(quán)。設(shè)樣本在在線性判別函數(shù)條件下，它是d維空間的一個(gè)超平面。相應(yīng)的決策面方程為其中,在線性判別函數(shù)條件下，它是d維空間的一個(gè)超平面。相應(yīng)的決策面基本思想：尋找一個(gè)最好的投影方向，當(dāng)特征向量從d

維空間映射到這個(gè)方向時(shí)，兩類能最好地分開(kāi)。Fisher準(zhǔn)則函數(shù)的基本思路：向量w的方向選擇應(yīng)能使兩類樣本在該向量上投影的交迭部分最少,投影的均值之差盡可能大些，而使類內(nèi)樣本的離散程度盡可能小。Fisher線性判決準(zhǔn)則基本思想：尋找一個(gè)最好的投影方向，當(dāng)特征向量從d維空間映射

第一步：計(jì)算參量。

(1)各類樣本的均值向量μi:

(2)樣本類內(nèi)離散度矩陣Si總類內(nèi)離散度矩陣Sw:第二步：計(jì)算最優(yōu)投影方向，并將樣本往該方向上投影。第三步：決策。在投影空間內(nèi)的決策準(zhǔn)則為:若y>y0,則x∈ω1,否則x∈ω2。步驟第一步：計(jì)算參量。(2)樣本類內(nèi)離散度矩陣Si總感知準(zhǔn)則函數(shù)這種方法只對(duì)線性可分情況適用。適用于兩類判決?；舅枷耄簩ふ乙粋€(gè)增廣權(quán)向量v，使規(guī)范化增廣樣本向量集的錯(cuò)分類樣本數(shù)最少。感知準(zhǔn)則函數(shù)這種方法只對(duì)線性可分情況適用。適用于兩類判決?；兄獪?zhǔn)則函數(shù)方法的思路是：先隨意找一個(gè)初始向量v，寫(xiě)作v(0)，然后用訓(xùn)練樣本集中的每個(gè)樣本來(lái)計(jì)算。一旦發(fā)現(xiàn)有的zi，使vTzi<0，則說(shuō)明當(dāng)前的廣義權(quán)向量v(0)不適合還需要進(jìn)一步修正。

感知準(zhǔn)則函數(shù)基本思想：尋找一個(gè)增廣權(quán)向量v，使規(guī)范化增廣樣本向量集的錯(cuò)分類樣本數(shù)最少。這種方法只對(duì)線性可分情況適用，并且適用于兩類判決。感知準(zhǔn)則函數(shù)方法的思路是：先隨意找一個(gè)初始向量v，寫(xiě)作v(0

設(shè)Z={z1,z2,…,zN}是經(jīng)過(guò)規(guī)范化的一組樣本集,定義感知準(zhǔn)則函數(shù):其中,Zk是被權(quán)向量v錯(cuò)分類的樣本集合,當(dāng)z∈Zk時(shí),有顯然,Jp(v)≥0。梯度下降算法求Jp(v)準(zhǔn)則函數(shù)的極小值。迭代公式為其中即Zk為第k步被錯(cuò)分的樣本集。ρk為正，是步長(zhǎng)系數(shù)。設(shè)Z={z1,z2,…,zN}是經(jīng)過(guò)規(guī)最小平方誤差準(zhǔn)則函數(shù)Js(v)越小越好,其最小值0為理想分類結(jié)果,實(shí)現(xiàn)所有樣本的正確分類。平方誤差準(zhǔn)則函數(shù)Js(v)為最小平方誤差準(zhǔn)則函數(shù)Js(v)越小越好,其分段線性距離分類器

正態(tài)分布條件下，兩類別問(wèn)題在各特征統(tǒng)計(jì)獨(dú)立、同方差、且先驗(yàn)概率相等情況下，最小錯(cuò)誤率決策可按最小距離決策，最小距離分類器的判決函數(shù)為

即這時(shí)類間的決策面為

它是兩類均值點(diǎn)連線的垂直平分面。<><>分段線性距離分類器正態(tài)分布條件下，兩類別問(wèn)題近鄰法

基本特點(diǎn)：將樣本集中的任何一個(gè)樣本都作為代表點(diǎn)。實(shí)質(zhì)：將樣本判屬于與代表點(diǎn)距離最近的類。近鄰法基本特點(diǎn)：將樣本集中的任何一個(gè)樣本都作為代表點(diǎn)。對(duì)于待分類樣本x,在N個(gè)樣本集中找出它的k個(gè)近鄰,設(shè)k個(gè)樣本中屬于第i類的為ki個(gè)(i=1,2,…,m),即定義判別函數(shù):

判決準(zhǔn)則為若，則x∈ωjk近鄰法對(duì)于待分類樣本x,在N個(gè)樣本集中找出它的k個(gè)近鄰,設(shè)習(xí)題

1.對(duì)于線性判決函數(shù):

(1)將判別函數(shù)寫(xiě)成g(x)=wTx+w0的形式,畫(huà)出

H:g(x)=0的幾何圖形,標(biāo)出權(quán)向量并確定決策區(qū)域R1和R2。(2)化成增廣權(quán)向量和增廣向量的形式:g(x)=vTy。習(xí)題1.對(duì)于線性判決函數(shù):(1)將判別2.有七個(gè)二維向量:，，，假定前三個(gè)為ω1類,后四個(gè)為ω2類。

(1)畫(huà)出最近鄰法決策區(qū)域;

(2)求樣本均值μ1、μ2;若按離樣本均值距離的大小進(jìn)行分類,試畫(huà)出決策區(qū)域。

2.有七個(gè)二維向量:，，，假定前三個(gè)為ω1類,后四第三章-線性判別分析非參數(shù)判別分類方法第四次課課件第三章線性判別分析——非參數(shù)判別分類方法第三章線性判別分析本章內(nèi)容3.1

線性判別函數(shù)3.2線性分類器Fisher線性判決感知準(zhǔn)則函數(shù)3.3分段線性分類器3.4近鄰分類器總結(jié)習(xí)題本章內(nèi)容3.1線性判別函數(shù)3.2.2Fisher線性判決

Fisher線性判決的基本思想是尋找一個(gè)最好的投影方向,當(dāng)特征向量x從d維空間映射到這個(gè)方向上時(shí),兩類能最好地分開(kāi)。這個(gè)方法實(shí)際上涉及特征維數(shù)的壓縮問(wèn)題。3.2線性分類器3.2.2Fisher線性判決3.2線性分類器分析w1方向之所以比w2方向優(yōu)越,可以歸納出這樣一個(gè)準(zhǔn)則：即向量w的方向選擇應(yīng)能使兩類樣本投影的均值之差盡可能大些,而使類內(nèi)樣本的離散程度盡可能小。這就是Fisher準(zhǔn)則函數(shù)的基本思路。分析w1方向之所以比w2方向優(yōu)越,可以歸納出這樣一個(gè)第一步：計(jì)算參量。(1)各類樣本的均值向量μi:

(2)樣本類內(nèi)離散度矩陣Si：總類內(nèi)離散度矩陣Sw:第二步：計(jì)算最優(yōu)投影方向，并將樣本往該方向上投影。第三步：決策。在投影空間內(nèi)的決策準(zhǔn)則為:若y>y0,則x∈ω1,否則x∈ω2。Fisher線性判決步驟第一步：計(jì)算參量。(2)樣本類內(nèi)離散度矩陣Si：總類采用類似于人認(rèn)知錯(cuò)誤、糾正錯(cuò)誤、通過(guò)自學(xué)習(xí)改善自己認(rèn)識(shí)事物本領(lǐng)的過(guò)程，隨意確定判別函數(shù)初始值，該值在對(duì)樣本分類訓(xùn)練過(guò)程中逐步修正直至最終確定?；舅枷耄簩ふ乙粋€(gè)權(quán)向量，使規(guī)范化增廣樣本向量集的錯(cuò)分類樣本數(shù)最少。

3.2.3感知準(zhǔn)則函數(shù)

采用類似于人認(rèn)知錯(cuò)誤、糾正錯(cuò)誤、通過(guò)自學(xué)習(xí)改善自己認(rèn)識(shí)事物本一、基本概念1.線性可分性已知來(lái)自ω1和ω2兩類的樣本集{x1,x2,…,xN},兩類的線性判決函數(shù)為yi為增廣樣本向量,v為增廣權(quán)向量。線性可分：如果存在一個(gè)線性分類器能把每個(gè)樣本正確分類,即若存在一個(gè)權(quán)向量v,使得對(duì)于任何yi∈ω1,都有vTyi>0,而對(duì)于任何yi∈ω2,都有vTyi<0,

則稱這組樣本集線性可分;否則稱為線性不可分。反過(guò)來(lái),若樣本集是線性可分的,則必然存在一個(gè)權(quán)向量v,能將每個(gè)樣本正確地分類。

一、基本概念yi為增廣樣本向量,v為增廣權(quán)向量。線性可分

2.樣本的規(guī)范化如果樣本集{y1,y2,…,yN}線性可分,則一定存在某個(gè)或某些權(quán)向量v,使如果令，則vTzi>0。規(guī)范化增廣樣本向量

經(jīng)過(guò)這樣的變換后,我們可以不考慮樣本原來(lái)的類別標(biāo)志,只要找到一個(gè)對(duì)全部樣本zi都滿足vTzi>0(i=1,2,…,N)的權(quán)向量即可。樣本的規(guī)范化2.樣本的規(guī)范化如果令，則vTzi>0。規(guī)范化

3.解向量和解區(qū)

滿足vTzi>0(i=1,2,…,N)的權(quán)向量稱為解向量。若把v看成是權(quán)向量空間中的一點(diǎn),對(duì)于任一zi,vTzi=0在權(quán)向量空間確定了一個(gè)超平面,這個(gè)超平面把權(quán)空間分為兩個(gè)半空間,該超平面的法向量為zi,超平面正側(cè)的向量滿足vTzi>0。3.解向量和解區(qū)

相應(yīng)地,N個(gè)樣本確定了N個(gè)超平面,每個(gè)超平面把權(quán)空間分為兩個(gè)半空間。所以,滿足vTzi>0(i=1,2,…,N)的權(quán)向量必在這N個(gè)超平面正側(cè)的交疊區(qū),稱這一交疊區(qū)為解區(qū),解區(qū)中的任意向量都是解向量v*。相應(yīng)地,N個(gè)樣本確定了N個(gè)超平面,每二、感知準(zhǔn)則函數(shù)感知準(zhǔn)則函數(shù)方法利用錯(cuò)分類對(duì)現(xiàn)決策權(quán)向量進(jìn)行修正直至收斂。這種方法只對(duì)線性可分情況適用，并且只適用于兩類判決。感知準(zhǔn)則函數(shù)方法的思路是：先隨意找一個(gè)初始向量v，寫(xiě)作v(0)，然后用訓(xùn)練樣本集中的每個(gè)樣本來(lái)計(jì)算。一旦發(fā)現(xiàn)有的zi，使vTzi<0，則說(shuō)明當(dāng)前的廣義權(quán)向量v(0)不適合還需要進(jìn)一步修正。

二、感知準(zhǔn)則函數(shù)感知準(zhǔn)則函數(shù)方法利用錯(cuò)分類對(duì)現(xiàn)決策權(quán)向量進(jìn)行

設(shè)Z={z1,z2,…,zN}是經(jīng)過(guò)規(guī)范化的一組樣本集,定義感知準(zhǔn)則函數(shù):其中,Zk是被權(quán)向量v錯(cuò)分類的樣本集合,當(dāng)z∈Zk時(shí),有顯然,Jp(v)≥0。梯度下降算法求Jp(v)準(zhǔn)則函數(shù)的極小值。迭代公式為其中即Zk為第k步被錯(cuò)分的樣本集。ρk為正，是步長(zhǎng)系數(shù)。設(shè)Z={z1,z2,…,zN}是經(jīng)過(guò)規(guī)兩點(diǎn)說(shuō)明：感知準(zhǔn)則函數(shù)方法只是對(duì)線性可分樣本集有效，而對(duì)線性不可分的樣本集，該算法不能收斂。這一節(jié)對(duì)感知準(zhǔn)則函數(shù)的討論，只是很初步的。但這種利用錯(cuò)誤提供的信息，進(jìn)行自修正的思想意義是十分深遠(yuǎn)的。這種只解決線性分類的感知器稱為單層感知器，在此基礎(chǔ)上發(fā)展起來(lái)的多層感知器在原理上能解決非線性分類、多類劃分，以及非線性擬和非線性映射等多種問(wèn)題。兩點(diǎn)說(shuō)明：3.2.4最小平方誤差準(zhǔn)則函數(shù)

設(shè)由X={x1,x2,…,xN}得到的規(guī)范化增廣向量集合為{z1,z2,…,zN},分類器設(shè)計(jì)的任務(wù)就在于尋找一個(gè)矢量v,滿足:引入余量bi,用超平面:代替zTiv>0,則引入余量后的解區(qū)在原解區(qū)之內(nèi)。將上式寫(xiě)成矩陣形式即為3.2.4最小平方誤差準(zhǔn)則函數(shù)引入余量bi,用超平面定義誤差向量:定義平方誤差準(zhǔn)則函數(shù):Js(v)是一個(gè)非負(fù)函數(shù),當(dāng)有解時(shí),Js(v)達(dá)到最小值0,

此時(shí)的矢量v*滿足:v*能將所有樣本正確分類。若v*不能使某個(gè)樣本zj正確分類,即(v*)Tzj≠bj,則e2j=(vTzj－bj)2。錯(cuò)分樣本的結(jié)果是使Js(v)增大,因此,Js(v)越小越好,其最小值0為理想分類結(jié)果,實(shí)現(xiàn)所有樣本的正確分類。

求使Js(v)最小的v*有兩種方法:梯度下降法和解析法。定義誤差向量:定義平方誤差準(zhǔn)則函數(shù):Js(v)是一個(gè)非負(fù)

1.梯度下降法對(duì)Js(v)求梯度(3-78)相應(yīng)地,梯度下降算法為其中，ρk為學(xué)習(xí)速率;初值v(0)可任意選取。1.梯度下降法(3-78)相應(yīng)地,梯度下降算法為其

2.解析法解析法得到的是偽逆解。令Js(v)=0得(3-79)其中(3-80)ZTZ為(d+1)×(d+1)方陣,一般是滿秩的,因此有唯一解:(3-81)是Z的左逆矩陣,Z的右逆矩陣定義為(3-82)b的典型值為2.解析法(3-79)其中(3-80)ZTZ為(d+3.3分段線性分類器

線性分類器的分界面是一個(gè)超平面。當(dāng)類與類之間不能用任何一個(gè)超平面實(shí)現(xiàn)劃分時(shí),類間的分界面應(yīng)是一個(gè)超曲面。曲線可以由多個(gè)線段近似表達(dá),曲面可以由多個(gè)平面逼近,因此,可以用多個(gè)超平面近似表達(dá)超曲面,分段線性分類器正是基于這種思路而設(shè)計(jì)的一種分類器。3.3分段線性分類器

線性分類器的分界面是一線性判決函數(shù)只能解決線性可分問(wèn)題。在線性不可分的情況下，可以采用分段線性判別或二次函數(shù)判別等方法。分段線性判決函數(shù)確定的決策面是由若干段超平面組成的。

3.3.1分段線性分類器的定義線性判決函數(shù)只能解決線性可分問(wèn)題。3.3.1分段線性分類器

與線性判別函數(shù)相比，分段線性判別函數(shù)設(shè)計(jì)中首先要解決的問(wèn)題是分段線性判別函數(shù)的分段段數(shù)問(wèn)題。分段段數(shù)過(guò)少，其分類效果必然要差；但段數(shù)又要盡可能少，以免分類判別函數(shù)過(guò)于復(fù)雜，增加分類決策的計(jì)算量。在有些實(shí)際的分類問(wèn)題中，同一類樣本可以用若干個(gè)子類來(lái)描述，這些子類的數(shù)目就可作為確定分段段數(shù)的依據(jù)。在有些情況下樣本分布及合適子類劃分并不知道，往往需要采用一種聚類的方法，設(shè)法將樣本劃分成相對(duì)密集的子類，然后用各種方法設(shè)計(jì)各段判別函數(shù)。與線性判別函數(shù)相比，分段線性判別函數(shù)把屬于類ωi的樣本區(qū)域Ri分為li個(gè)兩兩不相交的子區(qū),對(duì)每個(gè)子類定義一個(gè)線性判決函數(shù):定義類ωi的判別函數(shù):判決準(zhǔn)則為若，則x∈ωj

稱gi(x)(i=1,2,…,m)為分段線性判決函數(shù),相應(yīng)的分類器稱為分段線性分類器。把屬于類ωi的樣本區(qū)域Ri分為li個(gè)兩兩不相交的子區(qū),當(dāng)類由多個(gè)子類構(gòu)成時(shí),其決策面方程是由各子類的判決函數(shù)確定的,若第i類的第n個(gè)子類和第j類的第k個(gè)子類相鄰,則該段決策面方程為其中,n∈{1,2,…,li},k∈{1,2,…,lj},li和lj分別表示第i類和第j類的子類數(shù)目。當(dāng)類由多個(gè)子類構(gòu)成時(shí),其決策面方程是由各子類的判決函數(shù)3.3.2分段線性距離分類器

正態(tài)分布條件下，兩類別問(wèn)題在各特征統(tǒng)計(jì)獨(dú)立、同方差、且先驗(yàn)概率相等情況下，最小錯(cuò)誤率決策可按最小距離決策，最小距離分類器的判決函數(shù)為

即這時(shí)類間的決策面為

它是兩類均值點(diǎn)連線的垂直平分面。<><>3.3.2分段線性距離分類器正態(tài)分布條件下顯然最小距離判別方法只有在各類別密集地分布在其均值附近時(shí)才有效。最小距離分類器兩類物體在特征空間的分布

對(duì)右圖所示的情況按最小距離計(jì)算，就會(huì)將原來(lái)ω１類的x決策成ω2類，如不對(duì)ω１類進(jìn)行子類劃分，或采用別的決策就不會(huì)取得好的效果。顯然最小距離判別方法只有在各類別密集地分布在其均值附近時(shí)才有右圖所示情況，若企圖再用每類一個(gè)均值代表點(diǎn)產(chǎn)生最小距離分類器，就會(huì)產(chǎn)生很明顯的錯(cuò)誤率。在這種情況下，可以將各類別劃分成相對(duì)密集的子類，每個(gè)子類以它們的均值作為代表點(diǎn)，然后按最小距離分類，可以有比較滿意的效果。對(duì)樣本進(jìn)行子類的合適劃分是分段線性距離分類器性能好壞的一個(gè)關(guān)鍵問(wèn)題。分段線性距離分類器示意圖右圖所示情況，若企圖再用每類一個(gè)均值代表點(diǎn)產(chǎn)生最小距離分類器歸納起來(lái)，如果對(duì)于ωi有l(wèi)i個(gè)子類，則有l(wèi)i個(gè)代表點(diǎn)，或者說(shuō)將類ωi的樣本區(qū)域Ri分為li個(gè)子區(qū):其中,。用mli表示Rli中的均值向量,并以此作為該子區(qū)的代表點(diǎn),確定判別函數(shù):則判決準(zhǔn)則為若，則x∈ωj

稱這種分類器為分段線性距離分類器。歸納起來(lái)，如果對(duì)于ωi有l(wèi)i個(gè)子類，則有l(wèi)i個(gè)代表點(diǎn)，或

注意：

線性距離分類器使用的是馬氏距離,分段線性距離分類器使用的則是歐幾里德距離,由最小距離分類器的導(dǎo)出過(guò)程可知,僅當(dāng)所有子區(qū)的協(xié)方差陣相同且等于σ2I時(shí),才具有較好的分類效果。注意：線性距離分類器使用的是馬氏距離,分段線性距離分設(shè)計(jì)分段線性分類器的前提條件是有一組已知類別的樣本集,其關(guān)鍵在于解決以下兩個(gè)問(wèn)題:(1)根據(jù)樣本集確定子類數(shù)目及各子類的劃分;

(2)利用樣本集計(jì)算各子類判別函數(shù)的權(quán)向量和閾值權(quán)。根據(jù)已知條件的不同,可以分別采取不同的方法。3.3.3分段線性分類器設(shè)計(jì)的一般考慮

(1)子類數(shù)目及各子類劃分已知；(2)子類數(shù)目已知,各子類劃分不知；(3)子類數(shù)目未知。設(shè)計(jì)分段線性分類器的前提條件是有一組已知類別的樣本集,其最初的近鄰法是由Cover和Hart于1968年提出的，是非參數(shù)法中最重要的方法之一。最小距離分類器將各類訓(xùn)練樣本劃分成若干子類，并在每個(gè)子類中確定代表點(diǎn)，一般用子類的均值或鄰近均值的某一樣本為代表點(diǎn)。實(shí)質(zhì)就是將樣本判屬于與代表點(diǎn)距離最近的類。該法的缺點(diǎn)是所選擇的代表點(diǎn)并不一定能很好地代表各類，其后果將使錯(cuò)誤率增加。3.4近鄰分類器最初的近鄰法是由Cover和Hart于1968年提出的，是非3.5.1最近鄰法一、最近鄰法的原理及判決準(zhǔn)則

近鄰法的基本思想：以全部訓(xùn)練樣本作為“代表點(diǎn)”，計(jì)算測(cè)試樣本與這些“代表點(diǎn)”，即所有樣本的距離，并以最近鄰者的類別作為決策。其主要特點(diǎn)就是將樣本判屬它的最近鄰（和它距離最近的代表點(diǎn)）所在的類。3.5.1最近鄰法一、最近鄰法的原理及判決準(zhǔn)則

假定有m個(gè)類別ω1,ω2,…,ωm的模式識(shí)別問(wèn)題,每類有Ni(i=1,2,…,m)個(gè)樣本,規(guī)定類ωi的判別函數(shù)為其中,表示第i類的第k個(gè)元素。判決準(zhǔn)則:

若，則x∈ωj

假定有m個(gè)類別ω1,ω2,…,第三章-線性判別分析非參數(shù)判別分類方法第四次課課件二、錯(cuò)誤率分析最近鄰法的錯(cuò)誤概率比最小錯(cuò)誤概率判決準(zhǔn)則的錯(cuò)誤概率要大，但是當(dāng)樣本數(shù)目無(wú)限時(shí)，它的錯(cuò)誤概率不會(huì)超過(guò)后者的錯(cuò)誤概率的一倍。假設(shè)近鄰分類器的漸近平均錯(cuò)誤概率為P∞,最小錯(cuò)誤概率判決準(zhǔn)則的錯(cuò)誤概率為P*e,那么它們之間存在如下關(guān)系:其中m為類別數(shù),PN(e)是當(dāng)樣本數(shù)為N時(shí)近鄰分類器的平均錯(cuò)誤概率。二、錯(cuò)誤率分析最近鄰法的錯(cuò)誤概率比最小錯(cuò)誤概率判決準(zhǔn)則的錯(cuò)誤圖中曲線與直線分別是近鄰法分類器當(dāng)N→∞時(shí)漸近平均錯(cuò)誤概率的上、下界,具體的P∞落在圖中陰影區(qū)內(nèi)。P∞的上、下界圖中曲線與直線分別是近鄰法分類器當(dāng)N→∞時(shí)漸近平均錯(cuò)誤概率的3.5.2k近鄰法一、k近鄰法的原理及判決準(zhǔn)則最近鄰分類器的判決思想是將樣本判屬與它距離最小的樣本所屬的類。這種方法的特點(diǎn)是概念容易理解，最近鄰樣本和待分類樣本在距離意義下是最相似的。其缺點(diǎn)在于受隨機(jī)噪聲影響較大，尤其是在兩類的交疊區(qū)內(nèi)。3.5.2k近鄰法一、k近鄰法的原理及判決準(zhǔn)則例如下圖有兩類樣本點(diǎn)。圖中有兩個(gè)待識(shí)別樣本，其中點(diǎn)1落在第一類較密集的區(qū)域內(nèi)，它屬于第一類的可能性較大，但點(diǎn)1的最近鄰為第二類的樣本，而該樣本對(duì)于第二類的區(qū)域而言屬于因較大的隨機(jī)誤差引起的樣本；點(diǎn)2落在第二類較密集的區(qū)域內(nèi)，屬于第二類的可能性較大，但點(diǎn)2的最近鄰為第一類的樣本，而該樣本對(duì)于第一類的區(qū)域而言屬于因較大的隨機(jī)誤差引起的樣本。隨機(jī)噪聲對(duì)最近鄰分類結(jié)果的影響例如下圖有兩類樣本點(diǎn)。圖中有兩個(gè)待識(shí)別樣本，其中點(diǎn)1落在第一對(duì)于待分類樣本x,在N個(gè)樣本集中找出它的k個(gè)近鄰,設(shè)k個(gè)樣本中屬于第i類的為ki個(gè)(i=1,2,…,m),即定義判別函數(shù):

判決準(zhǔn)則為若，則x∈ωj稱這種方法為k近鄰法,相應(yīng)的分類器稱為k近鄰分類器。

對(duì)于待分類樣本x,在N個(gè)樣本集中找出它的k個(gè)近鄰,設(shè)8近鄰示意圖

對(duì)于下圖中的樣本點(diǎn),若按8近鄰方法判決,則點(diǎn)1的8近鄰中,k1=6,k2=2,所以應(yīng)判屬第一類；點(diǎn)2的8近鄰中,k1=2,k2=6,所以應(yīng)判屬第二類。8近鄰示意圖對(duì)于下圖中的樣本點(diǎn),若按8近鄰方法判二、錯(cuò)誤率分析

k近鄰一般采用k為奇數(shù)，跟投票表決一樣，避免因兩種票數(shù)相等而難以決策。

k近鄰分類器的漸近平均錯(cuò)誤概率也滿足:其中,P*e為最小錯(cuò)誤概率的貝葉斯分類器的錯(cuò)誤概率。二、錯(cuò)誤率分析k近鄰一般采用k為奇數(shù)，跟投票表決一樣近鄰法優(yōu)點(diǎn)：在模板數(shù)量很大時(shí)其錯(cuò)誤率指標(biāo)還是相當(dāng)不錯(cuò)的。缺點(diǎn)：需要存儲(chǔ)全部訓(xùn)練樣本，另外有繁重的距離計(jì)算量，即計(jì)算量大，存儲(chǔ)量大。剪輯近鄰法與壓縮近鄰法就是兩種有代表性的改進(jìn)方法。

3.5.3近鄰法的改進(jìn)方法近鄰法3.5.3近鄰法的改進(jìn)方法剪輯近鄰法，其基本原理是在原有樣本集中挑選出對(duì)分類計(jì)算有效的樣本，將不同類別交界處的樣本以適當(dāng)方式進(jìn)行篩選，把處于交界處的訓(xùn)練樣本給剪輯掉，使樣本總數(shù)合理地減少，以同時(shí)達(dá)到既減少計(jì)算量，又減少存儲(chǔ)量的雙重效果。壓縮近鄰法，其基本原理是對(duì)樣本集進(jìn)行組織與整理，分群分層，盡可能將計(jì)算壓縮到在接近測(cè)試樣本鄰域的小范圍內(nèi)，避免盲目地與訓(xùn)練樣本集中每個(gè)樣本進(jìn)行距離計(jì)算。第三章-線性判別分析非參數(shù)判別分類方法第四次課課件一、剪輯近鄰法

剪輯近鄰法著眼于如何減少模板樣本數(shù)目，從而可同時(shí)減少分類時(shí)的計(jì)算量及模板樣本的存儲(chǔ)量，同時(shí)還能進(jìn)一步改進(jìn)分類器的性能，如降低錯(cuò)誤率等要求。剪輯近鄰法的基本思想是從這樣一個(gè)現(xiàn)象出發(fā)的，即當(dāng)不同類別的樣本在分布上有交迭部分，分類的錯(cuò)誤率主要來(lái)自處于交迭區(qū)中的樣本。當(dāng)我們得到一個(gè)作為識(shí)別用的參考樣本集時(shí)，由于不同類別交迭區(qū)域中不同類別的樣本彼此穿插，導(dǎo)致用近鄰法分類出錯(cuò)。因此如果能將不同類別交界處的樣本以適當(dāng)方式篩選，可以實(shí)現(xiàn)既減少樣本數(shù)又提高正確識(shí)別率的雙重目的。為此可以利用現(xiàn)有樣本集對(duì)其自身進(jìn)行剪輯。

第三章-線性判別分析非參數(shù)判別分類方法第四次課課件

用近鄰法容易出錯(cuò)的區(qū)域是在兩類的交界處，這時(shí)某個(gè)訓(xùn)練樣本存在與否就會(huì)影響到某些測(cè)試分類的結(jié)果。因此剪輯的效果往往把這些處于交界的訓(xùn)練樣本給剪輯掉了。用近鄰法容易出錯(cuò)的區(qū)域是在兩類的交界處，這時(shí)某個(gè)二、壓縮近鄰法

剪輯近鄰法所得到的剪輯樣本集在樣本數(shù)量的壓縮方面并不十分明顯，它的作用在于將原樣本集中處于邊界處的樣本刪除掉，但靠近兩類中心的大部分樣本仍被保留下來(lái)。然而按近鄰規(guī)則來(lái)看，這些樣本中的大多數(shù)對(duì)分類決策沒(méi)什么用處，如能在剪輯的基礎(chǔ)上再去掉一部分這樣的樣本，將有助于進(jìn)一步縮短計(jì)算時(shí)間與壓縮存儲(chǔ)量。其實(shí)處于同一類樣本密集區(qū)的測(cè)試樣本并不一定要全部保留，幾乎絕大部分都可去掉，只要保留若干個(gè)訓(xùn)練樣本即可。問(wèn)題是保留哪些好。壓縮近鄰法采用了用測(cè)試集測(cè)試的辦法，采用只要分類有錯(cuò)，在出錯(cuò)處添加一個(gè)訓(xùn)練樣本的做法。二、壓縮近鄰法

壓縮近鄰法壓縮樣本的思想很簡(jiǎn)單，它利用現(xiàn)有樣本集，逐漸生成一個(gè)新的樣本集。使該樣本集在保留最少量樣本的條件下,仍能對(duì)原有樣本的全部用最近鄰法正確分類，那末該樣本集也就能對(duì)待識(shí)別樣本進(jìn)行分類,并保持正常識(shí)別率。該算法的作法也十分簡(jiǎn)單，它定義兩個(gè)存儲(chǔ)器，一個(gè)用來(lái)存放即將生成的樣本集，稱為Store；另一存儲(chǔ)器則存放原樣本集，稱為Grabbag。壓縮近鄰法壓縮樣本的思想很簡(jiǎn)單，它利用現(xiàn)有樣本集，逐漸生成一1.［初始化］Store是空集，原樣本集存入Grabbag；從Grabbag中任意選擇一樣本放入Store中作為新樣本集的第一個(gè)樣本。

2.［樣本集生成］在Grabbag中取出第i個(gè)樣本用Store中的當(dāng)前樣本集按最近鄰法分類。若分類錯(cuò)誤，則將該樣本從Grabbag轉(zhuǎn)入Store中，若分類正確，則將該樣本放回Grabbag中，對(duì)Grabbag中所有樣本重復(fù)上述過(guò)程。

3.［結(jié)束過(guò)程］若Grabbag中所有樣本在執(zhí)行第二步時(shí)沒(méi)有發(fā)生轉(zhuǎn)入Store的現(xiàn)象，或Grabbag已成空集，則算法終止，否則轉(zhuǎn)入第二步。在算法終止后，Store中的樣本集作為壓縮樣本集，可用來(lái)對(duì)待識(shí)別樣本按最近鄰法分類。壓縮近鄰法算法步驟：1.［初始化］Store是空集，原樣本集存入Grabba本章小結(jié)參數(shù)判別分類方法與非參數(shù)判別分類方法線性判別函數(shù)和決策面方程Fisher線性判決準(zhǔn)則感知準(zhǔn)則函數(shù)最小平方誤差準(zhǔn)則函數(shù)分段線性分類器近鄰分類器本章小結(jié)參數(shù)判別分類方法與非參數(shù)判別分類方法參數(shù)判別分類方法與非參數(shù)判別分類方法參數(shù)判別方法：適用條件：前提是清楚特征空間中的各類樣本的分布，一旦待分類樣本的特征向量值x已知，就可以確定x對(duì)各類的后驗(yàn)概率，也就可按相應(yīng)的準(zhǔn)則計(jì)算與分類。參數(shù)分類判別方法一般只能用在有統(tǒng)計(jì)知識(shí)的場(chǎng)合，或能利用訓(xùn)練樣本估計(jì)出參數(shù)的場(chǎng)合。

判別函數(shù)類型如何確定？判別函數(shù)及決策面方程的類別確定是由樣本分布規(guī)律決定的，例如，符合某種條件就可使用線性分類器，正態(tài)分布條件下一般適合用二次函數(shù)決策面。參數(shù)判別分類方法與非參數(shù)判別分類方法參數(shù)判別方法：參數(shù)判別分類方法與非參數(shù)判別分類方法非參數(shù)分類判別方法：直接利用訓(xùn)練樣本集，省去參數(shù)估計(jì)這一環(huán)節(jié)，根據(jù)一些準(zhǔn)則(如Fisher準(zhǔn)則、感知準(zhǔn)則函數(shù))來(lái)設(shè)計(jì)分類器。

判別函數(shù)類型如何確定？