第六章 近鄰法

第六章近鄰法第一頁(yè)，共二十一頁(yè)，2022年，8月28日第六章近鄰法第二頁(yè)，共二十一頁(yè)，2022年，8月28日6.1.1.問(wèn)題描述

特征向量類別X=(0.1,0.1)?§6.1近鄰法原理及其決策規(guī)則特征向量類別(0.1,0.2)W1(0.2,0.1)W1(0.4,0.5)W2(0.5,0.4)W2第六章近鄰法第三頁(yè)，共二十一頁(yè)，2022年，8月28日最小距離分類器:它將各類訓(xùn)練樣本劃分成若干子類，并在每個(gè)子類中確定代表點(diǎn)。未知樣本的類別則以其與這些代表點(diǎn)距離最近作決策。該方法的缺點(diǎn)是所選擇的代表點(diǎn)并不一定能很好地代表各類，其后果將使錯(cuò)誤率增加。m1m2xg(x)=0m1m2x最近鄰分類器(nearestneighborhoodclassifier,nnc):最小距離分類器的一種極端的情況，以全部訓(xùn)練樣本作為代表點(diǎn)，計(jì)算測(cè)試樣本與所有樣本的距離，并以最近鄰者的類別作為決策。最初的近鄰法是由Cover和Hart于1968年提出的，隨后得到理論上深入的分析與研究，是非參數(shù)法中最重要的方法之一。第四頁(yè)，共二十一頁(yè)，2022年，8月28日6.1.2.最近鄰法的決策規(guī)則將與測(cè)試樣本最近鄰樣本的類別作為決策的方法稱為最近鄰法。對(duì)一個(gè)C類別問(wèn)題，每類有Ni個(gè)樣本，i＝1，…，C，則第i類ωi的判別函數(shù)其中Xik表示是ωi類的第k個(gè)樣本。以上式為判別函數(shù)的決策規(guī)則為：最近鄰法在原理上最直觀，方法上也十分簡(jiǎn)單，只要對(duì)所有樣本(共N＝∑Ni)進(jìn)行N次距離運(yùn)算，然后以最小距離者的類別作決策。如果則決策§6.1近鄰法原理及其決策規(guī)則第五頁(yè)，共二十一頁(yè)，2022年，8月28日在二維情況下，最近鄰規(guī)則算法使得二維空間被分割成了許多Voronoi網(wǎng)格，每一個(gè)網(wǎng)格代表的類別就是它所包含的訓(xùn)練樣本點(diǎn)所屬的類別?！?.1近鄰法原理及其決策規(guī)則第六頁(yè)，共二十一頁(yè)，2022年，8月28日最近鄰法錯(cuò)誤率最近鄰法的錯(cuò)誤率高于貝葉斯錯(cuò)誤率，可以證明以下關(guān)系式成立：由于一般情況下P*很小，因此又可粗略表示成：可粗略說(shuō)最近鄰法的漸近平均錯(cuò)誤率在貝葉斯錯(cuò)誤率的兩倍之內(nèi)。§6.1.2近鄰法決策規(guī)則第七頁(yè)，共二十一頁(yè)，2022年，8月28日k-近鄰法:最近鄰法的擴(kuò)展，其基本規(guī)則是，在所有N個(gè)樣本中找到與測(cè)試樣本的k個(gè)最近鄰者，其中各類別所占個(gè)數(shù)表示成ki,i＝1，…，c。定義判別函數(shù)為：

gi(x)=ki,i=1,2,…,c。決策規(guī)則為：k-近鄰一般采用k為奇數(shù)，跟投票表決一樣，避免因兩種票數(shù)相等而難以決策。6.1.3.k-近鄰法決策規(guī)則§6.1近鄰法原理及其決策規(guī)則第八頁(yè)，共二十一頁(yè)，2022年，8月28日從樣本點(diǎn)x開始生長(zhǎng)，不斷擴(kuò)大區(qū)域，直到包含進(jìn)k個(gè)訓(xùn)練樣本點(diǎn)為止，并且把測(cè)試樣本點(diǎn)x的類別歸為這最近的k個(gè)訓(xùn)練樣本點(diǎn)中出現(xiàn)頻率最大的類別?！?.1.3K近鄰法第九頁(yè)，共二十一頁(yè)，2022年，8月28日k-近鄰法錯(cuò)誤率最近鄰法和k-近鄰法的錯(cuò)誤率上下界都是在一倍到兩倍貝葉斯決策方法的錯(cuò)誤率范圍內(nèi)。

在k

→∞的條件下，k-近鄰法的錯(cuò)誤率要低于最近鄰法。

在k

→∞的條件下，k-近鄰法的錯(cuò)誤率等于貝葉斯誤差率?！?.1.3K近鄰法第十頁(yè)，共二十一頁(yè)，2022年，8月28日最近鄰與k-近鄰法分類效果3-近鄰最近鄰第十一頁(yè)，共二十一頁(yè)，2022年，8月28日6.1.4.近鄰法中的幾個(gè)問(wèn)題問(wèn)題1：如何度量?jī)蓚€(gè)向量的相似性？各種距離度量§6.1近鄰法原理及其決策規(guī)則②絕對(duì)值距離（城市距離、棋盤距離）①s階明考夫斯基距離③歐幾里德距離已知兩個(gè)樣本④切比雪夫距離

s趨向無(wú)窮大時(shí)明氏距離的極限情況⑤馬哈拉諾比斯距離

