機器學習——K最近鄰算法（KNN）

---

前言

在傳統(tǒng)機器學習中，KNN算法是一種基于實例的學習算法，能解決分類和回歸問題，而本文將介紹一下KNN即K最近鄰算法。

---

一、原理

K最近鄰（KNN）算法是一種基于實例的學習算法，用于分類和回歸問題。它的原理是根據(jù)樣本之間的距離來進行預測。
核心思想是通過找到與待分類樣本最相似的K個訓練樣本，來確定待分類樣本的類別或者預測其數(shù)值。

假設存在一個樣本數(shù)據(jù)集（訓練集），并且樣本集中每個數(shù)據(jù)都存在標簽（即知道樣本集中數(shù)據(jù)的分類情況）
KNN算法的步驟如下：

1. 計算距離：對于給定的未知樣本（沒有標簽值的測試集），計算它與訓練集中每個樣本的距離。常用的距離度量方法有歐氏距離、曼哈頓距離等。

2. 選擇K值：選擇一個合適的K值，即要考慮的最近鄰的數(shù)量。

3. 選擇最近鄰：從訓練集中選擇K個距離最近的樣本。

4. 進行投票或計算平均值：對于分類問題，根據(jù)最近鄰的標簽進行投票，選取票數(shù)最多的標簽作為預測結(jié)果。對于回歸問題，根據(jù)最近鄰的值計算平均值作為預測結(jié)果。

按我的理解其實就是將待分類的樣本與訓練集中的每個樣本去計算距離，然后從訓練集中選擇K個與待分類樣本最靠近的幾個樣本，然后再根據(jù)選取得最靠近的幾個樣本得標簽值進行投票來分類。
對于回歸問題，則統(tǒng)計K個最近鄰樣本的數(shù)值，然后通過平均或加權(quán)平均的方式計算出待分類樣本的數(shù)值。

如圖所示（可看出K值的選擇對結(jié)果有很大的影響）：

當K=3時，根據(jù)距離計算，待分類的樣本點被劃為黃色那一類；（因為2>1)
當K=5時, 根據(jù)距離計算，待分類的樣本點被劃為紅色那一類；（因為3>2)

二、距離度量方法

參考文獻
https://zhuanlan.zhihu.com/p/354289511

以下是一些常見的距離度量方法：

2.1. 歐氏距離

歐氏距離（Euclidean Distance）：歐氏距離是最常見的距離度量方法，它是兩個向量之間的直線距離。對于兩個n維向量x和y，歐氏距離的計算公式為：

$$d(x,y)=\sqrt{\sum _{i=1}^n(x_i?y_i{)}^2}$$

其中，xi和yi分別表示向量x和y的第i個元素。
例如當n = 2 時，這就是中學學的二維平面中兩點之間距離公式的計算了。

2.2. 曼哈頓距離

曼哈頓距離（Manhattan Distance）：曼哈頓距離是兩個向量之間的城市街區(qū)距離，也稱為L1距離。對于兩個n維向量x和y，曼哈頓距離的計算公式為：
$$d(x,y)=\sum _{i=1}^n|x_i?y_i|$$

2.3. 閔可夫斯基距離

閔可夫斯基距離（Minkowski Distance）：閔可夫斯基距離是歐氏距離和曼哈頓距離的一般化形式，它可以根據(jù)參數(shù)p的不同取值變化為不同的距離度量方法。對于兩個n維向量x和y，閔可夫斯基距離的計算公式為：
$$d(x,y)=\sqrt[p]{\sum _{i=1}^n|x_i?y_i{|}^p}$$

其中，xi和yi分別表示向量x和y的第i個元素，p為參數(shù)，當p=2時，閔可夫斯基距離等價于歐氏距離；當p=1時，閔可夫斯基距離等價于曼哈頓距離。

2.4. 余弦相似度

余弦相似度（Cosine Similarity）：余弦相似度是衡量兩個向量方向相似程度的度量方法，它計算兩個向量之間的夾角余弦值。對于兩個n維向量x和y，余弦相似度的計算公式為：

$$cos(\theta )=\frac{{\sum }_{i=1}^n(x_i?y_i)}{\sqrt{{\sum }_{i=1}^n(x_i{)}^2}?\sqrt{{\sum }_{i=1}^n(y_i{)}^2}}$$

2.5. 切比雪夫距離

切比雪夫距離（Chebyshev Distance）：切比雪夫距離是兩個向量之間的最大絕對差距。對于兩個n維向量x和y，切比雪夫距離的計算公式為：
$$d(x,y)=\underset{i}{\max }(|p_i?q_i|)$$

2.6. 馬哈拉諾比斯距離

馬哈拉諾比斯距離（Mahalanobis Distance）：馬哈拉諾比斯距離是一種考慮特征之間相關性的距離度量方法。它首先通過計算協(xié)方差矩陣來衡量特征之間的相關性，然后計算兩個向量在經(jīng)過協(xié)方差矩陣變換后的空間中的歐氏距離。對于兩個n維向量x和y，馬哈拉諾比斯距離的計算公式為：

