• 数据驱动方法
• KNN算法
• 线性分类

一种实现方式是「硬编码」：先获取猫图像的边缘得到一些线条，然后定义规则比如三条线交叉是耳朵之类。然而这种方式的识别效果不好，并且不能识别新的物体。

我们会采用数据驱动算法：不具体写出识别每个物体对应的规则，而是针对每一类物体，找到大量样例图片，灌给计算机进行机器学习，归纳模式规律，生成一个分类器模型，总结出区分不同类物体的核心知识要素，然后用训练好的模型，识别新的图像。

数据驱动算法过程如下：

• 输入：输入是包含 N N N 个图像的集合，每个图像的标签是 K K K 种分类标签中的一种。这个集合称为训练集。
• 学习：这一步的任务是使用训练集来学习每个类的模式规律。一般该步骤叫做分类器训练或者模型学习。
• 评价：让分类器对它未曾见过的图像进行分类，把分类器预测的标签和图像真正的分类标签 （基本事实) 对比，并以此来评价分类器的质量。

本部分内容也可以参考ShowMeAI的 图解机器学习教程 中的文章详解 KNN算法及其应用

我们这里介绍第1个分类器算法：最近邻算法。训练过程只是简单的记住图像数据和标签，预测的时候和训练数据中图片比较找出最接近的输出标签。这个分类器和卷积神经网络没有任何关系，实际中也极少使用，但通过实现它，可以对解决图像分类问题的方法有个基本认识。

CIFAR-10 是一个非常流行的图像分类数据集。这个数据集包含 10 种分类标签，60000 张 32 × 32 32 \times 32 32×32 的小图像，每张图片含有一个标签。这 60000 张图像被分为包含 50000 张（每种分类 5000 张）图像的训练集和包含 10000 张图像的测试集。

假设现在我们用这 50000 张图片作为训练集，将余下的 10000 作为测试集并打上标签，Nearest Neighbor 算法将会拿着测试图片和训练集中每一张图片去比较，然后将它认为最相似的那个训练集图片的标签赋给这张测试图片。

结果如下图所示，效果并不是特别好。

• 左边：CIFAR-10 数据库的样本图像；
• 右边：第一列是测试图像，后面是使用Nearest Neighbor算法，根据像素差异，从训练集中选出的10张最类似的图片

那么具体如何比较两张图片呢？我们有一些距离度量计算方法，下面展开介绍一下。

距离度量的数学知识也可以参考ShowMeAI的系列教程 图解AI数学基础 中的文章 线性代数与矩阵论 对各种距离度量的展开讲解

在本例中，就是比较 32 × 32 × 3 32 \times 32 \times 3 32×32×3 的像素块。最简单的方法就是逐个像素比较，最后将差异值全部加起来。即将两张图片先转化为两个向量 I 1 I_{1} I1​ 和 I 2 I_{2} I2​，然后计算他们的 L1 距离：

d 1 ( I 1 , I 2 ) = ∑ p ∣ I 1 p − I 2 p ∣ d_{1} (I_{1} ,I_{2} )=\sum_{p}\vert I_{1}^p -I_{2}^p \vert d1​(I1​,I2​)=p∑​∣I1p​−I2p​∣

• 其中 p p p 为像素点， I p I^p Ip 表示第 p p p 个像素点的值。
• 两张图片使用 L1 距离来进行比较，即逐个像素求差值，然后将所有差值加起来得到一个数值。如果两张图片一模一样，那么 L1 距离为 0 0 0；但是如果两张图片很是不同，那 L1 值将会非常大。

下图是仅一个RGB通道的 4 × 4 4 \times 4 4×4 图片计算 L1 距离。

下面看具体编程如何实现：

① 首先，我们将 CIFAR-10 的数据加载到内存中，并分成4个数组：训练数据和标签，测试数据和标签。

