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 Ver menos

Abstract: Data clustering is widely recognized as a fundamental technique in pattern recognition and data mining, being extensively used in many fields of the sciences, business and engineering, covering a broad spectrum of applications. Currently, despite the large number of clustering methods, only a few of them take advantage of optimum connectivity between samples for more effective clustering. In this work, we present a graph-based data clustering framework, named Iterative Optimum-Path Forest (IOPF), that exploits optimum connectivity for the design of improved clustering methods. The IOPF framework consists of four fundamental components: (i) sampling of a seed set, (ii) partition of the graph induced from the dataset samples by an Optimum-Path Forest (OPF) rooted on the seed set, (iii) recomputation of the seed set based on the previous graph partition and, after multiple iterations of the last two steps, (iv) selection of the forest with the lowest total cost across all iterations. IOPF can be seen as a generalization of the Iterative Spanning Forest (ISF), a framework proposed for superpixel segmentation consisting of a sequence of Image Foresting Transforms (IFTs), from the image domain to the feature space. Moreover, we explore the use of dynamic arc-weight estimation, as the optimum-path trees grow - a strategy that has been demonstrated to provide more accurate delineation for superpixel segmentation and interactive object segmentation in recent works. In this context, our approach is employed to design improved clustering methods. We present four IOPF-based clustering solutions to illustrate distinct choices of its constituent components. These methods are subsequently used to address three different applications, namely, unsupervised object segmentation, road network analysis and clustering of two-dimensional synthetic datasets, in order to assess their effectiveness under various graph topologies and to ascertain their efficacy and robustness against competitive baselines. Furthermore, we introduce a seed selection procedure based on a sequence of OPF executions, which provides a suitable set of initial seeds that improve the accuracy of the IOPF-based methods Ver menos