图像分类 Image Classification

原文链接：http://cs231n.github.io/classification/

Example示例
例如，在下面的图像中，图像分类模型采用一张图像，并将概率分配给4个标签{ cat，dog，hat，mug }。 如图所示，对于计算机来说，图像是由一个大型的三维数组表示的。 在本例中，猫图像宽248像素，高400像素，有三个颜色通道 Red、 Green、 Blue (简称 RGB)。 因此，图像由248 x 400 x 3个数字组成，即总共297,600个数字。 每个数字都是一个从0(黑色)到255(白色)的整数。 我们的任务是把这25万个数字变成一个单一的标签，比如“猫”。

图像分类的任务是为给定的图像预测单个标签(或标签上的分布，如图所示)。 图像是由0到255的整数组成的三维数组，大小为宽度 x 高度 x 3。 3代表红、绿、蓝三色通道

Challenges. 挑战

由于识别一个视觉概念(比如猫)对于人类来说相对一些挑战时，请记住图像的原始表示为亮度值的3d 数组）:

Viewpoint variation.视点变化
对于摄像机来说，一个对象的单个实例可以通过多种方式进行导向。

Scale variation.尺度变化
视觉类经常显示其大小的变化（在现实世界中的大小，而不仅仅是其在图像中的范围）

Deformation.变形
许多感兴趣的物体不是刚体，可以在极端的方式下变形。

Occlusion.
感兴趣物体可以被遮挡。有时只能看到对象的一小部分（只有很少的像素）

Illumination conditions.光照条件
光照对像素级别的影响是剧烈的。

Background clutter.背景杂乱
感兴趣物体可能会融入他们的环境，使得他们难以识别。

Intra-class variation.类内变异
兴趣类别通常比较广泛，比如“椅子”。有许多不同类型的对象，每个都有自己的外观。

一个好的图像分类模型必须对所有这些变化的叉积保持不变，同时保持类间变化的敏感性。

##########################################################

Data-driven approach 数据驱动方法

向计算机提供每个类别的许多例子，然后开发学习算法，观察这些例子并了解每个类别的视觉外观。 这种方法被称为数据驱动的方法，因为它依赖于首先累积一个标记图像的训练数据集。 下面是一个数据集的一个例子:

四个视觉类别的示例训练集。在实际中，可能有成千上万的类别，每个类别有成千上万的图像。

The Image classification pipeline 图像分类管道

图像分类的任务是用一个像素数组表示单个图像，并为其分配标签。整个通道定义如下：
Input：输入有一组n个图像组成，每个图像都由K个不同的类别中的一个做为标签。将这些数据称为训练集（training set）
Learning：任务是利用训练集学习每个类别的样子。将这一步称为训练分类器或者学习模型。
Evaluation：最后，评估分类器的质量，要求它预测一组之前没有见过的新的图像。将这些图像的真实标签和分类器预测的标签进行比较。直观地说，希望大量的预测和真实答案是相吻合的（称之为基本事实ground truth）。

##########################################################

Nearest Neighbor Classifier 最近邻分类器

这种分类器与卷积神经网络没有任何关系，在实际应用中也很少使用，但它可以让我们对图像分类问题的基本方法有所了解。

图像分类示例数据集：CIFAR-10

这个数据集由60,000张高和宽都是32像素的小图片组成。 每个图像都被标记为10个类中的一个(例如“ airplane，automobile，bird，etc”)。 这60,000张图像被分割成一个包含50,000张图像的训练集和一个包含10,000张图像的测试集。 在下面的图片中，是来自10个类的10幅随机图片:

左边：CIFAR-10的示例图像。 右边: 第一列显示了一些测试图像，在每个图像的旁边，我们根据像素级别的差异显示了训练集中最近的10个邻居。

CIFAR-10：http://www.cs.toronto.edu/~kriz/cifar.html

