kNN算法如何在Python中實現

本篇文章給大家分享的是有關kNN算法如何在Python中實現，小編覺得挺實用的，因此分享給大家學習，希望大家閱讀完這篇文章后可以有所收獲，話不多說，跟著小編一起來看看吧。

鄰近算法（k-NearestNeighbor) 是機器學習中的一種分類（classification）算法，也是機器學習中最簡單的算法之一了。雖然很簡單，但在解決特定問題時卻能發揮很好的效果。因此，學習kNN算法是機器學習入門的一個很好的途徑。

kNN算法的思想非常的樸素，它選取k個離測試點最近的樣本點，輸出在這k個樣本點中數量最多的標簽（label）。我們假設每一個樣本有m個特征值（property），則一個樣本的可以用一個m維向量表示: X =（ x1，x2，... , xm ),  同樣地，測試點的特征值也可表示成：Y =（ y1，y2，... , ym )。那我們怎么定義這兩者之間的“距離”呢？

在二維空間中，有：d2 = ( x1 - y1 )2 + ( x2 - y2 )2 ,  在三維空間中，兩點的距離被定義為：d2 = ( x1 - y1 )2 + ( x2 - y2 )2  + ( x3 - y3 )2 。我們可以據此推廣到m維空間中，定義m維空間的距離：d2 = ( x1 - y1 )2 + ( x2 - y2 )2  + ...... + ( xm - ym )2 。要實現kNN算法，我們只需要計算出每一個樣本點與測試點的距離，選取距離最近的k個樣本，獲取他們的標簽（label) ，然后找出k個樣本中數量最多的標簽，返回該標簽。

在開始實現算法之前，我們要考慮一個問題，不同特征的特征值范圍可能有很大的差別，例如，我們要分辨一個人的性別，一個女生的身高是1.70m，體重是60kg，一個男生的身高是1.80m，體重是70kg，而一個未知性別的人的身高是1.81m, 體重是64kg，這個人與女生數據點的“距離”的平方 d2 = ( 1.70 - 1.81 )2 + ( 60 - 64 )2 = 0.0121 + 16.0 = 16.0121，而與男生數據點的“距離”的平方d2 = ( 1.80 - 1.81 )2 + ( 70 - 64 )2 = 0.0001 + 36.0 = 36.0001 。可見，在這種情況下，身高差的平方相對于體重差的平方基本可以忽略不計，但是身高對于辨別性別來說是十分重要的。為了解決這個問題，就需要將數據標準化（normalize），把每一個特征值除以該特征的范圍，保證標準化后每一個特征值都在0~1之間。我們寫一個normData函數來執行標準化數據集的工作：

def normData(dataSet):
  maxVals = dataSet.max(axis=0)
  minVals = dataSet.min(axis=0)
  ranges = maxVals - minVals
  retData = (dataSet - minVals) / ranges
  return retData, ranges, minVals

 然后開始實現kNN算法：

 def kNN(dataSet, labels, testData, k):
  distSquareMat = (dataSet - testData) ** 2 # 計算差值的平方
  distSquareSums = distSquareMat.sum(axis=1) # 求每一行的差值平方和
  distances = distSquareSums ** 0.5 # 開根號，得出每個樣本到測試點的距離
  sortedIndices = distances.argsort() # 排序，得到排序后的下標
  indices = sortedIndices[:k] # 取最小的k個
  labelCount = {} # 存儲每個label的出現次數
  for i in indices:
    label = labels[i]
    labelCount[label] = labelCount.get(label, 0) + 1 # 次數加一
  sortedCount = sorted(labelCount.items(), key=opt.itemgetter(1), reverse=True) 
  # 對label出現的次數從大到小進行排序
  return sortedCount[0][0] # 返回出現次數最大的label

注意，在testData作為參數傳入kNN函數之前，需要經過標準化。

我們用幾個小數據驗證一下kNN函數是否能正常工作：

if __name__ == "__main__":
  dataSet = np.array([[2, 3], [6, 8]])
  normDataSet, ranges, minVals = normData(dataSet)
  labels = ['a', 'b']
  testData = np.array([3.9, 5.5])
  normTestData = (testData - minVals) / ranges
  result = kNN(normDataSet, labels, normTestData, 1)
  print(result)

結果輸出 a ，與預期結果一致。

完整代碼：

import numpy as np
from math import sqrt
import operator as opt

def normData(dataSet):
  maxVals = dataSet.max(axis=0)
  minVals = dataSet.min(axis=0)
  ranges = maxVals - minVals
  retData = (dataSet - minVals) / ranges
  return retData, ranges, minVals


def kNN(dataSet, labels, testData, k):
  distSquareMat = (dataSet - testData) ** 2 # 計算差值的平方
  distSquareSums = distSquareMat.sum(axis=1) # 求每一行的差值平方和
  distances = distSquareSums ** 0.5 # 開根號，得出每個樣本到測試點的距離
  sortedIndices = distances.argsort() # 排序，得到排序后的下標
  indices = sortedIndices[:k] # 取最小的k個
  labelCount = {} # 存儲每個label的出現次數
  for i in indices:
    label = labels[i]
    labelCount[label] = labelCount.get(label, 0) + 1 # 次數加一
  sortedCount = sorted(labelCount.items(), key=opt.itemgetter(1), reverse=True) # 對label出現的次數從大到小進行排序
  return sortedCount[0][0] # 返回出現次數最大的label



if __name__ == "__main__":
  dataSet = np.array([[2, 3], [6, 8]])
  normDataSet, ranges, minVals = normData(dataSet)
  labels = ['a', 'b']
  testData = np.array([3.9, 5.5])
  normTestData = (testData - minVals) / ranges
  result = kNN(normDataSet, labels, normTestData, 1)
  print(result)

以上就是kNN算法如何在Python中實現，小編相信有部分知識點可能是我們日常工作會見到或用到的。希望你能通過這篇文章學到更多知識。更多詳情敬請關注億速云行業資訊頻道。