361 |
Texture analysis using complex system models: fractal dimension, swarm systems and non-linear diffusion / Análise de texturas usando sistemas complexos: dimensão fractal, multiagentes e difusão não-linearBruno Brandoli Machado 18 April 2016 (has links)
Texture is one of the primary visual attributes used to describe patterns found in nature. Several texture analysis methods have been used as powerful tools for real applications involving analysis and computer vision. However, existing methods do not successfully discriminate the complexity of texture patterns. Such methods disregard the possibility of describing image structures by means of measures such as the fractal dimension. Fractality-based measures allow a non-integer geometric interpretation with applications in areas such as mathematics, physics, and biology. With this gap in mind, the central hypothesis of this thesis is that textures can be described as irregular fractal surfaces due to their complex geometry; such geometry can be exploited for image analysis and computer vision. By exploring such possibilities, pushing the limits of the state-of-the-art, this thesis starts with an analysis of texture features achieved by means of agents on image surfaces. To do so, we used the Bouligand-Minkowski fractal dimension, swarm-system Artificial Crawlers, and non-linear diffusion of Perona-Malik, techniques that led to methodologies with efficacy and efficiency comparable to the state-of-the-art. Our first method combines fractal dimension with random walks on the surface of images. In a second approach, non-linear diffusion is used to represent texture images at different scales, which are described via their fractal dimension for image classification purposes. In a third proposal, we employ fractal dimension concepts over multiple scales derived from the same image for a richer texture description. One of the purposes is the automatic detection of diseases in soybean leaves. Finally, texture characteristics were exploited in a method based on complex networks used to analyze the agglomeration of particles in nanotechnology images. The results achieved in the four methodologies described in this thesis demonstrated the potential of using texture features in tasks of classification and pattern recognition. The contributions of this work shall support significant advances in materials engineering, computer vision, and agriculture. / A textura é um dos principais atributos visuais para a descrição de padrões encontrados na natureza. Diversos métodos de análise de textura têm sido usados como uma poderosa ferramenta para aplicações reais que envolvem análise de imagens e visão computacional. Entretanto, os métodos existentes não conseguem discriminar com sucesso a complexidade dos padrões de textura. Tais métodos desconsideram a possibilidade de se descrever estruturas de imagens por meio de medidas como a dimensão fractal. Medidas baseadas em fractalidade permitem uma interpretação geométrica não-inteira que possui aplicações encontradas em áreas como matemática, física, e biologia. Sobre esta lacuna metodológica, a hipótese central desta tese é que texturas presentes na natureza podem ser medidas como superfícies fractais irregulares devido à sua geometria complexa, o que pode ser explorado para fins de análise de imagens e visão computacional. Para superar tais limitações, avançando o estado da arte, esta tese se inicia com uma análise das características de texturas baseada em caminhadas aleatórias de agentes sobre superfícies de imagens. Esta primeira análise leva a um método que combina dimensão fractal com caminhadas de agentes sobre a superfície de imagens. Em uma segunda abordagem, usa-se a difusão não-linear para representar imagens de texturas em diferentes escalas, as quais são descritas via dimensão fractal para fins de classificação de imagens. Em uma terceira proposta, emprega-se a dimensão fractal sobre múltiplas escalas derivadas de uma mesma imagem com o propósito de se realizar a descrição multi-escala de texturas. Um dos propósitos específicos foi a detecção automática de doenças em folhas de soja. Por último, as características de textura foram exploradas segundo uma metodologia baseada em redes complexas para análise de aglomeração de partículas em imagens de nanotecnologia. Os resultados alcançados nesta tese demonstraram o potencial do uso de características de textura. Para tanto foram usadas técnicas de dimensão fractal de Bouligand-Minkowski, multiagentes Artificial Crawlerse difusão não-linear de Perona-Malik, os quais alcançaram eficácia e eficiência comparáveis ao do estado da arte. As contribuições obtidas devem suportar avanços significativos nas áreas de engenharia de materiais, visão computacional, e agricultura.
|
362 |
Propriedades de redes complexas de telecomunicações / Properties of complex networks telecommunicationsArturo Miranda Vera 08 December 2011 (has links)
Os objetivos desta monografia foram analisar as propriedades de topologias de redes complexas, analisar as potencialidades e comparar desempenho de softwares gratuitos de geração de topologias e simular roteamento de tráfego em redes de telecomunicações. As principais topologias analisadas foram a regular, aleatória e livre de escala. As propriedades topológicas incluem o grau nodal, a distribuição de grau, o coeficiente de agrupamento, o comprimento médio do caminho, além do efeito mundo pequeno. Foram avaliadas as potencialidades de três ferramentas gratuitas de geração e análise de redes, o B-A, Pajek e NetLogo. Como exemplos de aplicação em redes de telecomunicações, com destaque para redes ópticas utilizando técnica de multiplexação por divisão de comprimento de onda, foram implementados os seguintes algoritmos de roteamento de tráfego: roteamento fixo com alocação de comprimento de onda sequencial fixa e roteamento adaptativo com alocação de comprimento de onda menos usado, mais usado, aleatória e busca exaustiva. O desempenho dos algoritmos de roteamento e alocação de comprimentos de onda de modo nas topologias analisadas foram comparados. / The purposes of this master\'s thesis are to analyze the properties of complex network topologies, analyze and compare the performance of free software for generating topologies and simulate traffic routing in telecommunication networks. The main topologies analyzed were the regular, random and scale-free. The topological properties include the nodal degree, the distribution degree, clustering coefficient, average path length and small-world effect. The performance of the free softwares B-A, Pajek and Netlogo were evaluated. As examples of application in telecommunication networks, especially for optical networks using wavelength division multiplexing technique, the following routing traffic algorithms were implemented: Fixed routing with first-fit wavelength assignment and adaptive routing with least used wavelength assignment, most used, random and exhaustive search. The performance of algorithms for routing and wavelength allocation employed in the analyzed topologies was compared.
|
363 |
O modelo de Sznajd em redes complexas / Sznajd model in complex networksFabio Stucchi Vannucchi 31 August 2006 (has links)
Esta dissertação apresenta um estudo detalhado do comportamento do modelo de Sznajd, um modelo de interações microscópicas entre sítios empregado com freqüência para representar o processo de formação de opinião em uma comunidade. Neste modelo cada sítio tentará convencer seus vizinhos a assumir o mesmo estado em que está, com uma regra que privilegia a existência de pares de sítios já em um mesmo estado, ou seja, caso um par de vizinhos esteja no mesmo estado, a probabilidade dos outros vizinhos assumirem este estado será maior. Analisamos o papel das condições iniciais do sistema (particularmente do grau dos eleitores iniciais) e tentamos, através de representações gráficas e outros métodos, enteder que caracteríticas determinam o resultado final do processo. Os resultados previstos pelo modelo na rede de Barabási-Albert são também comparados com dados obtidos no TRE para eleições para casas legislativas brasileiras, e generalizamos o método da estimação via máxima verossimilhança para o caso em que a distribuição apresenta efeitos de tamanho finito nos dois extremos. Estudamos também os resultados de duas alterações da dinâmica do modelo, ainda na rede de Barabási-Albert. Na primeira, inserimos inomogeneidades na rede (que podem ser, por exemplo, cabos eleitorais) e vemos como a introdução destes defeitos na rede afetam o resultado final. Na segunda estudamos como a introdução de uma influência externa, não local, (que mimetizaria, por exemplo, a campanha publicitária) afeta a dinâmica, e encontramos uma transição de fase de primeira ordem no comportamento do sistema. As previsões da aproximação de campo médio para o modelo com ruído, por nós desenvolvida, descrevem qualitativamente bem a transição. Por fim, investigamos a influência de alterações na rede em que se dá a dinâmica do modelo, utilizando reticulados, cadeias regulares e a rede de Watts-Strogatz. Comparamos o comportamento do modelo nessas redes com a dinâmica de Glauber a temperatura nula e com o modelo do votante. / This work studies in detail the Szajd model, a dynamical model based on microscopic local interactions between sites, usually employed to simulate rumor spreading and opinion formation in a community.
|
364 |
Topological stability and textual differentiation in human interaction networks: statistical analysis, visualization and linked data / Estabilidade topológica e diferenciação textual em redes de interação humana: análise estatística, visualização e dados ligadosRenato Fabbri 08 May 2017 (has links)
This work reports on stable (or invariant) topological properties and textual differentiation in human interaction networks, with benchmarks derived from public email lists. Activity along time and topology were observed in snapshots in a timeline, and at different scales. Our analysis shows that activity is practically the same for all networks across timescales ranging from seconds to months. The principal components of the participants in the topological metrics space remain practically unchanged as different sets of messages are considered. The activity of participants follows the expected scale-free outline, thus yielding the hub, intermediary and peripheral classes of vertices by comparison against the Erdös-Rényi model. The relative sizes of these three sectors are essentially the same for all email lists and the same along time. Typically, 3-12% of the vertices are hubs, 15-45% are intermediary and 44-81% are peripheral vertices. Texts from each of such sectors are shown to be very different through direct measurements and through an adaptation of the Kolmogorov-Smirnov test. These properties are consistent with the literature and may be general for human interaction networks, which has important implications for establishing a typology of participants based on quantitative criteria. For guiding and supporting this research, we also developed a visualization method of dynamic networks through animations. To facilitate verification and further steps in the analyses, we supply a linked data representation of data related to our results. / Este trabalho relata propriedades topológicas estáveis (ou invariantes) e diferenciação textual em redes de interação humana, com referências derivadas de listas públicas de e-mail. A atividade ao longo do tempo e a topologia foram observadas em instantâneos ao longo de uma linha do tempo e em diferentes escalas. A análise mostra que a atividade é praticamente a mesma para todas as redes em escalas temporais de segundos a meses. As componentes principais dos participantes no espaço das métricas topológicas mantêm-se praticamente inalteradas quando diferentes conjuntos de mensagens são considerados. A atividade dos participantes segue o esperado perfil livre de escala, produzindo, assim, as classes de vértices dos hubs, dos intermediários e dos periféricos em comparação com o modelo Erdös-Rényi. Os tamanhos relativos destes três setores são essencialmente os mesmos para todas as listas de e-mail e ao longo do tempo. Normalmente, 3-12% dos vértices são hubs, 15-45% são intermediários e 44-81% são vértices periféricos. Os textos de cada um destes setores são considerados muito diferentes através de uma adaptação dos testes de Kolmogorov-Smirnov. Estas propriedades são consistentes com a literatura e podem ser gerais para redes de interação humana, o que tem implicações importantes para o estabelecimento de uma tipologia dos participantes com base em critérios quantitativos. De modo a guiar e apoiar esta pesquisa, também desenvolvemos um método de visualização para redes dinâmicas através de animações. Para facilitar a verificação e passos seguintes nas análises, fornecemos uma representação em dados ligados dos dados relacionados aos nossos resultados.
|
365 |
Collective dynamics in complex networks for machine learning / Dinâmica coletiva em redes complexas para aprendizado de máquinaFilipe Alves Neto Verri 19 March 2018 (has links)
Machine learning enables machines to learn automatically from data. In literature, graph-based methods have received increasing attention due to their ability to learn from both local and global information. In these methods, each data instance is represented by a vertex and is linked to other vertices according to a predefined affinity rule. However, they usually have unfeasible time cost for large problems. To overcome this problem, techniques can employ a heuristic to find suboptimal solutions in a feasible time. Early heuristic optimization methods exploit nature-inspired collective processes, such as ants looking for food sources and swarms of bees. Nowadays, advances in the field of complex systems provide powerful tools to assess and to understand dynamical systems. Complex networks, which are graphs with nontrivial topology, are among these theoretical tools capable of describing the interplay of topology, structure, and dynamics of complex systems. Therefore, machine learning methods based on complex networks and collective dynamics have been proposed. They encompass three steps. First, a complex network is constructed from the input data. Then, the simulation of a distributed collective system in the network generates rich information. Finally, the collected information is used to solve the learning problem. The coordination of the individuals in the system permit to achieve dynamics that is far more complex than the behavior of single individuals. In this research, I have explored collective dynamics in machine learning tasks, both in unsupervised and semi-supervised scenarios. Specifically, I have proposed a new collective system of competing particles that shifts the traditional vertex-centric dynamics to a more informative edge-centric one. Moreover, it is the first particle competition system applied in machine learning task that has deterministic behavior. Results show several advantages of the edge-centric model, including the ability to acquire more information about overlapping areas, a better exploration behavior, and a faster convergence time. Also, I have proposed a new network formation technique that is not based on similarity and has low computational cost. Since addition and removal of samples in the network is cheap, it can be used in real-time application. Finally, I have conducted analytical investigations of a flocking-like system that was needed to guarantee the expected behavior in community detection tasks. In conclusion, the result of the research contributes to many areas of machine learning and complex systems. / Aprendizado de máquina permite que computadores aprendam automaticamente dos dados. Na literatura, métodos baseados em grafos recebem crescente atenção por serem capazes de aprender através de informações locais e globais. Nestes métodos, cada item de dado é um vértice e as conexões são dadas uma regra de afinidade. Todavia, tais técnicas possuem custo de tempo impraticável para grandes grafos. O uso de heurísticas supera este problema, encontrando soluções subótimas em tempo factível. No início, alguns métodos de otimização inspiraram suas heurísticas em processos naturais coletivos, como formigas procurando por comida e enxames de abelhas. Atualmente, os avanços na área de sistemas complexos provêm ferramentas para medir e entender estes sistemas. Redes complexas, as quais são grafos com topologia não trivial, são uma das ferramentas. Elas são capazes de descrever as relações entre topologia, estrutura e dinâmica de sistemas complexos. Deste modo, novos métodos de aprendizado baseados em redes complexas e dinâmica coletiva vêm surgindo. Eles atuam em três passos. Primeiro, uma rede complexa é construída da entrada. Então, simula-se um sistema coletivo distribuído na rede para obter informações. Enfim, a informação coletada é utilizada para resolver o problema. A interação entre indivíduos no sistema permite alcançar uma dinâmica muito mais complexa do que o comportamento individual. Nesta pesquisa, estudei o uso de dinâmica coletiva em problemas de aprendizado de máquina, tanto em casos não supervisionados como semissupervisionados. Especificamente, propus um novo sistema de competição de partículas cuja competição ocorre em arestas ao invés de vértices, aumentando a informação do sistema. Ainda, o sistema proposto é o primeiro modelo de competição de partículas aplicado em aprendizado de máquina com comportamento determinístico. Resultados comprovam várias vantagens do modelo em arestas, includindo detecção de áreas sobrepostas, melhor exploração do espaço e convergência mais rápida. Além disso, apresento uma nova técnica de formação de redes que não é baseada na similaridade dos dados e possui baixa complexidade computational. Uma vez que o custo de inserção e remoção de exemplos na rede é barato, o método pode ser aplicado em aplicações de tempo real. Finalmente, conduzi um estudo analítico em um sistema de alinhamento de partículas. O estudo foi necessário para garantir o comportamento esperado na aplicação do sistema em problemas de detecção de comunidades. Em suma, os resultados da pesquisa contribuíram para várias áreas de aprendizado de máquina e sistemas complexos.
|
366 |
Alterações topológicas para reduzir a propagação de falhas na rede elétrica de alta tensão brasileira / Topological changes to prevent failure propagation on the Brazilian power transmission linesPaiva, William Roberto de, 1986- 24 August 2018 (has links)
Orientadores: André Franceshi de Angelis, José Geraldo Pena de Andrade / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Tecnologia / Made available in DSpace on 2018-08-24T15:13:51Z (GMT). No. of bitstreams: 1
Paiva_WilliamRobertode_M.pdf: 3222455 bytes, checksum: 4ba3e5407135ec1d8483e94ec4c11749 (MD5)
Previous issue date: 2014 / Resumo: Neste trabalho, propõe-se a avaliação de quatro métodos que possam melhorar a resiliência de redes de alta tensão através da adição de linhas de transmissão, utilizando-se a Teoria das Redes Complexas. Criou-se um modelo da rede brasileira de geração e transmissão de energia elétrica em forma de grafo para testar os métodos. O primeiro deles consiste em ligar pares de vértices que possuam menor grau em toda a rede. O segundo liga os vértices de menor betweenness. O terceiro efetua ligações entre pares de vértices de menor grau que estejam ligados aos vértices de maior carga em toda a rede. O último, faz ligações entre os dois vértices de betweenness mediano. Todos os métodos foram testados com e sem o auxílio do procedimento "min-cut", capaz de identificar as arestas que, ao serem removidas, dividem a rede em duas sub-redes, permitindo assim efetuar ligações que reduzam o risco dessa divisão. Além dos testes no modelo da rede brasileira, utilizaram-se também 1000 redes Scale-Free e 1000 aleatórias para verificar o aumento de eficiência trazidos. Todos os métodos foram capazes de aumentar a eficiência, tanto no modelo da rede real quanto nos modelos artificiais. A estratégia de ligar os vértices de betweenness mediano com auxílio do min-cut trouxe o maior aumento. A resiliência da rede, diante de falhas planejadas e falhas aleatórias, foi aumentada em poucos casos, porém, em nenhum houve redução da mesma. Conclui-se que as estratégias propostas podem ser utilizadas para melhorar a eficiência de redes de alta tensão, mantendo ou aumentando sua resiliência, bem como podem ser usadas para trazer os mesmos atributos para redes complexas em geral / Abstract: In this work we purpose to assess four methods to improve high-voltage networks resilience against failures and attacks, using the Complex Network Theory to do it. To test these methods, we created a network model in graph format, based on the Brazilian generation and transmission electrical network. The first of these methods consist in to link pairs of nodes which have the lowest degree in the network. The second creates a link betweenn the lowest betweenness nodes. The third method is to link the two lowest degree nodes which are linked to the highest load nodes. The last one creates a link betweenn the two nodes which has the median betweenness. All methods were tested with and without the use of the "min-cut" procedure. This procedure finds the lowest number of necessary links that, when removed, divide the network in two sub-networks. It allows us to identify these links and reduce the risk of this partitioning the network by adding new links. We also test the strategies in 1000 artificial Scale-Free networks and 1000 artificial Random networks to validate those methods. All strategies were able to increase efficiency, in the real and artificial networks models. The strategy which links the median betweenness nodes using the "min-cut" procedure brought the best results. The network resilience against planned and random failures was increased in in few cases, but no decreases was registered. We conclude that our strategies can be used to improve high-voltage network efficiency, keeping or improving its resilience, as they can be used to bring the same attribute to any type of complex networks / Mestrado / Tecnologia e Inovação / Mestre em Tecnologia
|
367 |
Abordagem de resolução de problemas complexos orientada aos princípios de processo / Approach to complex problem solvinmg oriented toward the principles of processGonçalves, Caio Márcio, 1963- 24 August 2018 (has links)
Orientador: André Munhoz de Argollo Ferrão / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Civil, Arquitetura e Urbanismo / Made available in DSpace on 2018-08-24T02:42:02Z (GMT). No. of bitstreams: 1
Goncalves_CaioMarcio_D.pdf: 5196417 bytes, checksum: 1b5a11393ecc1446ad09d0f9dc71f419 (MD5)
Previous issue date: 2013 / Resumo: Os métodos, técnicas e abordagens clássicas de identificação e caracterização de problema parecem não satisfazer e responder plena e prontamente aos problemas complexos da sociedade contemporânea. A complexidade dos problemas atuais requer a adoção de ferramentas inovadoras, centradas no problema e não em efeitos ou soluções pré-concebidas. O desenvolvimento da humanidade é um processo empreendedor das sociedades que a compõem e deve estar orientado ao ser humano e seu contexto. Esse escopo enfatiza a noção de processo, da possibilidade, da lógica difusa, do complexo, do transdisciplinar, bem como o emprego de estratégias investigativas, inclusive do tipo pesquisa-ação. O propósito da pesquisa converge para um tipo de engenharia social que visa a definição de elementos estratégicos para a definição de uma abordagem voltada para a real identificação do problema. A "Abordagem de Resolução de Problema Complexo Orientada aos Princípios de Processo" [ARPCOOP] é o resultado da pesquisa e está fundamentada no arcabouço teórico existente sobre resolução de problema e nos princípios da visão de mundo em processo, lançando luzes sobre o problema e não sobre a solução / Abstract: The methods, techniques, and classical approaches for the identification and characterization of a problem does not seem to neither please, nor fully answer the complex problems of contemporary society in a speedy manner. The complexity of today's problems requires the adoption of innovative tools, problem-centered rather than in effects or preconceived solutions. The human development is an entrepreneurial process by the comprising societies, and should be directed to the human being and its context. This scope emphasizes the notion of process, the complex, the trans disciplinary, as well as the use of strategic action research investigations. The purpose of the research converges to a type of social engineering aimed at defining strategic elements to form an approach directed at identifying the real problem. Known as "The Approach to Complex Problem Solving Oriented toward the Principles of Process" [ARPCOOP], the proposal is based on existing theoretical framework of a problem and on the principles of the world view in the process, casting light on the problem and not the solution / Doutorado / Recursos Hidricos, Energeticos e Ambientais / Doutor em Engenharia Civil
|
368 |
Réseaux et signal : des outils de traitement du signal pour l'analyse des réseaux / Networks and signal : signal processing tools for network analysisTremblay, Nicolas 09 October 2014 (has links)
Cette thèse propose de nouveaux outils adaptés à l'analyse des réseaux : sociaux, de transport, de neurones, de protéines, de télécommunications... Ces réseaux, avec l'essor de certaines technologies électroniques, informatiques et mobiles, sont de plus en plus mesurables et mesurés ; la demande d'outils d'analyse assez génériques pour s'appliquer à ces réseaux de natures différentes, assez puissants pour gérer leur grande taille et assez pertinents pour en extraire l'information utile, augmente en conséquence. Pour répondre à cette demande, une grande communauté de chercheurs de différents horizons scientifiques concentre ses efforts sur l'analyse des graphes, des outils mathématiques modélisant la structure relationnelle des objets d'un réseau. Parmi les directions de recherche envisagées, le traitement du signal sur graphe apporte un éclairage prometteur sur la question : le signal n'est plus défini comme en traitement du signal classique sur une topologie régulière à n dimensions, mais sur une topologie particulière définie par le graphe. Appliquer ces idées nouvelles aux problématiques concrètes d'analyse d'un réseau, c'est ouvrir la voie à une analyse solidement fondée sur la théorie du signal. C'est précisément autour de cette frontière entre traitement du signal et science des réseaux que s'articule cette thèse, comme l'illustrent ses deux principales contributions. D'abord, une version multiéchelle de détection de communautés dans un réseau est introduite, basée sur la définition récente des ondelettes sur graphe. Puis, inspirée du concept classique de bootstrap, une méthode de rééchantillonnage de graphes est proposée à des fins d'estimation statistique. / This thesis describes new tools specifically designed for the analysis of networks such as social, transportation, neuronal, protein, communication networks... These networks, along with the rapid expansion of electronic, IT and mobile technologies are increasingly monitored and measured. Adapted tools of analysis are therefore very much in demand, which need to be universal, powerful, and precise enough to be able to extract useful information from very different possibly large networks. To this end, a large community of researchers from various disciplines have concentrated their efforts on the analysis of graphs, well define mathematical tools modeling the interconnected structure of networks. Among all the considered directions of research, graph signal processing brings a new and promising vision : a signal is no longer defined on a regular n-dimensional topology, but on a particular topology defined by the graph. To apply these new ideas on the practical problems of network analysis paves the way to an analysis firmly rooted in signal processing theory. It is precisely this frontier between signal processing and network science that we explore throughout this thesis, as shown by two of its major contributions. Firstly, a multiscale version of community detection in networks is proposed, based on the recent definition of graph wavelets. Then, a network-adapted bootstrap method is introduced, that enables statistical estimation based on carefully designed graph resampling schemes.
|
369 |
Analyse de réseaux temporels par des méthodes de traitement du signal : application au système de vélos en libre-service à Lyon / Analysis of temporal networks using signal processing methods : Application to the bike-sharing system in LyonHamon, Ronan 30 September 2015 (has links)
Les systèmes de vélos en libre-service sont devenus des éléments indispensables dans les offres de transport urbain des grandes villes mondiales. À partir des données que ces systèmes génèrent, il est possible d'avoir une caractérisation fine de l'utilisation du vélo en milieu urbain, tant sur des problématiques traitant du domaine des transports que des aspects socio-économiques. Comme pour de nombreux domaines profitant de la récente abondance en données permises par les technologies actuelles de communication et de stockage de l'information, les enjeux actuels résident dans le développement de méthodes d'analyse de données efficaces et adaptées aux systèmes étudiés. Cette thèse se propose de répondre à cette problématique, à la fois par des développements méthodologiques et par une application à des données réelles issues du système de vélos en libre-service Vélo'v à Lyon.Le système Vélo'v peut se représenter sous la forme d'un réseau, décrivant un ensemble de relations entre les différentes stations. Cette représentation, valable également pour de nombreux systèmes, permet l'utilisation d'outils pour décrire la structure du réseau basés sur la théorie des graphes. Néanmoins, la prise en compte d'une dynamique temporelle dans l'évolution des systèmes nécessite d'étendre l'analyse à des réseaux temporels, dont la structure évolue au cours du temps. Le parallèle avec le domaine du traitement du signal, dont le but est l'analyse de signaux temporels, amène à considérer des connexions entre la description de l'évolution d'un réseau temporel et celle d'un signal. Ces travaux proposent de considérer une dualité entre les réseaux temporels et les signaux, de sorte que l'analyse dans le domaine des signaux, à l'aide des outils du traitement du signal, permet de caractériser le réseau temporel correspondant.Cette méthodologie, à la frontière entre le traitement du signal et l'analyse des réseaux, est tout d'abord justifiée par l'étude du système Vélo'v, en comparant différentes approches d'analyse de données et les apports de la représentation sous la forme de réseau temporel. Une méthode d'étiquetage des noeuds d'un graphe est ensuite discutée, permettant d'ouvrir la voie vers une dualité entre réseaux et signaux. Cette dualité est étendue aux réseaux temporels, pour lesquels une méthode d'extraction automatique des structures pertinentes au cours du temps est proposée, à travers la décomposition des signaux correspondants. / Bike-sharing systems have become essential elements in urban transportation systems of many world's big cities. Thanks to the data generated by these systems, it is possible to obtain a precise characterization of urban cycling, both in terms of transportation and socio-economic aspects. Taking advantage of the recent abundance of data allowed by the current technology, the challenges lie in the development of efficient data analysis method, adapted to these systems. This PhD thesis proposes some answers to this issue, first by methodological developments and second by studying real-world data obtained from the bike-sharing system in Lyon, called Vélo'v.The Vélo'v system can be represented as a network, describing a set of relations between the stations spread over the city. This representation, used for many systems, enables the use of tools from network theory to measure the network structure and understand the underlying mechanisms. Nevertheless, taking into account the dynamic evolution of the structure requires an extension of the classical tools to the temporal case. Parallels between this problem and the field of signal processing can be done, and opens the way to the consideration of connections between the description of the dynamics of temporal networks and those of signals. This work introduces a duality between temporal networks and signals, such that the analysis of the signals using the classical tools of signal processing helps to the characterization of the structure of the corresponding network.This methodology, at the juncture between signal processing and network analysis, is first justified by the study of the Vélo'v network, by comparing different data analysis method and the representation of the system as a temporal network. Then, a method to relabel the vertices of the graph according to the topology of the network is discussed, opening up a duality between networks and signals. This duality is then extended to temporal networks: The analysis of the spectral properties of the signals are studied through a fully automated extraction method, enabling the decomposition of relevant network structure over time.
|
370 |
Time series data mining using complex networks / Mineração de dados em séries temporais usando redes complexasLeonardo Nascimento Ferreira 15 September 2017 (has links)
A time series is a time-ordered dataset. Due to its ubiquity, time series analysis is interesting for many scientific fields. Time series data mining is a research area that is intended to extract information from these time-related data. To achieve it, different models are used to describe series and search for patterns. One approach for modeling temporal data is by using complex networks. In this case, temporal data are mapped to a topological space that allows data exploration using network techniques. In this thesis, we present solutions for time series data mining tasks using complex networks. The primary goal was to evaluate the benefits of using network theory to extract information from temporal data. We focused on three mining tasks. (1) In the clustering task, we represented every time series by a vertex and we connected vertices that represent similar time series. We used community detection algorithms to cluster similar series. Results show that this approach presents better results than traditional clustering results. (2) In the classification task, we mapped every labeled time series in a database to a visibility graph. We performed classification by transforming an unlabeled time series to a visibility graph and comparing it to the labeled graphs using a distance function. The new label is the most frequent label in the k-nearest graphs. (3) In the periodicity detection task, we first transform a time series into a visibility graph. Local maxima in a time series are usually mapped to highly connected vertices that link two communities. We used the community structure to propose a periodicity detection algorithm in time series. This method is robust to noisy data and does not require parameters. With the methods and results presented in this thesis, we conclude that network science is beneficial to time series data mining. Moreover, this approach can provide better results than traditional methods. It is a new form of extracting information from time series and can be easily extended to other tasks. / Séries temporais são conjuntos de dados ordenados no tempo. Devido à ubiquidade desses dados, seu estudo é interessante para muitos campos da ciência. A mineração de dados temporais é uma área de pesquisa que tem como objetivo extrair informações desses dados relacionados no tempo. Para isso, modelos são usados para descrever as séries e buscar por padrões. Uma forma de modelar séries temporais é por meio de redes complexas. Nessa modelagem, um mapeamento é feito do espaço temporal para o espaço topológico, o que permite avaliar dados temporais usando técnicas de redes. Nesta tese, apresentamos soluções para tarefas de mineração de dados de séries temporais usando redes complexas. O objetivo principal foi avaliar os benefícios do uso da teoria de redes para extrair informações de dados temporais. Concentramo-nos em três tarefas de mineração. (1) Na tarefa de agrupamento, cada série temporal é representada por um vértice e as arestas são criadas entre as séries de acordo com sua similaridade. Os algoritmos de detecção de comunidades podem ser usados para agrupar séries semelhantes. Os resultados mostram que esta abordagem apresenta melhores resultados do que os resultados de agrupamento tradicional. (2) Na tarefa de classificação, cada série temporal rotulada em um banco de dados é mapeada para um gráfico de visibilidade. A classificação é realizada transformando uma série temporal não marcada em um gráfico de visibilidade e comparando-a com os gráficos rotulados usando uma função de distância. O novo rótulo é dado pelo rótulo mais frequente nos k grafos mais próximos. (3) Na tarefa de detecção de periodicidade, uma série temporal é primeiramente transformada em um gráfico de visibilidade. Máximos locais em uma série temporal geralmente são mapeados para vértices altamente conectados que ligam duas comunidades. O método proposto utiliza a estrutura de comunidades para realizar a detecção de períodos em séries temporais. Este método é robusto para dados ruidosos e não requer parâmetros. Com os métodos e resultados apresentados nesta tese, concluímos que a teoria da redes complexas é benéfica para a mineração de dados em séries temporais. Além disso, esta abordagem pode proporcionar melhores resultados do que os métodos tradicionais e é uma nova forma de extrair informações de séries temporais que pode ser facilmente estendida para outras tarefas.
|
Page generated in 0.0438 seconds