機器學習-K近鄰(KNN)演演算法詳解
一、KNN演演算法描述
KNN（K Near Neighbor）：找到k個最近的鄰居，即每個樣本都可以用它最接近的這k個鄰居中所佔數量最多的類別來代表。KNN演演算法屬於有監督學習方式的分類演演算法，所謂K近鄰演演算法，就是給定一個訓練資料集，對新的輸入範例，在訓練資料集中找到與該範例最鄰近的K個範例（就是上面提到的K個鄰居），如果這K個範例的多數屬於某個類，就將該輸入範例分類到這個類中，如下圖所示。
上圖中有兩種不同類別的樣本資料，分別用藍色正方形和紅色三角形表示，最中間綠色的圓表示的資料則是待分類的資料。我們現在要解決的問題是：不知道中間的圓是屬於哪一類（正方形類還是三角形類）？我們下面就來給圓分類。
從圖中還能看出：如果K=3，圓的最近的3個鄰居是2個三角形和1個正方形，少數從屬於多數，基於統計的方法，判定圓標示的這個待分類資料屬於三角形一類。但是如果K=5，圓的最近的5個鄰居是2個三角形和3個正方形，還是少數從屬於多數，判定圓標示的這個待分類資料屬於正方形這一類。由此我們可以看到，當無法判定當前待分類資料從屬於已知分類中的哪一類時，可以看它所處的位置特徵，衡量它周圍鄰居的權重，而把它歸為權重更大的一類，這就是K近鄰演演算法分類的核心思想。
二、程式碼實現
演演算法步驟：
- 計算已知類別資料集中的點與當前點之間的距離；
- 按照距離遞增依次排序；
- 選取與當前點距離最小的K個點；
- 確定前k個點所在類別的出現頻率；
- 返回前k個點出現頻率最高的類別作為當前點的預測分類
"""
kNN: k Nearest Neighbors
Input: inX: vector to compare to existing dataset (1xN)
dataSet: size m data set of known vectors (NxM)
labels: data set labels (1xM vector)
k: number of neighbors to use for comparison (should be an odd number)
Output: the most popular class label
"""
from numpy import *
import operator
from os import listdir
def classify0(inX, dataSet, labels, k):
dataSetSize = dataSet.shape[0]
diffMat = tile(inX, (dataSetSize,1)) - dataSet #將inX重複成dataSetSize行1列，tile(A,n)，功能是將陣列A重複n次，構成一個新的陣列
sqDiffMat = diffMat**2
sqDistances = sqDiffMat.sum(axis=1) #sum(axis=1)就是將矩陣的每一行向量相加
distances = sqDistances**0.5
sortedDistIndicies = distances.argsort() #argsort()得到的是排序後資料原來位置的下標
classCount={}
for i in range(k):
voteIlabel = labels[sortedDistIndicies[i]]#確定前k個距離最小元素所在的主要分類labels
classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
#計算各個元素標籤的出現次數(頻率)，當voteIlabel在classCount中時，classCount.get()返回1，否則返回0
#operator.itemgetter(1)表示按照第二個元素的次序對元組進行排序，reverse=True表示為逆序排序，即從大到小排序
sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0] #最後返回發生頻率最高的元素標籤 classify0()函數有4個輸入引數：用於分類的輸入向量是inX，輸入的訓練樣本集為dataSet，標籤向量為labels，最後的引數k表示用於選擇最近鄰居的數目，其中標籤向量的元素數目和矩陣dataSet的行數相同。除了K值之外，kNN演演算法的另一個核心引數是距離函數的選擇。上述程式碼使用的是歐式距離，在日常生活中我們所說的距離往往是歐氏距離，也即平面上兩點相連後線段的長度。歐氏距離的定義如下：
除此之外，在機器學習中常見的距離定義有以下幾種：
-
漢明距離：兩個字串對應位置不一樣的個數。漢明距離是以理查德·衛斯里·漢明的名字命名的。在資訊理論中，兩個等長字串之間的漢明距離是兩個字串對應位置的不同字元的個數。換句話說，它就是將一個字串變換成另外一個字串所需要替換的字元個數；
-
馬氏距離：表示資料的協方差距離。計算兩個樣本集相似度的距離；
-
餘弦距離：兩個向量的夾角作為一種判別距離的度量；
-
曼哈頓距離：兩點投影到各軸上的距離總和；
-
切比雪夫距離：兩點投影到各軸上距離的最大值；
-
標準化歐氏距離： 歐氏距離裡每一項除以標準差。
還有一種距離叫閔可夫斯基距離，如下：
當q為1時，即為曼哈頓距離。當q為2時，即為歐氏距離。
在這裡介紹距離的目的一個是為了讓大家使用k近鄰演演算法時，如果發現效果不太好時，可以通過使用不同的距離定義來嘗試改進演演算法的效能。
KNN演演算法的優缺點
優點：
-
理解簡單，數學知識基本為
0； -
既能用於分來，又能用於迴歸；
-
支援多分類。
kNN演演算法可以用於迴歸，迴歸的思路是將離待測點最近的k個點的平均值作為待測點的迴歸預測結果。
kNN演演算法在測試階段是看離待測點最近的k個點的類別比分，所以不管訓練資料中有多少種類別，都可以通過類別比分來確定待測點類別。
注：當然會有類別比分打平的情況，這種情況下可以看待測點離哪個類別最近，選最近的類別作為待測點的預測類別。
缺點：
當然kNN演演算法的缺點也很明顯，就是當訓練集資料量比較大時，預測過程的效率很低。這是因為kNN演演算法在預測過程中需要計算待測點與訓練集中所有點的距離並排序。可想而知，當資料量比較大的時候，效率會奇低。對於時間敏感的業務不太適合。
三、使用sklearn進行KNN分類與迴歸演演算法
1.使用sklearn中的kNN演演算法進行分類
sklearn中KNeighborsClassifier的引數
比較常用的引數有以下幾個：
n_neighbors，即K近鄰演演算法中的K值，為一整數，預設為5；
metric，距離函數。引數可以為字串（預設好的距離函數）或者是callable（可呼叫物件，大家不明白的可以理解為函數即可）。預設值為閔可夫斯基距離；
p，當metric為閔可夫斯基距離公式時，上文中的q值，預設為2。
程式碼實現：
from sklearn.neighbors import KNeighborsClassifier
def classification(train_feature, train_label, test_feature):
'''
使用KNeighborsClassifier對test_feature進行分類
:param train_feature: 訓練集資料
:param train_label: 訓練集標籤
:param test_feature: 測試集資料
:return: 測試集預測結果
'''
clf = KNeighborsClassifier()
clf.fit(train_feature, train_label)
predict_result = clf.predict(test_feature)
return predict_result
2.使用sklearn中的kNN演演算法進行迴歸
當我們需要使用kNN演演算法進行迴歸器時，只需要把KNeighborsClassifier換成KNeighborsRegressor即可。KNeighborsRegressor和KNeighborsClassifier的引數是完全一樣的，所以在優化模型時可以參考上述的內容。
程式碼實現：
from sklearn.neighbors import KNeighborsRegressor
def regression(train_feature, train_label, test_feature):
'''
使用KNeighborsRegressor對test_feature進行分類
:param train_feature: 訓練集資料
:param train_label: 訓練集標籤
:param test_feature: 測試集資料
:return: 測試集預測結果
'''
clf = KNeighborsRegressor()
clf.fit(train_feature, train_label)
predict_result = clf.predict(test_feature)
return predict_result