實(shí)例最簡(jiǎn)，帶你輕松進(jìn)階機(jī)器學(xué)習(xí)K最近鄰算法

前言

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

基本原理

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

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

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

1.K值的選擇

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

2.距離的度量

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

歐式距離如下式

而曼哈頓距離如下式

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

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

實(shí)例分析

1.前期準(zhǔn)備

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

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

2.代碼實(shí)例示例

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

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

運(yùn)行結(jié)果：

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

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

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

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

標(biāo)準(zhǔn)化后，通常我們將會(huì)對(duì)整個(gè)數(shù)據(jù)集進(jìn)行劃分。第一個(gè)數(shù)據(jù)集稱為訓(xùn)練數(shù)據(jù)，另一個(gè)數(shù)據(jù)集稱為測(cè)試數(shù)據(jù)。Sklearn第三方模塊可以幫助用戶簡(jiǎn)單地將數(shù)據(jù)集化分成幾個(gè)部分。代碼如下，

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)

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

正如上文K最近鄰算法基本原理部分中提到，K值的選擇是一個(gè)非常重要的問題（也稱調(diào)參）。我們希望能找到使用程序自動(dòng)找出一個(gè)很好的K值，從而可以是模型的錯(cuò)誤率最小化。具體實(shí)現(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')

運(yùn)行后，會(huì)顯示如下結(jié)果

從圖中可以看出，當(dāng)K=30時(shí)，模型的錯(cuò)誤率值開始趨于平穩(wěn)，達(dá)到了一個(gè)非常理想的值。因此這里我們選取K=30，使用數(shù)據(jù)集X來實(shí)現(xiàn)K最近近鄰算法，代碼如下。

k= 30

knn= KNeighborsClassifier(n_neighbors=k)

knn.fit(X_train,y_train)

preds= knn.predict(X_test)

此后，需要對(duì)所建立的K-NN模型進(jìn)行評(píng)估，代碼如下，

fromsklearn.metrics import confusion_matrix, classification_report

print(confusion_matrix(y_test,preds))

print(classification_report(y_test,preds))

程序運(yùn)行后，將顯示classification_report，這是顯示主要分類指標(biāo)的文本報(bào)告，如下圖所示。在報(bào)告中顯示每個(gè)類別（0，1）的精確度（precision），召回率（recall），F(xiàn)1值等信息。其中，精確度是關(guān)注于所有被預(yù)測(cè)為正（負(fù)）的樣本中究竟有多少是正（負(fù)）。而召回率是關(guān)注于所有真實(shí)為正（負(fù)）的樣本有多少被準(zhǔn)確預(yù)測(cè)出來了。

結(jié)語

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