假设现在得到了包含50,000张图像的 CIFAR-10训练集(每张标签有5,000张图像) ，希望标记其余的10,000张图像。 最近邻分类器将获取一个测试图像，将其与每一个训练图像进行比较，并预测最近训练图像的标签。 在上面的图片的右边的图像中，可以看到这个过程用于10个示例测试图像的示例结果。 注意，在10个示例中，只有3个检索到同一类的图像，而在其他7个示例中，情况并非如此。 例如，在第8行距离马头最近的训练图像是一辆红色的汽车，大概是由于强烈的黑色背景。 因此，在这种情况下，马的图像会被错误地贴上汽车的标签。

你可能已经注意到，我们没有具体说明如何比较两个图像，在本例中，这两个图像只是32 x 32 x 3的两个块。 最简单的方法之一就是逐个像素地比较图像，然后把所有的差异加起来。 换句话说，给定两幅图像并将它们表示为矢量 I1，I2，比较它们的合理选择可能是 L1距离（L1 distance）:

这里的求和是用所有像素来表示的，下面是可视化的过程：

使用像素级差异比较两个图像与 L1距离的例子(在这个例子中为一个颜色通道)。 分别减去两幅图像，然后将所有差异合计为一个数字。 如果两幅图像相同，则结果为零。 但是，如果图像非常不同，结果将是巨大的

如何在代码中实现分类器。 首先，将 CIFAR-10数据用4个数组加载到内存中: the training data/labels 和 the test data/labels。 在下面的代码中，Xtr (大小为50,000 x 32 x 32 x 3)保存训练集中的所有图像，相应的一维数组 Ytr (长度为50,000)保存训练标签(从0到9) :

Xtr, Ytr, Xte, Yte = load_CIFAR10('data/cifar10/') # a magic function we provide
# flatten out all images to be one-dimensional
Xtr_rows = Xtr.reshape(Xtr.shape[0], 32 * 32 * 3) # Xtr_rows becomes 50000 x 3072
Xte_rows = Xte.reshape(Xte.shape[0], 32 * 32 * 3) # Xte_rows becomes 10000 x 3072

现在已经将所有的图像延伸成行，下面是如何训练和评估分类器的方法:

nn = NearestNeighbor() # create a Nearest Neighbor classifier class
nn.train(Xtr_rows, Ytr) # train the classifier on the training images and labels
Yte_predict = nn.predict(Xte_rows) # predict labels on the test images
# and now print the classification accuracy, which is the average number
# of examples that are correctly predicted (i.e. label matches)
print 'accuracy: %f' % ( np.mean(Yte_predict == Yte) )

作为一个评估标准，使用精确度(accuracy)是很常见的，它度量了预测正确的比例。 请注意，我们将构建的所有分类器都满足这一个通用 API: 它们有一个 train (x，y)函数，该函数接受数据和标签以供学习。 在内部，类应该构建标签的某种模型，以及如何从数据中预测它们。 然后还有一个预测(x)函数，它接受新的数据并预测标签下面是一个简单的L1距离最近邻分类器的实现，它满足这个模板:

import numpy as np

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

  def train(self, X, y):
    """ X is N x D where each row is an example. Y is 1-dimension of size N """
    # the nearest neighbor classifier simply remembers all the training data
    self.Xtr = X
    self.ytr = y

  def predict(self, X):
    """ X is N x D where each row is an example we wish to predict label for """
    num_test = X.shape[0]
    # lets make sure that the output type matches the input type
    Ypred = np.zeros(num_test, dtype = self.ytr.dtype)

    # loop over all test rows
    for i in xrange(num_test):
      # find the nearest training image to the i'th test image
      # using the L1 distance (sum of absolute value differences)
      distances = np.sum(np.abs(self.Xtr - X[i,:]), axis = 1)
      min_index = np.argmin(distances) # get the index with smallest distance
      Ypred[i] = self.ytr[min_index] # predict the label of the nearest example

    return Ypred

如果运行这段代码，您将看到这个分类器只能在 CIFAR-10上达到38.6% 。 这比随机猜测准确(由于有10个类别，猜测的准确率为10%) ，但是远远不及人类的表现(估计约为94%)也没有接近最先进的卷积神经网络（达到95% 的准确率，与人类的准确率相当(参见最近在 CIFAR-10上举办的 Kaggle 竞赛的排行榜)）。

