Objetivou-se, com este trabalho, estudar os métodos hierárquicos de análise de agrupamentos (ligação simples, ligação completa, ligação média, centróide e de Ward com base nas distâncias Euclidiana, Euclidiana ao quadrado, Manhattan e Mahalanobis), de modo a identificar qual é o mais adequado para uma base de dados arqueológicos. Utilizou-se uma base de dados fornecida pelo Grupo de Estudos Arqueométricos do IPEN CNEN/SP, na qual foram analisadas 146 amostras de fragmentos cerâmicos de três sítios arqueológicos por análise por ativação com nêutrons instrumental, sendo determinadas as frações de massa de 24 elementos químicos: As, Ba, Ce, Co, Cr, Cs, Eu, Fe, Hf, K, La, Lu, Na, Nd, Rb, Sb, Sc, Sm, Ta, Tb, Th, U, Yb e Zn. Para a determinação do melhor método, foram avaliados os dendrogramas conjuntamente com o valor dos coeficientes de correlação cofenética (CCC), obtidos para cada método. O método da ligação média mostrou-se mais coerente na formação dos agrupamentos, apresentando também os maiores valores do CCC. Por último, um script com funções do programa estatístico R foi desenvolvido para calcular o CCC, com o intuito de auxiliar os pesquisadores a encontrar o método de agrupamento mais apropriado para sua base de dados. / The objective of this work was to study the hierarchical methods of cluster analysis (single linkage, complete linkage, average linkage, centroid and Ward with base in the Euclidean distance, Squared Euclidean distance, Manhattan and Mahalanobis) to identify which is the most appropriate in archaeological data set. It was used a data set provided by the Archaeometry Studies Group from IPEN CNEN/SP in which 146 samples of ceramic fragments from three archaeological sites analyzed by instrumental neutron activation analysis, being determined the mass fractions of 24 chemical elements: As, Ba, Ce, Co, Cr, Cs, Eu, Fe, Hf, K, La, Lu, Na, Nd, Rb, Sb, Sc, Sm, Ta, Tb, Th, U, Yb and Zn. For the determination of the best method, it was evaluated the dendrograms together with value of the cophenetic correlation coefficient (CCC) obtained for each method. The average linkage method was more coherent in formation of the clusters, and with higher CCC values. Finally, a script with functions of the R statistical software was developed to calculate the CCC with aim to be a tool for researchers find the most appropriate method of cluster analysis for their data set.

