K-Nearest Neighbor implementado com Python + numpy
Tags: machinelearning, python, datascience, todayilearned
Published: 2022-11-06 12:35:00

### 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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ahcbdzu7v4wi2hlupb28.jpg)

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)_
{% katex %}  d_1(I_1, I_2) = \sum_{p}^{}|I^p_1 - I^p_2| {% endkatex %}

- _Euclidean distance (L2)_
{% katex %}d_2(I_1, I_2) = \sqrt[]{\sum_{p}^{}(I^p_1 - I^p_2)^2}{% endkatex %}


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/78vag61othge3f8wj13d.png)

### 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 `**`.

```python
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
```
`** 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):

```python
...
    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
```

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

```python
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)
```
Executando o script acima, é possível visualizar alguns exemplos do cifar10:
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jah7bye083ix6qncooci.png)

Em seguida, podemos realizar os testes:
```python
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} %')
```

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](https://github.com/Mateusmsouza/ml-and-cnn/blob/main/classifiers/knn/knn.ipynb)

### 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]