Non-uniform data distribution for communication-efficient parallel clustering

Global communicationrequirements andloadimbalanceof someparalleldataminingalgorithms arethe major obstacles to exploitthe computational power of large-scale systems. This work investigates how non-uniform data distributions can be exploited to remove the global communication requirement and to reduce the communication costin parallel data mining algorithms and, in particular, in the k-means algorithm for cluster analysis. In the straightforward parallel formulation of the k-means algorithm, data and computation loads are uniformly distributed over the processing nodes. This approach has excellent load balancing characteristics that may suggest it could scale up to large and extreme-scale parallel computing systems. However, at each iteration step the algorithm requires a global reduction operationwhichhinders thescalabilityoftheapproach.Thisworkstudiesadifferentparallelformulation of the algorithm where the requirement of global communication is removed, while maintaining the same deterministic nature ofthe centralised algorithm. The proposed approach exploits a non-uniform data distribution which can be either found in real-world distributed applications or can be induced by means ofmulti-dimensional binary searchtrees. The approachcanalso be extended to accommodate an approximation error which allows a further reduction ofthe communication costs. The effectiveness of the exact and approximate methods has been tested in a parallel computing system with 64 processors and in simulations with 1024 processing element

Dynamic group communication for large-scale parallel data mining

Exascale systems are the next frontier in high-performance computing and are expected to deliver a performance of the order of 10^18 operations per second using massive multicore processors. Very large- and extreme-scale parallel systems pose critical algorithmic challenges, especially related to concurrency, locality and the need to avoid global communication patterns. This work investigates a novel protocol for dynamic group communication that can be used to remove the global communication requirement and to reduce the communication cost in parallel formulations of iterative data mining algorithms. The protocol is used to provide a communication-efficient parallel formulation of the k-means algorithm for cluster analysis. The approach is based on a collective communication operation for dynamic groups of processes and exploits non-uniform data distributions. Non-uniform data distributions can be either found in real-world distributed applications or induced by means of multidimensional binary search trees. The analysis of the proposed dynamic group communication protocol has shown that it does not introduce significant communication overhead. The parallel clustering algorithm has also been extended to accommodate an approximation error, which allows a further reduction of the communication costs. The effectiveness of the exact and approximate methods has been tested in a parallel computing system with 64 processors and in simulations with 1024 processing elements.

Efficient group communication for large-scale parallel clustering

Global communication requirements and load imbalance of some parallel data mining algorithms are the major obstacles to exploit the computational power of large-scale systems. This work investigates how non-uniform data distributions can be exploited to remove the global communication requirement and to reduce the communication cost in iterative parallel data mining algorithms. In particular, the analysis focuses on one of the most influential and popular data mining methods, the k-means algorithm for cluster analysis. The straightforward parallel formulation of the k-means algorithm requires a global reduction operation at each iteration step, which hinders its scalability. This work studies a different parallel formulation of the algorithm where the requirement of global communication can be relaxed while still providing the exact solution of the centralised k-means algorithm. The proposed approach exploits a non-uniform data distribution which can be either found in real world distributed applications or can be induced by means of multi-dimensional binary search trees. The approach can also be extended to accommodate an approximation error which allows a further reduction of the communication costs.

A localização da indústria de transformação brasileira nas últimas três décadas

