Search

Orientação: Fernando Jose Von Zuben Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação Resumo: : Esta dissertação trata do desenvolvimento, análise e implementação de métodos de treinamento para redes neurais artificiais, envolvendo principalmente métodos que recorrem à informação de segunda ordem vinculadas a redes do tipo perceptron de múltiplas camadas. Como complemento ao estudo das arquiteturas com múltiplas camadas que utilizam treinamento supervisionado, é feita uma análise detalhada de um modelo auto-organizado e são propostas alternativas para alguns problemas críticos das redes neurais artificiais, como a determinação da arquitetura ótima a ser utilizada na solução de cada problema e métodos eficientes para a determinação de condições iniciais. Os resultados deste trabalho têm o propósito de contribuir no sentido de anunciar à comunidade científica que a área de redes neurais artificiais está concluindo um longo e necessário processo de transição entre uma fase inicial, caracterizada pela predominância de aspectos empíricos, e uma fase de maturidade científica, caracterizada pela formalização teórica dos resultados e maior proximidade com outras áreas de atuação científica já estabelecidas Abstract: This dissertation aims at developing, analysing and implementing training strategies for neural networks, involving mainly methods that take into account the second order information of feedforward multilayer perceptron networks. As a complement to the study of multilayer architectures, a detailed analysis of a self-organized model is performed, and some alternatives for determining optimal dimensionality of the architecture and efficient initial conditions are also proposed. The results of this work are supposed to contribute in the sense of annoucing to the scientific community that the artificial neural networks field is conc1uding a long and necessary transition between an initial phase, characterized by a great deal of heuristic content, and a phase of scientific maturity, characterized by the theoretical formalization of the results and strong interaction with other well stablished scientific fields Mestrado Automação Mestre em Engenharia Elétrica

Orientador : Fernando Jose Von Zuben Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação Doutorado

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior Conselho Nacional de Desenvolvimento Científico e Tecnológico Fundação de Amparo a Pesquisa do Estado de São Paulo Fundo Mackenzie de Pesquisa The increasing accumulation of data, from the most diverse sources, brings the need to develop new and robust data analysis tools. Among the many data analysis problems, two of them have been receiving special attention over the past years, both in academic and in business: multi-objective data clustering; and mining of data streams. At the same time, bio-inspired al-gorithms have been successfully applied in solving complex problems, such as those previously mentioned. It is in this context that this thesis proposes two new versions of swarm intelligence algorithms to solve these problems. More specifically, an algorithm inspired by the collective behavior of bees is used to tackle the multi-objective clustering problem, while a tool inspired by the collective decision-making of bacteria is used to mine association rules in data streams. The algorithms are potentially applicable to the cited current problems and the main thesis' contribution is the investigation of algorithms' adaptation and subsequent application to the already mentioned data mining complex problems. This document provides the theoretical basis necessary for the development and understanding of the research, introduces the algorithms, presents the results obtained, the conclusion of the performance achieved and brings a reflection of the future steps to be taken. O crescente acúmulo de dados, das mais diversas origens, traz intrinsecamente a necessi-dade de desenvolvimento de novas e robustas ferramentas de análise. Dentre os muitos proble-mas de análise de dados da literatura, dois deles vêm recebendo especial atenção nos últimos anos, tanto no âmbito acadêmico quando no mercado: agrupamento multiobjetivo de dados; e a análise de fluxos de dados (data streams). Ao mesmo tempo, algoritmos inspirados no com-portamento de sistemas biológicos vêm sendo aplicados com sucesso na solução de problemas complexos, como os anteriormente citados. É nesse contexto que propomos duas novas versões de algoritmos de inteligência de enxame para resolver esses problemas. Mais especificamente, um algoritmo inspirado no comportamento coletivo de abelhas é usado para resolver o problema de agrupamento multiobjetivo, enquanto uma ferramenta inspirada na tomada de decisão cole-tiva de bactérias é usada para minerar regras de associação em fluxos de dados. Os algoritmos são potencialmente aplicáveis aos problemas em questão e a contribuição principal dessa tese é a investigação da adaptação deles e posterior aplicação em problemas complexos de minera-ção de dados, já citados. Este documento traz a fundamentação teórica necessária ao desenvol-vimento e compreensão da pesquisa, apresenta os modelos propostos e os resultados experi-mentais obtidos, a conclusão do desempenho atingido e uma reflexão sobre os próximos passos a serem dados.

Orientadores: Fernando Jose Von Zuben, Leandro Nunes de Castro Silva Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e Computação Resumo: Este trabalho propõe uma classificação circunstancial para sistemas complexos, incluindo uma estrutura unificada de descrição a ser empregada na análise e síntese de sistemas computacionais bio-inspirados. Como um ramo dos sistemas complexos organizados, os sistemas computacionais bio-inspirados admitem uma sub-divisão em sistemas de inteligência computacional e sistemas homeostáticos artificiais. Com base neste formalismo, duas abordagens híbridas são concebidas e aplicadas em problemas de navegação autônoma de robôs. A primeira abordagem envolve sistemas classificadores com aprendizado e sistemas imunológicos artificiais, visando explorar conjuntamente conceitos intrínsecos a sistemas complexos, como auto-organização, evolução e cognição dinâmica. Fundamentada nas interações neuro-imuno-endócrinas do corpo humano, a segunda abordagem propõe um novo modelo de sistema homeostático artificial, explorando mudanças de contexto e efeitos do meio sobre o comportamento autônomo de um robô móvel. Embora preliminares, os resultados obtidos envolvem simulação computacional em ambientes virtuais e alguns experimentos com robôs reais, permitindo extrair conclusões relevantes acerca do potencial das abordagens propostas e abrindo perspectivas para a síntese de sistemas complexos adaptativos de interesse prático Abstract: This work proposes a circumstantial classification for complex systems, including a unified description structure to be employed in the analysis and synthesis of biologically inspired computing metaphors. Considered as a branch of organized complex systems, these bio-inspired computing frameworks may be subdivided into computation intelligence systems and artificial homeostatic systems. Developed under this formalism, two novel hybrid systems are conceived and applied to robot autonomous navigation problems. The first approach involves learning classifier systems and artificial immune systems, in an attempt to investigate intrinsic concepts of complex systems as self-organization, evolution, and dynamic cognition. Drawn on the principles of the human nervous, immune and endocrine systems, the second approach envisages a new model of an artificial homeostatic system to explore context changes and environmental effects on the behaviour of an autonomous robotic agent. Though preliminary, the obtained results encompass computer simulation on virtual environments in addition to a number of real robot¿s experiments. Relevant conclusions can be invoked, mainly related to the potentiality of the proposed frameworks, thus opening attractive prospects for the synthesis of complex adaptive systems of practical interest Doutorado Engenharia de Computação Doutor em Engenharia Elétrica

Orientador: Guilherme Palermo Coelho Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Tecnologia Resumo: Partículas sólidas e gotículas microscópicas suspensas no ar, conhecidas como material particulado (MP), podem afetar significativamente não só a saúde humana, mas também os sistemas urbanos, naturais e agrícolas. Portanto, é imperativo manter os níveis de concentração destes poluentes abaixo de limiares nocivos. Para isso, os mecanismos de previsão são particularmente relevantes, pois podem ajudar os órgãos públicos e agências ambientais a definir estratégias para controlar a concentração de MP na atmosfera. As ferramentas de previsão baseadas em Aprendizagem de Máquinas têm sido usadas para estimar a concentração de MP e outros poluentes na atmosfera, devido à sua capacidade de aprender com exemplos e identificar relações nos dados, sem serem explicitamente programadas para isto. No entanto, a maioria destas técnicas foi desenvolvida para aprender à partir de dados com distribuições de probabilidade estacionárias e, como é provável que as distribuições dos dados de concentração de MP mudem ao longo do tempo, o que é conhecido como concept drift, tais técnicas podem oferecer acurácia limitada. O objetivo geral deste trabalho é avaliar se algoritmos online de aprendizado de máquina, combinados a técnicas de detecção de concept drift tais como ensembles e janelas deslizantes, podem melhorar a acurácia da estimativa de valores futuros de MP. Neste trabalho, foram comparados algoritmos online e offline baseados em Extreme Learning Machines (ELM), a fim de avaliar seu desempenho quando são aplicados para prever as concentrações diárias de MP, especificamente partículas com diâmetro aerodinâmico inferior a 10 ?m (conhecidas como MP10). Experimentos foram realizados utilizando conjuntos de dados reais de concentração de MP10 de diferentes cidades do Estado de São Paulo, Brasil. Os resultados obtidos indicaram que os dados de concentração de MP evoluem lentamente com o passar do tempo, o que levou à proposição de novos mecanismos que permitem manter a informação de conceitos anteriores nos ensembles. Tais mecanismos têm mostrado bom desempenho em ensembles dinâmicos Abstract: Microscopically small solid particles and liquid droplets suspended in the air, known as particulate matter (PM), may significantly affect not only human health, but also urban, natural and agricultural systems. Therefore, it is imperative to keep the concentration levels of these pollutants below harmful thresholds. To do so, forecasting mechanisms are particularly relevant, as they may help public offices and environmental agencies define strategies to control PM concentration in the atmosphere. Forecasting tools based on Machine Learning have been used to estimate the concentration of PM and other pollutants in the atmosphere, as they are capable of learning from examples and identifying hidden insights in the data without being explicitly programmed. Nevertheless, most of these techniques were developed to learn from data with stationary probability distributions and, considering that PM data are uninterruptedly collected, thus producing a stream of data whose distribution may evolve over time, which is known as concept drift, such traditional machine learning techniques may offer limited accuracy. The overall goal of this work is to evaluate whether online sequential learning, combined with mechanisms and techniques to handle concept drift such as ensemble learning and sliding windows, can improve the estimation accuracy of PM forecasting. Online and offline algorithms based on Extreme Learning Machines (ELM) were compared, in order to evaluate their performance when applied to forecast daily concentrations of PM, specifically particles with aerodynamic diameter smaller than 10 ?m (known as PM10). The experiments were performed using real world datasets of PM10 concentration from different cities of the State of São Paulo, Brazil. The obtained results indicate that PM data distributions slowly evolve over time, so new mechanisms were proposed to keep information of past concepts into ensembles, so they can adapt to new concepts. These new mechanisms have shown good performance in dynamic ensembles Mestrado Sistemas de Informação e Comunicação Mestre em Tecnologia CAPES

Orientador: Paulo Licio de Geus Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: o sistema imunológico humano é capaz de garantir a sobrevivência de um indivíduo durante toda sua vida, mesmo que ele se depare, a cada dia, com bactérias e vírus potencialmente mortais. Dessa forma, esse sistema biológico provê uma rica fonte de inspiração para a manutenção da segurança computacional. Além de representar um modelo bastante próximo das condições em que a maioria das redes de computadores se encontra, o sistema imunológico engloba uma série de características e princípios desejáveis a um sistema de segurança. Considerando esses fatos, este trabalho explora as características e princípios do sistema imunológico humano para construir uma arquitetura de segurança computacional. A arquitetura desenvolvida possibilita a identificação de ataques através da análise de evidências de intrusão, respostas inespecífica e específica e a extração automatizada de assinaturas para ataques desconhecidos, tornando o sistema computacional dinamicamente adaptável a novos ataques. Com base nessa arquitetura foi construído um protótipo, ADENoIDS, que implementa as principais funcionalidades modeladas e considera a importante classe de ataques buffer overftow. Resultados experimentais permitem verificar que é possível identificar ataques desconhecidos através da análise de evidências de intrusão. Após identificar um ataque, são ativados os mecanismos de restauração e é iniciado o processo de extração de assinatura. Utilizando um algoritmo probabilistico para a extração de assinaturas, também desenvolvido nesta pesquisa, é possível eliminar falso-positivos e obter uma assinatura para o ataque em questão Abstract: The human immune system is able to guarantee the survival of an individual for his/her entire life, even though he/she encounters potentially deadly parasites, bacteria and viruses on a daily basis. In this way, this biological system provides a rich source of inspiration for the security of computer networks. Besides the fact that the human immune system presents a closely-related model of the real network conditions in the present day, it has many features that are desirable for a security system.Given these facts, this work explores the features and principIes of the human immune system for building a network security architecture. The architecture developed here enables the identification of attacks through intrusion evidence analysis, provides specific and unspecific responses and is able to extract signature for new attacks, making the computer system dinamically adaptable against new attacks. A prototype, ADENOIDS, was implemented based on this architecture, covering the main modeled features and considering buffer overflow attacks. Experimental results show that it is possible to identify new attacks by the intrusion evidence analysis mechanism. Afier identification, ADENOIDS activates system restoration mechanisms and initiates the signature extraction processo By using an algorithm developed in this research it is possible to discard false-positives and to identify the attack signatures Doutorado Ciência da Computação Doutor em Ciência da Computação

Orientadores: Fernando José Von Zuben, Leandro Nunes de Castro Silva Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação Resumo: Existem muitas formas de se entender e descrever a natureza, sendo que a Computação Natural parte do princípio de que sistemas naturais são processadores de informação, ou seja, realizam computação. Esta tese recorre aos mecanismos da Computação Natural para o entendimento das computações realizadas em um sistema natural específico: os ecossistemas. O primeiro passo está fundamentado na ciência da Biogeografia, que estuda os ecossistemas e seus padrões emergentes. Na Biogeografia, é possível identificar elementos, relações entre eles e processos. A principal contribuição desta tese está na formalização computacional da Biogeografia, dando origem à Computação Biogeográfica. A proposta da Computação Biogeográfica é desenvolvida em várias frentes. A primeira delas promove a formalização do metamodelo, definido como uma estrutura conceitual que busca contextualizar a existência de ecossistemas artificiais e seus processos espaço temporais. Em seguida, para ilustrar a aplicação do metamodelo, são propostas definições de computação de ecossistemas em superfícies adaptativas fenotípicas. Essas definições resultam em um conjunto de relações e processos, os quais são aplicáveis à construção de ecossistemas artificiais. Estes, por sua vez, permitem o entendimento de dinâmicas e padrões de ecossistemas e também podem contribuir para a resolução de problemas computáveis. Na etapa final da tese, será proposto um algoritmo de radiação adaptativa que exibe padrões similares aos encontrados em ecossistemas reais e que se mostra competitivo para otimização multimodal em espaços contínuos. Por fim, perspectivas futuras são apresentadas visando indicar caminhos para se consolidar a Computação Biogeográfica como um novo ramo da Computação Natural Abstract: There are several attempts to understand and describe nature, and Natural Computing is founded on the principle that natural systems are information processors, in the sense that they perform computation. This thesis makes use of Natural Computing mechanisms for the understanding of the computation taking place in a specific natural system: the ecosystems. The first step is based on the science of Biogeography, devoted to the study of ecosystems and their emerging patterns. In Biogeography, it is possible to identify elements, relations among them, and processes. The main contribution of this thesis resides in the computational formalization of Biogeography, thus establishing the research area of Biogeographic Computation. The proposal of Biogeographic Computation is introduced in several fronts. The first front promotes the metamodel formalism, which defines a conceptual framework focused on contextualizing the existence of artificial ecosystems and their spatio-temporal processes. After that, aiming at illustrating the application of the metamodel, definitions of ecosystems computing in phenotypic adaptive surfaces is proposed. These definitions proceed to a set of relations and processes directly applicable to the proposition of artificial ecosystems. These artificial ecosystems promote the understanding of natural ecosystems dynamics and patterns, and can also contribute to the resolution of computable problems. At the final stage of the thesis, it is presented an adaptive radiation algorithm exhibiting patterns which are similar to the ones found in real ecosystems, and also proving to be competitive for multimodal optimization in continuous spaces. To conclude, some perspectives for the further steps of the research are outlined with the purpose of indicating some routes to consolidate Biogeographic Computation as a new branch of Natural Computing Doutorado Engenharia de Computação Doutor em Engenharia Elétrica

