Uma nova forma de calcular os centros dos Clusters em algoritmos de agrupamento tipo fuzzy c-means

Clustering data is a very important task in data mining, image processing and pattern recognition problems. One of the most popular clustering algorithms is the Fuzzy C-Means (FCM). This thesis proposes to implement a new way of calculating the cluster centers in the procedure of FCM algorithm which are called ckMeans, and in some variants of FCM, in particular, here we apply it for those variants that use other distances. The goal of this change is to reduce the number of iterations and processing time of these algorithms without affecting the quality of the partition, or even to improve the number of correct classifications in some cases. Also, we developed an algorithm based on ckMeans to manipulate interval data considering interval membership degrees. This algorithm allows the representation of data without converting interval data into punctual ones, as it happens to other extensions of FCM that deal with interval data. In order to validate the proposed methodologies it was made a comparison between a clustering for ckMeans, K-Means and FCM algorithms (since the algorithm proposed in this paper to calculate the centers is similar to the K-Means) considering three different distances. We used several known databases. In this case, the results of Interval ckMeans were compared with the results of other clustering algorithms when applied to an interval database with minimum and maximum temperature of the month for a given year, referring to 37 cities distributed across continents

Algoritmos de agrupamento aplicados a dados de expressão gênica de câncer: um estudo comparativo

The use of clustering methods for the discovery of cancer subtypes has drawn a great deal of attention in the scientific community. While bioinformaticians have proposed new clustering methods that take advantage of characteristics of the gene expression data, the medical community has a preference for using classic clustering methods. There have been no studies thus far performing a large-scale evaluation of different clustering methods in this context. This work presents the first large-scale analysis of seven different clustering methods and four proximity measures for the analysis of 35 cancer gene expression data sets. Results reveal that the finite mixture of Gaussians, followed closely by k-means, exhibited the best performance in terms of recovering the true structure of the data sets. These methods also exhibited, on average, the smallest difference between the actual number of classes in the data sets and the best number of clusters as indicated by our validation criteria. Furthermore, hierarchical methods, which have been widely used by the medical community, exhibited a poorer recovery performance than that of the other methods evaluated. Moreover, as a stable basis for the assessment and comparison of different clustering methods for cancer gene expression data, this study provides a common group of data sets (benchmark data sets) to be shared among researchers and used for comparisons with new methods

Hardware reconfigurável para identificação de radionuclídeos utilizando o método de agrupamento subtrativo.

Fontes radioativas possuem radionuclídeos. Um radionuclídeo é um átomo com um núcleo instável, ou seja, um núcleo caracterizado pelo excesso de energia que está disponível para ser emitida. Neste processo, o radionuclídeo sofre o decaimento radioativo e emite raios gama e partículas subatômicas, constituindo-se na radiação ionizante. Então, a radioatividade é a emissão espontânea de energia a partir de átomos instáveis. A identificação correta de radionuclídeos pode ser crucial para o planejamento de medidas de proteção, especialmente em situações de emergência, definindo o tipo de fonte de radiação e seu perigo radiológico. Esta dissertação apresenta a aplicação do método de agrupamento subtrativo, implementada em hardware, para um sistema de identificação de elementos radioativos com uma resposta rápida e eficiente. Quando implementados em software, os algoritmos de agrupamento consumem muito tempo de processamento. Assim, uma implementação dedicada para hardware reconfigurável é uma boa opção em sistemas embarcados, que requerem execução em tempo real, bem como baixo consumo de energia. A arquitetura proposta para o hardware de cálculo do agrupamento subtrativo é escalável, permitindo a inclusão de mais unidades de agrupamento subtrativo para operarem em paralelo. Isso proporciona maior flexibilidade para acelerar o processo de acordo com as restrições de tempo e de área. Os resultados mostram que o centro do agrupamento pode ser identificado com uma boa eficiência. A identificação desses pontos pode classificar os elementos radioativos presentes em uma amostra. Utilizando este hardware foi possível identificar mais do que um centro de agrupamento, o que permite reconhecer mais de um radionuclídeo em fontes radioativas. Estes resultados revelam que o hardware proposto pode ser usado para desenvolver um sistema portátil para identificação radionuclídeos.

Contribuições a técnicas de agrupamento e visualização de dados multivariados utilizando mapas auto-organizáveis