O propósito dessa dissertação é avaliar, numa perspectiva geográfica, os setores industriais no Brasil nas últimas três décadas. Numa primeira instância, o objetivo é verificar o nível de especialização e concentração dos estados brasileiros em termos industriais, utilizando-se os índices de Krugman e Gini, respectivamente. Com os resultados desses dois índices, os estados brasileiros são separados em quatro grupos, segundo o método de grupamento de médias K. Através de um produto interno usual entre o vetor da distribuição da produção industrial dos setores nos estados e vetores de algumas características desses setores (chamado de Viés das Características da Indústria - VCI), verifica-se em que tipos de indústrias os estados estão se especializando e/ou concentrando. Uma análise multivariada de componentes principais é feita com os VCI’s, na qual esses componentes principais são usados para verificar a similaridade dos estados. Sob outra perspectiva, busca-se investigar o nível de concentração geográfico dos setores industriais brasileiros. Para tanto, utilizaram-se o índice Gini e o índice de Venables. Nesse último, a distância entre os estados não é negligenciada para mensuração da concentração. Os setores industriais são separados em três grupos pelo método de grupamento de médias K, no qual as variáveis utilizadas são os componentes principais das características das indústrias. Utilizando outro produto interno, o Viés da Característica dos Estados (VCE), observa-se em que tipo de estados os setores industriais estão se concentrando ou não. Para visualizar como essas duas perspectivas, ou seja, como as características dos estados e das indústrias influenciam a localização dos setores industriais no território brasileiro, um modelo econométrico de dados cruzados de Midelfart-Knarvik e outros (2000) é estabelecido para o caso brasileiro. Neste modelo econométrico, é possível investigar como a interação das características das indústrias e dos estados podem determinar onde a indústria se localiza. Os principais resultados mostram que os fortes investimentos em infraestrutura na década de 70 e a abertura comercial na década de 90 foram marcantes para localização da indústria brasileira.

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

Identificação de regiões pluviometricamente homogêneas no Estado do Rio de Janeiro, utilizando-se valores mensais

O objetivo deste trabalho é dar uma contribuição ao estudo das condições climáticas do Estado do Rio de Janeiro, visando a uma melhor Classificação Climática por meio da identificação de regiões homogêneas em precipitação. Para isto foram utilizadas médias mensais da precipitação de 48 estações meteorológicas, em um período de 30 anos (1971-2000). A análise hierárquica de agrupamento, a orografia e a proximidade do mar, mostraram que o Estado do Rio de Janeiro pode ser dividido, quanto à precipitação, em seis regiões pluviometricamente homogêneas o que possibilitou classificar as estações meteorológicas pelo método de classificação não hierárquica k-means. A região norte do Estado, com precipitações anuais em torno de 870 mm é a mais seca, e a região da encosta sul da Serra do Mar, com 2020 mm, é a mais chuvosa. Mas, em ambas as regiões, os valores da precipitação da estação chuvosa representam em torno de 70% dos totais anuais.

Seleção de genótipos resistentes de amendoinzeiro a Anticarsia gemmatalis Hübner (Lepidoptera: Noctuidae) com base em análises multivariadas