距离选择
计算向量之间的距离还有许多其他方法。 另一个常见的选择可能是使用L2距离，它具有计算两个向量之间的欧几里得度量的几何解释。 距离的形式是:

换句话说，我们将像以前一样计算像素差，但是这次我们将它们平方，加起来，最后得到平方根。 在 numpy 中，使用上面的代码只需要替换一行代码。 计算距离的那行:

distances = np.sqrt(np.sum(np.square(self.Xtr - X[i,:]), axis = 1))

请注意，在上面包含了 np.sqrt 调用，但在实际的最近邻应用程序中，可以省略平方根操作，因为平方根是单调函数。 也就是说，它缩放了距离的绝对大小，但保留了排序，因此有或没有排序的最近邻是相同的。 如果在 CIFAR-10上用这个距离运行最近邻分类器，将获得35.4% 的准确率(略低于 L1距离结果)。
L1 vs. L2. 考虑这两个指标之间的差异是很有趣的。 特别是，当涉及到两个矢量之间的差异时，L2距离比 L1距离更加无情。 也就是说，相对于一个大的分歧，L2距离更倾向于多个中等程度的分歧。 L1和 L2距离(或相当于一对图像之间差异的 L1 / L2范数)是 p 范数最常用的特殊情况。

Nearest Neighbor Classifier for CIFAR-10 完整代码

import pickle as p
import matplotlib.pyplot as plt
import numpy as np


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

    def train(self, X, y):
        """ X is N x D where each row is an example. Y is 1-dimension of size N """
        # the nearest neighbor classifier simply remembers all the training data
        self.Xtr = X
        self.ytr = y

    def predict(self, X):
        """ X is N x D where each row is an example we wish to predict label for """
        num_test = X.shape[0]
        # lets make sure that the output type matches the input type
        Ypred = np.zeros(num_test, dtype=self.ytr.dtype)

        # loop over all test rows
        for i in range(num_test):
            # find the nearest training image to the i'th test image
            # using the L1 distance (sum of absolute value differences)
            distances = np.sum(np.abs(self.Xtr - X[i, :]), axis=1)
            min_index = np.argmin(distances)  # get the index with smallest distance
            Ypred[i] = self.ytr[min_index]  # predict the label of the nearest example

        return Ypred


def load_CIFAR_batch(filename):
    """ load single batch of cifar """
    with open(filename, 'rb')as f:
        datadict = p.load(f, encoding='latin1')
        X = datadict['data']
        Y = datadict['labels']
        Y = np.array(Y)  # 字典里载入的Y是list类型，把它变成array类型
        return X, Y


def load_CIFAR_Labels(filename):
    with open(filename, 'rb') as f:
        label_names = p.load(f, encoding='latin1')
        names = label_names['label_names']
        return names
# load data
label_names = load_CIFAR_Labels("cifar-10-batches-py/batches.meta")
imgX1, imgY1 = load_CIFAR_batch("cifar-10-batches-py/data_batch_1")
imgX2, imgY2 = load_CIFAR_batch("cifar-10-batches-py/data_batch_2")
imgX3, imgY3 = load_CIFAR_batch("cifar-10-batches-py/data_batch_3")
imgX4, imgY4 = load_CIFAR_batch("cifar-10-batches-py/data_batch_4")
imgX5, imgY5 = load_CIFAR_batch("cifar-10-batches-py/data_batch_5")
Xte_rows, Yte = load_CIFAR_batch("cifar-10-batches-py/test_batch")

Xtr_rows = np.concatenate((imgX1, imgX2, imgX3, imgX4, imgX5))
Ytr_rows = np.concatenate((imgY1, imgY2, imgY3, imgY4, imgY5))

