最近邻分类器、L1与L2距离

客官°小女子只卖身不卖艺 2023-07-14 13:57 9阅读 0赞

# ![20191009191333910.png][][日萌社][Link 1] #

[人工智能AI：Keras PyTorch MXNet TensorFlow PaddlePaddle 深度学习实战（不定时更新）][AI_Keras PyTorch MXNet TensorFlow PaddlePaddle]

--------------------

# 2.1 图像分类介绍 #

### 2.1.1 图像分类 ###

*  任务目的：对输入的图像赋予一个标签，这个标签在指定类别集合中。

下面这个例子中，图像分类模型拍摄一张图像并将概率分配给4个标签\{cat，dog，hat，mug\}。如图所示，请记住，对于计算机而言，图像表示为一个大型3维数字数组。在此示例中，猫图像的宽度为248像素，高度为400像素，并具有红色，绿色，蓝色（简称RGB）三个颜色通道。因此，图像由248 x 400 x 3个数字或总共297,600个数字组成。每个数字都是一个整数，范围是0（黑色）到255（白色）。我们的任务是将这一百万分之一的数字变成一个单独的标签，例如*“ cat”*。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ppbWlhbzU1MjE0NzU3Mg_size_16_color_FFFFFF_t_70][]

> 图像分类的任务是预测给定图像的单个标签（或标签上的分布，如图所示，以表示我们的可信度）。图像是0到255之间的三维整数数组，大小为宽x高x 3。3表示红色、绿色、蓝色三个颜色通道。

2.1.1.1 挑战：

由于识别视觉概念的任务对人类来说相对来说是微不足道的，因此从计算机视觉算法的角度考虑所涉及的挑战存在并且具有价值的。图像的原始表示为亮度值的三维数组：

*  **Viewpoint variation**：单个物体从不同的角度照出来的图像
 *  **Scale variation**：展现出的图像大小会变化
 *  **Deformation**：许多物体的边缘可以形成不同的形状形式
 *  **Occlusion**：关注的某个物体会被遮挡，只有一小部分会被显示出来
 *  **Illumination conditions**: 光照对像素级的影响很大
 *  **Background clutter**: 感兴趣的物体与环境融合，很难进行区分
 *  **Intra-class variation**: 物体的类别非常广泛相近，例如椅子，这些对象有许多不同的类型，每个都有自己的外观

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ppbWlhbzU1MjE0NzU3Mg_size_16_color_FFFFFF_t_70 1][]

所以一个好的图像分类模型必须解决上述问题，对各种变化的交叉存在具有敏感性。

### 2.1.2 近邻分类器 ###

首先我们将介绍一个最近邻分类的方法，虽然这个方法没有用到深度学习的方法，并且也很少在实践中使用。但是能够给我们提供一个去解决图像分类问题的基础思路。

*  数据驱动方式

如何编写一个算法进行将一个张图片分类到具体一个类别，会给计算机提供每个类别的很多样本，然后使用算法去学习这些样本学习每个类别的视觉特点。这样的方式依赖于大量的指定类别的训练数据。如下所示

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ppbWlhbzU1MjE0NzU3Mg_size_16_color_FFFFFF_t_70 2][]

### 2.1.2.1 CIFAR-10例子介绍 ###

图像分类数据集示例：CIFAR-10，一个流行的图像分类数据集。这个数据集由60000个32像素高和宽组成的小图像组成。每个图像都被标记为10个类之一（例如“飞机、汽车、鸟等”）。这60000个图像被分割成50000个图像的训练集和10000个图像的测试集。在下图中，您可以看到10个类中每个类的10个随机示例图像：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ppbWlhbzU1MjE0NzU3Mg_size_16_color_FFFFFF_t_70 3][]

上面图中就是数据集的类别和图像的示例，右边展示了一部分测试图像以及最相近的在训练集中前10张图片集合。

2.1.2.2 算法思路

假设现在我们得到了cifar-10训练集，它包含50000个图像（每个标签有5000个图像），我们希望标记预测剩下的10000个图像。

*  最近邻分类器将得到一个测试图像，将其与每个训练图像进行比较，并预测其标签，为最近的训练图像的标签。

在上面和右边的图像中，您可以看到10个示例测试图像的这种过程的示例结果。注意，在大约10个示例中，只有3个检索到同一类的图像，而在其他7个示例中则不是这样。例如，在第8排，离马头最近的训练图像是一辆红色的汽车，大概是由于强烈的黑色背景。因此，在这种情况下，马的图像会被错误地标记为汽车。

### 如何比较图像两张图片 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ppbWlhbzU1MjE0NzU3Mg_size_16_color_FFFFFF_t_70 4][]

distances = np.sum(np.abs(Xtrain - Xtest[i,:]), axis = 1)

设定输入的图片和标签形状为

Xtrain_rows = Xtrain.reshape(Xtrain.shape[0], 32 * 32 * 3) # Xtr_rows becomes 50000 x 3072
    Xtest_rows = Xtest.reshape(Xtest.shape[0], 32 * 32 * 3) # Xte_rows becomes 10000 x 3072

完整代码实现(Numpy)

