模式識別近鄰法

模式識別近鄰法第一頁，共六十三頁，2022年，8月28日一最近鄰決策規(guī)則

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

第二頁，共六十三頁，2022年，8月28日最近鄰決策算法存儲訓練樣本；對一新的樣本x，在訓練樣本集中按某種距離度量找到x的最近鄰(xi,yi)，令x的類別y和yi相同。使用歐式距離時：使用平方距離結果是一樣的，免去了開方運算：第三頁，共六十三頁，2022年，8月28日近鄰法和使用的距離度量關系很大將所有的特征值規(guī)范到相同的范圍（比如[-1，1]），否則取值范圍大的特征起的作用大。去掉噪聲的、不好的特征，它們影響距離度量和性能。利用好的距離度量，如式中是互信息。或利用Mahalanobis距離：●使用k-近鄰更可靠。第四頁，共六十三頁，2022年，8月28日二最近鄰法的錯誤率分析下面先分析近鄰法的錯誤率，然后討論具體實施近鄰法時的一些問題。近鄰法錯誤率分析的思想是把它和貝葉斯錯誤率聯(lián)系起來第五頁，共六十三頁，2022年，8月28日最近鄰法的錯誤率分析

令是要分類的點，是它的最近鄰,的真實類是，的真實類別是,對于和，發(fā)生錯誤的概率為

第六頁，共六十三頁，2022年，8月28日最近鄰法的錯誤率分析假定事件“是類”和“是類”是獨立的事件，則最近鄰算法的條件錯誤率為：

第七頁，共六十三頁，2022年，8月28日最近鄰法的錯誤率分析如果密度函數(shù)是連續(xù)的，而且樣本點相當多，則的最近鄰將非常接近，因此可以合理地認為（假定）代入上式，有

(*)第八頁，共六十三頁，2022年，8月28日最近鄰法的錯誤率分析下面分析這個錯誤率和貝葉斯錯誤率間的關系令是根據(jù)貝葉斯決策規(guī)則將所分的類，即：第九頁，共六十三頁，2022年，8月28日最近鄰法的錯誤率分析貝葉斯決策的條件錯誤率為：

(**)或寫成

(1)第十頁，共六十三頁，2022年，8月28日為了導出的界，對(*)式中的平方項，有

(***)

對于固定的值，上式當，，都相等時取最小值。第十一頁，共六十三頁，2022年，8月28日又由(**)式，使(***)式的取最小值的為（2）第十二頁，共六十三頁，2022年，8月28日(***)式可以化為（把（1）和（2）代入）共(c-1)項，消除了一個(c-1)第十三頁，共六十三頁，2022年，8月28日把上式代入(*)式并化簡有，（3）第十四頁，共六十三頁，2022年，8月28日最近鄰法的錯誤率分析而近鄰法和貝葉斯決策的錯誤率定義為：

第十五頁，共六十三頁，2022年，8月28日最近鄰法的錯誤率分析第十六頁，共六十三頁，2022年，8月28日取(3)式期望，并利用上式，有由于貝葉斯錯誤率是最小的，所以完整的上下界是：

第十七頁，共六十三頁，2022年，8月28日最近鄰法的錯誤率分析上式的結果表明，當樣本數(shù)相當多時，近鄰法的錯誤率在貝葉斯錯誤率和兩倍的貝葉斯錯誤率之間。第十八頁，共六十三頁，2022年，8月28日的一些特殊情況

當時，第十九頁，共六十三頁，2022年，8月28日當各類的后驗概率相等時

的一些特殊情況

第二十頁，共六十三頁，2022年，8月28日4.2K-近鄰法

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

第二十一頁，共六十三頁，2022年，8月28日K-近鄰法的錯誤率界

K-近鄰的錯誤率的分析要復雜。當類別數(shù)c=2時，K-近鄰法的錯誤率以一族凹函數(shù)為上界。具有如下的性質：

第二十二頁，共六十三頁，2022年，8月28日K-近鄰法的錯誤率界這些函數(shù)的形狀如下：

第二十三頁，共六十三頁，2022年，8月28日K-近鄰法的錯誤率界第二十四頁，共六十三頁，2022年，8月28日*K-近鄰法的錯誤率界證明K-NN法錯誤率的思路：（對兩類，K為奇數(shù)的情況）

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

