必須要看的前言

本文風格：以??簡單易懂??的語言帶你徹底搞懂KNN，了解什么是有監督學習算法。

認真看完這篇文章，徹底了解KNN、了解監督學習算法絕對是一樣很簡單的事情。

注：本篇文章非常詳細，同時我也附加了Python代碼，歡迎收藏后慢慢閱讀。

監督學習算法

本文主要介紹的有監督學習算法是KNN，后續會接著介紹決策樹、線性回歸等算法。

KNN/K近鄰算法

1 算法原理

首先，第一個也是最主要的問題——KNN是如何對樣本進行分類的呢？

它的本質是通過距離判斷兩個樣本是否相似，如果距離夠近就認為他們足夠相似屬于同一類別。

當然只對比一個樣本是不夠的，誤差會很大，我們需要找到離其最近的 k 個樣本，并將這些樣本稱之為「近鄰」(nearest neighbor)。對這 k 個近鄰，查看它們的都屬于何種類別（這些類別我們稱作「標簽」 (labels)）。

然后根據“少數服從多數，一點算一票”原則進行判斷，數量最多的的標簽類別就是新樣本的標簽類別。其中涉及到的原理是“越相近越相似”，這也是KNN的基本假設。

1.1 實現過程

假設 X_test 待標記的數據樣本，X_train 為已標記的數據集。

• 遍歷已標記數據集中所有的樣本，計算每個樣本與待標記點的距離，并把距離保存在 Distance 數組中。
• 對 Distance 數組進行排序，取距離最近的 k 個點，記為 X_knn。
• 在 X_knn 中統計每個類別的個數，即 class0 在 X_knn 中有幾個樣本，class1 在 X_knn 中有幾個樣本等。
• 待標記樣本的類別，就是在 X_knn 中樣本個數最多的那個類別。

1.2 距離的確定

該算法的「距離」在二維坐標軸就表示兩點之間的距離，計算距離的公式有很多。

我們常用歐拉公式，即“歐氏距離”。回憶一下，一個平面直角坐標系上，如何計算兩點之間的距離？

應該不難會想起來吧，公式應該大致如下：$$distance(A,B)=\sqrt[]{(x_A?x_B{)}^2+(y_A?y_B{)}^2}$$那如果不是在一個平面直角坐標系，而是在立體直角坐標系上，怎么計算呢？$$distance(A,B)=\sqrt[]{(x_A?x_B{)}^2+(y_A?y_B{)}^2+(z_A?z_B{)}^2}$$那如果是n維空間呢？$$distance(A,B)=\sqrt[]{(x_{1A}?x_{1B}{)}^2+(x_{2A}?x_{2B}{)}^2+(x_{3A}?x_{3B}{)}^2+......+(x_{nA}?x_{nB}{)}^2}=\sqrt[]{\sum _{i=1}^n(x_{iA}?x_{iB}{)}^2}$$而在我們的機器學習中，坐標軸上的值 $x_1$,$x_2$ ,$x_3$ ,…… $x_n$正是我們樣本數據上的 n 個特征。

2 算法的優缺點

算法參數是 k，k 可以理解為標記數據周圍幾個數作為參考對象，參數選擇需要根據數據來決定。

• k 值越大，模型的偏差越大，對噪聲數據越不敏感。
• k 值很大時，可能造成模型欠擬合。
• k 值越小，模型的方差就會越大。
• 但是 k 值太小，容易過擬合。

3 算法的變種

3.1 變種一

默認情況下，在計算距離時，權重都是相同的，但實際上我們可以針對不同的鄰居指定不同的距。離權重，比如距離越近權重越高。

• 這個可以通過指定算法的 weights 參數來實現。

3.2 變種二

使用一定半徑內的點取代距離最近的 k 個點。

• 在 scikit-learn 中，RadiusNeighborsClassifier 實現了這種算法的變種。
• 當數據采樣不均勻時，該算法變種可以取得更好的性能。

4 Python代碼實現

這里我還是先以上篇文章講到的紅酒分類為例子，待會還會有其他實例。

4.1 導入模塊

