KNN（K-Nearest Neighbors）的起源與應用－晨晰統計部落格新站（統計、SPSS、BIG DATA討論園地）

筆者過去曾寫過用R執行KNN（K-Nearest Neighbors）分析(https://reurl.cc/qV5Xzp)的文章，筆者這篇將針對KNN的起源跟原理進行介紹及說明。

一、KNN (K-Nearest Neighbors)是甚麼?

KNN（K-Nearest Neighbors）是一種機器學習的監督式演算法，可用於分類和回歸。它根據一個對象周圍最近的K個鄰居的標籤來對該對象進行分類，或者是根據這些鄰居的平均值來預測該對象的值。具體來說，對於分類問題，KNN通過多數決原則來判斷新對象的類別，而對於回歸問題，KNN則是通過對標籤的平均值來進行預測。這種方法是一種無母數統計方法，因為它不假設數據的分佈，而是利用已知的數據來進行預測。

KNN的主要計算步驟包含以下三個項目，(1) 計算距離：對於每個待分類的資料點，計算其與所有已知類別資料點的距離，通常使用歐氏距離或曼哈頓距離等距離度量方法、(2) 選擇K值：選擇一個適當的K值，即要考慮多少個最近鄰居來進行分類或回歸，K值的選擇對結果影響重大、(3) 投票決定類別或平均值：根據K個最近鄰居的類別（對於分類問題）或值（對於回歸問題），以投票或平均值來決定待分類資料點的類別或數值。常見的距離計算方式有三種

如果遇到距離相等，以致無法分類的情況，這時候可以透過加權投票法去決定，實務上也盡量K值也會選擇奇數，避免這種情況的發生，K值過大會導致數據處理模糊，而選擇K值過小會使數據受個別樣本的影響。如果K值較小，則模型會使用較小鄰域內的資料進行預測，在測試集內準確率高，但是拿出去做驗證時就成效不加(外推性不佳)。K值增大可以減少估計誤差，但學習的近似誤差會增加，造成欠擬合(underfitting)，準確率過低。

二、KNN (K-Nearest Neighbors)的優缺點?

KNN的優點：

1.簡單易懂：KNN的原理非常簡單，易於理解和實現。2.廣泛的適用性：可用於分類和回歸問題，並且不需要假設數據的分佈情況。3. 對數據不敏感：能夠處理各種類型的數據，包括離散型和連續型資料。

KNN的缺點：

1.計算成本高：對於大型數據集，計算KNN的成本可能很高，因為它需要對每個預測點計算其與所有訓練點之間的距離。2.存儲空間需求大：需要保存所有訓練數據，因此隨著數據量的增加，存儲空間需求也會增加。3.對離群值敏感：KNN對離群值較為敏感，因為它主要依賴於鄰近點的標籤進行預測，如果附近大多數點的標籤與離群值不同，預測結果可能會有偏差。

三、KNN的起源與歷史背景

KNN演算法的歷史進程：

1951年: Evelyn Fix和Joseph Lawson Hodges Jr.首次提出KNN演算法，定義了最近鄰居規則。

1967年: Thomas Cover 提出了近似最近鄰（ANN）的概念，以提高KNN的效率。

1972年: 克林顿·艾塔尔提出了K-D樹的概念，進一步優化KNN演算法。

1991年: Leonard Uhr 和 Adi Littman 將KNN應用於文字識別中的字符識別。

2000年: 尼尔·斯利曼開發了IB1和IB2演算法，進一步改進了KNN的性能。

2006年: 柏林工業大學的Rosalind Picard和Tom Mitchell將KNN應用於心理健康的診斷。

四、參考資料