cs231n学习之路：1. 最近邻Nearest Neighbor和KNN

最近邻和K近邻都是懒惰学习，即在test过程中train。

import numpy as npclass NearestNeighbor(object):def __init__(self):passdef train(self,x,y):self.x = xself.y = ydef predict(self, x):num_test = x.shape[0]# ypred 用来保存test样本的label。ypred = np.zeros(num_test,dtype=self.y.dtype)for i in range(num_test):# l1 distancedistances = np.sum(np.abs(self.x - x[i,:]),axis=1)# l2 distance# distances = np.sum((self.x- x[i,:])**2, axis=1)min_index = np.argmin(distances)ypred = self.y[min_index]return ypred

KNN的思想也很简单。最近邻仅考虑了和测试样本距离最近的样本的标签。K近邻则是考虑了和测试样本距离最近的K个训练样本的标签，然后进行投票。所以K的取值一般是奇数。

关于KNN算法的设计，根据循环的使用重数，可以分为三种。分别是没有使用循环，使用一层for循环，使用两层for循环。

1. 使用两层for循环设计KNN

import numpy as npclass KNN(object):def __init__(self):passdef train(self,x,y):self.x_train = xself.y_train = ydef predict(self,x):num_test = x.shape[0]# 用来保存每一个测试样本距离每一个训练样本的距离，所以矩阵大小是# 测试样本数目 * 训练样本数目distances = np.zeros(num_test,self.x_train.shape[0])for i in range(num_test):for j in range(self.x_train.shape[0]):distances[i,j] = np.sqrt(np.sum(np.square(self.x_train[j] - x[i])))# 统计每一行中，最大的前K个数字出现的位置（index）def predict_label(self,distances,k):y_pred = np.zeros(distances.shape[0])for i in range(distances.shape[0]):single_line = distances[i]k_index = np.argsort(single_line)[:k]k_label = self.y_train[k_index]count = np.bincount(k_label)y_pred[i] = np.argmax(count)return y_pred

2. 使用一层for循环

    def predict(self,x):num_test = x.shape[0]distances = np.zeros(num_test,self.x_train.shape[0])for i in range(num_test):distances[i] = np.sqrt(np.sum(np.square(self.x_train - num_test[i,:]),axis=1))return distances

3. 不使用for循环

重点在于转化为向量化操作