柚子快報(bào)邀請(qǐng)碼778899分享：機(jī)器學(xué)習(xí)-KNN

http://yzkb.51969.com/

KNN：K最鄰近算法（K-Nearest Neighbor,KNN）

用特征空間中距離待分類(lèi)對(duì)象的最近的K個(gè)樣例點(diǎn)的類(lèi)別來(lái)預(yù)測(cè)。

投票法：K 個(gè)樣例的對(duì)數(shù)類(lèi)別。

k=1:最近鄰分類(lèi) k 通常是奇數(shù)（因?yàn)槲覀兏鶕?jù)這個(gè)K數(shù)據(jù)判斷類(lèi)別，如果是偶數(shù)可能出現(xiàn)類(lèi)別對(duì)半的情況）

基于實(shí)例學(xué)習(xí)：不需要訓(xùn)練。

K 最鄰近算法步驟：

計(jì)算待分類(lèi)對(duì)象魚(yú)所有樣例點(diǎn)的距離，找出 K 個(gè)距離最近的點(diǎn)。（目前用歐氏距離） 通過(guò)這 K 個(gè)點(diǎn)的投票決定待分類(lèi)對(duì)象的類(lèi)別。

等權(quán)投票 加權(quán)投票：相似度加權(quán)

如圖：K =3，分類(lèi)結(jié)果是三角形

? ? ? ? ? k=5，分類(lèi)結(jié)果是正方形

如果我們進(jìn)行了加權(quán)，即便是K=5，由于實(shí)例點(diǎn)離三角形特別近，分類(lèi)結(jié)果也有可能為三角形

如何確定K

K 太小，對(duì)噪音點(diǎn)敏感（早點(diǎn)附近的點(diǎn)，將都被分錯(cuò)） K太大，模型不細(xì)致（如果 K 是所有樣本數(shù)，那么分類(lèi)結(jié)果將是訓(xùn)練數(shù)據(jù)中數(shù)量最多的類(lèi)別，相當(dāng)于樸素貝葉斯分類(lèi)器中，只用了先驗(yàn)概率） K權(quán)限 模型復(fù)雜度和經(jīng)驗(yàn)風(fēng)險(xiǎn) 交差驗(yàn)證

K-D Tree(K-Dimensional Tree)

KD Tree 是一種數(shù)據(jù)結(jié)構(gòu)。對(duì) k 維空間里的點(diǎn)進(jìn)行組織，存儲(chǔ)為樹(shù)形的數(shù)據(jù)結(jié)構(gòu)。

KD Tree 為K維空間進(jìn)行分割，主要應(yīng)用于多維空間關(guān)鍵數(shù)據(jù)的搜索（如：范圍搜索和最近鄰搜索）。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 圖1

如圖1：空間先按紅線分割，然后前后兩個(gè)空間分別按綠色線分割，然后在四個(gè)空間中再按藍(lán)色線分割

建樹(shù)：

對(duì)當(dāng)前所有點(diǎn)，依次按照一個(gè)維度的中位數(shù)為切分線進(jìn)行切割,將當(dāng)前區(qū)域分為兩個(gè)區(qū)域，小于中位數(shù)放到左邊，大于中位數(shù)放到右邊。 重復(fù)步驟1，直到?jīng)]有點(diǎn)可分停止。

查找方法：（查找目標(biāo)為x）

在KD 樹(shù)中自上而下按照建樹(shù)的規(guī)則，找 x 對(duì)應(yīng)的葉子節(jié)點(diǎn)，當(dāng)做最近點(diǎn)，計(jì)算當(dāng)前最近距離。 從該葉節(jié)點(diǎn)開(kāi)始，從底向上，重復(fù)直到根節(jié)點(diǎn)：計(jì)算當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)的切分面到 x 的距離；如果該距離小于當(dāng)前前最優(yōu)距離，則在改父節(jié)點(diǎn)的另一子區(qū)域查找最近點(diǎn)，否則忽略該子區(qū)域，直接到上一層查找。

KD 樹(shù)練習(xí)：

數(shù)據(jù)（2,3）（5,4）（9,6）（4,7）（8,1）（7,2）

查找最近鄰近點(diǎn)：（4,5）（4,6）

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 圖2 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?圖3 ? ? ? ?

注意：

圖2 示：分割維度是依次輪換換著的。? K>1:我們需要在KD Tree中維護(hù)一個(gè)數(shù)據(jù)，只要到分割面距離或者到其他節(jié)點(diǎn)的距離小于數(shù)組總最大距離，就必須計(jì)算，因有可能存在節(jié)點(diǎn)去替換數(shù)組中的節(jié)點(diǎn)。 KD這個(gè)數(shù)組，我是在前幾輪算節(jié)點(diǎn)距離時(shí)，給填滿(mǎn)的。

柚子快報(bào)邀請(qǐng)碼778899分享：機(jī)器學(xué)習(xí)-KNN

http://yzkb.51969.com/

推薦文章