国产一级a片免费看高清,亚洲熟女中文字幕在线视频,黄三级高清在线播放,免费黄色视频在线看

KNN算法是選擇與輸入樣本在特征空間內(nèi)最近鄰的k個(gè)訓(xùn)練樣本并根據(jù)一定的決策規(guī)則，給出輸出結(jié)果 。

決策規(guī)則：

分類任務(wù)：輸出結(jié)果為k個(gè)訓(xùn)練樣本中占大多數(shù)的類 。

回歸任務(wù)：輸出結(jié)果為k個(gè)訓(xùn)練樣本值的平均值 。

如下圖的分類任務(wù)，輸出結(jié)果為w1類 。

K值的選擇、距離度量和分類決策規(guī)則是K近鄰算法的三個(gè)基本要素。當(dāng)三個(gè)要素確定后，對(duì)于任何一個(gè)新的輸入實(shí)例，它所屬的Y值也確定了，本節(jié)介紹了三要素的含義。

1. 分類決策規(guī)則

KNN算法一般是用多數(shù)表決方法，即由輸入實(shí)例的K個(gè)鄰近的多數(shù)類決定輸入實(shí)例的類。這種思想也是經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化的結(jié)果。

訓(xùn)練樣本為(xi , yi)。當(dāng)輸入實(shí)例為 x，標(biāo)記為c，

我們定義訓(xùn)練誤差率是K近鄰訓(xùn)練樣本標(biāo)記與輸入標(biāo)記不一致的比例，誤差率表示為：

因此，要使誤差率最小化即經(jīng)驗(yàn)風(fēng)險(xiǎn)最小，就要使(2.1)式右端的

2. K值的選擇：

K取值較小時(shí)，模型復(fù)雜度高，訓(xùn)練誤差會(huì)減小，泛化能力減弱；K取值較大時(shí)，模型復(fù)雜度低，訓(xùn)練誤差會(huì)增大，泛化能力有一定的提高。

KNN模型的復(fù)雜度可以通過對(duì)噪聲的容忍度來理解，若模型對(duì)噪聲很敏感，則模型的復(fù)雜度高；反之，模型的復(fù)雜度低。為了更好理解模型復(fù)雜度的含義，我們?nèi)∫粋€(gè)極端，分析K=1和K='樣本數(shù)'的模型復(fù)雜度。

由上圖可知，K=1時(shí)，模型輸出的結(jié)果受噪聲的影響很大。

由上圖可知，樣本數(shù)等于7，當(dāng)K=7時(shí)，不管輸入數(shù)據(jù)的噪聲有多大，輸出結(jié)果都是綠色類，模型對(duì)噪聲極不敏感，但是模型太過簡(jiǎn)單，包含的信息太少，也是不可取的。

通過上面兩種極端的K選取結(jié)果可知，K值選擇應(yīng)適中，K值一般小于20，建議采用交叉驗(yàn)證的方法選取合適的K值。

3. 距離度量

KNN算法用距離來度量?jī)蓚€(gè)樣本間的相似度，常用的距離表示方法：

(1)、歐式距離

(2)、曼哈頓距離

(3)、閔可夫斯基距離

可以看出，歐式距離是閔可夫斯基距離在p=2時(shí)的特例，而曼哈頓距離是p=1時(shí)的特例 。

暴力搜索（brute-force search）是線性掃描輸入實(shí)例與每一個(gè)訓(xùn)練實(shí)例的距離并選擇前k個(gè)最近鄰的樣本來多數(shù)表決，算法簡(jiǎn)單，但是當(dāng)訓(xùn)練集或特征維度很大時(shí)，計(jì)算非常耗時(shí)，故這種暴力實(shí)現(xiàn)原理是不可行的 。

kd樹是一種對(duì)k維空間中的實(shí)例點(diǎn)進(jìn)行存儲(chǔ)以便對(duì)其進(jìn)行快速檢索的樹形數(shù)據(jù)結(jié)構(gòu)，構(gòu)造kd樹相當(dāng)于不斷用垂直于坐標(biāo)軸的超平面將k維空間進(jìn)行劃分，構(gòu)成一系列的K維超矩形區(qū)域，kd樹省去了對(duì)大部分?jǐn)?shù)據(jù)的搜索，大大的較少了計(jì)算量。

kd樹的KNN算法實(shí)現(xiàn)包括三部分：kd樹的構(gòu)建，kd樹的搜索和kd樹的分類。

1. 構(gòu)建kd樹

kd樹實(shí)質(zhì)是二叉樹，其劃分思想與cart樹一致，即切分使樣本復(fù)雜度降低最多的特征。kd樹認(rèn)為特征方差越大，則該特征的復(fù)雜度亦越大，優(yōu)先對(duì)該特征進(jìn)行切分 ，切分點(diǎn)是所有實(shí)例在該特征的中位數(shù)。重復(fù)該切分步驟，直到切分后無樣本則終止切分，終止時(shí)的樣本為葉節(jié)點(diǎn)。

