Orientadores: Ricardo Ribeiro Gudwin, Cesar José Bonjuani Pagan / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-26T04:03:32Z (GMT). No. of bitstreams: 1 Angelo_TiagoNovaes_M.pdf: 3900207 bytes, checksum: 2eed8dd66c9bdc37e4d58e9eac614c9d (MD5) Previous issue date: 2014 / Resumo: O surgimento das Tecnologias de Comunicação e Informação trouxe uma nova perspectiva para o fortalecimento da democracia nas sociedades modernas. A democracia representativa, modelo predominante nas sociedades atuais, atravessa uma crise de credibilidade cuja principal consequência é o afastamento do cidadão na participação política, enfraquecendo os ideais democráticos. Neste contexto, a tecnologia surge como possibilidade para construção de um novo modelo de participação popular que resgate uma cidadania mais ativa, inaugurando o que denomina-se de democracia digital. O objetivo desta pesquisa foi desenvolver e implementar uma ferramenta, denominada "Extrator de Conhecimento Coletivo", com o propósito de conhecer o que um coletivo pensa a respeito de sua realidade a partir de pequenos relatos de seus participantes, dando voz à população num processo de democracia participativa. Os fundamentos teóricos baseiam-se em métodos de mineração de dados, sumarizadores extrativos e redes complexas. A ferramenta foi implementada e testada usando um banco de dados formado por opiniões de clientes a respeito de suas estadias em um Hotel. Os resultados apresentaram-se satisfatórios. Para trabalhos futuros, a proposta é que o Extrator de Conhecimento Coletivo seja o núcleo de processamento de dados de um espaço virtual onde a população pode se expressar e exercer ativamente sua cidadania / Abstract: The emergence of Information and Communication Technologies brought a new perspective to the strengthening of democracy in modern societies. The representative democracy, prevalent model in today's societies, crosses a crisis of credibility whose main consequence is the removal of citizen participation in politics, weakening democratic ideals. In this context, technology emerges as a possibility for construction of a new model of popular participation to rescue more active citizenship, inaugurating what is called digital democracy. The objective of this research was to develop and implement a tool called "Collective Knowledge Extractor", with the purpose of knowing what the collective thinks about his reality through small reports of its participants, giving voice to the people in a process participatory democracy. The theoretical foundations are based on methods of data mining, extractive summarizers and complex networks. The tool was implemented and tested using a database consisting of customer reviews about their stay in a Hotel. The results were satisfactory. For future work, the proposal is that the Extractor Collective Knowledge be the core data processing of a virtual space where people can express themselves and actively exercise their citizenship / Mestrado / Engenharia de Computação / Mestre em Engenharia Elétrica

A classificação é uma tarefa do aprendizado de máquina e mineração de dados, na qual um classificador é treinado sobre um conjunto de dados rotulados de forma que as classes de novos itens de dados possam ser preditas. Tradicionalmente, técnicas de classificação trabalham por definir fronteiras de decisão no espaço de dados considerando os atributos físicos do conjunto de treinamento e uma nova instância é classificada verificando sua posição relativa a tais fronteiras. Essa maneira de realizar a classificação, essencialmente baseada nos atributos físicos dos dados, impossibilita que as técnicas tradicionais sejam capazes de capturar relações semânticas existentes entre os dados, como, por exemplo, a formação de padrão. Por outro lado, o uso de redes complexas tem se apresentado como um caminho promissor para capturar relações espaciais, topológicas e funcionais dos dados, uma vez que a abstração da rede unifica a estrutura, a dinâmica e as funções do sistema representado. Dessa forma, o principal objetivo desta tese é o desenvolvimento de métodos e heurísticas baseadas em teorias de redes complexas para a classificação de dados. As principais contribuições envolvem os conceitos de conformidade de padrão, caracterização de importância e otimização estrutural de redes. Para a conformidade de padrão, onde medidas de redes complexas são usadas para estimar a concordância de um item de teste com a formação de padrão dos dados, é apresentada uma técnica híbrida simples pela qual associações físicas e topológicas são produzidas a partir da mesma rede. Para a caracterização de importância, é apresentada uma técnica que considera a importância individual dos itens de dado para determinar o rótulo de um item de teste. O conceito de importância aqui é definido em termos do PageRank, algoritmo usado na engine de busca do Google para definir a importância de páginas da web. Para a otimização estrutural de redes, é apresentado um framework bioinspirado capaz de construir a rede enquanto otimiza uma função de qualidade orientada à tarefa, como, por exemplo, classificação, redução de dimensionalidade, etc. A última investigação apresentada no documento explora a representação baseada em grafo e sua habilidade para detectar classes de distribuições arbitrárias na tarefa de difusão de papéis semânticos. Vários experimentos em bases de dados artificiais e reais, além de comparações com técnicas bastante usadas na literatura, são fornecidos em todas as investigações. Em suma, os resultados obtidos demonstram que as vantagens e novos conceitos propiciados pelo uso de redes se configuram em contribuições relevantes para as áreas de classificação, sistemas de aprendizado e redes complexas. / Data classification is a machine learning and data mining task in which a classifier is trained over a set of labeled data instances in such a way that the labels of new instances can be predicted. Traditionally, classification techniques define decision boundaries in the data space according to the physical features of a training set and a new data item is classified by verifying its relative position to the boundaries. Such kind of classification, which is only based on the physical attributes of the data, makes traditional techniques unable to detect semantic relationship existing among the data such as the pattern formation, for instance. On the other hand, recent works have shown the use of complex networks is a promissing way to capture spatial, topological and functional relationships of the data, as the network representation unifies structure, dynamic and functions of the networked system. In this thesis, the main objective is the development of methods and heuristics based on complex networks for data classification. The main contributions comprise the concepts of pattern conformation, data importance and network structural optimization. For pattern conformation, in which complex networks are employed to estimate the membership of a test item according to the data formation pattern, we present, in this thesis, a simple hybrid technique where physical and topological associations are produced from the same network. For data importance, we present a technique which considers the individual importance of the data items in order to determine the label of a given test item. The concept of importance here is derived from PageRank formulation, the ranking measure behind the Googles search engine used to calculate the importance of webpages. For network structural optimization, we present a bioinspired framework, which is able to build up the network while optimizing a task-oriented quality function such as classification, dimension reduction, etc. The last investigation presented in this thesis exploits the graph representation and its hability to detect classes of arbitrary distributions for the task of semantic role diffusion. In all investigations, a wide range of experiments in artificial and real-world data sets, and many comparisons with well-known and widely used techniques are also presented. In summary, the experimental results reveal that the advantages and new concepts provided by the use of networks represent relevant contributions to the areas of classification, learning systems and complex networks.

