本文的文字及圖片來源于網(wǎng)絡,僅供學習、交流使用,不具有任何商業(yè)用途,如有問題請及時聯(lián)系我們以作處理

原理解析

KNN-全稱K-Nearest Neighbor，最近鄰算法，可以做分類任務，也可以做回歸任務，KNN是一種簡單的機器學習方法，它沒有傳統(tǒng)意義上訓練和學習過程，實現(xiàn)流程如下：
1、在訓練數(shù)據(jù)集中，找到和需要預測樣本最近鄰的K個實例；
2、分別統(tǒng)計這K個實例所屬的類別，最多的那個類別就是樣本預測的類別(多數(shù)表決法)；
對于回歸任務而言，則是求這K個實例輸出值的平均值(選擇平均法)；

因此，該算法的幾個重點在于：
1、K值的選取，K值的不同直接會導致最終結(jié)果的不同
選擇較小的k值，就相當于用較小的領(lǐng)域中的訓練實例進行預測，訓練誤差會減小，只有與輸入實例較近或相似的訓練實例才會對預測結(jié)果起作用，與此同時帶來的問題是泛化誤差會增大，換句話說，K值的減小就意味著整體模型變得復雜，容易發(fā)生過擬合；
選擇較大的k值，就相當于用較大領(lǐng)域中的訓練實例進行預測，其優(yōu)點是可以減少泛化誤差，但缺點是訓練誤差會增大。這時候，與輸入實例較遠(不相似的)訓練實例也會對預測器作用，使預測發(fā)生錯誤，且K值的增大就意味著整體的模型變得簡單，容易欠擬合；
一般的，最佳K值的選取，我們可以用交叉驗證法來尋找，分類準確率最高的(回歸問題中就是均方誤差最小的)，就是最佳的K值；

2、距離的計算，計算最近鄰的K個樣本時，用哪種度量方式，最常用的是歐氏距離；

3、決策規(guī)則，一般就是多數(shù)表決法或者選擇平均法，但是，K個近鄰數(shù)據(jù)，到樣本的距離也不一樣，都一視同仁，也不太合理；

代碼實現(xiàn)

根據(jù)上面的KNN原理解析，我們來編寫python代碼(分類任務代碼)：

import numpy as npimport matplotlib.pyplot as pltfrom sklearn.datasets import make_classificationfrom sklearn.metrics import classification_reportclass Knn(): #默認k=5，設置和sklearn中的一樣 def __init__(self,k=5): self.k = k def fit(self,x,y): self.x = x self.y = y def predict(self,x_test): labels = [] #這里可以看出，KNN的計算復雜度很高，一個樣本就是O(m * n) for i in range(len(x_test)): #初始化一個y標簽的統(tǒng)計字典 dict_y = {} #計算第i個測試數(shù)據(jù)到所有訓練樣本的歐氏距離 diff = self.x - x_test[i] distances = np.sqrt(np.square(diff).sum(axis=1)) #對距離排名，取最小的k個樣本對應的y標簽 rank = np.argsort(distances) rank_k = rank[:self.k] y_labels = self.y[rank_k] #生成類別字典，key為類別，value為樣本個數(shù) for j in y_labels: if j not in dict_y: dict_y.setdefault(j,1) else: dict_y[j] += 1 #取得y_labels里面，value值最大對應的類別標簽即為測試樣本的預測標簽 #label = sorted(dict_y.items(),key = lambda x:x[1],reverse=True)[0][0] #下面這種實現(xiàn)方式更加優(yōu)雅 label = max(dict_y,key = dict_y.get) labels.append(label) return labels

實例展示

利用sklearn生成實驗數(shù)據(jù)集：

#有同學私信我，為什么每次都是生成2維數(shù)據(jù)，因為2維數(shù)據(jù)方便畫圖，哈哈x,y = make_classification(n_features=2,n_redundant=0,random_state=2019)plt.scatter(x[:,0],x[:,1],c=y)plt.show()

數(shù)據(jù)表現(xiàn)如上，來看看分類效果：

#預測knn = Knn()knn.fit(x,y)labels = knn.predict(x)#查看分類報告print(classification_report(y,labels))

f1的值為94%，下面畫圖看看分類邊界：

#畫等高線圖x_min,x_max = x[:,0].min() - 1,x[:,0].max() + 1y_min,y_max = x[:,1].min() - 1,x[:,1].max() + 1xx = np.arange(x_min,x_max,0.02)yy = np.arange(y_min,y_max,0.02)xx,yy = np.meshgrid(xx,yy)x_1 = np.c_[xx.ravel(),yy.ravel()]y_1 = knn.predict(x_1)#list沒有reshape方法，轉(zhuǎn)為np.array的格式plt.contourf(xx,yy,np.array(y_1).reshape(xx.shape),cmap='GnBu')plt.scatter(x[:,0],x[:,1],c=y)plt.show()

看起來還是很好的。

sklearn對比

下面調(diào)用sklearn里面的KNN庫對比效果：

from sklearn.neighbors import KNeighborsClassifierclf = KNeighborsClassifier(n_neighbors=5)clf.fit(x,y)#輸出分類報告print(classification_report(y,clf.predict(x)))#畫圖y_pred = clf.predict(x_1)plt.contourf(xx,yy,y_pred.reshape(xx.shape),cmap='GnBu')plt.scatter(x[:,0],x[:,1],c=y)plt.show()

結(jié)果基本上是一樣的。

總結(jié)

上面我們寫了python代碼，來實現(xiàn)基本的KNN分類，實際上sklearn里面的KNeighborsClassifier分類器，封裝的內(nèi)容則很多：

我們python代碼中采用的辦法稱為蠻力實現(xiàn)(brute-force)，即需要計算每一個測試樣本到所有訓練樣本的距離，才能確定最終的預測標簽，當數(shù)據(jù)集很大，特征很多，并且測試樣本也很多時，需要的計算量大家可以想象一下，基本上跑不出來結(jié)果，這點我自己是有實際案例的；

而sklearn里面則對這點做出了優(yōu)化，除了蠻力實現(xiàn)(brute-force)，還有KD樹實現(xiàn)(KDTree)和球樹(BallTree)實現(xiàn)，后兩者則大大提高了處理大數(shù)據(jù)集時的效率(感興趣的同學可自行去查找這兩者的資料)，對于這三個算法，sklearn會根據(jù)輸入的樣本，自動選擇一種算法(默認參數(shù)algorithm=‘a(chǎn)uto’)。

對于距離的計算，我們直接用的歐氏距離，在sklearn里面，封裝了很多種距離的度量方式，比如歐氏距離、曼哈頓距離、馬氏距離、閔可夫斯基距離等，默認的是p=2的閔可夫斯基距離，也就是歐氏距離。

私信小編01即可獲取大量Python學習資料

總結(jié)

以上是生活随笔為你收集整理的python实现tomasulo算法_手写算法-python代码实现KNN的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。