前言

K最近鄰（k-NearestNeighbor，K-NN）算法是一個有監督的機器學習算法，也被稱為K-NN算法，由Cover和Hart于1968年提出。可以用于解決分類問題和回歸問題。此外，作為一個理論上比較成熟的機器學習算法，關于K近鄰算法的介紹有很多，比如算法執行的步驟、應用領域等。不過網上關于K近鄰算法的大多數介紹都非常繁雜且缺乏簡單實用的代碼示例。這樣不免會增加學習負擔，在這篇文章中我們將針對這個問題以最簡單的實例，帶大家來輕松地進階掌握K近鄰算法。

基本原理

K最近鄰算法的基本原理是，對給定的訓練數據集，對新的輸入實例，在訓練數據集中找到與該實例最近鄰的K個實例，依據“少數服從多數”的原則，根據這K個實例中占多數的類，就把該實例分為這個類。

換言之，它實際上是利用訓練數據集對特征空間進行劃分，采用測量不同特征值之間的距離方法進行分類。如下圖所示，給定了紅色和藍色的訓練樣本，綠色為測試樣本。然后計算綠色點到其他點的距離，同時選取離綠點最近的k個點。如果選定k=1時，k個點全是藍色，那預測結果就是綠色為類別1（藍色）；k=3時，k個點中兩個紅色一個藍色，這里采取“少數服從多數”原則，那預測結果就是類別2（紅色）。

在K-NN算法中，K值的選擇、實例之間距離的度量及分類決策規則是三個基本要素。

1.K值的選擇

K值的選擇會對分類結果產生重要影響。如果k值過小，新樣本選擇的范圍就小。只有與新樣本很近的點才會被選擇到，那么模型就比較復雜，容易發生過擬合。如果k值過大，新樣本選擇的范圍增大，那么模型就會變得簡單，容易發生欠擬合。舉個極端的例子，如果k的值是整個訓練集的樣本數，那么返回的永遠是訓練集中類別最多的那一類，也就失去了分類的意義。。

2.距離的度量

特征空間中兩個實例點的距離是兩個實例點相似程度的反映。K近鄰的第一步，是找到x的最近鄰。那么這個近鄰怎么衡量呢？一般我們用距離來衡量，常見的有歐氏距離和曼哈頓距離。

歐式距離如下式

而曼哈頓距離如下式

3.分類決策規則及效率

由輸入實例的K個臨近訓練實例的多數決定輸入實例的類別。這K個近臨實例的權值可以相同，也可以根據一定的規則產生不同的權值，如離輸入實例越近，權值相應也越大。此外，k近鄰算法在實現時，要計算新樣本與訓練集中每一個實例的距離。這種線性搜索會大大增加時間的消耗，尤其是在數據量很大的情況下。為了提高效率，會使用KD樹的方法。KD樹是一種二叉樹，主要是按訓練集數據的不同維度的中位數來劃分區域。

實例分析

1.前期準備

推薦使用Anaconda,它是一個用于科學計算的Python發行版。常見的科學計算類的庫都包含在里面了，使得安裝比常規python安裝要容易。更適合新手用戶實踐上手。

下面實例分析我們將使anacoda內置的Scikit-learn(簡稱sklearn)來進行。sklearn是機器學習中常用的第三方模塊，對常用的機器學習方法進行了封裝，包括回歸(Regression)、降維(DimensionalityReduction)、分類(Classfication)、聚類(Clustering)等方法。Sklearn具有簡潔且易上手的特點.

2.代碼實例示例

首先使用下面代碼在Anacoda內的spyder中生成數據集。注意語句%matplotlibinline是JupyterNotebook專用語句，用于在Notebook中直接顯示圖像。如果你是用其它的pythonIDE，如spyder或者pycharm,這個地方會報錯，顯示是invalidsyntax（無效語法）——直接注釋掉這一句即可解決報錯的問題。此外，KNN_Project_Data數據文件放置在路徑D:/datanew/KNN_Project_Data下，讀者可以根據自己的使用習慣放在自定義的路徑下。

