機器學習入門：用OpenCV實現k-NN算法，終於有人講明白了

OpenCV 算法機器學習腳本語言 Python 歷史華章科技 2019-06-13

導讀：OpenCV 的構建是為了提供計算機視覺的通用基礎接口，現在已經成為經典和最優秀的計算機視覺和機器學習的綜合算法工具集。作為一個開源項目，研究者、商業用戶和政府部門都可以輕鬆利用和修改現成的代碼。
k-NN算法可以認為是最簡單的機器學習算法之一。本文教你利用OpenCV 和 Python 的基礎知識，實現 k-NN算法。

作者：邁克爾·貝耶勒（Michael Beyeler）

如需轉載請聯繫華章科技

01 使用分類模型預測類別：問題的提出

假設在一個叫作隨機鎮的小鎮，人們對他們的兩個運動隊隨機城紅隊和隨機城藍隊非常痴迷。紅隊歷史悠久，深受人們喜愛。但隨後一些外鎮的百萬富翁來到小鎮，買下紅隊中最出色的得分手，並開始組建一支新的球隊，藍隊。

除了讓大部分紅隊球迷不滿之外，那個最出色的得分手依舊可以在藍隊中一步一步贏得冠軍。儘管依舊會有一些永遠無法原諒他早期職業選擇的球迷不滿，幾年之後他還是會返回紅隊。

但無論如何，你可以發現紅隊球迷與藍隊球迷的關係並不好。事實上，這兩隊的球迷因為不願與對方做鄰居，連住所都是分開的。我甚至聽到過這種故事，紅隊球迷在藍隊球迷搬到家附近時，會故意搬走到其他地方。這是真實的故事！

無論如何，我們一無所知的進入這個小鎮，嘗試挨家挨戶賣給人們一些藍隊的貨物。然而，時不時地會遇到一些熱血的紅隊球迷會因為我們售賣藍隊的東西而對我們大喊大叫，並把我們驅趕出他們的草坪。非常不友好！如果可以避免這些房屋而僅僅訪問那些藍隊球迷的家，壓力將會更小，也可以更好地利用時間。

由於堅信可以學會預測紅隊球迷居住的地方，我們開始記錄每次的訪問。如果遇到了一個紅隊球迷的家，就在手邊的小鎮地圖上畫一個紅色三角形；否則，就畫一個藍色正方形。一陣子之後，我們就非常瞭解他們的居住信息了。

▲隨機鎮的小鎮地圖

然而，現在我們到了地圖中綠色圓圈標記的房子前了。應該敲門嗎？我們嘗試著找到一些線索來確定他們支持哪個球隊（也許在後陽臺上插著球隊的旗幟），但沒有找到。那如何知道敲門是否安全呢？

這個有些愚蠢的例子準確說明了監督學習算法可以解決的一類問題。我們有一些觀察信息（房屋、房屋的地點和他們支持球隊的顏色）組成了訓練數據。可以使用這些數據來從經驗裡學習，這樣當面對預測新房子的主人支持的球隊顏色這一任務時，就可以有足夠的信息做出評估。

正如前面所說，紅隊的球迷對他們的球隊非常狂熱，因此他們絕不可能成為藍隊球迷的鄰居。我們是否可以使用這個信息比對所有鄰居的房屋，以此來查明居住在新房子中的是哪一隊的球迷？

這正是k-NN算法將要處理的問題。

02 理解 k-NN 算法

k-NN算法可以認為是最簡單的機器學習算法之一。原因是我們只需要存儲訓練數據集。接下來，為了對新數據點進行預測，僅需要在訓練數據集中找到它最近鄰的點就可以了。

簡單而言，k-NN算法認為一個數據點很可能與它近鄰的點屬於同一個類。思考一下：如果我們的鄰居是紅隊球迷，我們很可能也是紅隊球迷，否則我們可能很早之前就搬家到其他地方了。對於藍隊球迷而言也是這樣。

