A descoberta e a análise de conglomerados textuais são processos muito importantes para a estruturação, organização e a recuperação de informações, assim como para a descoberta de conhecimento. Isto porque o ser humano coleta e armazena uma quantidade muito grande de dados textuais, que necessitam ser vasculhados, estudados, conhecidos e organizados de forma a fornecerem informações que lhe dêem o conhecimento para a execução de uma tarefa que exija a tomada de uma decisão. É justamente nesse ponto que os processos de descoberta e de análise de conglomerados (clustering) se insere, pois eles auxiliam na exploração e análise dos dados, permitindo conhecer melhor seu conteúdo e inter-relações. No entanto, esse processo, por ser aplicado em textos, está sujeito a sofrer interferências decorrentes de problemas da própria linguagem e do vocabulário utilizado nos mesmos, tais como erros ortográficos, sinonímia, homonímia, variações morfológicas e similares. Esta Tese apresenta uma solução para minimizar esses problemas, que consiste na utilização de “conceitos” (estruturas capazes de representar objetos e idéias presentes nos textos) na modelagem do conteúdo dos documentos. Para tanto, são apresentados os conceitos e as áreas relacionadas com o tema, os trabalhos correlatos (revisão bibliográfica), a metodologia proposta e alguns experimentos que permitem desenvolver determinados argumentos e comprovar algumas hipóteses sobre a proposta. As conclusões principais desta Tese indicam que a técnica de conceitos possui diversas vantagens, dentre elas a utilização de uma quantidade muito menor, porém mais representativa, de descritores para os documentos, o que torna o tempo e a complexidade do seu processamento muito menor, permitindo que uma quantidade muito maior deles seja analisada. Outra vantagem está no fato de o poder de expressão de conceitos permitir que os usuários analisem os aglomerados resultantes muito mais facilmente e compreendam melhor seu conteúdo e forma. Além do método e da metodologia proposta, esta Tese possui diversas contribuições, entre elas vários trabalhos e artigos desenvolvidos em parceria com outros pesquisadores e colegas.

