Defesa de Mestrado de Adán Echemendía Montero

Título do Trabalho
A Divide-and-Conquer Clustering Approach based on Optimum-Path Forest
Candidato(a)
Adán Echemendía Montero
Nível
Mestrado
Data
Add to Calender 2018-05-25 00:00:00 2018-05-25 00:00:00 Defesa de Mestrado de Adán Echemendía Montero A Divide-and-Conquer Clustering Approach based on Optimum-Path Forest Sala 85 IC 2 INSTITUTO DE COMPUTAÇÃO mauroesc@ic.unicamp.br America/Sao_Paulo public
Horário
16:00
Local
Sala 85 IC 2
Orientador(a)
Alexandre Xavier Falcão
Banca Examinadora

Condição

Titulares  -  Professores Doutores

Unidade/Instituição

Presidente

Alexandre Xavier Falcão

IC/UNICAMP

Membro

Luciano Silva

DInf/UFPR

Membro

João Paulo Papa

FC/UNESP

 

Condição

Suplentes  -  Professores Doutores

Unidade/Instituição

Suplente

Helio Pedrini

IC/UNICAMP

Suplente

Moacir Antonelli Ponti

ICMC/USP

Resumo

O agrupamento de dados é um dos principais desafios em problemas de Ciência de Dados. Apesar do seu progresso científico em quase um século de existência, desde sua aparição em Antropologia (por Driver and Kroeber, 1932), algoritmos de agrupamento ainda falham na identificação de grupos (\emph{clusters}) naturalmente relacionados com a semântica do problema. Ademais, os avanços das tecnologias de aquisição, comunicação, e armazenamento de dados acrescentam desafios cruciais com o aumento considerável de dados, os quais não são tratados pela maioria das técnicas. Essas questões são endereçadas neste trabalho através da proposta de uma abordagem de divisão e conquista para uma técnica de agrupamento única em encontrar um grupo por domo da função de densidade de probabilidade dos dados --- o algoritmo de agrupamento por floresta de caminhos ótimos (OPF - \emph{Optimum Path Forest}). Nesta técnica, amostras são interpretadas como nodos de um grafo cujos arcos conectam os $k$-vizinhos mais próximos no espaço de características. Os nodos são ponderados pela densidade de probabilidade deles e um mapa de conexidade é maximizado de modo que cada máximo da função densidade de probabilidade se torna a raiz de uma árvore de caminhos ótimos (grupo). O melhor valor de $k$ é estimado por otimização em um intervalo de valores dependente da aplicação. O problema com este método é que um número alto de amostras torna o algoritmo inviável, devido ao espaço de memória necessário para armazenar o grafo e o tempo computacional para encontrar o melhor valor de $k$. Visto que as soluções existentes levam a resultados ineficazes, este trabalho revisita o problema através da proposta de uma abordagem de divisão e conquista com dois níveis. No primeiro nível, o conjunto de dados é dividido em subconjuntos (blocos) menores e as amostras pertencentes a cada bloco são agrupadas pelo algoritmo OPF. Em seguida, as amostras representativas de cada grupo (mais especificamente as raízes da floresta de caminhos ótimos) são levadas ao segundo nível, onde elas são agrupadas novamente. Finalmente, os rótulos de grupo obtidos no segundo nível são transferidos para todas as amostras do conjunto de dados através de seus representantes do primeiro nível. Nesta abordagem, todas as amostras, ou pelo menos muitas amostras, podem ser usadas no processo de aprendizado não supervisionado, sem afetar a eficácia do agrupamento e, portanto, o procedimento é menos susceptível a perda de informação relevante ao agrupamento. Os resultados mostram agrupamentos satisfatórios em dois cenários, segmentação de imagem e agrupamento de dados arbitrários, tendo como base a comparação com abordagens populares. No primeiro cenário, a abordagem proposta atinge os melhores resultados em todas as bases de imagem testadas. No segundo cenário, os resultados são similares aos obtidos por uma versão otimizada do método original de agrupamento por floresta de caminhos ótimos.
\textbf{Palavras-chave}: agrupamento, floresta de caminhos ótimos, segmentação de imagem, transformada imagem-floresta, paradigma de divisão e conquista, aprendizado de máquina.