線性判別分析非參數(shù)判別分類方法第四次課詳解演示文稿

線性判別分析非參數(shù)判別分類方法第四次課詳解演示文稿第一頁，共五十八頁。（優(yōu)選）線性判別分析非參數(shù)判別分類方法第四次課第二頁，共五十八頁。3.2.2Fisher線性判決Fisher線性判決的基本思想是尋找一個最好的投影方向,當特征向量x從d維空間映射到這個方向上時,兩類能最好地分開。這個方法實際上涉及特征維數(shù)的壓縮問題。3.2線性分類器第三頁，共五十八頁。分析w1方向之所以比w2方向優(yōu)越,可以歸納出這樣一個準則：即向量w的方向選擇應(yīng)能使兩類樣本投影的均值之差盡可能大些,而使類內(nèi)樣本的離散程度盡可能小。這就是Fisher準則函數(shù)的基本思路。第四頁，共五十八頁。第一步：計算參量。(1)各類樣本的均值向量μi:(2)樣本類內(nèi)離散度矩陣Si：總類內(nèi)離散度矩陣Sw:第二步：計算最優(yōu)投影方向，并將樣本往該方向上投影。第三步：決策。在投影空間內(nèi)的決策準則為:若y>y0,則x∈ω1,否則x∈ω2。Fisher線性判決步驟第五頁，共五十八頁。采用類似于人認知錯誤、糾正錯誤、通過自學習改善自己認識事物本領(lǐng)的過程，隨意確定判別函數(shù)初始值，該值在對樣本分類訓練過程中逐步修正直至最終確定?；舅枷耄簩ふ乙粋€權(quán)向量，使規(guī)范化增廣樣本向量集的錯分類樣本數(shù)最少。

3.2.3感知準則函數(shù)

第六頁，共五十八頁。一、基本概念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,能將每個樣本正確地分類。

第七頁，共五十八頁。

