Investigação de KNNG paralelo rápido para estimativa de densidades múltiplas

• Processo: 23/00993-1
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Iniciação Científica
• Data de Início da vigência: 30 de março de 2023
• Data de Término da vigência: 29 de julho de 2023
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Sistemas de Computação
• Pesquisador responsável: Murilo Coelho Naldi
• Beneficiário: Gabriel Meirelles Carvalho Orlando
• Supervisor: Joerg Sander
• Instituição Sede: Centro de Ciências Exatas e de Tecnologia (CCET). Universidade Federal de São Carlos (UFSCAR). São Carlos , SP, Brasil
• Instituição Anfitriã: University of Alberta, Canadá
• Vinculado à bolsa: 22/04934-7 - Modelos escaláveis aproximados para o cálculo do kNNG distribuído, BP.IC
• Assunto(s): Aprendizado computacional Computação paralela Agrupamento de dados
• Palavra(s)-Chave do Pesquisador: Approximate Methods | Density-Based Clustering | Massive Parallel Computing | Aprendizado de Máquina

Resumo

Agrupamento é uma tarefa de aprendizado de máquina não supervisionada essencial para várias aplicações. Dessa forma, alguns algoritmos precisam do Grafo dos k Vizinhos Mais Próximos (k NNG) como parte do agrupamento. No entanto, encontrar o k NNG pode ser uma operação computacionalmente custosa, pois calcular todos os k vizinhos de todos os pontos do conjunto são necessários, resultando em uma complexidade quadrática relativa o tamanho de um conjunto de dados. Além disso, devido à limitação física na execução desses algoritmos, se grandes conjuntos de dados forem usados, o algoritmo tende a se tornar inviável. Portanto, encontrar o k NNG aproximado de uma maneira menos custosa computacionalmente pode acelerar o agrupamento através de paralelismo e distribuição de dados, tornando o processo mais eficiente. Neste contexto, um algoritmo famoso de agrupamento é Hierarchical Density-Based Spatial Clustering of Applications with Noise - (HDBSCAN) constrói o k NNG sobre o espaço de alcance mútuo densidade de habilidades. No entanto, para conjuntos de dados massivos, HDBSCAN torna-se computacionalmente ineficiente. Portanto, é essencial construir o k NNG computacionalmente eficiente necessário para realizar o HDBSCAN de forma distribuída e paralela, mesmo que precise ser aproximado. Este projeto visa melhorar o desempenho computacional do HDBSCAN através métodos k NNG aproximados usando paralelismo e distribuição de dados, garantindo uma perda mínima de qualidade. (AU)