算法核心

KNN算法的核心思想是“近朱者赤，近墨者黑”。對于一個待分類或預測的樣本點，它會查找訓練集中與其距離最近的K個樣本點（即“最近鄰”）。然后根據這K個最近鄰的標簽信息來對當前樣本進行分類或回歸。 在分類任務中，通常是根據K個最近鄰中出現次數最多的類別來確定待分類樣本的類別；在回歸任務中，則是根據K個最近鄰的目標值的平均值來預測待預測樣本的目標值。

?例如在圖中：

如果我們以k=3畫圓，因為在圓圈內ClassB出現的數量要比ClassA更多，因此我們可以把它歸到ClassB

但如果我們以k=6畫圓，因為在圓圈內ClassA出現的數量要比ClassB更多，因此我們可以把它歸到ClassA

值得注意的是：這里的k是離我們觀測點最近的第k個點，而非半徑

距離選擇

這里的距離可以采用不同的求法，常見的距離度量方式有：

? 歐氏距離：這是最常見的距離度量方式，它計算的是樣本點在多維空間中的直線距離。對于兩個樣本點 x = (x_1, x_2, ..., x_n) 和 y = (y_1, y_2, ..., y_n) ，歐氏距離定義為 \sqrt{(x_1 - y_1)^2 + (x_2 - y_2)^2 + ...?+ (x_n - y_n)^2} 。? 曼哈頓距離：它計算的是樣本點在坐標軸方向上的絕對距離之和，即 |x_1 - y_1| + |x_2 - y_2| + ...?+ |x_n - y_n| 。在某些場景下，比如在城市街區網格中計算兩點之間的距離時，曼哈頓距離更符合實際情況。

? 明可夫斯基距離：它是一種更通用的距離度量，歐氏距離和曼哈頓距離都是它的特例。明可夫斯基距離的定義為

?當 p = 2 時，就是歐氏距離；當 p = 1 時，就是曼哈頓距離

?K值的選擇

K值的選擇對KNN算法的性能影響很大。 如果K值選得太小，算法會過于敏感，容易受到噪聲數據的影響。例如，當K = 1時，一個噪聲點可能會直接影響到分類或回歸的結果。如果K值選得太大，算法又會過于“平滑”，可能會將不同類別的樣本混合在一起。比如在一個復雜的分類問題中，如果K值過大，可能會導致不同類別之間的邊界模糊。 通常，k值選擇時一般選擇的是比較小的值，像是3、5、7、9這樣的個位單數

kd樹優化算法

kd樹（k-d tree，k維樹）是用于優化KNN算法中最近鄰搜索過程的一種數據結構。

kd樹的作用

1. 加速最近鄰搜索

? 在KNN算法中，最耗時的部分是計算待預測點與訓練集中所有點之間的距離，以找到最近的K個鄰居。當訓練集規模很大時，這種暴力搜索方法效率非常低。

? kd樹通過將訓練數據組織成一種樹形結構，能夠快速定位到與目標點最近的區域，從而減少需要計算距離的點的數量，大大加快最近鄰搜索的速度。

2. 空間劃分

? kd樹是一種二叉樹結構，它通過遞歸地將數據空間劃分為超矩形區域。在每次劃分時，選擇一個維度（通常是方差最大的維度）作為劃分軸，將數據點按照該維度的中值分為兩部分，分別存儲在樹的左子樹和右子樹中。通過這種方式，kd樹將整個數據空間劃分為多個小區域，每個區域對應樹中的一個節點。

kd樹的構建過程

1. 選擇劃分維度

? 在構建kd樹時，需要選擇一個維度作為劃分軸。通常會選擇方差最大的維度，因為方差大的維度意味著數據在這個方向上的分布更分散，劃分效果更好。

2. 選擇劃分點

? 在選定的維度上，選擇該維度的中值作為劃分點。將小于中值的點分配到左子樹，大于中值的點分配到右子樹。

3. 遞歸劃分

? 對左右子樹重復上述過程，每次選擇不同的維度進行劃分，直到每個區域只包含一個數據點，或者滿足其他停止條件。

kd樹在KNN中的使用

1. 搜索最近鄰

? 當需要找到某個目標點的最近鄰時，kd樹會從根節點開始，沿著樹的結構向下搜索。根據目標點在當前劃分維度上的值，決定是進入左子樹還是右子樹。通過這種方式，可以快速定位到目標點所在的區域。

2. 回溯查找

? 單純沿著樹向下搜索可能無法找到真正的最近鄰，因為可能存在其他區域的點距離目標點更近。因此，在搜索到葉子節點后，需要進行回溯。在回溯過程中，檢查每個節點的劃分超平面與目標點的距離，如果這個距離小于當前已知的最近距離，就需要檢查另一側子樹，以確保找到真正的最近鄰。

示例場景

假設我們有一個二維空間中的數據點集合，目標是找到某個目標點\(P\)的最近鄰點。我們將通過以下步驟來展示如何利用空間劃分和距離關系來優化搜索過程。

1.數據點和目標點

假設我們有以下數據點：

? \(A(1,1)\)

? \(B(2,2)\)

? \(C(10,10)\)

? \(D(11,11)\)

? \(E(12,12)\)

目標點\(P\)的坐標為\((0,0)\)。

2.構建空間劃分結構（如kd樹）

為了優化搜索過程，我們首先構建一個kd樹。假設我們按照以下步驟構建kd樹：

1. 選擇第一個維度（x軸）作為劃分軸，找到中值點\(B(2,2)\)。

2. 將數據點分為兩部分：

? 左子樹：\(A(1,1)\)

? 右子樹：\(C(10,10)\)，\(D(11,11)\)，\(E(12,12)\)

3. 對右子樹，選擇第二個維度（y軸）作為劃分軸，找到中值點\(D(11,11)\)。

4. 繼續劃分，直到每個區域只包含一個點。

構建的kd樹如下：

? ? ? ? B(2, 2)/ \A(1, 1) D(11, 11)/ \C(10, 10) E(12, 12)

3.利用距離關系跳過某些點

現在，我們從目標點\(P(0,0)\)開始搜索其最近鄰點。

第一步：從根節點開始

? 從根節點\(B(2,2)\)開始，計算\(P\)與\(B\)的距離：

?第二步：選擇子樹

? 由于\(P\)的 x 坐標小于\(B\)的 x 坐標，我們進入左子樹，到達點\(A(1,1)\)。

? 計算\(P\)與\(A\)的距離：

?? 目前，\(A\)是最近鄰點，最近距離為\(\sqrt{2}\)。

第三步：回溯并跳過某些點

? 回溯到根節點\(B\)。檢查右子樹是否可能包含更近的點。

? 計算目標點\(P\)到右子樹劃分超平面（x=2）的距離：

?? 由于\(2>\sqrt{2}\)，這意味著右子樹中任何點到\(P\)的距離都不會小于當前的最近距離\(\sqrt{2}\)。因此，我們可以跳過右子樹中的所有點（\(C\)，\(D\)，\(E\)），而不需要進一步計算它們與\(P\)的距離。

4.優化后的搜索過程

通過上述步驟，我們利用了空間劃分（kd樹）和距離關系（跳過距離遠的點）來優化搜索過程。最終，我們確定\(A(1,1)\)是目標點\(P(0,0)\)的最近鄰點，而無需計算\(P\)與右子樹中所有點的距離。

5.復雜度分析

? 暴力搜索：計算目標點與所有點的距離，復雜度為\(O(DN)\)。

? 優化后的搜索：通過kd樹的空間劃分和跳過無關區域，復雜度降低到\(O(DN\log N)\)。這是因為：

? 構建kd樹的復雜度為\(O(N\log N)\)。

? 搜索過程通過遞歸和回溯，每次只需要檢查部分點，而不是所有點。

應用實例

以下是一個使用Python和`scikit-learn`庫實現的KNN算法對鳶尾花（Iris）數據集進行分類的完整代碼示例。鳶尾花數據集是機器學習中常用的入門數據集，包含150個樣本，每個樣本有4個特征（花萼長度、花萼寬度、花瓣長度、花瓣寬度），分為3個類別。
?

# 導入必要的庫
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import classification_report, confusion_matrix, accuracy_score# 加載鳶尾花數據集
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.3, random_state=42)# 數據標準化
scaler = StandardScaler()
X_train = scaler.fit_transform(X_train)
X_test = scaler.transform(X_test)# 創建KNN分類器
k = 3 ?# 選擇K值
knn = KNeighborsClassifier(n_neighbors=k)# 訓練模型
knn.fit(X_train, y_train)# 進行預測
y_pred = knn.predict(X_test)# 評估模型
print("混淆矩陣：")
print(confusion_matrix(y_test, y_pred))
print("\n分類報告：")
print(classification_report(y_test, y_pred))
print("\n準確率：")
print(accuracy_score(y_test, y_pred))# 輸出測試集的真實標簽和預測標簽
print("\n測試集的真實標簽：", y_test)
print("測試集的預測標簽：", y_pred)

代碼說明

1. 加載數據集

? 使用`load_iris()`函數加載鳶尾花數據集。

? 數據集包含150個樣本，每個樣本有4個特征，分為3個類別（0、1、2）。

2. 劃分訓練集和測試集

? 使用`train_test_split()`函數將數據集劃分為訓練集和測試集，其中測試集占30%。

? 設置`random_state`參數以確保結果的可重復性。

3. 數據標準化

? 使用`StandardScaler`對特征數據進行標準化處理，使每個特征的均值為0，標準差為1。這有助于提高KNN算法的性能。

4. 創建KNN分類器

? 使用`KNeighborsClassifier`創建KNN分類器，設置`n_neighbors=k`，其中`k`是最近鄰的數量。

5. 訓練模型

? 使用`fit()`方法訓練模型。

6. 進行預測

? 使用`predict()`方法對測試集進行預測。

7. 評估模型

? 使用`confusion_matrix`、`classification_report`和`accuracy_score`評估模型的性能。

? 輸出混淆矩陣、分類報告和準確率。

?注意事項

1. K值的選擇

? K值的選擇對KNN算法的性能有很大影響。可以通過交叉驗證等方法來選擇最優的K值。

2. 數據標準化

? 對于KNN算法，數據標準化是非常重要的，因為KNN依賴于距離計算，而不同特征的量綱可能不同。

3. 數據集劃分

? 數據集的劃分方式可能會影響模型的性能，可以通過多次劃分或使用交叉驗證來評估模型的穩定性。

?

?