import numpy as np
    
    class NearestNeighbor(object):
      def __init__(self):
        pass
    
      def train(self, X, y):
        """
        X：N x D形状，N为样本数，D为像素数量
        Y：1维，大小为N
        """
        # 所有最近邻需要的训练数据集
        self.Xtrain = X
        self.ytrain = y
    
      def predict(self, Xtest):
        """对输入的X若干个测试图片，每个进行预测"""
        num_test = Xtest.shape[0]
        # 确保输出类型一样
        Ypred = np.zeros(num_test, dtype = self.ytrain.dtype)
    
        # 循环所有测试数据
        for i in xrange(num_test):
          # 使用L1距离找到i最近的训练图片
          distances = np.sum(np.abs(self.Xtrain - Xtest[i,:]), axis = 1)
          min_index = np.argmin(distances)# 获取最近的距离的图像下标
          Ypred[i] = self.ytrain[min_index]# 预测标签（获取对应训练那张图片的目标标签）
        return Ypred

结果

使用上述方法，我们在CIFAR-10的测试机上面只能达到**38.6%** 的准确率，距离目前人类的测试结果（大概）94%的准确率，还有后面着重介绍的**state of the art（SOTA，前沿的）**的卷积神经网络取得的效果95%

距离选择

距离有很多种方式，在计算两个向量的距离时候，也可以选择L2，欧式距离。

![2020031419551254.png][]

只要去修改其中的距离计算即可

distances = np.sqrt(np.sum(np.square(Xtrain - Xtest[i,:]), axis = 1))

但是在实际的最近邻应用程序中，我们可以省略平方根操作，因为平方根是单调函数。缩放距离的绝对大小，因此有或没有顺序的最近邻是相同的。如果您使用L2距离在cifar-10上运行最近邻分类器，将获得35.4%的精度（略低于L1距离结果）。

L1和L2哪个好，没有明确的方法，具体问题具体分析，不断尝试

### 2.1.3 近邻分类器的优缺点 ###

*  **优点是实现和理解起来非常简单。此外，分类器不需要时间进行训练，因为所需的只是存储并可能索引训练数据。**
 *  **缺点是我们在测试时候的计算成本，因为对测试示例进行分类需要与每个单独的训练示例进行比较。这是向后的，因为在实践中，我们通常更关心测试时间的效率，而不是训练时间的效率。**
    
     *  利用L1和L2进行距离测量不适合描述图片的相似度，不适合描述图片在视觉感知上的差异
     *  测试太慢
     *  维数灾难

注：最近邻分类器的计算复杂度是非常值得研究的领域，现有的几种近似最近邻（ann）算法和库可以加速数据集中的最近邻查找。这些算法允许在检索过程中权衡最近邻检索的正确性和其空间/时间复杂性，并且通常依赖于涉及构建kdtree或运行k-means算法的预处理/索引阶段。在某些情况下（尤其是在数据低维的情况下），最近邻分类器有时可能是一个不错的选择，但它很少适用于实际的图像分类设置。一个问题是，图像是高维对象，高维空间上的距离可能非常反直观。

*  存在问题：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ppbWlhbzU1MjE0NzU3Mg_size_16_color_FFFFFF_t_70 5][]

基于高维数据（尤其是图像）的像素距离可能非常不直观。上述原始图像（左）和它旁边的其他三个图像，根据L2像素距离，三个变化后的图像都离原始图像同样远。显然，像素级的距离根本不符合图像的语义相似性。

后面我们回去解决这些问题，并最终得出90%以上准确率的解决方案，允许我们在学习完成后完全放弃训练集，让我们在不到一毫秒的时间内评估测试图像。

### 2.1.4 总结 ###

*  图像分类任务引入以及挑战
 *  最近邻分类器
 *  L1与L2距离在图像距离的计算和存在的问题

[20191009191333910.png]: /images/20230529/bb992e471e834ccaaf0f578595a5c4bc.png
[Link 1]: http://www.rimengshe.com/
[AI_Keras PyTorch MXNet TensorFlow PaddlePaddle]: https://blog.csdn.net/zimiao552147572/article/details/88867161
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ppbWlhbzU1MjE0NzU3Mg_size_16_color_FFFFFF_t_70]: /images/20230529/4b0b7b6fb0214b248e078d8ca721c5ea.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ppbWlhbzU1MjE0NzU3Mg_size_16_color_FFFFFF_t_70 1]: /images/20230529/89cb0aee9a504656b81baef9df1ed7ea.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ppbWlhbzU1MjE0NzU3Mg_size_16_color_FFFFFF_t_70 2]: /images/20230529/2a95323727404760b9f841ce91835f8d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ppbWlhbzU1MjE0NzU3Mg_size_16_color_FFFFFF_t_70 3]: /images/20230529/b182fdc717f64103934c4160913dc666.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ppbWlhbzU1MjE0NzU3Mg_size_16_color_FFFFFF_t_70 4]: /images/20230529/29d1269832aa4862bb7e3164d8bf6b4a.png
[2020031419551254.png]: /images/20230529/8634828860424660b7b11ba4fdb9179e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ppbWlhbzU1MjE0NzU3Mg_size_16_color_FFFFFF_t_70 5]: /images/20230529/6906432f1bb04d7f9bcdbefafc8afc96.png