2.樣本的規(guī)范化如果樣本集{y1,y2,…,yN}線性可分,則一定存在某個或某些權(quán)向量v,使如果令，則vTzi>0。規(guī)范化增廣樣本向量經(jīng)過這樣的變換后,我們可以不考慮樣本原來的類別標志,只要找到一個對全部樣本zi都滿足vTzi>0(i=1,2,…,N)的權(quán)向量即可。樣本的規(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。第九頁，共五十八頁。相應(yīng)地,N個樣本確定了N個超平面,每個超平面把權(quán)空間分為兩個半空間。所以,滿足vTzi>0(i=1,2,…,N)的權(quán)向量必在這N個超平面正側(cè)的交疊區(qū),稱這一交疊區(qū)為解區(qū),解區(qū)中的任意向量都是解向量v*。第十頁，共五十八頁。二、感知準則函數(shù)感知準則函數(shù)方法利用錯分類對現(xiàn)決策權(quán)向量進行修正直至收斂。這種方法只對線性可分情況適用，并且只適用于兩類判決。感知準則函數(shù)方法的思路是：先隨意找一個初始向量v，寫作v(0)，然后用訓練樣本集中的每個樣本來計算。一旦發(fā)現(xiàn)有的zi，使vTzi<0，則說明當前的廣義權(quán)向量v(0)不適合還需要進一步修正。

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

設(shè)由X={x1,x2,…,xN}得到的規(guī)范化增廣向量集合為{z1,z2,…,zN},分類器設(shè)計的任務(wù)就在于尋找一個矢量v,滿足:引入余量bi,用超平面:代替zTiv>0,則引入余量后的解區(qū)在原解區(qū)之內(nèi)。將上式寫成矩陣形式即為第十四頁，共五十八頁。定義誤差向量:定義平方誤差準則函數(shù):Js(v)是一個非負函數(shù),當有解時,Js(v)達到最小值0,此時的矢量v*滿足:v*能將所有樣本正確分類。若v*不能使某個樣本zj正確分類,即(v*)Tzj≠bj,則e2j=(vTzj－bj)2。錯分樣本的結(jié)果是使Js(v)增大,因此,Js(v)越小越好,其最小值0為理想分類結(jié)果,實現(xiàn)所有樣本的正確分類。

求使Js(v)最小的v*有兩種方法:梯度下降法和解析法。第十五頁，共五十八頁。

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

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

線性分類器的分界面是一個超平面。當類與類之間不能用任何一個超平面實現(xiàn)劃分時,類間的分界面應(yīng)是一個超曲面。曲線可以由多個線段近似表達,曲面可以由多個平面逼近,因此,可以用多個超平面近似表達超曲面,分段線性分類器正是基于這種思路而設(shè)計的一種分類器。第十八頁，共五十八頁。線性判決函數(shù)只能解決線性可分問題。在線性不可分的情況下，可以采用分段線性判別或二次函數(shù)判別等方法。分段線性判決函數(shù)確定的決策面是由若干段超平面組成的。

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

稱gi(x)(i=1,2,…,m)為分段線性判決函數(shù),相應(yīng)的分類器稱為分段線性分類器。第二十一頁，共五十八頁。當類由多個子類構(gòu)成時,其決策面方程是由各子類的判決函數(shù)確定的,若第i類的第n個子類和第j類的第k個子類相鄰,則該段決策面方程為其中,n∈{1,2,…,li},k∈{1,2,…,lj},li和lj分別表示第i類和第j類的子類數(shù)目。第二十二頁，共五十八頁。3.3.2分段線性距離分類器正態(tài)分布條件下，兩類別問題在各特征統(tǒng)計獨立、同方差、且先驗概率相等情況下，最小錯誤率決策可按最小距離決策，最小距離分類器的判決函數(shù)為

即這時類間的決策面為

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

稱這種分類器為分段線性距離分類器。第二十六頁，共五十八頁。

注意：

線性距離分類器使用的是馬氏距離,分段線性距離分類器使用的則是歐幾里德距離,由最小距離分類器的導出過程可知,僅當所有子區(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ù)目未知。第二十八頁，共五十八頁。最初的近鄰法是由Cover和Hart于1968年提出的，是非參數(shù)法中最重要的方法之一。最小距離分類器將各類訓練樣本劃分成若干子類，并在每個子類中確定代表點，一般用子類的均值或鄰近均值的某一樣本為代表點。實質(zhì)就是將樣本判屬于與代表點距離最近的類。該法的缺點是所選擇的代表點并不一定能很好地代表各類，其后果將使錯誤率增加。3.4近鄰分類器第二十九頁，共五十八頁。3.5.1最近鄰法一、最近鄰法的原理及判決準則

近鄰法的基本思想：以全部訓練樣本作為“代表點”，計算測試樣本與這些“代表點”，即所有樣本的距離，并以最近鄰者的類別作為決策。其主要特點就是將樣本判屬它的最近鄰（和它距離最近的代表點）所在的類。第三十頁，共五十八頁。假定有m個類別ω1,ω2,…,ωm的模式識別問題,每類有Ni(i=1,2,…,m)個樣本,規(guī)定類ωi的判別函數(shù)為其中,表示第i類的第k個元素。判決準則:

若，則x∈ωj

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

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

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

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

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

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

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

剪輯近鄰法所得到的剪輯樣本集在樣本數(shù)量的壓縮方面并不十分明顯，它的作用在于將原樣本集中處于邊界處的樣本刪除掉，但靠近兩類中心的大部分樣本仍被保留下來。然而按近鄰規(guī)則來看，這些樣本中的大多數(shù)對分類決策沒什么用處，如能在剪輯的基礎(chǔ)上再去掉一部分這樣的樣本，將有助于進一步縮短計算時間與壓縮存儲量。其實處于同一類樣本密集區(qū)的測試樣本并不一定要全部保留，幾乎絕大部分都可去掉，只要保留若干個訓練樣本即可。問題是保留哪些好。壓縮近鄰法采用了用測試集測試的辦法，采用只要分類有錯，在出錯處添加一個訓練樣本的做法。第四十四頁，共五十八頁。壓縮近鄰法壓縮樣本的思想很簡單，它利用現(xiàn)有樣本集，逐漸生成一個新的樣本集。使該樣本集在保留最少量樣本的條件下,仍能對原有樣本的全部用最近鄰法正確分類，那末該樣本集也就能對待識別樣本進行分類,并保持正常識別率。該算法的作法也十分簡單，它定義兩個存儲器，一個用來存放即將生成的樣本集，稱為Store；另一存儲器則存放原樣本集，稱為Grabbag。第四十五頁，共五十八頁。1.［初始化］Store是空集，原樣本集存入Grabbag；從Grabbag中任意選擇一樣本放入Store中作為新樣本集的第一個樣本。2.［樣本集生成］在Grabbag中取出第i個樣本用Store中的當前樣本集按最近鄰法分類。若分類錯誤，則將該樣本從Grabbag轉(zhuǎn)入Store中，若分類正確，則將該樣本放回Grabbag中，對Grabbag中所有樣本重復(fù)上述過程。3.［結(jié)束過程］若Grabbag中所有樣本在執(zhí)行第二步時沒有發(fā)生轉(zhuǎn)入Store的現(xiàn)象，或Grabbag已成空集，則算法終止，否則轉(zhuǎn)入第二步。在算法終止后，Store中的樣本集作為壓縮樣本集，可用來對待識別樣本按最近鄰法分類。壓縮近鄰法算法步驟：第四十六頁，共五十八頁。本章小結(jié)參數(shù)判別分類方法與非參數(shù)判別分類方法線性判別函數(shù)和決策面方程Fisher線性判決準則感知準則函數(shù)最小平方誤差準則函數(shù)分段線性分類器近鄰分類器第四十七頁，共五十八頁。參數(shù)判別分類方法與非參數(shù)判別分類方法參數(shù)判別方法：適用條件：前提是清楚特征空間中的各類樣本的分布，一旦待分類樣本的特征向量值x已知，就可以確定x對各類的后驗概率，也就可按相應(yīng)的準則計算與分類。參數(shù)分類判別方法一般只能用在有統(tǒng)計知識的場合，或能利用訓練樣本估計出參數(shù)的場合。

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

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

使用非參數(shù)分類判別方法進行分類器設(shè)計主要包含兩個步驟：選擇函數(shù)類型與確定參數(shù)。確定使用的判別函數(shù)類型或決策面方程類型，如線性分類器、非線性分類器、分段線性分類器或近鄰法等。在選定的函數(shù)類型條件下，確定相應(yīng)的參數(shù)，從而完成整個分類器設(shè)計。第五十頁，共五十八頁。其中wi是權(quán)向量,wi0是一個常數(shù)，稱為閾值權(quán)。設(shè)樣本在d維特征空間中描述，兩類問題線性判別函數(shù)的一般形式可表示成判決準則的可以表示為

線性判別函數(shù)和決策面方程第五十一頁，共五十八頁。在線性判別函數(shù)條件下