Resumo: O problema tratado foi o de formular k grupos a partir de um subconjunto discreto e finito em um espaço d-dimensional. Os grupos constituídos devem obedecer a uma divisão que privilegie a alta similaridade entre elementos do mesmo grupo e a alta dissimilaridade entre elementos de grupos distintos. Trata-se de um problema de clusterização partitiva, que possui aplicações em um grande número de áreas, desde a segmentação de mercado até a análise de sequências macromoleculares. Nesta tese, propomos dois métodos para realizar este agrupamento: um algoritmo semissupervisionado, baseado em uma variante do k-médias (pk-means), que usa restrições espaciais para os centroides. Ele permitiu realizar agrupamentos com o uso de amostras classificadas que seriam descartadas por uma abordagem não supervisionada e que, por outro lado, não seriam suficientes para induzir um classificador supervisionado. A segunda proposta é um esquema de vizinhança para uso da VNS (meta-heurística de busca em vizinhança variável) como apoio a algoritmos de clusterização que são incorporados como métodos de busca local (variantes VNS). Fizemos uma grande variedade de experimentos computacionais que confirmaram que tanto o pk-means quanto as variantes VNS geram grupos mais homogêneos e coesos. Acrescido a isso, temos que os métodos propostos podem ser aplicados inclusive a dados dinâmicos, como séries temporais de imagens de satélite, pois apresentamos uma transformação que troca as séries temporais por parte dos seus harmônicos. Isso permitiu que realizássemos um estudo de caso, usando os métodos propostos para classificar imagens NDVI extraídas do sensor AVHRR/NOAA 17 e TERRA/MODIS Ver menos

Abstract: The problem treated is one of formulating k groups from a discrete and finite subset in a d-dimensional space. The groups must have high similarity between elements of the same group and high dissimilarity between elements of different groups. It is a partitive clustering problem that has applications in multiple areas like market segmentation or macromolecular sequence analysis. In our work, we propose two methods to perform this grouping: a semi-supervised algorithm, based on a k-means variant (pk-means), which uses spatial constraints for centroids. It allowed grouping by the use of classified sample that would be discarded by an unsupervised approach and, on the other hand, would not be sufficient to induce a supervised classifier. The second method is based on a neighborhood for VNS metaheuristic (variable neighborhood search) as support for clustering algorithms, that is used like local search (VNS variants). We confirmed by a great variety of computational experiments that both, pk-means and VNS variants, generate more homogeneous and cohesive groups. In addition to this, we applied the proposed methods to dynamic data, such time series of satellite images, because we also present a transformation that exchange the time series by their harmonics. This allowed us to classify NDVI images extracted from the AVHRR / NOAA 17 and TERRA / MODIS sensors Ver menos