kNN(k-nearest neighbor)是一種基本的分類與回歸的算法。這里我們先只討論分類中的kNN算法。

k鄰近算法的輸入為實(shí)例的特征向量，對對應(yīng)于特征空間中的點(diǎn)；輸出為實(shí)例的類別，可以取多類，k近鄰法是建設(shè)給定一個訓(xùn)練數(shù)據(jù)集，其中的實(shí)例類別已定，分類時，對于新的實(shí)例，根據(jù)其k個最鄰近的訓(xùn)練實(shí)例的類別，通過多數(shù)表決等方式進(jìn)行預(yù)測。所以可以說，k近鄰法不具有顯示的學(xué)習(xí)過程。k臨近算法實(shí)際上是利用訓(xùn)練數(shù)據(jù)集對特征向量空間進(jìn)行劃分，并作為其分類的“模型”

k值的選擇，距離的度量和分類決策規(guī)則是k近鄰算法的三個基本要素。

這里需要說明的是，對于距離的度量，我們有很多種度量方法可以選擇，如歐氏距離（2-范數(shù)），曼哈頓距離（1-范數(shù)）,無窮范數(shù)等，根據(jù)不同的實(shí)例，我們可以選擇不同的距離度量方法。

下面給出了利用python和sklearn庫實(shí)現(xiàn)的kNN算法的過程及部分注釋：

# coding=utf-8  # 首先利用sklearn的庫進(jìn)行knn算法的建立與預(yù)測 # from sklearn import neighbors # from sklearn import datasets # # knn = neighbors.KNeighborsClassifier()   # 調(diào)用分類器賦在變量knn上 # # iris = datasets.load_iris()   # 返回一個數(shù)據(jù)庫，賦值在iris上 # # print iris   # 顯示這個數(shù)據(jù)集 # # knn.fit(iris.data, iris.target) # fit的第一個參數(shù) 是特征值矩陣，第二個參數(shù)是一維的向量 # # predictedLabel = knn.predict([[0.1,0.2,0.3,0.4]]) # # print predictedLabel  # 下面自己寫一個程序?qū)崿F(xiàn)knn算法  import csv import random import math import operator  # filename是指文件名,split是某一個數(shù)字，數(shù)字前的數(shù)據(jù)當(dāng)做訓(xùn)練集，數(shù)字后的數(shù)據(jù)當(dāng)做測試集 # trainingSet是訓(xùn)練集，testSet是測試集 # 函數(shù)作用，加載文件，并將文件通過隨機(jī)數(shù)的方法分為訓(xùn)練集和測試集 def loadDataset(filename, split, trainingSet=[], testSet=[]):   with open(filename, 'rb') as csvfile:  # 導(dǎo)入文件為csvfile格式     lines = csv.reader(csvfile)   # 讀取所有的行 reader函數(shù)的作用     dataset = list(lines)    # 將所有的行轉(zhuǎn)換為list的數(shù)據(jù)節(jié)后     for x in range(len(dataset)-1):   # x在總共的行數(shù)中遍歷       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])   # 函數(shù)作用：計算歐氏距離 # 函數(shù)的輸入是兩個實(shí)例和他們的維度 def euclideanDistance(instance1, instance2, length):   distance = 0   for x in range(length):   # 對于每一個維度內(nèi)進(jìn)行一個差的計算，計算出所有維度的平方和     distance += pow((instance1[x] - instance2[x]),2)   return math.sqrt(distance)  # 函數(shù)作用：返回最近的k的neightbor # 也就是返回在trainingSet中距離testInstance最近的k個鄰居 def getNeigthbors(trainingSet, testInstance, k):   distances =[] # 距離的容器，用來存放所有的距離值   length = len(testInstance) - 1 # 用來存放testInstance的維度   for x in range(len(trainingSet)):     # 對于每一個x 計算訓(xùn)練集中的數(shù)據(jù)與實(shí)例的距離     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]  # 用來檢驗(yàn)預(yù)測結(jié)果的正確率 def getAccuracy(testSet,predictions):   correct = 0   for x in range(len(testSet)):     if testSet[x][-1] == predictions[x]:    # [-1]值的是最后一個值，也就是每行的最后的值，即為花的分類       correct += 1   return (correct/float(len(testSet))) * 100.00   def main():   # prepare data   trainingSet = []   testSet = []   split = 0.67   loadDataset('irisdata.txt',split,trainingSet,testSet) # r的作用是防止錯誤字符串意思   print 'Train Set' + repr(len(trainingSet))   print 'Test Set' + repr(len(testSet))    # generate predicitions   predicitions = []   k = 3   for x in range(len(testSet)):     neighbors = getNeigthbors(trainingSet,testSet[x],k)     result = getResponse(neighbors)     predicitions.append(result)     print('> predicition = ' + repr(result) + ', actual = ' +repr(testSet[x][-1]))   accuracy = getAccuracy(testSet,predicitions)   print('Accuracy:' + repr(accuracy) + '%')  main()