cs231n之KNN算法

1.环境搭建以及前置条件

• 1.前置环境：
  • 1.mac
  • 2.pycharm
  • 3.python3
  • 4.Anaconda
• 2.环境搭建：
  • 1.官网下载并安装Anaconda
  • 2.官网下载并安装pycharm
  • 3.在pycharm中使用Anaconda
    • 1.preference-->project-->project interpreter
    • 2.将Anaconda的解释器当做一个project interpreter添加
  • 4.下载assignment1作业项目并导入pycharm中， 作业下载 。
  • 5.下载数据集并解压到assignment1作业项目的 assignment1/cs231n/datasets/中。 数据集下载
  • 6.执行数据集中的.sh文件使得数据集可用
• 3.前置知识：numpy、python、SciPy基础学习， 教程

2.KNN知识了解

1.两张图片的图片距离

对于两张图片来说我们如何量化这两张图片的相似度呢？计算机科学家给出了两个简单的方法：曼哈顿距离和欧氏距离

• 1.L1距离（曼哈顿距离）：给定两张 32*32 像素的图片i1和i2，那么可以将其看做两个 32*32 的矩阵。公式：
  曼哈顿距离公式

  解释：两个矩阵相减之后，再对该矩阵的所有值取绝对值，最后将该矩阵所有值相加。最后得出的值就是两张图片的距离。

• 2.L2距离（欧氏距离）：还是给定两张 32*32 像素的图片i1和i2，将这两张图片一维化，即拉伸成一个1024*1的矩阵。公式：
  欧式距离公式
  
  
  解释：在一个二维的坐标系中A(x1 , y1),B(x2 , y2)这两点的距离公式是：
  二维欧氏公式
  ，那么这两个矩阵的距离就可以推广为在一个1024维的坐标系上两点的距离

2.KNN的基本思想

从1中我们可以根据公式计算出两张图片的相似度在接下来设为 A ，我们再假设我们有 n 张可供训练的图片每张图片被称为 Tn ，对于训练图片我们都知道该图片到底属于哪个种类的图片，如猫、狗等，所以这里设第 Tn 张图片的种类为 CTn 。然后有 m 张可供测试的图片，每张图片被称为 Cm ，对于测试图片我们也知道该图片到底属于哪个种类，所以这里设第 Cm 张图片的种类为 CCm 。那么某张测试图片和某张训练图片的相似度就可以被称为 Anm 。

• 1.对于某一 Cm 来说，我们需要与每一 Tn 进行相似度计算，此时对于该 Cm 来说就有 n 个 Anm 。
• 2.从1中的 n 个 Anm 中取出k个最小值，这里的意思为为 Cm 找出最相似的 k 张图片。此时获取的 Anm 我们称为 Akm 。
• 3.因为我们知道每个 Tn 的种类，所以此时我们为 Cm 找到了 k 个 CTn ，也就是与该图片最相似的 k 个种类
• 4.由于 Cm 的 k 个 CTn 中可能会有重复的种类，所以我们要对这 k 个种类进行统计，最终找出数量最多的种类，此时这个种类就是我们预测该图片的种类，这里我们记该种类为 CmCTn 。
• 5.上面1-4我们只是对某一张测试图片进行了预测，接下来我们就按照上面的操作，对所有测试图片进行同样的操作，此时我们就能获取到 m 个 CmCTn 。
• 6.最后就是计算KNN的准确率了，因为我们知道每个 Cm 的种类，所以可以判断出 m 个 CmCTn 中哪些是预测正确的，哪些是预测错误的，继而算出KNN的准确率

3.KNN代码

1.我的项目

• 1.先上一个github吧，会持续更新直到把cs231n课程学习完： cs231n

• 2.我的项目目录：
  项目目录

2.代码解析

展示一下整体的KNN算法流程等等会按照这个图中代码一行行向下讲，建议结合github上面的代码食用更佳。

KNN算法

