DEV Community

Mateus Souza
Mateus Souza

Posted on

K-Nearest Neighbor implementado com Python + numpy

Conceito

K-nearest neighbor (kNN) é um algoritmo de Machine Learning supervisionado usado para classificação e regressão, em ambos os casos o funcionamento consiste em aproximar o dado de seus k exemplos mais similares contidos no dataset. [1]

  • Em caso de classificação o output será uma das labels que representa a classe do dado avaliado.
  • Em caso de regressão o output será um valor contendo a média dos valores dos k-nearest neighbors.

O kNN é simples de implementar, nenhum modelo estatístico é propriamente usado, durante a fase de treinamento, o dataset inteiro é armazenado em memória e o algoritmo utiliza aproximação para encontrar similaridades entre os dados de treino e de teste, realizando novas "observações". [2]

exemplo kNN

Para exemplificar o funcionamento do algoritmo, na imagem acima existem dois grupos de dados conhecidos (Grupo A e B), e um dado n. Considere que k seja igual a 3:

  • A aproximação entre n e cada dado presente no grupo A e B é calculado através de uma função de distância;
  • Em seguida, a lista é ordenada do menor para o maior (isso é feito para que os itens mais próximos de n fiquem no inicio da lista);
  • Os k primeiros itens da lista (vizinhos) são selecionados;
  • Em seguida, verifique qual label é a moda neste subconjunto, isto é: procure a label que mais aparece (no nosso caso seria Grupo A ou Grupo B) entre os k itens mais próximos de n.

Calculando a distância

O cálculo de distância aplicado [3] normalmente é

  • Manhattan distance (L1)

    d1(I1,I2)=pI1pI2pd_1(I_1, I_2) = \sum_{p}^{}|I^p_1 - I^p_2|
  • Euclidean distance (L2)

    d2(I1,I2)=p(I1pI2p)2d_2(I_1, I_2) = \sqrt[]{\sum_{p}^{}(I^p_1 - I^p_2)^2}

Image description

Escrevendo um pouco de código

Começando com a declaração da classe e o método de "treinamento", que é basicamente armazenar todo o dataset **.

import numpy as np
from collections import Counter


class KNearstNeighbor:

    def train(self, x_train, y_train):
        self.x_train = x_train
        self.y_train = y_train
Enter fullscreen mode Exit fullscreen mode

** No caso deste artigo usaremos o cifar10 (https://www.cs.toronto.edu/~kriz/cifar.html), um dataset que possui 60 mil imagens (50 mil de treino e 10 mil de teste) coloridas 32x32 sendo divididas entre classes como carro, avião, sapo, entre outras...

Em seguida, os métodos que realizam a predição, incluindo cálculo de distância e votação de labels (onde procura-se a label mais comúm entre os K neighbors):

...
    def predict(self, x_data, k=1):
        nearst_neighbors = []
        for x in x_data:
            distances_between_points = self.__euclidean_distance(
                point_a=x,
                points_b=self.x_train,
                labels_b=self.y_train)

            # sort by distance and carry label within
            sorted_distances = sorted(
                distances_between_points, key=lambda t: t[0])
            nearst_neighbors.append(
                sorted_distances[:k]
            )

        return self.__vote(nearst_neighbors)

     def __vote(self, nearst_neighbors):
        predicts = []
        for neighbors in nearst_neighbors:
            label_counter = Counter([neighbor[1] for neighbor in neighbors])
            [(predicted_label, _)] = label_counter.most_common(1)
            predicts.append([predicted_label])
        return predicts

    def __euclidean_distance(self, point_a, points_b, labels_b):
        distances = []
        size_points_b = len(points_b)
        for i in range(size_points_b):
            point = points_b[i]
            point_label = labels_b[i][0]

            distance = np.sqrt(np.sum(np.square(
                    point_a - point)))
            distances.append(
                (distance, point_label))
        return distances

    def evaluate(self, X_test, y_test, k=1):
        y_pred = self.predict(X_test, k)
        accuracy = sum(y_pred == y_test) / len(y_test)
        return accuracy
Enter fullscreen mode Exit fullscreen mode

Com a classe já definida, podemos baixar o cifar10 usando o keras datasets e realizar treinamento e testes:

from matplotlib import pyplot as plt
from keras.datasets import cifar10

def see_some_samples(traing_x):
    for i in range(9):
         plt.subplot(330 + 1 + i)
         plt.imshow(traing_x[i])
    plt.show()

# include indexes in array to separate by classes 
#Label  Description
#0  airplane
#1  automobile
#2  bird
#3  cat
#4  deer
#5  dog
#6  frog
#7  horse
#8  ship
#9  truck
classes_to_use = [0, 1]


(traing_x, traing_y), (test_x, test_y) = cifar10.load_data()
classes_training = np.isin(traing_y, classes_to_use).flatten()
classes_testing = np.isin(test_y, classes_to_use).flatten()
traing_x = traing_x[classes_training]
traing_y = traing_y[classes_training]
test_x = test_x[classes_testing]
test_y = test_y[classes_testing]

# limit samples at 500 to avoid evalute to get slow
# as KNN is quite slow
SAMPLES_COUNT = 500
traing_x = traing_x[:SAMPLES_COUNT]
traing_y = traing_y[:SAMPLES_COUNT]

test_x = test_x[:SAMPLES_COUNT]
test_y = test_y[:SAMPLES_COUNT]
see_some_samples(traing_x)
Enter fullscreen mode Exit fullscreen mode

Executando o script acima, é possível visualizar alguns exemplos do cifar10:
Image description

Em seguida, podemos realizar os testes:

knn_classifier = KNearstNeighbor()
knn_classifier.train(
    x_train=traing_x,
    y_train=traing_y)
accuracy = knn_classifier.evaluate(test_x, test_y, k=5)

print(f'accuracy was {round(accuracy[0], 2) * 100} %')
Enter fullscreen mode Exit fullscreen mode

No meu caso a acurácia obtida foi de 61%, o que é esperado de um algoritmo não muito inteligente realizando classificações imagens.
accuracy was 61.0 %

O código fonte está disponível aqui

Concluindo

  • kNN é um algoritmo bastante simples e conceitualmente interessante para iniciar em Machine Learning, porém também é bastante burro, sendo assim pode ser bem limitado :).

Referências

Wikipedia contributors. (2022, November 3). K-nearest neighbors algorithm. https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm [1]

Chapter 8 - Prediction in Text Mining: The Data Mining Algorithms of Predictive Analytics, Editor(s): Gary Miner, Dursun Delen, John Elder, Andrew Fast, Thomas Hill, Robert A. Nisbet, Practical Text Mining and Statistical Analysis for Non-structured Text Data Applications, Academic Press, 2012, Pages 893-919, ISBN 9780123869791, https://doi.org/10.1016/B978-0-12-386979-1.00036-0. (https://www.sciencedirect.com/science/article/pii/B9780123869791000360) [2]

Fei-Fei Li & Justin Johnson & Serena Yeung, Lecture Collection | Convolutional Neural Networks for Visual Recognition (Spring 2017), http://cs231n.stanford.edu/slides/2017/cs231n_2017_lecture2.pdf [3]

Top comments (0)