A teoria das redes complexas tem se tornado cada vez mais em uma poderosa teoria computacional capaz de representar, caracterizar e examinar sistemas com estrutura não trivial, revelando características intrínsecas locais e globais que facilitam a compreensão do comportamento e da dinâmica de tais sistemas. Nesta tese são exploradas as vantagens das redes complexas na resolução de problemas relacionados com tarefas do âmbito musical, especificamente, são estudadas três abordagens: reconhecimento de padrões, mineração e síntese de músicas. A primeira abordagem é desempenhada através do desenvolvimento de um método para a extração do padrão rítmico de uma peça musical de caráter popular. Nesse tipo de peças coexistem diferentes espécies de padrões rítmicos, os quais configuram uma hierarquia que é determinada por aspectos funcionais dentro da base rítmica. Os padrões rítmicos principais são caracterizados por sua maior incidência dentro do discurso musical, propriedade que é refletida na formação de comunidades dentro da rede. Técnicas de detecção de comunidades são aplicadas na extração dos padrões rítmicos, e uma medida para diferenciar os padrões principais dos secundários é proposta. Os resultados mostram que a qualidade da extração é sensível ao algoritmo de detecção, ao modo de representação do ritmo e ao tratamento dado às linhas de percussão na hora de gerar a rede. Uma fase de mineração foi desempenhada usando medidas topológicas sobre a rede obtida após a remoção dos padrões secundários. Técnicas de aprendizado supervisionado e não-supervisionado foram aplicadas para discriminar o gênero musical segundo os atributos calculados na fase de mineração. Os resultados revelam a eficiência da metodologia proposta, a qual foi constatada através de um teste de significância estatística. A última abordagem foi tratada mediante o desenvolvimento de modelos para a composição de melodias através de duas perspectivas, na primeira perspectiva é usada uma caminhada controlada por critérios sobre redes complexas predefinidas e na segunda redes neurais recorrentes e sistemas dinâmicos caóticos. Nesta última perspectiva, o modelo é treinado para compor uma melodia com um valor preestabelecido de alguma característica tonal subjetiva através de uma estratégia de controle proporcional que modifica a complexidade de uma melodia caótica, melodia que atua como entrada de inspiração da rede. / The theory of complex networks has become increasingly a powerful computational tool capable of representing, characterizing and examining systems with non-trivial structure, revealing both local and global intrinsic structures that facilitate the understanding of the behavior and dynamics of such systems. In this thesis, the virtues of complex networks in solving problems related to tasks within the musical scope are explored. Specifically, three approaches are studied: pattern recognition, data mining, and synthesis. The first perspective is addressed by developing a method for extracting the rhythmic pattern of a piece of popular music. In that type of musical pieces, there coexist different types of rhythm patterns which constitute a hierarchy determined by functional aspects within the basic rhythm. The main rhythmic patterns are characterized by a higher incidence within the musical discourse and this factor is reflected in the formation of communities within the network constructed from the music piece. Community detection techniques are applied in the extraction of rhythmic patterns, and a measure to distinguish the main patterns of the secondary is proposed. The results showed that the quality of extraction is sensitive to the detection algorithm, the method of representing rhythm, and treatment of percussion lines when generating the network. Data mining is performed using topological measures over the network obtained after the removal of secondary patterns. Techniques of supervised and unsupervised learning are applied to discriminate the musical genre according to the attributes calculated in the data mining phase. The quantitative results show the efficiency of the proposed methodology, which is confirmed by a test of statistical significance. Regarding the melody generation, an algorithm using a walk controlled by criteria on predefined complex networks has been developed, as well as the development of melody composition models using recurrent neural networks and chaotic dynamical systems. In the last approach, the model is trained to compose a melody with a subjective characteristic melodic value pre-established by a proportional control strategy that acts on the parameters of a chaotic melody as input inspiration.

