DAY02：【ML 第一彈】KNN算法

一、算法簡介

1.1 算法思想

如果一個樣本在特征空間中的 k 個最相似的樣本中的大多數屬于某一個類別，則該樣本也屬于這個類別。

1.2 樣本相似性

樣本都是屬于一個任務數據集的，樣本距離越近則越相似。

二維平面上點的歐氏距離
二維平面上點 $a(x_1, y_1)$ 與 $b(x_2, y_2)$ 間的歐氏距離：
$d_{12} = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$
三維空間點的歐氏距離
三維空間點 $a(x_1, y_1, z_1)$ 與 $b(x_2, y_2, z_2)$ 間的歐氏距離：
$d_{12} = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2 + (z_1 - z_2)^2}$
n維空間點（向量）的歐氏距離
n維空間點 $a(x11,x12,…,x1n)a(x_{11}, x_{12}, \dots, x_{1n})$ 與 $b(x21,x22,…,x2n)b(x_{21}, x_{22}, \dots, x_{2n})$ 間的歐氏距離（兩個n維向量）：
$d_{12} = \sqrt{\sum_{k=1}^{n} (x_{1k} - x_{2k})^2}$

1.3 K值的選擇

1.3.1 大小選擇

K值過小：

即用較小領域中的訓練實例進行預測
易受到異常點的影響
意味著整體模型變得復雜，容易發生過擬合

K值過大：

即用較大領域中的訓練實例進行預測
易受到樣本均衡的問題
意味著整體模型變得簡單，容易發生欠擬合

1.3.2 方法選擇

交叉驗證
網格搜索

1.4 應用方式

1.4.1 分類問題

計算未知樣本到每一個訓練樣本的距離
將訓練樣本根據距離大小升序排列
取出距離最近的 K 個訓練樣本
進行多數表決，統計 K 個樣本中哪個類別的樣本個數最多
將未知的樣本歸屬到出現次數最多的類別

1.4.2 回歸問題

計算未知樣本到每一個訓練樣本的距離
將訓練樣本根據距離大小升序排列
取出距離最近的 K 個訓練樣本
把這個 K 個樣本的目標值計算其平均值
作為將未知的樣本預測的值

二、API簡介

2.1 分類問題

class sklearn.neighbors.KNeighborsClassifier( n_neighbors=5, weights='uniform', algorithm='auto', leaf_size=30, p=2, metric='minkowski', metric_params=None, n_jobs=None 
)

2.1.1 參數說明

n_neighbors (int, default=5) ：表示K值，即預測樣本時考慮的最近鄰的數量。
weights ({‘uniform’, ‘distance’} or callable, default=‘uniform’) ：權重函數，用于確定在預測時，近鄰樣本對預測結果的影響程度。
- 'uniform'：所有鄰居的權重相同，即每個近鄰樣本在預測中具有同等的影響力。
- 'distance'：權重與距離成反比，意味著距離預測樣本越近的鄰居，對預測結果的影響越大。
- 自定義一個可調用的函數，根據距離來計算每個鄰居的權重。
algorithm ({‘auto’, ‘ball_tree’, ‘kd_tree’, ‘brute’}, default=‘auto’) ：計算最近鄰的算法。
- 'brute'：暴力搜索算法，它會計算所有樣本之間的距離，然后找出K個最近鄰。
- 'kd_tree'：KD樹算法，是一種對k維空間中的實例點進行存儲以便快速檢索的樹形數據結構，適用于低維數據，一般維數小于20時效果較好。
- 'ball_tree'：球樹算法，通過超球體來劃分樣本空間，每個節點對應一個超球體，相比KD樹在高維數據上表現更優。
- 'auto'：自動選擇最合適的算法，算法會根據訓練數據的規模、特征維度等因素來選擇。
leaf_size (int, default=30) ：僅在使用'kd_tree'或'ball_tree'算法時生效，表示KD樹或球樹的葉子節點大小。
p (int, default=2) ：距離度量的參數，僅當metric='minkowski'時有效。
- p=1：表示曼哈頓距離（L1范數），計算公式為 $d(x,y)=∑i=1n∣xi?yi∣d(x,y)=\sum_{i=1}^{n}|x_i - y_i|$ 。
- p=2：表示歐氏距離（L2范數），計算公式為 $d(x,y)=∑i=1n(xi?yi)2d(x,y)=\sqrt{\sum_{i=1}^{n}(x_i - y_i)^2}$ 。
metric (str or callable, default=‘minkowski’) ：距離度量類型。
- 'euclidean'（歐氏距離）
- 'manhattan'（曼哈頓距離）
- 'chebyshev'（切比雪夫距離）
- 'minkowski'（閔可夫斯基距離）
- 自定義一個可調用的函數，計算樣本之間的距離。
metric_params (dict, default=None) ：距離度量的額外參數，當使用自定義距離度量函數或者某些需要額外參數的距離度量時使用。
n_jobs (int, default=None) ：并行計算數。
- -1，表示使用所有可用的處理器進行并行計算，以加快計算速度。
- 具體的整數，表示使用指定數量的處理器進行并行計算。