Self-organizing maps (SOM) are artificial neural networks widely used in the data mining field, mainly because they constitute a dimensionality reduction technique given the fixed grid of neurons associated with the network. In order to properly the partition and visualize the SOM network, the various methods available in the literature must be applied in a post-processing stage, that consists of inferring, through its neurons, relevant characteristics of the data set. In general, such processing applied to the network neurons, instead of the entire database, reduces the computational costs due to vector quantization. This work proposes a post-processing of the SOM neurons in the input and output spaces, combining visualization techniques with algorithms based on gravitational forces and the search for the shortest path with the greatest reward. Such methods take into account the connection strength between neighbouring neurons and characteristics of pattern density and distances among neurons, both associated with the position that the neurons occupy in the data space after training the network. Thus, the goal consists of defining more clearly the arrangement of the clusters present in the data. Experiments were carried out so as to evaluate the proposed methods using various artificially generated data sets, as well as real world data sets. The results obtained were compared with those from a number of well-known methods existent in the literature

Comparação de métodos de agrupamento para o estudo da divergência genética em cultivares de feijão

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Detecção de padrões de desempenho académico no ensino superior

O paradigma de avaliação do ensino superior foi alterado em 2005 para ter em conta, para além do número de entradas, o número de alunos diplomados. Esta alteração pressiona as instituições académicas a melhorar o desempenho dos alunos. Um fenómeno perceptível ao analisar esse desempenho é que a performance registada não é nem uniforme nem constante ao longo da estadia do aluno no curso. Estas variações não estão a ser consideradas no esforço de melhorar o desempenho académico e surge motivação para detectar os diferentes perfis de desempenho e utilizar esse conhecimento para melhorar a o desempenho das instituições académicas. Este documento descreve o trabalho realizado no sentido de propor uma metodologia para detectar padrões de desempenho académico, num curso do ensino superior. Como ferramenta de análise são usadas técnicas de data mining, mais precisamente algoritmos de agrupamento. O caso de estudo para este trabalho é a população estudantil da licenciatura em Eng. Informática da FCT-UNL. Propõe-se dois modelos para o aluno, que servem de base para a análise. Um modelo analisa os alunos tendo em conta a sua performance num ano lectivo e o segundo analisa os alunos tendo em conta o seu percurso académico pelo curso, desde que entrou até se diplomar, transferir ou desistir. Esta análise é realizada recorrendo aos algoritmos de agrupamento: algoritmo aglomerativo hierárquico, k-means, SOM e SNN, entre outros.

Sistema para projeto de célula de manufatura : definição de agrupamentos

O entendimento da manufatura celular passa pelo estudo das rotas de fabricação e pelos métodos de agrupamento de máquinas e de peças. Neste contexto, o objetivo principal deste trabalho é a implemetação de uma ferramenta de auxílio ao projeto de células de manufatura, abordando uma metodologia fundamentada na Tecnologia de Grupo para agrupamento de máquinas em células de manufatura com as respectivas famílias de peças. A base de dados com as informações das peças, das máquinas e das rotas que compõe o fluxo de produção é implementada em um banco de dados relacional. A matriz incidência peça-máquina é montada a partir das rotas armazenadas no banco de dados através de um aplicativo desenvolvido em Visual Basic. Os agrupamentos em famílias de peças e células de manufatura são gerados por três diferentes algoritmos: o Rank Order Clustering (ROC), o Close Neighbor Algorithm (CNA) e um algoritmo heurístico (HEU). São aplicadas restrições referentes a limite de carregamento, tamanho de célula e resolução de situações de “gargalo”. Processados os algoritmos de agrupamento, são analisados os resultados em função da densidade e da eficiência do agrupamento. O sistema apresenta o resultado final em planilhas no formato MS Excel. A primeira planilha, chamada resultados, exibe os valores das restrições de projeto das células (número de máquinas por célula, tempo limite de carregamento e tempo limite para duplicação da máquina), o número de peças (colunas) e de máquinas (linhas) da matriz incidência, os valores de eficiência do agrupamento de peças, do agrupamento de máquinas e do aproveitamento dos recursos, bem como o número de células independentes e a quantidade de máquinas duplicadas, obtidos por cada algoritmo no sistema, destacando os melhores resultados. A segunda planilha mostra a matriz incidência peça-máquina. As demais planilhas apresentam, respectivamente, a matriz diagonalizada com o algoritmo original (ROC e CNA), a matriz diagonalizada levando-se em consideração as restrições de projeto das células (análise ROC, análise CNA e HEU) e por fim, uma planilha relatório. A planilha relatório tabula os mesmos valores citados na primeira planilha e lista as peças associadas a cada família, as máquinas associadas a cada célula, as peças rejeitadas, por não se enquadrarem nos agrupamentos, e que devem ser tratadas fora do ambiente celular e as máquinas duplicadas. A comparação dos resultados é efetuada considerando as características adicionadas aos algoritmos originais. Dos três estudados, as restrições de projeto são tratadas na implementação do HEU. Os demais, ROC e CNA, têm incorporado um pós processamento. Em análises comparativas observa-se a superioridade dos algoritmos ROC e HEU em relação ao CNA e os resultados do ROC são melhores ou iguais aos demais, dificilmente inferiores.

