目標
在本章中，我們將瞭解k近鄰（kNN）算法的原理。
理論
kNN是可用於監督學習的最簡單的分類算法之一。這個想法是在特徵空間中搜索測試數據的最近鄰。我們將用下面的圖片來研究它。
在圖像中，有兩個族，藍色正方形和紅色三角形。我們稱每一種為類。他們的房屋顯示在他們的城鎮地圖中，我們稱之為特徵空間。 （你可以將要素空間視為投影所有數據的空間。例如，考慮一個2D座標空間。每個數據都有兩個要素，x和y座標。你可以在2D座標空間中表示此數據，對吧？現在假設如果有三個要素，則需要3D空間；現在考慮N個要素，需要N維空間，對嗎？這個N維空間就是其要素空間。在我們的圖像中，你可以將其視為2D情況。有兩個功能）。
現在有一個新成員進入城鎮並創建了一個新房屋，顯示為綠色圓圈。他應該被添加到這些藍色/紅色家族之一中。我們稱該過程為分類。我們所做的？由於我們正在處理kNN，因此讓我們應用此算法。
一種方法是檢查誰是他的最近鄰。從圖像中可以明顯看出它是紅色三角形家族。因此，他也被添加到了紅色三角形中。此方法簡稱為“最近鄰”，因為分類僅取決於最近鄰。
但這是有問題的。紅三角可能是最近的。但是，如果附近有很多藍色方塊怎麼辦？然後，藍色方塊在該地區的權重比紅色三角更大。因此，僅檢查最接近的一個是不夠的。相反，我們檢查一些k近鄰的族。那麼，無論誰佔多數，新樣本都屬於那個族。在我們的圖像中，讓我們取k=3，即3個最近族。他有兩個紅色和一個藍色（有兩個等距的藍色，但是由於k = 3，我們只取其中一個），所以他又應該加入紅色家族。但是，如果我們取k=7怎麼辦？然後，他有5個藍色族和2個紅色族。太好了！！現在，他應該加入藍色族。因此，所有這些都隨k的值而變化。更有趣的是，如果k=4怎麼辦？他有2個紅色鄰居和2個藍色鄰居。這是一個平滑！因此最好將k作為奇數。由於分類取決於k個最近的鄰居，因此該方法稱為
k近鄰。同樣，在kNN中，我們確實在考慮k個鄰居，但我們對所有人都給予同等的重視，對吧？這公平嗎？例如，以k=4的情況為例。我們說這是平局。但是請注意，這兩個紅色族比其他兩個藍色族離他更近。因此，他更應該被添加到紅色。那麼我們如何用數學解釋呢？我們根據每個家庭到新來者的距離來給他們一些權重。對於那些靠近他的人，權重增加，而那些遠離他的人，權重減輕。然後，我們分別添加每個族的總權重。誰得到的總權重最高，新樣本歸為那一族。這稱為modified kNN。
那麼你在這裡看到的一些重要內容是什麼？
- 你需要了解鎮上所有房屋的信息，對嗎？因為，我們必須檢查新樣本到所有現有房屋的距離，以找到最近的鄰居。如果有許多房屋和家庭，則需要大量的內存，並且需要更多的時間進行計算。
- 幾乎沒有時間進行任何形式的訓練或準備。
現在讓我們在OpenCV中看到它。
OpenCV中的kNN
就像上面一樣，我們將在這裡做一個簡單的例子，有兩個族（類）。然後在下一章中，我們將做一個更好的例子。
因此，在這裡，我們將紅色系列標記為Class-0（因此用0表示），將藍色系列標記為Class-1（用1表示）。我們創建25個族或25個訓練數據，並將它們標記為0類或1類。我們藉助Numpy中的Random Number Generator來完成所有這些工作。
然後我們在Matplotlib的幫助下對其進行繪製。紅色系列顯示為紅色三角形，藍色系列顯示為藍色正方形。
<code>import cv2 as cv
import numpy as np
import matplotlib.pyplot as plt
# 包含(x,y)值的25個已知/訓練數據的特徵集
trainData = np.random.randint(0,100,(25,2)).astype(np.float32)
# 用數字0和1分別標記紅色或藍色
responses = np.random.randint(0,2,(25,1)).astype(np.float32)
# 取紅色族並繪圖
red = trainData[responses.ravel()==0]
plt.scatter(red[:,0],red[:,1],80,'r','^')
# 取藍色族並繪圖
blue = trainData[responses.ravel()==1]
plt.scatter(blue[:,0],blue[:,1],80,'b','s')
plt.show()/<code>
你會得到與我們的第一張圖片相似的東西。由於你使用的是隨機數生成器，因此每次運行代碼都將獲得不同的數據。
接下來啟動kNN算法，並傳遞trainData和響應以訓練kNN（它會構建搜索樹）。
然後，我們將在OpenCV中的kNN的幫助下將一個新樣本帶入一個族並將其分類。在進入kNN之前，我們需要了解測試數據（新樣本數據）上的知識。我們的數據應為浮點數組，其大小為$number\\ of\\ testdata\\times number\\ of\\ features$。然後我們找到新加入的最近鄰。我們可以指定我們想要多少個鄰居。它返回：
- 給新樣本的標籤取決於我們之前看到的kNN理論。如果要使用“最近鄰居”算法，只需指定k=1即可，其中k是鄰居數。
- k最近鄰的標籤。
- 衡量新加入到每個最近鄰的相應距離。
因此，讓我們看看它是如何工作的。新樣本被標記為綠色。
<code>newcomer = np.random.randint(0,100,(1,2)).astype(np.float32)
plt.scatter(newcomer[:,0],newcomer[:,1],80,'g','o')
knn = cv.ml.KNearest_create()
knn.train(trainData, cv.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()/<code>
我得到了如下的結果：
<code>result: [[ 1.]]
neighbours: [[ 1. 1. 1.]]
distance: [[ 53. 58. 61.]]/<code>
它說我們的新樣本有3個近鄰，全部來自Blue家族。因此，他被標記為藍色家庭。從下面的圖可以明顯看出：
如果你有大量數據，則可以將其作為數組傳遞。還獲得了相應的結果作為數組。
<code># 10個新加入樣本
newcomers = np.random.randint(0,100,(10,2)).astype(np.float32)
ret, results,neighbours,dist = knn.findNearest(newcomer, 3)
# 結果包含10個標籤/<code>
附加資源
- NPTEL關於模式識別的註釋，第11章
練習
閱讀更多 人工智能遇見磐創 的文章
