Contribuições aos Processos de Clustering com Base em Métricas não-Euclidianas

In this work we present a new clustering method that groups up points of a data set in classes. The method is based in a algorithm to link auxiliary clusters that are obtained using traditional vector quantization techniques. It is described some approaches during the development of the work that are based in measures of distances or dissimilarities (divergence) between the auxiliary clusters. This new method uses only two a priori information, the number of auxiliary clusters Na and a threshold distance dt that will be used to decide about the linkage or not of the auxiliary clusters. The number os classes could be automatically found by the method, that do it based in the chosen threshold distance dt, or it is given as additional information to help in the choice of the correct threshold. Some analysis are made and the results are compared with traditional clustering methods. In this work different dissimilarities metrics are analyzed and a new one is proposed based on the concept of negentropy. Besides grouping points of a set in classes, it is proposed a method to statistical modeling the classes aiming to obtain a expression to the probability of a point to belong to one of the classes. Experiments with several values of Na e dt are made in tests sets and the results are analyzed aiming to study the robustness of the method and to consider heuristics to the choice of the correct threshold. During this work it is explored the aspects of information theory applied to the calculation of the divergences. It will be explored specifically the different measures of information and divergence using the Rényi entropy. The results using the different metrics are compared and commented. The work also has appendix where are exposed real applications using the proposed method

Neste trabalho apresentamos um novo método de clustering que agrupa pontos de um conjunto de dados em classes. O método baseia-se em um algoritmo para ligação de clusters auxiliares que são obtidos usando-se técnicas de quantização vetorial tradicionais. São descritas algumas abordagens durante o desenvolvimento do trabalho que baseiam-se em medidas de distância ou dissimilaridade (divergência) entre os clusters auxiliares. Este novo método utiliza apenas duas informações a priori, a saber: o número de centros auxiliares Na e uma distância de limiar dt que será utilizada para decidir sobre a ligação ou não dos clusters auxilares. O número de clusters pode ser automaticamente encontrado pelo método, que o faz com base na distância limiar dt escolhida. Analogamente, o número de classes, pode ser fornecido como informação adicional para auxiliar na escolha do limiar correto. Algumas análises são feitas e os resultados são comparados com outros métodos tradicionais de clustering. Neste trabalho são analisadas diferentes métricas de dissimilaridade e uma nova métrica baseada no conceito de negentropia é proposta. Além de agrupar pontos de um conjunto de classes, é proposto um método para o modelamento estatístico das classes de modo a se obter uma expressão para a probabilidade de um ponto pertencer a uma das classes. Experimentos com diversos valores de Na e dt são realizados em conjuntos de teste e os resultados são analisados de maneira a se estudar a robustez do método e propor heurísticas para a escolha do limiar correto. No trabalho são explorados os aspectos de teoria da informação aplicados ao cálculo das divergências. São exploradas em particular as diferenças medidas de informação e divergência utilizando a entropia de Rényi. Os resultados utilizando as diferentes métricas são comparados e comentados. O trabalho ainda conta com apêndices onde são expostas aplicações reais utilizando o método proposto