Xtr, Ytr, Xte, Yte = load_CIFAR10('data/cifar10/') # 这个函数可以加载CIFAR10的数据
# Xtr是一个50000x32x32x3的数组，一共50000个数据，
# 每条数据都是32行32列的数组，数组每个元素都是一个三维数组，表示RGB。
# Xte是一个10000x32x32x3的数组；
# Ytr是一个长度为50000的一维数组，Yte是一个长度为10000的一维数组。
Xtr_rows = Xtr.reshape(Xtr.shape[0], 32 * 32 * 3) 
# Xtr_rows是50000x3072的数组，按每个像素点排列，每个像素点有三个值。
Xte_rows = Xte.reshape(Xte.shape[0], 32 * 32 * 3) 
# Xte_rows是10000x3072的数组
''' shape会返回数组的行和列数元组：（行数，列数），shape[0]表示行数, Xtr.shape[0]会返回50000；Xtr.shape会返回（50000，32，32，3） Xtr.reshape(50000，3072)会将Xtr 重构成50000x3072数组，等于 np.reshape(Xtr, (50000,3072))'''

• Xtr（大小是50000x32x32x3）存有训练集中所有的图像
• Xte（大小是10000x3072）存有测试集中所有的图像
• Ytr 是对应的长度为50000的1维数组，存有图像对应的分类标签（从0到9）
• Yte 对应长度为10000的1维数组

现在我们得到所有的图像数据，每张图片对应一个长度为 3072 的行向量。

② 接下来训练一个分类器并评估效果。我们常常使用准确率作为评价标准，它描述了我们预测正确的得分。

本例中OK，很多其他应用中准确率并不一定是最佳的评估准则，可以参考ShowMeAI的 图解机器学习教程 中的文章详解 模型评估方法与准则

nn = NearestNeighbor() # 创建一个最邻近分类器对象
nn.train(Xtr_rows, Ytr) # 用训练图片数据和标签训练分类器
Yte_predict = nn.predict(Xte_rows) # 预测测试图片的标签
# 并输出预测准确率，是一个平均值
print 'accuracy: %f' % ( np.mean(Yte_predict == Yte) )

• 请注意以后我们实现的所有分类器都需要有这个接口函数（API）：train(X, y) 函数。该函数使用训练集的数据和标签来进行训练。
• 从其内部来看，类应该实现一些关于标签和标签如何被预测的模型。这里还有个 predict(X) 函数，它的作用是预测输入的新数据的分类标签。

下面就是使用 L1 距离的 Nearest Neighbor 分类器的实现：

import numpy as np

class NearestNeighbor(object):
  def __init__(self):
    pass

  def train(self, X, y):
    """ X 是 NxD 维的数组，每一行都是一个样本，比如一张图片，D 是样本的数据维度； Y 是长度为 N 的一维数组。"""
    # 最邻近分类器只是简单的记住所有的训练数据
    self.Xtr = X
    self.ytr = y

  def predict(self, X):
    """ X 是 NxD 维的数组，每一行都是一个希望预测其标签的样本 """
    num_test = X.shape[0]
    # 确保输出的标签数据类型和输入的标签格式一致，长度是测试样本数
    Ypred = np.zeros(num_test, dtype = self.ytr.dtype)

    # 循环所有测试样本数，即测试数组的行数
    for i in range(num_test):
      # 为第 i 张测试图片找到最接近的训练图片
      # 使用 L1 距离 (差值的绝对值求和)
      '''self.Xtr - X[i,:] 利用传播机制，求测试集第 i 张图片对应的行向量和 训练集所有图片行向量的差值，得到一个一个50000x3072的差值矩阵； abs(self.Xtr - X[i,:] )会将矩阵所有元素求绝对值； 然后axis = 1 会对差值矩阵按行求和，最终得到一个长度为50000的一维 数组，存放第 i 张图片和训练集所有50000张图片的 L1 距离。'''
      distances = np.sum(np.abs(self.Xtr - X[i,:]), axis = 1)
      min_index = np.argmin(distances) # 获取距离最小的训练集图片索引
      Ypred[i] = self.ytr[min_index] # 预测第 i 张测试集图片的标签时与其最接近的训练集图片索引

    return Ypred

这段代码的训练时间复杂度为 O ( 1 ) O(1) O(1)，因为只是简单的存储数据，不管数据多大，都是一个相对固定的时间；如果训练集有 N N N 个样本，则预测时间复杂度为 O ( N ) O(N) O(N)，因为测试图片要和训练集每张图片进行比较。

这是一个不太好的分类器，实际对分类器的要求是，我们希望它预测的时候要快，训练的时候可以慢。

