1、第5章 近鄰法,5.1最近鄰法 5.2k近鄰法 5.3 剪輯近鄰法 5.4可做拒絕決策的近鄰法,前面我們介紹了Bayes方法和概率密度函數(shù)的估計(jì)?？梢钥闯?，Bayes方法的應(yīng)用受到很大限制。事實(shí)上，非參數(shù)模式識(shí)別方法更為實(shí)用。由于能解決許多實(shí)際的模式識(shí)別問題，雖然在許多情況下它們不是最優(yōu)的，但卻是應(yīng)用的最多的有效的方法。統(tǒng)計(jì)模式識(shí)別中常用的基本非參數(shù)方法除了前面介紹的線性判別函數(shù)外，還有本章將要介紹的近鄰法和集群。近鄰法屬于有監(jiān)督學(xué)習(xí)，集群屬于無監(jiān)督學(xué)習(xí)。近鄰法是由Cover和Hart于1968年提出來的。 它是在已知模式類別的訓(xùn)練樣本的條件下，繞開概率的估計(jì)，按最近距離原則對(duì)待識(shí)別模式直接進(jìn)

2、行分類。,返回本章首頁,5.1 最近鄰法,返回本章首頁,最近鄰決策規(guī)則 給定c 個(gè)類別 ，每類有標(biāo)明類別的樣本 個(gè)，近鄰法的判別函數(shù)為 決策法則為 直觀的說，就是對(duì)待識(shí)別的模式向量 ，只要比較 與所有已知類別的樣本之間的歐式距離，并決策 與離它最近的樣本同類。,返回本章首頁,返回本章首頁,下面我們先定性的比較一下最近鄰分類法與最小錯(cuò)誤率的Bayes分類方法的分類能力。 我們把 的最近鄰 的類別看成是一個(gè)隨機(jī)變量 ， 的概率為后驗(yàn)概率 最近鄰法則可以看成是一個(gè)隨機(jī)化決策 按照概率 來決定 的類別。 定義：,返回本章首頁,按最小錯(cuò)誤率的Bayes決策法則：以概率1決策 ； 按最近鄰決策法則：以概率

3、 決策 ； 這里假設(shè)在三類問題中， 的后驗(yàn)概率分別為 按最小錯(cuò)誤率的Bayes決策法則：以概率1決策 ； 按最近鄰決策法則：以概率 決策 ；以概率 決策 。 當(dāng) 時(shí)，最近鄰法的決策結(jié)果與最小錯(cuò)誤率的Bayes決策的決策結(jié)果相同，它們的錯(cuò)誤率都是比較小的，兩種方法同樣的好，當(dāng) ，兩者的錯(cuò)誤概率接近于 ，兩種方法同樣的壞。下面我們將進(jìn)一步分析近鄰法的錯(cuò)誤率。,返回本章首頁,最近鄰法的錯(cuò)誤率分析 在前面我們?cè)o出平均錯(cuò)誤率的 在最小錯(cuò)誤率的Bayes決策中，決策使條件錯(cuò)誤率 盡可能小，從而平均錯(cuò)誤率 也一定最小。這里，設(shè) 采用N個(gè)樣本的最近鄰法的平均錯(cuò)誤率 ，并設(shè),返回本章首頁,則有以下的不等式成立

4、： 證明：最近鄰法屬于隨機(jī)化決策，待分類模式 的近鄰隨樣本集的變化而隨機(jī)變化，設(shè)其最近鄰為 ，錯(cuò)誤的條件錯(cuò)誤率為 。對(duì)于 取平均,返回本章首頁,返回本章首頁,下面我們看一下上面的兩個(gè)表達(dá)式。 設(shè)對(duì)于給定的 ，概率密度是連續(xù)的且不為零。那么，任何樣本落入以 為中心的一個(gè)超球 S 中的概率為 N個(gè)獨(dú)立的樣本落在 S 外的概率為 即是，一個(gè)樣本也不落在 S 內(nèi)的概率為0，也就是說總有一個(gè)樣本落在 S 內(nèi)的概率為1。無論S多么小，這個(gè)結(jié)論也是成立的，所以,返回本章首頁,上式即是最近法錯(cuò)誤率的計(jì)算公式，先看下界的證明，這里指出下面的 兩種特殊情況。 （1） （2）,返回本章首頁,現(xiàn)在在來求最近鄰法分類錯(cuò)