Orientadores: Ricardo Ribeiro Gudwin, Álvaro João Magalhães de Queiroz Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação Resumo: Linguagem ainda é algo com que a Inteligência Artificial precisa lidar de forma mais apropriada. Processos relacionados como comunicação, interpretação e representação são indissociáveis de linguagem e devem ser considerados na construção de sistemas artificiais que irão usar linguagem. Diversos trabalhos já foram realizados sobre a emergência de comunicação entre agentes artificiais, mas estudos sobre os processos representacionais subjacentes encontram pouca discussão. Neste trabalho, propomos estudar as condições para emergência de comunicação baseada em representações de diferentes modalidades em uma comunidade de criaturas artificiais, avaliando os processos semióticos envolvidos. O projeto de nossos experimentos sintéticos segue inspirações biológicas e uma teoria de processos representacionais como fonte de requisitos e restrições, procedimento metodológico que defendemos. Nossos resultados mostram que comunicação baseada em diferentes modalidades de representação pode emergir a depender da arquitetura cognitiva, do custo de aquisição de competências cognitivas e da disponibilidade de atalhos cognitivos Abstract: Language is still something that Artificial Intelligence must deal with in a more appropriate way. Related processes such as communication, interpretation and representation are inseparable from language and should be considered in the building of artificial systems that will use language. Many works have already investigated the emergence of communication among artificial agents, but studies about the underlying representational processes find little discussion. In this work, we propose to study conditions to the emergence of communication based on representations of different modalities in a community of artificial creatures, assessing the semiotic processes involved. The design of our synthetic experiments follows biological inspirations and a theory of representations as sources of requirements and constraints, methodological approach that we advocate. Our results show that communication based on different modalities of representations can emerge depending on the cognitive architecture, on the cost of cognitive competences acquisition and on the availability of cognitive shortcuts Doutorado Engenharia de Computação Doutor em Engenharia Elétrica

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior Fundo Mackenzie de Pesquisa With the exponential increase of texts generated each year, the demand for Natural Language Processing techniques has been increasing, both by companies and by the Academy. Automatic topic detection in documents is one of the most challenging and useful tasks for information discovery and document summarization. Traditional topic detection techniques, such as the Latent Dirichlet Allocation (LDA) and the Non-Negative Matrix Factorization (NMF), originally did not produce good results for large databases nor use syntactic and semantic information to generate topics. Recently, word vectorization techniques, suchasWord2Vec, proved to have a good computational performance in large data sets and to be effective in representing words as word vectors in a distributed way, maintaining syntactic and semantic information. This dissertation proposes the verification of the following research hypothesis: Is Word2Vec capable of providing enough information to generate interpretable topics? For validation, a method, named Word2Topic, with two approaches for the generation of topics was proposed: direct grouping of word vectors and grouping after dimensionality reduction. The method was applied in two benchmark datasets and was compared with the traditional algorithms by a topic interpretability metric. It was observed in the results that the techniques proposed in one of the data bases generated set sof interpretable words or similar morphological classes. The topics obtained were similar to those of NMF, while LDA was unable to generate interpretable topics. It was not possible to fully validate the research hypothesis because the results of the second dataset did not lead to have the same interpretability or generated morphologically similar words. Com o aumento exponencial de textos gerados a cada ano, a procura de técnicas de Processamento de Língua Natural vem aumentado, tanto por empresas, como pela Academia. A detecção automática de tópicos em documentos é uma das tarefas mais desafiadoras e úteis para a descoberta de informações e sumarização de documentos. Técnicas tradicionais de detecção de tópicos, como a Latent Dirichlet Allocation (LDA) e a Non-Negative Matrix Factorization (NMF), originalmente não produzem bons resultados para bases de dados grandes, nem utilizam informações sintáticas e semânticas para geração de tópicos. Recentemente, técnicas de vetorização de palavras, como o Word2Vec, provaram ter um bom desempenho computacional em grandes conjuntos de dados e serem eficazes representando palavras como vetores de palavras de forma distribuída, mantendo as informações sintáticas e semânticas. Esta dissertação propõe a verificação da seguinte questão de pesquisa: O Word2Vec é capaz de prover informações suficientes para a geração de tópicos interpretáveis? Para a validação, foi proposto um método, denominado Word2Topic, com duas abordagens para a geração dos tópicos: agrupamento direto dos vetores de palavras e agrupamento após redução de dimensionalidade. O método foi aplicado em duas bases referência da literatura e foi comparado com os algoritmos tradicionais por uma métrica de interpretabilidade dos tópicos. Foi observado nos resultados que as técnicas propostas em uma das bases de dados gerou conjuntos de palavras interpretáveis ou de classes morfológicas similares. Os tópicos obtidos foram similares aos da técnica NMF, enquanto a técnica LDA não conseguiu gerar tópicos interpretáveis. Não foi possível validar completamente a questão de pesquisa, pois os resultados da segunda base não permitiram a mesma interpretabilidade ou geração de palavras morfologicamente similares.

Instituto Presbiteriano Mackenzie Today's software ecosystems have an architectural style of microservices and specific characteristics, systems and data distributed across different sources, making data management difficult. Because real-world conceptual models differ across systems, there are problems integrating data and carrying out communication between these microservices, which implies the need for matching between schemas and messages. The literature highlights matching problems such as search space size, semantic heterogeneity of data, and updates that schemas constantly go through, and shows as gaps the inadequacy of the user interfaces, the accommodation of changes in data structures, and the scarcity of approaches for practical use. Thus, the present study aimed to present a hybrid model of semantic schema matching for microservices with the ability to identify similarities between the elements of two large-scale schemes that supports the updating of the schemes and their data and considers the results of human validation for reuse. For this, the architecture of the HSSMatch model was presented, and the prototype of the HSSMatch System was implemented, allowing the user, through a web graphical interface, to manage the microservices schema matching process. The evaluation of this prototype, regarding its suitability of interaction design, was made through experiments and questionnaires applied to users working in the area of data integration and communication between software systems. The evaluation was also performed in experiments with two datasets, and showed aspects that confirm the hypothesis of this study, since there was an improvement in the efficiency and effectiveness of the schema matching process using the hybrid approach that accommodates data changes, reduces search space and combines matchers at schema and instance levels. As future work, supervised machine learning methods for semiautomatic configuration of schema matching strategies, as well as other schema partitioning techniques, domain ontologies for improving the quality of schema matching results for specific domains can be explored. Os ecossistemas de software da atualidade possuem estilo arquitetural de microsserviços e características específicas, sistemas e dados distribuídos em diferentes fontes, o que dificulta o gerenciamento de dados. Como os modelos conceituais do mundo real são diferentes entre os sistemas, há problemas para integrar os dados e realizar a comunicação entre esses microsserviços, o que implica na necessidade de matching entre os esquemas e mensagens. A literatura evidencia problemas de matching como o tamanho do espaço de busca, a heterogeneidade semântica dos dados, e as atualizações pelas quais os esquemas passam constantemente, e mostra como lacunas a inadequação das interfaces de usuários, a acomodação de alterações nas estruturas de dados, e, ainda, a escassez de abordagens para uso prático. Assim, o presente estudo teve por objetivo é apresentar um modelo híbrido de semantic schema matching para microsserviços com capacidade de identificar similaridades entre os elementos de dois esquemas em larga escala, que suporte a atualização dos esquemas e seus dados e, considere os resultados da validação humana para reuso. Para tanto, foi apresentada a arquitetura do modelo HSSMatch e implementado o protótipo do HSSMatch System que permite ao usuário, por meio de uma interface gráfica Web, gerenciar o processo de schema matching de microsserviços. A avaliação desse protótipo, no que se refere à sua adequação de design de interação, foi feita por meio de experimentos e questionários aplicados a usuários que atuam na área de integração de dados e comunicação entre sistemas de software. A avaliação também foi realizada em experimentos com dois datasets, e mostrou aspectos que confirmam a hipótese deste estudo, pois verificou-se melhoria na eficiência e eficácia do processo de schema matching utilizando a abordagem híbrida que acomoda alterações nos dados, reduz o espaço de busca e combina matchers em nível de esquema e de instâncias. Como trabalhos futuros, podem ser explorados métodos supervisionados de aprendizado de máquina para configuração semiautomática de estratégias de schema matching, e ainda outras técnicas de particionamento de esquemas, ontologias de domínio em prol da melhoria da qualidade do resultado de schema matching para domínios específicos.

Conselho Nacional de Desenvolvimento Científico e Tecnológico Emotions are important in interpersonal relationships and are part of the human being. Many people can express their feelings or emotions through social media, like Twitter and Facebook. Many computational techniques have been proposed for the study of emotions, and most use a bag-of-words representation for documents. Recently, new approaches, such as Word2Vec, ca-pable of generating distributed representations of words, called word vectors, have arisen and are being used for the syntactic and semantic study of documents. To contribute to the research in emotional states analysis from social media data and a better understanding of the use of distributed word representation models, this dissertation proposes to investigate three hypothe-ses: the Word2Vec parameters influence the distributed representations of words and, conse-quently, the performance of the emotional state classifiers that use these representations; the distributed representations of words can improve the performance of conventional classifiers applied to the study of emotional states; and clustering word vectors generate groups that carry the semantic context of emotional states. The experiments performed showed little influence of the algorithm parameters on its performance for this specific problem. We also observed that the word vectors could not be applied directly in the training of classifiers and the resulting vector greatly deteriorated the performance of the classifiers when compared to the traditional bag of words model. Finally, we found that the grouping of word vectors, while generating groups with clear semantic meaning, does not generate groups that reflect emotional states. Emoções são importantes nas relações interpessoais e fazem parte do ser humano. Muitas pessoas podem expressar seus sentimentos ou emoções nas mídias sociais, como no Twitter e no Facebook. Muitas técnicas computacionais foram propostas para o estudo das emoções e a maior parte delas utiliza uma representação baseada em conjuntos de palavras (bag of words) para os documentos. Recentemente, novas abordagens, como o Word2Vec, capazes de gerar representações distribuídas de palavras, chamadas de vetores de palavras ou word vectors, surgiram e vêm sendo empregadas para o estudo sintático e semântico de documentos. Para contribuir com a pesquisa nas áreas de análise de estados emocionais a partir de dados de mídias sociais e numa melhor compreensão sobre o uso de modelos de representação distribuída de palavras, essa dissertação propõe investigar três hipóteses de pesquisa: os parâmetros do Word2Vec influenciam as representações distribuídas das palavras e, consequentemente, o desempenho dos classificadores de estados emocionais que usam essas representações; as representações distribuídas de palavras podem melhorar o desempenho de classificadores convencionais aplicados ao estudo de estados emocionais; e o agrupamento dos vetores de palavras geram grupos que carregam o contexto semântico dos estados emocionais. Os experimentos realizados mostraram pouca influência dos parâmetros do algoritmo no seu desempenho para esse problema específico. Também observamos que os vetores de palavras não podem ser aplicados diretamente no treinamento dos classificadores e o vetor resultante deteriorou muito o desempenho dos classificadores quando comparado ao modelo tradicional do tipo bag of words. Por fim, verificamos que o agrupamento dos vetores de palavras, embora gere grupos com significado semântico claro, não gera os grupos que refletem os estados emocionais.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior Conselho Nacional de Desenvolvimento Científico e Tecnológico Fundação de Amparo a Pesquisa do Estado de São Paulo Fundo Mackenzie de Pesquisa Social media is full of unstructured data and content generated in a decentralized way, and it is possible to analyze these data to identify patterns or predict future events. The analysis of these data gives rise to social media mining, an area that uses data mining techniques to extract knowledge from social data. From how the user presents himself in social media, how he/she interacts, what he/she shares and posts, it is possible to analyze his/her behavior by assigning a virtual identity, called virtual persona, and, from the behavior of the virtual persona, to predict characteristics, such as the temperament. Temperament is a set of natural tendencies of the mind that is related to the processes of perceiving, analyzing and making daily decisions. This dis-sertation aims to identify the temperament of users (virtual personas) based on D. Keirsey’s model, who classifies the temperament in Artisan, Guardian, Idealist and Rational. As a result, an average accuracy of 88.37% was obtained for the SVM algorithm for the classification of temperaments for LIWC with 6-fold cross validation. As mídias sociais possuem um grande volume de dados não estruturados e permitem a geração de conteúdo de forma descentralizada, sendo possível analisar estes dados para identificar padrões ou prever eventos futuros. A análise desses dados dá origem à mineração de mídias sociais, uma área que utiliza técnicas de mineração de dados para extrair conhecimentos de dados sociais. A partir de como o usuário se apresenta nas mídias sociais, a forma como interage, o que curte, compartilha e posta, é possível analisar seu comportamento atribuindo uma identidade virtual, chamada persona virtual e, a partir do comportamento da persona virtual, predizer características, como o seu temperamento. O temperamento é um conjunto de tendências naturais da mente que tem relação com os processos de perceber, analisar e tomar decisão no dia a dia. Esta dissertação teve como objetivo predizer o temperamento de usuários (personas virtuais) de acordo com o modelo de D. Keirsey, que classifica o temperamento em Artesão, Guardião, Idealista e Racional. Como resultado, obteve-se uma acurácia média de 88,37% com o algoritmo SVM com estruturação dos textos via LIWC e validação cruzada em 6-pastas.