Os avanços na pesquisa em biologia molecular e bioquímica permitiram o desenvolvimento de técnicas capazes de extrair informações moleculares de milhares de genes simultaneamente, como DNA Microarrays, SAGE e, mais recentemente RNA-Seq, gerando um volume massivo de dados biológicos. O mapeamento dos níveis de transcrição dos genes em larga escala é motivado pela proposição de que o estado funcional de um organismo é amplamente determinado pela expressão de seus genes. No entanto, o grande desafio enfrentado é o pequeno número de amostras (experimentos) com enorme dimensionalidade (genes). Dessa forma, se faz necessário o desenvolvimento de novas técnicas computacionais e estatísticas que reduzam o erro de estimação intrínseco cometido na presença de um pequeno número de amostras com enorme dimensionalidade. Neste contexto, um foco importante de pesquisa é a modelagem e identificação de redes de regulação gênica (GRNs) a partir desses dados de expressão. O objetivo central nesta pesquisa é inferir como os genes estão regulados, trazendo conhecimento sobre as interações moleculares e atividades metabólicas de um organismo. Tal conhecimento é fundamental para muitas aplicações, tais como o tratamento de doenças, estratégias de intervenção terapêutica e criação de novas drogas, bem como para o planejamento de novos experimentos. Nessa direção, este trabalho apresenta algumas contribuições: (1) software de seleção de características; (2) nova abordagem para a geração de Redes Gênicas Artificiais (AGNs); (3) função critério baseada na entropia de Tsallis; (4) estratégias alternativas de busca para a inferência de GRNs: SFFS-MR e SFFS-BA; (5) investigação biológica das redes gênicas envolvidas na biossíntese de tiamina, usando a Arabidopsis thaliana como planta modelo. O software de seleção de características consiste de um ambiente de código livre, gráfico e multiplataforma para problemas de bioinformática, que disponibiliza alguns algoritmos de seleção de características, funções critério e ferramentas de visualização gráfica. Em particular, implementa um método de inferência de GRNs baseado em seleção de características. Embora existam vários métodos propostos na literatura para a modelagem e identificação de GRNs, ainda há um problema muito importante em aberto: como validar as redes identificadas por esses métodos computacionais? Este trabalho apresenta uma nova abordagem para validação de tais algoritmos, considerando três aspectos principais: (a) Modelo para geração de Redes Gênicas Artificiais (AGNs), baseada em modelos teóricos de redes complexas, os quais são usados para simular perfis temporais de expressão gênica; (b) Método computacional para identificação de redes gênicas a partir de dados temporais de expressão; e (c) Validação das redes identificadas por meio do modelo AGN. O desenvolvimento do modelo AGN permitiu a análise e investigação das características de métodos de inferência de GRNs, levando ao desenvolvimento de um estudo comparativo entre quatro métodos disponíveis na literatura. A avaliação dos métodos de inferência levou ao desenvolvimento de novas metodologias para essa tarefa: (a) uma função critério, baseada na entropia de Tsallis, com objetivo de inferir os inter-relacionamentos gênicos com maior precisão; (b) uma estratégia alternativa de busca para a inferência de GRNs, chamada SFFS-MR, a qual tenta explorar uma característica local das interdependências regulatórias dos genes, conhecida como predição intrinsecamente multivariada; e (c) uma estratégia de busca, interativa e flutuante, que baseia-se na topologia de redes scale-free, como uma característica global das GRNs, considerada como uma informação a priori, com objetivo de oferecer um método mais adequado para essa classe de problemas e, com isso, obter resultados com maior precisão. Também é objetivo deste trabalho aplicar a metodologia desenvolvida em dados biológicos, em particular na identificação de GRNs relacionadas a funções específicas de Arabidopsis thaliana. Os resultados experimentais, obtidos a partir da aplicação das metodologias propostas, mostraram que os respectivos ganhos de desempenho foram significativos e adequados para os problemas a que foram propostos. / Thanks to recent advances in molecular biology and biochemistry, allied to an ever increasing amount of experimental data, the functional state of thousands of genes can now be extracted simultaneously by using methods such as DNA microarrays, SAGE, and more recently RNA-Seq, generating a massive volume of biological data. The mapping of gene transcription levels at large scale is motivated by the proposition that information of the functional state of an organism is broadly determined by its gene expression. However, the main limitation faced is the small number of samples (experiments) with huge dimensionalities (genes). Thus, it is necessary to develop new computational and statistics techniques to reduce the inherent estimation error committed in the presence of a small number of samples with large dimensionality. In this context, particularly important related investigations are the modeling and identification of gene regulatory networks from expression data sets. The main objective of this research is to infer how genes are regulated, bringing knowledge about the molecular interactions and metabolic activities of an organism. Such a knowledge is fundamental for many applications, such as disease treatment, therapeutic intervention strategies and drugs design, as well as for planning high-throughput new experiments. In this direction, this work presents some contributions: (1) feature selection software; (2) new approach for the generation of artificial gene networks (AGN); (3) criterion function based on Tsallis entropy; (4) alternative search strategies for GRNs inference: SFFS-MR and SFFS-BA; (5) biological investigation of GRNs involved in the thiamine biosynthesis by adopting the Arabidopsis thaliana as a model plant. The feature selection software is an open-source multiplataform graphical environment for bioinformatics problems, which supports many feature selection algorithms, criterion functions and graphic visualization tools. In particular, a feature selection method for GRNs inference is also implemented in the software. Although there are several methods proposed in the literature for the modeling and identification of GRNs, an important open problem regards: how to validate such methods and its results? This work presents a new approach for validation of such algorithms by considering three main aspects: (a) Artificial Gene Networks (AGNs) model generation through theoretical models of complex networks, which is used to simulate temporal expression data; (b) computational method for GRNs identification from temporal expression data; and (c) Validation of the identified AGN-based network through comparison with the original network. Through the development of the AGN model was possible the analysis and investigation of the characteristics of GRNs inference methods, leading to the development of a comparative study of four inference methods available in literature. The evaluation of inference methods led to the development of new methodologies for this task: (a) a new criterion function based on Tsallis entropy, in order to infer the genetic inter-relationships with better precision; (b) an alternative search strategy for the GRNs inference, called SFFS-MR, which tries to exploit a local property of the regulatory gene interdependencies, which is known as intrinsically multivariate prediction; and (c) a search strategy, interactive and floating, which is based on scale-free network topology, as a global property of the GRNs, which is considered as a priori information, in order to provide a more appropriate method for this class of problems and thereby achieve results with better precision. It is also an objective of this work, to apply the developed methodology in biological data, particularly in identifying GRNs related to specific functions of the Arabidopsis thaliana. The experimental results, obtained from the application of the proposed methodologies, indicate that the respective performances of each methodology were significant and adequate to the problems that have been proposed.

