Modelos escaláveis aproximados para o cálculo do kNNG distribuído

• Processo: 22/04934-7
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de agosto de 2022
• Data de Término da vigência: 30 de novembro de 2023
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Metodologia e Técnicas da Computação
• Pesquisador responsável: Murilo Coelho Naldi
• Beneficiário: Gabriel Meirelles Carvalho Orlando
• Instituição Sede: Centro de Ciências Exatas e de Tecnologia (CCET). Universidade Federal de São Carlos (UFSCAR). São Carlos , SP, Brasil
• Bolsa(s) vinculada(s): 23/00993-1 - Investigação de KNNG paralelo rápido para estimativa de densidades múltiplas, BE.EP.IC
• Assunto(s): Aprendizado computacional Sistemas distribuídos Metodologia e técnicas de computação Estudo comparativo
• Palavra(s)-Chave do Pesquisador: Aprendizado de Máquina | Sistemas Distribuídos | Técnicas da Computação | Aprendizado de Máquina

Resumo

Encontrar o grafo dos K vizinhos mais próximos (do inglês k Nearest Neighbors Graph - kNNG) de um conjunto de dados é uma operação importante, usada em diversos algoritmos, como, por exemplo, algoritmos de agrupamento e de detecção de anomalias. Entretanto, essa operação é muito custosa, visto que, quando se calcula todos os k vizinhos de todos os pontos do conjunto, há uma complexidade quadrática em relação ao tamanho do conjunto de dados. Assim, há uma limitação física na execução destes algoritmos, visto que caso seja utilizado um volumosas quantidades de dados, o algoritmo tende a se tornar mais lento, dado a complexidade de memória e a complexidade de tempo. Devido a essa limitação, a existência de algoritmos de kNNG que constroem o grafo aproximado, mas, ao mesmo tempo, mantenham a qualidade e sejam escaláveis é muito importante. Logo, uma ideia que permite o comprimento destes requisitos é a distribuição e paralelização dos algoritmos que encontram o kNNG aproximado. Assim, para descobrir quais algoritmos que constroem o kNNG aproximado possuem os melhores resultados em termos de custo computacional e qualidade do resultado e possam ser paralelos e distribuídos é necessário realizar um estudo comparativo entre estes métodos. Este estudo engloba a comparação teórica, baseando-se na complexidade computacional dos algoritmos e a comparação prática, baseando-se na precisão do algoritmo, na acurácia e também na documentação das vantagens e desvantagens de cada algoritmo que constrói o kNNG aproximado. O resultado deste estudo será utilizado para otimizar algoritmos de agrupamento e de detecção de outliers, como, por exemplo, o HDBSCAN, que utiliza o processo de construir o kNNG em sua execução, e desse modo pode ser melhorado, caso for integrado com os algoritmos que encontra o kNNG aproximado de forma paralela e distribuída.(AU)