Orientador: Mateus Giesbrecht Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação Resumo: Uma parte significativa dos trabalhos de identificação de sistemas é focada em sistemas dinâmicos invariantes no tempo. No entanto, a maioria dos sistemas na vida real têm comportamento não linear e variante no tempo. Nesta dissertação, são apresentados métodos de identificação para sistemas lineares com múltiplas entradas e múltiplas saídas (MIMO) variantes lentamente no tempo, baseados em métodos de subespaços e em um paradigma no campo dos algoritmos evolutivos: o algoritmo co-evolutivo. O método de subespaço desenvolvido permite uma estimação eficiente para janelas de dados em que o sistema variante lentamente no tempo pode ser tratado como um sistema invariante no tempo. O método co-evolutivo proposto centra-se na relação entre o fitness de um indivíduo em relação ao fitness de outros indivíduos (ou grupo de indivíduos), tendo como base o princípio da pressão seletiva, que é parte do processo evolutivo. Uma breve comparação entre métodos de identificação determinística e os métodos co-evolutivos propostos é apresentada tendo em consideração a qualidade das soluções e a eficiência computacional Abstract: A significant part of works in system identification is focused on time invariant dynamic systems. However, most systems in real life have non-linear and time-varying behavior. In this dissertation, identification methods are presented for multiple-input multiple output (MIMO) linear slowly time-varying systems, based on subspace methods and on a paradigm in the field of evolutionary algorithms: the co-evolutionary algorithm. The developed subspace method allows an efficient estimation for data windows in which the time varying system can be treated as a time invariant system. The coevolutionary method focuses on the relationship between the fitness of an individual in relation to the fitness of other individuals (or group of individuals), based on the principle of selective pressure, which is part of the evolutionary process. A brief comparison between deterministic identification methods and proposed coevolutionary methods is presented taking into account the quality of the solutions and the computational efficiency Mestrado Automação Mestre em Engenharia Elétrica CAPES

Orientador: Marco Antonio Garcia de Carvalho Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Tecnologia Resumo: A Clorose Variegada dos Citros (CVC) é uma doença que afeta boa parte da produção de citros no Brasil, provocando expressivo prejuízo econômico à agricultura. Usualmente, é necessário conhecer o grau dessa doença na cultura de citros a fim de identificar o melhor tratamento. A análise de textura das folhas das plantas infectadas por meio de técnicas de processamento digital de imagens consiste em uma importante abordagem para análise do grau de comprometimento da cultura afetada pela CVC. Este trabalho propõe uma abordagem de análise de folhas de tabaco através do ranqueamento de imagens, uma técnica importante da área de Content-Based Image Retrieval (CBIR). Os ranqueamentos são calculados a partir de duas funções de distância, a Euclidiana e a de Canberra. As imagens são analisadas através de três descritores de textura: GLCM, LBP e Haralick. Com o intuito de melhorar os resultados obtidos foi aplicado um algoritmo de aprendizado não-supervisionado, o RL-Sim (RankedLists-Similarities), que consiste na obtenção de um novo ranqueamento a partir daquele inicialmente calculado. Experimentos foram realizados utilizando um conjunto de imagens cedido pelo Instituto Agronômico de Campinas (IAC). A performance dos métodos propostos é comparada à classificação manual realizada, de acordo com o grau de infecção da planta. Os resultados experimentais demonstram que a abordagem proposta atingiu níveis de eficiência da ordem de 37,33% a48,37% de acordo com a métrica Precision, indicando a necessidade de novos estudos afim de tornar esta abordagem totalmente adequada ao auxílio da análise de folhas de plantas infectadas Abstract: The Citrus Variegated Chlorosis (CVC) affects a significant part of citrus production in Brazil and causes expressive economic loss to agriculture. Usually, it is necessary to know the degree of this disease in the citrus to identify the best and correct treatment. The texture analysis of the leaves of infected plants by means of digital image processing techniques is an important method to analyze the degree of impairment affected by CVC. This paper proposes an approach to analyze tobacco leaves using image ranking, an important technique from the Content-Based Image Retrieval (CBIR) domain. Rankings are computed through two distance functions: Euclidean and Canberra. The images are analyzed by using three texture descriptors: GLCM, LBP and Haralick. With the intention of improving the retrieved results, an unsupervised distance learning algorithm was applied, the RL-Sim (RankedLists-Similarities), which consists in obtaining a new ranking from the one that was initially computed. Experiments were performed using a set of images provided by the Instituto Agronômico de Campinas (IAC). The performance of the methods is compared to the manual image classification, according to the degree of CVC infection. Experiment results demonstrate that the proposed approach achieved eficiency levels from 37,33% to 48,37% according to the Precision metric, which indicates the need of new studies to make sure this approach is totally proper to be used as an assistance to the analysis of infected plant leaves Mestrado Tecnologia e Inovação Mestra em Tecnologia

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior This dissertation makes use of Biogeography and Biogeographic Computation concepts for the proposal of an adaptive radiation model on adaptive surfaces. The proposed model is based on a computational definition of biological isolation to detect the emergence of a new species and, thus, to promote emergent processes of sympatric speciation and extinction of species from a single ancestral species. Ecosystem patterns were investigated in static and time-varying habitats based on the model. Adaptive surfaces represent ecological habitats and opportunities and, therefore, the temporal variation of habitats is linked to the variation of the surface. In this context we have investigated how adaptive radiation patterns emerge and are favorable to the continued adaptation of species, even in cases where severe environmental changes occur. Adaptive surfaces may also be linked to optimization problems, so the results allow a discussion of how ecosystem patterns can be conducive to optimization in dynamic environments where decision surfaces vary in time. Essa dissertação faz uso de conceitos da Biogeografia e Computação Biogeográfica para a proposta de um modelo de radiação adaptativa em superfícies de adaptação. O modelo pro-posto valeu-se de uma definição computacional de isolamento biológico para detecção do surgimento de uma nova espécie e, dessa forma, promover processos emergentes de especiação simpátrica e extinção de espécies a partir de uma única espécie ancestral. Por meio do modelo foram investigados padrões de ecossistemas em habitats estáticos e variantes no tempo. Superfícies de adaptação representam habitats e oportunidades ecológicas e, portanto, a variação temporal de habitats está vinculada à variação da superfície. Neste contexto foram investigados como padrões de radiação adaptativa emergem e são favoráveis à adaptação continuada de espécies, mesmo em casos em que ocorrem mudanças ambientais severas. Superfícies de adaptação também podem estar vinculadas a problemas de otimização, sendo assim os resultados permitem uma discussão de como padrões de ecossistemas podem ser favoráveis à otimização em ambientes dinâmicos onde superfícies de decisão são variantes no tempo.

Orientador: Prof. Dr. Ronaldo Pratti Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciência da Computação, 2017. O efeito de hubness, juntamente com a maldição de dimensionalidade, vem sendo estudado, sob diferentes oticas, nos ultimos anos. Os estudos apontam que este problema esta presente em varios conjuntos de dados do mundo real e que a presença de hubs (tendencia de alguns exemplos aparecem com frequencia na lista de vizinhos mais proximos de outros exemplos) traz uma serie de consequencias indesejaveis, como por exemplo, afetar o desempenho de classificadores. Em tarefas de mineração de texto, o problema depende tambem da maneira escolhida pra representar os documentos. Sendo assim o objetivo principal dessa dissertação é avaliar o impacto da formação de hubs em diferentes representações textuais. Ate onde vai o nosso conhecimento e durante o período desta pesquisa, não foi posivel encontrar na literatura um estudo aprofundado sobre as implicaçõess do efeito de hubness em diferentes representações textuais. Os resultados sugerem que as diferentes representações textuais implicam em corpus com propensão menor para a formação de hubs. Notou-se também que a incidencia de hubs nas diferentes representações textuais possuem in uencia similar em alguns classificadores. Analisamos tambem o desempenho dos classifcadores apos a remoção de documentos sinalizados como hubs em porçõess pre-estabelecidas do tamanho total do data set. Essa remoção trouxe, a alguns algoritmos, uma tendencia de melhoria de desempenho. Dessa maneira, apesar de nem sempre efetiva, a estrategia de identifcar e remover hubs com uma vizinhança majoritariamente ruim pode ser uma interessante tecnica de pre-processamento a ser considerada, com o intuito de melhorar o desempenho preditivo da tarefa de classificação. The hubness phenomenon, associated to the curse of dimensionality, has been studied, from diferent perspectives, in recent years. These studies point out that the hubness problem is present in several real-world data sets and, as a consequence, the hubness implies a series of undesirable side efects, such as an increase in misclassifcation error in classification tasks. In text mining research, this problem also depends on the choice of text representation. Hence, the main objective of the dissertation is to evaluate the impact of the hubs presence in diferent textual representations. To the best of our knowledge, this is the first study that performs an in-depth analysis on the efects of the hub problem in diferent textual representations. The results suggest that diferent text representations implies in diferent bias towards hubs presence in diferent corpus. It was also noticed that the presence of hubs in dierent text representations has similar in uence for some classifiers. We also analyzed the performance of classifiers after removing documents agged as hubs in pre-established portions of the total data set size. This removal allows, to some algorithms, a trend of improvement in performance. Thus, although not always efective, the strategy of identifying and removing hubs with a majority of bad neighborhood may be an interesting preprocessing technique to be considered in order to improve the predictive performance of the text classification task.

Orientador: Prof. Dr. Fabrício Olivetti de França Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciência da Computação, 2017. Um dos tópicos estudados em Ciência das Redes é o de detecção de comunidades, que são sub-redes com características que se destacam dentro de seu conjunto. Diversos algoritmos de detecção de comunidades foram criados, se diferenciando na natureza da comunidade estimada. Esta dissertação tem como objetivo principal analisar diferentes algoritmos de detecção de comunidades da literatura para criação de um modelo de escolha de algoritmos de detecção de comunidade a partir das características da rede. Para isso, três hipóteses. Foram testadas: i) os melhores algoritmos de detecção de comunidade se complementam em relação à redes em que obtém seu melhor desempenho; ii) o desempenho de cada algoritmo de detecção de comunidade esta ligada diretamente _a propriedade da rede. iii) uma vez que as propriedades da rede são mensuradas, é possível fazer uma escolha dos melhores algoritmos de detecção de comunidade para essa rede. Para a primeira hipótese foram testados sete algoritmos do estado da arte e avaliados seus desempenhos individuais sobre redes artifiais, em termos da métrica de Informação Mutua Normalizada (NMI). Veríamos a existência de um conjunto de algoritmos que obtiveram o maior NMI para determinados tipos de redes e nenhum outro algoritmo obteve esse mesmo valor, concluindo que a escolha adequada do algoritmo de acordo com as características da rede é importante. Para a segunda hipótese foram testados modelos de regressão com o objetivo de verificar a possibilidade de estimar o desempenho de cada algoritmo baseado nas caracteristicas da rede. Verifcamos que a maioria dos modelos foram superiores aos da base de referencia utilizados, principalmente ao remover as redes infectaveis. Para a terceira hipótese foram testados algoritmos de classicação com o objetivo de escolher um ou mais algoritmos de acordo com a características da rede. Verificamos que o desempenho dos modelos obtidos pelos algoritmos foram superiores aos da base de referencia, com algumas ressalvas. One of the topics studied in Network Science is the community detection, that are subnetworks with features that stand out as a whole. Many algorithms were developed for the detection of communities, difering in the nature of the estimated community. This dissertation has as its main objective, the analysis of diferent community detection algorithms from the literature to create models to help choosing the best algorithms given the features from the network. For this purpose, three hypotheses were tested: i) whether the best algorithms for detecting communities complement each other in relation to the networks in which they obtain better performance; ii) whether the performance of each community detection algorithm is directly associated with the network property, and iii) once the network properties are measured, whether it is possible to choose the best community detection algorithms for this network. For the first hypothesis, seven stateof- the-art algorithms were tested and their individual performances in articial networks were evaluated in terms of the NMI metric. We verifed the existence of a set of algorithms that obtained the highest NMI for certain types of networks and no other algorithm obtained that same value, concluding that the proper choice of the algorithm according to the network features is important. For the second hypothesis, regression models were tested to verify the possibility of estimate the performance of each algorithm based on the features of the network. We verifed that most of the models were superior to the baseline used, mainly in the removal of infeasible networks. For the third hypothesis, the classifcation algorithms were tested to choose one or more algorithms according to the network features. We veried that the performance of the models obtained by the algorithms was higher than those of the baseline, with some caveats.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior Conselho Nacional de Desenvolvimento Científico e Tecnológico Fundação de Amparo a Pesquisa do Estado de São Paulo Fundo Mackenzie de Pesquisa Understanding the human being is a continuous work of perception and inference about how he/she interacts and responds to various environmental stimuli in which he/she is inserted. Each person behaves based on how he/she sees and reacts to the world. However, the Internet has created an environment in which behaviors are also expressed and social media constantly stimulate the creation of social ties and the sharing of information. Identifying and mapping patterns from this data opens up opportunities to understand what is the persona that one wants to express within such environment, leading to what was named here the virtual persona. Therefore, data mining techniques are powerful tools for data exploration and analysis, making it possible to develop a computing infrastructure that allows to infer psychological aspects of the virtual persona. All this technical and computational framework for social media data analysis makes up the social media mining field of research. Motivated by this perspective, this thesis proposes computational frameworks to analyze three aspects of the virtual persona: sentiment; temperament; and personality. As a result, it was developed the Virtual Persona Triad, composed of frameworks for sentiment analysis, temperament prediction and personality identification. We assessed various techniques to represent text and classification algorithms, analyzed via social media mining methods capable of providing the desired inferences about the Triad. The results show a higher predictive ability for the category dictionaries combined with ensembles of classifiers. Entender o ser humano é um trabalho contínuo de percepções e inferências sobre como ele interage e responde aos diversos estímulos do ambiente no qual está inserido. Cada pessoa im-prime no ambiente padrões de comportamento que revelam sua forma de ver e reagir ao mundo. Não obstante, a internet criou um ambiente em que comportamentos também são expressos e as mídias sociais estimulam constantemente a criação de laços sociais e o compartilhamento de informações. Identificar e mapear padrões a partir desses dados abre oportunidades de entender qual é a persona que o usuário decidiu externar nesse ambiente, levando ao que se denomina aqui de persona virtual. Para tanto, técnicas de mineração de dados são ferramentas poderosas de exploração e análise de dados, tornando possível desenvolver uma infraestrutura computa-cional que permita inferir aspectos psicológicos sobre a persona virtual. Todo esse arcabouço técnico-computacional para análise de dados de mídias sociais compõe a mineração de mídias sociais. Motivada por essa perspectiva, esta tese propõe frameworks computacionais que pos-sibilitam analisar três aspectos sobre a persona virtual: sentimento, temperamento e personali-dade. Como resultado foi desenvolvida a tríade da persona virtual, composta pelos frameworks para análise de sentimento, temperamento e traços de personalidade. Foram avaliadas diferentes técnicas para representação de textos e também testados vários algoritmos de classificação, to-dos analisados via mineração de mídias sociais, capaz de fornecer as inferências desejadas sobre a tríade. Os resultados apontam uma maior capacidade de predição na combinação entre dicio-nários de categorias com técnicas de comitês de classificadores.

