EUAdvancer

CS231n-KNN模型分类Cifar10


从效果看来,KNN并不适合图像识别,它的识别更多基于背景,而不是图片的语义主体。所以在实际应用中我们一般不适用KNN识别图像,但是在学习过程中,通过KNN算法我们可以学习到图像识别的整个流程,对我们的帮助是非常大的

图像识别流程

无论是哪种分类算法,图像识别的流程主要为以下流程

  • 输入图像:一般来说,输入的是图像的像素值
  • 训练模型:通过输入的图像来训练模型
  • 评价模型:用测试数据来测试模型的分类能力从而评估模型的泛化能力

在训练模型阶段,由于很多模型都会有或多或少的参数需要设定(这些参数我们称为“超参”),所以我们需要增加一些步骤来确定这些参数,比如验证集或者交叉验证等方法,这些在接下来都会提到

输入图像

在下载完 cifar10数据集 后,我们首先需要读取cifar10数据集中的数据,这个我就不多介绍了,网上应该也有很多,注意Python版本就可以了,然后我们随机抽取一部分图像进行可视化显示得到效果如下

构建KNN模型

KNN模型是无需训练的,所以我们构建模型的主要步骤在于计算测试集和训练集的欧氏距离以及预测功能。以下代码均基于Python3.5, 用到的库为基本的科学计算库,如果numpy, matplotlib等

计算欧氏距离

公式如下:

计算这个公式其实有很多种方法,我们可以采取每一个测试集和每一个训练集分别计算欧氏距离的方式,也可以用向量化的方式实现(经过测试,嵌套for循环实现的方法所需时间大概是向量实现的几百倍),所以在这里我使用向量化实现。思路为:将欧氏距离公式展开,我们可以得到两个向量之间的距离为x^2 - 2^xy + y^2 (X, Y分别代表一个向量,也就是一张图片), 这样我们就可以用矩阵的方式求解了。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def compute_distances(self, X_test):
"""计算测试集和每个训练集的欧氏距离

向量化实现需转化公式后实现(单个循环不需要)
:param X_test: 测试集 numpy.ndarray
:return: 测试集与训练集的欧氏距离数组 numpy.ndarray
"""

dists = np.zeros((X_test.shape[0], self.X_train.shape[0]))

value_2xy = np.multiply(X_test.dot(self.X_train.T), -2)
value_x2 = np.sum(np.square(X_test), axis=1)
value_y2 = np.sum(np.square(self.X_train), axis=1)
# 注意这里需要将矩阵转回数组
dists = np.sqrt(value_2xy + np.matrix(value_x2).T + np.matrix(value_y2)).getA()
return dists

这里注意一下,因为python的广播无法将(5000 x 500)的数组和(500,)的向量相加,所以我先转成矩阵相加,最后再转回数组,而value_y2(5000,)是可以不用转矩阵直接加的,我转为矩阵是为了代码结构更整齐。

预测分类

原理其实在以前的博文 机器学习-KNN分类算法 里介绍过,取前K个最接近的训练数据的分类,然后将这些分类中个数最多的分类作为预测结果,当然,这里也是通过向量化实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def predict_label(self, dists, k):
"""选择前K个距离最近的标签,从这些标签中选择个数最多的作为预测分类

:param dists: 欧氏距离
:param k: 前K个分类
:return: 预测分类(向量)
"""

y_pred = np.zeros(dists.shape[0])

for i in range(dists.shape[0]):
# 取前K个标签
closest_y = self.y_train[np.argsort(dists[i, :])[:k]]
# 取K个标签中个数最多的标签
y_pred[i] = np.argmax(np.bincount(closest_y))
return y_pred

np.argsort:获取数组从小到大排列的索引
np.bincount:统计数组中每个值出现的次数
np.argmax:获取数组中值最大的索引

交叉验证

在我们训练完整数据集之前,我们必须先确定超参的值,这里我是用交叉验证方法,该方法主要思路为将训练集分为n份,然后每份分别作为测试集,剩下的作为训练集来检验不同的超参的效果,它适用于数据集较少的情况,因为交叉验证训练次数比较多,所以n的值不宜取过大,我们一般取5-10就可以了;如果数据集够大,我们可以使用验证集的方式,即从训练集取一小部分作为验证集来检验不同超参的效果,这样我们所需的训练次数就会少很多了。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def Cross_validation(X_train, y_train):
"""交叉验证,确定超参K,同时可视化K值

:param X_train: 训练集
:param y_train: 训练标签
"""

num_folds = 5
k_choices = [1, 3, 5, 8, 10, 12, 15, 20, 50, 100]
k_accuracy = {}
# 将数据集分为5份
X_train_folds = np.array_split(X_train, num_folds)
y_train_folds = np.array_split(y_train, num_folds)
# 计算每种K值
for k in k_choices:
k_accuracy[k] = []
# 每个K值分别计算每份数据集作为测试集时的正确率
for index in range(num_folds):
# 构建数据集
X_te = X_train_folds[index]
y_te = y_train_folds[index]
X_tr = np.reshape(X_train_folds[:index] + X_train_folds[index + 1:], (X_train.shape[0] * (num_folds - 1) / num_folds, -1))
y_tr = np.reshape(y_train_folds[:index] + y_train_folds[index + 1:], (X_train.shape[0] * (num_folds - 1) / num_folds))
# 预测结果
classify = KNearestNeighbor()
classify.train(X_tr, y_tr)
y_te_pred = classify.predict(X_te, k=k)
accuracy = np.sum(y_te_pred == y_te) / float(X_te.shape[0])
k_accuracy[k].append(accuracy)

for k, accuracylist in k_accuracy.items():
for accuracy in accuracylist:
print("k = %d, accuracy = %.3f" % (k, accuracy))

在上述的代码中,我们需要对每一个K的取值进行对5种训练集计算正确率,我对得到的结果进行可视化得到以下效果

对得到的数据计算算术平均值,作出以上误差棒图,从图中我们可以看出当K值取10左右的正确率为最高

训练评估完整数据模型

当我们确定了超参以后,我们就可以将完整的数据进行训练了,由于KNN在数据集比较大的时候(图片的数据维度很大)计算量特别大,所以我将5000个数据作为完整训练集,500个数据作为测试集(50000个训练集和10000个训练集在我的电脑不能正常运行,内存崩溃)。在上述数据中我得到的结果是正确率为28.2%,虽然识别率比较低,但这应该是个比较正常的结果,我们在使用KNN识别图片之前就应该明白它的识别率不会很高(和cnn比起来,笑而不语)

完整代码

由于代码比较多,为了控制篇幅,主要代码以上都已经贴上了,完整代码见 githubCS231n

结语

KNN不适合数据维度较大的数据集,如果数据是高维度数据,那么进行数据降维(PCA等)是很有必要的