• 1.导入几个常见的和我定义模块： numpy、pyplot、load_cifar10 （我写的读取文件用的）、 KNearestNeighbor （KNN的具体算法）
• 2.通过 load_cifar10 获取到数据，我定义一个cs231n/classifiers/data_util.py的文件用来作为数据读取工具类。
  data_util
  • 1.我们从 load_cifar10 这个方法讲起：先定义了两个数组 xs 和 ys
  • 2.进入一个循环，从我的目录截图我们可以看见，数据文件的命名是 data_batch_？ ，后面的问号表示1-5.
    • 1.先获取到某个数据文件名
    • 2.将文件传入到 load_cifar_batch 方法中去从中获取数据
      • 1.打开该文件
      • 2.使用 pickle 库将文件以字节流的形式读入内存，并且反序列化成 numpy 的对象
      • 3.定义 x,y 分别为 numpy 的图片矩阵数组 和 numpy 的图片类型数组，每张图片都对应着一个图片类型，如猫、狗等等
      • 4.将 x 图片矩阵数组重新展开成，10000张图片每张图片为32*32*3像素。
      • 5.将 y 展开成与 x 中10000张图片一一对应的图片类型
      • 6.返回 x，y
    • 3.获取到某个文件中的全部图片矩阵数组和全部图片类型数组之后，将其放入前面数组中，就这样一直循环，直到所有的文件数据都被放入到数组中
  • 3.将 xs和ys 这连个数组平铺，也就是最后获取到了 50000张32*32*3像素的图片和对应图片的类型。
  • 4.将测试数据，进行上面一样的操作，最后返回获取到的数据
• 2.展示一下数据的信息，看看读取是否有问题
• 3.定义训练图片数量 num_training ，这里大家可以减少一些从而减少训练所需时间
• 4.获取到 mask 这个数值 num_training 的范围，然后获取到具体需要的训练图片数量和对应图片类型 x_train 和 y_train
• 5.定义测试图片的数量 num_test ，同理获取具体的 x_test 和 y_test
• 6.将测试图片和训练图片降维，例如把原来10000*32*32*3的矩阵伸张成10000*3072的矩阵，也就是将每张图片平铺成一个一维数组，这样在后面计算的时候更加方便。
• 7.定义一个KNN的分类器 classifier ，将 x_train,y_train 放入其中，等等接下来的训练
• 8.前面我们在KNN的基本思想中提到了，对于一张测试图片来说，我们计算了其与全部测试图片的距离，然后会取出前k个距离最小的图片，所以这里我们定义了一个k从1-10的数组，称为 ks .
• 9.定义一个 num_correct 数组，用来储存在不同的k下，正确预测的测试图片数量
• 10.定义一个 accuracy 数组，用来储存在不同的k下，预测成功的概率
• 11.进入一个循环，循环在不同的k下的结果

  • 1.用上了前面定义的分类器，传入测试图片集和当前的k：
    预测图片结果
    • 1.这里有三种不同的方式来计算图片的L2距离，我们这里讲解比较简单的一种，方便读者了解。当 num_loops=2 的时候就是我们要讲的方法：
      两次循环计算L2距离
      • 1.先获取测试图片的数量 num_test ，再获取训练图片的数量 num_train
      • 2.建立一个 num_test*num_train 大的矩阵 dists ，用来储存接下来计算出的L2距离
      • 3.两层循环嵌套以然后用前面说到的公式计算L2距离，然后将结果储存到对应的 dists 中
      • 4.将 dists 返回
    • 2.获取到了L2距离矩阵之后，将其与k传入 predict_labels 方法中，用来获取每张测试图片的预测图片种类：
      获取预测的图片种类
      • 1.获取到测试图片的数量 num_test
      • 2.定义一个 num_test 大的数组 y_pred 用于储存预测图片种类结果
      • 3.进入循环中
        • 1.先在dists中对第i张测试图片的全部L2距离进行从小到大排序，获得了数组 y_indicies
        • 2.截取前k个第i张测试图片的L2距离，得到了 closest_y
        • 3.最后找到第i张测试图片的 closest_y 中数量最多的图片类别，存入 y_pred 中。
      • 4.返回预测的结果数组
  • 2.回到初始调用的地方，此时我们已经获取了在当前的k下，全部的测试图片的预测结果。将预测结果与实际结果进行比较，获取到了预测成功的数量 num 。
  • 3.向 num_correct 中添加当前的结果，向 accuracy 添加当前的准确率
• 12.以k为自变量， accuracy 为因变量，绘制出曲线并寻找在k为多少的时候，预测的准确率最高。