Fundo Mackenzie de Pesquisa Cellular automata are locally de ned dynamical systems which are discrete in space, time and in the state variables, and capable of presenting arbitrarily complex global emergent behaviour. One core question in the study of cellular automata refers to their limit behaviour, that is, to the global dynamical features in a in nite time evolution. Previous works have shown that for nite time evolutions, one-dimensional cellular automata present dynamics which can be described by regular languages and, therefore, by nite automata. Also, such studies have shown the existence of growth patterns in the evolution of such nite automata for some cellular automata rules; however these results were obtained manually by directly inspecting the structures that arise during the time evolution. In this work we present the formalisation of an automatic method to compute such structures. Based on this, the rules of the elementary cellular automata rule space were classi ed according to the existence of a growth pattern in their nite automata. Also, we present new methods to infer the limit graph of some elementary cellular automata rules by analysing the regular expressions describing their behaviour in nite-time and the attractors of each rule, as well as an application of these graphs in computing the Fourier spectra of the rules. Autômatos celulares são sistemas dinâmicos localmente definidos, discretos no espaço, no tempo e nas variáveis de estado, e capazes de apresentar comportamento emergente global arbitrariamente complexo. Uma das questões centrais no estudo de autômatos celulares refere-se ao comportamento limite, isto e, ás características da dinâmica global, ao considerar-se o limite de uma evolucão temporal infinita. Trabalhos anteriores mostraram que para evoluções temporais nitas de autômatos celulares unidimensionais, suas dinâmicas podem ser sempre descritas por linguagens regulares e, portanto, por autômatos finitos. Além disso, esses estudos indicaram a existência de padrões para a evolução desses autômatos finitos para algumas regras; entretanto tais resultados foram obtidos manualmente através da inspeção direta das estruturas que neles surgem ao longo do tempo. Neste trabalho apresenta-se a formalização de um método automático para o cálculo de tais estruturas. Com base nisso, as regras do espaço de autômatos celulares elementares são classificadas de acordo com a existência de um padrão de crescimento de seus autômatos finitos. Além disso, este trabalho apresenta novos métodos para a inferência do grafo-limite de alguns autômatos celulares elementares, por meio da análise das expressões regulares que descrevem seus comportamentos em tempo finito e do estudo da evolução dos atratores de cada regra, bem como uma aplicação desses grafos-limite para o cálculo de espectros de Fourier das regras.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior Fundo Mackenzie de Pesquisa Combinatorial optimization problems are widely studied in the literature. On the one hand, their challenging characteristics, such as the constraints and number of potential solutions, inspire their use to test new solution techniques. On the other hand, the practical application of these problems provides support on daily tasks of people and companies. Vehicle routing problems constitute a well-known class of combinatorial optimization problems, from which the Traveling Salesman Problem (TSP) is one of the most elementary problems. Despite its simplicity, the difficulty in finding its exact solution and its direct application in practical problems in multiple areas make it one of the most studied problems in the literature. Algorithms inspired by biological phenomena are being successfully applied to optimization problems, mainly combinatorial optimization problems. Those inspired by the collective behavior of insects produce good results for solving such problems. This work proposes the VRoptBees, a framework inspired by honeybee behavior to tackle vehicle routing problems. Together with the framework, two examples of implementation are described, one to solve the TSP and the other to solve the Capacitated Vehicle Routing Problem (CVRP). Tests were conducted with benchmark instances from the literature, on which the implementation for the TSP presented the third best results in a comparison with other bee-inspired algorithms. Problemas de otimização combinatória são largamente estudados na literatura. De um lado, suas características desafiadoras, como o número de restrições e possíveis soluções, inspiram seu uso para testar novas técnicas de solução. Por outro lado, a aplicação prática desses problemas auxilia no dia a dia de pessoas e empresas. Os problemas de roteamento de veículos constituem uma classe muito conhecida da otimização combinatória, tendo o Problema de Caixeiro Viajante (PCV) como um dos mais elementares. Apesar de sua simplicidade, a dificuldade em encontrar uma solução exata e sua direta aplicação prática em diversas áreas o faz um dos problemas mais estudados na literatura. Algoritmos inspirados em fenômenos naturais têm sido utilizados com sucesso em problemas de otimização, principalmente de natureza combinatória. Aqueles inspirados no comportamento coletivo de insetos apresentam bons resultados para esses problemas. Nesse trabalho é proposto um framework inspirado no comportamento de abelhas para a solução de problemas de roteamento de veículos, chamado de VRoptBees. Junto ao framework, dois exemplos de implementações são propostos, um para a solução do PCV e outro para o Problema de Roteamento de Veículos Capacitados (PRVC). Testes foram feitos com instâncias de benchmark comumente utilizadas na literatura, com a implementação ao PCV apresentando o terceiro melhor resultado entre os algoritmos inspirados em abelhas.

Universidade Presbiteriana Mackenzie Currently, the natural sciences are taking advantage of information and computing concepts to investigate the structure of nature and the interrelationships among the various natural systems. Furthermore, scientists from various fields are arguing that nature performs computations and others argue that the basic structure of the physical world is based on informational and computational processes. Within this scenario, there is the Natural Computing, whose main premise is to assume that natural phenomena can be interpreted from a computational perspective and that these phenomena can be modeled computationally and applied in different scientific contexts. Although Natural Computing is committed with the computational interpretation of nature, there is no theoretical framework that leads to the explanation of natural systems from a computational perspective. In this context, this thesis proposes a Conceptual Framework that allows to computationally explain the structures and processes within natural systems. The Conceptual Framework is based on a set of concepts and macroconcepts and its formalization consists of two sets of tools: a conceptual map with its graphical view of macroconcepts and concepts and their relationships; and a set of UML diagrams to computationally modeling the structures, processes and subprocesses present in natural systems. Thus, the proposed Conceptual Framework brings an intuitive and visual way to understand the natural systems under a computational perspective and to guide the modeling of bioinspired algorithms. From the perspective of a bioinspired analysis of algorithms, modeling tools allow to view conceptual gaps in the algorithms. Finally, the proposed Conceptual Structure is used as a tool for the analysis and synthesis of bioinspired algorithms, more specifically to develop algorithms inspired by the behavior of bacteria. In this way, the proposed framework aims to build an analysis and synthesis tool to collaborate for the theoretical and interdisciplinary maturation of Natural Computing. Atualmente, as ciências naturais estão se valendo de conceitos de informação e computação para investigar a estrutura da natureza e as inter-relações entre os diversos sistemas naturais. Além disso, cientistas de diversas áreas estão argumentando que a natureza realiza computações e outros defendem que a estrutura básica do mundo físico está fundamentada em processos informacionais e computacionais. Dentro deste cenário, existe a Computação Natural, cuja principal premissa é assumir que os fenômenos naturais podem ser interpretados sob uma perspectiva computacional e que esses fenômenos podem ser modelados computacionalmente e aplicados em diferentes contextos científicos. Embora a Computação Natural se comprometa com a interpretação computacional da natureza não existe um corpo teórico que permita explicar os sistemas naturais sob uma perspectiva computacional. Neste contexto, esta tese propõe uma Estrutura Conceitual, que explica computacionalmente as estruturas e processos presentes nos sistemas naturais. A Estrutura Conceitual é embasada em um conjunto de conceitos e macroconceitos e sua formalização consiste em dois conjuntos de ferramentas: um mapa conceitual que representa uma visualização gráfica dos macroconceitos e conceitos e suas relações; e um conjunto de diagramas UML para modelar computacionalmente as estruturas, processos e subprocessos presentes nos sistemas naturais. Desta forma, a Estrutura Conceitual proposta traz consigo uma forma intuitiva e visual de entender os sistemas naturais sob uma perspectiva computacional e de guiar a modelagem de algoritmos bioinspirados. Da perspectiva da análise de algoritmos bioinspirados, as ferramentas de modelagem permitem visualizar lacunas conceituais na engenharia dos algoritmos estudados. Por fim, a Estrutura Conceitual proposta é utilizada como ferramenta para o projeto e desenvolvimento (síntese) de algoritmos bioinspirados, mais especificamente para o desenvolvimento de algoritmos inspirados no comportamento das bactérias. Desta forma, a Estrutura Conceitual proposta visa a construção de um ferramental de análise e síntese que colabore para o amadurecimento teórico e interdisciplinar da Computação Natural.

The process of image binarization consists of transforming a color image into a new one with only two colors: black and white. This process is an important step for many modern applica-tions such as Check Clearance, Optical Character Recognition and Handwriting Recognition. Improvements in the automatic process of image binarization represent impacts on applications that rely on this step. The present work proposes a methodology for automatic image binariza-tion. This methodology applies supervised learning algorithms to binarize images and consists of the following steps: images database construction; extraction of the region of interest; pat-terns matrix construction; pattern labelling; database sampling; and classifier training. Experi-mental results are presented using a database of Brazilian bank check images and the competi-tion database DIBCO 2009. In conclusion, the proposal demonstrated to be superior to some of its competitors in terms of accuracy and F-Measure. O processo de binarização de imagens consiste na transformação de uma imagem colorida em uma nova imagem com apenas duas cores: uma que representa o fundo, outra o objeto de interesse. Este processo é uma importante etapa de diversas aplicações modernas, como a Compensação de Cheque, o Reconhecimento Ótico de Caracteres (do inglês Optical Characterer Recognition) e o Reconhecimento de Texto Manuscrito (do inglês Handwritten Recognition, HWR). Dado que melhorias no processo automático de binarização de imagens representam impactos diretos nas aplicações que dependem desta etapa o presente trabalho propõe uma metodologia para realizar a binarização automática de imagens. A proposta realiza a binarização de forma automática baseado no uso de algoritmos de aprendizagem supervisionada, tais como redes neurais artificiais e árvore de decisão. O processo como um todo consiste das seguintes etapas: construção do banco de imagens; extração da região de interesse; construção da matriz de padrões; rotulação dos padrões; amostragem da base; e treinamento do classificador. Resultados experimentais são apresentados utilizando uma base de imagens de cheques de bancos brasileiros (CMC-7 e montante de cortesia) e a base de imagens da competição DIBCO 2009. Em conclusão, a metodologia proposta apresentou-se competitiva aos métodos da literatura destacando-se em aplicações onde o processamento de imagens está restrito a uma categoria de imagens, como é o caso das imagens de cheques de bancos brasileiros. A presente metodologia apresenta resultados experimentais entre as três primeiras posições e melhores resultados em relação a medida F-Measure quando comparada com as demais.

With the popularization of Internet, the advancement of electronic devices and the ease of storage, the volume of data stored and available at companies has increased substantially. Therefore, it becomes necessary to use intelligent techniques to extract useful information and knowledge from these data. In this context, Data Mining has been the aim of several researches by providing a set of intelligent techniques to the exploration of large volumes of data. The present project aims to research and develop new algorithms inspired by the collective behavior of bee colonies for solving complex clustering and classification tasks. More specifically, this project proposes adaptations of an optimization algorithm inspired by the behavior of bees so that it can be applied to solve clustering problems and also for positioning centers of RBF neural networks. The proposed approaches were applied to several benchmark problems with promising results. Com a popularização da Internet, o avanço dos dispositivos eletrônicos e a facilidade de armazenamento, o volume de dados armazenados e disponibilizados por empresas de diversos ramos tem aumentado rapidamente. Com isso, torna-se necessária a utilização de técnicas avançadas capazes de extrair desses dados informações úteis e conhecimentos que, na maioria das vezes, estão implícitos. Nesse contexto, a Mineração de Dados tem sido alvo de diversas pesquisas por prover um conjunto de técnicas inteligentes para a exploração de grandes volumes de dados. O presente projeto visa à investigação e desenvolvimento de novos algoritmos inspirados no comportamento coletivo das colônias de abelhas para aplicação em problemas complexos de classificação e agrupamentos de dados, que são importantes tarefas da Mineração de Dados. Mais especificamente, esse projeto propõe adaptações de um algoritmo de otimização inspirado no comportamento de abelhas, sua aplicação em problemas de agrupamento de dados e para o posicionamento de centros de redes neurais do tipo RBF. Os resultados experimentais em bases de dados da literatura mostraram a viabilidade e benefícios das propostas, tanto para problemas de agrupamento, quanto para problemas de classificação.

Fundação de Amparo a Pesquisa do Estado de São Paulo A honeypot is a computer security system dedicated to being probed, attacked or compromised. The information collected help in the identification of threats to computer network assets. When probed, attacked and compromised the honeypot receives a sequence of commands that are mainly intended to exploit a vulnerability of the emulated systems. This work uses data collected by honeypots to create rules and signatures for intrusion detection systems. The rules are extracted from decision trees constructed from the data sets of real honeypots. The results of experiments performed with four databases, both public and private, showed that the extraction of rules for an intrusion detection system is possible using data mining techniques, particularly decision trees. The technique pointed out similarities between the data sets, even the collection occurring in places and periods of different times. In addition to the rules obtained, the technique allows the analyst to identify problems quickly and visually, facilitating the analysis process. Um honeypot é um sistema computacional de segurança dedicado a ser sondado, atacado ou comprometido. As informações coletadas auxiliam na identificação de ameaças computacionais aos ativos de rede. Ao ser sondado, atacado e comprometido o honeypot recebe uma sequência de comandos que têm como principal objetivo explorar uma vulnerabilidade dos sistemas emulados. Este trabalho faz uso dos dados coletados por honeypots para a criação de regras e assinaturas para sistemas de detecção de intrusão. As regras são extraídas de árvores de decisão construídas a partir dos conjuntos de dados de um honeypot real. Os resultados dos experimentos realizados com quatro bases de dados, duas públicas e duas privadas, mostraram que é possível a extração de regras para um sistema de detecção de intrusão utilizando técnicas de mineração de dados, em particular as árvores de decisão. A técnica empregada apontou similaridades entre os conjuntos de dados, mesmo a coleta ocorrendo em locais e períodos de tempos distintos. Além das regras obtidas, a técnica permite ao analista identificar problemas existentes de forma rápida e visual, facilitando o processo de análise.