$$d=\sqrt{(\vec{x}?\vec{y}{)}^T{S}^{?1}(\vec{x}?\vec{y})}$$

其中，x和y分別表示向量x和y，S為x和y的協(xié)方差矩陣。

2.7. 漢明距離

漢明距離（Hamming Distance）：漢明距離是用于比較兩個等長字符串之間的差異的度量方法。對于兩個等長字符串x和y，漢明距離的計算公式為：
$$d=\frac{1}{N}\sum _{i=1}^n{1}_{x_i\ne y_i}$$

三、在MD編輯器中輸入數(shù)學公式（額外）

在使用markdown文本編輯器時，對于數(shù)學公式的書寫一般是使用到LaTeX這個排版系統(tǒng)，基于latex語法構(gòu)建數(shù)學公式。

這對我這種剛開始接觸的初學者是不友好的（在這之前還要學習LateX語法…）。
$$

$$
在這之間填入數(shù)學公式對應的LaTeX語法，就能獲得對應的數(shù)學公式

對應的LaTeX語法可以從另一個編輯器——富文本編輯器 中獲得：

將LaTeX公式復制過來，d(x,y) = \sqrt{\sum_{i=1}^{{n}(x_{i}-y_{i})}{2}}
$$

$$
放于這兩個之間，可以得到對應公式：

$$d(x,y)=\sqrt{\sum _{i=1}^n(x_i?y_i{)}^2}$$

嗯…,其實我也不太清楚為何我的Mardown編輯器中沒有像富文本編輯器中那樣的公式編輯器，（或許是要下載插件嗎？），不用管這么多，能用就行。

四、代碼實現(xiàn)

2.1. 用KNN算法進行分類

from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score# 加載數(shù)據(jù)集
iris = load_iris()
X = iris.data
y = iris.target# 劃分訓練集和測試集
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.4, random_state=42)# 創(chuàng)建KNN分類器
knn = KNeighborsClassifier(n_neighbors=3)
#metric= "minkowski"，距離度量默認是閔可夫斯基距離# 擬合模型
knn.fit(X_train, y_train)# 預測
y_pred = knn.predict(X_test)# 計算準確率
accuracy = accuracy_score(y_test, y_pred)
print("Accuracy:", accuracy)
Accuracy: 0.9833333333333333

2.2. 用KNN算法進行回歸

from sklearn.neighbors import KNeighborsRegressor
from sklearn.datasets import load_boston
from sklearn.model_selection import train_test_split
from sklearn.metrics import mean_squared_error# 加載數(shù)據(jù)集
boston = load_boston()
X = boston.data
y = boston.target# 劃分訓練集和測試集
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)
# 創(chuàng)建KNN回歸器
knn = KNeighborsRegressor(n_neighbors=3)
# 擬合模型
knn.fit(X_train, y_train)
# 預測
y_pred = knn.predict(X_test)# 計算均方誤差
mse = mean_squared_error(y_test, y_pred)
print("MSE:", mse)
MSE: 21.65955337690632#計算R方值
print(knn.score(X_test,y_test))
0.7046442656646525#繪圖展示
import matplotlib.pyplot as plt
plt.style.use("ggplot")
plt.scatter(y_test,y_pred)
plt.plot([min(y_test),max(y_test)],[min(y_pred),max(y_pred)],"k--",color = "green", lw = 2,)
plt.xlabel("y_test")
plt.ylabel("y_pred")
plt.show()

均方誤差：

$$MSE=\frac{{\sum }_{i=1}^n(y_t?y_p{)}^2}{n}$$

再用線性回歸試一下：

from sklearn.linear_model import LinearRegression
model = LinearRegression()
model.fit(X_train, y_train)
coefficients = model.coef_
intercept = model.intercept_# 構(gòu)建回歸公式
equation = f"y = {intercept} + {coefficients[0]}*x1 + {coefficients[1]}*x2 + ..."# 計算R^2值
r2_score = model.score(X_test, y_test)
print("R^2值：", r2_score)
R^2值： 0.6687594935356289

這些模型都是十分簡單的模型，還未經(jīng)過參數(shù)的調(diào)優(yōu)和算法的優(yōu)化。

五、模型的保存和加載

#模型的保存和加載
import pickle
with open("model.pkl","wb") as f:pickle.dump(knn,f)
with open("model.pkl","rb") as f:knn_loaded = pickle.load(f)print(knn_loaded.score(X_test,y_test))
0.7046442656646525

---

總結(jié)

本文從KNN算法的原理：(根據(jù)樣本之間的距離來預測)出發(fā)，介紹了一些常見的距離度量方法,另外也介紹了一下在Markdown編輯器中輸入數(shù)學公式，最后就是KNN算法在python中的分類和回歸代碼的實現(xiàn)。最后的最后就是模型的保存和加載。

道可道，非常道；名可名，非常名。

–2023-9-10 筑基篇