CS231n-Lecture2:图像分类（Image Classification）

最近邻分类器（Nearest Neighbor Classifier / NN）

概念

1. 图像分类数据集

CIFAR-10：60,000 张图，训练集 50,000张（每个标签5,000张），测试集10,000 张

2. L1距离——曼哈顿距离
   $d_{1}\left(I_{1}, I_{2}\right)=\sum_{p}\left|I_{1}^{p}-I_{2}^{p}\right|$

可视化过程:

3. L2距离——欧氏距离
   $d_{2}\left(I_{1}, I_{2}\right)=\sqrt{\sum_{p}\left(I_{1}^{p}-I_{2}^{p}\right)^{2}}$

实现过程

首先，将CIFAR-10数据作为4个数组加载到内存中：训练数据/标签和测试数据/标签。在下面的代码中，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
# 所有图片都展开成一维
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) )

注意，作为评估标准，通常使用precision，它测量正确的预测分数。请注意，构建的所有分类器都满足这一通用API：它们具有一个train(X,y)函数，该函数接受数据和标签以供学习。在内部，类应构建标签的某种模型以及如何从数据中预测它们。然后是一个predict(X)函数，该函数获取新数据并预测标签。这是一个简单的最近邻分类器的实现，该分类器具有满足此模板的L1距离：

import numpy as npclass NearestNeighbor(object):def __init__(self):passdef 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 dataself.Xtr = Xself.ytr = ydef 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 typeYpred = np.zeros(num_test, dtype = self.ytr.dtype)# loop over all test rowsfor 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 distanceYpred[i] = self.ytr[min_index] # predict the label of the nearest examplereturn Ypred

此分类器在CIFAR-10上准确率仅达到38.6％，改为使用L2距离：

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

在CIFAR-10上以该距离运行最近邻分类器，则将获得35.4％的准确度（略低于L1距离结果）。

K-最近邻算法（K-nearest neighbor / kNN）

我们将找到前k个最接近的图像，然后在测试图像的标签上进行投票，而不是在训练集中找到单个最接近的图像。从直观感受上就可以看到，更高的k值可以让分类的效果更平滑，使得分类器对于异常值更有抵抗力。

理解：kNN决策边界

使用2维点表示，分成3类（红色，蓝色，绿色）的最近邻分类器和5-最近邻分类器之间差异的示例:
彩色区域显示由分类器以L2距离诱导的决策边界。白色区域显示了含糊不清的点（即，至少有两个类被投票）。请注意，在使用NN分类器的情况下，异常数据点（例如，蓝点云中间的绿色点）会创建可能存在错误预测的小岛，而5-NN分类器会平滑这些不规则现象，可能会导致更好的泛化在测试数据上（未显示）。还应注意，5-NN图像中的灰色区域是由最近邻居之间的投票关系引起的（例如2个邻居为红色，2个邻居为蓝色，1个邻居为绿色）。

超参数的选择（hyperparameter）

??不能将测试集用于调整超参数。设计机器学习算法时，理想情况下，直到最后一次才应该接触到测试集。如果将测试集用于调整超参数，可能会导致需要调整超参数才能在测试集上正常工作，部署模型时性能可能会大大降低——过拟合测试集。换言之，如果使用测试集来调优，实际上就是把测试集当做训练集，由测试集训练出来的算法再跑测试集，自然性能看起来会很好。所以，最终测试的时候再使用测试集，可以很好地近似度量你所设计的分类器的泛化性能。将您的训练集分为训练集和验证集。

超参数的正确调整方法：使用验证集调整所有超参数。最后，一次运行测试集并报告性能。

对于CIFAR-10：使用49,000张训练图像进行训练，而留出1,000张进行验证。该验证集实质上用作伪测试集，以调整超参数：

# assume we have Xtr_rows, Ytr, Xte_rows, Yte as before
# recall Xtr_rows is 50,000 x 3072 matrix
Xval_rows = Xtr_rows[:1000, :] # take first 1000 for validation
Yval = Ytr[:1000]
Xtr_rows = Xtr_rows[1000:, :] # keep last 49,000 for train
Ytr = Ytr[1000:]# 找出验证集上效果最好的超参数
validation_accuracies = []
for k in [1, 3, 5, 10, 20, 50, 100]:# 设置一些k值，用于评估nn = NearestNeighbor()nn.train(Xtr_rows, Ytr)# 用以k为输入的kNN进行预测Yval_predict = nn.predict(Xval_rows, k = k)acc = np.mean(Yval_predict == Yval)	#计算准确率print 'accuracy: %f' % (acc,)# 输出结果validation_accuracies.append((k, acc))

在此过程结束时，绘制一个图表，以显示k的哪个值最有效。然后，坚持使用该值，并在实际测试集中进行一次评估。

交叉验证

如果训练集（及验证集）的size很小，可进行交叉验证。

例如，在5倍交叉验证中，我们将训练数据分为5个相等的fold（折），轮流将其中4个用于训练，将1个用于验证。5次的结果的均值作为对算法精度的估计。

上图为参数k的5折交叉验证示例。对于k的每个值，我们进行4次训练，并在第5次进行评估。因此，对于每个k，我们在验证倍数上收到5个精度（精度是y轴，每个结果是一个点）。趋势线是通过每个k的结果平均值绘制的，误差线表示标准偏差。请注意，在这种特定情况下，交叉验证表明，大约 k = 7（对应于图中的峰值）在该特定数据集上效果最佳。如果我们使用5折以上，我们可能会期望看到更平滑（即更少的噪音）曲线。

kNN优缺点

1. 优点：施和理解非常简单
2. 缺点：由于需要与每个单独的训练示例进行比较，因此在测试时计算成本高、效率低。

reference

参考：https://cs231n.github.io/classification/