Fundação de Amparo a Pesquisa do Estado de São Paulo Clustering usually treats objects as belonging to mutually exclusive clusters, what is usually im-precise, because an object may belong to more than one cluster simultaneously with different membership degrees. The clustering algorithms, both crisp and fuzzy, have a number of parameters to be adjusted so that they present the best performance for a given database. Furthermore, it is known that no single algorithm is better than all the others for all problem classes, and the combi-nation of solutions found by various algorithms (or the same algorithm with different parameters) may lead to a global solution that is better than those found by individual algorithms, including the best one. It is within this context that the present thesis proposes a new fuzzy clustering algo-rithm inspired by the behavior of particle swarms and, then, introduces a new form of combining the clustering algorithms using concepts from Type-2 fuzzy sets. Da maneira tradicional o agrupamento trata os objetos que compõem a base como pertencentes a grupos mutuamente exclusivos, o que nem sempre é verdade, pois um objeto pode pertencer a mais de um grupo com diferentes graus de pertinência. Os algoritmos de agrupamento, sejam eles convencionais ou nebulosos (capazes de tratar múltiplas pertinências simultaneamente), possuem diversos parâmetros a serem ajustados de tal forma que ofereçam o melhor desempenho para uma base de dados. Além disso, é sabido que nenhum algoritmo é superior a todos os outros para todas as classes de problemas e que combinar soluções fornecidas por diferentes algoritmos pode levar a uma solução global superior a todas as soluções individuais, inclusive à melhor. É nesse contexto que a presente tese propõe um novo algoritmo de agrupamento nebuloso de dados inspirado no comportamento de enxames de partículas e, em seguida, propõe uma nova forma de realizar combinações (ensembles) de algoritmos de agrupamento usando conceitos da teoria de conjuntos nebulosos do Tipo-2.

Submitted by Santos Davilene (davilenes@ufba.br) on 2016-05-25T15:22:41Z No. of bitstreams: 1 dissertacao_mestrado_ciencia_computacao_rafael_glauber.pdf: 2701674 bytes, checksum: d9b74db08b0e071f5dddf22ab848cd3e (MD5) Made available in DSpace on 2016-05-25T15:22:41Z (GMT). No. of bitstreams: 1 dissertacao_mestrado_ciencia_computacao_rafael_glauber.pdf: 2701674 bytes, checksum: d9b74db08b0e071f5dddf22ab848cd3e (MD5) Sistemas de Recomendação sugerem itens de interesse explorando as preferências dos usuários ajudando-os contra o problema da sobrecarga de informações. Primeiramente estes sistemas eram construídos, exclusivamente, através de técnicas com origem nas áreas de Recuperação de Informação e Aprendizado de Máquina. Porém, desde o início da década de 90 a abordagem conhecida como Filtragem Colaborativa, que não explora qualquer tipo de conteúdo disponível dos itens para realizar sua tarefa, passou a ser a mais utilizada como solução para estes sistemas. Pesquisas como as de Shardanand & Maes (1995); Das et al. (2007); Konstan & Riedl (2012) justificam essa preferência por conta de deficiências preexistentes nos algoritmos de filtragem por conteúdo dos itens. Entretanto, nestas pesquisas não são evidenciadas essas deficiências ou mesmo as diferenças e semelhanças das recomendações geradas pelos algoritmos dessas duas abordagens levando esta discussão ao senso comum. Neste trabalho é proposta uma metodologia para comparação de algoritmos de recomendação que vai além da precisão das previsões. Para demonstrar essa metodologia a aplicamos na comparação das abordagens de Filtragem Baseada em Conteúdo Textual e a Filtragem Colaborativa. Nossos resultados demonstram que algoritmos dessas duas abordagens não só diferem em diversas dimensões em um teste de sistema, como também apresentam características que sugerem grande complementariedade.

Natcomp Informatica e Equipamentos Eletronicos LTDA Data clustering is an important data mining task that aims to segment a database into groups of objects based on their similarity or dissimilarity. Due to the unsupervised nature of clustering, the search for a good quality solution can become a complex process. There is currently a wide range of clustering algorithms and selecting the most suitable one for a given problem can be a slow and costly process. In 1976, Rice formulated the algorithm selection problem (PSA) postulating that a good performance algorithm can be chosen according to the problem s structural characteristics. Meta-learning brings the concept of learning about learning, that is, the meta-knowledge obtained from the algorithms learning process allows it to improve its performance. Meta-learning has a major intersection with data mining in classification problems, where it is used to select algorithms. This thesis proposes an approach to the algorithm selection problem by using meta-learning techniques for clustering. The characterization of 84 problems is performed by a classical approach, based on the problems, and a new proposal based on the similarity among the objects. Ten internal indices are used to provide different performance assessments of seven algorithms, where the combination of the indices determine the ranking for the algorithms. Several analyzes are performed in order to assess the quality of the obtained meta-knowledge in facilitating the mapping between the problem s features and the performance of the algorithms. The results show that the new characterization approach and method to combine the indices provide a good quality algorithm selection mechanism for data clustering problems. Agrupamento é uma tarefa importante na mineração de dados, tendo como objetivo segmentar uma base de dados em grupos de objetos baseando-se na similaridade ou dissimilaridade entre os mesmos. Devido à natureza não supervisionada da tarefa, a busca por uma solução de boa qualidade pode se tornar um processo complexo. Atualmente, existe na literatura acadêmica uma grande quantidade de algoritmos que podem ser utilizados na resolução deste problema. A seleção do algoritmo mais adequado para um determinado problema pode ser um processo lento e custoso. Em 1976, Rice formulou o Problema de Seleção de Algoritmos (PSA), postulando que um algoritmo de bom desempenho pode ser escolhido de acordo com as características estruturais do problema em que o mesmo será aplicado. A meta-aprendizagem traz consigo o conceito de aprender sobre o aprender, isto é, por meio do meta-conhecimento obtido do processo de aprendizagem dos algoritmos é possível aprimorar o desempenho do processo. Meta-aprendizagem possui grande interseção com mineração de dados no que tange problemas de classificação, sendo utilizada no desenvolvimento de sistemas de seleção de algoritmos. Nesta tese é proposta a abordagem ao PSA por meio de técnicas de meta-aprendizagem para agrupamento de dados. A caracterização de 84 problemas é realizada pela abordagem clássica, baseada nos problemas, e por uma nova proposta baseada na similaridade entre os objetos. São utilizados dez índices internos para promover diferentes avaliações do desempenho de sete algoritmos, onde a combinação desses índices determina o ranking dos algoritmos. São realizadas diversas análises no intuito de avaliar a qualidade do meta-conhecimento obtido em viabilizar o mapeamento entre as características do problema e o desempenho dos algoritmos. Os resultados mostram que a nova caracterização e combinação dos índices proporcionam a seleção, com qualidade, de algoritmos para agrupamento de dados.

The concepts of fractal geometry, which were developed in 1975 by Mandelbrot, complement Euclidean geometry as they provide theoretical dimensional fundamentals for shapes whose irregularities cannot be properly interpreted by classical topological definitions. The standards of this irregular morphology, found in abundance in nature, can be recognized in the construction processes of various fractals anthropic figures, mainly when combined with computational technology. Professionals and researchers from several knowledge fields are exploring these concepts to simulate or create models of irregular shapes, with detail levels hitherto inconceivable. Earth sciences supported by geotechnologies have great potential for applying Mandelbrot s theories as a conceptual reference for analyzing phenomena presenting fractal behaviors, belonging to different application areas as geomorphology, climatology and urban and landscapes studies. In this approach, the fractal dimension of the territorial space occupied by cities is considered an indicator for understanding occupation patterns as one of the factors to be considered in urban planning policies, e.g., to propose projects for more appropriate investments distribution and development of infrastructure. In this work, these concepts were applied by using the box-counting method to calculate the fractal dimension of urban forms from eight Brazilian state capitals by using the Municipal Human Development Index (MHDI) as the selection criteria: four cities ranked among the top of the list and four cities classified among the last positions of the state capitals. The results were analyzed in order to identify possible relationships or trends among these indicators, namely, fractal dimension and MHDI, that may support future studies and urban planning. These relationships were not confirmed: the eight studied cities presented heterogeneous fractal dimension values and no trends were verified. However, it was concluded that the fractal dimension of urban form is related to its scattering pattern and occupation over the geographical territorial space and may be an indicator of the occupation density from the urban area. Os conceitos da geometria fractal, desenvolvida em 1975 por Mandelbrot, complementam os da geometria euclidiana à medida que fornecem um arcabouço teórico de cálculo dimensional para diversas formas cujas irregularidades apresentam características que não podem ser interpretadas adequadamente pelas definições topológicas clássicas. Os padrões dessa morfologia irregular, encontrada em abundância na natureza, podem ser reproduzidos em processos de construção de figuras fractais desenvolvidas pelo homem, especialmente quando combinadas com a tecnologia computacional. Profissionais e pesquisadores de diversas áreas de conhecimento passaram a explorar esses conceitos a fim de simular ou criar modelos de formas irregulares, com níveis de detalhe até então inconcebíveis. As ciências da Terra, com o apoio de ferramentas de geotecnologia, apresentam grande potencial de se apropriar das teorias da geometria de Mandelbrot, como referência conceitual aos estudos de fenômenos que apresentam comportamento fractal, pertencentes a várias áreas de aplicação como a geomorfologia, climatologia e os estudos urbanos e de paisagens. Nessa abordagem, a dimensão fractal do espaço territorial ocupado pelas cidades vem sendo considerada indicador importante para entendimento desse padrão de ocupação, contribuindo como um dos fatores a ser considerados nas políticas de planejamento urbano e, por exemplo, propor projetos de distribuição de investimentos e desenvolvimento de infraestrutura mais adequados. Neste trabalho, esses conceitos foram aplicados por meio da utilização do método da contagem de quadrados para calcular a dimensão fractal das formas urbanas de oito capitais brasileiras, utilizando o Índice de Desenvolvimento Humano Municipal (IDHM) de 2010, publicado em julho de 2013, como critério de seleção. Foram escolhidas quatro cidades classificadas entre as primeiras da lista e outras quatro que ocupam as últimas posições entre as capitais estaduais, com o objetivo de encontrar possíveis relações ou tendências entre esses indicadores dimensão fractal e IDHM que pudessem subsidiar futuros estudos e planejamentos urbanos. Os resultados obtidos não revelaram a existência de tais relações: as oito cidades estudadas apresentaram valores dimensionais heterogêneos, sem registro de tendências. No entanto, foi possível concluir que a dimensão fractal de uma forma urbana está relacionada ao seu padrão de espalhamento e ocupação do espaço territorial geográfico e pode ser considerada um indicador da densidade de ocupação da área urbana.

Fundação de Amparo a Pesquisa do Estado de São Paulo Twitter is a microblog service that generates a huge amount of textual content daily. All this content needs to be explored by means of techniques, such as text mining, natural language processing and information retrieval. In this context, the automatic keyword extraction is a task of great usefulness that can be applied to indexing, summarization and knowledge extrac-tion from texts. A fundamental step in text mining consists of building a text representation model. The model known as vector space model, VSM, is the most well-known and used among these techniques. However, some difficulties and limitations of VSM, such as scalabil-ity and sparsity, motivate the proposal of alternative approaches. This dissertation proposes a keyword extraction method, called TKG (Twitter Keyword Graph), for tweet collections that represents texts as graphs and applies centrality measures for finding the relevant vertices (keywords). To assess the performance of the proposed approach, two different sets of exper-iments are performed and comparisons with TF-IDF and KEA are made, having human clas-sifications as benchmarks. The experiments performed showed that some variations of TKG are invariably superior to others and to the algorithms used for comparisons. O Twitter é um serviço de microblog que gera um grande volume de dados textuais. Todo esse conteúdo precisa ser explorado por meio de técnicas de mineração de textos, processamento de linguagem natural e recuperação de informação com o objetivo de extrair um conhecimento que seja útil de alguma forma ou em algum processo. Nesse contexto, a extração automática de palavras-chave é uma tarefa que pode ser usada para a indexação, sumarização e compreensão de documentos. Um passo fundamental nas técnicas de mineração de textos consiste em construir um modelo de representação de documentos. O modelo chamado mode-lo de espaço vetorial, VSM, é o mais conhecido e utilizado dentre essas técnicas. No entanto, algumas dificuldades e limitações do VSM, tais como escalabilidade e esparsidade, motivam a proposta de abordagens alternativas. O presente trabalho propõe o método TKG (Twitter Keyword Graph) de extração de palavras-chave de coleções de tweets que representa textos como grafos e aplica medidas de centralidade para encontrar vértices relevantes, correspondentes às palavras-chave. Para medir o desempenho da abordagem proposta, dois diferentes experimentos são realizados e comparações com TF-IDF e KEA são feitas, tendo classifica-ções humanas como referência. Os experimentos realizados mostraram que algumas variações do TKG são superiores a outras e também aos algoritmos usados para comparação.

