模式識別近鄰法

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

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

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

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

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

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

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

(**)或寫成

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

(***)

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

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

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

當時，第19頁，課件共63頁，創(chuàng)作于2023年2月當各類的后驗概率相等時

的一些特殊情況

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

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

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

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

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

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

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

①

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

②

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

①＋②

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

(3)

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

（當K為偶數時，有：

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

(5)

（Maclaulin）馬克勞林級數展開

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

(回想過去講的

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

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

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

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

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

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

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

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

和

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

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

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

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

Condensingalgor.

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

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

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

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

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

X

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

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

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

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

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

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

規(guī)則1

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

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