第十二頁(yè)，共二十一頁(yè)，2022年，8月28日問(wèn)題2幾種距離度量之間的關(guān)系每一個(gè)彩色的平面由距離原點(diǎn)為1的點(diǎn)所形成?！?.1近鄰法原理及其決策規(guī)則第十三頁(yè)，共二十一頁(yè)，2022年，8月28日問(wèn)題3計(jì)算復(fù)雜性N個(gè)樣本，每一個(gè)樣本是d維，在對(duì)于一個(gè)未知樣本判別時(shí)，需要的計(jì)算量為？當(dāng)樣本量N非常大時(shí)，如何實(shí)時(shí)（在線）完成識(shí)別任務(wù)？對(duì)于分類來(lái)說(shuō)，每一個(gè)樣本都有價(jià)值嗎？§6.1近鄰法原理及其決策規(guī)則第十四頁(yè)，共二十一頁(yè)，2022年，8月28日6.1.5近鄰法的應(yīng)用舉例§6.1近鄰法原理及其決策規(guī)則例1：人臉識(shí)別第一步：把人臉圖像映射到一個(gè)低維的字空間中，成為空間中的一個(gè)向量；第二步：使用近鄰法對(duì)于未知的人臉圖像分類。例2：B3B4B1B2A3A1A2第十五頁(yè)，共二十一頁(yè)，2022年，8月28日B3B4B1B2A3A1A2§6.1.5近鄰法應(yīng)用舉例第十六頁(yè)，共二十一頁(yè)，2022年，8月28日小結(jié)

模式識(shí)別（機(jī)器自動(dòng)分類）的基本方法有兩大類：將特征空間劃分成決策域，需要確定判別函數(shù)或確定分界面方程。模板匹配，即將待分類樣本與標(biāo)準(zhǔn)模板進(jìn)行比較，看跟哪個(gè)模板匹配度更好些，從而確定待測(cè)試樣本的分類。前面討論的方法可以說(shuō)都是將特征空間劃分為決策域，并用判別函數(shù)或決策面方程表示決策域的方法。近鄰法則在原理上屬于模板匹配。它將訓(xùn)練樣本集中的每個(gè)樣本都作為模板，用測(cè)試樣本與每個(gè)模板做比較，看與哪個(gè)模板最相似(即為近鄰)，就按最近似的模板的類別作為自己的類別。§6.1近鄰法原理及其決策規(guī)則缺點(diǎn)：要存儲(chǔ)的模板很多，每個(gè)測(cè)試樣本要對(duì)每個(gè)模板計(jì)算一次相似度，因此在模板數(shù)量很大時(shí)，距離計(jì)算量也很大的。

優(yōu)點(diǎn)：在模板數(shù)量很大時(shí)其錯(cuò)誤率指標(biāo)還是相當(dāng)不錯(cuò)的。這就是說(shuō)近鄰法有存在的必要。

趨利避害，保留其優(yōu)點(diǎn)，克服或改進(jìn)其缺點(diǎn)呢？剪輯近鄰法與壓縮近鄰法就是兩種有代表性的改進(jìn)方法。第十七頁(yè)，共二十一頁(yè)，2022年，8月28日§6.2改進(jìn)的近鄰法改進(jìn)的方法大致分為兩種原理：一種是對(duì)樣本集進(jìn)行組織與整理，分群分層，盡可能將計(jì)算壓縮到在接近測(cè)試樣本鄰域的小范圍內(nèi)，避免盲目地與訓(xùn)練樣本集中每個(gè)樣本進(jìn)行距離計(jì)算。

另一種原理則是在原有樣本集中挑選出對(duì)分類計(jì)算有效的樣本，使樣本總數(shù)合理地減少，以同時(shí)達(dá)到既減少計(jì)算量，又減少存儲(chǔ)量的雙重效果。第六章近鄰法第十八頁(yè)，共二十一頁(yè)，2022年，8月28日第六章近鄰法6.2.1.快速搜索近鄰法

這種方法著眼于減少計(jì)算量，但不能減少存儲(chǔ)量。

基本思想：將樣本集按鄰近關(guān)系分解成組，給出每組的質(zhì)心所在，以及組內(nèi)樣本至該質(zhì)心的最大距離。這些組又可形成層次結(jié)構(gòu)，即組又分子組。因而待識(shí)別樣本可將搜索近鄰的范圍從某一大組，逐漸深入到其中的子組，直至樹的葉結(jié)點(diǎn)所代表的組，確定其相鄰關(guān)系。第十九頁(yè)，共二十一頁(yè)，2022年，8月28日6.2.2.剪輯近鄰法

基本思想是：當(dāng)不同類別的樣本在分布上有交迭部分的，分類的錯(cuò)誤率主要來(lái)自處于交迭區(qū)中的樣本。由于交迭區(qū)域中不同類別的樣本彼此穿插，導(dǎo)致用近鄰法分類出錯(cuò)。因此如果能將不同類別交界處的樣本以適當(dāng)方式篩選，可以實(shí)現(xiàn)既減少樣本數(shù)又提高正確識(shí)別率的雙重目的。為此可以利用現(xiàn)有樣本集對(duì)其自身進(jìn)行剪輯。最終目標(biāo)：去掉兩類邊界附近的樣本§6.2改進(jìn)的近鄰法第二十頁(yè)，共二十一頁(yè)，2022年