模式識(shí)別近鄰法

模式識(shí)別近鄰法第1頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月一最近鄰決策規(guī)則

假定有c類(lèi)模式，ω1,ω2,…,ωc,每類(lèi)有個(gè)樣本，i=1,2,…,c，總樣本數(shù)為。對(duì)未知樣本，找出已知類(lèi)別的訓(xùn)練樣本集中和最近的一個(gè)樣本，把分到與該樣本一樣的類(lèi)。

第2頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月最近鄰決策算法存儲(chǔ)訓(xùn)練樣本；對(duì)一新的樣本x，在訓(xùn)練樣本集中按某種距離度量找到x的最近鄰(xi,yi)，令x的類(lèi)別y和yi相同。使用歐式距離時(shí)：使用平方距離結(jié)果是一樣的，免去了開(kāi)方運(yùn)算：第3頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月近鄰法和使用的距離度量關(guān)系很大將所有的特征值規(guī)范到相同的范圍（比如[-1，1]），否則取值范圍大的特征起的作用大。去掉噪聲的、不好的特征，它們影響距離度量和性能。利用好的距離度量，如式中是互信息。或利用Mahalanobis距離：●使用k-近鄰更可靠。第4頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月二最近鄰法的錯(cuò)誤率分析下面先分析近鄰法的錯(cuò)誤率，然后討論具體實(shí)施近鄰法時(shí)的一些問(wèn)題。近鄰法錯(cuò)誤率分析的思想是把它和貝葉斯錯(cuò)誤率聯(lián)系起來(lái)第5頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月最近鄰法的錯(cuò)誤率分析

令是要分類(lèi)的點(diǎn)，是它的最近鄰,的真實(shí)類(lèi)是，的真實(shí)類(lèi)別是,對(duì)于和，發(fā)生錯(cuò)誤的概率為

第6頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月最近鄰法的錯(cuò)誤率分析假定事件“是類(lèi)”和“是類(lèi)”是獨(dú)立的事件，則最近鄰算法的條件錯(cuò)誤率為：

第7頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月最近鄰法的錯(cuò)誤率分析如果密度函數(shù)是連續(xù)的，而且樣本點(diǎn)相當(dāng)多，則的最近鄰將非常接近，因此可以合理地認(rèn)為（假定）代入上式，有

(*)第8頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月最近鄰法的錯(cuò)誤率分析下面分析這個(gè)錯(cuò)誤率和貝葉斯錯(cuò)誤率間的關(guān)系令是根據(jù)貝葉斯決策規(guī)則將所分的類(lèi)，即：第9頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月最近鄰法的錯(cuò)誤率分析貝葉斯決策的條件錯(cuò)誤率為：

(**)或?qū)懗?/p>

(1)第10頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月為了導(dǎo)出的界，對(duì)(*)式中的平方項(xiàng)，有

(***)

對(duì)于固定的值，上式當(dāng)，，都相等時(shí)取最小值。第11頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月又由(**)式，使(***)式的取最小值的為（2）第12頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月(***)式可以化為（把（1）和（2）代入）共(c-1)項(xiàng)，消除了一個(gè)(c-1)第13頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月把上式代入(*)式并化簡(jiǎn)有，（3）第14頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月最近鄰法的錯(cuò)誤率分析而近鄰法和貝葉斯決策的錯(cuò)誤率定義為：

第15頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月最近鄰法的錯(cuò)誤率分析第16頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月取(3)式期望，并利用上式，有由于貝葉斯錯(cuò)誤率是最小的，所以完整的上下界是：

第17頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月最近鄰法的錯(cuò)誤率分析上式的結(jié)果表明，當(dāng)樣本數(shù)相當(dāng)多時(shí)，近鄰法的錯(cuò)誤率在貝葉斯錯(cuò)誤率和兩倍的貝葉斯錯(cuò)誤率之間。第18頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月的一些特殊情況

當(dāng)時(shí)，第19頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月當(dāng)各類(lèi)的后驗(yàn)概率相等時(shí)

的一些特殊情況

第20頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月4.2K-近鄰法

取未知樣本的K個(gè)近鄰，看這K個(gè)近鄰中哪類(lèi)的樣本數(shù)最多，就把未知樣本歸到該類(lèi)。

第21頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月K-近鄰法的錯(cuò)誤率界

K-近鄰的錯(cuò)誤率的分析要復(fù)雜。當(dāng)類(lèi)別數(shù)c=2時(shí)，K-近鄰法的錯(cuò)誤率以一族凹函數(shù)為上界。具有如下的性質(zhì)：

第22頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月K-近鄰法的錯(cuò)誤率界這些函數(shù)的形狀如下：

第23頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月K-近鄰法的錯(cuò)誤率界第24頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月*K-近鄰法的錯(cuò)誤率界證明K-NN法錯(cuò)誤率的思路：（對(duì)兩類(lèi)，K為奇數(shù)的情況）

若，而時(shí)則發(fā)生錯(cuò)分，其錯(cuò)誤率為

①

