Made available in DSpace on 2019-03-29T23:12:57Z (GMT). No. of bitstreams: 0 Previous issue date: 2008-09-30 / To understand the behavior of criminal events and how they are distributed is important information for planning urban police. The identification of the main aspects that influence criminal occurrence allows for better use and distribution of police resources. However, the evaluation of this problem is complex because it involves many variables. This dissertation deals with this issue proposing the use of a simulation model of criminal behavior, in which were inserted the characteristics that are necessary for crime simulation in a region. At the end of the simulation, we can consider the spatial and temporal distribution of crimes generated by the simulator to be similar to the real distribution of crimes occurred in a region. The model was built based on multiagent systems, where each agent is responsible for representing persons and objects that are placed in an environment that is shared by all. The behavior of agents that are part of this model follows a bio-inspired model and is based on a swarm intelligence algorithm. To evaluate the model, comparative analysis were performed with the crime distributions generated by the criminal model and the real distribution of crimes occurred. In order to perform this analysis, a characterization of criminal data of the city of Fortaleza was performed and this data was very important to validate this research. Keywords: Multiagent Simulation, Crime Model, Swarm Intelligence, Genetic Algorithms and Artificial Intelligence. / Entender o comportamento dos eventos criminais e como eles estão distribuídos é uma importante informação para o planejamento do policiamento urbano. A identificação dos principais aspectos que influenciam a ocorrência de crimes permite uma melhor utilização e distribuição dos recursos policiais. Contudo, este é um problema complexo de ser avaliado, pois envolve diversas variáveis. Este trabalho aborda esta questão propondo o emprego de um modelo de simulação criminal, no qual foram inseridas as características necessárias para a simulação dos crimes em uma região e ao final da simulação poderemos considerar a distribuição espacial e temporal dos crimes gerada pelo simulador como similar à distribuição real dos crimes ocorridos na região. O modelo foi construído utilizando uma arquitetura de sistemas multiagentes, onde cada agente é responsável por representar um indivíduo no ambiente que é compartilhado por todos. O comportamento dos agentes que fazem parte desse modelo segue um modelo bio-inspirado, baseado em no algoritmo de inteligência coletiva. Para avaliar o modelo, foram realizadas análises comparativas entre as distribuições dos crimes geradas pelo modelo criminal e a distribuição real de crimes ocorridos, para essa análise foi realizada uma caracterização dos dados criminais da cidade de Fortaleza, dados estes importantes para a validação dessa pesquisa. Palavras-chave: Simulação Multiagente, Modelo Criminal, Inteligência Coletiva, Algoritmo Genético e Inteligência Artificial