Extracting useful knowledge from data sets is a key concept in modern information systems. Consequently, the need of efficient techniques to extract the desired knowledge has been growing over time. Machine learning is a research field dedicated to the development of techniques capable of enabling a machine to \"learn\" from data. Many techniques have been proposed so far, but there are still issues to be unveiled specially in interdisciplinary research. In this thesis, we explore the advantages of network data representation to develop machine learning techniques based on dynamical processes on networks. The network representation unifies the structure, dynamics and functions of the system it represents, and thus is capable of capturing the spatial, topological and functional relations of the data sets under analysis. We develop network-based techniques for the three machine learning paradigms: supervised, semi-supervised and unsupervised. The random walk dynamical process is used to characterize the access of unlabeled data to data classes, configuring a new heuristic we call ease of access in the supervised paradigm. We also propose a classification technique which combines the high-level view of the data, via network topological characterization, and the low-level relations, via similarity measures, in a general framework. Still in the supervised setting, the modularity and Katz centrality network measures are applied to classify multiple observation sets, and an evolving network construction method is applied to the dimensionality reduction problem. The semi-supervised paradigm is covered by extending the ease of access heuristic to the cases in which just a few labeled data samples and many unlabeled samples are available. A semi-supervised technique based on interacting forces is also proposed, for which we provide parameter heuristics and stability analysis via a Lyapunov function. Finally, an unsupervised network-based technique uses the concepts of pinning control and consensus time from dynamical processes to derive a similarity measure used to cluster data. The data is represented by a connected and sparse network in which nodes are dynamical elements. Simulations on benchmark data sets and comparisons to well-known machine learning techniques are provided for all proposed techniques. Advantages of network data representation and dynamical processes for machine learning are highlighted in all cases / A extração de conhecimento útil a partir de conjuntos de dados é um conceito chave em sistemas de informação modernos. Por conseguinte, a necessidade de técnicas eficientes para extrair o conhecimento desejado vem crescendo ao longo do tempo. Aprendizado de máquina é uma área de pesquisa dedicada ao desenvolvimento de técnicas capazes de permitir que uma máquina \"aprenda\" a partir de conjuntos de dados. Muitas técnicas já foram propostas, mas ainda há questões a serem reveladas especialmente em pesquisas interdisciplinares. Nesta tese, exploramos as vantagens da representação de dados em rede para desenvolver técnicas de aprendizado de máquina baseadas em processos dinâmicos em redes. A representação em rede unifica a estrutura, a dinâmica e as funções do sistema representado e, portanto, é capaz de capturar as relações espaciais, topológicas e funcionais dos conjuntos de dados sob análise. Desenvolvemos técnicas baseadas em rede para os três paradigmas de aprendizado de máquina: supervisionado, semissupervisionado e não supervisionado. O processo dinâmico de passeio aleatório é utilizado para caracterizar o acesso de dados não rotulados às classes de dados configurando uma nova heurística no paradigma supervisionado, a qual chamamos de facilidade de acesso. Também propomos uma técnica de classificação de dados que combina a visão de alto nível dos dados, por meio da caracterização topológica de rede, com relações de baixo nível, por meio de medidas de similaridade, em uma estrutura geral. Ainda no aprendizado supervisionado, as medidas de rede modularidade e centralidade Katz são aplicadas para classificar conjuntos de múltiplas observações, e um método de construção evolutiva de rede é aplicado ao problema de redução de dimensionalidade. O paradigma semissupervisionado é abordado por meio da extensão da heurística de facilidade de acesso para os casos em que apenas algumas amostras de dados rotuladas e muitas amostras não rotuladas estão disponíveis. É também proposta uma técnica semissupervisionada baseada em forças de interação, para a qual fornecemos heurísticas para selecionar parâmetros e uma análise de estabilidade mediante uma função de Lyapunov. Finalmente, uma técnica não supervisionada baseada em rede utiliza os conceitos de controle pontual e tempo de consenso de processos dinâmicos para derivar uma medida de similaridade usada para agrupar dados. Os dados são representados por uma rede conectada e esparsa na qual os vértices são elementos dinâmicos. Simulações com dados de referência e comparações com técnicas de aprendizado de máquina conhecidas são fornecidos para todas as técnicas propostas. As vantagens da representação de dados em rede e de processos dinâmicos para o aprendizado de máquina são evidenciadas em todos os casos

