教程：用Python從零開始實現K近鄰算法

rehrhh 7年前發布 | 17K 次閱讀算法 Python K近鄰 Python開發

K近鄰算法（或簡稱kNN）是易于理解和實現的算法，而且是你解決問題的強大工具。

在本教程中，你將基于Python（2.7）從零開始實現kNN算法。該實現主要針對分類問題，將會用鳶尾花分類問題來演示。

這篇教程主要針對Python程序員，或者你可以快速上手Python，并且對如何從零實現kNN算法感興趣。

什么是kNN

kNN算法的模型就是整個訓練數據集。當需要對一個未知數據實例進行預測時，kNN算法會在訓練數據集中搜尋k個最相似實例。對k個最相似實例的屬性進行歸納，將其作為對未知實例的預測。

相似性度量依賴于數據類型。對于實數，可以使用歐式距離來計算。其他類型的數據，如分類數據或二進制數據，可以用漢明距離。

對于回歸問題，會返回k個最相似實例屬性的平均值。對于分類問題，會返回k個最相似實例屬性出現最多的屬性。

kNN如何工作

kNN屬于基于實例算法簇的競爭學習和懶惰學習算法。

基于實例的算法運用數據實例（或數據行）對問題進行建模，進而做出預測決策。kNN算法算是基于實例方法的一種極端形式，因為其保留所有的訓練集數據作為模型的一部分。

kNN是一個競爭學習算法，因為為了做出決策，模型內部元素（數據實例）需要互相競爭。數據實例之間客觀相似度的計算，促使每個數據實例都希望在競爭中“獲勝”或者盡可能地與給定的未知數據實例相似，繼而在預測中做出貢獻。

懶惰學習是指直到需要預測時算法才建立模型。它很懶，因為它只在最后一刻才開始工作。優點是只包含了與未知數據相關的數據，稱之為局部模型。缺點是，在大型訓練數據集中會重復相同或相似的搜索過程，帶來昂貴的計算開銷。

最后，kNN的強大之處在于它對數據不進行任何假設，除了任意兩個數據實例之間距離的一致計算。因此，它被稱為成為無參數或者非線性的，因為它沒有預設的函數模型。

使用測量值對鳶尾花分類

本教程中我們演示的是鳶尾花分類問題。

原始數據集由來自3個品種鳶尾花的150個觀察結果組成。對每一朵花有四個測量值：萼片長度、萼片寬度、花瓣長度、花瓣寬度，單位都是厘米。待預測鳶尾花屬于Setosa，Versicolour，Virginica三個種類之一。

這是一個標準的數據集，所有示例的種類都是已知的。因此我們可以將數據集分割成訓練數據集和測試數據集，并使用預測結果來評估實現的算法。這個問題，比較好的分類算法的準確度在90%以上，通常為96%甚至更好。

你可以從iris.data上免費下載數據集，更多細節見參考資料部分。

怎樣用Python實現k-Nearest Neighbors

本教程將KNN算法分為如下幾步：

數據處理：打開CSV文件獲取數據，將原始數據分為測試集/訓練集。

相似性度量：計算每兩個數據實例之間的距離。

近鄰查找：找到k個與當前數據最近的鄰居。

結果反饋：從近鄰實例反饋結果。

精度評估：統計預測精度。

主函數：將上述過程串起來。

1. 數據處理

我們首先要做的是把文件中的數據加載進來。這些數據以CSV形式存放在文件中，不包含header行和其它任何引用。我們可以使用open函數打開這些文件，然后使用csv module中的reader函數去讀取文件。

import csv
with open('iris.data', 'rb') as csvfile:
    lines = csv.reader(csvfile)
    for rowin lines:
        print ', '.join(row)

接下來，我們需要將這些數據拆分為kNN用于做預測的訓練集(training dataset)和用來評估模型精度的測試集(test dataset)。

首先，我們需要將以字符串形式載入的鳶尾花測量數據轉換為容易處理的數組。接下來，我們需要將數據集隨機的分為訓練集與測試集。通常訓練集/測試集的劃分比例標準為67/33。

將上述步驟合在一起，我們可以定義一個叫loadDataset的函數，該函數可以加載指定的CSV文件，并按照指定的比例隨機分為訓練集與測試集。

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])

將鳶尾花數據集的csv文件下載到本地目錄，我們可以用鳶尾花數據集按照如下方式測試這個函數：

trainingSet=[]
testSet=[]
loadDataset('iris.data', 0.66, trainingSet, testSet)
print 'Train: ' + repr(len(trainingSet))
print 'Test: ' + repr(len(testSet))

2.相似性度量

為了進行預測我們需要計算任意兩個數據實例的相似性。這是必要的，因為對于給定的每一個測試集中的數據實例，我們都可以在訓練集中找出k個相似性最高的數據實例，這樣就可以依次進行預測。

假定鳶尾花的4個測量數據都為數值形式且單位相同，我們可以直接采用歐氏距離(Euclidean distance)進行相似性度量。歐式距離定義為：兩組向量對應元素之差的平方和再做平方根運算。