importpandas as pd

importnumpy as np

importmatplotlib.pyplot as plt

importseaborn as sns

#%matplotlibinline

df= pd.read_csv('D:/datanew/KNN_Project_Data')

df.head()

運行結果：

從上面運行程序得到的數據集標題頭可以清楚看出，表中數據集包含10個變量（XVPM,GWYH, TRAT, TLLZ, IGGA, HYKR, EDFS, GUUB，MGJM,JHZC）和一個目標類（TARGETCLASS）。此目標類中包含給定參數的不同類。

正如我們已經看到的那樣，數據集是不標準化的。如果我們不對數據集進行標準化操作，無法得到正確的分類結果。而Sklearn第三方模塊提供了一種非常簡單的方法來幫助用戶來對數據進行標準化。使用下面代碼進行數據集標準化操作，

fromsklearn.preprocessing import StandardScaler

scaler= StandardScaler()

scaler.fit(df.drop('TARGETCLASS', axis=1))

sc_transform= scaler.transform(df.drop('TARGET CLASS', axis=1))

sc_df= pd.DataFrame(sc_transform)

sc_df.head()

打開變量查看器窗口中的標準化的數據集變量sc_df，如下圖所示

標準化后，通常我們將會對整個數據集進行劃分。第一個數據集稱為訓練數據，另一個數據集稱為測試數據。Sklearn第三方模塊可以幫助用戶簡單地將數據集化分成幾個部分。代碼如下，

fromsklearn.model_selection import train_test_split

X= sc_transform

y= df['TARGET CLASS']

X_train,X_test, y_train, y_test = train_test_split(X, y, test_size=0.3)

運行程序后，在變量窗口可以看到劃分的數據集變量X_test,X_train, y_test, y_train

正如上文K最近鄰算法基本原理部分中提到，K值的選擇是一個非常重要的問題（也稱調參）。我們希望能找到使用程序自動找出一個很好的K值，從而可以是模型的錯誤率最小化。具體實現程序代碼如下：

fromsklearn.neighbors import KNeighborsClassifier

error_rates= []

fora in range(1, 40):

k = a

knn = KNeighborsClassifier(n_neighbors=k)

knn.fit(X_train, y_train)

preds = knn.predict(X_test)

error_rates.append(np.mean(y_test - preds))

plt.figure(figsize=(10,7))

plt.plot(range(1,40),error_rates,color='blue',linestyle='dashed', marker='o',

markerfacecolor='red', markersize=10)

plt.title('ErrorRate vs. K Value')

plt.xlabel('K')

plt.ylabel('ErrorRate')

運行后，會顯示如下結果

從圖中可以看出，當K=30時，模型的錯誤率值開始趨于平穩，達到了一個非常理想的值。因此這里我們選取K=30，使用數據集X來實現K最近近鄰算法，代碼如下。

k= 30

knn= KNeighborsClassifier(n_neighbors=k)

knn.fit(X_train,y_train)

preds= knn.predict(X_test)

此后，需要對所建立的K-NN模型進行評估，代碼如下，

fromsklearn.metrics import confusion_matrix, classification_report

print(confusion_matrix(y_test,preds))

print(classification_report(y_test,preds))

程序運行后，將顯示classification_report，這是顯示主要分類指標的文本報告，如下圖所示。在報告中顯示每個類別（0，1）的精確度（precision），召回率（recall），F1值等信息。其中，精確度是關注于所有被預測為正（負）的樣本中究竟有多少是正（負）。而召回率是關注于所有真實為正（負）的樣本有多少被準確預測出來了。

結語

至此，我們使用了不到60行代碼完成了數據集創建，劃分，最優K值的尋找，K-NN算法模型建立以及評估一整套機器學習分類流程。避免了非常繁雜的數學公式以及算法理論。我們可以看出。K-NN算法非常其簡單易用，整個算法中只用提供兩個度量：k值和距離度量。同時也可以使用任意數量的類，而不僅僅是二進制分類器。這意味著向算法中添加新數據相當容易。