Machine learning is evidenced as a research area with the main purpose of developing computational methods that are capable of learning with their previously acquired experiences. Although a large amount of machine learning techniques has been proposed and successfully applied in real systems, there are still many challenging issues, which need be addressed. In the last years, an increasing interest in techniques based on complex networks (large-scale graphs with nontrivial connection patterns) has been verified. This emergence is explained by the inherent advantages provided by the complex network representation, which is able to capture the spatial, topological and functional relations of the data. In this work, we investigate the new features and possible advantages offered by complex networks in the machine learning domain. In fact, we do show that the network-based approach really brings interesting features for supervised, semisupervised, and unsupervised learning. Specifically, we reformulate a previously proposed particle competition technique for both unsupervised and semisupervised learning using a stochastic nonlinear dynamical system. Moreover, an analytical analysis is supplied, which enables one to predict the behavior of the proposed technique. In addition to that, data reliability issues are explored in semisupervised learning. Such matter has practical importance and is found to be of little investigation in the literature. With the goal of validating these techniques for solving real problems, simulations on broadly accepted databases are conducted. Still in this work, we propose a hybrid supervised classification technique that combines both low and high orders of learning. The low level term can be implemented by any classification technique, while the high level term is realized by the extraction of features of the underlying network constructed from the input data. Thus, the former classifies the test instances by their physical features, while the latter measures the compliance of the test instances with the pattern formation of the data. Our study shows that the proposed technique not only can realize classification according to the semantic meaning of the data, but also is able to improve the performance of traditional classification techniques. Finally, it is expected that this study will contribute, in a relevant manner, to the machine learning area / Aprendizado de máquina figura-se como uma área de pesquisa que visa a desenvolver métodos computacionais capazes de aprender com a experiência. Embora uma grande quantidade de técnicas de aprendizado de máquina foi proposta e aplicada, com sucesso, em sistemas reais, existem ainda inúmeros problemas desafiantes que necessitam ser explorados. Nos últimos anos, um crescente interesse em técnicas baseadas em redes complexas (grafos de larga escala com padrões de conexão não triviais) foi verificado. Essa emergência é explicada pelas inerentes vantagens que a representação em redes complexas traz, sendo capazes de capturar as relações espaciais, topológicas e funcionais dos dados. Nesta tese, serão investigadas as possíveis vantagens oferecidas por redes complexas quando utilizadas no domínio de aprendizado de máquina. De fato, será mostrado que a abordagem por redes realmente proporciona melhorias nos aprendizados supervisionado, semissupervisionado e não supervisionado. Especificamente, será reformulada uma técnica de competição de partículas para o aprendizado não supervisionado e semissupervisionado por meio da utilização de um sistema dinâmico estocástico não linear. Em complemento, uma análise analítica de tal modelo será desenvolvida, permitindo o entendimento evolucional do modelo no tempo. Além disso, a questão de confiabilidade de dados será investigada no aprendizado semissupervisionado. Tal tópico tem importância prática e é pouco estudado na literatura. Com o objetivo de validar essas técnicas em problemas reais, simulações computacionais em bases de dados consagradas pela literatura serão conduzidas. Ainda nesse trabalho, será proposta uma técnica híbrica de classificação supervisionada que combina tanto o aprendizado de baixo como de alto nível. O termo de baixo nível pode ser implementado por qualquer técnica de classificação tradicional, enquanto que o termo de alto nível é realizado pela extração das características de uma rede construída a partir dos dados de entrada. Nesse contexto, aquele classifica as instâncias de teste segundo qualidades físicas, enquanto que esse estima a conformidade da instância de teste com a formação de padrões dos dados. Os estudos aqui desenvolvidos mostram que o método proposto pode melhorar o desempenho de técnicas tradicionais de classificação, além de permitir uma classificação de acordo com o significado semântico dos dados. Enfim, acredita-se que este estudo possa gerar contribuições relevantes para a área de aprendizado de máquina.