Fundo Mackenzie de Pesquisa E-commerce has been growing rapidly over the past years. Various products, services, and information are constantly offered to millions of internet users. Defining an adequate strategy to offer a product to a customer is the main goal of a recommender system. To do so, the items to be offered have to take into account the interests of each customer. This association of items is a data mining task, more specifically a task called association rule mining. This dissertation investigated the use of bioinspired algorithms, particularly evolutionary and im-mune algorithms, to build associations among items of a database. Three sets of experiments were performed: an investigation into the influence of different selection and crossover mech-anisms in an evolutionary algorithm for association rule mining; the use of a probabilistic selection in the immune algorithm; and a comparison of the bioinspired algorithms with the standard deterministic algorithm called Apriori. The data bases for comparison were taken from real e-commerce applications. The results allowed the identification of a suitable combi-nation of the selection and crossover mechanisms for the evolutionary algorithm, and to iden-tify the strengths and weaknesses of all approaches when applied to real-world recommender systems. O comércio eletrônico vem crescendo rapidamente ao longo dos últimos anos. Produtos, serviços e informações dos mais variados tipos são oferecidos todos os dias para milhares de usuários na Internet. Definir uma estratégia adequada para oferecer um produto a clientes é o objetivo dos sistemas de recomendação. Para isso leva em conta itens que podem ser ofertados considerando o interesse de cada cliente. Essa associação entre itens é uma tarefa que recai sobre a competência da mineração de dados, mais especificamente a área chamada de mineração de regras de associação. Esta dissertação investigou o uso de algoritmos bioinspirados, mais especificamente algoritmos evolutivos e imunológicos, a fim de construir associações entre os itens de uma base de dados. Foram feitos três estudos: a influência de diferentes mecanismos de seleseleção e cruzamento no algoritmo evolutivo; o uso de seleção probabilística no algoritmo imunológico; e a comparação dos algoritmos bioinspirados com o algoritmo determinístico clássico aplicado a essa tarefa, chamado de Apriori. As bases de dados para efeitos comparativos foram coletadas em lojas nacionais de comércio eletrônico. Os resulta-dos apresentados permitiram identificar uma combinação adequada dos mecanismos de sele-ção e cruzamento do algoritmo evolutivo, assim como identificar os pontos fortes e fracos dos algoritmos bioinspirados quando comparados ao algoritmo tradicional.

Universidade Presbiteriana Mackenzie Cellular automata are totally discrete systems that act locally in a simple and deterministic way, but whose resulting global behavior can be extremely complex. The set of possible global configurations in one finite time step for a CA can be described by a regular language, which in turn can be represented by a finite automaton, more precisely the so-called process graph, in which all states are initial and final. Here, we study the temporal evolution complexity of the elementary cellular automata (i.e., one-dimensional, binary, with radius 1), and related previous works are revisited and discussed, indicating problems and their consequences. We also start up a novel approach for the problem, substituting the process graph based representation that describes the configuration at each time step by adjacency matrices derived from them. In fact, we extend the classical adjacency matrix notation, as they cannot fully represent process graphs. With this new notation, we show that it is possible to obtain the algorithm to generate a process graph for an arbitrary finite time step for each of the rules at study. In conclusion, although advancing the limit graph problem, it still remains open, and we provide suggestions for further research. Autômatos celulares são sistemas totalmente discretos que agem localmente de forma simples e determinística, mas cujo comportamento global resultante pode ser extremamente complexo. O conjunto de possíveis configurações globais em um passo de tempo t finito para um autômato celular pode ser descrito por uma linguagem regular, a qual por sua vez pode ser representada por meio de um autômato finito, mais precisamente, pelo chamado grafo de processo, em que todos os estados são iniciais e finais. Estuda-se aqui a complexidade da evolução temporal dos autômatos celulares elementares (i.e., unidimensionais, binários, de raio 1), e trabalhos anteriores são revisitados e discutidos, no quais apontam-se problemas e suas consequências. Também inicia-se uma nova abordagem para o problema, substituindo a representação dos grafos de processo que descrevem a configuração a cada passo de tempo por matrizes de adjacência deles derivadas. De fato, estende-se a notação clássica de matriz de adjacência, já que ela se mostra insuficiente para descrever completamente os grafos de processo em questão. Com essa nova notação, mostra-se que é possível obter o algoritmo que gere o grafo de processo de tempo t para cada uma das regras estudadas. Conclui-se que, embora houve avanços para o problema do grafo limite, este ainda permanece aberto, e sugestões para continuação da pesquisa são dadas.

Orientador: Romis Ribeiro de Faissol Attux Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação Resumo: As redes neurais com estados de eco (em inglês, echo state networks, ESNs) são estruturas recorrentes capazes de aliar processamento dinâmico a um processo de treinamento relativamente simples, o qual se resume à adaptação dos coeficientes do combinador linear da saída no sentido de mínimo erro quadrático médio (em inglês, mean squared error, MSE), enquanto os pesos das conexões no reservatório de dinâmicas são ajustados de maneira antecipada e permanecem fixos. A presente tese trata dos principais elementos que caracterizam as ESNs e propõe: (i) uma unificação entre as abordagens de computação com reservatórios, como as ESNs e as liquid state machines (LSMs), e as extreme learning machines (ELMs), sob o termo geral de máquinas desorganizadas, o qual estabelece uma conexão com as pioneiras idéias conexionistas de Alan Mathison Turing; (ii) uma nova arquitetura de ESN, cuja camada de saída é composta por um filtro de Volterra e por um estágio de compressão baseado em Análise de Componentes Principais (em inglês, Principal Component Analysis, PCA); (iii) o uso de critérios de aprendizado baseados em teoria da informação e em normas Lp em lugar do critério MSE para a adaptação dos parâmetros da camada de saída de ESNs; e (iv) uma estratégia não-supervisionada de projeto da camada recorrente de ESNs baseada em interações laterais, modeladas segundo a função chapéu mexicano, e na auto-organização dos pesos de entrada. As propostas elaboradas neste trabalho são analisadas através de simulações no contexto de diferentes problemas de processamento da informação, como equalização de canais de comunicação, separação de fontes e predição de séries temporais Abstract: Echo state networks (ESNs) are recurrent structures capable of allying dynamic processing to a relatively simple training process, which amounts to adapting the coefficients of the linear combiner at the output in the minimum mean squared error (MSE) sense, while the connection weights in the dynamical reservoir are adjusted in advance and remain fixed. The present thesis deals with the main elements that characterize ESNs and proposes: (i ) a unification between reservoir computing approaches, such as ESNs and liquid state machines (LSMs), and extreme learning machines (ELMs), under the general term of unorganized machines, which establishes a connection with the pioneering connectionist ideas of Alan Mathison Turing; (ii ) a novel ESN architecture whose output layer is composed of a Volterra filter and of a compression stage based on Principal Component Analysis (PCA); (iii ) the use of information-theoretic learning criteria and those based on Lp norms instead of the MSE criterion for the adaptation of the parameters of the ESN output layer; and (iv) an unsupervised strategy for designing the recurrent layer of ESNs based on lateral interactions, modeled according to the mexican hat function, and on the self-organization of the input weights. The proposals developed in this work are analyzed through simulations in the context of different information processing problems, such as channel equalization, source separation and time series prediction Doutorado Engenharia de Computação Doutor em Engenharia Elétrica

Fundação de Amparo a Pesquisa do Estado de São Paulo Social media have become a way of expressing collective interests. People are motivated by the sharing of information and the feedback from friends and colleagues. Among the many social media tools available, the Twitter microblog is gaining popularity as a platform for in-stantaneous communication. Millions of messages are generated daily, from over 100 million users, about the most varied subjects. As it is a rapid communication platform, this microblog spurred a phenomenon called television storytellers, where surfers comment on what they watch on TV while the programs are being transmitted. The Social TV emerged from this integration between social media and television. The amount of data generated on the TV shows is a rich material for data analysis. Broadcasters may use such information to improve their programs and increase interaction with their audience. Among the main challenges in social media data analysis there is sentiment analysis (to determine the polarity of a text, for instance, positive or negative), and sense disambiguation (to determine the right context of polysemic words). This dissertation aims to use machine learning techniques to create a tool to support Social TV, contributing specifically to the automation of sentiment analysis and disambiguation of Twitter messages. As mídias sociais são uma forma de expressão dos interesses coletivos, as pessoas gostam de compartilhar informações e sentem-se valorizadas por causa disso. Entre as mídias sociais o microblog Twitter vem ganhando popularidade como uma plataforma para comunicação ins-tantânea. São milhões de mensagens geradas todos os dias, por cerca de 100 milhões de usuá-rios, carregadas dos mais diversos assuntos. Por ser uma plataforma de comunicação rápida esse microblog estimulou um fenômeno denominado narradores televisivos, em que os inter-nautas comentam sobre o que assistem na TV no momento em que é transmitido. Dessa inte-gração entre as mídias sociais e a televisão emergiu a TV Social. A quantidade de dados gera-dos sobre os programas de TV formam um rico material para análise de dados. Emissoras podem usar tais informações para aperfeiçoar seus programas e aumentar a interação com seu público. Dentre os principais desafios da análise de dados de mídias sociais encontram-se a análise de sentimento (determinação de polaridade em um texto, por exemplo, positivo ou negativo) e a desambiguação de sentido (determinação do contexto correto de palavras polis-sêmicas). Essa dissertação tem como objetivo usar técnicas de aprendizagem de máquina para a criação de uma ferramenta de apoio à TV Social com contribuições na automatização dos processos de análise de sentimento e desambiguação de sentido de mensagens postadas no Twitter.

The educational game Calangos is based on the ecological modeling of a real case of lizards that inhabit the Dunes of the Middle São Francisco River, in the state of Bahia - Brazil. The goal of the game is to enable students to interact with an environment that promotes a proper understanding of ecological and evolutionary processes. The game should serve as a tool to support the teaching and learning of ecology and evolution to high school students. For the Calangos Game to achieve this goal, central concepts of evolution and ecology should be properly incorporated in the game. Thus, the first scientific challenge of the project, in addition to the technological challenge of developing the game itself, is related to modeling the population dynamics and evolutionary biology in the context of Calangos. To investigate these aspects independently of the game, this dissertation proposes a simulator for Calangos, as well as a genetic-evolutionary model for the lizards. Furthermore, it performs a set of experiments that examine the ecology and evolution of the lizards in the proposed simulated environment. More specifically, four experimental scenarios and three difficulty levels for each environmental scenario are proposed to carefully analyze the dynamics of populations and the influence of the evolution on the fertility and longevity of lizards populations located within the simulated environment. The results clearly show that in a balanced environment without predators it is possible to observe a dynamic equilibrium of populations in a typical Lotka-Volterra model of population dynamics. On the other hand, it is also observed that in the most hostile environments containing large numbers of predators, the capability of evolution allows the lizard species to survive in the environment, which does not occur if the lizards evolution is disabled during the simulations. In the context of the Calangos game, the results presented here serve as the initial proof of concept necessary for the modeling of the lizards to be incorporated in the game. O jogo eletrônico educativo Calangos é baseado na modelagem de um caso ecológico real relativo aos lagartos que habitam a região das Dunas do Médio São Francisco, no Estado da Bahia. O objetivo final do jogo é possibilitar ao estudante interagir com um ambiente que promova uma compreensão adequada de processos ecológicos e evolutivos da natureza. O jogo deve funcionar como ferramenta de apoio ao ensino e aprendizagem de ecologia e evolução no nível médio de escolaridade. Para que o Calangos atinja esse objetivo conceitos centrais de evolução e ecologia deverão ser incorporados adequadamente ao jogo. Nesse sentido, o primeiro desafio científico do projeto, que antecede aos desafios tecnológicos de desenvolvimento de jogos propriamente ditos, está relacionado à como modelar a dinâmica das populações e a biologia evolutiva no contexto do Calangos. Para investigar estes aspectos de forma independente do jogo, essa dissertação propõe um simulador para o Calangos, assim como uma modelagem genético-evolutiva para os lagartos e, na sequência, realiza um conjunto de experimentos que permitem analisar a ecologia e evolução dos lagartos no ambiente simulado. Mais especificamente, são propostos quatro cenários experimentais e três níveis de dificuldade ambiental para cada cenário, que permitirão analisar cuidadosamente a dinâmica das populações e influência da evolução na fecundidade e longevidade de populações de lagartos localizadas dentro do ambiente de simulação. Os resultados mostram que em um ambiente equilibrado e sem predadores é possível observar um equilíbrio dinâmico das populações, em um formato típico dos modelos clássicos de dinâmica populacional baseados nas equações de Lotka-Volterra. Por outro lado, observa-se também que em ambientes mais hostis contendo grande quantidade de predadores a capacidade de evolução dos lagartos permite a sobrevivência da espécie no ambiente, o que não ocorre caso os lagartos não possam evoluir durante as simulações. No contexto do jogo Calangos, os resultados apresentados aqui servem como a prova de conceito inicial necessária para a modelagem computacional dos lagartos a serem incorporados no jogo.

Universidade Presbiteriana Mackenzie A container is a broadly used solution for the cargo storage to be transported between ports, playing a central role in international trade. Consequently, ships grew in size in order to maximize their container transportation capacity in each trip. Due to increasing demand, container terminals face the challenges of increasing their service capacity and optimizing the loading and unloading time of ships. Optimization problems, such as these, often present features that make it impossible to obtain closed analytical solutions, requiring iterative search procedures in high-dimensional spaces, or subject to a combinatorial explosion of possible solutions. This dissertation presents the proposal of a novel meta-heuristic based on the Clonal Selection Algorithm, named MRC, to minimize the number of reshuffles in operations involving piles of containers. The performance of the proposed model was evaluated through simulations and results comparison with those obtained by algorithms from the literature under the same test conditions. The results obtained show that MRC is competitive in terms of minimizing the need of reshuffles, besides presenting a reduced processing time compared with models of similar performance. A utilização de contêineres é uma solução amplamente adotada para o armazenamento da carga a ser transportada entre portos, tornando-se de grande importância no comércio internacional e, consequentemente, navios cresceram de tamanho com o objetivo de transportar a maior quantidade possível de contêineres em cada viagem. Devido à crescente demanda, terminais de contêineres enfrentam os desafios de aumentar a sua capacidade de atendimento e otimizar os tempos de carregamento e descarregamento de navios. Problemas de otimização como estes geralmente apresentam características que inviabilizam a obtenção de soluções analíticas fechadas, requerendo processos iterativos de busca em espaços de dimensão muitas vezes elevada, ou ainda sujeitos a explosão combinatória de possíveis soluções. Esta dissertação apresenta a proposta de uma meta-heurística bioinspirada baseada no Algoritmo de Seleção Clonal para a minimização de rearranjos em operações que envolvem pilhas de contêineres, denominado MRC. O desempenho do algoritmo foi avaliado por meio de simulações e comparação dos resultados com os obtidos por algoritmos da literatura sob as mesmas condições de teste. Os resultados obtidos permitem concluir que o MRC possui resultados competitivos em termos de minimização de rearranjos, além de apresentar um tempo de processamento reduzido quando comparado aos modelos tradicionalmente empregados na solução desse tipo de problema.

