cs231n assignment1

2017-09-23

k-Nearest Neighbor classifier
1. compute distances
2. Cross-validation
  1. Split up the training data into folds
  2. Perform k-fold cross validation
参考

k-Nearest Neighbor classifier

compute distances

compute distances with two loops

思想很简单，但是耗时较长，代码如下。

import numpy as np
def compute_distances_two_loops(X,X_train):
    assert(X.shape[1]==X_train.shape[1])
    num_test=X.shape[0]
    num_train=X_train.shape[0]
    dists=np.zeros((num_test,num_train))
    for i in range(num_test):
        for j in range(num_train):
            dists[i][j]=np.linalg.norm(X[i,:]-X_train[j,:])
    return dists

compute distances with one loop

利用numpy.sum代替一个循环，但是在测试中比第一种方法更耗时。

def compute_distances_one_loop(X,X_train):
    assert(X.shape[1]==X_train.shape[1])
    num_test=X.shape[0]
    num_train=X_train.shape[0]
    dists=np.zeros((num_test,num_train))
    for i in range(num_test):
        dists[i,:]=np.linalg.norm(X[i,:]-X_train,axis=1)
    return dists

compute distances with no loop

利用矩阵运算代替循环，用时极短但是不容易理解。

def compute_distances_no_loop(X,X_train):
    assert(X.shape[1]==X_train.shape[1])
    num_test=X.shape[0]
    num_train=X_train.shape[0]
    dists=np.zeros((num_test,num_train))
    M=X.dot(X_train.T)
    te=np.square(X).sum(axis=1)
    tr=np.square(X_train).sum(axis=1)
    dists = np.sqrt(-2*M+tr+np.matrix(te).T)
    return dists

Cross-validation

Split up the training data into folds

1 2	y_train_ = y_train.reshape(-1, 1) X_train_folds , y_train_folds = np.array_split(X_train,num_folds),p.array_split(y_train_,num_folds)

Perform k-fold cross validation

for k_ in k_choices:
    k_to_accuracies.setdefault(k_, [])
for i in range(num_folds):
    classifier = KNearestNeighbor()
    X_val_train = np.vstack(X_train_folds[0:i] + X_train_folds[i+1:])
    y_val_train = np.vstack(y_train_folds[0:i] + y_train_folds[i+1:])
    y_val_train = y_val_train[:,0]
    classifier.train(X_val_train, y_val_train)
    for k_ in k_choices:
        y_val_pred = classifier.predict(X_train_folds[i], k=k_)
        num_correct = np.sum(y_val_pred == y_train_folds[i][:,0])
        accuracy = float(num_correct) / len(y_val_pred)
        k_to_accuracies[k_] = k_to_accuracies[k_] + [accuracy]

参考

完整代码
 Assignment1