用Python來實現K近鄰分類算法（KNN）已經是一個老生常談的問題，網上也已經有諸多資料，不過這里我還是決定記錄一下自己的學習心得。

1、配置numpy庫

numpy庫是Python用于矩陣運算的第三方庫，大多數數學運算都會依賴這個庫來進行，關于numpy庫的配置參見：Python配置第三方庫Numpy和matplotlib的曲折之路，配置完成后將numpy庫整體導入到當前工程中。

2、準備訓練樣本

這里簡單的構造四個點并配以對應標簽作為KNN的訓練樣本：

# ====================創建訓練樣本====================
def createdataset():
    group = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
    labels = ['A', 'B', 'C', 'D']
    return group, labels

這里有一個小細節，就是通過array（）函數老構造并初始化numpy的矩陣對象時，要保證只有一個參數，因此在代碼中需要將參數用中括號括起來，像下面這種調用方式是不合法的：

group = array([1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1])

3、創建分類函數

K近鄰算法在分類時一般是根據歐氏距離進行分類的，因此需要將輸入的數據與訓練數據在各個維度上相減再平方求和，再開方，如下：

# ====================歐氏距離分類====================
def classify(Inx, Dataset, labels, k):
    DataSetSize = Dataset.shape[0]  # 獲取數據的行數，shape[1]位列數
    diffmat = tile(Inx, (DataSetSize, 1)) - Dataset
    SqDiffMat = diffmat**2
    SqDistances = SqDiffMat.sum(axis=1)
    Distance = SqDistances**0.5
    SortedDistanceIndicies = Distance.argsort()
    ClassCount = {}

這里tile（）函數是numpy的矩陣擴展函數，比如說這個例子中訓練樣本有四個二維坐標點，對于輸入樣本（一個二維坐標點），需要將其先擴展為一個4行1列的矩陣，然后在進行矩陣減法，在平法求和，再開平方算距離。計算完距離之后，調用矩陣對象的排序成員函數argsort（）對距離進行升序排序。在這里介紹一個Pycharm查看源碼生命的小技巧：加入在編寫這段程序的時候我們并不確定argsort（）是否為array對象的成員函數，我們選中這個函數然后 右鍵 -> Go to -> Declaration，這樣就會跳轉到argsort（）函數的聲明代碼片中，通過查看代碼的從屬關系能夠確認array類中確實包含這個成員函數，調用沒有問題：

對距離排序之后，接下來就根據前K個最小距離值所對應的標簽來判斷當前樣本屬于哪一類：

    for i in range(k):
        VoteiLabel = labels[SortedDistanceIndicies[i]]
        ClassCount[VoteiLabel] = ClassCount.get(VoteiLabel, 0) + 1
    SortedClassCount = sorted(ClassCount.items(), key = operator.itemgetter(1), reverse = True)

這里有一個小問題就是在Python2中獲取字典元素使用的是dict.iteritems（）成員函數，而在Python3中改為 dict.items（）函數。“key = operator.itemgetter(1)”的意思是指定函數針對字典中第二維元素進行排序，注意這里需要在之前導入符號庫operator。這里是通過記錄前K個距離最下值中每類標簽出現的次數來判決測試樣本的歸屬。

4、測試

這里給出完整的KNN測試代碼：

# coding: utf-8
from numpy import *
import operator

====================創建訓練樣本====================
def createdataset():
    group = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
    labels = ['A', 'B', 'C', 'D']
    return group, labels
====================歐氏距離分類====================
def classify(Inx, Dataset, labels, k):
    DataSetSize = Dataset.shape[0]  # 獲取數據的行數，shape[1]位列數
    diffmat = tile(Inx, (DataSetSize, 1)) - Dataset
    SqDiffMat = diffmat2
    SqDistances = SqDiffMat.sum(axis=1)
    Distance = SqDistances0.5
    SortedDistanceIndicies = Distance.argsort()
    ClassCount = {}
    for i in range(k):
        VoteiLabel = labels[SortedDistanceIndicies[i]]
        ClassCount[VoteiLabel] = ClassCount.get(VoteiLabel, 0) + 1
    SortedClassCount = sorted(ClassCount.items(), key = operator.itemgetter(1), reverse = True)
    return SortedClassCount[0][0]
Groups, Labels = createdataset()
Result = classify([0, 0], Groups, Labels, 1)
print(Result)</pre>運行代碼，程序答應結果“C”。這里需要提一點的就是對于單訓練樣本（每類只有一個訓練樣本）的分類問題，KNN的K值應該設定為1。





來自：http://www.cnblogs.com/fengliucaizi/p/5021775.html