O problema de agrupamento de dados em grafos consiste em encontrar clusters de nós em um dado grafo, ou seja, encontrar subgrafos com alta conectividade. Esse problema pode receber outras nomenclaturas, algumas delas são: problema de particionamento de grafos e problema de detecção de comunidades. Para modelar esse problema, existem diversas formulações matemáticas, cada qual com suas vantagens e desvantagens. A maioria dessas formulações tem como desvantagem a necessidade da definição prévia do número de grupos que se deseja obter. Entretanto, esse tipo de informação não está contida em dados para agrupamento, ou seja, em dados não rotulados. Esse foi um dos motivos da popularização nas últimas décadas da medida conhecida como modularidade, que tem sido maximizada para encontrar partições em grafos. Essa formulação, além de não exigir a definição prévia do número de clusters, se destaca pela qualidade das partições que ela fornece. Nesta Tese, metaheurísticas Greedy Randomized Search Procedures para dois modelos existentes para agrupamento em grafos foram propostas: uma para o problema de maximização da modularidade e a outra para o problema de maximização da similaridade intra-cluster. Os resultados obtidos por essas metaheurísticas foram melhores quando comparadas àqueles de outras heurísticas encontradas na literatura. Entretanto, o custo computacional foi alto, principalmente o da metaheurística para o modelo de maximização da modularidade. Com o passar dos anos, estudos revelaram que a formulação que maximiza a modularidade das partições possui algumas limitações. A fim de promover uma alternativa à altura do modelo de maximização da modularidade, esta Tese propõe novas formulações matemáticas de agrupamento em grafos com e sem pesos que visam encontrar partições cujos clusters apresentem alta conectividade. Além disso, as formulações propostas são capazes de prover partições sem a necessidade de definição prévia do número de clusters. Testes com centenas de grafos com pesos comprovaram a eficiência dos modelos propostos. Comparando as partições provenientes de todos os modelos estudados nesta Tese, foram observados melhores resultados em uma das novas formulações propostas, que encontrou partições bastante satisfatórias, superiores às outras existentes, até mesmo para a de maximização de modularidade. Os resultados apresentaram alta correlação com a classificação real dos dados simulados e reais, sendo esses últimos, em sua maioria, de origem biológica / Graph clustering aims at identifying highly connected groups or clusters of nodes of a graph. This problem can assume others nomenclatures, such as: graph partitioning problem and community detection problem. There are many mathematical formulations to model this problem, each one with advantages and disadvantages. Most of these formulations have the disadvantage of requiring the definition of the number of clusters in the final partition. Nevertheless, this type of information is not found in graphs for clustering, i.e., whose data are unlabeled. This is one of the reasons for the popularization in the last decades of the measure known as modularity, which is being maximized to find graph partitions. This formulation does not require the definition of the number of clusters of the partitions to be produced, and produces high quality partitions. In this Thesis, Greedy Randomized Search Procedures metaheuristics for two existing graph clustering mathematical formulations are proposed: one for the maximization of the partition modularity and the other for the maximization of the intra-cluster similarity. The results obtained by these proposed metaheuristics outperformed the results from other heuristics found in the literature. However, their computational cost was high, mainly for the metaheuristic for the maximization of modularity model. Along the years, researches revealed that the formulation that maximizes the modularity of the partitions has some limitations. In order to promote a good alternative for the maximization of the partition modularity model, this Thesis proposed new mathematical formulations for graph clustering for weighted and unweighted graphs, aiming at finding partitions with high connectivity clusters. Furthermore, the proposed formulations are able to provide partitions without a previous definition of the true number of clusters. Computational tests with hundreds of weighted graphs confirmed the efficiency of the proposed models. Comparing the partitions from all studied formulations in this Thesis, it was possible to observe that the proposed formulations presented better results, even better than the maximization of partition modularity. These results are characterized by satisfactory partitions with high correlation with the true classification for the simulated and real data (mostly biological)