O problema de clusterização (agrupamento) consiste em, a partir de uma base de dados, agrupar os elementos de modo que os mais similares fiquem no mesmo cluster (grupo), e os elementos menos similares fiquem em clusters distintos. Há várias maneiras de se realizar esses agrupamentos. Uma das mais populares é a hierárquica, onde é criada uma hierarquia de relacionamentos entre os elementos. Há vários métodos de se analisar a similaridade entre elementos no problema de clusterização. O mais utilizado entre eles é o método single linkage, que agrupa os elementos que apresentarem menor distância entre si. Para se aplicar a técnica em questão, uma matriz de distâncias é a entrada utilizada. Esse processo de agrupamento gera ao final uma árvore invertida conhecida como dendrograma. O coeficiente de correlação cofenética (ccc), obtido após a construção do dendrograma, é utilizado para avaliar a consistência dos agrupamentos gerados e indica o quão fiel o dendrograma está em relação aos dados originais. Dessa forma, um dendrograma apresenta agrupamentos mais consistentes quando o ccc for o mais próximo de um (1) . O problema de clusterização em todas as suas vertentes, inclusive a clusterização hierárquica (objeto de estudo nesse trabalho), pertence a classe de problemas NP-Completo. Assim sendo, é comum o uso de heurísticas para obter soluções de modo eficiente para esse problema. Com o objetivo de gerar dendrogramas que resultem em melhores ccc, é proposto no presente trabalho um novo algoritmo que utiliza os conceitos da metaheurística GRASP. Também é objetivo deste trabalho implementar tal solução em computação paralela em um cluster computacional, permitindo assim trabalhar com matrizes de dimensões maiores. Testes foram realizados para comprovar o desempenho do algoritmo proposto, comparando os resultados obtidos com os gerados pelo software R. / The problem of clustering (grouping) consists of, from a database, group the elements so that more queries are in the same cluster (group) and less similar elements are different clusters. There are several ways to accomplish these groupings. One of the most popular is the hierarchical, where a hierarchical relationships between the elements is created. There are several methods of analyzing the similarity between elements in the clustering problem. The most common among them is the single linkage method, which brings together the elements that are experiencing less apart. To apply the technique in question, distance matrix is the input used. This grouping process generates the end an inverted tree known as dendrogram. The cophenetic correlation coefficient (ccc), obtained after the construction of the dendrogram is a measure used to evaluate the consistency of the clusters generated and indicates how faithful he is in relation to the original data. Thus, a dendrogram gives more consistent clusters when the ccc is closer to one (1). The clustering problem in all its aspects, including hierarchical clustering (object of study in this work), belongs to the class of NP-complete problems. Therefore, it is common to use heuristics for efficient solutions to this problem. In order to generate dendrograms that result in better ccc, it is proposed in this paper a new algorithm that uses the concepts of GRASP metaheuristic. It is also objective of this work to implement such a solution in parallel computing in a computer cluster, thus working with arrays larger. Tests were conducted to confirm the performance of the proposed algorithm, comparing the results with those generated by the software R.

Objetivou-se, com este trabalho, estudar os métodos hierárquicos de análise de agrupamentos (ligação simples, ligação completa, ligação média, centróide e de Ward com base nas distâncias Euclidiana, Euclidiana ao quadrado, Manhattan e Mahalanobis), de modo a identificar qual é o mais adequado para uma base de dados arqueológicos. Utilizou-se uma base de dados fornecida pelo Grupo de Estudos Arqueométricos do IPEN CNEN/SP, na qual foram analisadas 146 amostras de fragmentos cerâmicos de três sítios arqueológicos por análise por ativação com nêutrons instrumental, sendo determinadas as frações de massa de 24 elementos químicos: As, Ba, Ce, Co, Cr, Cs, Eu, Fe, Hf, K, La, Lu, Na, Nd, Rb, Sb, Sc, Sm, Ta, Tb, Th, U, Yb e Zn. Para a determinação do melhor método, foram avaliados os dendrogramas conjuntamente com o valor dos coeficientes de correlação cofenética (CCC), obtidos para cada método. O método da ligação média mostrou-se mais coerente na formação dos agrupamentos, apresentando também os maiores valores do CCC. Por último, um script com funções do programa estatístico R foi desenvolvido para calcular o CCC, com o intuito de auxiliar os pesquisadores a encontrar o método de agrupamento mais apropriado para sua base de dados. / The objective of this work was to study the hierarchical methods of cluster analysis (single linkage, complete linkage, average linkage, centroid and Ward with base in the Euclidean distance, Squared Euclidean distance, Manhattan and Mahalanobis) to identify which is the most appropriate in archaeological data set. It was used a data set provided by the Archaeometry Studies Group from IPEN CNEN/SP in which 146 samples of ceramic fragments from three archaeological sites analyzed by instrumental neutron activation analysis, being determined the mass fractions of 24 chemical elements: As, Ba, Ce, Co, Cr, Cs, Eu, Fe, Hf, K, La, Lu, Na, Nd, Rb, Sb, Sc, Sm, Ta, Tb, Th, U, Yb and Zn. For the determination of the best method, it was evaluated the dendrograms together with value of the cophenetic correlation coefficient (CCC) obtained for each method. The average linkage method was more coherent in formation of the clusters, and with higher CCC values. Finally, a script with functions of the R statistical software was developed to calculate the CCC with aim to be a tool for researchers find the most appropriate method of cluster analysis for their data set.