模式識別課件(第六章NO1)(最近鄰法)

1、第六第六章章 近鄰法近鄰法6.1 最近鄰法最近鄰法一一. 最近鄰法的基本思想最近鄰法的基本思想此法是一種根據(jù)全部樣本全部樣本提供的信息，繞開概率的估計而直接決策的方法，所以它是非參數(shù)決策方法是非參數(shù)決策方法的一種。其基本思想基本思想是：設有一組N個樣本 = X1,X2,XN其中每個樣本都已標以類別標志。如果在這N個樣本中與待分樣本X相距最近相距最近的一個樣本為Xi，則把X分到Xi所在的類別中去。 二二. 最近鄰法的決策規(guī)則最近鄰法的決策規(guī)則設有c類模式樣本， 1, 2, c每類有Ni個樣本(i=1,2,c)，則最近鄰法的最近鄰法的(i類類)判別判別函數(shù)為函數(shù)為:式中 表示i類中的第k個樣本。

2、kiX)N,1,2,.(k min)(ikikiXXXg 對應的決策規(guī)則為：對應的決策規(guī)則為： 如果如果 則決策則決策 即只要將待分樣本X與全部與全部N( )個已知類別的樣本進行歐氏距離歐氏距離之間的比較，然后將X歸到離它最近的類別中歸到離它最近的類別中。 由于這種方法只根據(jù)離待分樣本X最近的一個樣本的類別而決定其類別，所以通常稱為1-最近鄰法最近鄰法(亦稱1-NN方法方法)iXciiN1c),1,2,.(j )(gmin)(jXXgji三三. 最近鄰法的錯誤率問題最近鄰法的錯誤率問題最近鄰法是一種次優(yōu)次優(yōu)方法，它的錯誤率錯誤率比最小錯誤概率最小錯誤概率的的Bayes決策規(guī)則決策規(guī)則下的錯誤率

3、要大要大，但是，當樣本數(shù)目無限無限時，它的錯誤率不會超過Bayes錯誤率的一倍一倍。定性分析：定性分析： 若將X的最近鄰Xj的類別看成是一個隨機變量隨機變量 ，于是 的概率就是后驗概率 .當樣本數(shù)目很多樣本數(shù)目很多時，可以認為X的最近鄰Xj 離它很近離它很近，從而近似的近似的認為j)(jjXPjj)()(XPXPjjj這時最近鄰法可看成是如下的隨機化決策如下的隨機化決策：按照概率按照概率 來決定來決定X的類別的類別。故最近鄰法可看成是用后驗概率后驗概率來對X進行分類的。再進一步說，就是如果有下式成立如果有下式成立：則依Bayes決策，應取 作為X的類別。而在最近鄰法最近鄰法中，最近鄰的類別為

4、的概率為 ，所以X分到分到 類去的概率為 ，而不分到不分到 類去的概率為：)(XPi)(XPj)(max)(XPXPjjiii)(XPii)(1XPii這也就是說：這也就是說： 按Bayes決策決策的話：以概率為1，而得決策 按最近鄰法決策最近鄰法決策的話：以概率為，而得決策 顯然，當接近于當接近于1時，最近鄰法與最小錯誤率下的Bayes法的結果結果就幾乎相同幾乎相同了。也就是說，當最小錯誤概率較小時，最近鄰法的錯誤概率也是較小的，這兩種方法同樣同樣“好好”。而當各類的都接近于當各類的都接近于 時時(即所有類別是等可能的)，最近鄰法與Bayes法的結果就不一樣了。這時兩者的錯兩者的錯誤率都接近

5、于誤率都接近于iX)(XPiiX)(XPi)(XPic1c11 定量描述：定量描述：式中：p為最近鄰法的漸近平均錯誤率 為 Bayes錯誤率 c 為類別數(shù) 一般較小 )12(PccPPPPP PPP2 6.2 k-近鄰法近鄰法(k-NN法法)為了克服單個樣本類別的偶然性偶然性以增加分類的可靠性可靠性，可將最近鄰法則最近鄰法則進行改進，一個簡單的方法就是k-近鄰法近鄰法。此法就是考察待分樣本考察待分樣本X的的k個最近鄰樣本個最近鄰樣本，這這k個最近鄰個最近鄰元素中元素中哪一類哪一類的樣本最多的樣本最多，就將X判屬哪一類。或者說，就是在在N個已知類別個已知類別的樣本中，找出的樣本中，找出X的的k個

6、近鄰個近鄰，這，這k個近鄰中個近鄰中多多數(shù)屬于的那一類數(shù)屬于的那一類 ，就是 。具體就是：具體就是：設k1,k2,.,kc分別為X的的k個最近鄰樣本個最近鄰樣本中屬于屬于 類的樣本數(shù)類的樣本數(shù)，iiXc,.,21則定義定義 類的判別函數(shù)為：類的判別函數(shù)為： 決策規(guī)則為：決策規(guī)則為： 如果如果 則判則判最近鄰法和k-近鄰法的共同優(yōu)點是簡單簡單，而且結果是比較好結果是比較好的的，但是它們也存在下述問題存在下述問題： 需要將全部樣本全部樣本存入機器中，每次決策都要計算X與全部樣本間的距離并進行比較。所以要求的存儲容量存儲容量和和計算量都很大計算量都很大。 沒有考慮到?jīng)Q策的沒有考慮到?jīng)Q策的風險風險，所