2.1.2 常用方法

fit(X, y) ：用于擬合模型，將訓練數據X（特征矩陣，形狀為(n_samples, n_features)）和對應的標簽y（形狀為(n_samples,)）輸入該方法，模型會存儲訓練數據。
predict(X) ：預測輸入數據X（特征矩陣）的類別標簽，返回一個數組，數組中的每個元素是對應樣本的預測類別。
predict_proba(X) ：返回輸入數據X屬于各類別的概率，返回一個形狀為(n_samples, n_classes)的數組，n_samples是樣本數量，n_classes是類別數量，數組中每個元素[i][j]表示第i個樣本屬于第j個類別的概率。
kneighbors((X, n_neighbors, return_distance)) ：查找點的K近鄰。
- X：需要查找近鄰的樣本點（特征矩陣）。
- n_neighbors：指定查找的近鄰數量，如果不指定，則使用構造函數中設置的n_neighbors值。
- return_distance：布爾值，默認為True，表示是否返回距離信息。如果為True，會返回兩個數組，第一個數組是查詢點與近鄰點之間的距離，第二個數組是近鄰點在訓練數據中的索引；如果為False，只返回近鄰點在訓練數據中的索引。
score(X, y) ：返回給定測試數據X和標簽y的平均準確率，即預測正確的樣本數占總樣本數的比例，用于評估模型在測試集上的性能。

2.1.3 代碼實操

# 1. 工具包
from sklearn.neighbors import KNeighborsClassifier, KNeighborsRegressor# 2. 數據
# 分類
x = [[0,2,3],[1,3,4],[3,5,6],[4,7,8],[2,3,4]]
y = [0,0,1,1,0]# 3. 實例化
# 分類
model_1 = KNeighborsClassifier(n_neighbors=3)# 4. 訓練
model_1.fit(x,y)# 5. 預測
print("分類：", model_1.predict([[4,4,5]]))

2.2 回歸問題

class sklearn.neighbors.KNeighborsRegressor(n_neighbors=5,weights='uniform',algorithm='auto',leaf_size=30,p=2,metric='minkowski',metric_params=None,n_jobs=None
)

2.2.1 代碼實操

# 1. 工具包
from sklearn.neighbors import KNeighborsClassifier, KNeighborsRegressor# 2. 數據
# 回歸
m = [[0,1,2],[1,2,3],[2,3,4],[3,4,5]]
n = [0.1,0.2,0.3,0.4]# 3. 實例化
# 回歸
model_2 = KNeighborsRegressor(n_neighbors=3)# 4. 訓練
model_2.fit(m,n)# 5. 預測
print("回歸：", model_2.predict([[4,4,5]]))

三、距離度量方法

3.1 歐氏距離

3.1.1 定義

Euclidean Distance 歐氏距離
兩個點在空間中的距離

3.1.2 數學公式

二維平面上點的歐氏距離
二維平面上點 $a(x_1, y_1)$ 與 $b(x_2, y_2)$ 間的歐氏距離：
$d_{12} = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$
三維空間點的歐氏距離
三維空間點 $a(x_1, y_1, z_1)$ 與 $b(x_2, y_2, z_2)$ 間的歐氏距離：
$d_{12} = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2 + (z_1 - z_2)^2}$
n維空間點（向量）的歐氏距離
n維空間點 $a(x11,x12,…,x1n)a(x_{11}, x_{12}, \dots, x_{1n})$ 與 $b(x21,x22,…,x2n)b(x_{21}, x_{22}, \dots, x_{2n})$ 間的歐氏距離（兩個n維向量）：
$d_{12} = \sqrt{\sum_{k=1}^{n} (x_{1k} - x_{2k})^2}$

