PS: 本文默认已学习CS231N相关课程并掌握相关知识。

KNN的实验部分主要分为3大块内容：

• 计算测试集数据与训练集数据之间的距离，存放在dists矩阵中
• 用距离最近的K个标签，做classifier得到测试集label
• 交叉验证

接下来我们对这三部分进行探究

距离计算

实验中分别让我们用two-loops, one-loop和no-loop计算距离。

假设我们的训练集规模为 $ n * k $, 测试集规模为 $ m * k $, 那么计算距离的方法如下：

\[ dists[i][j] = \sqrt{\sum_{l=1}^k(test[i][l] - train[j][l])^2} \]

其中，dists为$ m * n $的矩阵

那么，two-loops的计算方法就呼之欲出了，就是对两个$ k $维向量计算距离：

1
2
3

for i in xrange(num_test):
  for j in xrange(num_train):
    dists[i][j] = np.sqrt(np.sum(np.square(X[i] - self.X_train[j])))

现在，我们考虑下one-loop的算法。对于测试集中每一个数据，都要与训练集中每个数据计算距离。其实我们可以利用numpy的broadcast,对每个测试集中的数据计算他到所有训练集数据的距离：

1
2

for i in xrange(num_test):
    dists[i] = np.sqrt(np.sum(np.square(X[i] - self.X_train), axis=1))

接下来，我们考虑no-loop的做法，这就需要用到一些矩阵运算的知识。我们将平方项展开:

在这里我们注意到, \({\sum_{l=1}^{k}{test[i][l] * train[j][l]}}\) 就是 \(test * train^T\) , 而 \(\sum_{l=1}^k{test[i][l]^2}\) 和 \(\sum_{l=1}^k{train[j][l]^2}\) 只是对矩阵中的 \(k\) 维向量求平方和，可以用numpy实现。代码如下：

1

dists = np.sqrt(-2*np.dot(X, self.X_train.T) + np.sum(np.square(self.X_train), axis = 1) + np.transpose([np.sum(np.square(X), axis = 1)]))

计算测试集label

在得到dists矩阵后，我们就可以计算测试集中每个样本的label。KNN算法就是获得距离样本最近的K个点，然后将这K个点中出现最多的label作为样本label：

1
2
3
4
5
6
7

# 获得最近的k个点标签
dist = np.argsort(dists[i])
for i in xrange(k):
    closest_y.append(self.y_train[dist[i]])
# 获得出现最多的label
y_pred[i] = np.argmax(np.bincount(closest_y))

交叉验证

交叉验证最主要的工作在于数据集的划分，实验中提供了np.array_split作为参考。实验中用了5-floder交叉验证。我们使用np.vstack将其他四份数据合在一起作为训练集，剩下一份作为验证集。

代码参考

• https://github.com/lightaime/cs231n