【例】給定一個(gè)二維空間的數(shù)據(jù)集：

構(gòu)造kd樹的步驟：

(1)、數(shù)據(jù)集在維度

(2)、 數(shù)據(jù)集在

(3)、分別對(duì)左右兩個(gè)矩形的樣本在

(4)、重復(fù)步驟（2）（3），直到無樣本，該節(jié)點(diǎn)為葉子節(jié)點(diǎn)。

如下圖，綠色為葉子節(jié)點(diǎn) ，紅色為節(jié)點(diǎn)和根節(jié)點(diǎn)。

2. KD樹搜索

(1)、搜索路徑從根節(jié)點(diǎn)到葉節(jié)點(diǎn)，在KD樹里面找到包含目標(biāo)點(diǎn)的葉子節(jié)點(diǎn)。

(2)、搜索路徑從葉節(jié)點(diǎn)到根節(jié)點(diǎn)，找到距離目標(biāo)點(diǎn)最近的樣本實(shí)例點(diǎn)。過程不再復(fù)述，具體方法請(qǐng)參考李航博士《統(tǒng)計(jì)學(xué)習(xí)方法》。

3. KD樹預(yù)測(cè)

每一次搜尋與輸入樣本最近的樣本節(jié)點(diǎn)，然后忽略該節(jié)點(diǎn)，重復(fù)同樣步驟K次，找到與輸入樣本最近鄰的K個(gè)樣本 ，投票法確定輸出結(jié)果。

若正負(fù)樣本處于不平衡狀態(tài)，運(yùn)用投票決策的KNN算法判斷輸入樣本的所屬類別：

結(jié)果顯示輸入樣本為綠色類 。原因是紅色類的個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于綠色樣本，導(dǎo)致出現(xiàn)的分類錯(cuò)誤 。

（1）若分類決策選擇限定半徑最近鄰法，即以輸入樣本為圓心，最大半徑R的圓內(nèi)選擇出現(xiàn)次數(shù)最多的類做為輸入樣本的類 。如下圖，黑色樣本的分類結(jié)果正確。

（2）投票法是默認(rèn)每個(gè)樣本的權(quán)重相等，我們假定權(quán)重與距離成反比，即距離越大，對(duì)結(jié)果的影響越小，那么該樣本的權(quán)重也越小，反之，權(quán)重則越大，根據(jù)權(quán)重對(duì)輸入樣本進(jìn)行分類 。這種思想與adaBoost算法相似，分類性能好的弱分類器給予一個(gè)大的權(quán)重 。

分類過程：

(1)、選擇與輸入樣本距離X0最近的K個(gè)訓(xùn)練樣本Xi（i = 1,2,...,K），d(X0,Xi)表示輸入樣本和訓(xùn)練樣本的距離。 

(2)、根據(jù)距離與樣本成反比的性質(zhì)將距離轉(zhuǎn)化成權(quán)重Wi，Wi表示輸入樣本X0與訓(xùn)練樣本Xi的權(quán)重。

(3)、我們累加每一類的樣本權(quán)重，并認(rèn)為該權(quán)重占所有權(quán)重和的比例是該類的生成概率，概率最大的類就是輸入樣本的分類結(jié)果。

假設(shè)目標(biāo)是二分類{C1，C2}，表達(dá)式：

若

回歸過程：

（1）（2）步驟與分類過程一直，第（3）步使用如下表達(dá)式得到回歸值：

其中，y為輸出結(jié)果，f(xi)為最近鄰樣本的值。若權(quán)重相同的話，則輸出結(jié)果為K個(gè)訓(xùn)練樣本的平均值。

用權(quán)重思想重新對(duì)上例進(jìn)行分類，可得輸入樣本為紅色類。

優(yōu)點(diǎn)：

1）算法簡(jiǎn)單，理論成熟，可用于分類和回歸。

2）對(duì)異常值不敏感。

3）可用于非線性分類。

4）比較適用于容量較大的訓(xùn)練數(shù)據(jù)，容量較小的訓(xùn)練數(shù)據(jù)則很容易出現(xiàn)誤分類情況。

5）KNN算法原理是根據(jù)鄰域的K個(gè)樣本來確定輸出類別，因此對(duì)于不同類的樣本集有交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為合適。

缺點(diǎn)：

1）時(shí)間復(fù)雜度和空間復(fù)雜度高。

2）訓(xùn)練樣本不平衡，對(duì)稀有類別的預(yù)測(cè)準(zhǔn)確率低。

3）相比決策樹模型，KNN模型可解釋性不強(qiáng)。