Anais > Edição Atual > Anais do XVII WCF 2021 > Um Estudo Experimental com um Algoritmo que Objetiva Acelerar o Algoritmo k-NN

Um Estudo Experimental com um Algoritmo que Objetiva Acelerar o Algoritmo k-NN

Autores: Raphael Lopes de Souza, Osvaldo Luiz de Oliveira

O k-NN – k-nearest neighbor – é um notável algoritmo utilizado em aplicações de Aprendizado de Máquina que envolvem, entre outras, reconhecimento de padrões, mineração de dados e raciocínio automatizado. Tendo como entradas uma instância x e um inteiro k ≥ 1, o k-NN envolve um processo de busca de k instâncias mais similares à instância x em um conjunto T de N ≥ 1 instâncias definidas por D ≥ 1 dimensões. Quando T possui grande número de instâncias e/ou grande dimensionalidade tal processo de busca tende a consumir muito tempo devido, principalmente a cálculos de funções de similaridade entre instâncias, geralmente utilizando a métrica descrita pela distância euclidiana entre instâncias. Diversas propostas têm sido feitas para reduzir o tempo de busca do algoritmo k-NN. Este artigo relata parte dos esforços de um trabalho em andamento que investiga algoritmos que objetivam reduzir o tempo de busca do algoritmo k-NN. Um destes algoritmos é conhecido como kMkNN. Especificamente este artigo relata os trabalhos de reprodução de um estudo experimental com o algoritmo kMkNN em que esse algoritmo é comparado com o algoritmo k-NN no que se refere ao tempo de busca. Os resultados dos experimentos reproduzidos são confrontados com os resultados dos experimentos publicados.

DOCUMENTO COMPLETO

• Um Estudo Experimental com um Algoritmo que Objetiva Acelerar o Algoritmo k-NN