Contribuições aos Processos de Clustering com Base em Métricas não-Euclidianas
AUTOR(ES)
Allan de Medeiros Martins
DATA DE PUBLICAÇÃO
2005
RESUMO
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
ASSUNTO(S)
engenharia eletrica teoria da informação métricas não-euclidianas information theory clustering clustering
