CIFAR-10的KNN实现

作业讲解

KNN的实现主要分为两步：

训练：分类器简单地记住所有的数据
测试：测试数据分别和所有训练数据计算距离，选取k个最近的训练样本的label，通过投票（vote）获得预测值。

代码实现

#导入一些包 import random import numpy as np from cs231n.data_utils import load_CIFAR10 import matplotlib.pyplot as plt# 图片展示在此处，不会出现新的窗口 %matplotlib inline plt.rcParams['figure.figsize'] = (10.0, 8.0) # set default size of plots plt.rcParams['image.interpolation'] = 'nearest' plt.rcParams['image.cmap'] = 'gray'

数据集下载到本地

# 下载训练数据集 # 训练集 trainset = datasets.CIFAR10(root='./CIFAR10',train=True,download=True,transform=transform) # 测试集 testset = datasets.CIFAR10(root='./CIFAR10',train=False,download=True,transform=transform)

读取数据集

加载数据集以及划分训练集和测试集

# 加载CIFAR-10 data.这里我是提前下载到本地 cifar10_dir = './cs231n/datasets/cifar-10-batches-py' #下载到的本地地址#清理变量以防止多次加载数据（这可能会导致内存问题） try:del X_train, y_traindel X_test, y_testprint('Clear previously loaded data.') except:passX_train, y_train, X_test, y_test = load_CIFAR10(cifar10_dir)# 打印出训练和测试数据的大小一检查是否合理 print('Training data shape: ', X_train.shape) print('Training labels shape: ', y_train.shape) print('Test data shape: ', X_test.shape) print('Test labels shape: ', y_test.shape)

输出：训练集中有50000张图片，测试集有10000张图片

部分样本展示

展示一些训练集样本
数据集中总共有7个类别

# 可视化部分数据集 # 我们可以得到每一个类在训练数据集上的展示 classes = ['plane', 'car', 'bird', 'cat', 'deer', 'dog', 'frog', 'horse', 'ship', 'truck'] num_classes = len(classes) samples_per_class =8 for y, cls in enumerate(classes):idxs = np.flatnonzero(y_train == y)#该函数输入一个矩阵，返回扁平化后矩阵中非零元素的位置（index）idxs = np.random.choice(idxs, samples_per_class, replace=False)#返enumerate():回一个可迭代对象的枚举形式，（上面第一个 返回 0 plane/ 1 car/ 2 bird/……）for i, idx in enumerate(idxs):plt_idx = i * num_classes + y + 1plt.subplot(samples_per_class, num_classes, plt_idx)plt.imshow(X_train[idx].astype('uint8'))plt.axis('off')if i == 0:plt.title(cls) plt.show()

输出：

在本练习中对数据进行子采样以提高代码执行效率

# 在本练习中对数据进行子采样以提高代码执行效率 num_training = 5000 mask = list(range(num_training))#产生训练样本的位置 X_train = X_train[mask]#选择训练样本 y_train = y_train[mask]#确定训练样本标签num_test = 500 mask = list(range(num_test)) X_test = X_test[mask] y_test = y_test[mask]# 把（50000，32，32，3）变成（5000，3072） #一个图片用一个32323的一行来表示，相当于把图片拉成一个行向量 X_train = np.reshape(X_train, (X_train.shape[0], -1)) X_test = np.reshape(X_test, (X_test.shape[0], -1)) print(X_train.shape, X_test.shape)

创建KNN分类器

import numpy as np from collections import Counterclass KNearestNeighbor(object):""" a kNN classifier with L2 distance """def __init__(self):passdef train(self, X, y):self.X_train = Xself.y_train = ydef predict(self, X, k=1, num_loops=0):if num_loops == 0:dists = self.compute_distances_no_loops(X)elif num_loops == 1:dists = self.compute_distances_one_loop(X)elif num_loops == 2:dists = self.compute_distances_two_loops(X)else:raise ValueError('Invalid value %d for num_loops' % num_loops)return self.predict_labels(dists, k=k)def compute_distances_two_loops(self, X):num_test = X.shape[0]num_train = self.X_train.shape[0]dists = np.zeros((num_test, num_train))for i in range(num_test):#测试样本的循环for j in range(num_train):#训练样本的循环 #dists[i,j]=np.sqrt(np.sum(np.square(self.X_train[j,:]-X[i,:])))dists[i,j]=np.linalg.norm(X[i]-self.X_train[j])#np.square是针对每个元素的平方方法 return distsdef compute_distances_one_loop(self, X):num_test = X.shape[0]num_train = self.X_train.shape[0]dists = np.zeros((num_test, num_train))for i in range(num_test):#dists[i,:] = np.sqrt(np.sum(np.square(self.X_train-X[i,:]),axis = 1))dists[i,:]=np.linalg.norm(X[i,:]-self.X_train[:],axis=1)return distsdef compute_distances_no_loops(self, X):num_test = X.shape[0]num_train = self.X_train.shape[0]dists = np.zeros((num_test, num_train)) """mul1 = np.multiply(np.dot(X,self.X_train.T),-2) sq1 = np.sum(np.square(X),axis=1,keepdims = True) sq2 = np.sum(np.square(self.X_train),axis=1) dists = mul1+sq1+sq2 dists = np.sqrt(dists) """dists += np.sum(np.multiply(X,X),axis=1,keepdims = True).reshape(num_test,1)dists += np.sum(np.multiply(self.X_train,self.X_train),axis=1,keepdims = True).reshape(1,num_train)dists += -2*np.dot(X,self.X_train.T)dists = np.sqrt(dists) return distsdef predict_labels(self, dists, k=1):num_test = dists.shape[0]y_pred = np.zeros(num_test)for i in range(num_test):closest_y = []closest_y = self.y_train[np.argsort(dists[i, :])[:k]].flatten()c = Counter(closest_y)y_pred[i]=c.most_common(1)[0][0]"""closest_y=self.y_train[np.argsort(dists[i, :])[:k]] y_pred[i] = np.argmax(np.bincount(closest_y))"""return y_pred