5、誤率的精確上界。,返回本章首頁,返回本章首頁,例題1 設(shè)在一個(gè)二維空間，A類有三個(gè)訓(xùn)練樣本，圖中用 紅點(diǎn)表示，B類四個(gè)樣本，圖中用藍(lán)點(diǎn)表示。試問： （1） 按近鄰法分類，這兩類最多有多少個(gè)分界面（2） 畫出實(shí)際用到的分界面（3） A1與B4之間的分界面沒有用到,返回本章首頁,答：按近鄰法，對(duì)任意兩個(gè)由不同類別的訓(xùn)練樣本構(gòu)成的樣本對(duì)， 如果它們有可能成為測(cè)試樣本的近鄰，則它們構(gòu)成一組最小距離分 類器，它們之間的中垂面就是分界面，因此由三個(gè)A類與四個(gè)B類訓(xùn) 練樣本可能構(gòu)成的分界面最大數(shù)量為3412。實(shí)際分界面如下圖所示，由9條線段構(gòu)成：,返回本章首頁,例題2 當(dāng) 時(shí)， （1）證明一維問題的Baye

6、s錯(cuò)誤率 （2）證明此時(shí)最近鄰法漸近平均錯(cuò)誤率,返回本章首頁,解：,返回本章首頁,課后習(xí)題 P160： 6.3 6.4 6.5 P81： 3.1 3.4 3.15,5.2 k近鄰法,返回本章首頁,k近鄰法是在近鄰法的基礎(chǔ)上加以改進(jìn)而來的，這個(gè)法則就是在 的 k 個(gè)近鄰中，按出現(xiàn)最多的樣本類別來作為 的類別。前面我們?cè)敿?xì)討論了近鄰法的錯(cuò)誤率的表達(dá)式及其上下界。同樣，對(duì)于k近鄰法則，我們也討論一下錯(cuò)誤率的問題，這里以 和 二類問題為例。為避免出現(xiàn) 而不能判決的情況，我們?nèi)?為奇數(shù)。對(duì)待識(shí)別模式 誤分類有以下兩種情況：,返回本章首頁,前面我們已經(jīng)說過，當(dāng) ， 的 k 個(gè)已知類別的最近鄰樣本 以概率

7、1 收斂于 ，所以這k 個(gè)樣本可以不標(biāo)出下標(biāo)，統(tǒng)記為 。對(duì)于給定的 的條件錯(cuò)誤率為,返回本章首頁,返回本章首頁,漸近平均錯(cuò)誤率 這里定義Bayes條件錯(cuò)誤率 的函數(shù) 為大于 的最小凹函數(shù)，即對(duì)所有的,返回本章首頁,近鄰法則討論,返回本章首頁,從上面可以看出近鄰法有方法簡(jiǎn)單的優(yōu)點(diǎn)，但也存在這一些缺點(diǎn)： （1）存儲(chǔ)量和計(jì)算量都很大； （2）沒有考慮決策的風(fēng)險(xiǎn)，如果決策的錯(cuò)誤代價(jià)很大時(shí)，會(huì)產(chǎn)生很大的風(fēng)險(xiǎn)； （3）以上的分析漸近平均錯(cuò)誤率，都是建立在樣本數(shù)趨向無窮大的條件下得來的，在實(shí)際應(yīng)用時(shí)大多是無法實(shí)現(xiàn)的。,5.3 剪輯近鄰法,返回本章首頁,這種方法的思想是,清理兩類間的邊界，去掉類別混雜的樣本，