Made available in DSpace on 2019-03-29T23:16:04Z (GMT). No. of bitstreams: 0 Previous issue date: 2009-08-21 / Real-world databases may contain several missing values, which may degrade the performance of data mining algorithms running over them, making it hard to analyze data. This problem is usually dealt with missing value imputation. The present work evaluates how imputation by numerical optimization using bio-inspired algorithms may affect the performance of classifiers induced over pre-processed data. Here, three techniques were conceived: imputation using genetic algorithm (GA), imputation using particle swarm optimization (PSO), and imputation using cooperative co-evolution. In order to analyze the proposed techniques, six different datasets from the UCI Machine Learning Repository and five well known classification algorithms were adopted. In this analysis, efficiency and efficacy criteria were taken into account. In order to compare the results obtained, two traditional missing value imputation techniques were used, namely, imputation using mean or mode, and imputation using the KNN algorithm. The study shows that all the imputation techniques considered could increase the performance of the resulting classifiers. The obtained results do not point out an optimal method, adequate to all situations. The experiments, however, showed that, in general, the techniques that use bio-inspired algorithms were the most effective, while traditional techniques entailed better computational performance. It should also be observed that the heuristic techniques PSO and cooperative co-evolution, still not much explored in the context of data preprocessing, could have prevailed in several experiments. Keywords: Data mining, Data preparation, Missing value imputation, Metaheuristics, Genetic algorithms, Particle swarm optimization, Cooperative co-evolution. / Diversas bases de dados reais se caracterizam pela ausência marcante de determinados valores de seus atributos. Esses dados ausentes podem vir a degradar sobremaneira o desempenho de algoritmos de mineração de dados, dificultando a análise resultante. Uma maneira comum de tratar esse problema é via imputação, ou seja, estimação dos valores faltantes a partir de outros existentes na base. Este trabalho avalia como uma abordagem de imputação por otimização numérica utilizando algoritmos bio-inspirados pode vir a aprimorar o desempenho de classificadores induzidos sobre as bases pré-processadas. Três técnicas foram empregadas segundo esta abordagem: imputação utilizando algoritmo genético (GA), imputação utilizando otimização por enxame de partículas (PSO) e imputação utilizando co-evolução cooperativa. Com o intuito de analisar as técnicas propostas, em termos de eficiência e eficácia, seis bases de dados do repositório UCI e cinco populares algoritmos de classificação foram adotados. Para efeito de comparação, foram empregadas ainda outras duas técnicas tradicionais de imputação: a imputação pela média ou moda e a imputação fazendo uso do algoritmo KNN. O estudo mostra que todas as técnicas de imputação consideradas são capazes de elevar o desempenho dos classificadores. Os resultados obtidos não apontam para um método ótimo para todas as situações. Contudo, os experimentos sugerem que, em geral, as técnicas que fazem uso de algoritmos bio-inspirados são as mais eficazes ao passo que as técnicas tradicionais são as de melhor desempenho computacional. Observa-se também que os algoritmos co-evolução cooperativa e PSO, ainda não muito explorados no contexto de pré-processamento de dados, sobressaíram-se em diversos experimentos realizados. Palavras-Chave: Mineração de dados, Pré-processamento de dados, Imputação de valores faltantes, Metaheurísticas, Algoritmos genéticos, Otimização por enxame de partículas, Co-evolução cooperativa.

Made available in DSpace on 2019-03-29T23:22:38Z (GMT). No. of bitstreams: 0 Previous issue date: 2009-12-28 / Wireless sensor networks (WSNs) are very usefull in a wide range of applications. However, the sensor nodes that composes these WSNs are very limited devices. Their batteries cannot supply energy for a lifetime as long as desired. In a particular scenario, the areas where these devices are deployed are inaccessible so these batteries replacements are unfeasible. In this situation the energy consumption plays a very important role and must be well optimized. Recent literature presented an integer programming model for optimizing this energy consumption. The Generate and Solve is a new hybrid methodology. The integrative collaboration of Genetic Algorithms and Linear Integer Programming merged their strong points and offered excellent results on cutting and packing problem domains. However, its original implementation had some problems which limits the results, one of them is the density explosion. This methodology has been adapted and enhanced to fix these problems and extend the capacity of this model to larger problem instances. Thus, the WSN lifetime can be much longer than before. Comparing the results against literature, the WSN lifetime planned by Generate and Solve is 150% longer and it is capable of handling problem instances with a number of sensor nodes 125% larger. Keywords: Wireless sensor networks, Optimization, Hybridization, Genetic Algorithms, Linear Integer Programming. / Redes de sensores sem fios (RSSF) são muito úteis em uma ampla gama de aplicações. Entretanto, os nós sensores que compõem essas RSSF's são dispositivos muito limitados. Suas baterias não podem suprir a energia de uma vida útil tão longa quanto desejada. Em um cenário particular, as áreas nas quais estes dispositivos são instalados são inacessíveis, logo, as trocas dessas baterias são inviáveis. Nesta situação, o consumo de energia tem um papel muito importante e deve ser bem otimizado. Uma literatura recente apresentou um modelo de programação inteira para otimizar este consumo de energia. A Gerar e Resolver é uma nova metodologia híbrida. A colaboração integrativa entre algoritmos genéticos e programação linera inteira fundiu os seus pontos fortes e ofereceu exelentes resultados em domínios de cortes e empacotamento. Entretanto, sua implementação original teve alguns problemas os quais limitam os resultados, um deles é a explosão da densidade. Esta metodologia foi adaptada e melhorada para corrigir esses problemas e extender a capacidade deste modelo para instancias de problemas maiores. Desta forma, a vida útil da RSSF pode ser bem maior que anteriormente. Comparando os resultados com a literatura, o tempo de vida da RSSF planejada pela Gerar e Resolver é 150% mais longa e ela é capaz de lidar com instâncias de problemas com um número de nós sensores 125% maior. Palavras-chave: Redes de sensores sem fios, Otimização, Hibridização, Algorítmos Genéticos, Programação Linear Inteira.

