Forem: Mateus Souza

K-Nearest Neighbor implementado com Python + numpy

Mateus Souza — Sun, 06 Nov 2022 12:35:00 +0000

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)

$d1(I1,I2)=∑p∣I1p−I2p∣d_1(I_1, I_2) = \sum_{p}^{}|I^p_1 - I^p_2|$
Euclidean distance (L2)

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

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]

Oracle Autonomous Database + Python3: criando database e conectando

Mateus Souza — Fri, 14 Oct 2022 07:05:11 +0000

Recentemente comecei a desenvolver um pequeno projeto que precisaria de um pequeno banco de dados, realmente pequeno: os registros seriam dicionários com duas ou três propriedades, algo como:

{
  foo: bar,
  zig: bee,
  created_at: sometime
}

Porém, desta vez não queria subir um banco de dados dentro de um container docker, por questões de economia de recurso: a aplicação por já consumiria as máquinas que o always free tier da Oracle Cloud disponibiliza.

Sendo assim, fui dar uma olhada para os outros recursos fornecidos pela Oracle, e entre eles, achei o Autonomous JSON Database, que entrega 20GB de armazenamento (não é muito, mas é 0800 :D) e acabei escolhendo como parte da stack do projetinho.

Criando o Banco de Dados

A criação é bem simples, no painel do OCI: Menu > Oracle Database > Autonomous JSON Database, em seguida basta clicar no botão de criação.

Realizando a conexão via código

A conexão via código deixa a desejar, é necessário fazer instalação de libs via pip, instalação de libs no Sistema Operacional, além de algumas configurações no Banco de Dados.

Permitindo conexões via TLS.

Primeiro é necessário permitir conexões TLS no Banco de dados:

Em seguida copie a string de conexão como TLS

Instalando dependências

Instale a biblioteca Python necessária:

pip install oracledb

Instale as bibliotecas no Sistema Operacional seguindo a documentação da Oracle (infelizmente para a maioria das distribuições em Linux a biblioteca não é disponibilizado em um gerenciador de pacotes)

Realize a conexão via código:

import oracledb

from settings import app_settings


class Database:

    def __init__(self) -> None:
        self.connection = oracledb.connect(
            user=app_settings.oci_database_user,
            password=app_settings.oci_database_password,
            dsn=app_settings.oci_database_connection_string,
            encoding=app_settings.oci_encoding
        )

    def get(self):
        cur =  self.connection.cursor()
        cur.execute("select sysdate from dual")
        res = cur.fetchall()
        for row in res:
            print(row)
        cur.close()

A execução desde código deverá ter sucesso:

$ python3 main.py 
(datetime.datetime(2022, 10, 14, 6, 29, 36),)

Referências

python-oracledb.readthedocs.io

blogs oracle

towardsdev

O Bubble Sort é ruim, mas tem algoritmo pior?

Mateus Souza — Sun, 26 Jun 2022 18:59:37 +0000

Se você já fez alguma matéria de algoritmos ou estrutura de dados, ou só brincou com ordenação, já deve ter ouvido falar de Bubble Sort: uma solução bastante ineficiente para o problema de ordenação.

Na verdade, existem várias outras soluções para este problema, mas resumidamente aqui está uma tabela comparando o tempo de complexidade de alguns algoritmos de ordenação:

Algoritmo	Execução
Bubble Sort	O(n^2)
Insertion Sort	O(n^2)
Selection Sort	O(n^2)
Heap Sort	O(n log_2 n)
Merge Sort	O(n log_2 n)
QuickSort	O(log2 n)

É bastante fácil de notar que de maneira geral os algoritmos de ordenação simples tem complexidade n^2, enquanto outros como Merge Sort n log_2 n, apesar da complexidade, cada um tem um desempenho melhor ou pior em cada caso. Mas...

Dá para ser tão pior que Bubble Sort?

A resposta curta: ✨ dá ✨