KNN训练

classifier = KNearestNeighbor()#加载分类器 classifier.train(X_train, y_train)#在训练集上训练

KNN分类器是要把预测的样本与训练集比较，找到离训练集最近的。所以train（）的作用是把训练集X_train绑定到类KNearestNeighbor的属性self.X_train

dists = classifier.compute_distances_two_loops(X_test) print(dists.shape) #dists 表示的是test集与training data的距离，dists[i, j] 表示的是test的第i个与training data的第j个的距离。 #out：（500，5000） plt.imshow(dists, interpolation='none') plt.show()

得到了dists以后，就可以预测test data里的图片的分类。dists的第i行表示，test的第i个样本与5000个训练集数据的距离，找到距离最小的K个训练集图片，他们的图片类型就是我们预测的结果y_test_pred。 这里指定了k=1，在classifier.predict_labels函数中就只会找到距离最小的一个图片，他的类别就是对test预测的类别。

预测

k=1时

#k = 1 y_test_pred = classifier.predict_labels(dists, k=1)# 得到预测的准确率 num_correct = np.sum(y_test_pred == y_test) accuracy = float(num_correct) / num_test print('Got %d / %d correct => accuracy: %f' % (num_correct, num_test, accuracy)) #out：Got 137 / 500 correct => accuracy: 0.274000

k=5

y_test_pred = classifier.predict_labels(dists, k=5) num_correct = np.sum(y_test_pred == y_test) accuracy = float(num_correct) / num_test print('Got %d / %d correct => accuracy: %f' % (num_correct, num_test, accuracy)) #out：Got 145 / 500 correct => accuracy: 0.290000

k=10

y_test_pred = classifier.predict_labels(dists, k=10) num_correct = np.sum(y_test_pred == y_test) accuracy = float(num_correct) / num_test print('Got %d / %d correct => accuracy: %f' % (num_correct, num_test, accuracy)) #out：Got 144 / 500 correct => accuracy: 0.288000

时间计算

检查一范数L1和二范数L2的距离度量公式算出来的结果是否一样

#检查两次距离是否一样dists，dists_one dists_one = classifier.compute_distances_one_loop(X_test) difference = np.linalg.norm(dists - dists_one, ord='fro') print('One loop difference was: %f' % (difference, )) if difference < 0.001:print('Good! The distance matrices are the same') else:print('Uh-oh! The distance matrices are different') '''out: One loop difference was: 0.000000 Good! The distance matrices are the same '''

计算不同距离度量下计算的时间结果

# Let's compare how fast the implementations are def time_function(f, *args):"""Call a function f with args and return the time (in seconds) that it took to execute."""import timetic = time.time()f(*args)toc = time.time()return toc - tictwo_loop_time = time_function(classifier.compute_distances_two_loops, X_test) print ('Two loop version took %f seconds' % two_loop_time)one_loop_time = time_function(classifier.compute_distances_one_loop, X_test) print ('One loop version took %f seconds' % one_loop_time)no_loop_time = time_function(classifier.compute_distances_no_loops, X_test) print ('No loop version took %f seconds' % no_loop_time) '''out: Two loop version took 24.126041 seconds One loop version took 51.611078 seconds No loop version took 0.319181 seconds'''

选择K

利用Cross-validation选择K值
超参数 hyperparameter

机器学习算法设计中，如K-NN中的k的取值，以及计算像素差异时使用的距离公式，都是超参数，而调参更是机器学习中不可或缺的一步。

注意：调参要用validation set,而不是test set. 机器学习算法中，测试集只能被用作最后测试，得出结论，如果之前用了，就会出现过拟合的情况

交叉验证cross validation set

