Busca por vizinhos próximos de forma online

Resumo

A busca por vizinhos mais próximos (NNS) é uma das principais áreas de pesquisa em ciência da computação. O aprendizado de máquina utiliza algoritmos de NNS eficientes para acelerar algoritmos baseados em distância. No entanto, a maioria dos algoritmos de aprendizado incremental baseados em vizinhança ainda dependem de estratégias de busca por força bruta. Este projeto de pesquisa está focado principalmente no algoritmo online de k-vizinhos mais próximos (k-NN) baseado em janela deslizante. Esta família de algoritmos usa pouca memória, é conceitualmente simples e possui poucos hiperparâmetros para ajuste. Ainda assim, soluções baseadas em k-NN são fortes concorrentes em cenários de aprendizado incremental e são naturalmente robustos contra deriva de conceito. Uma desvantagem clara das implementações atuais de k-NN incremental é que buscas exaustivas devem ser realizadas na janela deslizante para cada nova amostra recebida. Portanto, dependendo do tamanho da janela de dados, o k-NN incremental pode se tornar muito ineficiente em termos de tempo de execução. A hipótese para este projeto é que as técnicas de clustering incremental e técnicas de NNS tradicionais podem ser adaptadas para acelerar os algoritmos k-NN incrementais. Objetiva-se desenvolver algoritmos k-NN incrementais eficientes no quesitos de tempo de processamento e uso de memória, sem incorrer perda significativa de acurácia preditiva. (AU)