nn = NearestNeighbor()  # create a Nearest Neighbor classifier class
nn.train(Xtr_rows[:5000,:], Ytr_rows[:5000])  # train the classifier on the training images and labels
Yte_predict = nn.predict(Xte_rows[:1000,:])  # predict labels on the test images
# and now print the classification accuracy, which is the average number
# of examples that are correctly predicted (i.e. label matches)
# print(Yte_predict)
print('accuracy: %f' % (np.mean(Yte_predict == Yte[:1000]))) # Yte_predict==Yte时分类正确，求正确的概率

# show a picture
image=imgX1[9,0:1024].reshape(32,32)
print(image.shape)
plt.imshow(image)
plt.imshow(image,cmap=plt.cm.gray)
plt.axis('off')    #去除图片边上的坐标轴
plt.show()

##########################################################

K-Nearest Neighbor Classifier K-最近邻分类器

当进行预测时，只使用最近图像的标签是很奇怪的。 事实上，通过使用 k- 最近邻分类器，几乎总是可以做得更好。 这个想法非常简单: 不需要在训练集中找到最接近的图像，而是找到最接近的 k 个图像，然后让他们对测试图像的标签进行投票。 特别是，当 k=1时，恢复最近邻分类器。 直观上，k 值越高，分类器对异常值的抵抗能力就越强:

最近邻和5-最近邻分类器之间差异的示例，使用2维点和3个有色区域（红色，蓝色，绿色）显示由具有L2距离的分类器引起的**决策边界(decision boundaries)**。 白色区域显示模糊分类的点（即，类别投票与至少两个类别相关联）。 请注意，在最近邻分类器的情况下，异常数据点（例如蓝点云中间的绿点）会产生可能不正确预测的小岛，而5-最近邻分类器会平滑这些不规则性，可能会导致在测试数据上更好的泛化（未显示）。 还要注意，5-NN图像中的灰色区域是由最近邻居之间的投票关系引起的（例如，2个邻居是红色，接下来的两个邻居是蓝色，最后一个邻居是绿色）。

k的值如何选择呢？ 接下来我们谈谈这个问题。

Validation sets for Hyperparameter tuning 用于超参数调优的验证集

K-最近邻分类器需要 k 的设置。 但是什么数字最有效呢？ 此外，有许多不同的距离函数，可以使用: L1标准，L2标准，还有许多其他的选择，甚至还没有考虑(如点积)。 这些选择被称为超参数(hyperparameters)，它们经常出现在许多从数据中学习的机器学习算法的设计中。 应该选择什么样的值 / 设置通常并不明显。

你可能会建议尝试许多不同的值，看看哪个最有效。这是一个好主意，这确实是我们将要做的，但这必须非常小心。特别是，不能使用测试集来调整超参数。每当设计机器学习算法时，应该把测试集看作是一个非常宝贵的资源，理想情况下，直到最后一次才接触到它。否则，真正的危险是。调整后的超参数能过很好的在测试集上工作，但是当要部署模型时，可能会看到性能显著降低。在实践中，称作过拟合测试集。另一种看法是，如果在测试集上调整超参数，那么相当于把测试集当作训练集，因此，在部署模型时，其上实现的性能对于实际观察到的内容会过于乐观。但是如果只在最后使用一次测试集，它仍然是衡量分类器泛化(generalization)的一个很好的代理。

⚠️Evaluate on the test set only a single time, at the very end.
在测试集上只评估一次，在最后一次。

K-Nearest Neighbor Classifier for CIFAR-10 完整代码

import pickle as p
import matplotlib.pyplot as plt
import numpy as np


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

    def train(self, X, y):
        """ X is N x D where each row is an example. Y is 1-dimension of size N """
        # the nearest neighbor classifier simply remembers all the training data
        self.Xtr = X
        self.ytr = y

    def predict(self, X):
        """ X is N x D where each row is an example we wish to predict label for """
        num_test = X.shape[0]
        # lets make sure that the output type matches the input type
        Ypred = np.zeros(num_test, dtype=self.ytr.dtype)

        # loop over all test rows
        for i in range(num_test):
            # find the nearest training image to the i'th test image
            # using the L1 distance (sum of absolute value differences)
            distances = np.sum(np.abs(self.Xtr - X[i, :]), axis=1)
            sort_id = distances.argsort()
            # min_index = np.argmin(distances)  # get the index with smallest distance
            # print(min_index)
            dic = {}
            for j in range(20):
                vlable = self.ytr[sort_id[j]]  # 为对应的标签记数
                dic[vlable] = dic.get(vlable, 0) + 1
                # 寻找vlable代表的标签，如果没有返回0并加一，如果已经存在返回改键值对应的值并加一
            max = 0
            # print(dic.items())
            for index, v in dic.items():  # .items  返回所有的键值对
                if v > max:
                    max = v
                    maxIndex = index
                Ypred[i] = maxIndex # predict the label
        print(Ypred)


        return Ypred


