一、引入

問題：確定綠色圓是屬于紅色三角形、還是藍色正方形？

KNN的思想：

從上圖中我們可以看到，圖中的數據集是良好的數據，即都打好了label，一類是藍色的正方形，一類是紅色的三角形，那個綠色的圓形是我們待分類的數據。

如果K=3，那么離綠色點最近的有2個紅色三角形和1個藍色的正方形，這3個點投票，于是綠色的這個待分類點屬于紅色的三角形

如果K=5，那么離綠色點最近的有2個紅色三角形和3個藍色的正方形，這5個點投票，于是綠色的這個待分類點屬于藍色的正方形

即如果一個樣本在特征空間中的k個最相鄰的樣本中，大多數屬于某一個類別，則該樣本也屬于這個類別。我們可以看到，KNN本質是基于一種數據統計的方法！其實很多機器學習算法也是基于數據統計的。

二、KNN算法

1.介紹

KNN即K-Nearest Neighbor，是一種memory-based learning，也叫instance-based learning，屬于lazy learning。即它沒有明顯的前期訓練過程，而是程序開始運行時，把數據集加載到內存后，不需要進行訓練，就可以開始分類了。

KNN也是一種監督學習算法，通過計算新數據與訓練數據特征值之間的距離，然后選取K(K>=1)個距離最近的鄰居進行分類判(投票法)或者回歸。若K=1，新數據被簡單分配給其近鄰的類。

2.步驟

1)計算測試數據與各個訓練數據之間的距離；

(計算距離的方式前文講k-means時說過，不清楚的可以去查看以下?傳送門)

2)按照距離的遞增關系進行排序；

3)選取距離最小的K個點；

K值是由自己來確定的

4)確定前K個點所在類別的出現頻率；

5)返回前K個點中出現頻率最高的類別作為測試數據的預測分類。

說明：對于步驟5的預測分類有以下兩種方法

• 多數表決法：多數表決法類似于投票的過程，也就是在 K 個鄰居中選擇類別最多的種類作為測試樣本的類別。
• 加權表決法：根據距離的遠近，對近鄰的投票進行加權，距離越近則權重越大，通過權重計算結果最大值的類為測試樣本的類別。

特點

非參數統計方法：不需要引入參數

K的選擇：

K = 1時，將待分類樣本劃入與其最接近的樣本的類。

K = |X|時，僅根據訓練樣本進行頻率統計，將待分類樣本劃入最多的類。

K需要合理選擇，太小容易受干擾，太大增加計算復雜性。

算法的復雜度：維度災難，當維數增加時，所需的訓練樣本數急劇增加，一般采用降維處理。

三、算法優缺點

優點

簡單、有效。

重新訓練的代價較低(類別體系的變化和訓練集的變化，在Web環境和電子商務應用中是很常見的)。

計算時間和空間線性于訓練集的規模(在一些場合不算太大)。

由于KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對于類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。

該算法比較適用于樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域采用這種算法比較容易產生誤分。

缺點

KNN算法是懶散學習方法(lazy learning)，而一些積極學習的算法要快很多。

需要存儲全部的訓練樣本

輸出的可解釋性不強，例如決策樹的可解釋性較強。

該算法在分類時有個主要的不足是，當樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導致當輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本占多數。該算法只計算最近的鄰居樣本，某一類的樣本數量很大，那么或者這類樣本并不接近目標樣本，或者這類樣本很靠近目標樣本。無論怎樣，數量并不能影響運行結果。可以采用權值的方法(和該樣本距離小的鄰居權值大)來改進。

計算量較大。目前常用的解決方法是事先對已知樣本點進行剪輯，事先去除對分類作用不大的樣本。

四、KNN與K-means的區別

廢話不多說，咱直接上圖：

相似點：

雖然兩者有很大且別，但兩者也有共同之處。都包含了一個過程：給定一個點，在數據集找離它最近的點，即都用到了NN(Nearest Neighbor)算法。

五、python實例實現

下面引入一個實例，通過python代碼具體看下KNN算法的流程。

from numpy import *import operatordataSet = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])labels = ['A','A','B','B']def classify0(inX,dataSet,labels,k): #求出樣本集的行數，也就是labels標簽的數目 dataSetSize = dataSet.shape[0] #構造輸入值和樣本集的差值矩陣 diffMat = tile(inX,(dataSetSize,1)) - dataSet #計算歐式距離 sqDiffMat = diffMat**2 sqDistances = sqDiffMat.sum(axis=1) distances = sqDistances**0.5 #求距離從小到大排序的序號 sortedDistIndicies = distances.argsort() #對距離最小的k個點統計對應的樣本標簽 classCount = {} for i in range(k): #取第i+1鄰近的樣本對應的類別標簽 voteIlabel = labels[sortedDistIndicies[i]] #以標簽為key，標簽出現的次數為value將統計到的標簽及出現次數寫進字典 classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1 #對字典按value從大到小排序 sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True) #返回排序后字典中最大value對應的key return sortedClassCount[0][0]if __name__ == '__main__': print(classify0([1.1,0],dataSet,labels,3))

私信我:“學習”，可免費領取更多相關學習資料 (免費的哦)。

總結

以上是生活随笔為你收集整理的knn算法python代码_K-最近邻分类算法(KNN)及python实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。