O presente texto descreve a tese de doutorado intitulada Análise de Formas usando Wavelets em Grafos. O tema está relacionado à área de Visão Computacional, particularmente aos tópicos de Caracterização, Descrição e Classificação de Formas. Dentre os métodos da extensa literatura em Análise de Formas 2D, percebe-se uma presença menor daqueles baseados em grafos com topologia arbitrária e irregular. As contribuições desta tese procuram preencher esta lacuna. É proposta uma metodologia baseada no seguinte pipeline : (i) Amostragem da forma, (ii) Estruturação das amostras em grafos, (iii) Função-base definida nos vértices, (iv) Análise multiescala de grafos por meio da Transformada Wavelet Espectral em grafos, (v) Extração de Características da Transformada Wavelet e (vi) Discriminação. Para cada uma das etapas (i), (ii), (iii), (v) e (vi), são inúmeras as abordagens possíveis. Um dos desafios é encontrar uma combinação de abordagens, dentre as muitas alternativas, que resulte em um pipeline eficaz para nossos propósitos. Em particular, para a etapa (iii), dado um grafo que representa uma forma, o desafio é identificar uma característica associada às amostras que possa ser definida sobre os vértices do grafo. Esta característica deve capturar a influência subjacente da estrutura combinatória de toda a rede sobre cada vértice, em diversas escalas. A Transformada Wavelet Espectral sobre os Grafos revelará esta influência subjacente em cada vértice. São apresentados resultados obtidos de experimentos usando formas 2D de benchmarks conhecidos na literatura, bem como de experimentos de aplicações em astronomia para análise de formas de galáxias do Sloan Digital Sky Survey não-rotuladas e rotuladas pelo projeto Galaxy Zoo 2 , demonstrando o sucesso da técnica proposta, comparada a abordagens clássicas como Transformada de Fourier e Transformada Wavelet Contínua 2D. / This document describes the PhD thesis entitled Shape Analysis by using Wavelets on Graphs. The addressed theme is related to Computer Vision, particularly to the Characterization, Description and Classication topics. Amongst the methods presented in an extensive literature on Shape Analysis 2D, it is perceived a smaller presence of graph-based methods with arbitrary and irregular topologies. The contributions of this thesis aim at fullling this gap. A methodology based on the following pipeline is proposed: (i) Shape sampling, (ii) Samples structuring in graphs, (iii) Function dened on vertices, (iv) Multiscale analysis of graphs through the Spectral Wavelet Transform, (v) Features extraction from the Wavelet Transforms and (vi) Classication. For the stages (i), (ii), (iii), (v) and (vi), there are numerous possible approaches. One great challenge is to nd a proper combination of approaches from the several available alternatives, which may be able to yield an eective pipeline for our purposes. In particular, for the stage (iii), given a graph representing a shape, the challenge is to identify a feature, which may be dened over the graph vertices. This feature should capture the underlying inuence from the combinatorial structure of the entire network over each vertex, in multiple scales. The Spectral Graph Wavelet Transform will reveal such an underpining inuence over each vertex. Yielded results from experiments on 2D benchmarks shapes widely known in literature, as well as results from astronomy applications to the analysis of unlabeled galaxies shapes from the Sloan Digital Sky Survey and labeled galaxies shapes by the Galaxy Zoo 2 Project are presented, demonstrating the achievements of the proposed technique, in comparison to classic approaches such as the 2D Fourier Transform and the 2D Continuous Wavelet Transform.