def load_CIFAR_batch(filename):
    """ load single batch of cifar """
    with open(filename, 'rb')as f:
        datadict = p.load(f, encoding='latin1')
        X = datadict['data']
        Y = datadict['labels']
        Y = np.array(Y)  # 字典里载入的Y是list类型，把它变成array类型
        return X, Y


def load_CIFAR_Labels(filename):
    with open(filename, 'rb') as f:
        label_names = p.load(f, encoding='latin1')
        names = label_names['label_names']
        return names
# load data
label_names = load_CIFAR_Labels("cifar-10-batches-py/batches.meta")
imgX1, imgY1 = load_CIFAR_batch("cifar-10-batches-py/data_batch_1")
imgX2, imgY2 = load_CIFAR_batch("cifar-10-batches-py/data_batch_2")
imgX3, imgY3 = load_CIFAR_batch("cifar-10-batches-py/data_batch_3")
imgX4, imgY4 = load_CIFAR_batch("cifar-10-batches-py/data_batch_4")
imgX5, imgY5 = load_CIFAR_batch("cifar-10-batches-py/data_batch_5")
Xte_rows, Yte = load_CIFAR_batch("cifar-10-batches-py/test_batch")

Xtr_rows = np.concatenate((imgX1, imgX2, imgX3, imgX4, imgX5))
Ytr_rows = np.concatenate((imgY1, imgY2, imgY3, imgY4, imgY5))

nn = NearestNeighbor()  # create a Nearest Neighbor classifier class
nn.train(Xtr_rows[:5000,:], Ytr_rows[:5000])  # train the classifier on the training images and labels
Yte_predict = nn.predict(Xte_rows[:1000,:])  # predict labels on the test images
# and now print the classification accuracy, which is the average number
# of examples that are correctly predicted (i.e. label matches)
# print(Yte_predict)
print('accuracy: %f' % (np.mean(Yte_predict == Yte[:1000]))) # Yte_predict==Yte时分类正确，求正确的概率

# show a picture
image=imgX1[9,0:1024].reshape(32,32)
print(image.shape)
plt.imshow(image)
plt.imshow(image,cmap=plt.cm.gray)
plt.axis('off')    #去除图片边上的坐标轴
plt.show()

幸运的是，有一种调优超参数的正确方法，不涉及测试集。想法是：把训练集分成两部分：一部分比较小的训练集称为“验证集(validation set)”。以 CIFAR-10为例，我们可以使用49,000个训练图像进行训练，并留下1,000个图像进行验证。 这个验证集实质上是一个伪测试集，用来调整超参数。

以下是 CIFAR-10的情况:

在这个过程结束时，可以绘制一个图表，显示哪个 k 值工作得最好。 然后，使用这个值，在实际测试集上进行一次计算。

⚠️把训练集分成训练集和验证集。 使用验证集优化所有超参数。 最后在测试集上运行一次并报告性能。

Cross-validation交叉验证

如果训练数据的大小（以及验证数据）可能很小，人们有时会使用更复杂的技术进行超参数调整，称为交叉验证。 使用我们之前的示例，我们的想法是，不是任意选择前1000个数据点作为验证集和静态训练集，而是通过迭代来获得更好且噪声更小的估计k的某个值的工作效果。 验证集并平衡这些性能。 例如，在5倍交叉验证中，我们将训练数据分成5个相等的folds，其中4个用于训练，1个用于验证。 然后我们将迭代哪个fold是验证折叠，评估性能，最后平均不同fold的性能。

