%0 Thesis
%4 sid.inpe.br/mtc-m21c/2019/08.14.01.42
%2 sid.inpe.br/mtc-m21c/2019/08.14.01.42.26
%T Rede protótipo: um algoritmo para agrupamento de fluxo de dados baseado em redes complexas
%J Prototype network: an algorithm for data stream clustering based on complex networks
%D 2019
%8 2019-08-21
%9 Tese (Doutorado em Computação Aplicada)
%P 133
%A Porto, Sandy Moreira,
%E Vijaykumar, Nandamudi Lankalapalli (presidente),
%E Quiles, Marcos Gonçalves (orientador),
%E Macau, Elbert Einstein Nehrer,
%E Lorena, Ana Carolina,
%E Basgalupp, Márcio Porto,
%I Instituto Nacional de Pesquisas Espaciais (INPE)
%C São José dos Campos
%K Fluxo de dados, redes complexas, agrupamento, MODIS, observação da Terra, data streams, complex network, clustering, Earth observing.
%X Fluxo de dados são um novo conceito surgido a partir do grande avanço tecnológico das últimas décadas. Data streams, como são chamados em inglês, são sequências de objetos que são gerados em tempo real e, portanto, trazem desafios únicos aos algoritmos que pretendem processá-los. Este trabalho está concentrado na tarefa de analisar os objetos que chegam com intuito de agrupá-los em conjuntos similares. Como os fluxos tendem ao infinito e, geralmente, os dados chegam com rapidez, os algoritmos de agrupamento para este tipo de dado, diferentemente das técnicas tradicionais, tem que desempenhar seus papéis com restrições quanto ao espaço de armazenamento e tempo de processamento que limitam sua atuação. Além disso, o algoritmo a tratar esses dados deve estar preparado para lidar com mudanças e evoluções no conceito dos dados ao longo do tempo. A metodologia apresentada neste trabalho, nomeada Rede Protótipo, utiliza uma estrutura de dados baseada em Redes Complexas para armazenar um sumário inteligente dos dados do fluxo, inteligente porque ao mesmo tempo que agrupa os dados em conjuntos similares, consegue acompanhar os movimentos de conceito sem maiores interferências do usuário. A proposta deste trabalho tem como maior vantagem a dependência de apenas dois parâmetros, MAXV e H, sendo que o primeiro define a quantidade máxima de vértices da rede e o segundo a quantidade de dados recentes do fluxo a serem considerados. Os experimentos relatados nesta tese avaliam o desempenho da Rede Protótipo contra algoritmos clássicos na tarefa de agrupamento de fluxos como CluStream e DenStream, mas também contra outros algoritmos também baseados em Redes Complexas. Os algoritmos são testados com dados sintéticos que simulam mudanças e evoluções de conceito, além de dados provenientes de imagens de Observação da Terra, que se mostraram ainda mais desafiadores para os algoritmos de agrupamento de fluxo de dados. ABSTRACT: Data streams are a new concept that emerged from the significant technological advances of the last decades. Those data are sequences of objects that are generated in real-time and therefore pose unique challenges to the algorithms that intend to process them. This work is focused on the task of analyzing the objects that arrive with the intent of group them into similar sets. Since data streams tend to infinity and data usually arrive quickly, clustering algorithms for this type of data, unlike traditional techniques, have to play their role with storage space and processing time constraints that limit their performance. In addition, the algorithm handling this data must be prepared to deal with changes and developments in the concept of data over time. The methodology presented in this thesis, called Prototype Network, uses a data structure based on Complex Networks to store an intelligent data stream summary, intelligent because while grouping the data into similar sets, it can follow the concept movements without major user interference. The purpose of this work has the most significant advantage of relying on only two parameters, MAXV and H, the first one defining the maximum amount of network vertices and the second the amount of recent stream data to be considered. The experiments reported in this thesis evaluate the performance of the Prototype Network against classical algorithms in the clustering task such as CluStream and DenStream, but also against other algorithms also based on Complex Networks. The algorithms are tested with synthetic data that simulate concept changes and evolution, as well as data from Earth Observation images, which have proven to be even more challenging for data streams clustering algorithms.
%@language pt
%3 publicacao.pdf