算法簡(jiǎn)介

KNN(K近鄰算法)是一種不需要學(xué)習(xí)任何參數(shù)同時(shí)也非常簡(jiǎn)單的機(jī)器學(xué)習(xí)算法，既可以用來(lái)解決分類問(wèn)題也可以用來(lái)解決回歸問(wèn)題。直觀解釋這個(gè)算法就是'近朱者赤，近墨者黑'，當(dāng)輸入一個(gè)新樣本時(shí)，根據(jù)與其相近的樣本值來(lái)估計(jì)新輸入的樣本。如下圖所示新輸入的樣本會(huì)被分類為W1。

影響算法的幾個(gè)因子

在了解算法大體的思路后，其實(shí)還有幾個(gè)問(wèn)題需要繼續(xù)深究:

1、如何表達(dá)兩個(gè)樣本的距離(相似度)？ 

2、KNN中的K值應(yīng)該如何選??？ 

3、確定了相鄰的點(diǎn)后，如何得出最終的結(jié)果？

距離的計(jì)算:

首先我們把每個(gè)樣本的特征映射到特征空間中,樣本距離的衡量其實(shí)就是空間中兩點(diǎn)之間的距離，一般使用的是歐式距離

使用哪種方式來(lái)計(jì)算距離還是需要看具體的場(chǎng)景以及要解決的問(wèn)題(domain-knowledge)，比如輸入經(jīng)緯度的信息預(yù)測(cè)房?jī)r(jià)，計(jì)算距離的話可以直接使用經(jīng)緯度的距離計(jì)算公式。

預(yù)測(cè)黑色點(diǎn)的房?jī)r(jià)

K值的選取:

K值的選擇會(huì)對(duì)最后的結(jié)果產(chǎn)生非常大的影響，假設(shè)我們選取的k值很小那么樣本很容易被周圍的異常點(diǎn)給影響，這樣的模型容易過(guò)擬合。

下圖為是k取1時(shí)的效果圖，很明顯邊界非常不平滑并且一些異常點(diǎn)嚴(yán)重影響到了分類的結(jié)果。

K取值為1的分類效果 

那如果選擇較大的K值，就相當(dāng)于用較大范圍的訓(xùn)練實(shí)例進(jìn)行預(yù)測(cè)，可以減少異常數(shù)據(jù)的影響。假如K取值為整個(gè)樣本的大小那么最后的結(jié)果相當(dāng)于對(duì)樣本整體做了個(gè)平均，這時(shí)模型會(huì)過(guò)于簡(jiǎn)單。

總結(jié)一下：K取值越小，模型越容易過(guò)擬合。取值越大，模型越簡(jiǎn)單，發(fā)現(xiàn)不了數(shù)據(jù)的差異。

確定相鄰點(diǎn)后的的決策過(guò)程:

一般情況下直接對(duì)K個(gè)值取平均或者多數(shù)表決來(lái)決定最后的預(yù)測(cè)結(jié)果，也可以對(duì)每種類型或者不同距離的遠(yuǎn)近施加不同的權(quán)重，具體需要根據(jù)業(yè)務(wù)場(chǎng)景來(lái)決定。

算法實(shí)現(xiàn):

下面是一個(gè)非常簡(jiǎn)單的版本實(shí)現(xiàn)，每次都需要遍歷完一遍樣本集，最后取平均得出預(yù)測(cè)結(jié)果。

完成分類過(guò)程，以sklearn的KNeighborsClassifier做了一下驗(yàn)證，發(fā)現(xiàn)預(yù)測(cè)結(jié)果都是1。sklearn的KNeighborsClassifier有不同的參數(shù)可以設(shè)置，但都圍繞我們之前討論的3個(gè)問(wèn)題。

補(bǔ)充：

KNN每次在計(jì)算距離的時(shí)候都需要遍歷完全部的樣本，非常耗時(shí)。我們可以使用KD樹(shù)來(lái)優(yōu)化查詢的過(guò)程，核心思想就是把相近的樣本索引在同一個(gè)區(qū)間上，這樣每次查詢的時(shí)候只要看相近的區(qū)間都可以。這部分我沒(méi)有實(shí)現(xiàn)，有興趣的同學(xué)可以在網(wǎng)上查詢相關(guān)的資料。