當然，有些社區可能稍微複雜一些。在這種情況下，我們將不僅僅考慮我們最近鄰的類別（即k=1），而是考慮k個最近鄰的類別。對於前面提到的例子，如果我們是紅隊球迷，我們可能不會搬到鄰居大部分都是藍隊球迷的地方。

這就是它的全部了。

03 使用 OpenCV 實現 k-NN

使用OpenCV，可以很輕鬆地通過cv2.ml.KNearest_create()函數來創建一個k-NN模型。然後進行以下幾步：

生成一些訓練數據。
指定k值，創建一個k-NN對象。
找到想要分類的新數據點的k個最近鄰的點。
使用多數投票來分配新數據點的類標籤。
畫出結果圖。

首先引入所有必需的模塊：使用k-NN算法的OpenCV、處理數據的NumPy、用於繪圖的Matplotlib。如果使用Jupyter Notebook，別忘了調用%matplotlib inline魔法命令。

In [1]: import numpy as np
... import cv2
... import matplotlib.pyplot as plt
... %matplotlib inline
In [2]: plt.style.use('ggplot')

1. 生成訓練數據

第一步是生成一些訓練數據。我們將使用NumPy的隨機數生成器來完成這個操作。我們將固定隨機數生成器的種子值，這樣重新運行腳本將總可以生成相同的值。

In [3]: np.random.seed(42)

好了，現在可以開始了。那麼我們的訓練數據到底應該是什麼樣子的呢？

在前面的例子中，數據點是小鎮地圖中的房子。每個數據點有兩個特徵（也就是，在小鎮地圖上的位置的x和y座標）以及一個類別標籤（也就是，如果是藍隊球迷居住的地方則是一個藍色的正方形，如果是紅隊球迷居住的地方則是一個紅色的三角形）。

單獨數據點的特徵可以用一個具有兩個元素的向量表示，這個向量表示數據點在小鎮地圖上的x座標和y座標。相似的，如果標記是藍色的正方形，則類別是數字0，如果是紅色的三角形，則類別是數字1。

可以通過從地圖上隨機選擇一個位置並隨機分配一個標籤（不是0就是1）就可以生成一個數據點。假設小鎮地圖的範圍是0≤x＜100和0≤y＜100。那麼可以使用下面的代碼來生成一個隨機數據點：

In [4]: single_data_point = np.random.randint(0, 100, 2)
... single_data_point
Out[4]: array([51, 92])

正如上面的輸出結果所示，這段代碼將會從0到100之間獲取兩個隨機的整數。我們將把第一個整數當作數據點在地圖上的x座標值，第二個整數當作數據點的y座標值。同樣，可以為這個數據點選擇一個標籤：

In [5]: single_label = np.random.randint(0, 2)
... single_label
Out[5]: 0

結果表示這個數據點的類別是0，我們把它當作一個藍色的正方形。

把這個過程包裝成函數，輸入是要生成的數據點的個數（即num_sample）和每個數據點的特徵數（即num_features）。

In [6]: def generate_data(num_samples, num_features=2):
 """隨機生成一些數據點"""

因為在這個例子中特徵的數量是2，使用默認的參數值是沒有問題的。在這種調用函數時不顯式指定num_features值的情況下，這個參數會被自動分配為2。相信你已經瞭解了這個知識點。

我們想要創建的數據矩陣應該有num_samples行、num_features列，其中每一個元素都應該是[0, 100]範圍內的一個隨機整數。

... data_size = (num_samples, num_features)
... train_data = np.random.randint(0, 100, size=data_size)

同樣，我們想要創建一個所有樣本在[0, 2]範圍內的隨機整數標籤值的向量：

... labels_size = (num_samples, 1)
... labels = np.random.randint(0, 2, size=labels_size)

別忘了讓函數返回生成的數據：

... return train_data.astype(np.float32), labels

Tips：OpenCV對於數據類型有些過分的講究，因此確保總是把數據點的類型轉換為np.float32！

接下來對函數進行測試，先生成任意數量的數據點，比如說11個數據點，並隨機選擇它們的座標：

