前言

本文旨在学习和记录，如需转载，请附出处https://www.jianshu.com/p/ea566512b04f

KNN

原理

K近邻(K-nearest neighbor) 是一种基本的分类和回归的算法，在cs231中只介绍了分类算法。KNN分类算法的思想：给定一批带标签的数据作为训练数据，在对未知标签的数据进行分类时，根据其K个最近邻训练数据的标签，采取多数表决的方法进行预测。KNN中训练不花时间，预测时需要采取特定的距离的度量方式来进行最近邻的寻找，如果待预测的样本很多，其预测时间也会相应的增加。

距离度量

距离度量一般采取Minkowski距离，其公式为：
$L_{p}(x_{i},x_{j})=(\sum_{l=1}^{n}|x_{i}^{l}-x_{j}^{l}|^{p})^{1/p}$

二维空间中Lp距离.png

当p = 2时，就是我们常用的欧式距离；
当p = 1时，就是曼哈顿距离；
当p= $\infty$ 时，该距离就表示为各个坐标系中最大的距离：
$L_{\infty}=max_{l}|x_{i}^{l}-x_{j}^{l}|$
当然，还有许多距离，比如遥感应用中的光谱角距离，这里就不一一介绍了。

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)