Submitted by (ana.araujo@ufrpe.br) on 2016-07-05T16:55:56Z No. of bitstreams: 1 Evert Elvis Batista Almeida.pdf: 8214568 bytes, checksum: 34db767d9a38f53b7b60aaf92ca37a20 (MD5) / Made available in DSpace on 2016-07-05T16:55:56Z (GMT). No. of bitstreams: 1 Evert Elvis Batista Almeida.pdf: 8214568 bytes, checksum: 34db767d9a38f53b7b60aaf92ca37a20 (MD5) Previous issue date: 2009-02-26 / We applied a non-supervisioned data clustering technique based on a map of the problem into an inhomogeneous granular magnet problem. The physical behavior of the magnet is studied through the usual Monte Carlo method. Each data item is described by a set of numerical attributes, interpreted as points in a multiple-dimensional Euclidian space. The mapping consists in associating a Potts spin to each data point. The physical system is described by a disordered Potts Hamiltonian with several states with an exponentially decaying interaction among spins. The magnet reaches a superparamagnetic state at high temperatures in which the spins in certain grains are strongly correlated whereas the grains are loosely linked. In this way, each grain corresponds to a group or cluster. We implemented the method in a microcanonical ensemble where the conserved total energy is the control parameter. The temperature is calculated during the simulation and, besides thermodynamic stable states, it is possible to sample unstable and metastable state as well. We work with three artificial multiple-dimensional data set and a four-dimensional real data set. We obtained good results in all cases and discuss some issues concerning the microcanonical implementation of the superparamagnetic data clustering. / Aplicamos um método não supervisionado de agrupamento de dados para identificar padrões em vários conjuntos dados. A técnica baseia-se em um mapeamento do problema em um sistema magnético granular heterogêneo, cujo comportamento é investigado através de métodos Monte Carlo comumente empregado no campo da física estatística. Cada objeto é descrito por um conjunto de atributos de valores numéricos, interpretados como um ponto em um espaço euclidiano de dimensão apropriada. O mapeamento consiste em associar a cada item do conjunto, um ponto no espaço, um spin de Potts. O sistema físico é descrito por um hamiltoniano de Potts de muitos estados, no qual a interação entre os spins decai exponencialmente com a distância entre eles. Itens semelhantes, próximos, interagem fortemente enquanto que aqueles mais distantes entre si interagem apenas fracamente. O magneto atinge um estado superparamagnético para temperaturas suficientemente altas, no qual os spins de alguns grãos permanecem fortemente correlacionados, porém, os grãos estão fracamente ligados entre si. Cada grão corresponde a um grupo. Implementamos o método no ensemble microcanônico, no qual a energia total é conservada e constitui o parâmetro de controle. Nesse caso, a temperatura é calculada ao longo do processo e podemos acessar estados termodinamicamente estáveis, metaestáveis, bem como, instáveis. Trabalhamos com três conjuntos artificiais de dados, em duas e três dimensões, e um conjunto de dados reais com quatro dimensões. O desempenho do método foi satisfatório em todos os casos investigados.

