# 教程從頭開始在Python中實現k-Nearest Neighbors > 原文： [https://machinelearningmastery.com/tutorial-to-implement-k-nearest-neighbors-in-python-from-scratch/](https://machinelearningmastery.com/tutorial-to-implement-k-nearest-neighbors-in-python-from-scratch/) k-Nearest Neighbors算法（或簡稱kNN）是一種易于理解和實現的算法，是您可以隨意使用的強大工具。 在本教程中，您將從頭開始在Python（2.7）中實現k-Nearest Neighbors算法。實施將特定于分類問題，并將使用虹膜花分類問題進行演示。 本教程適合您，如果您是Python程序員，或者可以快速獲取python的程序員，并且您對如何從頭開始實現k-Nearest Neighbors算法感興趣。 [](https://3qeqpr26caki16dnhd19sv6by6v-wpengine.netdna-ssl.com/wp-content/uploads/2014/09/k-Nearest-Neighbors-algorithm.png) k-Nearest Neighbors algorithm 圖片來自 [Wikipedia](http://en.wikipedia.org/wiki/File:Map1NN.png) ，保留所有權利 ## 什么是k-Nearest Neighbors kNN的模型是整個訓練數據集。當對于看不見的數據實例需要預測時，kNN算法將在訓練數據集中搜索k個最相似的實例。總結了最相似實例的預測屬性，并將其作為未見實例的預測返回。 相似性度量取決于數據類型。對于實值數據，可以使用歐幾里德距離。可以使用其他類型的數據，例如分類或二進制數據，漢明距離。 在回歸問題的情況下，可以返回預測屬性的平均值。在分類的情況下，可以返回最普遍的類別。 ## k-Nearest Neighbors是如何工作的 kNN算法屬于基于實例的競爭學習和懶惰學習算法的家族。 基于實例的算法是使用數據實例（或行）對問題建模以便做出預測決策的算法。 kNN算法是基于實例的方法的一種極端形式，因為所有訓練觀察都被保留作為模型的一部分。 它是一種競爭性學習算法，因為它在內部使用模型元素（數據實例）之間的競爭來做出預測決策。數據實例之間的客觀相似性度量使得每個數據實例競爭“贏”或與給定的未見數據實例最相似并且有助于預測。 延遲學習是指算法在需要預測之前不構建模型的事實。這是懶惰的，因為它只在最后一秒工作。這樣做的好處是只包括與看不見的數據相關的數據，稱為本地化模型。缺點是在較大的訓練數據集上重復相同或類似的搜索可能在計算上是昂貴的。 最后，kNN非常強大，因為它不會假設任何有關數據的內容，除了可以在任何兩個實例之間一致地計算距離度量。因此，它被稱為非參數或非線性，因為它不假設功能形式。 ## 獲取免費算法思維導圖  方便的機器學習算法思維導圖的樣本。 我已經創建了一個由類型組織的60多種算法的方便思維導圖。 下載，打印并使用它。 ## 使用測量對花進行分類 我們將在本教程中使用的測試問題是虹膜分類。 該問題包括150個來自三個不同物種的鳶尾花的觀察結果。給定花有4種尺寸：萼片長度，萼片寬度，花瓣長度和花瓣寬度，均以厘米為單位。預測的屬性是物種，它是setosa，versicolor或virginica之一。 它是一個標準數據集，其中物種對于所有實例都是已知的。因此，我們可以將數據拆分為訓練和測試數據集，并使用結果來評估我們的算法實現。該問題的良好分類準確度高于90％正確，通常為96％或更高。 * [下載鳶尾花數據集](https://archive.ics.uci.edu/ml/machine-learning-databases/iris/iris.data) 使用文件名“ _iris.data_ ”將文件保存在當前工作目錄中。 ## 如何在Python中實現k-Nearest Neighbors 本教程分為以下幾個步驟： 1. **句柄**數據：從CSV打開數據集并拆分為測試/訓練數據集。 2. **相似度**：計算兩個數據實例之間的距離。 3. **鄰居**：找到k個最相似的數據實例。 4. **響應**：從一組數據實例生成響應。 5. **準確度**：總結預測的準確性。 6. **主**：將它們捆綁在一起。 ### 1.處理數據 我們需要做的第一件事是加載我們的數據文件。數據為CSV格式，沒有標題行或任何引號。我們可以使用open函數打開文件，并使用 [csv](https://docs.python.org/2/library/csv.html) 模塊中的reader函數讀取數據行。 Read a CSV File in Python Python ```py import csv with open('iris.data', 'rb') as csvfile: lines = csv.reader(csvfile) for row in lines: print ', '.join(row) ``` 接下來，我們需要將數據拆分為kNN可用于進行預測的訓練數據集和我們可用于評估模型準確性的測試數據集。 我們首先需要將作為字符串加載的花卉度量轉換為我們可以使用的數字。接下來，我們需要將數據集隨機分成訓練和數據集。訓練/測試的比率為67/33是使用的標準比率。 將它們全部拉到一起，我們可以定義一個名為 **loadDataset** 的函數，該函數使用提供的文件名加載CSV，并使用提供的分割比率將其隨機分成訓練和測試數據集。 Load a dataset and spit into train and test sets in Python Python ```py import csv import random def loadDataset(filename, split, trainingSet=[] , testSet=[]): with open(filename, 'rb') as csvfile: lines = csv.reader(csvfile) dataset = list(lines) for x in range(len(dataset)-1): for y in range(4): dataset[x][y] = float(dataset[x][y]) if random.random() < split: trainingSet.append(dataset[x]) else: testSet.append(dataset[x]) ``` 將iris flowers數據集CSV文件下載到本地目錄。我們可以使用我們的iris數據集測試此函數，如下所示： Test the loadDataset function in Python Python ```py trainingSet=[] testSet=[] loadDataset('iris.data', 0.66, trainingSet, testSet) print 'Train: ' + repr(len(trainingSet)) print 'Test: ' + repr(len(testSet)) ``` ### 2.相似性 為了進行預測，我們需要計算任何兩個給定數據實例之間的相似性。這是必需的，以便我們可以在訓練數據集中為測試數據集的給定成員定位k個最相似的數據實例，然后進行預測。 鑒于所有四個花測量都是數字并具有相同的單位，我們可以直接使用歐幾里德距離測量。這被定義為兩個數字數組之間的平方差之和的平方根（再讀幾次并讓它沉入其中）。 另外，我們想要控制在距離計算中包括哪些字段。具體來說，我們只想包含前4個屬性。一種方法是將歐氏距離限制為固定長度，忽略最終尺寸。 將所有這些放在一起我們可以定義 **euclideanDistance** 函數如下： Calculate Euclidean distance in Python Python ```py import math def euclideanDistance(instance1, instance2, length): distance = 0 for x in range(length): distance += pow((instance1[x] - instance2[x]), 2) return math.sqrt(distance) ``` 我們可以使用一些示例數據測試此函數，如下所示： Test the euclideanDistance function in Python Python ```py data1 = [2, 2, 2, 'a'] data2 = [4, 4, 4, 'b'] distance = euclideanDistance(data1, data2, 3) print 'Distance: ' + repr(distance) ``` ### 3.鄰居 現在我們有一個相似性度量，我們可以使用它為給定的看不見的實例收集k個最相似的實例。 這是計算所有實例的距離并選擇具有最小距離值的子集的直接過程。 下面是 **getNeighbors** 函數，該函數從給定測試實例的訓練集中返回k個最相似的鄰居（使用已定義的 **euclideanDistance** 函數） Locate most similar neighbours in Python Python ```py import operator def getNeighbors(trainingSet, testInstance, k): distances = [] length = len(testInstance)-1 for x in range(len(trainingSet)): dist = euclideanDistance(testInstance, trainingSet[x], length) distances.append((trainingSet[x], dist)) distances.sort(key=operator.itemgetter(1)) neighbors = [] for x in range(k): neighbors.append(distances[x][0]) return neighbors ``` 我們可以測試這個函數如下： Test the getNeighbors function in Python Python ```py trainSet = [[2, 2, 2, 'a'], [4, 4, 4, 'b']] testInstance = [5, 5, 5] k = 1 neighbors = getNeighbors(trainSet, testInstance, 1) print(neighbors) ``` ### 4.回應 一旦我們為測試實例找到了最相似的鄰居，下一個任務就是根據這些鄰居設計預測響應。 我們可以通過允許每個鄰居投票選擇他們的類屬性來做到這一點，并將多數投票作為預測。 下面提供了從多個鄰居獲得多數投票回復的功能。它假定該類是每個鄰居的最后一個屬性。 Summarize a prediction from neighbours in Python Python ```py import operator def getResponse(neighbors): classVotes = {} for x in range(len(neighbors)): response = neighbors[x][-1] if response in classVotes: classVotes[response] += 1 else: classVotes[response] = 1 sortedVotes = sorted(classVotes.iteritems(), key=operator.itemgetter(1), reverse=True) return sortedVotes[0][0] ``` 我們可以用一些測試鄰居測試這個函數，如下所示： Test the getResponse function in Python Python ```py neighbors = [[1,1,1,'a'], [2,2,2,'a'], [3,3,3,'b']] response = getResponse(neighbors) print(response) ``` 在繪制的情況下，此方法返回一個響應，但您可以以特定方式處理此類情況，例如不返回響應或選擇無偏的隨機響應。 ### 5.準確性 我們已經完成了kNN算法的所有部分。一個重要的問題是如何評估預測的準確性。 評估模型準確性的一種簡單方法是計算所有預測中的總正確預測的比率，稱為分類準確度。 下面是 **getAccuracy** 函數，該函數對總正確預測進行求和，并以正確分類的百分比形式返回準確度。 Calculate accuracy of predictions in Python Python ```py def getAccuracy(testSet, predictions): correct = 0 for x in range(len(testSet)): if testSet[x][-1] is predictions[x]: correct += 1 return (correct/float(len(testSet))) * 100.0 ``` 我們可以使用測試數據集和預測來測試此函數，如下所示： Test the getAccuracy function in Python Python ```py testSet = [[1,1,1,'a'], [2,2,2,'a'], [3,3,3,'b']] predictions = ['a', 'a', 'a'] accuracy = getAccuracy(testSet, predictions) print(accuracy) ``` ### 6.主要 我們現在擁有算法的所有元素，我們可以將它們與主函數綁定在一起。 下面是在Python中從頭開始實現kNN算法的完整示例。 Example of kNN implemented from Scratch in Python Python ```py # Example of kNN implemented from Scratch in Python import csv import random import math import operator def loadDataset(filename, split, trainingSet=[] , testSet=[]): with open(filename, 'rb') as csvfile: lines = csv.reader(csvfile) dataset = list(lines) for x in range(len(dataset)-1): for y in range(4): dataset[x][y] = float(dataset[x][y]) if random.random() < split: trainingSet.append(dataset[x]) else: testSet.append(dataset[x]) def euclideanDistance(instance1, instance2, length): distance = 0 for x in range(length): distance += pow((instance1[x] - instance2[x]), 2) return math.sqrt(distance) def getNeighbors(trainingSet, testInstance, k): distances = [] length = len(testInstance)-1 for x in range(len(trainingSet)): dist = euclideanDistance(testInstance, trainingSet[x], length) distances.append((trainingSet[x], dist)) distances.sort(key=operator.itemgetter(1)) neighbors = [] for x in range(k): neighbors.append(distances[x][0]) return neighbors def getResponse(neighbors): classVotes = {} for x in range(len(neighbors)): response = neighbors[x][-1] if response in classVotes: classVotes[response] += 1 else: classVotes[response] = 1 sortedVotes = sorted(classVotes.iteritems(), key=operator.itemgetter(1), reverse=True) return sortedVotes[0][0] def getAccuracy(testSet, predictions): correct = 0 for x in range(len(testSet)): if testSet[x][-1] == predictions[x]: correct += 1 return (correct/float(len(testSet))) * 100.0 def main(): # prepare data trainingSet=[] testSet=[] split = 0.67 loadDataset('iris.data', split, trainingSet, testSet) print 'Train set: ' + repr(len(trainingSet)) print 'Test set: ' + repr(len(testSet)) # generate predictions predictions=[] k = 3 for x in range(len(testSet)): neighbors = getNeighbors(trainingSet, testSet[x], k) result = getResponse(neighbors) predictions.append(result) print('> predicted=' + repr(result) + ', actual=' + repr(testSet[x][-1])) accuracy = getAccuracy(testSet, predictions) print('Accuracy: ' + repr(accuracy) + '%') main() ``` 運行該示例，您將看到每個預測的結果與測試集中的實際類值進行比較。在運行結束時，您將看到模型的準確性。在這種情況下，略高于98％。 Example output ```py ... > predicted='Iris-virginica', actual='Iris-virginica' > predicted='Iris-virginica', actual='Iris-virginica' > predicted='Iris-virginica', actual='Iris-virginica' > predicted='Iris-virginica', actual='Iris-virginica' > predicted='Iris-virginica', actual='Iris-virginica' Accuracy: 98.0392156862745% ``` ## 擴展的想法 本節為您提供了可以應用的擴展的概念，并使用您在本教程中實現的Python代碼進行調查。 * **回歸**：您可以調整實現以適應回歸問題（預測實值屬性）。最接近的實例的摘要可涉及取預測屬性的均值或中值。 * **標準化**：當屬性之間的度量單位不同時，屬性可能在它們對距離度量的貢獻中占主導地位。對于這些類型的問題，您需要在計算相似度之前將所有數據屬性重新縮放到0-1范圍內（稱為規范化）。更新模型以支持數據規范化。 * **替代距離測量**：有許多可用的距離測量，如果您愿意，您甚至可以開發自己的特定于域的距離測量。實施替代距離測量，例如曼哈頓距離或向量點積。 您可能希望探索此算法的更多擴展。另外兩個想法包括支持對預測的k-最相似實例的距離加權貢獻以及用于搜索類似實例的更高級的基于數據樹的結構。 ## 資源了解更多 本節將提供一些資源，您可以使用這些資源來了解k-Nearest Neighbors算法的更多信息，包括它的工作原理和原理以及在代碼中實現它的實際問題。 ### 問題 * [維基百科上的鳶尾花數據集](http://en.wikipedia.org/wiki/Iris_flower_data_set) * [UCI機器學習庫Iris數據集](https://archive.ics.uci.edu/ml/datasets/Iris) ### 碼 本節鏈接到流行的機器學習庫中的kNN的開源實現。如果您正在考慮實施自己的方法版本以供操作使用，請查看這些內容。 * [在scikit-learn中實現kNN](https://github.com/scikit-learn/scikit-learn/tree/master/sklearn/neighbors) * [在Weka中實施kNN](https://github.com/baron/weka/blob/master/weka/src/main/java/weka/classifiers/lazy/IBk.java) （非正式） ### 圖書 您可能有一本或多本關于應用機器學習的書籍。本節重點介紹有關機器學習的常見應用書籍中涉及k-Nearest Neighbors的章節或章節。 * [Applied Predictive Modeling](http://www.amazon.com/dp/1461468485?tag=inspiredalgor-20) ，第159和350頁。 * [數據挖掘：實用機器學習工具和技術，第三版（數據管理系統中的Morgan Kaufmann系列）](http://www.amazon.com/dp/0123748569?tag=inspiredalgor-20)，第76,128和235頁。 * [黑客機器學習](http://www.amazon.com/dp/1449303714?tag=inspiredalgor-20)，第10章。 * [機器學習在行動](http://www.amazon.com/dp/1617290181?tag=inspiredalgor-20)，第2章。 * [編程集體智慧：構建智能Web 2.0應用程序](http://www.amazon.com/dp/0596529325?tag=inspiredalgor-20)，第2章和第8章以及第293頁。 ## 教程摘要 在本教程中，您了解了k-Nearest Neighbor算法，它的工作原理以及可用于思考算法并將其與其他算法相關聯的一些隱喻。您從頭開始在Python中實現kNN算法，以便您了解每行代碼并調整實現以探索擴展并滿足您自己的項目需求。 以下是本教程的5個主要學習內容： * **k-最近鄰**：一種理解和實現的簡單算法，以及強大的非參數方法。 * **基于實例的方法**：使用數據實例（觀察）對問題建模。 * **競爭學習**：學習和預測決策是由模型元素之間的內部競爭決定的。 * **懶惰學習**：為了進行預測，只有在需要時才構建模型。 * **相似性度量**：計算數據實例之間的客觀距離度量是算法的關鍵特征。 您是否使用本教程實現了kNN？你是怎么去的？你學到了什么？