基本概念

K近鄰算法，即是給定一個(gè)訓練數據集，對新的輸入實(shí)例，在訓練數據集中找到與該實(shí)例最鄰近的K個(gè)實(shí)例，這K個(gè)實(shí)例的多數屬于某個(gè)類(lèi)，就把該輸入實(shí)例分類(lèi)到這個(gè)類(lèi)中。如下圖:

如上圖所示，有兩類(lèi)不同的樣本數據，分別用藍色的小正方形和紅色的小三角形表示，而圖正中間的那個(gè)綠色的圓所標示的數據則是待分類(lèi)的數據。這也就是我們的目的，來(lái)了一個(gè)新的數據點(diǎn)，我要得到它的類(lèi)別是什么？好的，下面我們根據k近鄰的思想來(lái)給綠色圓點(diǎn)進(jìn)行分類(lèi)。

• 如果K=3，綠色圓點(diǎn)的最鄰近的3個(gè)點(diǎn)是2個(gè)紅色小三角形和1個(gè)藍色小正方形，**少數從屬于多數，**基于統計的方法，判定綠色的這個(gè)待分類(lèi)點(diǎn)屬于紅色的三角形一類(lèi)。
• 如果K=5，綠色圓點(diǎn)的最鄰近的5個(gè)鄰居是2個(gè)紅色三角形和3個(gè)藍色的正方形，**還是少數從屬于多數，**基于統計的方法，判定綠色的這個(gè)待分類(lèi)點(diǎn)屬于藍色的正方形一類(lèi)。

從上面例子我們可以看出，k近鄰的算法思想非常的簡(jiǎn)單，也非常的容易理解，那么我們是不是就到此結束了，該算法的原理我們也已經(jīng)懂了，也知道怎么給新來(lái)的點(diǎn)如何進(jìn)行歸類(lèi)，只要找到離它最近的k個(gè)實(shí)例，哪個(gè)類(lèi)別最多即可。

距離的度量

距離的度量一般使用歐式距離,L_p距離或者 Minkowsji距離:

K值的選擇

如果K值選擇比較小,相對而言誤差也就會(huì )比較少,但是容易發(fā)生過(guò)擬合的現象.假設K=1,則樣本中的噪聲會(huì )對模型產(chǎn)生比較大的影響.

如果K值選擇過(guò)大就會(huì )產(chǎn)生比較大的誤差,造成誤判的現象比較嚴重.假設K=N,就會(huì )輸出所有樣本中占比比較大的類(lèi)型,而忽略掉其他類(lèi)型.

所以我們需要的K值不能太大也不能太小.

在實(shí)際應用中K值一般取比較小的值,通常采用交叉驗證的方法選取最優(yōu)的K值.

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

優(yōu)點(diǎn):簡(jiǎn)單、易于理解、容易實(shí)現、通過(guò)對K的選擇可具備丟噪音數據的健壯性.
缺點(diǎn):需要大量的空間儲存已知的實(shí)例、算法的復雜度高.因為這類(lèi)樣本實(shí)例的數量過(guò)大，但這個(gè)新的未知實(shí)例實(shí)際并未接近目標樣本.