k-Nearest Neighbors算法（簡稱KNN算法）的邏輯很簡單，它易於理解和實現，是你可以使用的有力工具。
通過學習這個教程，你將能夠用Python從0開始實現一個KNN算法。這個實現主要用來處理分類問題，我們將使用鳶尾花分類問題來演示這個例子。
這個教程的學習要求是你能夠使用Python編碼，並且對實現一個KNN算法感興趣。
什麼是k-Nearest Neighbors？
KNN的模型是整個訓練數據集。當我們需要預測一個新實例的某個屬性A時，KNN算法會搜索訓練數據集找到K個最相似的實例。這些相似實例的A屬性會被總結歸納，作為新實例A屬性的預測。
如何判斷實例之間的相似程度，這需要具體看數據的類型。對於實數數據，我們可以使用歐式距離。對於分類或者二進位數據，我們可以使用漢明距離。
對於回歸問題，可以使用預測值的平均值。對於分類問題，可以返回最普遍的一類。
KNN算法是如何工作的？
KNN算法屬於基於實例的、競爭學習與懶惰學習算法。
基於實例的算法是算法模型使用數據實例（或者說數據行），並依據這些實例做出預測的算法。KNN算法是基於實例算法中的一個極端例子，因為所有的訓練數據都成了算法模型的一部分。
它是一個競爭學習邏輯，因為它內部使用模型元素（數據實例）之間的競爭來作出預測。數據實例之間的相似性計算導致每一個數據實例都競爭去「贏」，或者說競爭去和需要預測的元素相似，再或者說競爭為預測結果做貢獻。
說它是懶惰學習算法是因為一直到需要進行預測操作了，它才會建立一個預測模型，它總是最後需要出結果的時候才開始幹活。
它的優勢是只有跟需要預測元素相似的數據實例才會其作用，可以稱之為一個局部模型。劣勢是計算成本很高，因為它在一個很大的訓練集上重複做著相似的搜索。
最後，KNN很有用，因為它不對數據做任何的假設，同時使用一致的規則在任意兩個數據實例之間計算距離。也因為如此，它被稱作非參數，或者非線性算法，因為它沒有假設一個模型函數。
使用測量來分類花朵
本教程使用的練習問題是分類鳶尾花。
已有的數據集由對3個不同品種的鳶尾花的150組觀察數據組成。對於這些花有4個測量維度：萼片長度、萼片寬度、花瓣長度、花瓣寬度，所有的數值都以釐米為單位。需要預測的屬性是品種，品種的可能值有：清風藤、雲芝、錦葵。
我們有一個標準數據集，在這個數據集中品種是已知的。我們可以把這個數據集切分成訓練數據集和測試數據集，然後用測試結果來評估算法的準確程度。在這個問題上，好的分類算法應該有大於90%的正確率，通常都會達到96%甚至更高。
你可以從https://archive.ics.uci.edu/ml/machine-learning-databases/iris/iris.data 免費下載這個數據集，在資源那一段有更多的說明。
如何用Python實現KNN
這個教程把實現步驟分為如下6布。
處理數據：從CSV中讀取數據，並把它們分割成訓練數據集和測試數據集。
相似度：計算兩個數據實例之間的距離。
臨近：確定最相近的N個實例。
結果：從這些實力中生成預測結果。
準確度：總結預測的準確度。
主程序：把這些串起來
1、處理數據
我們要做的第一件事是加載我們的數據文件。數據文件是CSV格式的，並且沒有標題行和備註。我們可以使用open方法打開文件，並用csv模塊讀取數據：
接下來我們要把數據集切分成用來做預測的訓練數據集和用來評估準確度的測試數據集。
首先，我們要把加載進來的特徵數據從字符串轉換成整數。然後我們隨機地切分訓練數據集和測試數據集。訓練數據集數據量/測試數據集數據量的比值取67/33是一個常用的慣例。
把這些邏輯放在一起，我們得到下面這個函數loadDataset：
把鳶尾花的CSV數據文件下載到本地文件夾，我們就可以測試一下我們的函數了，測試代碼如下：
2、相似度
為了作出預測，我們需要計算兩個數據實例之間的相似度。有了計算相似度的函數，我們後面才能獲取最相似的N個實例來做出預測。
因為有關花的四個測量維度的數據都是數字形式的，並且具有相同的單位。我們可以直接使用歐式距離來測量。歐式距離就是兩列數中對應數做差的平方和，之後再開方。（類似於二維平面的距離公式，擴展到多維）。
另外，我們要確定哪些維度參與計算。在這個問題裡，我們只需要包含測量好的4個維度，這4個維度放在數組的前幾個位置。限制維度的一個辦法就是增加一個參數，告訴函數前幾個維度需要處理，忽略後面的維度。
把這些邏輯放在一起，得到計算歐式距離的函數：
我們可以用一些假數據來測試這個函數，像這樣：
3、鄰近元素
現在我們有了相似度計算的方法，我們可以獲取跟需要預測數據最接近的N個數據實例了。
最直接的方法就是計算待預測數據到所有數據實例的距離，取其中距離最小的N個。
這個邏輯可以由下面函數表示：
我們可以像下面這樣測試這個函數
4、結果
接下來的任務就是基於最近的幾個實例來得到預測結果了。
我們可以讓這些近鄰元素來對預測屬性投票，得票最多的選項作為預測結果。
下面這個函數實現了投票的邏輯，它假設需預測的屬性放在數據實例（數組）的最後。
我們可以用一些測試數據測試一下：
如果投票結果是平局，這個函數還是返回了一個預測結果。不過你可以有你自己的處理方式，比如平局時返回None，或者平局時隨機選擇一個結果。
5、準確度
做預測的部分已經都寫完了，接下來是評估這個算法的準確度。
一個簡單的評估方法是，計算在測試數據集中算法正確預測的比例，這個比例叫分類準確度。
下面這個函數可以計算分類準確度。
我們可以用下面這個例子來測試它：
6、主程序
好了，我們已經有了這個算法需要的所有函數，剩的就是把它們串起來了。
下面是完整的代碼：
運行這個程序，你就會看到每個預測數據和實際數據的對比。在程序的最後，你能看到這個預測模型的準確度。在這個例子中，準確度略高於98%。
有關擴展的想法
這一部分我們講講一些對本教程給出的Python代碼的做擴展的想法。
回歸：你可以調整代碼，讓這個算法能夠處理一些回歸問題（預測一個實數屬性）。比如總結近鄰實例的時候，採用預測屬性的平均值或者中值。
歸一化：當不同屬性之間單位不同時，某些屬性在決定距離時可能會獲得很大的權重。對於這類問題，你可能需要在計算之前把各個屬性的值都縮放到0-1之間（這個過程叫歸一化）。你可以改進這個算法讓它支持數據歸一化。
可更換距離計算方法：其實有很多其他的距離計算方法，你甚至可以自己開發一個距離計算方法。實現一個替換的距離計算方法，比如曼哈頓距離，或者向量的點積。
你可以發掘更多擴展的邏輯。比如投票的時候不同距離的實例有不同的權重，或者你可以用一個樹形結構來進行最近實例的搜索。
英文原文：http://machinelearningmastery.com/tutorial-to-implement-k-nearest-neighbors-in-python-from-scratch/
譯者：詩書塞外
了解野狗，請點擊閱讀原文。