In [7]: train_data, labels = generate_data(11)
... train_data
Out[7]: array([[ 71., 60.],
 [ 20., 82.],
 [ 86., 74.],
 [ 74., 87.],
 [ 99., 23.],
 [ 2., 21.],
 [ 52., 1.],
 [ 87., 29.],
 [ 37., 1.],
 [ 63., 59.],
 [ 20., 32.]], dtype=float32)

可以從上面的輸出結果看到，train_data變量是一個11x2的數組，每一行表示一個單獨的數據點。可以通過使用數組的索引獲取第一個數據和它對應的標籤：

In [8]: train_data[0], labels[0]
Out[8]: (array([ 71., 60.], dtype=float32), array([1]))

這個結果告訴我們第一個數據點是一個藍色的正方形（因為它的類別是0），它在小鎮地圖的座標位置是(x, y) = (71, 60)。如果想要的話，可以使用Matplotlib在小鎮地圖上畫出這個數據點：

In [9]: plt.plot(train_data[0, 0], train_data[0, 1], 'sb')
... plt.xlabel('x coordinate')
... plt.ylabel('y coordinate')
Out[9]: <matplotlib.text.Text at 0x137814226a0>

但如果想要一次就顯示所有的訓練數據集呢？可以寫一個函數。這個函數的輸入應該是一個所有都是藍色正方形的數據點的列表（all_blue）和一個所有都是紅色三角形的數據點的列表（all_red）：

In [10]: def plot_data(all_blue, all_red):

接下來函數應該可以把所有藍色數據點用藍色正方形畫出來（使用顏色'b'和標記's'），可以使用Matplotlib中的scatter函數完成這個任務。在使用這個函數時，需要把藍色數據點當作N×2的數組來傳入，其中N是樣本的數量。接著all_blue[:,0]包含了所有藍色數據點的x座標，all_blue[:, 1]包含了所有藍色數據點的y座標：

... plt.scatter(all_blue[:, 0], all_blue[:, 1], c='b', marker='s', s=180)

同理，對於所有的紅色數據點也可以這麼做：

... plt.scatter(all_red[:, 0], all_red[:, 1], c='r', marker='^', s=180)

最後，設置繪圖的標籤：

... plt.xlabel('x coordinate (feature 1)')
... plt.ylabel('y coordinate (feature 2)')

在我們的數據集上測試一下這個函數吧！首先需要把所有的數據點分成紅色數據集和藍色數據集。可以使用下面的命令（其中ravel將平面化數組）快速選擇前面創建的labels數組中所有等於0的元素：

In [11]: labels.ravel() == 0
Out[11]: array([False, False, False, True, False, True, True, True, True,
 True, False], dtype=bool)

前面創建的train_data中對應標籤為0的那些行就是所有藍色的數據點：

In [12]: blue = train_data[labels.ravel() == 0]

對於所有的紅色數據點也可以同樣操作：

In [13]: red = train_data[labels.ravel() == 1]

最後，讓我們畫出所有的數據點：

In [14]: plot_data(blue, red)

這將會創建如下所示的圖：

▲整個訓練數據集的可視化

2. 訓練分類器

現在是時候訓練分類器了。

和其他所有的機器學習函數一樣，k-NN分類器也是OpenCV 3.1 中ml模塊的一部分。可以使用下面的命令來創建一個新的分類器：

In [15]: knn = cv2.ml.KNearest_create()

Tips：在OpenCV的舊版本中，這個函數可能叫作cv2.KNearest()。

接下來把訓練數據傳入到train方法中：

In [16]: knn.train(train_data, cv2.ml.ROW_SAMPLE, labels)
Out[16]: True

這裡，必須告訴knn我們的數據是一個 N×2 的數組（即每一行都是一個數據點）。這個函數會在執行成功後返回True。

3. 預測新數據點的類別

knn提供的另一個非常有用的方法叫作findNearest。它可以根據最近鄰數據點的標籤來預測新數據點的標籤。