第25頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月K-近鄰法的錯(cuò)誤率界同樣，當(dāng)，而時(shí)發(fā)生誤分類(lèi)，其錯(cuò)誤率為

②

第26頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月K-近鄰法的錯(cuò)誤率界所以，給出x時(shí)的條件錯(cuò)誤率為

①＋②

第27頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月K-近鄰法的錯(cuò)誤率界上式可以化為

(3)

第28頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月K-近鄰法的錯(cuò)誤率界其中：

（當(dāng)K為偶數(shù)時(shí)，有：

,)(4)第29頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月K-近鄰法的錯(cuò)誤率界而給出x時(shí)的條件貝葉斯風(fēng)險(xiǎn)為

(5)

（Maclaulin）馬克勞林級(jí)數(shù)展開(kāi)

第30頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月K-近鄰法的錯(cuò)誤率界利用上面的③–⑤式，有

(回想過(guò)去講的

和間聯(lián)系了起來(lái)，貝葉斯錯(cuò)誤率的Bhattacharyya界，稱(chēng)為B距離。）

第31頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月K-近鄰法的錯(cuò)誤率界例

投票法最近鄰分類(lèi)的錯(cuò)誤率

第32頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月K-近鄰法的錯(cuò)誤率界粗略地說(shuō)，有些樣本落在了其它類(lèi)的決策區(qū)，錯(cuò)了。而這個(gè)錯(cuò)的樣本又可能把正確地落在區(qū)域內(nèi)的樣本弄錯(cuò)，所以最近鄰法的錯(cuò)誤率在貝葉斯錯(cuò)誤率和2倍貝葉斯錯(cuò)誤率之間。

第33頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月最近鄰法的決策邊界：訓(xùn)練樣本的部分VoronoiDiagram近鄰法雖然沒(méi)有直接計(jì)算決策邊界，然而所得到的決策邊界是訓(xùn)練樣本VoronoiDiagram的一個(gè)子集。每一條線是不同類(lèi)樣本間連線的平分線。樣本越多，決策邊界越復(fù)雜。第34頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月減少近鄰法的計(jì)算和存儲(chǔ)問(wèn)題減少訓(xùn)練樣本的數(shù)量，盡量利用“好”的訓(xùn)練樣本。設(shè)計(jì)好的數(shù)據(jù)結(jié)構(gòu)和查找算法快速查找x的k近鄰。第35頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月存儲(chǔ)所有的訓(xùn)練樣本需要大量的存儲(chǔ)，要從訓(xùn)練樣本中挑選一些好的樣本常用的方法有兩種：逐步從訓(xùn)練集中刪掉一些“壞的”樣本。逐步從訓(xùn)練集中挑選出一些“好的”代表樣本。第36頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月4.3剪輯近鄰法由前面的圖可以看出，在投票法的k－近鄰法中，第類(lèi)的樣本落在類(lèi)的區(qū)域后，它可能成為某些類(lèi)樣本的近鄰，因而引起額外的錯(cuò)誤，這是為什么近鄰法的錯(cuò)誤率大于貝葉斯錯(cuò)誤率的原因。

這些額外的錯(cuò)誤可以通過(guò)去掉類(lèi)落在類(lèi)區(qū)域中的樣本而減少（上圖中的1、3、5、6）。

第37頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月在實(shí)際問(wèn)題中，由于不知道準(zhǔn)確的貝葉斯決策邊界，所以不能準(zhǔn)確確定類(lèi)落在類(lèi)區(qū)域中的樣本。而代之以去掉被k近鄰分錯(cuò)的樣本。這樣得到的樣本集合稱(chēng)為剪輯（Editedset）集。以后的實(shí)驗(yàn)樣本集用剪輯集按k近鄰法分類(lèi)。這種算法稱(chēng)為剪輯近鄰法。

第38頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月在剪輯近鄰法中，類(lèi)的落在類(lèi)區(qū)域中的有些樣本被（正確）分到了類(lèi)，因而未被剪掉。而類(lèi)的在區(qū)域中的一些樣本則有可能被誤分類(lèi)，而被剪輯掉。所以剪輯近鄰法的錯(cuò)誤率不可能和貝葉斯錯(cuò)誤率一樣。下面我們分析漸進(jìn)情況下（即）時(shí)的錯(cuò)誤率。第39頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月1剪輯的最近鄰法的錯(cuò)誤率假定給出x的后驗(yàn)概率為和，在使用投票法的最近鄰中，被正確分類(lèi)和不正確分類(lèi)的概率為

和

i=1,2第40頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月剪輯的最近鄰法的錯(cuò)誤率當(dāng)剪輯掉被錯(cuò)分的，保留分對(duì)的時(shí)，在剪輯集中x的后驗(yàn)概率為第41頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月剪輯的最近鄰法的錯(cuò)誤率原來(lái)樣本集若用剪輯集按NN法分類(lèi)，則錯(cuò)誤率為式中利用了，當(dāng)時(shí)。第42頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月剪輯的最近鄰法的錯(cuò)誤率可以證明，未剪輯的最近鄰法的錯(cuò)誤率和貝葉斯錯(cuò)誤率分別為上式的上下界：

,()第43頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月更一般的剪輯近鄰法用一近鄰剪輯，用一近鄰分類(lèi)第44頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月更一般的剪輯近鄰法重復(fù)使用最近鄰法，把落在類(lèi)區(qū)域中類(lèi)的樣本剪掉，其錯(cuò)誤率的情況為

第45頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月4.4壓縮近鄰法近鄰法存在的問(wèn)題計(jì)算量大，存儲(chǔ)量大，要計(jì)算大量的樣本間的距離在投票近鄰法，靠近貝葉斯決策邊界的點(diǎn)對(duì)分類(lèi)有關(guān)鍵作用。而位于各類(lèi)類(lèi)中心附近、遠(yuǎn)離決策邊界的點(diǎn)不影響分類(lèi)，因而可以把它們?nèi)サ?。這樣減少（參考）樣本點(diǎn)，可以節(jié)省近鄰法的時(shí)間和空間。這類(lèi)的算法稱(chēng)為壓縮近鄰法。第46頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月壓縮近鄰法每個(gè)樣本x的條件風(fēng)險(xiǎn)是表示x是否靠近決策邊界的一種度量。因此可設(shè)置一個(gè)閾值τ，并把小于閾值的樣本去掉，。為了避免如剪輯法中討論的問(wèn)題，減少額外的錯(cuò)誤，應(yīng)當(dāng)先剪輯，后壓縮。

