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]
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)
-
Euclidean distance (L2)
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
** 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
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)
Executando o script acima, é possível visualizar alguns exemplos do cifar10:
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} %')
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)