前言
本文旨在学习和记录，如需转载，请附出处https://www.jianshu.com/p/ea566512b04f
KNN
原理
K近邻(K-nearest neighbor) 是一种基本的分类和回归的算法，在cs231中只介绍了分类算法。KNN分类算法的思想：给定一批带标签的数据作为训练数据，在对未知标签的数据进行分类时，根据其K个最近邻训练数据的标签，采取多数表决的方法进行预测。KNN中训练不花时间，预测时需要采取特定的距离的度量方式来进行最近邻的寻找，如果待预测的样本很多，其预测时间也会相应的增加。
距离度量
距离度量一般采取Minkowski距离，其公式为：
二维空间中Lp距离.png
- 当p = 2时，就是我们常用的欧式距离；
- 当p = 1时，就是曼哈顿距离；
- 当p=
时，该距离就表示为各个坐标系中最大的距离：
当然，还有许多距离，比如遥感应用中的光谱角距离，这里就不一一介绍了。
K值的选择
- 如果K值很小（最小为1），这种预测只在一个很小的领域中进行预测，会很大程度的依赖近邻点，这在深度学习中表现就是容易过拟合，K值太小模型太复杂；
- 如果K值很大（最大为训练集的数目），这是不可取的，忽略了大量有用的信息，容易预测错误，模型过于简单。
所以K值需要精心调节选取。 -
在cs231实验中，采用了X折交叉验证的方法来选择K值；
其做法是将训练集切成X份，每次拿一份来验证，剩下的X-1份组成新的训练集，这样就会存在X组不同的情况，然后再选择几个K值（比如1，3，5，7，9等）；通过计算每一个K值下X组不同情况下的验证集的精度的均值，来寻找最优的K值。
cs231实验
cs231实验中选择的数据为cifar10数据。
距离矩阵计算
实验中介绍了计算距离矩阵的几种方法，two-loop,one-loop, no-loop(该方法采取矩阵向量的操作)，这里只介绍no-loop的代码：
X_test_2 = np.square(X).sum(axis = 1)
X_train_2 = np.square(self.X_train).sum(axis = 1)
dists = np.sqrt(-2*np.dot(X,self.X_train.T)+X_train_2+np.matrix(X_test_2).T)###(5000,) and (500,1) broadcast
# print(dists.shape)
# *****END OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****
return np.array(dists)
注意：这里采取的numpy中加法的broadcast机制
Two loop version took 146.657845 seconds
One loop version took 89.948750 seconds
No loop version took 1.911102 seconds
no-loop计算距离矩阵的效率明显高于loop！
KNN预测
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 = []
closest_y = self.y_train[np.argsort(dists[i,:])[:k]]# 排序
if np.shape(np.shape(closest_y))[0] !=1:
closest_y=np.squeeze(closest_y)
y_pred[i] = np.argmax(np.bincount(closest_y)) # 计数找出次数最多的标签
return y_pred
交叉验证
num_folds = 5
X_train_folds = np.array_split(X_train,num_folds)
y_train_folds = np.array_split(y_train,num_folds)
for k in k_choices:#find the best k-value
for i in range(num_folds):
X_train_cv = np.vstack(X_train_folds[:i]+X_train_folds[i+1:])
X_test_cv = X_train_folds[i]
y_train_cv = np.hstack(y_train_folds[:i]+y_train_folds[i+1:])
y_test_cv = y_train_folds[i]
# print(y_train_cv)
classifier.train(X_train_cv, y_train_cv)
dists_cv = classifier.compute_distances_no_loops(X_test_cv)
y_test_cv_pred = classifier.predict_labels(dists_cv, k)
num_correct = np.sum(y_test_cv_pred == y_test_cv)
accuracy = float(num_correct) / y_test_cv.shape[0]
# print(accuracy)
k_to_accuracies[k].append(accuracy)
参考
cs231课件
.