Made available in DSpace on 2019-03-29T23:33:04Z (GMT). No. of bitstreams: 0 Previous issue date: 2012-07-27 / The selection of components in ensembles of classifiers is a very common activity in the field of Machine Learning with several studies showing its effectiveness in obtaining significant gains in accuracy. However, the most studied classification task involves mutually exclusive labels (classes). The objective of this work is to present a study on the selection of components in ensembles of multi-label classifiers, whereby an instance can become associated with more than one label. Two search approaches for the component selection were used, one based on Genetic Algorithms and the other based on Hill Climbing. Conversely, two types of evaluation measures were adopted for ensemble selection: one based on multilabel accuracy measures and the other based on well known diversity measures for ensembles, which were modified to handle the multilabel case. Another selection approach was also conceived to assign different ensembles to different labels of the labelset. Specifically for generating the RAkEL components, 10 well known learning algorithms for inducing one-label classifiers were used, namely, Naïve Bayes, RBF Neural Networks, Support Vector Machines, J48, REP Tree, IBk, Decision Stump, OneR, PART, and Decision Table. A systematic empirical study was conducted on seven publicly available datasets, involving two ensemble models, each making use of one of the well known multi-label classifiers RAkEL and ML-RBF. In general, the results achieved show that the ensembles produced via ensemble selection can yield better results than the full ensembles and some of their components. The ensemble selection type based on multilabel accuracy measures performed usually better than the other based on diversity measures. Finally, among the search procedures for conducting the selection, none has prevailed over the other. Keywords: Machine Learning, Multi-label Classification, Ensembles, Ensemble Selection, Diversity Measures, Genetic Algorithms, Hill Climbing. / A seleção de componentes em ensembles de classificadores é uma atividade muito comum no campo de Aprendizado de Máquina, com vários estudos comprovando sua efetividade em obter maiores ganhos de acuidade. Contudo, a tarefa de classificação mais investigada é a de rótulos, ou classes, mutuamente exclusivos. Nesse contexto, o objetivo deste trabalho é apresentar um estudo sobre a seleção de componentes em ensembles de classificadores multirrótulo, em que uma instância (padrão, exemplo) pode ser associada a mais de um rótulo. Os procedimentos de seleção investigados utilizaram a abordagem evolucionária dos Algoritmos Genéticos e o método de busca gulosa Subida da Encosta. Dois tipos de medidas de avaliação foram adotados para a seleção dos componentes: enquanto o primeiro tipo inclui métricas de acuidade já propostas para o caso multirrótulo, o segundo envolve medidas bem conhecidas de diversidade em ensembles, as quais sofreram modificações para tratar problemas de classificação multirrótulo. Foi analisada também uma abordagem de seleção de componentes que atribui distintos ensembles para distintos rótulos do problema. Um estudo empírico sistemático foi conduzido com base em sete conjuntos de dados disponíveis publicamente e envolvendo dois arranjos de ensembles, cada um fazendo uso de um dos conhecidos classificadores multirrótulo RAkEL e ML-RBF. Especificamente para gerar os componentes do RAkEL, foram escolhidos 10 algoritmos conhecidos de indução de classificadores único-rótulo, quais sejam, Naïve Bayes, Redes Neurais RBF, Máquinas de Vetores-Suporte, J48, REP Tree, IBk, Decision Stump, OneR, PART e Decision Table. Em geral, os resultados experimentais obtidos evidenciam que as diferentes abordagens de seleção de componentes podem melhorar o desempenho do novo ensemble em relação ao ensemble original e a alguns dos módulos-componentes. Dos tipos de seleção adotados, aquele que utilizou as métricas de acuidade geralmente apresentou os melhores resultados. Por outro lado, dos procedimentos de busca para a seleção, não houve um que obtivesse maior destaque que o outro. Palavras-chave: Aprendizado de Máquina, Classificação Multirrótulo, Ensembles, Seleção de Componentes, Medida de Diversidade, Algoritmos Genéticos, Subida da Encosta.