Comitês de grupamento aplicados a dados de expressão gênica

The main goal of this work is to investigate the suitability of applying cluster ensemble techniques (ensembles or committees) to gene expression data. More specifically, we will develop experiments with three diferent cluster ensembles methods, which have been used in many works in literature: coassociation matrix, relabeling and voting, and ensembles based on graph partitioning. The inputs for these methods will be the partitions generated by three clustering algorithms, representing diferent paradigms: kmeans, ExpectationMaximization (EM), and hierarchical method with average linkage. These algorithms have been widely applied to gene expression data. In general, the results obtained with our experiments indicate that the cluster ensemble methods present a better performance when compared to the individual techniques. This happens mainly for the heterogeneous ensembles, that is, ensembles built with base partitions generated with diferent clustering algorithms

Novos métodos determinísticos para gerar centros iniciais dos grupos no algoritmo fuzzy C-Means e variantes

Data clustering is applied to various fields such as data mining, image processing and pattern recognition technique. Clustering algorithms splits a data set into clusters such that elements within the same cluster have a high degree of similarity, while elements belonging to different clusters have a high degree of dissimilarity. The Fuzzy C-Means Algorithm (FCM) is a fuzzy clustering algorithm most used and discussed in the literature. The performance of the FCM is strongly affected by the selection of the initial centers of the clusters. Therefore, the choice of a good set of initial cluster centers is very important for the performance of the algorithm. However, in FCM, the choice of initial centers is made randomly, making it difficult to find a good set. This paper proposes three new methods to obtain initial cluster centers, deterministically, the FCM algorithm, and can also be used in variants of the FCM. In this work these initialization methods were applied in variant ckMeans.With the proposed methods, we intend to obtain a set of initial centers which are close to the real cluster centers. With these new approaches startup if you want to reduce the number of iterations to converge these algorithms and processing time without affecting the quality of the cluster or even improve the quality in some cases. Accordingly, cluster validation indices were used to measure the quality of the clusters obtained by the modified FCM and ckMeans algorithms with the proposed initialization methods when applied to various data sets

Extração de conhecimento em bases de dados espaciais: algoritmo CHSMST+

Pós-graduação em Ciência da Computação - IBILCE

Detecção de outliers espaciais: refinamento de similaridade e desempenho

Pós-graduação em Ciência da Computação - IBILCE

Modelos de agrupamento e classificação para os bairros da cidade do Rio de Janeiro sob a ótica da Inteligência Computacional: Lógica Fuzzy, Máquinas de Vetores Suporte e Algoritmos Genéticos

