參考文章：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合為本次的訓練集。