機(jī)器學(xué)習(xí)——K最近鄰算法（KNN）

---

前言

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

---

一、原理

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

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

1. 計(jì)算距離：對(duì)于給定的未知樣本（沒有標(biāo)簽值的測(cè)試集），計(jì)算它與訓(xùn)練集中每個(gè)樣本的距離。常用的距離度量方法有歐氏距離、曼哈頓距離等。

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

3. 選擇最近鄰：從訓(xùn)練集中選擇K個(gè)距離最近的樣本。

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

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

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

當(dāng)K=3時(shí)，根據(jù)距離計(jì)算，待分類的樣本點(diǎn)被劃為黃色那一類；（因?yàn)?>1)
當(dāng)K=5時(shí), 根據(jù)距離計(jì)算，待分類的樣本點(diǎn)被劃為紅色那一類；（因?yàn)?>2)

二、距離度量方法

參考文獻(xiàn)
https://zhuanlan.zhihu.com/p/354289511

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

2.1. 歐氏距離

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

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

其中，xi和yi分別表示向量x和y的第i個(gè)元素。
例如當(dāng)n = 2 時(shí)，這就是中學(xué)學(xué)的二維平面中兩點(diǎn)之間距離公式的計(jì)算了。

2.2. 曼哈頓距離

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

2.3. 閔可夫斯基距離

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

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

2.4. 余弦相似度

余弦相似度（Cosine Similarity）：余弦相似度是衡量?jī)蓚€(gè)向量方向相似程度的度量方法，它計(jì)算兩個(gè)向量之間的夾角余弦值。對(duì)于兩個(gè)n維向量x和y，余弦相似度的計(jì)算公式為：

$$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）：切比雪夫距離是兩個(gè)向量之間的最大絕對(duì)差距。對(duì)于兩個(gè)n維向量x和y，切比雪夫距離的計(jì)算公式為：
$$d(x,y)=\underset{i}{\max }(|p_i?q_i|)$$

2.6. 馬哈拉諾比斯距離

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

$$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）：漢明距離是用于比較兩個(gè)等長(zhǎng)字符串之間的差異的度量方法。對(duì)于兩個(gè)等長(zhǎng)字符串x和y，漢明距離的計(jì)算公式為：
$$d=\frac{1}{N}\sum _{i=1}^n{1}_{x_i\ne y_i}$$

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

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

這對(duì)我這種剛開始接觸的初學(xué)者是不友好的（在這之前還要學(xué)習(xí)LateX語法…）。
$$

$$
在這之間填入數(shù)學(xué)公式對(duì)應(yīng)的LaTeX語法，就能獲得對(duì)應(yīng)的數(shù)學(xué)公式

對(duì)應(yīng)的LaTeX語法可以從另一個(gè)編輯器——富文本編輯器 中獲得：

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

$$
放于這兩個(gè)之間，可以得到對(duì)應(yīng)公式：

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

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

四、代碼實(shí)現(xiàn)

2.1. 用KNN算法進(jìn)行分類

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ùn)練集和測(cè)試集
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"，距離度量默認(rèn)是閔可夫斯基距離# 擬合模型
knn.fit(X_train, y_train)# 預(yù)測(cè)
y_pred = knn.predict(X_test)# 計(jì)算準(zhǔn)確率
accuracy = accuracy_score(y_test, y_pred)
print("Accuracy:", accuracy)
Accuracy: 0.9833333333333333

2.2. 用KNN算法進(jìn)行回歸

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ùn)練集和測(cè)試集
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ù)測(cè)
y_pred = knn.predict(X_test)# 計(jì)算均方誤差
mse = mean_squared_error(y_test, y_pred)
print("MSE:", mse)
MSE: 21.65955337690632#計(jì)算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 + ..."# 計(jì)算R^2值
r2_score = model.score(X_test, y_test)
print("R^2值：", r2_score)
R^2值： 0.6687594935356289

這些模型都是十分簡(jiǎn)單的模型，還未經(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ù)樣本之間的距離來預(yù)測(cè))出發(fā)，介紹了一些常見的距離度量方法,另外也介紹了一下在Markdown編輯器中輸入數(shù)學(xué)公式，最后就是KNN算法在python中的分類和回歸代碼的實(shí)現(xiàn)。最后的最后就是模型的保存和加載。

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

–2023-9-10 筑基篇