cs231n Assignment 1# KNN详细答案及总结

答案及总结"/>

cs231n Assignment 1# KNN详细答案及总结

Assignment 1# KNN

• • KNN分类器简介
  • • 基本思路：
    • 超参数：
  • Part One
  • • Two loop version
  • Part Two
  • • One loop version
    • Two loop version
  • Cross Validation
  • • 预测函数
    • cross validation函数

KNN分类器简介

基本思路：

首先将目标图片（33232）伸展为一维的目标向量向量，然后比较目标向量和训练集中所有样本向量的“”距离“。找出其中距离最小（最相似）的K个样本，找到这些样本所属类别。找出其中最多的作为预测值。

超参数：

这是无监督学习的模型。没有参数，只有距离度量方法和K（近邻数目）两个超参数。通过在dev set 上 cross validation 获得。
cross validation 一般是直接拆训练集进行practice，但是这里也讲了对于小规模数据可以采用k-fold calidation。但总而言之k-fold 一般不用，因为计算复杂性较高。
L1和L2距离。

### Pros and Cons Pros：便于理解，算法简单。 Cons: 1. 高维数据距离难以理解，counter-intuitive。很多时候和人类对相似的理解相违背。 2. 需要存储所有的训练集，存储消耗大。相比之下，SVM softmax分类器训练之后可以舍弃训练集。 3. 每一个目标图像都要和所有数据集图像一一比较。计算消耗大。有相应的改进。ANN通过pre processing 来 trade off correctness with space/time complexity.

Part One

计算testset 和training set之间的距离。在=1 以及K=5条件下分别进行test set的判断，计算准确率。
其中X 作为test_set形状为（500,3072）
self.X_train 作为training_set形状为（5000,3072）
dist作为距离，形状为（500，5000）
其中500，5000为样本数目。
3072=33232为样本向量长度。也就是（500，3072）每一行是一张展开成（1，3072）的图片向量。

核心代码在于距离的计算，就是一个切片：

Two loop version

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(X[i,:]-self.X_train[j,:]))))return dists                 

之后带入 accuracy分别是0.274，0.290

Part Two

通过numpy的矢量化，将循环改成单循环甚至没有循环，计算比较消耗相应的时间消耗。

One loop version

这里用到的技巧是numpy的broadcasting功能。
取出第i个样本向量X[i]（1，3072），与self.X_train（5000，3072.）作差平方。通过广播机制，矩阵的每一行与向量分别作差。
之后按照axis=1求和并开根号，就得到了一个（5000，1）的列向量，代表样本i与train_set之中5000个样本的距离，转置之后就是dists矩阵的第i行了。
之后就所有的500个样本遍历，就可以得到（500，5000）的距离矩阵。
重点：

1. numpy的广播机制。
2. reshape。当时搞的时候看了一些视频，吴恩达推荐迷惑的时候reshape一下看一下矩阵和你想象的样子是不是一样的。或者加注释，总之自己就感觉很容易不知道这个矩阵是什么形状，或者是每个维度是什么含义，浪费大量时间。

def 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(X[i] - self.X_train), axis=1)).reshape(1,num_train)return dists

Two loop version

这个相对难想一些。
思路是采用二项式定理展开
先计算样本和training各维度平方和。test_square（500,1），training_square（1，5000）
之后计算样本和training之间的二次项。用X（500，3072）和self.X_training.T（3072，5000）点乘。得到二次项quadratic_term（500，5000）。
最后利用二项式定理计算dists（500，5000）。
test_square（500,1）+training_square（1，5000）。再次通过强大的broadcasting。demo如下：

def compute_distances_no_loops(self, X):# HINT: Try to formulate the l2 distance using matrix multiplication#num_test = X.shape[0]num_train = self.X_train.shape[0]dists = np.zeros((num_test, num_train))test_square=(X**2).sum(axis=1).reshape(-1,1)#平方项training_square=(self.X_train ** 2).sum(axis=1).reshape(1,-1)#平方项quadratic_term=2*X.reshape(num_test,3702)@self.X_train.reshape(3702,num_train)#二次项dists=np.sqrt(test_square+training_square-quadratic_npterm)return dists

Cross Validation

这一部分就是用5-fold cross validation 确定K这个超参数的选取。

预测函数

重点：

1. arg系函数（argsort，argmax，argmin，argwhere）
   他们都与相应的函数对应，但是他们可以返回满足相应条件的下标。
2. max函数的key
   可以根据出现次数取出最大的

思路就是找到dist[i]（1，5000）里面最小的k个放在closest_y里面。
然后通过max函数找到出现次数最多的。就是预测值。

def 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 = []neighbor_label=list(np.argsort(dists[i])[0:k])for s in neighbor_label:closest_y.append(self.y_train[s])y_pred[i]=max(closest_y,key=closest_y.count)return y_pred

cross validation函数

重点：

1. np.array_split()函数拆分数据集，不是随机的拆分
2. np.concatenate([X_train_folds[j] for j in range(num_folds) if j!=i])就没啥说的，很妙。

num_folds = 5
k_choices = [1, 3, 5, 8, 10, 12, 15, 20, 50, 100]
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]=[]for i in range(num_folds):classifier.train(np.concatenate([X_train_folds[j] for j in range(num_folds) if j!=i]),np.concatenate([y_train_folds[j] for j in range(num_folds) if j!=i]))         			  		k_to_accuracies[k].append(np.sum(classifier.predict(X_train_folds[i],k=k)==y_train_folds[i])/len(y_train_folds[i]))

最后画出来一个cross validation的图。还是很有成就感的，这段代码自己真正cross validation的时候也可以拿来用。