这段代码跑 CIFAR-10，准确率能达到 38.6 % 38.6\% 38.6%。这比随机猜测的 10 % 10\% 10% 要好，但是比人类识别的水平和卷积神经网络能达到的 95 % 95\% 95% 还是差很多。

距离度量的数学知识也可以参考ShowMeAI的系列教程图解AI数学基础中的文章线性代数与矩阵论对各种距离度量的展开讲解

另一个常用的方法是 L2 距离，从几何学的角度，可以理解为它在计算两个向量间的欧式距离。L2 距离的公式如下：

d 2 ( I 1 , I 2 ) = ∑ p ( I 1 p − I 2 p ) 2 d_{2} (I_{1},I_{2})=\sqrt{\sum_{p}(I_{1}^p - I_{2}^p )^2 } d2​(I1​,I2​)=p∑​(I1p​−I2p​)2 ​

• 依旧是在计算像素间的差值，只是先求差值的平方，然后把这些平方全部加起来，最后对这个和开方。

此时的代码只需改动计算距离差异的一行：

distances = np.sqrt(np.sum(np.square(self.Xtr - X[i,:]), axis = 1))
'''np.square(self.Xtr - X[i,:]) 会对差值矩阵的每一个元素求平方'''

注意在这里使用了 np.sqrt，但是在实际中可能不用。因为对不同距离的绝对值求平方根虽然改变了数值大小，但依然保持了不同距离大小的顺序。这个模型，正确率是 35.4 % 35.4\% 35.4%，比刚才低了一点。

在 L1 距离更依赖于坐标轴的选定，坐标轴选择不同 L1 距离也会跟着变化，判定的数据归类的边界会更趋向于贴近坐标系的轴来分割所属区域，而 L2 的话相对来说与坐标系的关联度没那么大，会形成一个圆，不跟随坐标轴变化。

在面对两个向量之间的差异时，L2比 L1 更加不能容忍这些差异。也就是说，相对于1个巨大的差异，L2 距离更倾向于接受多个中等程度的差异（因为会把差值平方）。

L1 和 L2 都是在 p-norm 常用的特殊形式。

当图像中有特别在意的特征时可以选择 L1 距离；当对图像中所有元素未知时，L2距离会更自然一些。最好的方式是两种距离都尝试，然后找出最好的那一个。

本部分内容也可以参考ShowMeAI的图解机器学习教程中的文章详解KNN算法及其应用

只用最相似的 1 张图片的标签来作为测试图像的标签，有时候会因为参照不够多而效果不好，我们可以使用 k-Nearest Neighbor 分类器。KNN的思想是：找最相似的 k k k 个图片的标签， k k k 中数量最多的标签作为对测试图片的预测。

当 k = 1 k=1 k=1 的时候，k-Nearest Neighbor 分类器就是上面所说的最邻近分类器。

如下图所示，例子使用了2维的点来表示图片，分成3类（红、绿、蓝）。不同颜色区域代表的是使用 L2距离的分类器的决策边界。

上面示例展示了NN分类器和KNN（ k = 5 k=5 k=5）分类器的区别。从直观感受上就可以看到，更高的 k k k 值可以让分类的效果更平滑，使得分类器对于异常值更有抵抗力。

• 在 k = 1 k=1 k=1 时，异常的数据点（比如：在蓝色区域中的绿点）制造出一个不正确预测的孤岛。
• 在 k = 5 k=5 k=5 时分类器将这些不规则都平滑了，使得它针对测试数据的**泛化（generalization）**能力更好。
  • 注意，5-NN 中也存在一些白色区域，这些区域是因为5个近邻标签中的最高数相同导致的分类模糊（即图像与两个以上的分类标签绑定）。
  • 比如：2 个邻居是红色，2 个邻居是蓝色，还有 1 个是绿色，所以无法判定是红色还是蓝色。

模型调优，超参数的实验选择方法也可以参考ShowMeAI的文章 图解机器学习 | 模型评估方法与准则 和 深度学习教程 | 网络优化：超参数调优、正则化、批归一化和程序框架

• KNN 分类器需要设定 k k k 值，如何选择 k k k 值最合适？
• L1 距离和 L2 距离选哪个比较好（还是使用其他的距离度量准则例如点积）？