The velvetbean caterpillar Anticarsia gemmatalis Hübner attacks peanut leaves, and the use of resistant varieties has directly contributed to ecological and economic aspects of pest control. The aim of this work was to select resistant peanut genotypes to A. gemmatalis using cluster analyses (dendogram obtained by Ward's methods and K-means) and Principal Components analysis for data interpretation. The evaluated genotypes were: IAC 5, IAC 8112, IAC 22 and IAC Tatu ST with upright growth habit, and IAC 147, IAC 125, IAC Caiapó and IAC Runner 886 with runner growth habit, and soybean genotype BR 16 as a susceptible control. The biological parameters: leaf consumption, larval (4o instar) and pupal (24h old) weight, larval and pupal development time and adult longevity were evaluated at laboratory conditions. The genotypes IAC 147 and IAC Runner 886 were resistant to A. gemmatalis in both cluster tests, grouping apart from most of the other genotypes. Both dendrogram and K-means methods provided satisfactory biological explanation, and they can be complementary used together with Principal Component and vice-versa. These results suggest that cluster analyses may be an important statistical tool in the selection of host plant resistance.

Parâmetros genéticos de características de carcaça e de qualidade da carne de aves oriundas de cruzamento recíproco

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

Abordagem multivariada na seleção de progênies de soja superiores e portadoras do gene RR

Pós-graduação em Agronomia (Genética e Melhoramento de Plantas) - FCAV

Variabilidade genética de caracteres morfológicos e germinação de Tabebuia caraiba (Mart.) Bur. (Bignoniaceae) no Município de Macapá, AP

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

Heterogeneidade Estrutural na Produtividade das Firmas Brasileiras

O objetivo deste trabalho é analisar uma das dimensões da heterogeneidade produtiva, estudando a distribuição das firmas entre diferentes estratos de produtividade na indústria de transformação, assim como a dinâmica de transição destas firmas dentro e entre estes estratos. Com esse objetivo, identificam-se, em primeiro lugar, grupos ou estratos em que a produtividade é marcadamente diferente, a partir de instrumental de cluster k-means. Posteriormente, por meio de um modelo probit ordenado, estuda-se a probabilidade de permanência das firmas nos diferentes estratos de produtividade, determinada por variáveis associadas ao progresso técnico, participação no comércio exterior, difusão e absorção de tecnologia e políticas públicas. Esta análise se faz em duas partes: em primeiro lugar para o total das empresas e incluindo os efeitos marginais para cada um dos clusters encontrados. Em segundo lugar, separando as firmas em quatro grupos, definidos pela intensidade tecnológica do processo produtivo. O estudo abrange o período 2000-2008, com uma base de dados de mais de 14.000 firmas brasileiras com 30 ou mais trabalhadores. O objetivo do trabalho é testar em que medida a heterogeneidade produtiva é um fenômeno persistente no tempo, em que medida ela tende a aumentar ou diminuir e em que medida é possível esperar um processo de transição entre estratos ou grupos no qual os grupos de mais alta produtividade elevam seu peso no total.

Estratégia de redução de consumo de energia em redes de sensores sem fio heterogêneas utilizando lógica fuzzy

O avanço nas áreas de comunicação sem fio e microeletrônica permite o desenvolvimento de equipamentos micro sensores com capacidade de monitorar grandes regiões. Formadas por milhares de nós sensores, trabalhando de forma colaborativa, as Redes de Sensores sem Fio apresentam severas restrições de energia, devido à capacidade limitada das baterias dos nós que compõem a rede. O consumo de energia pode ser minimizado, permitindo que apenas alguns nós especiais, chamados de Cluster Head, sejam responsáveis por receber os dados dos nós que formam seu cluster e propagar estes dados para um ponto de coleta denominado Estação Base. A escolha do Cluster Head ideal influencia no aumento do período de estabilidade da rede, maximizando seu tempo de vida útil. A proposta, apresentada nesta dissertação, utiliza Lógica Fuzzy e algoritmo k-means com base em informações centralizadas na Estação Base para eleição do Cluster Head ideal em Redes de Sensores sem Fio heterogêneas. Os critérios usados para seleção do Cluster Head são baseados na centralidade do nó, nível de energia e proximidade para a Estação Base. Esta dissertação apresenta as desvantagens de utilização de informações locais para eleição do líder do cluster e a importância do tratamento discriminatório sobre as discrepâncias energéticas dos nós que formam a rede. Esta proposta é comparada com os algoritmos Low Energy Adaptative Clustering Hierarchy (LEACH) e Distributed energy-efficient clustering algorithm for heterogeneous Wireless sensor networks (DEEC). Esta comparação é feita, utilizando o final do período de estabilidade, como também, o tempo de vida útil da rede.

Composição florística, estrutura e heterogeneidade ambiental da comunidade arbórea de uma várzea em Porto Ferreira, SP, Brasil

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Multivariate approach in the selection of superior soybean progeny which carry the RR gene

Efficiency in the use of genetic variability, whether existing or created, increases when properly explored and analysed. Incorporation of biotechnology into breeding programs has been the general practice. The challenge for the researcher is the constant development of new and improved cultivars. The aim of this experiment was to select progenies with superior characteristics, whether or not carriers of the RR gene, derived from bi-parental crosses in the soybean, with the help of multivariate techniques. The experiment was carried out in a family-type experimental design, including controls, during the agricultural year 2010/2011 and 2011/2012 in Jaboticabal in the Brazilian State of São Paulo. From the F3 generation, phenotypically superior plants were selected, which were evaluated for the following traits: number of days to flowering; number of days to maturity; height of first pod insertion; plant height at maturity; lodging; agronomic value; number of branches; number of pods per plant; 100-seed weight; number of seeds per plant; grain yield per plant. Given the results, it appears possible to select superior progeny by principal component analysis. Cluster analysis using the K-means method links progeny according to the most important characteristics in each group and identifies, by the Ward method and by means of a dendrogram, the structure of similarity and divergence between selected progeny. Both methods are effective in aiding progeny selection.

Multivariate analysis of the temporal variability of sugarcane ripening in south-eastern Brazil

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