由於有generate_data函數，我們可以非常容易地生成一個新的數據點！可以把新數據點當作只有一個數據的數據集。

In [17]: newcomer, _ = generate_data(1)
Out[17]: newcomer

函數也返回一個隨機的類別，但我們對它不感興趣。相反，我們想要使用我們訓練的模型對它進行預測！可以通過一個下劃線（_）讓Python忽略輸出值。

回到我們的小鎮地圖，我們要像之前一樣把訓練數據集畫出來，並將新的數據點加入，用綠色的圓圈表示（因為我們現在還不知道它應該是一個藍色的正方形還是一個紅色的三角形）。

In [18]: plot_data(blue, red)
... plt.plot(newcomer[0, 0], newcomer[0, 1], 'go', markersize=14);

Tips：可以在plt.plot函數後面添加一個分號以抑制輸出，與Matlab一樣。

上面的代碼將生成下面這幅圖（不包含圓環）：

▲整個訓練數據集，加上一個有待確定標籤的新數據點（綠色）

如果要你根據它的臨近點猜測，你會給新的數據點分配什麼標籤，藍色還是紅色呢？

其實，這也看情況，不是嗎？如果看離它最近的房子（那個位置大致在(x, y)=(85,75)，上圖中點圓裡面的房子），可能會把新的數據點同樣分配一個紅色的三角形。這也確實是在k=1的情況下我們的分類器預測的結果。

In [19]: ret, results, neighbor, dist = knn.findNearest(newcomer, 1)
... print("Predicted label:\t", results)
... print("Neighbors label:\t", neighbor)
... print("Distance to neighbor:\t", dist)
Out[19]: Predicted label: [[ 1.]]
... Neighbors label: [[ 1.]]
... Distance to neighbor: [[ 250.]]

這裡，knn報告說最近鄰的點有250個單位遠，其類別是1（我們說過1對應的是紅色三角形），因此新的數據點類別應該也是1。如果設置k=2最近鄰和k=3最近鄰，結果也是一樣的。

但要小心不要選擇任意偶數的k值。為什麼呢？其實，可以從上面的圖中看出來（虛線圓），在虛線圓裡面的6個最近鄰點中，有3個藍色正方形和3個紅色三角形—這是個平局！

Tips：在這種平局的情況下，OpenCV的k-NN實現將會選擇到數據點整體距離更近的鄰居。

最後，如果非常大地擴大搜索窗口，根據k=7最近鄰來對新數據點分類（在前面的圖中是實線圓），會發生什麼呢？

通過調用findNearest方法並設置k=7，可以看到結果：

In [20]: ret, results, neighbor, dist = knn.findNearest(newcomer, 7)
... print("Predicted label:\t", results)
... print("Neighbors label:\t", neighbor)
... print("Distance to neighbor:\t", dist)
Out[20]: Predicted label: [[ 0.]]
 Neighbors label: [[ 1. 1. 0. 0. 0. 1. 0.]]
 Distance to neighbor: [[ 250. 401. 784. 916. 1073. 1360. 4885.]]

忽然之間，預測的標籤變為0（藍色正方形）。原因是現在實線圓內有四個鄰居是藍色正方形（標籤0），而只有三個是紅色三角形（標籤1）。因此多數投票建議預測新來者也是一個藍色正方形。

正如所看到的，k-NN的輸出結果會隨著k的變化而變化。然而，大多數情況下是無法提前知道k為何值時是最合適的。對於這個問題最簡單的解決方法是嘗試一組k值，並觀察哪個的結果最好。

關於作者：Michael Beyeler，華盛頓大學神經工程和數據科學專業的博士後，主攻仿生視覺計算模型，用以為盲人植入人工視網膜（仿生眼睛），改善盲人的視覺體驗。他的工作屬於神經科學、計算機工程、計算機視覺和機器學習的交叉領域。同時他也是多個開源項目的積極貢獻者。

本文摘編自《機器學習：使用OpenCV和Python進行智能圖像處理》，經出版方授權發佈。