快捷導(dǎo)航

利用Python實(shí)現(xiàn)kNN算法的代碼

更新時(shí)間：2019年08月16日 15:09:49 作者：魔法少女小Q

這篇文章主要介紹了利用Python實(shí)現(xiàn)kNN算法的代碼，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧

鄰近算法（k-NearestNeighbor) 是機(jī)器學(xué)習(xí)中的一種分類(lèi)（classification）算法，也是機(jī)器學(xué)習(xí)中最簡(jiǎn)單的算法之一了。雖然很簡(jiǎn)單，但在解決特定問(wèn)題時(shí)卻能發(fā)揮很好的效果。因此，學(xué)習(xí)kNN算法是機(jī)器學(xué)習(xí)入門(mén)的一個(gè)很好的途徑。

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

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

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

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

然后開(kāi)始實(shí)現(xiàn)kNN算法：

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

注意，在testData作為參數(shù)傳入kNN函數(shù)之前，需要經(jīng)過(guò)標(biāo)準(zhǔn)化。

我們用幾個(gè)小數(shù)據(jù)驗(yàn)證一下kNN函數(shù)是否能正常工作：

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)

結(jié)果輸出 a ，與預(yù)期結(jié)果一致。

完整代碼：

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 # 計(jì)算差值的平方
  distSquareSums = distSquareMat.sum(axis=1) # 求每一行的差值平方和
  distances = distSquareSums ** 0.5 # 開(kāi)根號(hào)，得出每個(gè)樣本到測(cè)試點(diǎn)的距離
  sortedIndices = distances.argsort() # 排序，得到排序后的下標(biāo)
  indices = sortedIndices[:k] # 取最小的k個(gè)
  labelCount = {} # 存儲(chǔ)每個(gè)label的出現(xiàn)次數(shù)
  for i in indices:
    label = labels[i]
    labelCount[label] = labelCount.get(label, 0) + 1 # 次數(shù)加一
  sortedCount = sorted(labelCount.items(), key=opt.itemgetter(1), reverse=True) # 對(duì)label出現(xiàn)的次數(shù)從大到小進(jìn)行排序
  return sortedCount[0][0] # 返回出現(xiàn)次數(shù)最大的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)

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: