機器學習模型：KNN (K-Nearest Neighbors)

KNN (K-Nearest Neighbors) 概述

近鄰算法 KNN 是常用的監督型算法，可用于分類或者回歸。預測新樣本的标簽的時候，根據樣本鄰域内的 K 個訓練資料的标簽來決定新樣本屬于哪個類。值得注意的是，KNN 的名稱與聚類算法 K-means 聽上去類似，但兩者是完全不同類型的算法：KNN 是監督型算法，K-means 是非監督型聚類算法。

同時，近鄰算法是非參數算法，即，算法對樣本資料本身不做假設，模型的結果是由資料本身來決定的。與之相對應的是參數算法，例如回歸模型，我們預先需要假定回歸模型的類型，例如線性回歸，對象是回歸等。這些假定是由參數決定的。

近鄰算法不需要對資料進行大量的訓練，是以算法執行的速度是很快的。

近鄰算法的三大要素是：K值，點之間距離的定義，分類決策規則。

主要優點有：

• 算法簡單易懂，不依賴于高深的數學知識。
• 訓練速度快。
• 對異常值不敏感。

主要缺點：

• 因為算法存儲所有資料的資訊，占用記憶體較大。
• 對參數 K 敏感。

KNN 算法描述

近鄰算法用于分類時，選擇新樣本鄰域内與其特征值最接近的 K 個樣本，選擇最多的類别數作為新樣本的類别。其中鄰域的選取依賴于距離度量的定義。

近鄰算法用于回歸時，選取鄰域内 K 個樣本的平均值作為新樣本的回歸預測值。

距離的度量有很多種，常用的有歐氏距離:

d(x,y)=(x1−y1)2+...+(xn−yn)2−−−−−−−−−−−−−−−−−−−−−−√=∑i=1n(xi−yi)2−−−−−−−−−−√

曼哈頓距離：

d(x,y)=|x1−y1|+...+|xn−yn|=∑i=1n|xi−yi|

闵可夫斯基距離(Minkowski Distance):

d(x,y)=[(|x1−y1|)p+...+(|xn−yn|)p]1p=[∑i=1n(|xi−yi|)p]1p,p≥1

關于 K 的選擇，沒有固定的算法。

選擇較小的 K 值，訓練資料的誤差較小，但對于測試資料容易過度拟合，因為選擇的鄰域較小，同時模型的泛化能力較差。

選擇較大的 K 值，模型變得簡單，返化能力強，但同時訓練資料的誤差增大。因為鄰域變大，距離預測樣本較遠的樣本也會對預測結果有影響。

在實際應用中，我們常使用交叉驗證來确定最佳的 K 值。即将資料拆分為訓練資料和驗證資料，逐漸增大 K 的值，并計算驗證資料的方差。一般情況下，随着 K 值得增加，驗證資料得方差呈 V 形，驗證資料方差随着 K 的增加首先減小，而後突破臨界值以後反而會上升。這個臨界值就是最佳的 K 值。

KNN 算法複雜度

理論上，對于每個新樣本，我們需要計算周遊所有樣本，計算他們的特征值到新樣本特征值的距離，進而找到在新樣本領域内的樣本。這個算法 (brute force) 雖然簡單，但是當樣本特征值數量巨大的情況下，算法的效率很低。

常用的解決方法是 KD 樹算法，和球樹算法。

KNN 用于資料的降維處理

KNN 的概念被用于資料的降維處理。基于 KNN 概念的 Uniform Manifold Approximation and Projection (UMAP) 是一種資料降維方法，盡量保持了局部和全局的樣本資料結構，相對于其他降維方法運作時間較短。

UMAP 使用梯度法 stochastic gradient descent 優化結果。它首先計算高維空間中點和點之間的距離，将他們映射到低維空間，并且計算低維空間中點之間的距離。然後利用 stochastic gradient descent 最小化距離之間的差别。算法的具體細節參見文章：

https://arxiv.org/pdf/1802.03426.pdf

KNN 程式實作：scikit

Nearest Neighbor 廣泛用于監督型(分類問題和回歸問題)和非監督型模型中，應用執行個體包括手寫字型識别，衛星圖像識别等。下面以 scikit-learn 為例講述KNN在分類問題中的應用。

scikit-learn 中的 Nearest Neighbor 分類模型有兩類：

KNeighborsClassifier： 基于新樣本周圍的k個點的資訊，這裡k 是使用者給定的常數。這是最常用的模型。

RadiusNeighborsClassifier：基于新樣本周圍半徑為r 的範圍内的點，這裡r 是使用者給定的常數。

當樣本分布不均勻時，RadiusNeighborsClassifier 是更好的選擇，給定半徑r，新樣本周圍在給定半徑r 的範圍内的點數随樣本密度分布而變化。另外，新樣本的标簽可以是周圍標明樣本标簽的平均，也可以是随距離而變化的權重平均。

在 scikit-learn 中的模型調用同樣分為四步：

第一步，建立一個模型架構，并設定所需的參數。

# Construct model; the paramters are set as default values;
>>> model = KNeighborsClassifier(n_neighbors = 3, weight='uniform', algorithm='auto', metric='minkowski')           

第二步，用建立好的模型架構拟合訓練資料。模型将會選擇最優的參數。

# Fit the model to the data;
>>> model.fit(X_train,y_train)           

第三步，用建立好的模型架構拟合訓練資料。模型将會選擇最優的參數。

# Use the model to predict the labels of test data;
>>> y_pred_lr = model.predict(X_test)           

第四步，計算模型的性能名額。

# Check the performance of model by using training data;
>>> model.score(X_train,y_train)