目標(biāo)

在本章中，將理解

• k最近鄰（kNN）算法的概念

理論

kNN是可用于監(jiān)督學(xué)習(xí)的最簡單的分類算法之一。這個(gè)想法是在特征空間中搜索測試數(shù)據(jù)的最近鄰。用下面的圖片來研究它。

在圖像中，有兩個(gè)族類，藍(lán)色正方形和紅色三角形。稱每一種為類（Class）。他們的房屋顯示在他們的城鎮(zhèn)地圖中，我們稱之為特征空間（ Feature Space）。 （可以將特征空間視為投影所有數(shù)據(jù)的空間。例如，考慮一個(gè)2D坐標(biāo)空間。每個(gè)數(shù)據(jù)都有兩個(gè)特征，x和y坐標(biāo)。可以在2D坐標(biāo)空間中表示此數(shù)據(jù)；如果有三個(gè)特征，則需要3D空間；現(xiàn)在考慮N個(gè)特征，需要N維空間，這個(gè)N維空間就是其特征空間。在上圖中，可以將其視為2D情況。有兩個(gè)特征）。 現(xiàn)在有一個(gè)新成員進(jìn)入城鎮(zhèn)并創(chuàng)建了一個(gè)新房屋，顯示為綠色圓圈。它應(yīng)該被添加到這些藍(lán)色/紅色家族之一中。稱該過程為分類（Classification）。這個(gè)新會(huì)員應(yīng)該如何分類？本文使用kNN算法解決上述問題。

一種方法是檢查誰是其最近鄰。從圖像中可以明顯看出它是紅色三角形家族。因此，它也被添加到了紅色三角形中。此方法簡稱為最近鄰（Nearest Neighbour ）分類，因?yàn)榉诸悆H取決于最近鄰。 但這是有問題的。紅三角可能是最近的。但是，如果附近有很多藍(lán)色方塊怎么辦？然后，藍(lán)色方塊在該地區(qū)的權(quán)重比紅色三角更大。因此，僅檢查最接近的一個(gè)是不夠的。相反，檢查一些k個(gè)近鄰的族。那么，看誰占多數(shù)，新樣本就屬于那個(gè)類。在上圖中，假設(shè)設(shè)置k=3，即3個(gè)最近族。它有兩個(gè)紅色和一個(gè)藍(lán)色（有兩個(gè)等距的藍(lán)色，但是由于k = 3，只取其中一個(gè)），所以它應(yīng)該加入紅色家族。但是，如果我們?nèi)?code>k=7時(shí)，它有5個(gè)藍(lán)色族和2個(gè)紅色族，它應(yīng)該加入藍(lán)色族。因此，分類結(jié)果隨著k的值而變化。更有趣的是，如果k=4時(shí)，它有2個(gè)紅色鄰居和2個(gè)藍(lán)色鄰居，這是一個(gè)平局！因此最好將k設(shè)置為奇數(shù)。由于分類取決 于k個(gè)最近的鄰居，因此該方法稱為k近鄰。 同樣，在kNN中，在考慮k個(gè)鄰居時(shí)，對所有人都給予同等的重視，這公平嗎？例如，以k=4的情況為例，按照數(shù)量來說這是平局。但是其中的兩個(gè)紅色族比其他兩個(gè)藍(lán)色族離它更近。因此，它更應(yīng)該被添加到紅色。那么如何用數(shù)學(xué)解釋呢？根據(jù)每個(gè)家庭到新來者的距離來給他們一些權(quán)重。對于那些靠近它的人，權(quán)重增加，而那些遠(yuǎn)離它的人，權(quán)重減輕。 然后，分別添加每個(gè)族的總權(quán)重。誰得到的總權(quán)重最高，新樣本歸為那一族。這稱為modified kNN或者** weighted kNN**。 因此，使用kNN算法時(shí)候，需要了解的重要信息如下：

• 需要了解鎮(zhèn)上所有房屋的信息，因?yàn)楸仨殭z查新樣本到所有現(xiàn)有房屋的距離，以找到最近的鄰居。如果有許多房屋和家庭，則需要大量的內(nèi)存，并且需要更多的時(shí)間進(jìn)行計(jì)算
• 任何類型的“訓(xùn)練”或準(zhǔn)備幾乎是零時(shí)間。“學(xué)習(xí)”涉及在測試和分類之前記?。ù鎯?chǔ)）數(shù)據(jù)

OpenCV中的kNN

就像上面一樣，將在這里做一個(gè)簡單的例子，有兩個(gè)族（類）。 因此，在這里，將紅色系列標(biāo)記為Class-0（用0表示），將藍(lán)色系列標(biāo)記為Class-1（用1表示）。創(chuàng)建25個(gè)族或25個(gè)訓(xùn)練數(shù)據(jù)，并將它們標(biāo)記為0類或1類。借助Numpy中的Random Number Generator來完成所有這些工作。然后在Matplotlib的幫助下對其進(jìn)行繪制。紅色系列顯示為紅色三角形，藍(lán)色系列顯示為藍(lán)色正方形。