所有这些选择，被称为超参数（hyperparameter）。在基于数据进行学习的机器学习算法设计中，超参数是很常见的。

超参数是需要提前设置的，设置完成后模型才可以训练学习，具体的设置方法通常要借助于实验，尝试不同的值，根据效果表现进行选择。

特别注意：不能使用测试集来进行调优。

• 如果使用测试集来调优，而且算法看起来效果不错，真正的危险在于：算法实际部署后，性能可能会远低于预期。这种情况，称之为算法对测试集过拟合。

• 大家可以理解为，如果使用测试集来调优，实际上就是把测试集当做训练集，由测试集训练出来的算法再预测测试集，性能自然会看起来很好，但实际部署起来效果就会差很多。

• 最终测试的时候再使用测试集，可以很好地近似度量分类器的泛化性能。

测试数据集只能使用一次，而且是在训练完成后评价最终模型时使用，不可用来调优！

从训练集中取出一部分数据用来调优，称之为 验证集（validation set）。以 CIFAR-10 为例，可以用 49000 个图像作为训练集，用 1000 个图像作为验证集。验证集其实就是作为假的测试集来调优。

代码如下：

# 假设 Xtr_rows, Ytr, Xte_rows, Yte 还是和之前一样
# Xtr_rows 是 50,000 x 3072 的矩阵
Xval_rows = Xtr_rows[:1000, :] # 取前 1000 个训练集样本作为验证集
Yval = Ytr[:1000]
Xtr_rows = Xtr_rows[1000:, :] # 剩下的 49,000 个作为训练集
Ytr = Ytr[1000:]

# 找出在验证集表现最好的超参数 k 
validation_accuracies = []
for k in [1, 3, 5, 10, 20, 50, 100]:
  # 使用一个明确的 k 值评估验证集
  nn = NearestNeighbor()
  nn.train(Xtr_rows, Ytr)
  # 这里假设一个修正过的 NearestNeighbor 类，可以把 k 值作为参数输入
  Yval_predict = nn.predict(Xval_rows, k = k)
  acc = np.mean(Yval_predict == Yval)
  print 'accuracy: %f' % (acc,)

  # 把每个 k 值和相应的准确率保存起来
  validation_accuracies.append((k, acc))

程序结束后，作图分析出哪个 k k k 值表现最好，然后用这个 k k k 值来跑真正的测试集，并作出对算法的评价。

训练集数量较小（因此验证集的数量更小）时，可以使用交叉验证的方法。还是用刚才的例子，如果是交叉验证集，我们就不是取 1000 个图像，而是将训练集平均分成 5 份，每份 10000 张图片，其中4份用来训练，1份用来验证。然后我们循环着取其中4份来训练，其中1份来验证，最后取所有5次验证结果的平均值作为算法验证结果。

下面是 5 份交叉验证对 k k k 值调优的例子。针对每个 k k k 值，得到 5 次验证的准确率结果，取其平均值，然后对不同 k k k 值的平均表现画线连接。

上图可以看出，本例中，当 k = 7 k=7 k=7 的时算法表现最好（对应图中的准确率峰值）。如果我们将训练集分成更多份数，直线一般会更加平滑（噪音更少）。

实际情况下，深度学习不会使用交叉验证，主要是因为它会耗费较多的计算资源。一般直接把训练集按照 50 % ∼ 90 % 50\% \sim 90\% 50%∼90% 的比例分成训练集和验证集。但是训练集数量不多时可以使用交叉验证，一般都是分成3、5和10份。

① 易于理解，实现简单。 ② 算法的训练不需要花时间，因为其训练过程只是将训练集数据存储起来。

① 测试要花费大量时间

• 因为每个测试图像需要和所有存储的训练图像进行比较在实际应用中，关注测试效率远远高于训练效率；

② 使用像素差异来比较图像是不够的，图片间 L2 距离小，更多的是被背景主导而不是图片语义内容本身主导，往往背景相似图片的 L2 距离就会小。

• 也就是说，在高维度数据上，基于像素的相似和基于感官上的相似非常不同。感官上不同的两张图片，可能有相同的 L2 距离。

③ 维度灾难

• KNN 有点像训练数据把样本空间分成几块，我们需要训练数据密集的分布在样本空间里，否则测试图