参考文章:assignment1——KNN
KNN
测试时分别计算测试样本和训练集中的每个样本的距离,然后选取距离最近的k个样本的标签信息来进行分类。
方法1:Two Loops
for i in range(num_test):for j in range(num_train):dist = X[i, :] - self.X_train[j, :]dists[i, j] = np.sqrt(np.sum(np.power(dist, 2)))return dists
方法2:One Loop
利用numpy的广播机制,可同时计算一个测试集样本和所有训练集样本之间的距离。
for i in range(num_test):difference = X[i, :] - self.X_traindifference_squared_sum = np.sum(np.power(difference, 2), axis=1)dists[i, :] = np.sqrt(difference_squared_sum).Treturn dists
方法3:No Loops
dists = np.zeros(num_test, num_train)p = np.sum(X, axis=1, keepdims=True)
dists += np.tile(p, (1, num_train))q = np.sum(self.X_train, axis=1, keepdims=True).T
dists += np.tile(q, (num_test, 1))dists += -2 * X.dot(self.X_train.T)
dists = np.sqrt(dists)return dists
计算距离方法的运行时间对比:
方法1时间 > 方法2时间 > 方法3时间
所以编程时应当充分利用numpy的库特性,尽量使用向量化编程,不要使用for循环。
交叉验证选取最优的k:
使用函数np.split将训练集分成多个fold,然后使用np.vstack函数将多个fold合为本次的训练集。