20 ago 2021
10:00 Defesa de Mestrado Integralmente a distância
Tema
Floresta de Caminhos Ótimos Iterativa: Um Arcabouço para Agrupamento de Dados Baseado em Grafos
Aluno
David Aparco Cardenas
Orientador / Docente
Orientador: Pedro Jussieu de Rezende/ Coorientador: Alexandre Xavier Falcão
Breve resumo
Agrupamento de dados é amplamente reconhecido como uma técnica fundamental em reconhecimento de padrões e mineração de dados, sendo extensivamente utilizado em um vasto espectro de aplicações em diversos campos das ciências, negócios e engenharia. Atualmente, apesar do grande número de métodos de agrupamento já conhecidos, apenas um pequeno conjunto deles aproveita a conectividade ótima entre amostras visando obter um agrupamento mais efetivo. Neste trabalho, apresentamos um arcabouço para agrupamento de dados baseado em grafos, chamado Floresta de Caminhos Ótimos Iterativa (IOPF), a qual explora a conectividade ótima para o projeto de métodos de agrupamento aprimorados. O arcabouço IOPF consiste em quatro componentes fundamentais: (i) amostragem de um conjunto de sementes, (ii) partição do grafo induzido pelas amostras da base de dados através da Floresta de Caminhos Ótimos (OPF) enraizada no conjunto de sementes, (iii) recomputação do conjunto de sementes a partir de partição prévia do grafo e, após várias iterações das duas últimas etapas, (iv) seleção da floresta com o menor custo total entre todas as iterações. O arcabouço IOPF pode ser visto como uma generalização da Floresta Geradora Iterativa (ISF), uma metodologia proposta para segmentação de superpixels que consiste de uma sequência de Transformadas de Imagem-Floresta (IFTs), do domínio da imagem para o domínio do espaço de características. Além disso, exploramos o uso da estimação dinâmica de peso de arco enquanto as árvores de caminhos ótimos crescem -- uma estratégia que demonstrou fornecer um delineamento mais preciso para segmentação de superpixels e segmentação interativa de objetos em trabalhos recentes. Nesse contexto, a abordagem proposta é utilizada para projetar métodos de agrupamento aprimorados. Apresentamos quatro soluções de agrupamento baseadas no IOPF para ilustrar escolhas distintas de seus componentes constituintes. Esses métodos são subsequentemente usados na abordagem de três aplicações diferentes, a saber, segmentação de objetos não-supervisionada, análise de redes rodoviárias e agrupamento de bases de dados sintéticas bidimensionais, de modo a avaliar a efetividade dos métodos sob várias topologias de grafo, assim como para determinar sua eficácia e robustez quando comparados com baselines competitivos. Além disso, introduzimos um procedimento de seleção de sementes baseado em uma sequência de execuções do OPF, o qual fornece um conjunto apropriado de sementes iniciais que melhoram a precisão dos métodos baseados no IOPF.
Banca examinadora
Titulares:
Pedro Jussieu de Rezende IC/UNICAMP
Sandra Eliza Fontes de Avila IC/UNICAMP
Alexandru Cristian Telea Faculty of Science/Utrecht University
Suplentes:
João Paulo Papa FC/UNESP
Hélio Pedrini IC/UNICAMP