Made available in DSpace on 2019-03-29T23:32:55Z (GMT). No. of bitstreams: 0 Previous issue date: 2012-08-30 / The aim of this study is to establish a parallel between four bioinspired metaheuristic algorithms (namely, Genetic Algorithm, Differential Evolution, Particle Swarm Optimization, and Harmony Search), testing them with continuous optimization benchmark functions and assessing them based on data collected about the quality of the solutions they generate and based on the way they explore the search space. Novel techniques are proposed to collect data about the modus operandi of the algorithms using Voronoi Diagrams and through a division of the search space in bi-dimensional regions using Self-Organizing Maps. The use of these maps as a Visual Data Mining tool aims to process the resulting data and identify the available clusters. We wish to understand the influence of parameter calibration on the search behavior of the metaheuristic algorithms, as well as their sensitivity to dimension changes of the optimization functions they are solving. Furthermore, behavior profiles can be established and patterns can be defined, allowing us to analyze in detail the similarities/dissimilarities between the algorithms. All metaheuristics were implemented step-by-step to allow us to understand their inner workings, peculiarities, and also facilitate the tracking of their search behavior along their execution on the optimization problems. Keywords: Bioinspired Metaheuristics. Information Visualization. Visual Data Mining. Self-Organizing Maps. Kohonen Maps. Voronoi Diagrams. / Este trabalho tem por finalidade traçar um paralelo entre quatro algoritmos bio-inspirados de cunho meta-heurístico (a saber: Algoritmo Genético, Evolução Diferencial, Otimização por Enxame de Partículas e Busca Harmônica), testando-os em funções de benchmark de otimização contínua e avaliando-os com base em dados coletados sobre a qualidade das soluções geradas e sobre o modo de exploração do espaço de busca. São propostas aqui técnicas de coleta de informações sobre o modus operandi dos algoritmos que envolvem Diagramas de Voronoi e divisão do espaço de busca em regiões bidimensionais utilizando Mapas Auto-organizáveis. O uso desses mapas como ferramenta de Mineração Visual de Dados tem como objetivo avaliar os dados gerados e identificar os agrupamentos que foram formados. Procuramos entender a influência da alteração dos valores dos parâmetros das meta-heurísticas no seu comportamento ao longo do tempo, bem como a sua sensibilidade às mudanças de dimensão das funções de otimização que estão solucionando. Dessa forma, almeja-se traçar perfis de comportamento e definir a posteriori um padrão para possibilitar a análise mais detalhada das similaridades/dissimilaridades entre as abordagens. Todos os algoritmos utilizados foram implementados passo-a-passo a fim de entender as suas particularidades, esclarecer melhor seus mecanismos internos e facilitar o rastreamento do comportamento dos mesmos no ato da resolução dos problemas. Palavras-chave: Meta-heurísticas Bioinspiradas. Visualização da Informação. Mineração Visual de Dados. Mapas Auto-Organizáveis. Mapas de Kohonen. Diagramas de Voronoi.

Orientador: Marcelo Grafulha Vanti. / Dissertação (mestrado) - Universidade Regional de Blumenau, Centro de Ciências Tecnológicas, Programa de Pós-Graduação em Engenharia Elétrica.