另外，我們要控制哪個字段參與歐式距離的計算。具體來講，我們只想包括前四個屬性。一種方法是采用固定長度的向量來限制歐式距離，忽略最后的維度。

將上述步驟合在一起，我們可以將euclideanDistance函數定義為：

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)

我們可以用一些樣本數據來測試這個函數，具體如下：

data1 = [2, 2, 2, 'a']
data2 = [4, 4, 4, 'b']
distance = euclideanDistance(data1, data2, 3)
print 'Distance: ' + repr(distance)

3. 近鄰查找

由于我們有相似性度量的方法，因此可以采用該方法尋找未知數據實例的k個相似性最高的實例。

處理過程直接計算所有樣本點到給定點的歐式距離，進而篩選距離最近的樣本點子集。

下面是getNeighbors函數，該函數遍歷訓練集并返回與測試實例距離最近的k個近鄰樣本點（采用已經定義好的euclideanDistance函數）。

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

我們可以按如下方法來測試這個函數：

trainSet = [[2, 2, 2, 'a'], [4, 4, 4, 'b']]
testInstance = [5, 5, 5]
k = 1
neighbors = getNeighbors(trainSet, testInstance, 1)
print(neighbors)

4. 結果反饋

我們已經找到了測試實例的最近的鄰居，下一步就是基于這些近鄰做出預測結果。

我們可以讓每個鄰居對測試實例的類別屬性進行投票，最終以票數多者做為預測結果。

下面的函數提供了從近鄰投票中反饋多數投票結果的機制。該函數假定每個鄰居的最后一列為類別屬性。

import operator
def getResponse(neighbors):
    classVotes = {}
    for x in range(len(neighbors)):
        response = neighbors[x][-1]
        if responsein classVotes:
            classVotes[response] += 1
        else:
            classVotes[response] = 1
    sortedVotes = sorted(classVotes.iteritems(), key=operator.itemgetter(1), reverse=True)
    return sortedVotes[0][0]

我們可以輸入近鄰數據測試該函數，結果如下：

neighbors = [[1,1,1,'a'], [2,2,2,'a'], [3,3,3,'b']]
response = getResponse(neighbors)
print(response)

該方法在平局的情況下依然會有一個返回結果，但是我們可以對其特殊處理，例如返回空值或者選擇一個無偏隨機結果

5. 精度評估

我們已經具備了所有的kNN算法片段。還有一件事情仍需我們重點關注，那就是就是如何評估預測精度。

評估模型精度最簡單的方法就是計算正確預測結果數量占全部預測結果數量的比例，稱為分類精度。

下面是getAccuracy函數，該函數統計所有的正確預測并返回正確分類的百分比精度。

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

我們可以采用測試集與預測結果來測試該函數，結果如下：

testSet = [[1,1,1,'a'], [2,2,2,'a'], [3,3,3,'b']]
predictions = ['a', 'a', 'a']
accuracy = getAccuracy(testSet, predictions)
print(accuracy)

6. 主函數

目前為止，我們已經具備了所有的算法組成元素，下面我們將這些元素串起來，組成主函數。

下面是從零開始實現的kNN算法完整Python代碼。

# 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 responsein 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 = get
        Neighbors(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%。

...
> 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%

思路擴展

本節向讀者提供了一些思路擴展，以便大家在本教程實現代碼的基礎上進一步應用和探索。

回歸問題：你可以將本實現應用到一些回歸問題（預測基于數值的屬性）。對近鄰實例的匯總可能涉及要預測屬性的平均數或者中位數
歸一化：當屬性之間的度量單位不同時，很容易造成某些屬性在距離度量層面成為主導因素。對于這類問題，你應該在相似性度量前將屬性值都放縮到0-1范圍內（稱為歸一化）。將模型升級以支持數據歸一化。
多種距離度量：通常有許多距離度量方法可供選用，如果你愿意，甚至可以創造出針對特定領域的距離度量方法。實現替代的距離度量方法，例如曼哈頓距離(Manhattan distance)或向量點積(vector dot product)。

該算法還有很多擴展形式可以探索。這里給出兩個擴展思路，包括基于距離權重的k-most相似性實例去預測以及更進一步的基于樹形結構查找相似度去查找。

總結

在本教程中，你了解了k近鄰算法的工作原理，其中一些隱喻可以用來思考本算法，并延伸到其他算法。我們用python從零開始實現了kNN算法，你理解了每一行代碼，因此你可以基于本實現去探索擴展，滿足你自己的項目需求。

以下是本教程涉及的5類學習算法：

K近鄰算法 ：理解和實現起來較簡單的算法，非常強大的非參數算法
基于實例的算法 ：使用數據集（觀察值）對問題建模
競爭算法 ：通過模型元素之間的內部競爭來做出預測決策
懶惰學習 ：需要做出預測時才開始建立模型
相似性計算 ：計算數據實例之間的客觀距離是該算法的一個關鍵特征

你用本教程實現kNN算法了嗎？你是怎么做的？你學到了什么？

來自：http://python.jobbole.com/87407/

本文由用戶 rehrhh 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。

轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。

本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！

本文地址：http://www.baiduhome.net/lib/view/open1488527008410.html

算法 Python K近鄰 Python開發