Clusterização baseada em algoritmos fuzzy

Abstract

Análise de cluster é uma técnica aplicada a diversas áreas como mineração de dados, reconhecimento de padrões, processamento de imagens. Algoritmos de clusterização têm por objetivo particionar um conjunto de dados em clusters de tal forma que indivíduos dentro de um mesmo cluster tenham um alto grau de similaridade, enquanto indivíduos pertencentes a diferentes clusters tenham alto grau de dissimilaridade. Uma importante divisão dos algoritmos de clusterização é entre algoritmos hard e fuzzy. Algoritmos hard associam um indivíduo a somente um cluster. Ao contrário, algoritmos fuzzy associam um indivíduo a todos os clusters através da variação do grau de pertinência do indivíduo em cada cluster. A vantagem de um algoritmo clusterização fuzzy é que este pode representar melhor incerteza e este fato é importante, por exemplo, para mostrar que um indivíduo não é um típico indivíduo de nenhuma das classes, mas tem similaridade em maior ou menor grau com mais de uma classe. Uma forma intuitiva de medir similaridade entre indivíduos é usar medidas de distância tais como a distância euclidiana. Existem muitas medidas de distância disponíveis na literatura. Muitos dos algoritmos de clusterização populares geralmente buscam minimizar um critério baseados numa medida de distância. Através de um processo iterativo estes algoritmos calculam parâmetros de modo a diminuir o valor do critério iteração a iteração até um estado de convergência ser atingido. O problema com muitas das distâncias encontradas na literatura é que elas são estáticas. Para o caso de algoritmos de clusterização iterativos, parece razoável ter distâncias que mudem ou atualizem seus valores de acordo com o que for ocorrendo com os dados e as estruturas de dado do algoritmo. Esta dissertação apresenta duas distâncias adaptativas aplicadas ao algoritmo fuzzy c-means pelo Prof. Francisco de Carvalho. Este algoritmo foi escolhido pelo fato de ser amplamente utilizado. Para avaliar as proposições de distância, experimentos foram feitos utilizando-se conjunto de dados de referência e conjuntos de dados artificiais (para ter resultados mais precisos experimentos do tipo Monte Carlo foram realizados neste caso). Até o momento, comparações das versões do fuzzy c-means, obtidas através da utilização de distâncias adaptativas, com algoritmos similares da literatura permitem concluir que em geral as novas versões têm melhor performance que outros disponíveis na literatura