• 46.1 理解 K 近邻
  • 46.1.1 OpenCV 中的 kNN
• 46.2 使用 kNN 对手写数字 OCR
  • 46.2.1 手写数字的 OCR
  • 46.2.2 英文字母的 OCR
• 47.1 理解 SVM
  • 47.1.1 线性数据分割

部分 VIII：机器学习

46 K 近邻（k-Nearest Neighbour）

46.1 理解 K 近邻

kNN 是最简单的监督学习分类器，就是找出测试数据在特征空间中的最近邻居。

上图中的对象可以分成两组，蓝色方块和红色三角。每一组也可以称为一个 类。

例如在一个 2D 的坐标空间中，每个数据都两个特征 $x$ 坐标和 $y$ 坐标，你可以在 2D 坐标空间中表示这些数据。 $N$ 个特征就需要 $N$ 维空间，这个 $N$ 维空间就是特征空间。在上图中，我们可以认为是具有两个特征色 2D 空间）。

如果给定绿色的点，我们需要将这个点归为红色或蓝色，我们把这过程称为 分类。一个方法就是查看他最近的邻居属于哪个类，从图像中我们知道最近的是红色三角形。所以他被分到红色类。这种方法被称为简单近邻，因为分类仅仅决定与它最近的邻居。

但是这里还有一个问题。红色三角可能是最近的，但如果他周围还有很多蓝色方块怎么办呢？此时蓝色方块对局部的影响应该大于红色三角。所以仅仅检测最近的一个邻居是不足的。所以我们检测 $k$ 个最近邻居。谁在这 $k$ 个邻居中占据多数，那新的成员就属于那一类。

如果 $k$ 等于 $3$ ，也就是在上面图像中检测 $3$ 个最近的邻居。他有两个红的和一个蓝的邻居，所以他还是属于红色类。但是如果 $k$ 等于 $7$ 呢？他有 $5$ 个蓝色和 $2$ 个红色邻居，现在他就会被分到蓝色类了。 $k$ 的取值对结果影响非常大。更有趣的是，如果 $k$ 等于 $4$ 呢？两个红两个蓝。这是一个死结。所以 $k$ 的取值最好为奇数。这中根据 $k$ 个最近邻居进行分类的方法被称为 kNN。

在 kNN 中我们考虑了 $k$ 个最近邻居，但是我们给了这些邻居相等的权重，这样做公平吗？以 $k$ 等于 $4$ 为例，我们说它是一个死结。但是两个红色三角比两个蓝色方块距离新成员更近一些。所以他更应该被分为红色类。那用数学应该如何表示呢？我们要根据每个房子与新房子的距离对每个房子赋予不同的权重。距离近的具有更高的权重，距离远的权重更低。然后我们根据两个类的权重和来判断新房子的归属，谁的权重大就属于谁。这被称为 修改过的 kNN。

那这里面哪些是重要的呢？

• 我们需要整个数据集中每个实例的信息。因为我们要测量测试实例到所有现存实例的距离，并在其中找到最近的。如果数据集有很多实例，就要占用很大的内存和更多的计算时间
• 训练和处理几乎不需要时间

现在我们看看 OpenCV 中的 kNN。

46.1.1 OpenCV 中的 kNN

这里我们将红色类标记为 Class-0，蓝色类标记为 Class-1。还要再创建 $25$ 个训练数据，把它们分别标记为 Class-0 或者 Class-1。Numpy 中随机数产生器可以帮助我们完成这个任务。

import numpy as np
import matplotlib.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)

# Labels each one either Red or Blue with numbers 0 and 1
responses = np.random.randint(0, 2, (25, 1)).astype(np.float32)

# Take Red families and plot them
red = trainData[responses.ravel() == 0]
plt.scatter(red[:, 0], red[:, 1], 80, 'r', '^')

# Take Blue families and plot them
blue = trainData[responses.ravel() == 1]
plt.scatter(blue[:, 0], blue[:, 1], 80, 'b', 's')

plt.show()

下面就是 kNN 算法分类器的初始化，我们要传入一个训练数据集，以及与训练数据对应的分类来训练 kNN 分类器（构建搜索树）。

最后要使用 OpenCV 中的 kNN 分类器，我们给它一个测试数据，让它来进行分类。在使用 kNN 之前，我们应该对测试数据有所了解。我们的数据应该是大小为数据数目乘以特征数目的浮点性数组。然后我们就可以通过计算找到测试数据最近的邻居了。我们可以设置返回的最近邻居的数目。返回值包括：

1. 由 kNN 算法计算得到的测试数据的类别标志（ $0$ 或 $1$ ）。如果你想使用最近邻算法，只需要将 $k$ 设置为 $1$ ， $k$ 就是最近邻的数目
2. $k$ 个最近邻居的类别标志
3. 每个最近邻居到测试数据的距离

import cv2
import matplotlib.pyplot as plt
import numpy as np

# Feature set containing (x,y) values of 25 known/training data
trainData = np.random.randint(0, 100, (25, 2)).astype(np.float32)

# Labels each one either Red or Blue with numbers 0 and 1
responses = np.random.randint(0, 2, (25, 1)).astype(np.float32)

# Take Red families and plot them
red = trainData[responses.ravel() == 0]
plt.scatter(red[:, 0], red[:, 1], 80, 'r', '^')

# Take Blue families 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:', results)
print('neighbours:', neighbours)
print('distance:', dist)

plt.show()

我们得到的结果：

result: [[1.]]
neighbours: [[0. 1. 1.]]
distance: [[ 16. 289. 514.]]

这说明我们的测试结果为蓝色，有两个蓝色邻居和一个红色邻居，所有被判断为蓝色，如图所示：