import cv2
import numpy as np
from matplotlib import pyplot as plt
# Feature set containing (x,y) values of 25 known/training data
trainData = np.random.randint(0, 100, (25, 2)).astype(np.float32)
# Label each one either Red or Blue with numbers 0 and 1
responses = np.random.randint(0, 2, (25, 1)).astype(np.float32)
responses
# Take Red neighbours and plot them
red = trainData[responses.ravel()==0]
plt.scatter(red[:, 0], red[:, 1], 80, 'r', '^')
# Take Blue neighbours and plot them
blue = trainData[responses.ravel()==1]
plt.scatter(blue[:, 0], blue[:, 1], 80, 'b', 's')
plt.show()

由于使用的是隨機(jī)數(shù)生成器，因此每次運(yùn)行代碼都將獲得不同的數(shù)據(jù)。 接下來啟動(dòng)kNN算法，并傳遞trainData和響應(yīng)以訓(xùn)練kNN（它會(huì)構(gòu)建搜索樹）。 然后，將在OpenCV中的kNN的幫助下將一個(gè)新樣本進(jìn)行分類。在進(jìn)入kNN之 前，需要了解測試數(shù)據(jù)（新樣本數(shù)據(jù)）上的知識(shí)。數(shù)據(jù)應(yīng)為浮點(diǎn)數(shù)組，其大小為number??of??testdata×number??of??features×number of features。然后找到新加入的最近鄰?？梢灾付ㄎ覀兿胍嗌賯€(gè)鄰居k（這里設(shè)置為3）。它返回：

• 給新樣本的標(biāo)簽取決于kNN理論。如果要使用“最近鄰居”算法，只需指定k=1即可，其中k是鄰居數(shù)
• k最近鄰的標(biāo)簽
• 與新鄰居的新距離相應(yīng)的距離

下面看看它是如何工作的，新樣本被標(biāo)記為綠色。

# Feature set containing (x,y) values of 25 known/training data
trainData = np.random.randint(0, 100, (25, 2)).astype(np.float32)
# Label each one either Red or Blue with numbers 0 and 1
responses = np.random.randint(0, 2, (25, 1)).astype(np.float32)
# Take Red neighbours and plot them
red = trainData[responses.ravel()==0]
plt.scatter(red[:, 0], red[:, 1], 80, 'r', '^')
# Take Blue neighbours and plot them
blue = trainData[responses.ravel()==1]
plt.scatter(blue[:, 0], blue[:, 1], 80, 'b', 's')
newcomer = np.random.randint(0, 100, (1, 2)).astype(np.float32)
plt.scatter(newcomer[:, 0], newcomer[:, 1], 80, 'g', 'o')
knn = cv2.ml.KNearest_create()
knn.train(trainData, cv2.ml.ROW_SAMPLE, responses)
ret, results, neighbours, dist = knn.findNearest(newcomer, 3)
print("result: {}\n".format(results))
print("neighbours: {}\n".format(neighbours))
print("distance: {}\n".format(dist))
plt.show()

得到了如下的結(jié)果：

它說我們的新樣本有3個(gè)近鄰，一個(gè)來自Red家族，另外兩個(gè)來自Blue家族。因此，他被標(biāo)記為藍(lán)色家庭。

如果有大量數(shù)據(jù)，則可以將其作為數(shù)組傳遞。獲得的相應(yīng)的結(jié)果是以數(shù)組的形式出現(xiàn)。

# Feature set containing (x,y) values of 25 known/training data
trainData = np.random.randint(0, 100, (25, 2)).astype(np.float32)
# Label each one either Red or Blue with numbers 0 and 1
responses = np.random.randint(0, 2, (25, 1)).astype(np.float32)
# Take Red neighbours and plot them
red = trainData[responses.ravel()==0]
plt.scatter(red[:, 0], red[:, 1], 80, 'r', '^')
# Take Blue neighbours and plot them
blue = trainData[responses.ravel()==1]
plt.scatter(blue[:, 0], blue[:, 1], 80, 'b', 's')
# newcomer = np.random.randint(0, 100, (1, 2)).astype(np.float32)
newcomers = np.random.randint(0,100,(10,2)).astype(np.float32)  # 10 new-comers
plt.scatter(newcomers[:, 0], newcomers[:, 1], 80, 'g', 'o')
knn = cv2.ml.KNearest_create()
knn.train(trainData, cv2.ml.ROW_SAMPLE, responses)
ret, results, neighbours, dist = knn.findNearest(newcomers, 3)  # The results also will contain 10 labels.
plt.show()
print("result: {}\n".format(results))
print("neighbours: {}\n".format(neighbours))
print("distance: {}\n".format(dist))

附加資源

• NPTEL notes on Pattern Recognition, Chapter 11
• Wikipedia article on Nearest neighbor search
• Wikipedia article on k-d tree

以上就是OpenCV之理解KNN k-Nearest Neighbour的詳細(xì)內(nèi)容，更多關(guān)于OpenCV理解KNN的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論