A resposta longa: existe um algoritmo chamado Stooge Sort. E ele funciona da seguinte maneira: sua lógica lembra o Bubble Sort, sempre faz a comparação de posições do arranjo em pares, e procurando o maior elemento, porém implementado de forma recursiva.

O pseudocódigo dessa criaturinha é o seguinte:

Se o valor do primeiro item for maior do que o último:
    trocar o primeiro e o último valor;

Se o arranjo possuir 3 elementos ou mais:
    recursivamente chamar stooge sort com os primeiros 2/3 do arranjo;
    recursivamente chamar stooge sort com os últimos 2/3 do arranjo;
    recursivamente chamar stooge sort com os primeiros 2/3 do arranjo;

retornar arranjo;

E sua implementação em C++ fica assim:

void stoogeSort(int arr[], int left, int right){
    if (left >= right) return;
    if (arr[left] > arr[right]) swap(arr[left], arr[right]);
    if ((right - left + 1) > 2){
        int t = floor((right - left + 1)/3);
        stoogeSort(arr, left, right - t);
        stoogeSort(arr, left + t, right);
        stoogeSort(arr, left, right - t);
    }
}

Sua complexidade é de O(n^2.7), e isso quer dizer que ele é pior que o Bubble Sort. Olhando para os números, não parece ter tanta diferença de O(n^2) e O(n^2.7), certo?

Bom, pode não parecer tão pior, mas para isso precisamos testar 😄.

Os testes

Os testes foram executados em uma máquina com as seguintes configurações:

LSB Version:    n/a
Distributor ID: ManjaroLinux
Description:    Manjaro Linux
Release:        21.2.6
Codename:       Qonos
-----------
Arquitetura:                  x86_64
  Modo(s) operacional da CPU: 32-bit, 64-bit
  Tamanhos de endereço:       43 bits physical, 48 bits virtual
  Ordem dos bytes:            Little Endian
CPU(s):                       6
  Lista de CPU(s) on-line:    0-5
ID de fornecedor:             AuthenticAMD
  Nome do modelo:             AMD Ryzen 5 3500X 6-Core Processor
    Família da CPU:           23
    Modelo:                   113
    Thread(s) per núcleo:     1
    Núcleo(s) por soquete:    6
    Soquete(s):               1
    Step:                     0
    Aumento de frequência:    habilitado
    CPU(s) scaling MHz:       87%
    CPU MHz máx.:             4520,8979
    CPU MHz mín.:             2200,0000
    BogoMIPS:                 7902.79
----------
MemTotal:       16356904 kB (a.k.a 16GB de ram :))

O plano era executar todos os algoritmos para os seguintes cenários: listas de 10, 100, 1000, 10.000, 100.000 e 1.000.000 números não repetidos e não ordenados. Porém o Stooge Sort não colaborou, você pode ver os resultados no Github em números reais, neste arquivo e também neste mas o que vale a pena mencionar é que para ordenar o arranjo de 100.000 números o Stooge Sort levou 155662 segundos, convertendo isso dá mais ou menos 43 horas (vale a pena mencionar que o tempo medido é de processador, não de relógio), e devido a isto, os testes foram realizados apenas até o arranjo de 100.000 números. O interessante é que o Bubble Sort que é bem ruim, levou apenas 32 segundos para ordenar o mesmo arranjo. É uma diferença enorme né?

Tendo dito isso, mostrar o gráfico comparando os tempos de todos os algoritmos é até sem graça... pois ele ficou um pouco esticado:

Basicamente o Stooge Sort é mais lento que todos os algoritmos na maioria dos cenários testados, e não é um pouco pior: na verdade é ridiculamente pior, apesar disso é um algoritmo interessante como objeto de estudo :), você pode ler mais sobre o Stooge Sort nas referências abaixo.

Referências
https://www.ijitee.org/wp-content/uploads/papers/v8i12/L31671081219.pdf

https://is.muni.cz/th/gp4gz/bc.pdf

https://www.geeksforgeeks.org/