 算法簡介 KNN(K近鄰算法)是一種不需要學(xué)習(xí)任何參數(shù)同時(shí)也非常簡單的機(jī)器學(xué)習(xí)算法，既可以用來解決分類問題也可以用來解決回歸問題。直觀解釋這個(gè)算法就是'近朱者赤，近墨者黑'，當(dāng)輸入一個(gè)新樣本時(shí)，根據(jù)與其相近的樣本值來估計(jì)新輸入的樣本。如下圖所示新輸入的樣本會(huì)被分類為W1。 影響算法的幾個(gè)因子 在了解算法大體的思路后，其實(shí)還有幾個(gè)問題需要繼續(xù)深究: 1、如何表達(dá)兩個(gè)樣本的距離(相似度)？ 2、KNN中的K值應(yīng)該如何選取？ 3、確定了相鄰的點(diǎn)后，如何得出最終的結(jié)果？ 距離的計(jì)算: 首先我們把每個(gè)樣本的特征映射到特征空間中,樣本距離的衡量其實(shí)就是空間中兩點(diǎn)之間的距離，一般使用的是歐式距離 使用哪種方式來計(jì)算距離還是需要看具體的場景以及要解決的問題(domain-knowledge)，比如輸入經(jīng)緯度的信息預(yù)測房價(jià)，計(jì)算距離的話可以直接使用經(jīng)緯度的距離計(jì)算公式。 預(yù)測黑色點(diǎn)的房價(jià) K值的選取: K值的選擇會(huì)對最后的結(jié)果產(chǎn)生非常大的影響，假設(shè)我們選取的k值很小那么樣本很容易被周圍的異常點(diǎn)給影響，這樣的模型容易過擬合。 下圖為是k取1時(shí)的效果圖，很明顯邊界非常不平滑并且一些異常點(diǎn)嚴(yán)重影響到了分類的結(jié)果。
那如果選擇較大的K值，就相當(dāng)于用較大范圍的訓(xùn)練實(shí)例進(jìn)行預(yù)測，可以減少異常數(shù)據(jù)的影響。假如K取值為整個(gè)樣本的大小那么最后的結(jié)果相當(dāng)于對樣本整體做了個(gè)平均，這時(shí)模型會(huì)過于簡單。 總結(jié)一下：K取值越小，模型越容易過擬合。取值越大，模型越簡單，發(fā)現(xiàn)不了數(shù)據(jù)的差異。 確定相鄰點(diǎn)后的的決策過程: 一般情況下直接對K個(gè)值取平均或者多數(shù)表決來決定最后的預(yù)測結(jié)果，也可以對每種類型或者不同距離的遠(yuǎn)近施加不同的權(quán)重，具體需要根據(jù)業(yè)務(wù)場景來決定。 算法實(shí)現(xiàn): 下面是一個(gè)非常簡單的版本實(shí)現(xiàn)，每次都需要遍歷完一遍樣本集，最后取平均得出預(yù)測結(jié)果。
完成分類過程，以sklearn的KNeighborsClassifier做了一下驗(yàn)證，發(fā)現(xiàn)預(yù)測結(jié)果都是1。sklearn的KNeighborsClassifier有不同的參數(shù)可以設(shè)置，但都圍繞我們之前討論的3個(gè)問題。
補(bǔ)充： KNN每次在計(jì)算距離的時(shí)候都需要遍歷完全部的樣本，非常耗時(shí)。我們可以使用KD樹來優(yōu)化查詢的過程，核心思想就是把相近的樣本索引在同一個(gè)區(qū)間上，這樣每次查詢的時(shí)候只要看相近的區(qū)間都可以。這部分我沒有實(shí)現(xiàn)，有興趣的同學(xué)可以在網(wǎng)上查詢相關(guān)的資料。 嚴(yán)力，一個(gè)有著老師夢的程序猿 專欄：https://zhuanlan.zhihu.com/yanli
|
|
|