如果我们有大量的数据要进行测试，可以直接传入一个数组。对应的结果同样也是数组。

# 10 new comers
newcomers = np.random.randint(0, 100, (10, 2)).astype(np.float32)
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)

result:
[[1.]
 [0.]
 [1.]
 [1.]
 [1.]
 [0.]
 [1.]
 [0.]
 [0.]
 [0.]]
neighbours:
[[1. 1. 1.]
 [0. 0. 1.]
 [1. 1. 0.]
 [1. 0. 1.]
 [1. 1. 1.]
 [0. 0. 1.]
 [1. 1. 1.]
 [0. 1. 0.]
 [0. 1. 0.]
 [0. 0. 1.]]
distance:
[[ 529.  580.  605.]
 [ 229.  289.  292.]
 [  25.   65.  145.]
 [   0.  260.  377.]
 [  17.  193.  274.]
 [ 260.  436.  541.]
 [ 233. 1297. 1373.]
 [  29.   72.   89.]
 [ 234.  281.  306.]
 [  61.  314.  349.]]

46.2 使用 kNN 对手写数字 OCR

目标

• 要根据我们掌握的 kNN 知识创建一个基本的 OCR 程序
• 使用 OpenCV 自带的手写数字和字母数据测试我们的程序

46.2.1 手写数字的 OCR

我们的目的是创建一个可以对手写数字进行识别的程序。为了达到这个目的我们需要训练数据和测试数据。

现在 OpenCV 已经不再内置 OCR 手写数字的测试数据了，图片 digits.png 可以在一些网站下载：

https://cdn.jsdelivr.net/gh/opencv/opencv@3.2.0/samples/data/digits.png

图片如下：

其中有 $5000$ 个手写数字（ $0 \sim 9$ 每个数字包含 $500$ 个实例）。每个数字是一个 $20 \times 20$ 的小图。所以第一步就是将这个图像分割成 $5000$ 个不同的数字。我们在将拆分后的每一个数字的图像重排成一行含有 $400$ 个像素点的新图像。

这个就是我们的特征集，所有像素的灰度值。这是我们能创建的最简单的特征集。我们使用每个数字的前 $250$ 个样本做训练数据，剩余的 $250$ 个做测试数据。让我们先准备一下：

import cv2
import numpy as np
from matplotlib import pyplot as plt

img = cv2.imread('./images/digits.png')
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)

# Now we split the image to 5000 cells, each 20x20 size
cells = [np.hsplit(row, 100) for row in np.vsplit(gray, 50)]

# Make it into a Numpy array. It size will be (50,100,20,20)
x = np.array(cells)

# Now we prepare train_data and test_data.
train = x[:, :50].reshape(-1, 400).astype(np.float32)  # Size = (2500,400)
test = x[:, 50:100].reshape(-1, 400).astype(np.float32)  # Size = (2500,400)

# Create labels for train and test data
k = np.arange(10)
train_labels = np.repeat(k, 250)[:, np.newaxis]
test_labels = train_labels.copy()

# Initiate kNN, train the data, then test it with test data for k=1
knn = cv2.ml.KNearest_create()
knn.train(train, cv2.ml.ROW_SAMPLE, train_labels)
ret, result, neighbours, dist = knn.findNearest(test, k=5)

# Now we check the accuracy of classification
# For that, compare the result with test_labels and check which are wrong
matches = result == test_labels
correct = np.count_nonzero(matches)
accuracy = correct * 100.0 / result.size
print(accuracy)

运行结果为：

91.76

现在最基本的 OCR 程序已经准备好了，这个示例中我们得到的准确率为 $91\%$ 。改善准确度的一个办法是提供更多的训练数据，尤其是判断错误的那些数字。为了避免每次运行程序都要准备和训练分类器，我们最好把它保留，这样在下次运行是时，只需要从文件中读取这些数据开始进行分类就可以了。Numpy 函数 np.savetxt()，np.load() 等可以帮助我们搞定这些。

46.2.2 英文字母的 OCR

访问：http://archive.ics.uci.edu/ml/datasets/Letter+Recognition 获取更多信息。

47 支持向量机

47.1 理解 SVM

目标

• 对 SVM 有一个直观理解

47.1.1 线性数据分割

最短距离：

$$\mathrm{distance}_\text{support vector} = \frac{1} {\lVert \omega \rVert}$$

$$\min_{\omega, b_0} L(\omega, b_0) = \frac{1}{2} \lVert \omega \rVert^2 \text{ subject to } t_i(\omega^{\mathsf{T}}x + b_0) \ge 1 \,\forall\, i$$

其中 $t_i$ 是每一组标记， $t_i \in [-1,\, 1]$ 。

$$\begin{aligned} \phi(p) &= \left(p_1^2,\, p_2^2,\, \sqrt{2}p_1 p_2\right)\phi(q) \\ &= \left(q_1^2,\, q_2^2,\, \sqrt{2}q_1 q_2\right) \end{aligned}$$

核函数 $K(p,\,q)$ 定义为：

$$\begin{aligned} K(p,\,q) &= \phi(p) \cdot \phi(q) \\ &= \phi(p)^{\mathsf{T}} \phi(q) \\ &= \left(p_1^2,\,p_2^2,\,\sqrt{2}p_1 p_2\right) \cdot \left(q_1^2,\,q_2^2,\,\sqrt{2}q_1 q_2\right) \\ &= p_1 q_1 + p_2 q_2 + 2p_1 q_1 p_2 q_2 \\ &= \left(p_1 q_1 + p_2 q_2\right)^2 \end{aligned}$$

即

$$\phi(p) \cdot \phi(q) = (p \cdot q)^2$$