①

第二十五頁，共六十三頁，2022年，8月28日K-近鄰法的錯誤率界同樣，當，而時發(fā)生誤分類，其錯誤率為

②

第二十六頁，共六十三頁，2022年，8月28日K-近鄰法的錯誤率界所以，給出x時的條件錯誤率為

①＋②

第二十七頁，共六十三頁，2022年，8月28日K-近鄰法的錯誤率界上式可以化為

(3)

第二十八頁，共六十三頁，2022年，8月28日K-近鄰法的錯誤率界其中：

（當K為偶數(shù)時，有：

,)(4)第二十九頁，共六十三頁，2022年，8月28日K-近鄰法的錯誤率界而給出x時的條件貝葉斯風險為

(5)

（Maclaulin）馬克勞林級數(shù)展開

第三十頁，共六十三頁，2022年，8月28日K-近鄰法的錯誤率界利用上面的③–⑤式，有

(回想過去講的

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

第三十一頁，共六十三頁，2022年，8月28日K-近鄰法的錯誤率界例

投票法最近鄰分類的錯誤率

第三十二頁，共六十三頁，2022年，8月28日K-近鄰法的錯誤率界粗略地說，有些樣本落在了其它類的決策區(qū)，錯了。而這個錯的樣本又可能把正確地落在區(qū)域內的樣本弄錯，所以最近鄰法的錯誤率在貝葉斯錯誤率和2倍貝葉斯錯誤率之間。

第三十三頁，共六十三頁，2022年，8月28日最近鄰法的決策邊界：訓練樣本的部分VoronoiDiagram近鄰法雖然沒有直接計算決策邊界，然而所得到的決策邊界是訓練樣本VoronoiDiagram的一個子集。每一條線是不同類樣本間連線的平分線。樣本越多，決策邊界越復雜。第三十四頁，共六十三頁，2022年，8月28日減少近鄰法的計算和存儲問題減少訓練樣本的數(shù)量，盡量利用“好”的訓練樣本。設計好的數(shù)據(jù)結構和查找算法快速查找x的k近鄰。第三十五頁，共六十三頁，2022年，8月28日存儲所有的訓練樣本需要大量的存儲，要從訓練樣本中挑選一些好的樣本常用的方法有兩種：逐步從訓練集中刪掉一些“壞的”樣本。逐步從訓練集中挑選出一些“好的”代表樣本。第三十六頁，共六十三頁，2022年，8月28日4.3剪輯近鄰法由前面的圖可以看出，在投票法的k－近鄰法中，第類的樣本落在類的區(qū)域后，它可能成為某些類樣本的近鄰，因而引起額外的錯誤，這是為什么近鄰法的錯誤率大于貝葉斯錯誤率的原因。

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

第三十七頁，共六十三頁，2022年，8月28日在實際問題中，由于不知道準確的貝葉斯決策邊界，所以不能準確確定類落在類區(qū)域中的樣本。而代之以去掉被k近鄰分錯的樣本。這樣得到的樣本集合稱為剪輯（Editedset）集。以后的實驗樣本集用剪輯集按k近鄰法分類。這種算法稱為剪輯近鄰法。

第三十八頁，共六十三頁，2022年，8月28日在剪輯近鄰法中，類的落在類區(qū)域中的有些樣本被（正確）分到了類，因而未被剪掉。而類的在區(qū)域中的一些樣本則有可能被誤分類，而被剪輯掉。所以剪輯近鄰法的錯誤率不可能和貝葉斯錯誤率一樣。下面我們分析漸進情況下（即）時的錯誤率。第三十九頁，共六十三頁，2022年，8月28日1剪輯的最近鄰法的錯誤率假定給出x的后驗概率為和，在使用投票法的最近鄰中，被正確分類和不正確分類的概率為

和

i=1,2第四十頁，共六十三頁，2022年，8月28日剪輯的最近鄰法的錯誤率當剪輯掉被錯分的，保留分對的時，在剪輯集中x的后驗概率為第四十一頁，共六十三頁，2022年，8月28日剪輯的最近鄰法的錯誤率原來樣本集若用剪輯集按NN法分類，則錯誤率為式中利用了，當時。第四十二頁，共六十三頁，2022年，8月28日剪輯的最近鄰法的錯誤率可以證明，未剪輯的最近鄰法的錯誤率和貝葉斯錯誤率分別為上式的上下界：

,()第四十三頁，共六十三頁，2022年，8月28日更一般的剪輯近鄰法用一近鄰剪輯，用一近鄰分類第四十四頁，共六十三頁，2022年，8月28日更一般的剪輯近鄰法重復使用最近鄰法，把落在類區(qū)域中類的樣本剪掉，其錯誤率的情況為

第四十五頁，共六十三頁，2022年，8月28日4.4壓縮近鄰法近鄰法存在的問題計算量大，存儲量大，要計算大量的樣本間的距離在投票近鄰法，靠近貝葉斯決策邊界的點對分類有關鍵作用。而位于各類類中心附近、遠離決策邊界的點不影響分類，因而可以把它們去掉。這樣減少（參考）樣本點，可以節(jié)省近鄰法的時間和空間。這類的算法稱為壓縮近鄰法。第四十六頁，共六十三頁，2022年，8月28日壓縮近鄰法每個樣本x的條件風險是表示x是否靠近決策邊界的一種度量。因此可設置一個閾值τ，并把小于閾值的樣本去掉，。為了避免如剪輯法中討論的問題，減少額外的錯誤，應當先剪輯，后壓縮。

第四十七頁，共六十三頁，2022年，8月28日壓縮近鄰法下面是一個壓縮算法：（這個算法沒有計算，另種思路）

Condensingalgor.

設兩個存儲器Store和Grabbag。把第一個樣本放入Store中，把所有其它樣本放在Grabbag中

第四十八頁，共六十三頁，2022年，8月28日壓縮近鄰法用當前Store中的樣本按一近鄰規(guī)則對Grabbag中樣本進行分類。若分類正確，則該樣本仍放回Grabbag中；否則，放入Store中。對Grabbag中的所有樣本重復以上過程。

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

第四十九頁，共六十三頁，2022年，8月28日4.5查找k近鄰的快速算法（樹搜索）為了減少查找k－近鄰的計算量，需要盡量避免窮盡地計算和所有樣本間的距離，可把樣本組織（分解）成一定的等級如樹結構等，盡量排除一些不必要的計算。常用的是k-d樹等一類結構和搜索算法。

第五十頁，共六十三頁，2022年，8月28日假定樣本集，目的是要在

X

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

下面介紹另外一種把樣本組織成樹結構的算法。算法分兩個階段:第五十一頁，共六十三頁，2022年，8月28日把樣本集X

分級分解，組織成樹結構。可根據(jù)樣本在特征空間中所占的位置，把樣本集分成不相交的一些子集（個），然后把這些樣本子集再分解成不相交的子集，如此進行下去，直到每個終端點只含一個樣本為止。如下圖：第五十二頁，共六十三頁，2022年，8月28日第五十三頁，共六十三頁，2022年，8月28日樹的中間節(jié)點都代表一個樣本子集，可以用下列參數(shù)描述：：節(jié)點k所對應的樣本子集：中的樣本數(shù)：中的樣本均值，從到中的樣本的最大距離（不妨稱為的半徑）第五十四頁，共六十三頁，2022年，8月28日分成子集的方法，可根據(jù)樣本在特征空間中所占的位置，把相鄰樣本組織成一個子集?？梢杂镁垲惙治龅姆椒ǎㄈ鏲均值聚類算法）第五十五頁，共六十三頁，2022年，8月28日

可以利用下面兩個規(guī)則加快搜索。判斷xi或xi所屬的子集有否可能是x的近鄰。2.搜索未知樣本的（最，k）近鄰（分支限界算法）規(guī)則1：令B是算法執(zhí)行過程中已經(jīng)找到的x的最近鄰離x的距離，程序開始時可設B的初值為∞。第五十六頁，共六十三頁，2022年，8月28日令是的半徑，若，則不可能是x的最近鄰。

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

第五十七頁，共六十三頁，2022年，8月28日根據(jù)三角不等式：

規(guī)則1

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

第五十八頁，共六十三頁，2022年，8月28日規(guī)則2：若,