3.2 曼哈頓距離

3.2.1 定義

Manhattan Distance 曼哈頓距離
City Block Distance 城市街區距離
橫平豎直

3.2.2 數學公式

二維平面兩點 $a(x_1,y_1)$ 與 $b(x_2,y_2)$ 間的曼哈頓距離：
$d_{12} =|x_1 - x_2| + |y_1 - y_2|$
n維空間點 $a(x11,x12,…,x1n)a(x_{11},x_{12},\dots,x_{1n})$ 與 $b(x21,x22,…,x2n)b(x_{21},x_{22},\dots,x_{2n})$ 的曼哈頓距離：
$d_{12} = \sum_{k=1}^{n} |x_{1k} - x_{2k}|$

3.3 切比雪夫距離

3.3.1 定義

Chebyshev Distance 切比雪夫距離
國際象棋中，國王可以直行、橫行、斜行，所以國王走一步可以移動到相鄰8個方格中的任意一個。國王從格子 $x_1,y_1)$ 走到格子 $x_2,y_2)$ 最少需要的步數

3.3.2 數學公式

二維平面兩點 $a(x1,y1)\text{a}(x_1,y_1)$ 與 $b(x2,y2)\text{b}(x_2,y_2)$ 間的切比雪夫距離：
$d_{12} = \max\left(|x_1 - x_2|, |y_1 - y_2|\right)$
n維空間點 $a(x11,x12,…,x1n)\text{a}(x_{11},x_{12},\dots,x_{1n})$ 與 $b(x21,x22,…,x2n)\text{b}(x_{21},x_{22},\dots,x_{2n})$ 的切比雪夫距離：
$d_{12} = \max\left(|x_{1i} - x_{2i}|\right) \quad (i = 1,2,\dots,n)$

3.4 閔氏距離

3.4.1 定義

Minkowski Distance 閔可夫斯基距離
根據 p 的不同，閔氏距離可表示某一種類的距離

3.4.2 數學公式

兩個n維變量 $a(x11,x12,…,x1n)\boldsymbol{a}(x_{11}, x_{12}, \dots, x_{1n})$ 與 $b(x21,x22,…,x2n)\boldsymbol{b}(x_{21}, x_{22}, \dots, x_{2n})$ 間的閔可夫斯基距離定義為：
$d_{12} = \sqrt[p]{\sum_{k=1}^{n} \left| x_{1k} - x_{2k} \right|^p}$

變參數 p：
- 當 $p = 1$ 時，退化為曼哈頓距離（Manhattan Distance）
- 當 $p = 2$ 時，退化為歐氏距離（Euclidean Distance）
- 當 $\to \infty$ 時，退化為切比雪夫距離（Chebyshev Distance）

四、特征預處理

4.1 預處理的原因

特征的單位或者大小相差較大，或者某特征的方差相比其他的特征要大出幾個數量級，容易影響（支配）目標結果，使得一些模型（算法）無法學習到其它的特征。

4.2 預處理的方法

4.2.1 歸一化