Submitted by Neusa Fagundes (neusa.fagundes@unioeste.br) on 2018-06-15T20:19:22Z No. of bitstreams: 2 Fabiane_Fontana2018.pdf: 2677532 bytes, checksum: 3036328537227cc96b8ea368e893f2fc (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2018-06-15T20:19:22Z (GMT). No. of bitstreams: 2 Fabiane_Fontana2018.pdf: 2677532 bytes, checksum: 3036328537227cc96b8ea368e893f2fc (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2017-07-19 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Precision Agriculture (AP) uses technologies aimed at increasing productivity and reducing environmental impact through localized application of agricultural inputs. In order to make AP economically feasible, it is essential to improve current methodologies, as well as to propose new ones, such as the design of management areas (MZs) from productivity data, topographic, and soil attributes, among others, to determine which are heterogeneous subareas among themselves in the same area. In this context, the main objective of this research was to evaluate three distance metrics (Diagonal, Euclidian, and Mahalanobis) through FUZME and SDUM software (for the definition of management units) using the fuzzy c-means algorithm, and, at a further moment, to evaluate the cultures of soybeans and corn, as well as the association between them. On the first scientific paper, using data corresponding to four distinct areas, the three metrics with original and normalized data associated with soybean yield were evaluated. For area A, the Diagonal and Mahalanobis distances exempted the need for normalization of the variables, presenting areas that were identical for both versions. After the normalization of the data, the Euclidian distance presented a better delineation in its MZs for area A. For areas B, C, and D it was not possible to reach conclusions regarding the best performance, since only one variable was used for the process of MZs, and that has directly influenced the results. On the second scientific paper, data corresponding to three distinct areas were applied to analyze the use of soybean and corn yields, as well as the association between them, in the selection of variables to define MZs. Based on the variables available for each of the areas, the selection was carried out using the spatial correlation method, considering, for each one of the areas, the three target yields (soybean, corn, and soybean+corn). The type of productivity used demonstrated two different outcomes: first in the variable selection process, where its alternation resulted in different selections for the same area, and second, in the evaluation of the defined MZs, where even when the same variables were selected in the definition of the MZs, the performances of the MZs were different. After the validation methods applied, it was verified that the best target yield was soybean+corn, reasserting the idea of being better to use these two cultures, together, when defining the MZs of an area with rotating crops of soybean and corn. / A Agricultura de Precisão (AP) utiliza tecnologias objetivando o aumento da produtividade e redução do impacto ambiental por meio de aplicação localizada de insumos agrícolas. Para viabilizar economicamente a AP, é essencial aprimorar as metodologias atuais, bem como propor novas, como, por exemplo, o delineamento de zonas de manejo (ZMs) a partir de dados de produtividade, atributos topográficos e do solo, entre outros, utilizados a fim de determinar subáreas heterogêneas entre si em uma mesma área. Neste contexto, este trabalho teve como principal objetivo avaliar três métricas de distâncias (Diagonal, Euclidiana e Mahalanobis) junto aos Softwares FUZME e SDUM (Software para a definição de unidades de manejo), que utilizam o algoritmo fuzzy c-means, e, em um segundo momento, avaliar também as culturas de soja e milho, assim como a associação entre elas. No primeiro artigo, utilizando dados correspondentes a quatro áreas distintas, avaliaram-se as três métricas com dados originais e normalizados associados à produtividade de soja. Para a área A, as distâncias Diagonal e Mahalanobis dispensaram a necessidade de normalização das variáveis, apresentando áreas idênticas para as duas versões. Após a normalização dos dados, a distância Euclidiana apresentou um melhor delineamento em suas ZMs para a área A. Para as áreas B, C e D não foi possível obter conclusões quanto ao melhor desempenho, visto que o fato de ser utilizado apenas uma variável para o processo de definição de ZMs influenciou diretamente nos resultados obtidos. No segundo artigo, dados correspondentes a três áreas distintas foram utilizados para analisar o uso de produtividades de soja e milho, assim como a associação entre elas, na seleção de variáveis para definição de ZMs. A partir das variáveis disponíveis para cada uma das áreas foi realizada a seleção destas através do método da correlação espacial, levando em consideração, para cada uma das áreas, as três produtividades-alvo (soja, milho e soja+milho). O tipo de produtividade utilizada repercutiu de duas formas diferentes: primeiro no processo de seleção de variáveis, onde a sua alternância resultou em seleções diferenciadas para uma mesma área; e em um segundo momento, na avaliação das ZMs definidas, onde mesmo quando as mesmas variáveis foram selecionadas na definição das ZMs, os desempenhos das ZMs foram diferentes. Após os métodos de validação aplicados, verificou-se que a melhor produtividade-alvo foi soja+milho, reforçando a ideia de ser útil a utilização destas duas culturas, em conjunto, na definição das ZMs de uma área com alternância de produção de soja e milho.

Made available in DSpace on 2016-03-15T19:38:50Z (GMT). No. of bitstreams: 1 Daniel Gomes Ferrari.pdf: 2637416 bytes, checksum: 535856887beb7ff04af53570120bc1f9 (MD5) Previous issue date: 2014-03-27 / 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.

Made available in DSpace on 2014-06-12T18:03:09Z (GMT). No. of bitstreams: 2 arquivo4064_1.pdf: 3434833 bytes, checksum: 071831eaf1a52556ee4511725ac60544 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2008 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Apesar de todos os esforços das últimas décadas para desenvolver melhores estratégias de controle e vigilância, a malaria é uma das doenças infecciosas mais fatais matando mundialmente em média dois indivíduos por minuto. A malária é causada por 4 diferentes espécies do protozoário plasmódio dos quais o mais nocivo e letal é o Plasmodium falciparum. As drogas antimaláricas desenvolvidas até o momento para controlar a população do mosquito ou a proliferação do parasita e sintomas da malária mostram eficiência limitada devido `a habilidade de ambos, mosquito e parasita, desenvolverem resistência `as drogas. Para melhorar a vigilância e controle da malária é importante compreender a dinâmica de interação entre o parasita e o hospedeiro humano e porque os indivíduos infectados que vivem em áreas endêmicas não desenvolvem imunidade contra o parasita após múlltiplas exposições. Nesta tese n´os estudamos alguns aspectos do ciclo sangu´ıneo da mal´aria em hospedeiros humanos agrupando diferentes comportamentos das series temporais de parasitemia (contagem di´aria de parasitas) de pacientes com mal´aria obtidos a partir de um estudo de cohorts realizado nos EUA na d´ecada de 50. Na verdade estes pacientes eram pacientes neurosifil´ıticos que foram submetidos a malarioterapia para serem curados. Os 193 pacientes que foram tratados com diferentes drogas antimaláricas através de diferentes protocolos foram analisados separadamente dos 79 pacientes que não foram submetidos a qualquer tratamento. Neste trabalho, nós reportamos em detalhes a análise dos pacientes que foram tratados e descrevemos brevemente os resultados dos não-tratados. Como as séries temporais possuem comprimentos diferentes, para realizar nossa análise nós precisamos reduzir o espaço de parâmetros das mesmas. Para isto usamos dois conjuntos de parâmetros (9 e 14) para descrever as principais características das séries temporais destes pacientes. Usando a técnica de agrupamento não supervisionado [1] baseado em um modelo físico, nós buscamos por comportamentos similares nos dois grupos (pacientes não-tratados e tratados). A técnica de agrupamento superparamagnético (SPC) consiste no mapeamento do conjunto de pacientes (pontos no espaço de parâmetros D- dimensional), a serem agrupados de acordo com suas similaridades, no estudo da transição de primeira ordem de um modelo de Potts inomogêneo de q estados (q ≥ 10). A interação entre quaisquer dois spins de Potts depende da distância no espaço de parâmetros entre os pacientes correspondentes (objetos). Através do estudo das transições de fase deste modelo usando métodos de Monte Carlo, nós obtemos a curva de susceptibilidade magnética e localizamos as temperaturas de transição do modelo. Nós prosseguimos nossa análise identificando todos os grupos estáveis (de pacientes) que são formados na região das fases ferromagnética e superparamagnética. A separação em grupos resultante reflete as similaridades dos pacientes com respeito ao espaço de parâmetros escolhido. Desta forma, nós completamos nossa análise procurando por similaridades entre os elementos de todos os grupos obtidos, com respeito a outras informações disponíveis sobre estes pacientes: cepa do plasmódio, rota de inoculação do parasita, protocolos de drogas, etc. Os 193 pacientes tratados foram agrupados de acordo com o tipo de resposta aos diferentes protocolos e combinações de drogas. A separação também foi sensível ao número de protocolos que eles foram submetidos, bem como cepas e rotas de inoculação. Os 79 pacientes não-tratados foram agrupados de acordo com suas principais características das series temporais, embora em alguns casos a separação tenha sido sensível também `a cepa do parasita e rota de inoculação. O fato dos resultados da última análise trazerem menos informação que a análise dos pacientes tratados indica que ou o número de amostras é pequena para tal análise ou que diferentes padrôes observados são característicos do mesmo plasmódio e que não existe correlação entre os padrões das séries temporais de parasitemia e outras características extrínsecas dos pacientes disponíveis (cepa, rota de inoculação, etc.). O grande impacto do nosso trabalho vem do estudo dos pacientes tratados. O fato dos diferentes grupos agregam pacientes sujeitos a diferentes protocolos e drogas que exibem o mesmo tipo de resposta (de acordo com critérios da OMS) indica que o SPC é uma técnica não-supervisionada apropriada para ser usada neste tipo de análise. Deste modo ela pode ser muito útil para analisar séries de parasitemia coletada de outros estudos com cohorts em desenvolvimento, desenhados para se obter mais informações sobre a interação parasita-hospedeiro. Como a maioria das aplicações desta técnica de agrupamento foram focadas na análise de expressão gênica, o presente trabalho mostra também que o SPC pode ser aplicado no estudo de séries temporais

Técnicas de projeção desempenham papel importante na análise e exploração de dados multidimensionais, já que permitem visualizar informações muitas vezes ocultas na alta dimensão. Esta tese explora o potencial destas técnicas para resolver problemas relacionados à: 1) identificação de agrupamentos e 2) busca por similaridade em dados multidimensionais. Para identificação de agrupamentos foi desenvolvida uma técnica de projeção local e interativa que, além de projetar dados com ótima preservação de distâncias, permite que o usuário modifique o layout da projeção, agrupando um número reduzido de amostras representativas no espaço visual, de acordo com suas características. Os mapeamentos produzidos tendem a seguir o layout das amostras organizadas pelo usuário, facilitando a organização dos dados e identificação de agrupamentos. Contudo, nem sempre é possível selecionar ou agrupar amostras com base em suas características visuais de forma confiável, principalmente quando os dados não são rotulados. Para estas situações, um novo método para identificação de agrupamentos baseado em projeção foi proposto, o qual opera no espaço visual, garantindo que os grupos obtidos não fiquem fragmentados durante a visualização. Além disso, é orientado por um mecanismo de amostragem determinístico, apto a identificar instâncias que representam bem o conjunto de dados como um todo e capaz de operar mesmo em conjuntos de dados desbalanceados. Para o segundo problema: busca por similaridade em dados multidimensionais, uma família de métricas baseada em classes foi construída para projetar os dados, com o objetivo de minimizar a dissimilaridade entre pares de objetos pertencentes à mesma classe e, ao mesmo tempo, maximizá-la para objetos pertencentes a classes distintas. As métricas classes-específicas são avaliadas no contexto de recuperação de imagens com base em conteúdo. Com o intuito de aumentar a precisão da família de métricas classes-específicas, outra técnica foi desenvolvida, a qual emprega a teoria dos conjuntos fuzzy para estimar um valor de incerteza que é transferido para a métrica, aumentando sua precisão. Os resultados confirmam a efetividade das técnicas desenvolvidas, as quais representam significativa contribuição na tarefa de identificação de grupos e busca por similaridade em dados multidimensionais. / Projection techniques play an important role in multidimensional data analysis and exploration, since they allow to visualize information frequently hidden in high-dimensional spaces. This thesis explores the potential of those techniques to solve problems related to: 1) clustering and 2) similarity search in multidimensional data. For clustering data, a local and interactive projection technique capable of projecting data with effective preservation of distances was developed. This one allows the user to manipulate a reduced number of representative samples in the visual space so as to better organize them. The final mappings tend to follow the layout of the samples organized by the user, therefore, the user can interactively steer the projection. This makes it easy to organize and group large data sets. However, it is not always possible to select or group samples visually, in a reliable manner, mainly when handling unlabeled data. For these cases, a new clustering method based on multidimensional projection was proposed, which operates in the visual space, ensuring that clusters are not fragmented during the visualization. Moreover, it is driven by a deterministic sampling mechanism, able to identify instances that are good representatives for the whole data set. The proposed method is versatile and robust when dealing with unbalanced data sets. For the second problem: similarity search in multidimensional data, we build a family of class-specific metrics to project data. Such metrics were tailored to minimize the dissimilarity measure among objects from the same class and, simultaneously to maximize the dissimilarity among objects in distinct classes. The class-specific metrics are assessed in the context of content-based image retrieval. With the aim of increasing the precision of the class-specific metrics, another technique was developed. This one, uses the fuzzy set theory to estimate a degree of uncertainty, which is embedded in the metric, increasing its precision. The results confirm the effectiveness of the developed techniques, which represent significant contributions for clustering and similarity search in multidimensional data.

This work applies complex network theory to the problem of semi-supervised and unsupervised learning in networks that are representations of multivariate datasets. Complex networks allow the use of nonlinear dynamical systems to represent behaviors according to the connectivity patterns of networks. Inspired by behavior observed in nature, such as competition for limited resources, dynamical system models can be employed to uncover the organizational structure of a network. In this dissertation, we develop a technique for classifying data represented as interaction networks. As part of the technique, we model a dynamical system inspired by the biological dynamics of resource competition. So far, similar methods have focused on vertices as the resource of competition. We introduce edges as the resource of competition. In doing so, the connectivity pattern of a network might be used not only in the dynamical system simulation but in the learning task as well. / Este trabalho aplica a teoria de redes complexas para o estudo de uma técnica aplicada ao problema de aprendizado semissupervisionado e não-supervisionado em redes, especificamente, aquelas que representam conjuntos de dados multivariados. Redes complexas permitem o emprego de sistemas dinâmicos não-lineares que podem apresentar comportamentos de acordo com os padrões de conectividade de redes. Inspirado pelos comportamentos observados na natureza, tais como a competição por recursos limitados, sistema dinâmicos podem ser utilizados para revelar a estrutura da organização de uma rede. Nesta dissertação, desenvolve-se uma técnica aplicada ao problema de classificação de dados representados por redes de interação. Como parte da técnica, um sistema dinâmico inspirado na competição por recursos foi modelado. Métodos similares concentraram-se em vértices como o recurso da concorrência. Neste trabalho, introduziu-se arestas como o recurso-alvo da competição. Ao fazê-lo, utilizar-se-á o padrão de conectividade de uma rede tanto na simulação do sistema dinâmico, quanto na tarefa de aprendizado.

Técnicas de projeção desempenham papel importante na análise e exploração de dados multidimensionais, já que permitem visualizar informações muitas vezes ocultas na alta dimensão. Esta tese explora o potencial destas técnicas para resolver problemas relacionados à: 1) identificação de agrupamentos e 2) busca por similaridade em dados multidimensionais. Para identificação de agrupamentos foi desenvolvida uma técnica de projeção local e interativa que, além de projetar dados com ótima preservação de distâncias, permite que o usuário modifique o layout da projeção, agrupando um número reduzido de amostras representativas no espaço visual, de acordo com suas características. Os mapeamentos produzidos tendem a seguir o layout das amostras organizadas pelo usuário, facilitando a organização dos dados e identificação de agrupamentos. Contudo, nem sempre é possível selecionar ou agrupar amostras com base em suas características visuais de forma confiável, principalmente quando os dados não são rotulados. Para estas situações, um novo método para identificação de agrupamentos baseado em projeção foi proposto, o qual opera no espaço visual, garantindo que os grupos obtidos não fiquem fragmentados durante a visualização. Além disso, é orientado por um mecanismo de amostragem determinístico, apto a identificar instâncias que representam bem o conjunto de dados como um todo e capaz de operar mesmo em conjuntos de dados desbalanceados. Para o segundo problema: busca por similaridade em dados multidimensionais, uma família de métricas baseada em classes foi construída para projetar os dados, com o objetivo de minimizar a dissimilaridade entre pares de objetos pertencentes à mesma classe e, ao mesmo tempo, maximizá-la para objetos pertencentes a classes distintas. As métricas classes-específicas são avaliadas no contexto de recuperação de imagens com base em conteúdo. Com o intuito de aumentar a precisão da família de métricas classes-específicas, outra técnica foi desenvolvida, a qual emprega a teoria dos conjuntos fuzzy para estimar um valor de incerteza que é transferido para a métrica, aumentando sua precisão. Os resultados confirmam a efetividade das técnicas desenvolvidas, as quais representam significativa contribuição na tarefa de identificação de grupos e busca por similaridade em dados multidimensionais. / Projection techniques play an important role in multidimensional data analysis and exploration, since they allow to visualize information frequently hidden in high-dimensional spaces. This thesis explores the potential of those techniques to solve problems related to: 1) clustering and 2) similarity search in multidimensional data. For clustering data, a local and interactive projection technique capable of projecting data with effective preservation of distances was developed. This one allows the user to manipulate a reduced number of representative samples in the visual space so as to better organize them. The final mappings tend to follow the layout of the samples organized by the user, therefore, the user can interactively steer the projection. This makes it easy to organize and group large data sets. However, it is not always possible to select or group samples visually, in a reliable manner, mainly when handling unlabeled data. For these cases, a new clustering method based on multidimensional projection was proposed, which operates in the visual space, ensuring that clusters are not fragmented during the visualization. Moreover, it is driven by a deterministic sampling mechanism, able to identify instances that are good representatives for the whole data set. The proposed method is versatile and robust when dealing with unbalanced data sets. For the second problem: similarity search in multidimensional data, we build a family of class-specific metrics to project data. Such metrics were tailored to minimize the dissimilarity measure among objects from the same class and, simultaneously to maximize the dissimilarity among objects in distinct classes. The class-specific metrics are assessed in the context of content-based image retrieval. With the aim of increasing the precision of the class-specific metrics, another technique was developed. This one, uses the fuzzy set theory to estimate a degree of uncertainty, which is embedded in the metric, increasing its precision. The results confirm the effectiveness of the developed techniques, which represent significant contributions for clustering and similarity search in multidimensional data.

Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2017-11-22T20:38:08Z No. of bitstreams: 1 ClauberGomesBezerra_TESE.pdf: 7864722 bytes, checksum: 17c21362443f4d25511a0a211d52b805 (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2017-11-23T23:24:44Z (GMT) No. of bitstreams: 1 ClauberGomesBezerra_TESE.pdf: 7864722 bytes, checksum: 17c21362443f4d25511a0a211d52b805 (MD5) / Made available in DSpace on 2017-11-23T23:24:44Z (GMT). No. of bitstreams: 1 ClauberGomesBezerra_TESE.pdf: 7864722 bytes, checksum: 17c21362443f4d25511a0a211d52b805 (MD5) Previous issue date: 2017-05-24 / Nesta tese apresentamos uma nova abordagem para realizar o agrupamento e a classifica??o de um conjunto de dados de forma n?o supervisionada. A abordagem proposta utiliza os conceitos de tipicidade e excentricidade usados pelo algoritmo TEDA na detec??o de outliers. Para realizar o agrupamento e a classifica??o ? proposto um algoritmo estat?stico chamado Auto-Cloud. As amostras analisadas pelo Auto-Cloud s?o agrupadas em unidades chamadas de data clouds, que s?o estruturas que n?o possuem formato ou limites definidos. O Auto-Cloud permite que cada amostra analisada possa pertencer simultaneamente a v?rias data clouds. O Auto-Cloud ? um algoritmo aut?nomo e evolutivo, que n?o necessita de treinamento ou qualquer conhecimento pr?vios sobre o conjunto de dados analisado. Ele permite a cria??o e a fus?o das data clouds de forma aut?noma, ? medida que as amostras s?o lidas, sem qualquer interven??o humana. As caracter?sticas do algoritmo fazem com que ele seja indicado para o agrupamento e classifica??o de streams de dados e para aplica??es que requerem respostas em tempo-real. O Auto- Cloud tamb?m ? um algoritmo recursivo, o que o torna r?pido e exige pouca quantidade de mem?ria. J? no processo de classifica??o dos dados, o Auto-Cloud trabalha como um classificador fuzzy, calculando o grau de pertin?ncia entre a amostra analisada e cada data cloud criada no processo de agrupamento. A classe a que pertence cada amostra ? determinada pela data cloud com maior grau de pertin?ncia com rela??o a amostra. Para validar o m?todo proposto, aplicamos o mesmo em v?rios conjuntos de dados existentes na literatura sobre o assunto. Al?m disso, o m?todo tamb?m foi validado numa aplica??o de detec??o e classifica??o de falhas em processos industriais, onde foram utilizados dados reais, obtidos de uma planta industrial. / In this thesis we propose a new approach to unsupervised data clustering and classification. The proposed approach is based on typicality and eccentricity concepts. This concepts are used by recently introduced TEDA algorithm for outlier detection. To perform data clustering and classification, it is proposed a new statistical algorithm, called Auto-Cloud. The data samples analyzed by Auto-Cloud are grouped in the form of unities called data clouds, which are structures without pre-defined shape or boundaries. Auto-Cloud allows each data sample to belong to multiple data clouds simultaneously. Auto-Cloud is an autonomous and evolving algorithm, which does not requires previous training or any prior knowledge about the data set. Auto-Cloud is able to create and merge data clouds autonomously, as data samples are obtained, without any human interference. The algorithm is suitable for data clustering and classification of online data streams and application that require real-time response. Auto-Cloud is also recursive, which makes it fast and with little computational effort. The data classification process works like a fuzzy classifier using the degree of membership between the analyzed data sample to each data cloud created in clustering process. The class to which each data sample belongs is determined by the cloud with the highest activation with respect to that sample. To validate the proposed method, we apply it to several existing datasets for data clustering and classification. Moreover, the method was also used in a fault detection in industrial processes application. In this case, we use real data obtained from a real world industrial plant.

Submitted by (ana.araujo@ufrpe.br) on 2016-07-06T19:39:45Z No. of bitstreams: 1 Jose Domingos Albuquerque Aguiar.pdf: 818824 bytes, checksum: 7c15525f356ca47ab36ddd8ac61ebd31 (MD5) / Made available in DSpace on 2016-07-06T19:39:45Z (GMT). No. of bitstreams: 1 Jose Domingos Albuquerque Aguiar.pdf: 818824 bytes, checksum: 7c15525f356ca47ab36ddd8ac61ebd31 (MD5) Previous issue date: 2008-02-29 / In this work we present a new data cluster algorithm based on social behavior of ants which applies Monte Carlo simulations in selecting the maximum path length of the ants. We compare the performance of the new method with the popular k-means and another algorithm also inspired by the social ant behavior. For the comparative study we employed three data sets from the real world, three deterministic artificial data sets and two random generated data sets, yielding a total of eight data sets. We find that the new algorithm outperforms the others in all studied cases but one. We also address the issue concerning about the right number of groups in a particular data set. Our results show that the proposed algorithm yields a good estimate for the right number of groups present in the data set. / Esta dissertação apresenta um algoritmo inédito de agrupamento de dados que têm como fundamentos o método de Monte Carlo e uma heurística que se baseia no comportamento social das formigas, conhecida como Otimização por Colônias de Formigas. Neste trabalho realizou-se um estudo comparativo do novo algoritmo com outros dois algoritmos de agrupamentos de dados. O primeiro algoritmo é o KMédias que é muito conhecido entre os pesquisadores. O segundo é um algoritmo que utiliza a Otimização por Colônias de Formigas juntamente com um híbrido de outros métodos de otimização. Para implementação desse estudo comparativo utilizaram-se oito conjuntos de dados sendo três conjuntos de dados reais, dois artificiais gerados deterministicamente e três artificiais gerados aleatoriamente. Os resultados do estudo comparativo demonstram que o novo algoritmo identifica padrões nas massas de dados, com desempenho igual ou superior aos outros dois algoritmos avaliados. Neste trabalho investigou-se também a capacidade do novo algoritmo em identificar o número de grupos existentes nos conjuntos dados. Os resultados dessa investigação mostram que o novo algoritmo é capaz de identificar o de número provável de grupos existentes dentro do conjunto de dados.