这是当训练集数量较小的时候，可以将训练集平分成几份，然后循环取出一份当做validation set 然后把每次结果最后取平均。如下： 将训练集分为如下几部分：

num_folds = 5#5折交叉验证 k_choices = [1, 3, 5, 8, 10, 12, 15, 20, 50, 100]X_train_folds = [] y_train_folds = []X_train_folds = np.array_split(X_train, num_folds) y_train_folds = np.array_split(y_train, num_folds)k_to_accuracies = {}for k in k_choices:k_to_accuracies[k] = np.zeros(num_folds)for i in range(num_folds):Xtr = np.array(X_train_folds[:i] + X_train_folds[i+1:])ytr = np.array(y_train_folds[:i] + y_train_folds[i+1:])Xte = np.array(X_train_folds[i])yte = np.array(y_train_folds[i]) Xtr = np.reshape(Xtr,(X_train.shape[0] * 4 // 5, -1))ytr = np.reshape(ytr,(y_train.shape[0] * 4 // 5, -1))Xte = np.reshape(Xte,(X_train.shape[0] // 5, -1))yte = np.reshape(yte,(y_train.shape[0]// 5, -1))classifier.train(Xtr,ytr)yte_pred = classifier.predict(Xte, k)yte_pred = np.reshape(yte_pred, (yte_pred.shape[0], -1))num_correct = np.sum(yte_pred == yte)accuracy = float(num_correct) / len(yte)k_to_accuracies[k][i] = accuracy # Print out the computed accuracies for k in sorted(k_to_accuracies):for accuracy in k_to_accuracies[k]:print ('k = %d, accuracy = %f' % (k, accuracy)) '''out k = 1, accuracy = 0.263000 k = 1, accuracy = 0.257000 k = 1, accuracy = 0.264000 k = 1, accuracy = 0.278000 k = 1, accuracy = 0.266000 k = 3, accuracy = 0.257000 k = 3, accuracy = 0.263000 k = 3, accuracy = 0.273000 k = 3, accuracy = 0.282000 k = 3, accuracy = 0.270000 k = 5, accuracy = 0.265000 k = 5, accuracy = 0.275000 k = 5, accuracy = 0.295000 k = 5, accuracy = 0.298000 k = 5, accuracy = 0.284000 k = 8, accuracy = 0.272000 k = 8, accuracy = 0.295000 k = 8, accuracy = 0.284000 k = 8, accuracy = 0.298000 k = 8, accuracy = 0.290000 k = 10, accuracy = 0.272000 k = 10, accuracy = 0.303000 k = 10, accuracy = 0.289000 k = 10, accuracy = 0.292000 k = 10, accuracy = 0.285000 k = 12, accuracy = 0.271000 k = 12, accuracy = 0.305000 k = 12, accuracy = 0.285000 k = 12, accuracy = 0.289000 k = 12, accuracy = 0.281000 k = 15, accuracy = 0.260000 k = 15, accuracy = 0.302000 k = 15, accuracy = 0.292000 k = 15, accuracy = 0.292000 k = 15, accuracy = 0.285000 k = 20, accuracy = 0.268000 k = 20, accuracy = 0.293000 k = 20, accuracy = 0.291000 k = 20, accuracy = 0.287000 k = 20, accuracy = 0.286000 k = 50, accuracy = 0.273000 k = 50, accuracy = 0.291000 k = 50, accuracy = 0.274000 k = 50, accuracy = 0.267000 k = 50, accuracy = 0.273000 k = 100, accuracy = 0.261000 k = 100, accuracy = 0.272000 k = 100, accuracy = 0.267000 k = 100, accuracy = 0.260000 k = 100, accuracy = 0.267000'''

绘制5折交叉验证下不同k值得准确率如何

for k in k_choices:accuracies = k_to_accuracies[k]plt.scatter([k] * len(accuracies), accuracies)accuracies_mean = np.array([np.mean(v) for k,v in sorted(k_to_accuracies.items())]) accuracies_std = np.array([np.std(v) for k,v in sorted(k_to_accuracies.items())]) plt.errorbar(k_choices, accuracies_mean, yerr=accuracies_std) plt.title('Cross-validation on k') plt.xlabel('k') plt.ylabel('Cross-validation accuracy') plt.show()

根据上面的交叉验证结果，选择 k 的最佳值，
使用所有训练数据重新训练分类器，并在测试中进行测试数据。您应该能够在测试数据上获得超过28%的准确率。

best_k = 8 classifier = KNearestNeighbor() classifier.train(X_train, y_train) y_test_pred = classifier.predict(X_test, k=best_k)# Compute and display the accuracy num_correct = np.sum(y_test_pred == y_test) accuracy = float(num_correct) / num_test print ('Got %d / %d correct => accuracy: %f' % (num_correct, num_test, accuracy)) #out：Got 147 / 500 correct => accuracy: 0.294000

总结

以上是生活随笔为你收集整理的KNN-2实现的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。