作為『十大機(jī)器學(xué)習(xí)算法』之一的K-近鄰(K-Nearest Neighbors)算法是思想簡(jiǎn)單、易于理解的一種分類(lèi)和回歸算法。今天,我們來(lái)一起學(xué)習(xí)KNN算法的基本原理,并用Python實(shí)現(xiàn)該算法,最后,通過(guò)一個(gè)案例闡述其應(yīng)用價(jià)值。
KNN算法的直觀理解
(添加一個(gè)直觀的圖)
它基于這樣的簡(jiǎn)單假設(shè):彼此靠近的點(diǎn)更有可能屬于同一個(gè)類(lèi)別。用大俗話(huà)來(lái)說(shuō)就是『臭味相投』,或者說(shuō)『近朱者赤,近墨者黑』。
它并未試圖建立一個(gè)顯示的預(yù)測(cè)模型,而是直接通過(guò)預(yù)測(cè)點(diǎn)的臨近訓(xùn)練集點(diǎn)來(lái)確定其所屬類(lèi)別。
K近鄰算法的實(shí)現(xiàn)主要基于三大基本要素:
K的選擇;
距離度量方法的確定;
分類(lèi)決策規(guī)則。
下面,即圍繞這三大基本要素,探究它的分類(lèi)實(shí)現(xiàn)原理。
KNN算法的原理
算法步驟
K近鄰算法的實(shí)施步驟如下:
根據(jù)給定的距離度量,在訓(xùn)練集TT中尋找出與xx最近鄰的kk個(gè)點(diǎn),涵蓋這kk個(gè)點(diǎn)的xx的鄰域記作Nk(x)Nk(x);
在Nk(x)Nk(x)中根據(jù)分類(lèi)決策規(guī)則決定樣本的所屬類(lèi)別yy:
y=argmaxcj∑xi∈Nk(x)I(yi=cj),i=1,2,?,N;j=1,2,?,K.y=argmaxcj∑xi∈Nk(x)I(yi=cj),i=1,2,?,N;j=1,2,?,K.
K的選擇
K近鄰算法對(duì)K的選擇非常敏感。K值越小意味著模型復(fù)雜度越高,從而容易產(chǎn)生過(guò)擬合;K值越大則意味著整體的模型變得簡(jiǎn)單,學(xué)習(xí)的近似近似誤差會(huì)增大。
在實(shí)際的應(yīng)用中,一般采用一個(gè)比較小的K值。并采用交叉驗(yàn)證的方法,選取一個(gè)最優(yōu)的K值。
距離度量
距離度量一般采用歐式距離。也可以根據(jù)需要采用LpLp距離或明氏距離。
分類(lèi)決策規(guī)則
K近鄰算法中的分類(lèi)決策多采用多數(shù)表決的方法進(jìn)行。它等價(jià)于尋求經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化。
但這個(gè)規(guī)則存在一個(gè)潛在的問(wèn)題:有可能多個(gè)類(lèi)別的投票數(shù)同為最高。這個(gè)時(shí)候,究竟應(yīng)該判為哪一個(gè)類(lèi)別?
可以通過(guò)以下幾個(gè)途徑解決該問(wèn)題:
從投票數(shù)相同的最高類(lèi)別中隨機(jī)地選擇一個(gè);
通過(guò)距離來(lái)進(jìn)一步給票數(shù)加權(quán);
減少K的個(gè)數(shù),直到找到一個(gè)唯一的最高票數(shù)標(biāo)簽。
KNN算法的優(yōu)缺點(diǎn)
優(yōu)點(diǎn)
精度高
對(duì)異常值不敏感
沒(méi)有對(duì)數(shù)據(jù)的分布假設(shè)
缺點(diǎn)
計(jì)算復(fù)雜度高
在高維情況下,會(huì)遇到『維數(shù)詛咒』的問(wèn)題
KNN算法的算法實(shí)現(xiàn)
import os os.chdir('D:\\my_python_workfile\\Project\\Writting')os.getcwd()'D:\\my_python_workfile\\Project\\Writting'from __future__ import divisionfrom collections import Counter#from linear_algebra import distance#from statistics import meanimport math, randomimport matplotlib.pyplot as plt# 定義投票函數(shù)defraw_majority_vote(labels): votes = Counter(labels) winner,_ = votes.most_common(1)[0] return winner
以上的投票函數(shù)存在潛在的問(wèn)題:有可能多個(gè)類(lèi)別的投票數(shù)同為最高。
下面的函數(shù)則實(shí)現(xiàn)了解決方案中的第三種分類(lèi)決策方法。
# defmajority_vote(labels): """assumes that labels are ordered from nearest to farthest """ vote_counts = Counter(labels) winner,winner_count = vote_counts.most_common(1)[0] num_winners = len([count for count in vote_counts.values() if count == winner_count]) if num_winners == 1: return winner else: return majority_vote(labels[:-1]) # try again wthout the farthest# define distance functionimport math#### 減法定義defvector_substract(v,w): """substracts coresponding elements""" return [v_i - w_i for v_i,w_i in zip(v,w)]defsquared_distance(v,w): """""" return sum_of_squares(vector_substract(v,w))defdistance(v,w): return math.sqrt(squared_distance(v,w))########################################### define sum_of_squares### 向量的點(diǎn)乘defdot(v,w): return sum(v_i * w_i for v_i,w_i in zip(v,w))### 向量的平房和defsum_of_squares(v): """v_1*v_1+v_2*v_2+...+v_n*v_n""" return dot(v,v)# classifierdefknn_classify(k,labeled_points,new_point): """each labeled point should be a pair (point,label)""" # order the labeled points from nearest to farthest by_distance = sorted(labeled_points, key = lambda (point,_):distance(point,new_point)) # find the labels for the k cloest k_nearest_labels = [label for _,label in by_distance[:k]] # and let them vote return majority_vote(k_nearest_labels)KNN算法的應(yīng)用:案例分析# cities = [(-86.75,33.5666666666667,'Python'),(-88.25,30.6833333333333,'Python'),(-112.016666666667,33.4333333333333,'Java'), (-110.933333333333,32.1166666666667,'Java'),(-92.2333333333333,34.7333333333333,'R'),(-121.95,37.7,'R'), (-118.15,33.8166666666667,'Python'), (-118.233333333333,34.05,'Java'),(-122.316666666667,37.8166666666667,'R'), (-117.6,34.05,'Python'),(-116.533333333333,33.8166666666667,'Python'), (-121.5,38.5166666666667,'R'),(-117.166666666667,32.7333333333333,'R'),(-122.383333333333,37.6166666666667,'R'), (-121.933333333333,37.3666666666667,'R'),(-122.016666666667,36.9833333333333,'Python'), (-104.716666666667,38.8166666666667,'Python'),(-104.866666666667,39.75,'Python'),(-72.65,41.7333333333333,'R'), (-75.6,39.6666666666667,'Python'),(-77.0333333333333,38.85,'Python'),(-80.2666666666667,25.8,'Java'), (-81.3833333333333,28.55,'Java'),(-82.5333333333333,27.9666666666667,'Java'),(-84.4333333333333,33.65,'Python'), (-116.216666666667,43.5666666666667,'Python'),(-87.75,41.7833333333333,'Java'),(-86.2833333333333,39.7333333333333,'Java'), (-93.65,41.5333333333333,'Java'),(-97.4166666666667,37.65,'Java'),(-85.7333333333333,38.1833333333333,'Python'), (-90.25,29.9833333333333,'Java'),(-70.3166666666667,43.65,'R'),(-76.6666666666667,39.1833333333333,'R'), (-71.0333333333333,42.3666666666667,'R'),(-72.5333333333333,42.2,'R'),(-83.0166666666667,42.4166666666667,'Python'), (-84.6,42.7833333333333,'Python'),(-93.2166666666667,44.8833333333333,'Python'),(-90.0833333333333,32.3166666666667,'Java'), (-94.5833333333333,39.1166666666667,'Java'),(-90.3833333333333,38.75,'Python'),(-108.533333333333,45.8,'Python'), (-115.166666666667,36.0833333333333,'Java'),(-71.4333333333333,42.9333333333333,'R'),(-74.1666666666667,40.7,'R'), (-106.616666666667,35.05,'Python'),(-78.7333333333333,42.9333333333333,'R'),(-73.9666666666667,40.7833333333333,'R'), (-80.9333333333333,35.2166666666667,'Python'),(-78.7833333333333,35.8666666666667,'Python'),(-100.75,46.7666666666667,'Java'), (-84.5166666666667,39.15,'Java'),(-81.85,41.4,'Java'),(-82.8833333333333,40,'Java'),(-97.6,35.4,'Python'), (-122.666666666667,45.5333333333333,'Python'),(-75.25,39.8833333333333,'Python'),(-80.2166666666667,40.5,'Python'), (-71.4333333333333,41.7333333333333,'R'),(-81.1166666666667,33.95,'R'),(-96.7333333333333,43.5666666666667,'Python'), (-90,35.05,'R'),(-86.6833333333333,36.1166666666667,'R'),(-97.7,30.3,'Python'),(-96.85,32.85,'Java'), (-98.4666666666667,29.5333333333333,'Java'),(-111.966666666667,40.7666666666667,'Python'),(-73.15,44.4666666666667,'R'), (-77.3333333333333,37.5,'Python'),(-122.3,47.5333333333333,'Python'),(-95.9,41.3,'Python'),(-95.35,29.9666666666667,'Java'), (-89.3333333333333,43.1333333333333,'R'),(-104.816666666667,41.15,'Java')]cities = [([longitude,latitude],language) for longitude,latitude,language in cities]# plot_state_bordersimport resegments = []points = []lat_long_regex = r"
# try several different values for kfor k in [1,3,5,7]: num_correct = 0 for city in cities: location,actual_language = city other_cities = [other_city for other_city in cities if other_city != city] predicted_language = knn_classify(k,other_cities,location) if predicted_language == actual_language: num_correct += 1 print k,"neighbor[s]:",num_correct,"correct out of ",len(cities)1 neighbor[s]: 40 correct out of 753 neighbor[s]: 44 correct out of 755 neighbor[s]: 41 correct out of 757 neighbor[s]: 35 correct out of 75
-
python
+關(guān)注
關(guān)注
53文章
4753瀏覽量
84069 -
KNN算法
+關(guān)注
關(guān)注
0文章
2瀏覽量
6131
原文標(biāo)題:K近鄰算法的Python實(shí)現(xiàn)
文章出處:【微信號(hào):AI_shequ,微信公眾號(hào):人工智能愛(ài)好者社區(qū)】歡迎添加關(guān)注!文章轉(zhuǎn)載請(qǐng)注明出處。
發(fā)布評(píng)論請(qǐng)先 登錄
相關(guān)推薦
評(píng)論