Submitted by Automação e Estatística (sst@bczm.ufrn.br) on 2018-07-03T15:32:36Z No. of bitstreams: 1 ThaisDeAlmeidaRatisRamos_DISSERT.pdf: 5907109 bytes, checksum: 89a190289f7aa32aedb29f2dff662907 (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2018-07-11T13:58:20Z (GMT) No. of bitstreams: 1 ThaisDeAlmeidaRatisRamos_DISSERT.pdf: 5907109 bytes, checksum: 89a190289f7aa32aedb29f2dff662907 (MD5) / Made available in DSpace on 2018-07-11T13:58:20Z (GMT). No. of bitstreams: 1 ThaisDeAlmeidaRatisRamos_DISSERT.pdf: 5907109 bytes, checksum: 89a190289f7aa32aedb29f2dff662907 (MD5) Previous issue date: 2018-05-11 / A criação de enciclopédias de expressão gênica possibilita a compreensão de grupos de genes que são co-expressos em diferentes tecidos e o entendimento de grupos gênicos conforme suas funções e origem. Devido à enorme quantidade de dados em larga escala, gerados em projetos de transcriptômica, houve uma demanda intensa em usar técnicas fornecidas pela inteligência artificial, que tornou-se amplamente utilizada na bioinformática. A aprendizagem não supervisionada é a tarefa de aprendizagem de máquina que analisa os dados fornecidos e determina os objetos que podem ser agrupados. Foi construída uma ferramenta amigável chamada CORAZON (Correlation Analyses Zipper Online), que implementa 3 algoritmos de aprendizagem de máquina não supervisionada (mean shift, k-means e hierárquico), 6 metodologias de normalização (Fragments Per Kilobase Million (FPKM), Transcripts Per Million (TPM), Counts Per Million (CPM), log base-2, normalização pela soma dos valores da instância e normalização pelo maior valor de atributo para cada instância) e uma estratégia para observar a influência dos atributos, para agrupamento de dados de expressão gênica. Os desempenhos dos algoritmos foram avaliados através de 5 modelos comumente usados para validar metodologias de agrupamento, cada um composto por 50 conjuntos de dados gerados aleatoriamente. Os algoritmos apresentaram acurácia variando entre 92-100%. Em seguida, a ferramenta foi aplicada para agrupar tecidos, obter conhecimentos evolutivos e funcionais dos genes, com base no enriquecimento de processos biológicos, e associar com fatores de transcrição. Para selecionar o melhor número de clusters para o k-means e o hierárquico, foram utilizados o critério de informação bayesiana (BIC), seguido da derivada da função discreta e a Silhueta. No hierárquico foi adotado o método do Ward. No total, 3 bases de dados (Uhlen, Encode e Fantom) foram analisadas e, em relação aos tecidos, foram observados grupos relacionados a glândulas, tecidos cardíacos, musculares, relacionados ao sistema reprodutivo e grupos com um único tecido, como testículo, cérebro e medula óssea. Em relação aos grupos de genes, foram obtidos vários grupos com especificidades em suas funções: detecção de estímulos envolvidos na percepção sensorial, reprodução, sinalização sináptica, sistema nervoso, sistema imunológico, desenvolvimento de sistemas e metabólicos. Também foi observado que geralmente grupos com mais de 80% de genes não codificantes, mais de 40% dos seus genes codificantes são recentes, originados em Mammalia e a minoria é do clado Eukaryota. Por outro lado, grupos com mais de 90% de genes codificantes, mais de 40% deles apareceram em Eukaryota e a minoria em Mammalia. Estes resultados mostram o potencial dos métodos do CORAZON, que podem ajudar na análise de grande quantidade de dados genômicos, possibilitando associações dos processos biológicos com RNAs não codificantes e codificantes agrupados juntos, bem como a possibilidade do estudo da história evolutiva. CORAZON está disponível gratuitamente em http://biodados.icb.ufmg.br/corazon ou http://corazon.integrativebioinformatics.me. / The creation of gene expression encyclopedias possibilities the understanding of gene groups that are co-expressed in different tissues and comprehend gene clusters according to their functions and origin. Due to the huge amount of data generated in large-scale transcriptomics projects, an intense demand to use techniques provided by artificial intelligence became widely used in bioinformatics. Unsupervised learning is the machine learning task that analyzes the data provided and tries to determine if some objects can be grouped in some way, forming clusters. We developed an online tool called CORAZON (Correlation Analyses Zipper Online), which implements three unsupervised machine learning algorithms (mean shift, k-means and hierarchical) to cluster gene expression datasets, six normalization methodologies (Fragments Per Kilobase Million (FPKM), Transcripts Per Million (TPM), Counts per million (CPM), base-2 log, normalization by the sum of the instance's values and normalization by the highest attribute value for each instance), and a strategy to observe the attributes influence, all in a friendly environment. The algorithms performances were evaluated through five models commonly used to validate clustering methodologies, each one composed by fifty randomly generated datasets. The algorithms presented accuracies ranging between 92-100%. Next, we applied our tool to cluster tissues, obtain gene’s evolutionarily knowledgement and functional insights, based on the Gene Ontology enrichment, and connect with transcription factors. To select the best number of clusters for k-means and hierarchical algorithms we used Bayesian information criterion (BIC), followed by the derivative of the discrete function and Silhouette. In the hierarchical, we adopted the Ward’s method. In total, we analyzed three databases (Uhlen, Encode and Fantom) and in relation to tissues we can observe groups related to glands, cardiac tissues, muscular tissues, tissues related to the reproductive system and in all three groups are observed with a single tissue, such as testis, brain and bone-narrow. In relation to the genes clusters, we obtained several clusters that have specificities in their functions: detection of stimulus involved in sensory perception, reproduction, synaptic signaling, nervous system, immunological system, system development, and metabolics. We also observed that clusters with more than 80% of noncodings, more than 40% of their coding genes are recents appearing in mammalian class and the minority are from eukaryota class. Otherwise, clusters with more than 90% of coding genes, have more than 40% of them appeared in eukaryota and the minority from mammalian. These results illustrate the potential of the methods in CORAZON tool, which can help in the large quantities analysis of genomic data, possibiliting the potential associations analyzes between non-coding RNAs and the biological processes of clustered together coding genes, as well as the possibility of evolutionary history study. CORAZON is freely available at http://biodados.icb.ufmg.br/corazon or http://corazon.integrativebioinformatics.me.

Submitted by Sophia Mangussi Franchi Dutra null (sophiamfd@gmail.com) on 2018-04-06T17:25:56Z No. of bitstreams: 1 Tese versão final Sophia.pdf: 1221972 bytes, checksum: 4c5069079ed78d11bd09f984fc16f5ac (MD5) / Approved for entry into archive by Alexandra Maria Donadon Lusser Segali null (alexmar@fcav.unesp.br) on 2018-04-09T17:54:15Z (GMT) No. of bitstreams: 1 dutra_smf_dr_jabo.pdf: 1221972 bytes, checksum: 4c5069079ed78d11bd09f984fc16f5ac (MD5) / Made available in DSpace on 2018-04-09T17:54:15Z (GMT). No. of bitstreams: 1 dutra_smf_dr_jabo.pdf: 1221972 bytes, checksum: 4c5069079ed78d11bd09f984fc16f5ac (MD5) Previous issue date: 2018-03-22 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Os objetivos principais com a pesquisa foram: alocar genótipos de milho em grupos divergentes pela abordagem multivariada e correlacionar caracteres agronômicos com caracteres relacionados à qualidade de sementes de milho. Para alocação em grupos heteróticos, foram utilizados dois métodos multivariados, método K-means e método Tocher. A partir da avaliação de caracteres agronômicos (altura de planta, posição relativa da espiga, acamamento, quebramento, prolificidade e produtividade de grãos), foram alocadas 229 linhagens parcialmente endogâmicas (S3), avaliadas em três safras. Já para correlação entre caracteres foram utilizados os métodos Redes Bayesiana e correlação linear simples de Pearson. Os caracteres avaliados, de 31 genótipos de milho, foram caracteres agronômicos (altura de planta, posição relativa da espiga, acamamento, quebramento, prolificidade e produtividade de grãos), avaliados em três safras, e caracteres de sementes (primeira contagem de germinação, germinação final, primeira contagem de emergência, emergência final e índice de velocidade de germinação). As análises estatísticas foram realizadas utilizando-se o programa computacional SAS, Selegen e RStudio. Na análise de variância conjunta foi constatado efeito significativo para safra em todas caracteres analisadas, caracterizando a influência das safras e indicando diferença entre os ambientes de avaliação. Foi possível alocar os genótipos de milho em grupos heteróticos a partir dos métodos de agrupamento. A correlação linear de Pearson variou de -0,511 (entre quebramento e produtividade) a 0,987 (entre primeira contagem de emergência e emergência final). A partir do Directed Acyclic Graph é possível observar a correlação entre caracteres agronômicos e caracteres relacionados à qualidade de sementes de milho. Assim, os genótipos de milho foram alocados quanto à divergência a partir das análises multivariadas de agrupamento K-médias e Tocher. Foi possível identificar sete grupos divergêntes pelo método Kmédias e 21 pelo método Tocher. E também, observa-se pouca correlação existente entre os caracteres agronômicos e os caracteres relacionados à qualidade de sementes de milho. / The main objectives of the research were: to allocate corn genotypes in divergent groups by the multivariate approach and to correlate agronomic traits with traits related to maize seed quality. For allocation in heterotic groups, two multivariate methods, K-means method and Tocher method were used. Based on the evaluation of agronomic characters (plant height, relative position of the spike, lodging, breaking, prolificacy and grain yield), 229 partially inbred lines (S3) were evaluated, evaluated in three harvests. Already for the correlation between characters were used the methods Bayesian Networks and simple linear correlation of Pearson. The evaluated traits of 31 corn genotypes were agronomic characteristics (plant height, relative position of the spike, lodging, breaking, prolificacy and grain yield) evaluated in three harvests, and seed characteristics (first germination count, germination endpoint, first emergency count, final emergency and germination speed index). Statistical analyzes were performed using the SAS software, Selegen and RStudio. In the analysis of joint variance it was verified a significant effect for harvest in all characters analyzed, characterizing the influence of the crops and indicating difference between the evaluation environments. It was possible to allocate the maize genotypes to heterotic groups from the clustering methods. Pearson's linear correlation ranged from -0.511 (between breakage and productivity) to 0.987 (between first emergency count and final emergency). From the Directed Acyclic Graph it is possible to observe the correlation between agronomic characters and characters related to the quality of maize seeds. Thus, maize genotypes were allocated for divergence from the multivariate K-medium and Tocher cluster analyzes. It was possible to identify seven divergent groups by the K-means method and 21 by the Tocher method. Also, there is little correlation between agronomic characters and traits related to maize seed quality.

Submitted by Thiago Alexandre Domingues de Souza null (thi.alex@gmail.com) on 2017-06-13T21:07:36Z No. of bitstreams: 1 dissertacao_thiago_final.pdf: 4785471 bytes, checksum: 3e37f93660d9b1fa3f368341de0bfdcd (MD5) / Rejected by Luiz Galeffi (luizgaleffi@gmail.com), reason: Solicitamos que realize uma nova submissão seguindo a orientação abaixo: A ficha catalográfica deve ser inserida na página subsequente à folha de rosto. Corrija esta informação e realize uma nova submissão com o arquivo correto. Agradecemos a compreensão. on 2017-06-19T13:20:07Z (GMT) / Submitted by Thiago Alexandre Domingues de Souza null (thi.alex@gmail.com) on 2017-06-19T14:07:52Z No. of bitstreams: 1 dissertacao_thiago_final.pdf: 4785471 bytes, checksum: 3e37f93660d9b1fa3f368341de0bfdcd (MD5) / Approved for entry into archive by Luiz Galeffi (luizgaleffi@gmail.com) on 2017-06-19T14:17:58Z (GMT) No. of bitstreams: 1 souza_tad_me_sjrp.pdf: 4785471 bytes, checksum: 3e37f93660d9b1fa3f368341de0bfdcd (MD5) / Made available in DSpace on 2017-06-19T14:17:58Z (GMT). No. of bitstreams: 1 souza_tad_me_sjrp.pdf: 4785471 bytes, checksum: 3e37f93660d9b1fa3f368341de0bfdcd (MD5) Previous issue date: 2017-05-12 / A indústria de tecnologia da informação tem permitido uma explosão de dados coletados nos últimos anos. Isso ocorreu, entre outros fatores, pela expansão do acesso à rede por meio de uma infinidade de equipamentos. Uma análise detalhada dos dados armazenados pode, por exemplo, extrair informações valiosas sobre o comportamento dos indivíduos, permitindo uma relação personalizada de acordo com os interesses dos usuários. Essa tarefa pode ser feita usando algoritmos de agrupamento de dados. Porém, esse é um processo que requer grande esforço computacional tanto pela ordem de complexidade dos algoritmos existentes como pelos crescentes volumes processados. Nesse contexto, execuções sequenciais não são viáveis e sua paralelização é o caminho natural. Isso exige remodelar algoritmos para explorar o potencial de plataformas massivamente paralelas, de acordo com as particularidades da arquitetura alvo. Neste trabalho se propõe uma implementação paralela do algoritmo Fuzzy Minimals para GPU, como uma solução de alto desempenho e baixo custo para contornar dificuldades frequentes no agrupamento de dados. Com o objetivo de avaliar o desempenho de nossa solução, também desenvolvemos versões paralelas em MPI e OpenMP. Nossos experimentos mostram que a solução para GPU alcança resultados expressivos com um baixo custo, mantendo uma precisão significativa. / IT industry has witnessed an explosion of data collected for the past few years. This took place, among other factors, due to the expansion of network access through several devices. For example, a detailed analysis of the stored data can extract some valuable information about human behaviors, allowing a customized experience that matches the interests of users . This task can be performed by clustering algorithms. However, this is a time-consuming process due to the asymptotic complexity of existing algorithms and the increasing volumes of data processed. In this context, sequential executions are not feasible and their parallelization is the natural path. This requires redesigning algorithms to take advantage of massively parallel platforms according to the particularities of targeted architectures. In this paper, it is proposed a novel parallel implementation of the Fuzzy Minimals algorithm on GPU, as a high-performance lowcost solution for common clustering issues. In order to evaluate the performance of our implementation, we have also designed parallel versions using MPI and OpenMP. Our experiments show that our parallel solution on GPU can achieve a high performance at a low cost, preserving a significant accuracy.

Orientador: Fernando Frei / Banca: Jaime de Oliveira Gomes / Banca: Sérgio Nascimento Stampar / Resumo: Os aracnídeos conseguiram sucesso ao longo do processo evolutivo graças à alta capacidade de adaptação. Dentro deste grupo, as aranhas e escorpiões apresentam ampla distribuição no planeta, e podem trazer problemas de saúde aos seres humanos. Para avaliar os problemas de infestação provocados por estes animais é necessário o uso de ferramentas estatísticas que possam aferir quais são os fatores que favorecem ou perpetuam a aparição, presença e proliferação destes animais. Desta forma, este trabalho tem como objetivo apresentar a Análise de Agrupamentos para determinar padrões de infestação, fazendo com que locais aparentemente distintos possam ser reunidos em grupos semelhantes o que pode trazer benefícios para políticas de saúde. Os 25 pontos geográficos de coleta utilizados na amostragem foram reunidos em seis grupos com características distintas, dentre os quais, três foram formados por um único ponto de coleta (outliers). Os grupos obtidos apresentaram relação entre os pontos que os formam e as características ambientais dos locais, demonstrando que a distribuição das famílias de aracnídeos nos diferentes gradientes urbanos é influenciada pelas condições do ambiente. Assim, a ocupação dos espaços urbanizados por aracnídeos peçonhentos torna-se um problema para a saúde pública, necessitando de políticas de controle epidemiológico através de monitoramento e mapeamento das áreas de risco que podem ser melhor avaliadas com o uso da Análise de Agrupamentos. Palavras chave: Aranha, Escorpião, Epidemiologia, Análise de Agrupamentos / Abstract: Arachnids have been successful along the evolutionary process thanks to their high adaptability. Within this group, spiders and scorpions are widely distributed on the planet and may affect human health. In order to evaluate the infestation problems caused by these animals, it is necessary to use statistical tools that can assess the factors that favor or perpetuate their appearance, presence and proliferation. Thus, this work aims to present cluster analysis in order to determine infestation patterns, allowing seemingly distinct sites to be grouped into similar clusters, which can benefit health policies. The 25 geographic collection sites used for sampling were divided into six groups with different characteristics, among which three were formed by a single collection point (outliers). The groups obtained showed a relationship with the environmental characteristics of the sites, indicating that the distribution of arachnid families in the different urban gradients is influenced by environmental conditions. Therefore, the occupation of urbanized areas by venomous arachnids becomes a problem for public health, requiring epidemiological control policies through monitoring and mapping of risk areas, which can be better assessed with the use of cluster analysis / Mestre

Esta Tese apresenta um framework para análise exploratória de dados via técnicas de agrupamento. O objetivo é facilitar o trabalho dos especialistas no domínio dos dados. O ponto central do framework é um algoritmo de ensemble multi-objetivo, o algoritmo MOCLE, complementado por um método para a visualização integrada de um conjunto de partições. Pela aplicação conjunta das idéias de ensemble de agrupamentos e agrupamento multi-objetivo, o MOCLE efetua atomaticamente importantes passos da análise de agrupamento: executa vários algoritmos conceitualmente diferentes com várias configurações de parâmetros, combina as partições resultantes desses algoritmos e seleciona as partições com os melhores compromissos de diferentes medidas de validação. MOCLE é uma abordagem robusta para lidar com diferentes tipos de estrutura que podem estar presentes em um conjunto de dados. Ele resulta em um conjunto conciso e estável de estruturas alternativas de alta qualidade, sem a necessidade de conhecimento prévio sobre os dados e nem conhecimento profundo em análise de agrupamento. Além disso, para facilitar a descoberta de estruturas mais complexas, o MOCLE permite a integração automática de conhecimento prévio de uma estrutura simples por meio das suas funções objetivo. Finalmente, o método de visualização proposto permite a observação simultânea de um conjunto de partições. Isso ajuda na análise dos resultados do MOCLE. / This Thesis presents a framework for exploratory data analysis via clustering techniques. The goal is to facilitate the work of the experts in the data domain. The core of the framework is a multi-objective clustering ensemble algorithm, the MOCLE algorithm, complemented by a method for integrated visualization of a set of partitions. By applying together the ideas of clustering ensemble and multi-objective clustering, MOCLE automatically performs important steps of cluster analysis: run several conceptually different clustering algorithms with various parameter configuration, combine the partitions resulting from these algorithms, and select the partitions with the best trade-offs for different validation measures. MOCLE is a robust approach to deal with different types of structures that can be present in a dataset. It results in a concise and stable set of high quality alternative structures, without the need of previous knowledge about the data or deep knowledge on cluster analysis. Furthermore, in order to facilitate the discovery of more complex structures, MOCLE allows the automatic integration of previous knowledge of a simple structure via their objective functions. Finally, the visualization method proposed allows the simultaneous observation of a set of partitions. This helps in the analysis of MOCLE results.

O agrupamento de dados (ou do inglês Clustering) é uma tarefa não supervisionada capaz de descrever objetos em grupos (ou clusters), de maneira que objetos de um mesmo grupo sejam mais semelhantes entre si do que objetos de grupos distintos. As técnicas de agrupamento de dados são divididas em duas principais categorias: particionais e hierárquicas. As técnicas particionais dividem um conjunto de dados em um determinado número de grupos distintos, enquanto as técnicas hierárquicas fornecem uma sequência aninhada de agrupamentos particionais separados por diferentes níveis de granularidade. Adicionalmente, o agrupamento hierárquico de dados baseado em densidade é um paradigma particular de agrupamento que detecta grupos com diferentes concentrações ou densidades de objetos. Uma das técnicas mais populares desse paradigma é conhecida como HDBSCAN*. Além de prover hierarquias, HDBSCAN* é um framework que fornece detecção de outliers, agrupamento semi-supervisionado de dados e visualização dos resultados. No entanto, a maioria das técnicas hierárquicas, incluindo o HDBSCAN*, possui uma alta complexidade computacional. Fato que as tornam proibitivas para a análise de grandes conjuntos de dados. No presente trabalho de mestrado, foram propostas duas variações aproximadas de HDBSCAN* computacionalmente mais escaláveis para o agrupamento de grandes quantidades de dados. A primeira variação de HDBSCAN* segue o conceito de computação paralela e distribuída, conhecido como MapReduce. Já a segunda, segue o contexto de computação paralela utilizando memória compartilhada. Ambas as variações são baseadas em um conceito de divisão eficiente de dados, conhecido como Recursive Sampling, que permite o processamento paralelo desses dados. De maneira similar ao HDBSCAN*, as variações propostas também são capazes de fornecer uma completa análise não supervisionada de padrões em dados, incluindo a detecção de outliers. Experimentos foram realizados para avaliar a qualidade das variações propostas neste trabalho, especificamente, a variação baseada em MapReduce foi comparada com uma versão paralela e exata de HDBSCAN* conhecida como Random Blocks. Já a versão paralela em ambiente de memória compartilhada foi comparada com o estado da arte (HDBSCAN*). Em termos de qualidade de agrupamento e detecção de outliers, tanto a variação baseada em MapReduce quanto a baseada em memória compartilhada mostraram resultados próximos à versão paralela exata de HDBSCAN* e ao estado da arte, respectivamente. Já em termos de tempo computacional, as variações propostas mostraram maior escalabilidade e rapidez para o processamento de grandes quantidades de dados do que as versões comparadas. / Clustering is an unsupervised learning task able to describe a set of objects in clusters, so that objects of a same cluster are more similar than objects of other clusters. Clustering techniques are divided in two main categories: partitional and hierarchical. The particional techniques divide a dataset into a number of distinct clusters, while hierarchical techniques provide a nested sequence of partitional clusters separated by different levels of granularity. Furthermore, hierarchical density-based clustering is a particular clustering paradigm that detects clusters with different concentrations or densities of objects. One of the most popular techniques of this paradigm is known as HDBSCAN*. In addition to providing hierarchies, HDBSCAN* is a framework that provides outliers detection, semi-supervised clustering and visualization of results. However, most hierarchical techniques, including HDBSCAN*, have a high complexity computational. This fact makes them prohibitive for the analysis of large datasets. In this work have been proposed two approximate variations of HDBSCAN* computationally more scalable for clustering large amounts of data. The first variation follows the concept of parallel and distributed computing, known as MapReduce. The second one follows the context of parallel computing using shared memory. Both variations are based on a concept of efficient data division, known as Recursive Sampling, which allows parallel processing of this data. In a manner similar to HDBSCAN*, the proposed variations are also capable of providing complete unsupervised patterns analysis in data, including outliers detection. Experiments have been carried out to evaluate the quality of the variations proposed in this work, specifically, the variation based on MapReduce have been compared to a parallel and exact version of HDBSCAN*, known as Random Blocks. Already the version parallel in shared memory environment have been compared to the state of the art (HDBSCAN*). In terms of clustering quality and outliers detection, the variation based on MapReduce and other based on shared memory showed results close to the exact parallel verson of HDBSCAN* and the state of the art, respectively. In terms of computational time, the proposed variations showed greater scalability and speed for processing large amounts of data than the compared versions.

A análise de agrupamento de dados é uma tarefa fundamental em mineração de dados e aprendizagem de máquina. Ela tem por objetivo encontrar um conjunto finito de categorias que evidencie as relações entre os objetos (registros, instâncias, observações, exemplos) de um conjunto de dados de interesse. Os algoritmos de agrupamento podem ser divididos em particionais e hierárquicos. Uma das vantagens dos algoritmos hierárquicos é conseguir representar agrupamentos em diferentes níveis de granularidade e ainda serem capazes de produzir partições planas como aquelas produzidas pelos algoritmos particionais, mas para isso é necessário que seja realizado um corte (por exemplo horizontal) sobre o dendrograma ou hierarquia dos grupos. A escolha de como realizar esse corte é um problema clássico que vem sendo investigado há décadas. Mais recentemente, este problema tem ganho especial importância no contexto de algoritmos hierárquicos baseados em densidade, pois somente estratégias mais sofisticadas de corte, em particular cortes não-horizontais denominados cortes locais (ao invés de globais) conseguem selecionar grupos de densidades diferentes para compor a solução final. Entre as principais vantagens dos algoritmos baseados em densidade está sua robustez à interferência de dados anômalos, que são detectados e deixados de fora da partição final, rotulados como ruído, além da capacidade de detectar clusters de formas arbitrárias. O objetivo deste trabalho foi adaptar uma variante da medida da Modularidade, utilizada amplamente na área de detecção de comunidades em redes complexas, para que esta possa ser aplicada ao problema de corte local de hierarquias de agrupamento. Os resultados obtidos mostraram que essa adaptação da modularidade pode ser uma alternativa competitiva para a medida de estabilidade utilizada originalmente pelo algoritmo estado-da-arte em agrupamento de dados baseado em densidade, HDBSCAN*. / Cluster Analysis is a fundamental task in Data Mining and Machine Learning. It aims to find a finite set of categories that evidences the relationships between the objects (records, instances, observations, examples) of a data set of interest. Clustering algorithms can be divided into partitional and hierarchical. One of the advantages of hierarchical algorithms is to be able to represent clusters at different levels of granularity while being able to produce flat partitions like those produced by partitional algorithms. To achieve this, it is necessary to perform a cut (for example horizontal) through the dendrogram or cluster tree. How to perform this cut is a classic problem that has been investigated for decades. More recently, this problem has gained special importance in the context of density-based hierarchical algorithms, since only more sophisticated cutting strategies, in particular nonhorizontal cuts (instead of global ones) are able to select clusters with different densities to compose the final solution. Among the main advantages of density-based algorithms is their robustness to noise and their capability to detect clusters of arbitrary shape. The objective of this work was to adapt a variant of the Q Modularity measure, widely used in the realm of community detection in complex networks, so that it can be applied to the problem of local cuts through cluster hierarchies. The results show that the proposed measure can be a competitive alternative to the stability measure, originally used by the state-of-the-art density-based clustering algorithm HDBSCAN*.

A descoberta e a análise de conglomerados textuais são processos muito importantes para a estruturação, organização e a recuperação de informações, assim como para a descoberta de conhecimento. Isto porque o ser humano coleta e armazena uma quantidade muito grande de dados textuais, que necessitam ser vasculhados, estudados, conhecidos e organizados de forma a fornecerem informações que lhe dêem o conhecimento para a execução de uma tarefa que exija a tomada de uma decisão. É justamente nesse ponto que os processos de descoberta e de análise de conglomerados (clustering) se insere, pois eles auxiliam na exploração e análise dos dados, permitindo conhecer melhor seu conteúdo e inter-relações. No entanto, esse processo, por ser aplicado em textos, está sujeito a sofrer interferências decorrentes de problemas da própria linguagem e do vocabulário utilizado nos mesmos, tais como erros ortográficos, sinonímia, homonímia, variações morfológicas e similares. Esta Tese apresenta uma solução para minimizar esses problemas, que consiste na utilização de “conceitos” (estruturas capazes de representar objetos e idéias presentes nos textos) na modelagem do conteúdo dos documentos. Para tanto, são apresentados os conceitos e as áreas relacionadas com o tema, os trabalhos correlatos (revisão bibliográfica), a metodologia proposta e alguns experimentos que permitem desenvolver determinados argumentos e comprovar algumas hipóteses sobre a proposta. As conclusões principais desta Tese indicam que a técnica de conceitos possui diversas vantagens, dentre elas a utilização de uma quantidade muito menor, porém mais representativa, de descritores para os documentos, o que torna o tempo e a complexidade do seu processamento muito menor, permitindo que uma quantidade muito maior deles seja analisada. Outra vantagem está no fato de o poder de expressão de conceitos permitir que os usuários analisem os aglomerados resultantes muito mais facilmente e compreendam melhor seu conteúdo e forma. Além do método e da metodologia proposta, esta Tese possui diversas contribuições, entre elas vários trabalhos e artigos desenvolvidos em parceria com outros pesquisadores e colegas.

Submitted by Isaac Francisco de Souza Dias (isaac.souzadias@ufpe.br) on 2016-01-19T18:57:09Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) TESE_LUCIANA_FRANÇA_2015.pdf: 24518868 bytes, checksum: 4269eb570ad8b8aee5ee4554090855b3 (MD5) / Made available in DSpace on 2016-01-19T18:57:09Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) TESE_LUCIANA_FRANÇA_2015.pdf: 24518868 bytes, checksum: 4269eb570ad8b8aee5ee4554090855b3 (MD5) Previous issue date: 2015-06-05 / CAPES / O município de Lagoa dos Gatos, pertencente ao Estado de Pernambuco, localiza-se na mesorregião do Agreste e se insere na microrregião do Brejo Pernambucano, a 180 km da cidade do Recife. Este município é contemplado com um rico cenário, tanto da geodiversidade quanto da biodiversidade, constituído principalmente por cachoeiras, geoformas graníticas, serras, extensos lajedos e reserva de mata atlântica. Geologicamente o município está inserido na Província Borborema, sendo constituído pelos litotipos dos complexos Cabrobó e Belém do São Francisco e da Suíte Calcialcalina de Médio a Alto Potássio Itaporanga. Foi realizado um inventário dos geossítios considerando o inventário temático e sistemático proposto por Sharples a partir da abordagem de classificação baseado no contexto geológico-geomorfológico da região. A quantificação dos geossítios foi feita utilizando-se o método de Brilha, determinando-se os valores: (A) intrínseco, (B) de uso potencial e (C) de necessidade de proteção. Após a quantificação, os geossítios foram divididos em grupos, de acordo com a sua semelhança, a partir da aplicação da técnica de Análise de Agrupamentos. Os resultados obtidos não invalidam a quantificação tradicional, onde é determinado um índice de quantificação denominado Q, que corresponde à média aritmética dos valores dos geossítios de caráter regional ou local, aplicando-se aos valores dos geossítios. Os valores A, B e C são avaliados distintamente, e as relações desses três elementos criam uma resposta em forma de grupos que representam as diversas modalidades da geodiversidade de uma determinada área. A aplicação da técnica de Análise de Agrupamentos permitiu a formação de 5 grupos a partir dos catorzes geossítios inventariados. De acordo com as características dos grupos, foi possível definir prioridades, através de um plano de ação, no qual foram pontuadas estratégias de divulgação, de uso e de preservação, visto que geralmente há limitação de recursos a serem investidos. / The municipality of Lagoa dos Gatos, in the State of Pernambuco, located in the middle region of Agreste and inserts on the microregion Pernambucano Brejo. This municipality is covered with a rich scenario, both geodiversity as biodiversity, mainly of waterfalls, granite landforms, mountain ranges, large flagstones and Mata Atlântica reserve. Geologically the municipality is inserted in the Borborema Province, being composed of rock types of Cabrobó complex and Belém de São Francisco and suite Calcialcalina Medium to High Potassium Itaporanga. An inventory was conducted of geosites considering the thematic and systematic inventory proposed by Sharples from the classification approach based on the geological and geomorphological context of the region. The quantification of geosite was made using the method Brilha, determining the values: (A) intrinsic (B) potential use and (C) need protection. After quantification, the geosites were divided into groups according to their similarity, from the application of the cluster analysis technique. After quantification, the geosites were divided into groups according to their similarity, from the application of the Cluster Analysis technique. The results do not invalidate the traditional quantification, which is given a quantification index known as Q, which is the arithmetic average of the national or local character geosites, applying the values of geosites. The values A, B and C are assessed distinctly, and the relationships of these three elements create a response in the form of groups representing the different types of geodiversity of a given area. The application of the cluster analysis technique allowed the formation of 5 groups from catorzes potential geosites inventoried. According to the characteristics of the groups, it was possible to set priorities, through a plan of action, which were scored dissemination strategies, usage and preservation, since there is usually limited resources to be invested.