[Stanford Univ: CS231n] Spring 2025 Assignment1. Q1(K-Nearest Neighbor Classifier)

본 포스팅은 Stanford University  School of Engineering의 CS231n: Convolutional Neural Networks for Visual Recognition을 수강하고 공부한 내용을 정리하기 위한 포스팅입니다.

 

https://github.com/cs231n/cs231n.github.io/blob/master/assignments/2025/assignment1.md

cs231n.github.io/assignments/2025/assignment1.md at master · cs231n/cs231n.github.io

 

https://youtu.be/DsGd2e9JNH4?si=O8lh9xG5djQMsJf4

 

https://github.com/KwonKiHyeok/cs231n

GitHub - KwonKiHyeok/cs231n: cs231n assignments

 

Q1: K-Nearest Neighbor classifier

 

def compute_distances_two_loops(self, X):
        num_test = X.shape[0]
        num_train = self.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.sqrt(np.sum((self.X_train[j] - X[i])**2))

        return dists

Inline Question 1

Notice the structured patterns in the distance matrix, where some rows or columns are visibly brighter. (Note that with the default color scheme black indicates low distances while white indicates high distances.)

• What in the data is the cause behind the distinctly bright rows?
• What causes the columns?

YourAnswer: First, we need to remember that in this distance matrix, the horizontal axis represents the size of the training data, and the vertical axis represents the size of the test data.

Answer 1: If a particular row in the distance matrix is generally bright, it means that the corresponding test data point has large distances from all training data points. This suggests that the test data is likely an outlier that is significantly different from the training data.

Answer 2: Similarly, if a particular column is generally bright, it means that the corresponding training data point has large distances from all test data points. Therefore, this indicates that the training data point is likely an outlier.

 

 

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]]
            y_pred[i] = np.argmax(np.bincount(closest_y))

        return y_pred

 

 

 

def compute_distances_one_loop(self, X):
        num_test = X.shape[0]
        num_train = self.X_train.shape[0]
        dists = np.zeros((num_test, num_train))

        for i in range(num_test):
          dists[i, :] = np.sqrt(np.sum((self.X_train - X[i])**2, axis = 1))
          
        return dists

 

def compute_distances_no_loops(self, X):
        num_test = X.shape[0]
        num_train = self.X_train.shape[0]
        dists = np.zeros((num_test, num_train))

        X_square = np.sum(X ** 2, axis = 1).reshape(-1, 1)
        train_square = np.sum(self.X_train ** 2, axis = 1).reshape(1, -1)
        X_dot_train = X.dot(self.X_train.T)

        dists = np.sqrt(X_square - 2 * X_dot_train + train_square)

        return dists

 

 

 

num_folds = 5
k_choices = [1, 3, 5, 8, 10, 12, 15, 20, 50, 100]

X_train_folds = []
y_train_folds = []

X_train_folds = np.array_split(X_train, num_folds)
y_train_folds = np.array_split(y_train, num_folds)

k_to_accuracies = {}

for k in k_choices:
  k_to_accuracies[k] = []
  for i in range(num_folds):

    x_val = X_train_folds[i]
    y_val = y_train_folds[i]
    x_train_fold = np.concatenate([X_train_folds[j] for j in range(num_folds) if j != i])
    y_train_fold = np.concatenate([y_train_folds[j] for j in range(num_folds) if j != i])

    
    classifier.train(x_train_fold, y_train_fold)
    y_pred_fold = classifier.predict(x_val, k = k, num_loops = 0)

    accuracy = float(np.mean(y_pred_fold == y_val))
    k_to_accuracies[k].append(accuracy)


# Print out the computed accuracies
for k in sorted(k_to_accuracies):
    for accuracy in k_to_accuracies[k]:
        print('k = %d, accuracy = %f' % (k, accuracy))

 

# Based on the cross-validation results above, choose the best value for k,
# retrain the classifier using all the training data, and test it on the test
# data. You should be able to get above 28% accuracy on the test data.
best_k = k_choices[accuracies_mean.argmax()]

classifier = KNearestNeighbor()
classifier.train(X_train, y_train)
y_test_pred = classifier.predict(X_test, k=best_k)

# Compute and display the accuracy
num_correct = np.sum(y_test_pred == y_test)
accuracy = float(num_correct) / num_test
print('Got %d / %d correct => accuracy: %f' % (num_correct, num_test, accuracy))

 

 

from builtins import range
from builtins import object
import numpy as np
from past.builtins import xrange


class KNearestNeighbor(object):

    def __init__(self):
        pass

    def train(self, X, y):
        self.X_train = X
        self.y_train = y

    def predict(self, X, k=1, num_loops=0):
        if num_loops == 0:
            dists = self.compute_distances_no_loops(X)
        elif num_loops == 1:
            dists = self.compute_distances_one_loop(X)
        elif num_loops == 2:
            dists = self.compute_distances_two_loops(X)
        else:
            raise ValueError("Invalid value %d for num_loops" % num_loops)

        return self.predict_labels(dists, k=k)

    def compute_distances_two_loops(self, X):
        num_test = X.shape[0]
        num_train = self.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.sqrt(np.sum(np.square((self.X_train[j] - X[i]))))

        return dists

    def compute_distances_one_loop(self, X):
        num_test = X.shape[0]
        num_train = self.X_train.shape[0]
        dists = np.zeros((num_test, num_train))

        for i in range(num_test):
          dists[i, :] = np.sqrt(np.sum((self.X_train - X[i])**2, axis = 1))
          
        return dists

    def compute_distances_no_loops(self, X):
        num_test = X.shape[0]
        num_train = self.X_train.shape[0]
        dists = np.zeros((num_test, num_train))

        X_square = np.sum(X ** 2, axis = 1).reshape(-1, 1)
        train_square = np.sum(self.X_train ** 2, axis = 1).reshape(1, -1)
        X_dot_train = X.dot(self.X_train.T)

        dists = np.sqrt(X_square - 2 * X_dot_train + train_square)

        return dists

    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]]
            y_pred[i] = np.argmax(np.bincount(closest_y))

        return y_pred