例如参数k为5-fold的交叉验证。 对于k的每个值，我们在4folds上训练并在第5个上进行评估。 因此，对于每个k，我们在验证fold上获得5个精度（精度是y轴，每个结果是一个点）。 趋势线通过每个k的结果的平均值绘制，误差条表示标准偏差。 请注意，在此特定情况下，交叉验证表明约k = 7的值最适合此特定数据集（对应于图中的峰值）。 如果我们使用超过5folds，我们可能会看到更平滑（即噪声较小）的曲线。

实际上实际上，更倾向于避免使用交叉验证，而是使用单一的验证分割(a single validation split)，因为使用交叉验证验证可能会耗费大量计算时间。 人们倾向于使用50%-90% 的训练数据用于训练，剩余的用于验证。 但是，这取决于多个因素: 例如，如果超参数的数量很大，可能倾向于使用更大的验证分割。 如果验证集中的示例数量很少(可能只有几百个左右) ，那么使用交叉验证更安全。 在实践中，通常可以看到3-fold、5-fold甚至10-fold的交叉验证。

常见数据分割。给定训练集和测试集。训练及被分成几个folds（例如这里采用5 folds）。folds 1-4 作为训练集。一个fold（如图中fold5被标黄）作为验证fold，并用于调整参数。交叉验证更进一步迭代选择哪个fold是验证fold，与1-5分开。这就是5-fold交叉验证。最后模型训练完毕，所有最佳超参数被确定后，对测试数据进行一次评价（红色）

K-Nearest Neighbor Classifier for CIFAR-10 交叉验证完整代码

import pickle as p
import matplotlib.pyplot as plt
import numpy as np

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

    def train(self, X, y):
        """ X is N x D where each row is an example. Y is 1-dimension of size N """
        # the nearest neighbor classifier simply remembers all the training data
        self.Xtr = X
        self.ytr = y

    def predict(self, X,k):
        """ X is N x D where each row is an example we wish to predict label for """
        num_test = X.shape[0]
        # lets make sure that the output type matches the input type
        Ypred = np.zeros(num_test, dtype=self.ytr.dtype)

        # loop over all test rows
        for i in range(num_test):
            # find the nearest training image to the i'th test image
            # using the L1 distance (sum of absolute value differences)
            distances = np.sum(np.abs(self.Xtr - X[i, :]), axis=1)
            sort_id = distances.argsort()
            # min_index = np.argmin(distances)  # get the index with smallest distance
            # print(min_index)
            dic = {}
            for j in range(k):
                vlable = self.ytr[sort_id[j]]  # 为对应的标签记数
                dic[vlable] = dic.get(vlable, 0) + 1
                # 寻找vlable代表的标签，如果没有返回0并加一，如果已经存在返回改键值对应的值并加一
            max = 0
            print(dic.items())
            for index, v in dic.items():  # .items  返回所有的键值对
                if v > max:
                    max = v
                    maxIndex = index
                Ypred[i] = maxIndex # predict the label
        print(Ypred)


        return Ypred

def load_CIFAR_batch(filename):
    """ load single batch of cifar """
    with open(filename, 'rb')as f:
        datadict = p.load(f, encoding='latin1')
        X = datadict['data']
        Y = datadict['labels']
        Y = np.array(Y)  # 字典里载入的Y是list类型，把它变成array类型
        return X, Y

def load_CIFAR_Labels(filename):
    with open(filename, 'rb') as f:
        label_names = p.load(f, encoding='latin1')
        names = label_names['label_names']
        return names
# load data
label_names = load_CIFAR_Labels("cifar-10-batches-py/batches.meta")
imgX1, imgY1 = load_CIFAR_batch("cifar-10-batches-py/data_batch_1")
imgX2, imgY2 = load_CIFAR_batch("cifar-10-batches-py/data_batch_2")
imgX3, imgY3 = load_CIFAR_batch("cifar-10-batches-py/data_batch_3")
imgX4, imgY4 = load_CIFAR_batch("cifar-10-batches-py/data_batch_4")
imgX5, imgY5 = load_CIFAR_batch("cifar-10-batches-py/data_batch_5")
Xte_rows, Yte = load_CIFAR_batch("cifar-10-batches-py/test_batch")

