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

第三章線性判別分析——非參數判別分類方法第三章線性判別分析本章內容3.1

線性判別函數3.2線性分類器Fisher線性判決感知準則函數3.3分段線性分類器3.4近鄰分類器總結習題本章內容3.1線性判別函數3.2.2Fisher線性判決

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

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

3.2.3感知準則函數

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

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

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

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

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

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

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

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

二、感知準則函數感知準則函數方法利用錯分類對現決策權向量進行

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

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

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

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

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

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分段線性分類器

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

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

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

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

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

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

即這時類間的決策面為

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

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

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

注意：

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

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

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

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

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

若，則x∈ωj

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

判決準則為若，則x∈ωj稱這種方法為k近鄰法,相應的分類器稱為k近鄰分類器。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

第一步：計算參量。

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

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

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

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

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

即這時類間的決策面為

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

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

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

1.對于線性判決函數:

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

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

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

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

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

線性判別函數3.2線性分類器Fisher線性判決感知準則函數3.3分段線性分類器3.4近鄰分類器總結習題本章內容3.1線性判別函數3.2.2Fisher線性判決

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

(2)樣本類內離散度矩陣Si：總類內離散度矩陣Sw:第二步：計算最優(yōu)投影方向，并將樣本往該方向上投影。第三步：決策。在投影空間內的決策準則為:若y>y0,則x∈ω1,否則x∈ω2。Fisher線性判決步驟第一步：計算參量。(2)樣本類內離散度矩陣Si：總類采用類似于人認知錯誤、糾正錯誤、通過自學習改善自己認識事物本領的過程，隨意確定判別函數初始值，該值在對樣本分類訓練過程中逐步修正直至最終確定。基本思想：尋找一個權向量，使規(guī)范化增廣樣本向量集的錯分類樣本數最少。

3.2.3感知準則函數

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

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

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

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

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

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

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

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

二、感知準則函數感知準則函數方法利用錯分類對現決策權向量進行

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

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

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

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

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

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分段線性分類器

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

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

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

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

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

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

即這時類間的決策面為

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

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

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

注意：

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

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

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

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

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

若，則x∈ωj

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

判決準則為若，則x∈ωj稱這種方法為k近鄰法,相應的分類器稱為k近鄰分類器。

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

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

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

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

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

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

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

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

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

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

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

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

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

判別函數類型如何確定？