0

k nearest neighbour is useful algorithm to classify labels, and I have some queries about it.

If I have a train set(1000, 400), a test set(300, 400) and train labels (1000), how can I apply k nearest neighbour to find the right test lables? Also, by using numpy. Thank you!

ethereal
  • 1

2 Answers2

1

Assuming you have some basic understandment of numpy, this is some old code of mine for a KNN_classifier, anyway if you have any trouble using it or understanding it i can kindly explain it to you tommorow when i'll have some free time in case no one responds till then.

import numpy as np 
from sklearn.metrics import accuracy_score as accuracy


class Knn_classifier:
    
    def __init__(self, train_images, train_labels):
        self.train_images = train_images
        self.train_labels = train_labels
    
    def classify_image(self, test_image, num_neighbors=3, metric='l2'):
        if metric == 'l2':
            distances = np.sqrt(np.sum(
                np.square(self.train_images - test_image),
                axis = 1
            ))
            indexes = np.argsort(distances)
            indexes = indexes[:num_neighbors]
            labels = self.train_labels[indexes]
            label = np.argmax(np.bincount(labels))
        else:
            distances = np.sum(np.abs(self.train_images - test_image),axis = 1)
            indexes = np.argsort(distances)
            indexes = indexes[:num_neighbors]
            labels = self.train_labels[indexes]
            label = np.argmax(np.bincount(labels))

        return label 
    
    def classify_images(self, test_images, num_neighbors=3, metric='l2'):
        # write your code here
        labels = []
        for image in test_images:
            labels.append(self.classify_image(image,num_neighbors,metric))

        return labels
    
    def accuracy_score(self,predicted, ground_truth):
        return accuracy(predicted, ground_truth)*100


train_images = np.load('data/train_images.npy') # load training images
train_labels = np.load('data/train_labels.npy') # load training labels
test_images = np.load('data/test_images.npy') # load testing images
test_labels = np.load('data/test_labels.npy') # load testing labels


knn = Knn_classifier(train_images, train_labels)
predicted = knn.classify_images(test_images, metric='l1')
knn.accuracy_score(predicted,test_labels)

The shapes of my train.images and train_labels we're (1000, 784) and (1000,)

Rares
  • 58
  • 7
0

Here's a fully vectorized solution.

import numpy as np

(N_train, N_test, N_feats, N_labels, k) = (1000, 300, 400, 20, 5)

train_X = np.random.rand(N_train, N_feats)
train_y = np.random.randint(N_labels, size=N_train)
test_X = np.random.rand(N_test, N_feats)

# See: https://jaykmody.com/blog/distance-matrices-with-numpy/.
test_X2 = np.sum(test_X**2, axis=1, keepdims=True)
train_X2 = np.sum(train_X**2, axis=1)
test_train_X = test_X @ train_X.T
sq_dists = test_X2 - 2 * test_train_X + train_X2

k_nearest_neighbors = np.argsort(sq_dists, axis=1)[:, :k]
k_labels = train_y[k_nearest_neighbors]
# See: https://stackoverflow.com/a/71812803/1316276.
k_labels_onehot = k_labels[..., None] == np.arange(N_labels)[None, None, :]
pred_y = np.argmax(np.count_nonzero(k_labels_onehot, axis=1), axis=-1)
airalcorn2
  • 156
  • 1
  • 2
  • 15