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

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

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

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

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

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

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

經(jīng)過這樣的變換后,我們可以不考慮樣本原來的類別標(biāo)志,只要找到一個對全部樣本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)向量空間中的一點,對于任一zi,vTzi=0在權(quán)向量空間確定了一個超平面,這個超平面把權(quán)空間分為兩個半空間,該超平面的法向量為zi,超平面正側(cè)的向量滿足vTzi>0。3.解向量和解區(qū)

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

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

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

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

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

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

1.梯度下降法對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分段線性分類器

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

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

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

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

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

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

即這時類間的決策面為

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

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

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

注意：

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

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

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

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

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

若，則x∈ωj

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

第一步：計算參量。

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

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

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

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

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

即這時類間的決策面為

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

經(jīng)過這樣的變換后,我們可以不考慮樣本原來的類別標(biāo)志,只要找到一個對全部樣本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)向量空間中的一點,對于任一zi,vTzi=0在權(quán)向量空間確定了一個超平面,這個超平面把權(quán)空間分為兩個半空間,該超平面的法向量為zi,超平面正側(cè)的向量滿足vTzi>0。3.解向量和解區(qū)

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

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

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

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

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

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

1.梯度下降法對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分段線性分類器

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

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

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

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

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

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

即這時類間的決策面為

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

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

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

注意：

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

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

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

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

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

若，則x∈ωj

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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