Neste trabalho, foram utilizadas técnicas e conceitos tipicamente encontrados em estudos de Redes Complexas, uma sub-área da Física Estatística, para caracterizar a Internet e sua evolução em uma década, de 1998 a 2007. Foi considerada como unidade básica de análise, a estrutura Sistema Autônomo. Nesta caracterização, foram utilizadas várias ferramentas computacionais desenvolvidas em linguagem C/C++, que permitiram classificar, simular e modelar propriedades dinâmicas. Dentre estas propriedades podemos destacar o coeficiente de conectividade, fundamental para os estudos topológicos, e o parâmetro menor caminho médio, ambos baseados nas propriedades da matriz adjacência. Os dados experimentais foram inicialmente obtidos nos roteadores de borda da RedeRio de Computadores - FAPERJ e posteriormente, os dados relativos ao intervalo de estudo, foram retirados da base de dados disponibilizada pela Universidade de Oregon. Foi proposto um modelo de crescimento de uma rede complexa baseado nas premissas de crescimento contínuo e conexão preferencial não linear com suporte aos mecanismos de rearranjo e novas conexões entre nós já existentes. Este modelo se mostrou bastante adequado no estudo das propriedades consideradas. Foi desenvolvido um método para cálculo do menor caminho médio que apresentou performance superior àqueles normalmente utilizados pela comunidade acadêmica. O comportamento da topologia sob o ponto de vista da distribuição de probabilidades de conexão e do ranque de conectividade, apresentaram comportamento linear constante no período estudado com coeficientes médios iguais a -2,0 e -0,93, respectivamente. O parâmetro menor caminho médio global da Internet permaneceu praticamente inalterado e igual a 4, 2 ao longo da década estudada. / Connection networks are observed in many areas of human knowledge. The characterization and topological studies of these networks may be performed through distribution of connectivity degrees, rank properties, shortest path length between nodes, adjacency matrix etc, typical concepts from Complex networks, a filed of study of Statistical Physics domain. In this thesis we characterize the Internet connections evolution from 1998 to 2007. The Internet may be seen under several levels of reach and complexity considering different basic units. A wide vision is to consider the Internet basic element as an Autonomous System - AS, which is defined as a cluster of LANs or routers submitted to the same policy of usage, connectivity and technically administrated by the same network management group. The complex network considered in this work is composed by Autonomous Systems (vertices) and the established tra connection (edges) between them obtained from the BGP routing table. Many interesting property of this networks is analyzed, e.g. degree distribution (the rank and outdegree exponents) from 1998 to 2007 and the shortest path length (L), obtained by a proposed computational method (Friburgo algorithm) among each pair of ASs represented in the adjacency matrix. Finally, we present the behavior of the power law function and the shortest path length of the Internet for each year. Simulations of the connections network were carried out by a proposed model developed from continuous growth premises, possibilities of new and rearranging connections. This model was based on the concept of potential preferable connection showing a stable exponential factor that reproduces the true shortest path parameter over the decade.

