一、概述

KNN（K-最近鄰）算法是相對(duì)比較簡(jiǎn)單的機(jī)器學(xué)習(xí)算法之一，它主要用于對(duì)事物進(jìn)行分類(lèi)。用比較官方的話(huà)來(lái)說(shuō)就是：給定一個(gè)訓(xùn)練數(shù)據(jù)集，對(duì)新的輸入實(shí)例，在訓(xùn)練數(shù)據(jù)集中找到與該實(shí)例最鄰近的K個(gè)實(shí)例， 這K個(gè)實(shí)例的多數(shù)屬于某個(gè)類(lèi)，就把該輸入實(shí)例分類(lèi)到這個(gè)類(lèi)中。為了更好地理解，通過(guò)一個(gè)簡(jiǎn)單的例子說(shuō)明。

我們有一組自擬的關(guān)于電影中鏡頭的數(shù)據(jù)：

那么問(wèn)題來(lái)了，如果有一部電影 X，它的打戲?yàn)?3，吻戲?yàn)?2。那么這部電影應(yīng)該屬于哪一類(lèi)？

我們把所有數(shù)據(jù)通過(guò)圖表顯示出來(lái)（圓點(diǎn)代表的是自擬的數(shù)據(jù)，也稱(chēng)訓(xùn)練集；三角形代表的是 X 電影的數(shù)據(jù)，稱(chēng)為測(cè)試數(shù)據(jù)）：

計(jì)算測(cè)試數(shù)據(jù)到訓(xùn)練數(shù)據(jù)之間的距離，假設(shè) k 為 3，那么我們就找到距離中最小的三個(gè)點(diǎn)，假如 3 個(gè)點(diǎn)中有 2 個(gè)屬于動(dòng)作片，1 個(gè)屬于愛(ài)情片，那么把該電影 X 分類(lèi)為動(dòng)作片。這種通過(guò)計(jì)算距離總結(jié) k 個(gè)最鄰近的類(lèi)，按照”少數(shù)服從多數(shù)“原則分類(lèi)的算法就為 KNN（K-近鄰）算法。

二、算法介紹

還是以上面的數(shù)據(jù)為例，打戲數(shù)為 x，吻戲數(shù)為 y，通過(guò)歐式距離公式計(jì)算測(cè)試數(shù)據(jù)到訓(xùn)練數(shù)據(jù)的距離，我上中學(xué)那會(huì)兒不知道這個(gè)叫做歐式距離公式，一直用”兩點(diǎn)間的距離公式“來(lái)稱(chēng)呼這個(gè)公式： 。但是現(xiàn)實(shí)中的很多數(shù)據(jù)都是多維的，即使如此，也還是按照這個(gè)思路進(jìn)行計(jì)算，比如如果是三維的話(huà)，就在根號(hào)里面再加上 z 軸差的平方，即  ，以此類(lèi)推。

知道了這個(gè)計(jì)算公式，就可以計(jì)算各個(gè)距離了。我們以到最上面的點(diǎn)的距離為例： ，那么從上到下的距離分別是： ， ， ， ?，F(xiàn)在我們把 k 定為 3，那么距離最近的就是后面三個(gè)數(shù)了，在這三個(gè)數(shù)中，有兩個(gè)屬于動(dòng)作片，因此，電影 X 就分類(lèi)為動(dòng)作片。

三、算法實(shí)現(xiàn)

知道了原理，那就可以用代碼實(shí)現(xiàn)了，這里就不再贅述了，直接上帶注釋的 Python 代碼：

'''
  trainData - 訓(xùn)練集
  testData - 測(cè)試集
  labels - 分類(lèi)
'''
def knn(trainData, testData, labels, k):
  # 計(jì)算訓(xùn)練樣本的行數(shù)
  rowSize = trainData.shape[0]
  # 計(jì)算訓(xùn)練樣本和測(cè)試樣本的差值
  diff = np.tile(testData, (rowSize, 1)) - trainData
  # 計(jì)算差值的平方和
  sqrDiff = diff ** 2
  sqrDiffSum = sqrDiff.sum(axis=1)
  # 計(jì)算距離
  distances = sqrDiffSum ** 0.5
  # 對(duì)所得的距離從低到高進(jìn)行排序
  sortDistance = distances.argsort()
  
  count = {}
  
  for i in range(k):
    vote = labels[sortDistance[i]]
    count[vote] = count.get(vote, 0) + 1
  # 對(duì)類(lèi)別出現(xiàn)的頻數(shù)從高到低進(jìn)行排序
  sortCount = sorted(count.items(), key=operator.itemgetter(1), reverse=True)
  
  # 返回出現(xiàn)頻數(shù)最高的類(lèi)別
  return sortCount[0][0]

ps：np.tile(testData, (rowSize, 1)) 是將 testData 這個(gè)數(shù)據(jù)擴(kuò)展為 rowSize 列，這樣能避免運(yùn)算錯(cuò)誤；

sorted(count.items(), key=operator.itemgetter(1), reverse=True) 排序函數(shù)，里面的參數(shù) key=operator.itemgetter(1), reverse=True 表示按照 count 這個(gè)字典的值（value）從高到低排序，如果把 1 換成 0，則是按字典的鍵（key）從高到低排序。把 True 換成 False 則是從低到高排序。

四、測(cè)試與總結(jié)

用 Python 實(shí)現(xiàn)了算法之后，我們用上面的數(shù)據(jù)進(jìn)行測(cè)試，看一下結(jié)果是否和我們預(yù)測(cè)的一樣為動(dòng)作片：

trainData = np.array([[5, 1], [4, 0], [1, 3], [0, 4]])
labels = ['動(dòng)作片', '動(dòng)作片', '愛(ài)情片', '愛(ài)情片']
testData = [3, 2]
X = knn(trainData, testData, labels, 3)
print(X)

執(zhí)行這段代碼后輸出的結(jié)果為：動(dòng)作片 。和預(yù)測(cè)的一樣。當(dāng)然通過(guò)這個(gè)算法分類(lèi)的正確率不可能為 100%，可以通過(guò)增加修改數(shù)據(jù)測(cè)試，如果有大量多維的數(shù)據(jù)就更好了。

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

最新評(píng)論