㈠ 8_分類演算法-k近鄰演算法（KNN）
KNN演算法是基於距離的分類和回歸方法，通過尋找與待預測樣本距離最近的K個訓練樣本，來進行預測。它主要由以下步驟組成：
1. 從訓練集合中獲取K個離待預測樣本距離最近的樣本數據；
2. 根據獲取得到的K個樣本數據來預測當前待預測樣本的目標屬性值。
在KNN演算法中，三個重要因素如下：
1. K的大小：K值選擇影響預測結果的准確性。較小的K值可能導致過擬合，較大的K值可能導致過簡化。
2. 距離度量：常用的有歐幾里得距離、曼哈頓距離等。選擇適當的度量方式對預測結果影響較大。
3. 訓練數據的質量：數據的完整性和代表性直接影響KNN演算法的性能。
在分類預測中，KNN演算法通常採用多數表決法或加權多數表決法；在回歸預測中，則採用平均值法或加權平均值法。
KNN演算法實現的關鍵在於高效地找出K個最鄰近的點，常用方法有鄰近搜索演算法、KD-Tree、Ball Tree、BBF Tree、MVP Tree等。
KNN演算法的優點在於簡單、易於理解和實現，無需估計參數或訓練過程。然而，其缺點在於計算復雜度高，尤其是在大數據集上。KNN演算法適用場景為小數據場景，一般幾千至幾萬樣本較為合適。
KD樹是一種用於在高維空間中進行數據索引的數據結構。構建KD樹的過程如下：
1. 從m個樣本的n維特徵中，選擇方差最大的第k維特徵nk作為根節點。對於該特徵，選擇取值的中位數nkv作為樣本的劃分點，將樣本分為兩部分，分別屬於左子樹和右子樹。
2. 對於每個子樹，重復上述過程，直到所有樣本被正確分類。
KD樹可以有效降低KNN演算法的計算復雜度，提高查找最近鄰的效率。在使用KNN演算法時，通常需要合理設置K值、選擇合適的距離度量方式，並結合KD樹等優化策略，以達到最佳預測效果。