O presente texto descreve a tese de doutorado intitulada Análise de Formas usando Wavelets em Grafos. O tema está relacionado à área de Visão Computacional, particularmente aos tópicos de Caracterização, Descrição e Classificação de Formas. Dentre os métodos da extensa literatura em Análise de Formas 2D, percebe-se uma presença menor daqueles baseados em grafos com topologia arbitrária e irregular. As contribuições desta tese procuram preencher esta lacuna. É proposta uma metodologia baseada no seguinte pipeline : (i) Amostragem da forma, (ii) Estruturação das amostras em grafos, (iii) Função-base definida nos vértices, (iv) Análise multiescala de grafos por meio da Transformada Wavelet Espectral em grafos, (v) Extração de Características da Transformada Wavelet e (vi) Discriminação. Para cada uma das etapas (i), (ii), (iii), (v) e (vi), são inúmeras as abordagens possíveis. Um dos desafios é encontrar uma combinação de abordagens, dentre as muitas alternativas, que resulte em um pipeline eficaz para nossos propósitos. Em particular, para a etapa (iii), dado um grafo que representa uma forma, o desafio é identificar uma característica associada às amostras que possa ser definida sobre os vértices do grafo. Esta característica deve capturar a influência subjacente da estrutura combinatória de toda a rede sobre cada vértice, em diversas escalas. A Transformada Wavelet Espectral sobre os Grafos revelará esta influência subjacente em cada vértice. São apresentados resultados obtidos de experimentos usando formas 2D de benchmarks conhecidos na literatura, bem como de experimentos de aplicações em astronomia para análise de formas de galáxias do Sloan Digital Sky Survey não-rotuladas e rotuladas pelo projeto Galaxy Zoo 2 , demonstrando o sucesso da técnica proposta, comparada a abordagens clássicas como Transformada de Fourier e Transformada Wavelet Contínua 2D. / This document describes the PhD thesis entitled Shape Analysis by using Wavelets on Graphs. The addressed theme is related to Computer Vision, particularly to the Characterization, Description and Classication topics. Amongst the methods presented in an extensive literature on Shape Analysis 2D, it is perceived a smaller presence of graph-based methods with arbitrary and irregular topologies. The contributions of this thesis aim at fullling this gap. A methodology based on the following pipeline is proposed: (i) Shape sampling, (ii) Samples structuring in graphs, (iii) Function dened on vertices, (iv) Multiscale analysis of graphs through the Spectral Wavelet Transform, (v) Features extraction from the Wavelet Transforms and (vi) Classication. For the stages (i), (ii), (iii), (v) and (vi), there are numerous possible approaches. One great challenge is to nd a proper combination of approaches from the several available alternatives, which may be able to yield an eective pipeline for our purposes. In particular, for the stage (iii), given a graph representing a shape, the challenge is to identify a feature, which may be dened over the graph vertices. This feature should capture the underlying inuence from the combinatorial structure of the entire network over each vertex, in multiple scales. The Spectral Graph Wavelet Transform will reveal such an underpining inuence over each vertex. Yielded results from experiments on 2D benchmarks shapes widely known in literature, as well as results from astronomy applications to the analysis of unlabeled galaxies shapes from the Sloan Digital Sky Survey and labeled galaxies shapes by the Galaxy Zoo 2 Project are presented, demonstrating the achievements of the proposed technique, in comparison to classic approaches such as the 2D Fourier Transform and the 2D Continuous Wavelet Transform.

Neste trabalho, foram utilizadas técnicas e conceitos tipicamente encontrados em estudos de Redes Complexas, uma sub-área da Física Estatística, para caracterizar a Internet e sua evolução em uma década, de 1998 a 2007. Foi considerada como unidade básica de análise, a estrutura Sistema Autônomo. Nesta caracterização, foram utilizadas várias ferramentas computacionais desenvolvidas em linguagem C/C++, que permitiram classificar, simular e modelar propriedades dinâmicas. Dentre estas propriedades podemos destacar o coeficiente de conectividade, fundamental para os estudos topológicos, e o parâmetro menor caminho médio, ambos baseados nas propriedades da matriz adjacência. Os dados experimentais foram inicialmente obtidos nos roteadores de borda da RedeRio de Computadores - FAPERJ e posteriormente, os dados relativos ao intervalo de estudo, foram retirados da base de dados disponibilizada pela Universidade de Oregon. Foi proposto um modelo de crescimento de uma rede complexa baseado nas premissas de crescimento contínuo e conexão preferencial não linear com suporte aos mecanismos de rearranjo e novas conexões entre nós já existentes. Este modelo se mostrou bastante adequado no estudo das propriedades consideradas. Foi desenvolvido um método para cálculo do menor caminho médio que apresentou performance superior àqueles normalmente utilizados pela comunidade acadêmica. O comportamento da topologia sob o ponto de vista da distribuição de probabilidades de conexão e do ranque de conectividade, apresentaram comportamento linear constante no período estudado com coeficientes médios iguais a -2,0 e -0,93, respectivamente. O parâmetro menor caminho médio global da Internet permaneceu praticamente inalterado e igual a 4, 2 ao longo da década estudada. / Connection networks are observed in many areas of human knowledge. The characterization and topological studies of these networks may be performed through distribution of connectivity degrees, rank properties, shortest path length between nodes, adjacency matrix etc, typical concepts from Complex networks, a filed of study of Statistical Physics domain. In this thesis we characterize the Internet connections evolution from 1998 to 2007. The Internet may be seen under several levels of reach and complexity considering different basic units. A wide vision is to consider the Internet basic element as an Autonomous System - AS, which is defined as a cluster of LANs or routers submitted to the same policy of usage, connectivity and technically administrated by the same network management group. The complex network considered in this work is composed by Autonomous Systems (vertices) and the established tra connection (edges) between them obtained from the BGP routing table. Many interesting property of this networks is analyzed, e.g. degree distribution (the rank and outdegree exponents) from 1998 to 2007 and the shortest path length (L), obtained by a proposed computational method (Friburgo algorithm) among each pair of ASs represented in the adjacency matrix. Finally, we present the behavior of the power law function and the shortest path length of the Internet for each year. Simulations of the connections network were carried out by a proposed model developed from continuous growth premises, possibilities of new and rearranging connections. This model was based on the concept of potential preferable connection showing a stable exponential factor that reproduces the true shortest path parameter over the decade.