Orientadora: Ana Carolina Lorena Dissertação (mestrado) - Universidade Federal do ABC. Programa de Programa de Pós-Graduação em Engenharia da Informação, 2012

Orientador: Fernando José Von Zuben Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação Resumo: O dinamismo do mundo moderno traz consigo grandes desafios científicos e tecnológicos, particularmente junto a problemas de otimização. Problemas antes tratados de forma estática estão sendo reformulados para incorporar esse dinamismo, exigindo com isso novas estratégias de solução. Meta-heurísticas populacionais para otimização surgem então como abordagens promissoras, visto que favorecem a exploração do espaço de busca e contribuem para a adaptação ao dinamismo do ambiente. Foram tratados aqui algoritmos de estimação de distribuição (AEDs), os quais empregam modelos probabilísticos para identificar regiões promissoras do espaço de busca. Pelo fato de serem raras e limitadas as propostas de AEDs para problemas dinâmicos, principalmente em espaços de busca contínuos, foram concebidos AEDs baseados em modelos de mistura gaussianos flexíveis, auto-controláveis e com baixo custo computacional, incluindo ainda operadores de manutenção de diversidade e de controle de convergência. Uma extensa comparação com métodos alternativos de otimização para ambientes dinâmicos foi realizada e, em várias situações, a proposta deste trabalho superou o desempenho de métodos considerados estado-da-arte Abstract: The dynamism of the modern world gives rise to huge scientific and technological challenges. Problems until recently being treated as static are now being reformulated to incorporate that dynamism, thus requiring novel solution strategies. Population-based metaheuristics devoted to optimization emerge as promising approaches, given that they promote an effective exploration of the search space and contribute to the adaptation to the dynamism of the environment. Estimation of distribution algorithms (EDAs) were considered here, which make use of probabilistic models to identify promising regions of the search space. Due to the fact that the proposals of EDAs for dynamic problems are rare and limited, mainly in real-parameter search spaces, EDAs were conceived based on flexible Gaussian mixture models, self-controlable and computationally inexpensive steps, including diversity maintenance and convergence control mechanisms. An extensive comparison with alternative optimization methods for dynamic environments was accomplished and, in many situations, the proposed technique overcame the performance produced by state-of-the-art methods Mestrado Engenharia de Computação Mestre em Engenharia Elétrica

Orientador: Marco Antonio Garcia de Carvalho Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Tecnologia Resumo: O particionamento de grafos tem sido amplamente utilizado como meio de segmentação de imagens. Uma das formas de particionar grafos é por meio de uma técnica conhecida como Corte Normalizado, que analisa os autovetores da matriz laplaciana de um grafo e utiliza alguns deles para o corte. Essa dissertação propõe o uso de Corte Normalizado em grafos originados das modelagens por Quadtree e Árvore dos Componentes a fim de realizar segmentação de imagens. Experimentos de segmentação de imagens por Corte Normalizado nestas modelagens são realizados e um benchmark específico compara e classifica os resultados obtidos por outras técnicas propostas na literatura específica. Os resultados obtidos são promissores e nos permitem concluir que o uso de outras modelagens de imagens por grafos no Corte Normalizado pode gerar melhores segmentações. Uma das modelagens pode inclusive trazer outro benefício que é gerar um grafo representativo da imagem com um número menor de nós do que representações mais tradicionais Abstract: The graph partitioning has been widely used as a mean of image segmentation. One way to partition graphs is through a technique known as Normalized Cut, which analyzes the graph's Laplacian matrix eigenvectors and uses some of them for the cut. This work proposes the use of Normalized Cut in graphs generated by structures based on Quadtree and Component Tree to perform image segmentation. Experiments of image segmentation by Normalized Cut in these models are made and a specific benchmark compares and ranks the results obtained by other techniques proposed in the literature. The results are promising and allow us to conclude that the use of other image graph models in the Normalized Cut can generate better segmentations. One of the structures can also bring another benefit that is generating an image representative graph with fewer graph nodes than the traditional representations Mestrado Tecnologia e Inovação Mestre em Tecnologia

Fundo Mackenzie de Pesquisa Molecular replication was introduced as a possible theory to explain the origin of life. Since their proposal they have been extensively studied from a biochemical perspective. This work proposes a taxonomy for the main properties of replicators that are important for building computational tools to solve complex problems as well as introduces two computational models for these entities in order to observe and analyze the behavior of these models in light of the natural properties of replicators introduced. A replicação molecular foi introduzida como uma possível teoria para explicar a origem da vida. Desde sua proposição, ela vem sendo estudada extensivamente a partir de uma perspectiva bioquímica. Baseado na literatura de replicadores moleculares, esta dissertação organiza e propõe uma taxonomia para as principais propriedades dos replicadores que sejam interessantes para a construção de ferramentas computacionais voltadas para a solução de problemas complexos na engenharia e na computação, bem como introduz dois modelos computacionais baseado nessas entidades a fim de observar e analisar o comportamento destes modelos sob a luz das propriedades dos replicadores naturais discutidas nesta dissertação.

Fundo Mackenzie de Pesquisa The large number of data generated by people and organizations has stimulated the research on effective and automatic methods of knowledge extraction from databases. This dissertation proposes two new bioinspired techniques, named cPSC and oPSC, based on the Particle Swarm Optimization Algorithm (PSO) to solve data clustering problems. The proposed algorithms are applied to data and text clustering problems and their performances are compared with a standard algorithm from the literature. The results allow us to conclude that the proposed algorithms are competitive with those already available in literature, but bring benefits such as automatic determination of the number of groups on the dataset and a search for the best partitioning of the dataset considering an explicit cost function. A grande quantidade de dados gerados por pessoas e organizações tem estimulado a pesquisa sobre métodos efetivos e automáticos de extração de conhecimentos a partir de bases de dados. Essa dissertação propõe duas novas técnicas bioinspiradas, denominadas cPSC e oPSC, baseadas no algoritmo de otimização por enxame de partículas (PSO - Particle Swarm Optimization) para resolver problemas de agrupamento de dados. Os algoritmos propostos são aplicados a problemas de agrupamento de dados e textos, e seus desempenhos são comparados com outros propostos na literatura específica. Os resultados obtidos nos permitem concluir que os algoritmos propostos são competitivos com aqueles já disponíveis na literatura, porém trazem outros benefícios como a determinação automática do número de grupos nas bases e a efetuação de uma busca pelo melhor particionamento possível da base considerando uma função de custo explícita.

Fundo Mackenzie de Pesquisa Cellular automata have been studied as computer models in many different forms. Several of its properties have been widely explored, among which reversibility stands out. This property is able to provide a cellular automaton the possibility of having their temporal evolution regenerated backward in time, regardless of its initial configuration, through an inverse cellular automaton. Reversibility is such a well characterized concept that many fundamental results associated with it have been obtained, such as the development of algorithms to enumerate all reversible one-dimensional cellular automata and the undecidability of this property for cellular automata in dimensions larger than 1. The driving force for the present research is to introduce a new concept involving the reversibility ability of a cellular automaton, the concept of partial reversibility, which is analysed herein according to the pre-images of all initial configurations of a rule, up to a certain length. This new concept may be useful for evolutionary searches for reversible cellular automata, to allow the use of cellular automata in tasks related somehow to the reversibility degree of a rule, or in applications where reversible rules are demonstrably employed, such as in cryptography. To that end, some parameters presumably related to reversibility are studied and compared, and empirical measures (lexicographical and numerical) are addressed. The results involving these empirical measures, showed that is possible to refer to a more partially reversible rule than another, besides revealing properties, apparently unknown so far, involving the pre-images of elementary rules. Os autômatos celulares têm sido estudados como modelos computacionais de diversas formas. Diversas de suas propriedades têm sido amplamente exploradas, entre elas destacando-se a reversibilidade. Esta propriedade é capaz de fornecer a um autômato celular a possibilidade de ter sua evolução temporal refeita para trás no tempo, independentemente de sua configuração inicial, através de um autômato celular inverso. A reversibilidade é um conceito tão bem caracterizado que muitos resultados fundamentais associados a ela têm sido obtidos, tais como o desenvolvimento de algoritmos para enumerar todos os autômatos celulares unidimensionais reversíveis e a indecidibilidade desta propriedade para autômatos celulares com dimensão maior que 1. A ideia principal deste trabalho é introduzir um novo conceito envolvendo a capacidade de reversibilidade de um autômato celular, o conceito de reversibilidade parcial, que é analisado com base nas pré- imagens de todas configurações iniciais de uma regra, até um determinado tamanho de reticulado. Este novo conceito pode ser útil em buscas evolutivas de autômatos celulares reversíveis, a fim de permitir a utilização de autômatos celulares em tarefas associadas de alguma forma ao grau de reversibilidade de uma regra, ou ainda, em aplicações onde as regras reversíveis são comprovadamente empregadas, tal como em criptografia. Para tanto, alguns parâmetros supostamente relacionados à reversibilidade são estudados e comparados, e medidas empíricas (lexicográficas e numéricas) são abordadas. Os resultados obtidos envolvendo essas medidas empíricas mostraram que é possível referir-se a uma regra mais parcialmente reversível do que outra, além de revelar propriedades, até então desconhecidas, envolvendo as pré-imagens das regras elementares.

Fundo Mackenzie de Pesquisa This dissertation discusses the use of bio-inspired algorithms for data clustering, with emphasis on a model of emergent collective behavior of agents and a new clustering algorithm called cBoids is presented. The cBoids algorithm is a variation of the classic Boids model. In this new algorithm, each Boid represents an object from the data base and the three original rules from the Boids model were modified so that the objects of the database have influence on the behaviour of the Boids. Two new rules have also been proposed, responsible for the creation and destruction of centroids, which represent the formed clusters. In the experiments conducted in this work the algorithm was successfully tested on four databases. Esta dissertação aborda o uso de algoritmos bioinspirados para a tarefa de agrupamento de dados , com ênfase nos modelos de comportamentos emergentes coletivos de agentes e um novo algoritmo de agrupamento de dados chamado cBoids é apresentado. O algoritmo cBoids é uma variação do clássico modelo Boids. Neste novo algoritmo, cada Boid representa um objeto da base de dados e as três regras originais do modelo Boids foram alteradas para que os objetos da base de dados influenciem o comportamento dos Boids. Duas novas regras também foram propostas, responsáveis pela criação e destruição de centróides, que representam os clusters formados. Nos experimentos realizados nesta dissertação o algoritmo foi testado com sucesso em quatro bases de dados.

Fundo Mackenzie de Pesquisa The learning of computer programming is fundamental in the formation of a computing professional. However, its learning is difficult and longlife, considering that every day new languages and environments appear in the labor market. In the Computer Science courses, many students have difficulties programming, the activity requires the learning of complex concepts. The development of computational environments to support the learning of programming is of great value in this scenario, which involves students, teachers and professionals. Many researches and studies have been developed and they provide important contributions in the construction of learning computing environments. This dissertation proposes the development of a tool to support the process of teaching and learning of programming to students, prioritizing interdisciplinary, with an approach based on the Method of Learning by Competence. It presents also a mechanism of Concept Pyramid as an alternative to the planning of learning for a student. To support teaching of computer programming, the tool, presented in this work, uses the Java programming language, motivated by the high demand for use in undergraduate courses. The students are classified by their prior knowledge of each concept and it is expected that from this information and the measure of the student s Conceptual Gap regarding Conceptual Pyramid of a concept is possible to develop a learning plan for each student. It is expected that the use of this tool, helping the process of teaching and learning in the classroom, contribute to make the representation of concepts, exercises and skills related to each discipline from an appropriate course. O aprendizado de programação de computadores é fundamental na formação de um profissional de computação. No entanto, esta atividade é de aprendizagem difícil, contínua e permanente, uma vez que a cada dia novas linguagens e ambientes surgem no mercado de trabalho. Nos cursos da área de computação, muitos estudantes apresentam dificuldades para aprender a programar, pois a atividade requer alto nível de competência e o aprendizado e domínio de conceitos complexos. O desenvolvimento de ambientes computacionais que apóiem a aprendizagem de programação é de grande valia nesse cenário, que envolve estudantes, professores e profissionais. Muitas pesquisas e trabalhos têm sido desenvolvidos nessa área, na medida em que fornecem contribuições importantes na construção de ambientes computacionais. Este trabalho apresenta uma ferramenta de suporte ao processo de ensinoaprendizagem de programação a alunos de graduação, priorizando a interdisciplinaridade, com uma abordagem baseada no método de aprendizagem por competências. Apresenta-se aqui também o mecanismo de Pirâmide Conceitual como uma alternativa ao planejamento de aprendizagem para o aluno. Como suporte ao ensino de programação, este trabalho utiliza a linguagem de programação Java, motivado pela alta demanda de utilização nos cursos superiores. Os estudantes são classificados por seus conhecimentos prévios em cada um dos conceitos e é esperado que a partir dessas informações e com a medida do Conceptual Gap com relação a Pirâmide Conceitual de determinado conceito seja possível desenvolver um plano de aprendizagem para esse aluno. Espera-se que a utilização desta ferramenta, auxiliando o processo de aprendizagem, contribua no sentido de tornar a representação de conceitos, exercícios e competências relacionados às disciplinas de um curso de Computação adequada.

Clustering is an important data mining task from the field of Knowledge Discovery in Databases. There are several algorithms capable of performing clustering tasks, and the most popular ones involve the calculation of a similarity or distance measure among objects from the database. Many algorithms can perform clustering in a simple and efficient manner, but have drawbacks as a way to get the optimal number of partitions and the possibility of getting stuck in local optima solutions. To try and reduce these drawbacks this dissertation proposes a new clustering algorithm based on Artificial Immune Systems. This algorithm is characterized by the generation of multiple simultaneous high quality solutions in terms of the number of partitions (clusters) for the database and the use of a cost function that explicitly evaluates the quality of partitions, minimizing the inconvenience of getting stuck in local optima. The algorithm was tested using four databases known in the literature and obtained satisfactory results in terms of the diversity of solutions, but has a high computational cost compared to other algorithms tested. Agrupamento de dados é uma importante tarefa da mineração de dados e descoberta de conhecimentos em bases de dados. Existem diversos algoritmos capazes de realizar a tarefa de agrupamento de dados, sendo que os mais populares envolvem o cálculo de similaridade ou distância entre objetos da base de dados. Boa parte dos algoritmos pode agrupar os dados de forma simples e eficiente, mas possui inconvenientes como a forma de obter o número ótimo de partições e a possibilidade de ficar preso em ótimos locais. Para tentar diminuir estes inconvenientes essa dissertação propõe um novo Algoritmo Imunológico para Agrupamento de Dados baseado em Sistemas Imunológicos Artificiais. Esse algoritmo é caracterizado pela geração de múltiplas soluções simultâneas de boa qualidade no que tange o número de partições (grupos) para a base de dados e uma função de custo que avalia explicitamente a qualidade dessas partições, minimizando o inconveniente de ficar preso em ótimos locais. O algoritmo foi testado utilizando quatro bases de dados conhecidas na literatura e obteve resultados satisfatórios no que tange a diversidade das soluções encontradas, mas apresentou um custo computacional elevado em relação a outros algoritmos testados.