A partir de 2011, ocorreram e ainda ocorrerão eventos de grande repercussão para a cidade do Rio de Janeiro, como a conferência Rio+20 das Nações Unidas e eventos esportivos de grande importância mundial (Copa do Mundo de Futebol, Olimpíadas e Paraolimpíadas). Estes acontecimentos possibilitam a atração de recursos financeiros para a cidade, assim como a geração de empregos, melhorias de infraestrutura e valorização imobiliária, tanto territorial quanto predial. Ao optar por um imóvel residencial em determinado bairro, não se avalia apenas o imóvel, mas também as facilidades urbanas disponíveis na localidade. Neste contexto, foi possível definir uma interpretação qualitativa linguística inerente aos bairros da cidade do Rio de Janeiro, integrando-se três técnicas de Inteligência Computacional para a avaliação de benefícios: Lógica Fuzzy, Máquina de Vetores Suporte e Algoritmos Genéticos. A base de dados foi construída com informações da web e institutos governamentais, evidenciando o custo de imóveis residenciais, benefícios e fragilidades dos bairros da cidade. Implementou-se inicialmente a Lógica Fuzzy como um modelo não supervisionado de agrupamento através das Regras Elipsoidais pelo Princípio de Extensão com o uso da Distância de Mahalanobis, configurando-se de forma inferencial os grupos de designação linguística (Bom, Regular e Ruim) de acordo com doze características urbanas. A partir desta discriminação, foi tangível o uso da Máquina de Vetores Suporte integrado aos Algoritmos Genéticos como um método supervisionado, com o fim de buscar/selecionar o menor subconjunto das variáveis presentes no agrupamento que melhor classifique os bairros (Princípio da Parcimônia). A análise das taxas de erro possibilitou a escolha do melhor modelo de classificação com redução do espaço de variáveis, resultando em um subconjunto que contém informações sobre: IDH, quantidade de linhas de ônibus, instituições de ensino, valor m médio, espaços ao ar livre, locais de entretenimento e crimes. A modelagem que combinou as três técnicas de Inteligência Computacional hierarquizou os bairros do Rio de Janeiro com taxas de erros aceitáveis, colaborando na tomada de decisão para a compra e venda de imóveis residenciais. Quando se trata de transporte público na cidade em questão, foi possível perceber que a malha rodoviária ainda é a prioritária

Algoritmos de agrupamentos fuzzy intervalares e índice de validação para agrupamento de dados simbólicos do tipo intervalo

Symbolic Data Analysis (SDA) main aims to provide tools for reducing large databases to extract knowledge and provide techniques to describe the unit of such data in complex units, as such, interval or histogram. The objective of this work is to extend classical clustering methods for symbolic interval data based on interval-based distance. The main advantage of using an interval-based distance for interval-based data lies on the fact that it preserves the underlying imprecision on intervals which is usually lost when real-valued distances are applied. This work includes an approach allow existing indices to be adapted to interval context. The proposed methods with interval-based distances are compared with distances punctual existing literature through experiments with simulated data and real data interval

Agrupamento espacial em robótica de enxame.

Os Sistemas Multi-Robôs proporcionam vantagens sobre um robô individual, quando da realização de uma tarefa com maiores velocidade, precisão e tolerância a falhas. Os estudos dos comportamentos sociais na natureza têm permitido desenvolver algoritmos bio-inspirados úteis na área da robótica de enxame. Seguindo instruções simples e repetitivas, grupos de robôs, fisicamente limitados, conseguem solucionar problemas complexos. Quando existem duas ou mais tarefas a serem realizadas e o conjunto de robôs é heterogêneo, é possível agrupá-los de acordo com as funcionalidades neles disponíveis. No caso em que o conjunto de robôs é homogêneo, o agrupamento pode ser realizado considerando a posição relativa do robô em relação a uma tarefa ou acrescentando alguma característica distintiva. Nesta dissertação, é proposta uma técnica de clusterização espacial baseada simplesmente na comunicação local de robôs. Por meio de troca de mensagens entre os robôs vizinhos, esta técnica permite formar grupos de robôs espacialmente próximos sem precisar movimentar os robôs. Baseando-se nos métodos de clusterização de fichas, a técnica proposta emprega a noção de fichas virtuais, que são chamadas de cargas, sendo que uma carga pode ser estática ou dinâmica. Se uma carga é estática permite determinar a classe à qual um robô pertence. Dependendo da quantidade e do peso das cargas disponíveis no sistema, os robôs intercambiam informações até alcançar uma disposição homogênea de cargas. Quando as cargas se tornam estacionárias, é calculada uma densidade que permite guiar aquelas que estão ainda em movimento. Durante as experiências, foi observado visualmente que as cargas com maior peso acabam se agrupando primeiro enquanto aquelas com menor peso continuam se deslocando no enxame, até que estas cargas formem faixas de densidades diferenciadas para cada classe, alcançando assim o objetivo final que é a clusterização dos robôs.

Avances en algoritmos de estimación de distribuciones. Alternativas en el aprendizaje y representación de problemas

131 p.: graf.