Assignment 1_KNN
2018-10-17 本文已影响0人
SnorlaxSE
代码实现部分
- 计算test样本与training样本的L2距离. L2距离的定义如下：
Open cs231n/classifiers/k_nearest_neighbor.py and implement compute_distances_two_loops.
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):
#####################################################################
# TODO: #
# Compute the l2 distance between the ith test point and the jth #
# training point, and store the result in dists[i, j]. You should #
# not use a loop over dimension. #
#####################################################################
pass
### X - X_test.shape == (500,3072) X_train.shape = (5000,3072)
# dists[i][j] = np.sqrt(np.sum((X[i]-self.X_train[j])**2))
dists[i][j] = np.sqrt(np.sum(np.square(X[i,:] - self.X_train[j,:])))
#####################################################################
# END OF YOUR CODE #
#####################################################################
return dists #dists.shape = (500, 5000)
Now lets speed up distance matrix computation by using partial vectorization with one loop. Implement the function compute_distances_one_loop
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):
#######################################################################
# TODO: #
# Compute the l2 distance between the ith test point and all training #
# points, and store the result in dists[i, :]. #
#######################################################################
pass
# dists[i] = np.sqrt(np.sum((self.X_train - X[i]) ** 2, 1))
dists[i] = np.sqrt(np.sum(np.square(self.X_train - X[i]), axis=1))
#######################################################################
# END OF YOUR CODE #
#######################################################################
return dists # dists.shape = (500, 5000)
Now implement the fully vectorized version inside compute_distances_no_loops
def 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))
#########################################################################
# TODO: #
# Compute the l2 distance between all test points and all training #
# points without using any explicit loops, and store the result in #
# dists. #
# #
# You should implement this function using only basic array operations; #
# in particular you should not use functions from scipy. #
# #
# HINT: Try to formulate the l2 distance using matrix multiplication #
# and two broadcast sums. #
#########################################################################
pass
dists += np.sum(self.X_train ** 2, axis=1).reshape(1, num_train)
dists += np.sum(X ** 2, axis=1).reshape(num_test, 1) # reshape for broadcasting
dists -= 2 * np.dot(X, self.X_train.T)
dists = np.sqrt(dists)
#########################################################################
# END OF YOUR CODE #
#########################################################################
return dists
Now implement the function predict_labels
def predict_labels(self, dists, k=1):
num_test = dists.shape[0]
y_pred = np.zeros(num_test)
for i in range(num_test):
# A list of length k storing the labels of the k nearest neighbors to
# the ith test point.
closest_y = []
#########################################################################
# TODO: #
# Use the distance matrix to find the k nearest neighbors of the ith #
# testing point, and use self.y_train to find the labels of these #
# neighbors. Store these labels in closest_y. #
# Hint: Look up the function numpy.argsort. #
#########################################################################
pass
# sorted_index = np.argsort(dists[i])
# closest_y = self.y_train[sorted_index[:k]]
closest_y = self.y_train[np.argsort(dists[i])[:k]]
#########################################################################
# TODO: #
# Now that you have found the labels of the k nearest neighbors, you #
# need to find the most common label in the list closest_y of labels. #
# Store this label in y_pred[i]. Break ties by choosing the smaller #
# label. #
#########################################################################
pass
y_pred[i] = np.bincount(closest_y).argmax()
# timeLabel = sorted([(np.sum(np.array(closest_y) == y_), y_) for y_ in set(closest_y)])[-1]
# y_pred[i] = timeLabel[1]
# appear_times = {}
# for label in closest_y:
# if label in appear_times:
# appear_times[label] += 1
# else:
# appear_times[label] = 0
# # find most commen label
# y_pred[i] = max(appear_times, key=lambda x: appear_times[x])
#########################################################################
# END OF YOUR CODE #
#########################################################################
return y_pred
-
We will now determine the best value of this hyperparameter with cross-validation.
使用cross validation的方法，来选择hyper-parameter超参数k的值.
cross validation的原理是，将training样本集分成n份（如下图中的例子，是5份），每一份叫做一个fold，然后依次迭代这n个fold，将其作为validation集合，其余的n-1个fold一起作为training集合，然后进行训练并计算准确率。
选择一组候选k值，依次迭代执行上面描述的过程，最终根据准确率，进行评估选择最合适的k值。
num_folds = 5
k_choices = [1, 3, 5, 8, 10, 12, 15, 20, 50, 100]
X_train_folds = []
y_train_folds = []
################################################################################
# TODO: #
# Split up the training data into folds. After splitting, X_train_folds and #
# y_train_folds should each be lists of length num_folds, where #
# y_train_folds[i] is the label vector for the points in X_train_folds[i]. #
# Hint: Look up the numpy array_split function. #
################################################################################
# Your code
X_train_folds = np.array_split(X_train, num_folds)
y_train_folds = np.array_split(y_train, num_folds)
################################################################################
# END OF YOUR CODE #
################################################################################
# A dictionary holding the accuracies for different values of k that we find
# when running cross-validation. After running cross-validation,
# k_to_accuracies[k] should be a list of length num_folds giving the different
# accuracy values that we found when using that value of k.
k_to_accuracies = {}
################################################################################
# TODO: #
# Perform k-fold cross validation to find the best value of k. For each #
# possible value of k, run the k-nearest-neighbor algorithm num_folds times, #
# where in each case you use all but one of the folds as training data and the #
# last fold as a validation set. Store the accuracies for all fold and all #
# values of k in the k_to_accuracies dictionary. #
################################################################################
# Your code
for k_candi in k_choices:
k_to_accuracies[k_candi] = []
for i in range(num_folds):
X_test_hy = X_train_folds[i]
y_test_hy = y_train_folds[i]
X_train_hy = np.vstack(X_train_folds[0:i]+X_train_folds[i+1:])
y_train_hy = np.hstack(y_train_folds[0:i]+y_train_folds[i+1:])
# x_trai = np.array(X_train_folds[:f] + X_train_folds[f+1:])
# y_trai = np.array(Y_train_folds[:f] + Y_train_folds[f+1:])
# x_trai = x_trai.reshape(-1, x_trai.shape[2])
# y_trai = y_trai.reshape(-1)
classifier.train(X_train_hy, y_train_hy)
dists_hy = classifier.compute_distances_no_loops(X_test_hy)
y_test_pred_hy = classifier.predict_labels(dists_hy, k=k_candi)
# Compute the fraction of correctly predicted examples
num_correct_hy = np.sum(y_test_pred_hy == y_test_hy)
accuracy_hy = float(num_correct_hy) / len(y_test_hy)
k_to_accuracies[k_candi].append(accuracy_hy)
################################################################################
# END OF YOUR CODE #
################################################################################
print(k_to_accuracies)
# 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))
numpy/matplotlib 部分函数说明
1. numpy.flatnonzero(): 输入一个矩阵，返回了其中非零元素的位置
2. numpy.random.choice(a, size=None, replace=True, p=None)
- a: If an ndarray, a random sample is generated from its elements.
If an int, the random sample is generated as if a was np.arange(n)
- size : int or tuple of ints, optional
- replace : boolean, optional
If you want only unique samples then this should be false.
- p : 1-D array-like, optional
The probabilities associated with each entry in a. If not given the sample assumes a uniform distribution over all entries in a.
3. matplotlib.pyplot.subplot(X,X,X)：
- 前两个数表示子图组成的矩阵的行列数，比如有6个子图，排列成3行2列，那就是subplot(3,2,X)。最后一个数表示要画第X个图了。
4. matplotlib.pyplot.imshow(X,interpolation='none',cmap=None)
- X: 要绘制的图像或数组.
- interpolation 插值方式 [None, 'none', 'nearest', 'bilinear', 'bicubic', 'spline16',
'spline36', 'hanning', 'hamming', 'hermite', 'kaiser', 'quadric',
'catrom', 'gaussian', 'bessel', 'mitchell', 'sinc', 'lanczos']
- cmap: 颜色图谱（colormap), 默认绘制为RGB(A)颜色空间.
5. numpy.reshape(a, newshape, order='C')
- 注：给出一个m*n的矩阵，如果newshape给的参数是（x, -1）,那么函数会自动判别newshape为（x, m*n/x）,这里的x一定要能被m*n整除！
6. numpy.argsort()：输出排好序的元素下标, a[np.argsort(a)]的结果才是最终排好序的结果.
7. numpy.binicount(x, weight = None, minlength = None)
>>> x = np.array([0, 1, 1, 3, 2, 1, 7])
>>> np.bincount(x)
array([1, 3, 1, 1, 0, 0, 0, 1])
8. x_norm=np.linalg.norm(x, ord=None, axis=None, keepdims=False)
- linalg=linear（线性）+algebra（代数），norm则表示范数
- x: 表示矩阵（也可以是一维）
- ord：范数类型
- ord=1：列和的最大值
- ord=2：|λE-ATA|=0，求特征值，然后求最大特征值的算术平方根
- ord=np.inf：行和的最大值
- axis：处理类型
- axis=1表示按行向量处理，求多个行向量的范数
- axis=0表示按列向量处理，求多个列向量的范数
- axis=None表示矩阵范数
- keepding：是否保持矩阵的二维特性
- True表示保持矩阵的二维特性，False相反
9. np.dot(A, B)：对于二维矩阵，计算真正意义上的矩阵乘积，同线性代数中矩阵乘法的定义.
10. sum(a, axis=None, dtype=None, out=None, keepdims=<class 'numpy._globals._NoValue'>)
- axis :
- axis = None: 对所有元素求和
- axis = 0: 对所有在同一列的元素求和
- axis = 1: 对所有在同一行的元素求和
11. np.vstack(tup): 沿着竖直方向将矩阵堆叠起来
- Note: the arrays must have the same shape along all but the first axis. 除开第一维外，被堆叠的矩阵各维度要一致.
12. np.hstack(tup):沿着水平方向将数组堆叠起来
13. plt.scatter(X, Y)： 散点图 (x,y)即坐标
Summary
即使经过调优，knn算法的准确率也不足30%，可以知道knn算法并不适合用于图像分类学习任务.
参考：cs231n - assignment1 - knn、Stanford cs231n Assignment #1 (a) 实现KNN