Wolfram Research, Inc. Cellular automata (CAs) can be defined as discrete dynamical systems over n-dimensional networks of locally connected components, whose evolution occur in a discrete, synchronous and homogeneous fashion. Among their several applications, they have been used as a tool for complex systems modeling governed by fundamental laws of conservation (number-conserving cellular automata) or reversibility (reversible cellular automata). Another fundamental property that can be observed in CAs is regarding to their linearity (linear cellular automata) or nonlinearity. Usually, linear phenomena present low dynamic complexity, however, nonlinear phenoma can present complex behaviours like sensitive dependence on initial conditions and routes to chaos. This work focuses on investigating properties of cellular automata belonging to the intersection of those four classes, namely, reversible, number-conserving, and linear or nonlinear cellular automata. After presenting basic definitions, the notions of number-conserving cellular automata, conservation degree and reversibility are reviewed. Following, a dynamical characterisation parameter which relates the reversibility property of a onedimensional cellular automaton and the pre-images of their basic blocks is introduced, and some proofs of its general properties are given. Empirical observations herein suggest that a cellular automaton is reversible and number-conserving if, and only if, its local transition function is a composition of the local transition functions of the reversible, number-conserving cellular automata with neighbourhood size n=2; such an observation was drawn for neighbourhood sizes n∈{2, 3, 4, 5, 6} and number of states q=2; n∈{2, 3} and q=3; n∈{2, 3} and q=4. A proof for such a conjecture would allow the enumeration between neighbourhood lengths and the quantity of reversible, numberconserving cellular automata in the corresponding space, which can be easily identified by working out the compositions of the local transition functions with n=2. Finally, some relationships between reversible, number-conserving, linear and nonlinear CA rules, their spatio-temporal diagrams and basin of attraction fields are presented. Autômatos celulares (ACs) podem ser definidos como sistemas dinâmicos sobre redes ndimensionais de componentes localmente conectados, cuja evolução ocorre de forma discreta, síncrona e homogênea. Dentre suas diversas aplicações, têm sido utilizados como ferramenta para modelagem de sistemas complexos regidos por leis fundamentais de conservação (autômatos celulares conservativos) ou reversibilidade (autômatos celulares reversíveis). Outra propriedade fundamental que pode ser observada nos ACs diz respeito à sua linearidade (autômatos celulares lineares) ou nãolinearidade. Fenômenos lineares normalmente apresentam menor complexidade dinâmica, enquanto fenômenos não-lineares podem apresentar propriedades tais como sensibilidade às condições iniciais e rotas para caos. O presente trabalho concentra-se na investigação de propriedades de autômatos celulares unidimensionais pertencentes à interseção dessas quatro classes, isto é, autômatos celulares unidimensionais conservativos, reversíveis, e lineares ou não-lineares. Após definições básicas, são revisitados os conceitos de conservabilidade e reversibilidade. Em seguida, introduz-se um parâmetro de caracterização dinâmica que relaciona a distribuição do número de pré-imagens dos blocos básicos à reversibilidade de autômatos celulares unidimensionais e apresentam-se algumas demonstrações decsuas propriedades gerais. Observações empíricas aqui realizadas sugerem que um autômato celular unidimensional é conservativo e reversível se, e somente se, sua função local de transição de estados é uma composição das funções locais de transição de estado dos autômatos celulares conservativos e reversíveis de vizinhança de comprimento n=2; tal observação foi constatada para vizinhanças de comprimento n∈{2, 3, 4, 5, 6} e quantidade de estados q=2; n∈{2, 3} e q=3; n∈{2, 3} e q=4. Uma demonstração para tal conjectura permitiria estabelecer uma enumeração entre os comprimentos das vizinhanças e a quantidade de autômatos celulares unidimensionais conservativos e reversíveis no espaço correspondente, os quais podem ser facilmente identificados através do cálculo das composições das funções locais de transição de estados com n=2. Por fim, apresentam-se relações entre as classes dos ACs conservativos, reversíveis, lineares e não-lineares, suas dinâmicas espaçotemporais e campos de bacias de atração.

Wolfram Research, Inc. Cellular automata are discrete dynamical systems composed of simple, locally connected structures (the cells), general in terms of their computational power, and that display complex patterns of behaviour. The purpose of this work was to expand previous studies by Zanon (2006), on non-uniform, one-dimensional cellular automata with nonlocal neighbourhood, in order to verify the existence of rules of these kinds of automata to solve the density classification task, that is, the determination of the predominant bit in a binary string. Our concern here was to look for solutions of the problem mainly by evolutionary computation means, to solve it in a non-trivial fashion, i.e., without including in the solution the majority rule over the entire lattice, and, at the same time, with the target of inferring common features for the solutions that would be found. The results achieved led to an expansion in the quantity of perfect solutions available in the literature, but it became clear that all of them have at least one of the rules involved able to account for the entire lattice at once, an evidence that solutions without rules with global action may not exist. Furthermore, the following observations have been made for the type of automata we considered: even distinct automata may have the same temporal evolution; a certain degree of flexibility is allowed in the total balancing of the rules present in a solution of the density classification task; and, in principle, no common patterns seem to exist between solutions for lattices with 3 and 5 cells, thereby suggesting the impossibility of constructing a solution to the problem from another of a smaller lattice. Autômatos celulares são sistemas dinâmicos discretos, formados por estruturas simples (as células) conectadas localmente entre si, gerais em termos de seu poder computacional, e que apresentam padrões de comportamento bastante complexos. O intuito deste trabalho foi expandir estudos anteriores de Zanon (2006), sobre autômatos celulares unidimensionais não-uniformes, com vizinhança não-local, visando verificar a existência de autômatos desse tipo na resolução da tarefa da classificação de densidade, isto é, a determinação do bit predominante em uma cadeia binária. Interessou-nos aqui descobrir soluções do problema principalmente por meio de buscas evolutivas, resolvê-lo de forma não trivial, isto é, sem a necessidade da regra da maioria sobre todo o reticulado, e objetivando inferir características necessárias para as soluções que viessem a resolver o problema. Os resultados obtidos levaram a uma expansão da quantidade de soluções perfeitas reportadas na literatura, mas observou-se que todas elas contém pelo menos uma das regras envolvidas tomando todo o reticulado como base de ação, uma evidência da impossibilidade de existir soluções sem regras individuais de ação global. Adicionalmente, as seguintes constatações foram feitas para os autômatos celulares do tipo considerado: mesmo autômatos distintos entre si podem ter a mesma evolução temporal; uma flexibilização do balanceamento total das regras na solução do problema da classificação de densidade é conseguida; e, em princípio, não há padrões nas soluções perfeitas para reticulados de 3 e 5 células, sugerindo a impossibilidade de se construir uma solução a partir de outra de menor tamanho de reticulado.

Orientador: Akebo Yamakami Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação Resumo: O objetivo desta dissertação é explorar a utilização de um Sistema Imunológico Artificial, baseado no princípio de Seleção Clonal, na resolução de problemas de Otimização Multiobjetivo. Os Sistemas Imunológicos Artificiais apresentam, em sua estrutura elementar, as principais características requeridas para a resolução de problemas de Otimização Multiobjetivo: exploração, explotação, paralelismo, elitismo, memória, diversidade, mutação e clonagem proporcionais à afinidade e população dinâmica. A abordagem proposta utiliza o conceito de Pareto dominância e factibilidade para identificar os anticorpos (soluções) que devem ser clonados. Nos experimentos, foram consideradas algumas situações importantes que podem aparecer nos problemas reais: presença de restrições (lineares e não-lineares) e formato da Fronteira de Pareto (convexa, côncava, contínua, descontínua, discreta, não-uniforme). Na maioria dos problemas, o algoritmo obteve resultados bons e competitivos quando comparados com as propostas da literatura. Palavras-chave: Otimização Multiobjetivo, Algoritmos Bio-inspirados, Sistemas Imunológicos Artificiais, Seleção Clonal Abstract: The aim of this work is to explore an Artificial Immune System, based on the Clonal Selection principle, in the solution of Multiobjective Optimization problems. Artificial Immune Systems have, in their elementary structure, the main characteristics required to solve Multiobjective Optimization problems: exploration, exploitation, paralelism, elitism, memory, diversity, mutation and proliferation proportional to the affinity, and dynamic repertorie. The proposed algorithm uses the Pareto dominance concept and feasibility to identify the antibodies (solutions) that must to be cloned. In the experiments, some important situations that occurs in real problems were considered: the presence of constraints (linear and non-linear) and Pareto Front format (convex, concave, continuous, discontinuous, discrete, non-uniforme). In the major part of the problems, the algorithm obtains good and competitive results when compared with approaches from the literature. Keywords: Multiobjective Optimization, Bio-inspired Algorithms, Artificial Immune Systems, Clonal Selection Mestrado Telecomunicações e Telemática Mestre em Engenharia Elétrica

Orientadores: Ricardo Ribeiro Gudwin, Leandro Nunes de Castro Silva Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação Resumo: A Internet tornou-se um dos principais meios de comunicação da atualidade, reduzindo custos, disponibilizando recursos e informação para pessoas das mais diversas áreas e interesses. Esta dissertação desenvolve e aplica duas abordagens de computação inspirada na biologia aos problemas de otimização do processo de busca e recuperação de informação na web e agrupamento de textos. Os algoritmos investigados e modificados são o algoritmo genético e o algoritmo de agrupamento por colônia de formigas. O objetivo final do trabalho é desenvolver parte do conjunto de ferramentas que será usado para compor o núcleo de uma comunidade virtual acadêmica adaptativa. Os resultados obtidos mostraram que o algoritmo genético é uma ferramenta adequada para otimizar a busca de informação na web, mas o algoritmo de agrupamento por colônia de formigas ainda apresenta limitações quanto a sua aplicabilidade para agrupamento de textos. Abstract: The Internet became one of the main sources of information and means of communication, reducing costs and providing resources and information to the people all over the world. This dissertation develops and applies two biologically-inspired computing approaches, namely a genetic algorithm and the ant-clustering algorithm, to the problems of optimizing the information search and retrieval over the web, and to perform text clustering. The final goal of this project is to design and develop some of the tools to be used to construct an adaptive academic virtual community. The results obtained showed that the genetic algorithm can be feasibly applied to the optimizing information search and retrieval, whilest the ant-clustering algorithm needs further investigation in order to be efficiently applied to text clustering. Mestrado Engenharia de Computação Mestre em Engenharia Elétrica

Orientadores: Fernando Jose Von Zuben, Mauricio Fernandes Figueiredo Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação Resumo: A concepção de sistemas autônomos de navegação para robôs móveis, havendo múltiplos objetivos simultâneos a serem atendidos, como a coleta de lixo com manutenção da integridade, requer a adoção de técnicas refinadas de coordenação de módulos de comportamento elementar. Modelos de redes imunológicas artificiais podem então ser empregados na proposição de um controlador concebido com base em um processo de mapeamento dinâmico. Os anticorpos da rede são responsáveis pelos módulos de comportamento elementar, na forma de regras do tipo -, e as conexões são responsáveis pelos mecanismos de estímulo e supressão entre os anticorpos. A rede iniciará uma resposta imunológica sempre que lhe forem apresentados os antígenos. Estes antígenos representam a situação atual capturada pelos sensores do robô. A dinâmica da rede é baseada no nível de concentração dos anticorpos, definida com base na interação dos anticorpos e dos anticorpos com os antígenos. De acordo com o nível de concentração, um anticorpo é escolhido para definir a ação do robô. Um processo evolutivo é então responsável por definir um padrão de conexões para a rede imunológica, a partir de uma população de redes candidatas, capaz de maximizar o atendimento dos objetivos durante a navegação. Resulta então um sistema híbrido que tem a rede imunológica como responsável por introduzir um processo dinâmico de tomada de decisão e tem agora a computação evolutiva como responsável por definir a estrutura da rede. Para que fosse possível avaliar os controladores (redes imunológicas) a cada geração do processo evolutivo, um ambiente virtual foi desenvolvido para simulação computacional, com base nas características do problema de navegação. As redes imunológicas obtidas através do processo evolutivo foram analisadas e testadas em novas situações, apresentando capacidade de coordenação em tarefas simples e complexas. Os experimentos preliminares com um robô real do tipo Khepera II indicaram a eficácia da ferramenta de navegação Abstract: The design of an autonomous navigation system for mobile robots, with simultaneous objectives to be satisfied, as garbage collection with maintenance of integrity, requires refined coordination mechanisms to deal with modules of elementary behavior. Models of artificial immune networks can then be applied to produce a controller based on dynamic mapping. The antibodies of the immune network are responsible for the modules of elementary behavior, in the form of - rules, and the connections are responsible for the mechanisms of stimulation and suppression of antibodies. The network will always start an immune response when antigens are presented. These antigens represent the current output of the robot sensors. The network dynamics is based on the levels of antibody concentration, provided by interaction among antibodies, and among antibodies and antigens. Based on its concentration level, an antibody is chosen to define the robot action. An evolutionary process is then used to define the connection pattern of the immune network, from a population of candidate networks, capable of maximizing the objectives during navigation. As a consequence, a hybrid system is conceived, with an immune network implementing a dynamic process of decision-making, and an evolutionary algorithm defining the network structure. To be able to evaluate the controllers (immune networks) at each iteration of the evolutionary process, a virtual environment was developed for computer simulation, based on the characteristics of the navigation problem. The immune networks obtained by evolution were analyzed and tested in new situations and presented coordination capability in simple and complex tasks. The preliminary experiments on a real Khepera II robot indicated the efficacy of the navigation tool Mestrado Engenharia de Computação Mestre em Engenharia Elétrica

Orientadores: Ricardo Ribeiro Gudwin, Alvaro João Magalhães de Queiroz Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação Mestrado Engenharia de Computação Mestre em Engenharia Elétrica