import numpy as npimport pandas as pdimport matplotlib.pyplot as plt# 解決坐標軸刻度負號亂碼plt.rcParams["axes.unicode_minus"] = False# 解決中文亂碼問題plt.rcParams["font.sans-serif"] = ["Simhei"]plt.style.use("ggplot")# plt.figure(figsize=(2,3),dpi=720)

4.2 構建已經分類好的原始數據集

首先隨機設置十個樣本點表示十杯酒，這里取了部分樣本點。

為了方便驗證，這里使用 Python 的字典 dict 構建數據集，然后再將其轉化成 DataFrame 格式。

rowdata = {"顏色深度": [14.23,13.2,13.16,14.37,13.24,12.07,12.43,11.79,12.37,12.04],           "酒精濃度": [5.64,4.38,5.68,4.80,4.32,2.76,3.94,3.1,2.12,2.6],           "品種":     [0,0,0,0,0,1,1,1,1,1]}        # 0 代表 “黑皮諾”，1 代表 “赤霞珠” wine_data = pd.DataFrame(rowdata)wine_data

X = np.array(wine_data.iloc[:,0:2]) #我們把特征（酒的屬性）放在X y = np.array(wine_data.iloc[:,-1]) #把標簽（酒的類別）放在Y

我們先來畫一下圖。

#探索數據，假如我們給出新數據[12.03,4.1] ，你能猜出這杯紅酒是什么類別么? new_data = np.array([12.03,4.1]) plt.scatter(X[y==1,0], X[y==1,1], color="red", label="赤霞珠") #畫出標簽y為1 的、關于“赤霞珠”的散點 plt.scatter(X[y==0,0], X[y==0,1], color="purple", label="黑皮諾") #畫出標簽y為0 的、關于“黑皮諾”的散點 plt.scatter(new_data[0],new_data[1], color="yellow") # 新數據點 new_data plt.xlabel("酒精濃度") plt.ylabel("顏色深度") plt.legend(loc="lower right") plt.savefig("葡萄酒樣本.png")

講道理，你應該一下就能看出來了。不過，如果是計算機，會這么分辨呢？

4.3 計算已知類別數據集中的點與當前點之間的距離。

我們使用歐式距離公式，計算新數據點 new_data 與現存的 X 數據集每一個點的距離：

from math import sqrt distance = [sqrt(np.sum((x-new_data)**2)) for x in X ] distance

那現在，我們就已經得到黃點距離其它每個點的距離啦。

4.4 將距離升序排列，然后選取距離最小的k個點。

sort_dist = np.argsort(distance) # 這里是用到了argsort方法，可以返回數據對應的下標，如果直接用sort方法的話是返回打亂的數據，我們也不好區分對應是什么類別。sort_dist

array([6, 7, 1, 4, 5, 9, 2, 8, 3, 0], dtype=int64)

6、7、4為最近的3個“數據點”的索引值，那么這些索引值對應的原數據的標簽是什么？

k = 3 topK = [y[i] for i in sort_dist[:k]] topK

[1,1,0]

這個時候我們就得到了離黃點最近的三個點對應的類別啦。

4.5 確定前k個點所在類別的計數。

# 在numpy中有mean、median方法可以求平均數和中位數，不過沒有方法直接求眾數。pd.Series(topK).value_counts().index[0]

1

所以當我們的k取3時，分類結果為1，也就是赤霞珠。大家看一下是不是跟我們人腦分辨的結果是一樣的呢？

4.6 封裝成函數

那為了后續更好的操作，我們可以將上述過程封裝成一個函數。

def KNN(new_data,dataSet,k): 	""" 	函數功能：KNN分類器 	參數說明： 	new_data: 需要預測分類的數據集 	dataSet: 已知分類標簽的數據集 	k: k-近鄰算法參數，選擇距離最小的k個點 	return: 	result: 分類結果 	""" 	from math import sqrt 	from collections import Counter 	import numpy as np 	import pandas as pd 	result = [] 	distance = [sqrt(np.sum((x-new_data)**2)) for x in np.array(dataSet.iloc[:,0:2])] 	sort_dist = np.argsort(distance) 	topK = [dataSet.iloc[:,-1