第47頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月壓縮近鄰法下面是一個(gè)壓縮算法：（這個(gè)算法沒(méi)有計(jì)算，另種思路）

Condensingalgor.

設(shè)兩個(gè)存儲(chǔ)器Store和Grabbag。把第一個(gè)樣本放入Store中，把所有其它樣本放在Grabbag中

第48頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月壓縮近鄰法用當(dāng)前Store中的樣本按一近鄰規(guī)則對(duì)Grabbag中樣本進(jìn)行分類(lèi)。若分類(lèi)正確，則該樣本仍放回Grabbag中；否則，放入Store中。對(duì)Grabbag中的所有樣本重復(fù)以上過(guò)程。

若從Grabbag中轉(zhuǎn)到Store中的樣本數(shù)為0，或Grabbag中的樣本數(shù)變?yōu)?時(shí)，停止。否則轉(zhuǎn)2。壓縮后，以Store中的樣本作為分類(lèi)的參考集（設(shè)計(jì)集）

第49頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月4.5查找k近鄰的快速算法（樹(shù)搜索）為了減少查找k－近鄰的計(jì)算量，需要盡量避免窮盡地計(jì)算和所有樣本間的距離，可把樣本組織（分解）成一定的等級(jí)如樹(shù)結(jié)構(gòu)等，盡量排除一些不必要的計(jì)算。常用的是k-d樹(shù)等一類(lèi)結(jié)構(gòu)和搜索算法。

第50頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月假定樣本集，目的是要在

X

中尋找未知樣本x的k個(gè)近鄰。為了簡(jiǎn)單，先假定k＝1，即最近鄰的搜索。

下面介紹另外一種把樣本組織成樹(shù)結(jié)構(gòu)的算法。算法分兩個(gè)階段:第51頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月把樣本集X

分級(jí)分解，組織成樹(shù)結(jié)構(gòu)。可根據(jù)樣本在特征空間中所占的位置，把樣本集分成不相交的一些子集（個(gè)），然后把這些樣本子集再分解成不相交的子集，如此進(jìn)行下去，直到每個(gè)終端點(diǎn)只含一個(gè)樣本為止。如下圖：第52頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月第53頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月樹(shù)的中間節(jié)點(diǎn)都代表一個(gè)樣本子集，可以用下列參數(shù)描述：：節(jié)點(diǎn)k所對(duì)應(yīng)的樣本子集：中的樣本數(shù)：中的樣本均值，從到中的樣本的最大距離（不妨稱(chēng)為的半徑）第54頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月分成子集的方法，可根據(jù)樣本在特征空間中所占的位置，把相鄰樣本組織成一個(gè)子集。可以用聚類(lèi)分析的方法（如c均值聚類(lèi)算法）第55頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月

可以利用下面兩個(gè)規(guī)則加快搜索。判斷xi或xi所屬的子集有否可能是x的近鄰。2.搜索未知樣本的（最，k）近鄰（分支限界算法）規(guī)則1：令B是算法執(zhí)行過(guò)程中已經(jīng)找到的x的最近鄰離x的距離，程序開(kāi)始時(shí)可設(shè)B的初值為∞。第56頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月令是的半徑，若，則不可能是x的最近鄰。

這個(gè)規(guī)則可以排除不可能是x近鄰的，不用計(jì)算每個(gè)，。直觀意義如下：

第57頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月根據(jù)三角不等式：

規(guī)則1

對(duì)于終端節(jié)點(diǎn)，可以利用下面的規(guī)則2迅速檢驗(yàn)它能否成為x的最近鄰，省去計(jì)算所有的。

第58頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月規(guī)則2：若,