Tese (doutorado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Engenharia Elétrica, Florianópolis, 2017. / Made available in DSpace on 2017-11-28T03:25:59Z (GMT). No. of bitstreams: 1 348184.pdf: 8542695 bytes, checksum: 00dbcf0646cad503237577f7ccf85fdb (MD5) Previous issue date: 2017 / Aparelhos auditivos binaurais consistem em um par de aparelhos que compartilham e processam os sinais sonoros que recebem em seus microfones. Decorrente disto, estes dispositivos podem explorar pistas binaurais de localização das fontes acústicas. Isto permite o desenvolvimento de técnicas de redução de ruído para processar os sinais recebidos com o intuito de criarem uma percepção mais verossímil do cenário acústico para o usuário de aparelhos auditivos. Neste sentido, uma técnica bastante utilizada em aparelhos binaurais é o filtro de Wiener multicanal (MWF ? Multichannel Wiener filter). Os coeficientes do MWF determinam um estimador linear para o sinal desejado de fala. Este estimador preserva as pistas binaurais de localização da fala e altera, contudo, as do ruído aditivo. Por esta razão, várias técnicas foram desenvolvidas com a finalidade de preservar as pistas binaurais do ruído. Algumas destas técnicas baseiam-se na extensão da função custo do erro quadrático médio através de um termo derivado a partir da definição matemática da pista de localização binaural denominada diferença de intensidade interaural (ILD ? Interaural leveld diference). Entretanto, a determinação dos coeficientes ótimos que minimizam estas funções custo requer o uso de técnicas de otimização numérica, o que pode acarretar em tempos de processamento e/ou recursos computacionais inadmissíveis em aplicações em tempo real. Diante disto, este trabalho propõe um algoritmo adaptativo para redução de ruído e preservação da ILD do sinal de ruído. O método proposto determina os coeficientes dos filtros lineares de forma iterativa, o que representa uma mudança de paradigma e uma redução de custo computacional em relação à técnicas anteriores. Para os cenários acústicos avaliados, o algoritmo desenvolvido diminui em 6,96 dB a métrica de preservação da ILD do ruído, tendo um aumento de apenas 0,98 dB na métrica de preservação da ILD da fala em relação ao MWF. As métricas de qualidade de fala, redução de ruído e inteligibilidade se mantém aproximadamente as mesmas no ouvido mais distante da fonte de ruído. Adicionalmente, resultados subjetivos mostram que o método proposto preserva a percepção da localização da fonte de ruído próximo de sua posição original. / Abstract : Binaural hearing aids are two devices which share and process the signals received in their microphones. Consequently, these devices can explore binaural localisation cues. This results in the development of noise reduction techniques which process the received signals to create a reliable perception of the acustic scenario for the hearing impaired person. In this sense, the techniques based on the multichannel Wiener filter (MWF) are extensivily used in applications of binaural hearing aids. The MWF coefficients produce a linear estimator of the desired speech component. This estimator preserves the speech binaural cues, and shifts the cues of the additive noise. Because of this, many techniques have been developed aiming to preserve the noise localisation cues. Some of that are based in the extension of the mean squared error cost function using a perceptualy motivated term based on the mathematical expresion of a binaural localization cue called interaurallevel difference (ILD). However, the technique uses numerical optimization approches to calculate the coefficients of linear noise reduction filters. Considering a real time application, this may result in unacceptable processing time and/or computational resources. For this reason, this work presents an adaptive algorithm for both noise reduction and preservation of noise ILDs. The proposed method calculates de linear filters using recursive equation which results in a reduction of the computacional cost with respect to the previews techniques. In the assessed acustic scenario, the method leads to a reduction of the noise ILD preservation measurement of up to 6.96 dB, and to an increase of just 0.98 dB in speech ILD preservation measurement, with respect to the MWF. The measures of speech quality, noise reduction and intelligibility are kept approximately the same in the ear in the opposite side of the noise source. In addition, subjective experiments show the proposed technique preserves the noise position perception near of the original noise source.

Made available in DSpace on 2019-03-29T23:15:55Z (GMT). No. of bitstreams: 0 Previous issue date: 2009-08-21 / This work presents a novel decision making approach developed upon two Multicriteria Decision Aiding (MCDA) classification methods. The classification methods are centered on the concept of prototypes, that are alternatives that serve as class representatives related to a given problem, and have their performance index very dependent upon the choice of values of some control parameters. In contrast with most MCDA classification research, which put more emphasis on the development of new methods, this study investigates the impact that the prototype selection task exerts on the classification performance exhibited by the classifiers under analysis. To overcome this problem and leverage the classifier performance, two techniques, one based on ELECTRE IV methodology and the other on a customized genetic algorithm, are employed in order to select the prototypes and calibrate the control parameters. To validate the devised classification approach, a case study based on the Alzheimer's disease (AD) was developed to assist clinicians and researchers in the AD early detection. Moreover, the experiments realized, involving different datasets, reveal that there are still some gaps in existing MCDA classification methods that can lead to an improvement of the methodology for the classification problems. Keywords: Multicriteria Decision Aiding, Classification, ELECTRE IV , Genetic Algorithm, Alzheimer's Disease. / Esse trabalho apresenta uma nova abordagem de tomada de decisão desenvolvida sobre dois métodos Multicritério de Apoio à Decisão (MCDA) na área de classificação. Os métodos de classificação são fundamentados no conceito de protótipos, que são alternativas que funcionam como representantes de classe de um determinado problema, e possuem sua performance dependente da escolha dos parâmetros de controle do algoritmo. Em contraste com a maioria das pesquisas relacionadas à MCDA, que colocam uma maior ênfase no desenvolvimento de novos métodos, esse estudo investiga o impacto que a tarefa de seleção de protótipos exerce na performance dos algoritmos de classificação em questão. Para superar esse problema e melhorar a performance dos classificadores, duas técnicas, uma baseada na metodologia ELECTRE IV e a outra em um algoritmo genético customizado, foram aplicadas para selecionar os protótipos e calibrar os parâmetros de controle. Para validar a abordagem de classificação criada, um estudo de caso baseado na doença de Alzheimer foi desenvolvido para ajudar médicos e pesquisadores na identificação precoce da doença. Além disso, os experimentos realizados, envolvendo diferentes conjuntos de dados, revelam que existem alguns espaços para melhoria nos métodos de classificação MCDA que podem levar a um avanço na metodologia dos problemas de classificação. Palavras-chave: DecisãoMulticritério, Classificação, ELECTRE IV, Algoritmo Genético, Doença de Alzheimer.

Made available in DSpace on 2019-03-29T23:27:56Z (GMT). No. of bitstreams: 0 Previous issue date: 2011-08-19 / Wireless sensor networks (WSN) are composed of a set of sensor nodes in order to detect and transmit a characteristic of the physical environment. These sensor nodes, after capturing an event, should communicate with a special node, called sink node. The use of a single sink node implies a bottleneck in the network of sensors, especially for applications requiring a heavy flow of data. Thus, research studies have led to the selection of routes in sensor networks with multiple sink nodes. The approach proposed by this work presents the application of Genetic Fuzzy Systems (SFGs) to estimate the quality of routes in WSNs, in order to realize the communication between multiple sensor nodes and multiple sink nodes. A Fuzzy Inference System of Mamdani is used to estimate the sink node best suited for communication at a given instant, based on some network characteristics such as energy and the number of hops. Genetic Algorithms (GAs) are employed to obtain the optimal setting of design parameters of the fuzzy inference system of Mamdani. The proposed route classification was applied by means of computer simulations to demonstrate the feasibility of the implemented approach. The results show a network of sensors with longer life, through an adequate choice of sink node used for sending packets across the network in order to find the best routes. / Redes de Sensores Sem Fio (RSSF) são compostas por um conjunto de nós sensores com o objetivo de detectar e transmitir alguma característica do meio físico. Estes nós sensores, depois de captar algum evento, devem se comunicar com um nó especial, denominado sink node. A utilização de um único sink node implica em um gargalo na rede de sensores, especialmente para aplicações que demandam um fluxo intenso de dados. Desta forma, as pesquisas têm direcionado estudos para a seleção de rotas em redes de sensores com múltiplos sink nodes. A abordagem proposta por este trabalho apresenta a aplicação de Sistemas Fuzzy Genéticos (SFGs) para a estimação da qualidade de rotas em RSSFs, de modo a realizar a comunicação entre múltiplos nós sensores e múltiplos sink nodes. Um Sistema de Inferência Fuzzy de Mamdani é utilizado para estimar o sink node mais adequado para a comunicação em um determinado instante, baseado em algumas características da rede, como a energia e o número de saltos. Algoritmos Genéticos (AGs) são empregados para obter o ajuste otimizado dos parâmetros de projeto do sistema de inferência fuzzy de Mamdani. A classificação das rotas foi aplicada, por meio de simulações computacionais, para demonstrar a viabilidade da abordagem implementada. Os resultados obtidos apresentam uma rede de sensores com maior tempo de vida, por meio da escolha adequada do sink node utilizado para o envio de pacotes pela rede, de forma a encontrar as melhores rotas.

Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2017-08-17T16:05:45Z No. of bitstreams: 1 texto completo.pdf: 2079237 bytes, checksum: 42491677e48c32006c0d10c2f53b0f35 (MD5) / Made available in DSpace on 2017-08-17T16:05:45Z (GMT). No. of bitstreams: 1 texto completo.pdf: 2079237 bytes, checksum: 42491677e48c32006c0d10c2f53b0f35 (MD5) Previous issue date: 2017-03-20 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Um dos desafios ao se agrupar documentos é encontrar uma boa medida de simila- ridade para documentos de textos, que seja capaz de gerar grupos coesos. Algumas medidas são baseadas no clássico modelo bag of words e consideram apenas o vo- cabulário do documento. Com isso, documentos semanticamente similares podem ser atribuídos a diferentes grupos se eles não compartilham o mesmo vocabulário. Por essa razão, medidas de similaridade semântica que usam conhecimento externo, como um corpus, dicionários ou banco de palavras, têm sido propostas na literatura. Neste trabalho, a medida Frequency Google Tri-grams Measures (FGTM) é proposta para identificar similaridade entre documentos baseado nas frequências dos termos nos documentos e no corpus Google n-grams. A comparação entre as frequências de um termo em um dado par de documentos pode quantificar a importância daquele termo para o assunto dos documentos, assumindo que um termo possui maior rele- vância para um documento se ele ocorre mais vezes. Adicionalmente, as frequências dos termos dos documentos no corpus Google n-grams permitem estimar semanti- camente suas similaridades. Adicionalmente, oito variantes de dois algoritmos de agrupamento são aplicadas a vários conjuntos de dados reais, com o objetivo de avaliar experimentalmente a qualidade dos grupos obtidos com a medida proposta e compará-la com outras medidas do estado da arte. Análises de complexidade computacional das medidas comparadas são apresentadas. Os resultados experi- mentais demonstram que a medida proposta melhora significativamente a qualidade dos agrupamentos de documentos, comprovado por testes estatísticos. Também é mostrado que, combinar resultados de agrupamento obtidos com bag of words e medida semântica obtém melhores resultados que adotar uma medida individualmente. Para finalizar, é feito um estudo sobre heurísticas para estimar o número K de gru- pos em agrupamento de textos. Uma versão modificada da heurística G-means é proposta e comparada com heurísticas da literatura. / One challenge for document clustering consists of finding a proper similarity me- asure for text documents, which enables the generation of cohesive groups. Some measures are based on the classic bag of words model and take into account the vocabulary of the documents solely. In doing so, semantically similar documents may reside in different clusters if they do not share the same vocabulary. For this reason, semantic similarity measures that use external knowledge, such as corpus, dictionaries, or word bases, have been proposed in the literature. In this paper, the Frequency Google Tri-grams Measure (FGTM) is proposed to assess similarity between documents based on the frequencies of terms in the compared documents and Google n-gram corpus. The comparison between the frequencies of a term in a given pair of documents can quantify the importance of that term to the documents’ subjects, assuming that a term is relevant to a document if it occurs multiple times. Additionally, the frequencies of documents’ terms in Google n-gram corpus allows to semantically estimate their similarity. Additionally, eight variants of two clustering algorithms are applied to several real data sets in order to experimentally evalu- ate the quality of the clusters obtained with the proposed measure and compare it with other state-of-the-art measures. Computational complexity analysis of the compared measures are provided. The experimental results demonstrate that the proposed measure improves significantly the quality of document clustering, based on statistical tests. Additionally, we show that combining clustering results obtained with bag of words and semantic measure give better results than adopting a single approach. Finally, a study involving heuristcs to identify the number K of clusters in a document clustering is done. A modified version of the G-means heuristic is proposed and compared to other heuristcs from the literature.