7、以如果決策的錯誤代價很大時，會產(chǎn)生很大的風險。上述分析是建立在樣本數(shù)建立在樣本數(shù) 的假定上的的假定上的，這在實際實際應用中是無法實現(xiàn)的無法實現(xiàn)的。),.,2 , 1(ciiiikXg)()(max)(XgXgiijjXN6.3 近鄰法的改進算法近鄰法的改進算法共同特點是如何盡快地找出盡快地找出最近鄰可能存在的小的空間，減少搜索的范圍減少搜索的范圍，從而達到減少減少近鄰法中的計算量計算量和存儲量存儲量的問題。一一. 快速近鄰算法快速近鄰算法該算法對最近鄰法對最近鄰法和k-近鄰法近鄰法都適用都適用。下面以最近鄰法為例來討論。1. 基本思想基本思想將全部已知樣本按級分成全部已知樣本按級分成一些不相交

8、的子集不相交的子集，并在子集的基礎上進行搜索。也就是說，該算法由兩個階段組成：第一階段：第一階段：將樣本集按級分解按級分解，形成樹狀結構。第二階段：第二階段：用搜索算法搜索算法找出待識樣本的最近鄰。2. 涉及的規(guī)則涉及的規(guī)則設=X1,X2,XN表示全部樣本集全部樣本集；P表示節(jié)點P對應的樣本子集樣本子集，即P；NP表示P中的樣本數(shù)中的樣本數(shù)；MP表示P中的樣本均值中的樣本均值(即“類心類心”)；rP ：表示從從MP到到Xi p 的最大距離的最大距離；B表示除除p中的樣本之外的樣本中的樣本之外的樣本到待分樣本X的最近距離最近距離。B的初值設為，以后再不斷修正不斷修正。規(guī)則規(guī)則1如果存在如果存在

9、則Xi p不可不可能是能是X的最近鄰的最近鄰。),(ppMXDrB),(maxpiXMXDpi證明：證明：對任意 ，據(jù)三角不等式有 而據(jù) rp定義有 由上兩式可得 即得則則 不可能是不可能是X的最近鄰的最近鄰。piX),(),(),(pPiiMXDMXDXXDppirMXD),(BrMXDXXDpPi),(),(),(ppMXDrBpiX的近鄰iMp rP規(guī)則規(guī)則2.如果存在則 不可能是X的最近鄰。證明：證明：比較規(guī)則比較規(guī)則1與規(guī)則與規(guī)則2，并參圖，可知 故得證。),(),(ppiMXDMXDBpiXppirMXD),(3. 快速近鄰算法快速近鄰算法第一階段：第一階段：將樣本集樣本集按級分解

10、按級分解。首先將將分為l個子集個子集，每個子集再分成每個子集再分成l個子子集個子子集，依次分下去，圖圖6.3為l=3的情況。這時每個節(jié)點上對應一群樣本。第二階段：第二階段：搜索搜索樹搜索算法：step1：設置設置B=，L=0，P=0.(L是當前水平，P是當前節(jié)點)。step2：將當前節(jié)點當前節(jié)點P的所有直接后繼節(jié)點所有直接后繼節(jié)點(即子節(jié)點)放入一個目錄表中，并對這些節(jié)點節(jié)點X計算計算),(pMXD二二. 剪輯近鄰法剪輯近鄰法此類方法的基本思想是基本思想是：剪掉剪掉(清理)兩類間的邊界兩類間的邊界，取掉類別混雜的樣本混雜的樣本，使兩類邊界更清晰。1. 兩分剪輯近鄰法兩分剪輯近鄰法(亦稱剪輯最近

11、鄰法剪輯最近鄰法)基本過程為：基本過程為：設N個樣本分成c類 = , , (N1+N2+,+Nc= N)step1：剪輯。剪輯。利用已知樣本集 中的樣本進行預分預分 類，類，并剪輯掉被錯分類的樣本剪輯掉被錯分類的樣本，留下的樣本構成 剪輯樣本集剪輯樣本集step2：分類。分類。利用 和近鄰規(guī)則對未知樣本X進行 分類。NN11N22NccNENNE下面以兩類情況以兩類情況進行具體介紹：設將已知類別的樣本集N分成測試集測試集NT和參照集參照集NR兩個獨立的獨立的部分(即這兩部分沒有公共元素沒有公共元素)，它們的樣本數(shù)各為NR和NT，且NR+NT=N。剪輯步：剪輯步：利用參照集參照集NR中的樣本 對測試集對測試集NT 中的每個樣本每個樣本采用最