前言

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

基本原理

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

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

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

1.K值的選擇

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

2.距離的度量

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

歐式距離如下式

而曼哈頓距離如下式

3.分類決策規(guī)則及效率

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

實例分析

1.前期準備

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

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

2.代碼實例示例

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

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()

運行結(jié)果：

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

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

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()

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

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

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)

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

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

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')

運行后，會顯示如下結(jié)果

從圖中可以看出，當K=30時，模型的錯誤率值開始趨于平穩(wěn)，達到了一個非常理想的值。因此這里我們選取K=30，使用數(shù)據(jù)集X來實現(xiàn)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），F(xiàn)1值等信息。其中，精確度是關(guān)注于所有被預測為正（負）的樣本中究竟有多少是正（負）。而召回率是關(guān)注于所有真實為正（負）的樣本有多少被準確預測出來了。

結(jié)語

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