Xtr_rows = np.concatenate((imgX1, imgX2, imgX3, imgX4, imgX5))
Ytr_rows = np.concatenate((imgY1, imgY2, imgY3, imgY4, imgY5))

nn = NearestNeighbor()  # create a Nearest Neighbor classifier class

nn.train(Xtr_rows[:5000,:], Ytr_rows[:5000])  # train the classifier on the training images and labels
Xval_rows = Xtr_rows[:1000, :]  # take first 1000 for validation
Yval = Ytr_rows[:1000]
Xtr_rows = Xtr_rows[1000:, :]  # keep last 49,000 for train
Ytr_rows = Ytr_rows[1000:]

# find hyperparameters that work best on the validation set
validation_accuracies = []
for k in [1, 3, 5, 10, 20, 50, 100]:
    # use a particular value of k and evaluation on validation data
    nn = NearestNeighbor()
    nn.train(Xtr_rows, Ytr_rows)
    # here we assume a modified NearestNeighbor class that can take a k as input
    Yval_predict = nn.predict(Xval_rows, k=k)
    acc = np.mean(Yval_predict == Yval)
    print('accuracy: %f' % (acc,))

    # keep track of what works on the validation set
    validation_accuracies.append((k, acc))

##########################################################

最近邻分类器优缺点

Pros：
1.实现和理解非常简单。
2.分类器不需要时间训练，只需要存储并索引训练数据。

Cons：
1.测试时需要支付计算成本。因为测试示例分类需要与每个单独的训练数据进行比较。（实践中，更关心测试时间的效率而不是训练时间的效率）

最近邻分类器的计算复杂度是一个非常活跃的研究领域，现有的一些近似最近邻算法（Approximate Nearest Neighbor ，ANN）和库可以加速数据集中的最近邻查找(例如 FLANN)。 这些算法允许在检索过程中权衡最近邻检索的正确性与其空间 / 时间复杂度，通常依赖于预处理 / 索引阶段，该阶段包括构建 kdtree 或运行 k-means 算法。

最近邻分类器在某些设置(特别是低维数据)中可能是一个不错的选择，但它很少适用于实际的图像分类设置。 一个问题是，图像是高维对象(即它们通常包含许多像素) ，在高维空间中的距离可能是非常违反直觉的。 下面的图片说明了我们上面提到的基于像素的L2相似性与视觉上的相似性是非常不同的:

基于高维数据(尤其是图像)的像素距离可能非常不直观。 一个原始图像(左)和它旁边的其他三个图像，都是同样远离它的基础上 L2像素距离。 显然，像素级距离与视觉或语义相似度完全不对应

这里还有一个可视化的例子，使用像素差异来比较图像是不够的。 使用一种称为 t-SNE 的可视化技术来获取 CIFAR-10图像，并将它们嵌入到二维空间中，以便最好地保存它们的(局部)成对距离。 在这个可视化中，根据我们上面展示的 L2像素距离，附近显示的图像被认为是非常接近的:

用 t-SNE 嵌入二维 CIFAR-10图像。 基于 L2像素的距离，这张图片上附近的图片被认为是近距离的。 注意背景的强烈影响，而不是语义类别的差异
更大的可视化版本：http://cs231n.github.io/assets/pixels_embed_cifar10_big.jpg0

特别要注意的是，相互邻近的图像更多的是图像的一般色彩分布的函数，或背景的类型，而不是它们的语义特征。 例如，一只狗可以看到非常接近青蛙，因为两者碰巧都在白色的背景上。 理想情况下，希望所有10个类的图像形成它们自己的集群，以便同一类的图像彼此邻近，而不考虑不相关的特征和变化(例如背景)。 但是，要获得这个属性，必须超越原始像素。