8、使兩類邊界更清晰。這種方法的性能在理論上明顯好于一般的最近鄰法。 1 剪輯最近鄰法 對(duì)于兩類問題，設(shè)將已知類別的樣本集 分成參照集 和考試集 兩部分，這兩部分沒有公共元素，兩部分的樣本數(shù)分別為 和 ，且 。 第一步：利用參照集中的樣本 采用最近鄰法對(duì)考試集中的樣本 進(jìn)行分類，剪輯掉 中被錯(cuò)分類的樣本，具體的說就是： 是 的最近鄰元，剪輯掉 中不與 同類 余下的部分構(gòu)成剪輯樣本集 。,返回本章首頁,第二步：利用剪輯樣本集 和最近鄰法對(duì)待分類模式 作分類決策。 定理：當(dāng)樣本數(shù) 時(shí)， 。如果 是 和 的連續(xù)點(diǎn)，設(shè) 在 中的最近鄰為 ，則 在 中的最近鄰 有 那么我們可以得到 的近鄰 屬于 的漸近概率

9、為,返回本章首頁,誤判的情況： 屬于 類而其近鄰元屬于 ，或 屬于 類但其近鄰元屬于 類，因此沒有剪輯的最近鄰法的漸近條件錯(cuò)誤率為 剪輯了的最近鄰法的漸近條件錯(cuò)誤了率為,返回本章首頁,返回本章首頁,返回本章首頁,2 重復(fù)剪輯近鄰法 只要樣本足夠多，就可以重復(fù)地執(zhí)行剪輯程序，以提高分類性能。這里從理論上對(duì)二類問題重復(fù)剪輯最近鄰法的錯(cuò)誤率進(jìn)行分析。經(jīng)過第一次剪輯后， 的最近鄰樣本 屬于 的概率為,返回本章首頁,第二次剪輯后， 的最近鄰樣本屬于 的概率為,返回本章首頁,第M次剪輯后， 的最近鄰樣本屬于 的概率為,返回本章首頁,5.4 可做拒絕決策的近鄰法,返回本章首頁,在運(yùn)用k近鄰法時(shí)，為克服k個(gè)近

10、鄰元屬于不同類別的樣本數(shù)的偶然性，采用的方法之一是增大k ，然而這仍然不能完全消除k個(gè)近鄰元類別的偶然性。我們說若k個(gè)近鄰元中某一類的樣本數(shù)占很大的優(yōu)勢(shì)，則誤判的可能性就較小；如果是微弱優(yōu)勢(shì)，則作出判別決策，誤判的可能性就很大。進(jìn)一步，在某些實(shí)際問題中誤判的風(fēng)險(xiǎn)很大的話，則會(huì)付出很大的代價(jià)，因此在這種情況下引入拒絕決策就很有必要了，一般記為 類。 下面我們結(jié)合前面講述的k近鄰法和剪輯近鄰法進(jìn)行分析。,返回本章首頁,1 具有拒絕決策的k近鄰法 對(duì)于兩類問題，引入了拒絕決策k近鄰法的思想是，根據(jù)可信性要求選定一個(gè) 值，應(yīng)使 ，如果待識(shí)別模式 的k個(gè)近鄰中有大于或等于 個(gè)樣本屬于某一類 ,則判 ，否則拒絕作出類別決策。 的k個(gè)近鄰元至少有 個(gè)來自 類的漸近概率為,返回本章首頁,當(dāng) 的 個(gè)近鄰中有少于 個(gè)屬于同一類時(shí)，則考慮拒絕，這時(shí)的概率為,返回本章首頁,決策的錯(cuò)誤率 決策的拒絕率 2 具有拒絕決策的剪輯近鄰法 拒絕決策的近鄰法推廣到剪輯近鄰法。 首先選定 和 ，然后我們按以下的步驟對(duì)樣本集進(jìn)行剪輯，然后用剪輯樣本集對(duì)待識(shí)別模式進(jìn)行分類。,返回本章首頁,步驟如下： （1）對(duì)于訓(xùn)練集 中的每個(gè)樣本 ，從 中找出它的 個(gè)近鄰元； （2）如果 的 個(gè)近鄰