定義：通過對原始數據進行變換把數據映射到 [mi, mx]（默認為 [0, 1]）之間。
數學公式：
- $\frac{x - \min}{\max - \min}$
- $X^{''} = X^{'} ? (m x ? mi) + mi$
API：sklearn.preprocessing.MinMaxScaler(feature_range=(0,1))
- feature_range=(min, max)：指定歸一化后數據的取值范圍，min 和 max 為自定義區間上下限。
特點：
- 受到最大值和最小值的影響
- 容易受到異常數據的影響，魯棒性較差
- 適合傳統精確小數據的場景
代碼實操：

# 1. 工具包
from sklearn.preprocessing import MinMaxScaler, StandardScaler# 2. 數據
x = [[90, 2, 10, 40], [60, 4, 15, 45], [75, 3, 13, 46]]# 3. 實例化
# 歸一化
process_1 = MinMaxScaler()# 4. 特征處理
res_1 = process_1.fit_transform(x)print("歸一化：", res_1.mean(), res_1.std())

4.2.2 標準化

定義：通過對原始數據進行標準化，轉換為均值為0、標準差為1的標準正態分布的數據。
數學公式：
- $\frac{x - \text{mean}}{\sigma}$
- $m e an$ ：特征平均值
- $σ\sigma$ ：特征標準差
API：sklearn.preprocessing.StandardScaler()
- with_mean=True：是否中心化（均值為 0）
- with_std=True：是否縮放（標準差為 1）
特點：
- 如果出現異常點，由于具有一定數據量，少量的異常點對于平均值的影響并不大
- 適合現代嘈雜大數據場景
代碼實操：

# 1. 工具包
from sklearn.preprocessing import MinMaxScaler, StandardScaler# 2. 數據
x = [[90, 2, 10, 40], [60, 4, 15, 45], [75, 3, 13, 46]]# 3. 實例化
# 標準化
process_2 = StandardScaler()# 4. 特征處理
res_1 = process_1.fit_transform(x)print("標準化：", res_2.mean(), res_2.std())

4.3 代碼實操

4.3.1 利用KNN算法進行鳶尾花分類

# 1. 工具包
import pandas as pd
import seaborn as sns
import matplotlib.pyplot as plt
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier# 2. 獲取數據集
from sklearn.datasets import load_iris# 3. 加載數據集
iris = load_iris()
# 查看信息
print("信息：", iris.data[:5])
# 查看目標值
print("目標值：", iris.target)
# 查看目標值名字
print("目標值名字：", iris.target_names)
# 查看特征名
print("特征名：", iris.feature_names)
# 查看描述
print("描述：", iris.DESCR)
# 查看文件路徑
print("文件路徑：", iris.filename)# 4. 可視化數據集
# 轉換數據格式為dataframe
iris_df = pd.DataFrame(iris['data'], columns=iris.feature_names)
iris_df['label'] = iris.target
print("dataframe：", iris_df.head())
# 可視化數據
sns.lmplot(x='sepal length (cm)', y='sepal width (cm)', data=iris_df, hue='label', fit_reg=False)
plt.show()# 5. 劃分數據集
X_train, X_test, Y_train, Y_test = train_test_split(iris.data, iris.target, test_size=0.3, random_state=22)# 6. 模型訓練和預測
# 數據標準化
process = StandardScaler()
X_train = process.fit_transform(X_train)
X_test = process.transform(X_test)
# 模型訓練
model = KNeighborsClassifier(n_neighbors=3)
model.fit(X_train, Y_train)
# 模型評估
model_score = model.score(X_test, Y_test)
print("準確率：", model_score)
# 模型預測
x = [[5.1, 3.5, 1.4, 0.2]]
x = process.transform(x)
y_predict =model.predict(X_test)
print("預測結果：", model.predict(x))
print("預測概率值：", model.predict_proba(x))

4.3.2 利用KNN算法實現手寫數字識別

# 1. 工具包
import matplotlib.pyplot as plt
import pandas as pd
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
import joblib
from collections import Counter# 2. 加載數據集
digit = pd.read_csv('手寫數字識別.csv')
# 顯示指定的信息
x = digit.iloc[:, 1:]
y = digit.iloc[:, 0]
print("基本信息：", x.shape)
print("類別比例：", Counter(y))
print("第一個數字標簽：", y[0])
# 顯示指定的圖片
digit_ = x.iloc[0].values
digit_ = digit_.reshape(28, 28)
plt.imshow(digit_, cmap='gray')
plt.show()# 3. 歸一化處理
x = digit.iloc[:, 1:] / 255
y = digit.iloc[:, 0]# 4. 劃分數據集
X_train, X_test,Y_train, Y_test = train_test_split(x, y, test_size=0.2, stratify=y, random_state=0)# 5. 模型訓練
model = KNeighborsClassifier(n_neighbors=3)
model.fit(X_train, Y_train)# 6. 模型評估
acc = model.score(X_test, Y_test)
print(f"準確率：{acc:.2f}")# 7. 模型保存
joblib.dump(model, 'KNN.pth')# 8. 模型預測
# 加載測試圖片
img = plt.imread('demo.png')
plt.imshow(img)
plt.show()
# 加載保存后的模型
KNN = joblib.load('KNN.pth')
# 預測測試圖片
y_pred = KNN.predict(img.reshape(1, -1))
print(f"該圖中的數字是：{y_pred}")

五、超參數選擇方法

5.1 交叉驗證

5.1.1 定義

??一種數據集的分割方法，將訓練集劃分為 n 份，拿一份做驗證集（測試集）、其他 n-1 份做訓練集。

5.1.2 原理

（假設數據集劃分為：cv=4）

第一次：把第一份數據做驗證集，其他數據做訓練。
第二次：把第二份數據做驗證集，其他數據做訓練。
… 以此類推，總共訓練4次，評估4次。
使用訓練集 + 驗證集多次評估模型，取平均值做交叉驗證為模型得分。
若 k=5 模型得分最好，再使用全部數據集（訓練集 + 驗證集）對 k=5 模型再訓練一邊，再使用測試集對 k=5 模型做評估。

5.1.3 目的

為了得到更加準確可信的模型評分。

5.2 網格搜索

5.2.1 定義

??模型調參的有力工具，尋找最優超參數的工具！只需要將若干參數傳遞給網格搜索對象，它自動幫我們完成不同超參數的組合、模型訓練、模型評估，最終返回一組最優的超參數。

5.2.2 目的

模型有很多超參數，其能力也存在很大的差異，需要手動產生很多超參數組合，來訓練模型。
每組超參數都采用交叉驗證評估，最后選出最優參數組合建立模型。

5.3 API簡介

sklearn.model_selection.GridSearchCV(estimator,param_grid=None,cv=None,scoring='accuracy',n_jobs=-1
)

參數：

estimator：待調優的模型（如 SVC、RandomForestClassifier）。
param_grid：參數字典，格式為{參數名: [取值列表]}。
cv：交叉驗證折數（整數或 CV 迭代器）。
scoring：評估指標（如accuracy、f1、roc_auc）。
n_jobs：并行計算的 CPU 核心數，-1表示全部使用。

方法：

fit(X, y)：執行網格搜索和交叉驗證。
predict(X)：使用最佳模型預測。
best_params_：最佳參數組合。
best_score_：最佳模型在驗證集上的平均分數。
cv_results_：所有參數組合的詳細結果。

5.4 代碼實操——利用KNN算法進行鳶尾花分類(2)

# 1. 工具包
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split, GridSearchCV
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_score, classification_report# 2. 加載數據集
iris = load_iris()# 3. 劃分數據集
X_train, X_test, y_train, y_test = train_test_split(iris.data, iris.target, test_size=0.2, random_state=42)# 4. 特征預處理
scaler = StandardScaler()
X_train = scaler.fit_transform(X_train)
X_test = scaler.transform(X_test)# 5. 模型實例化 + 交叉驗證 + 網格搜索
model = KNeighborsClassifier(n_neighbors=1)
param_grid = {'n_neighbors': [3, 4, 5, 6, 7, 8, 9]}
grid_search = GridSearchCV(estimator=model,param_grid=param_grid,cv=4,scoring='accuracy',n_jobs=-1
)
grid_search.fit(X_train, y_train)
# 最優參數和最佳模型性能
print(f"最佳參數: {grid_search.best_params_}")
print(f"交叉驗證最佳準確率: {grid_search.best_score_:.4f}")
# 6. 使用最優參數的模型進行預測
best_model = grid_search.best_estimator_
y_pred = best_model.predict(X_test)
# 模型評估
accuracy = accuracy_score(y_test, y_pred)
print(f"測試集準確率: {accuracy:.4f}")
# 分類報告
print("分類報告:")
print(classification_report(y_test, y_pred, target_names=iris.target_names))
# 對新樣本進行預測
new_sample = [[5.1, 3.5, 1.4, 0.2]]
new_sample_scaled = scaler.transform(new_sample)
predicted_class = best_model.predict(new_sample_scaled)
predicted_probabilities = best_model.predict_proba(new_sample_scaled)
print(f"預測樣本類別: {iris.target_names[predicted_class][0]}")
print(f"各類別概率: {[f'{p:.4f}' for p in predicted_probabilities[0]]}")