Novas metodologias para clusterização de dados

NOVAS METODOLOGIAS PARA CLUSTERIZAÇÃO DE DADOS

ÍNDICE
AGRADECIMENTOS iii
RESUMO iv
ABSTRACT v
1 INTRODUÇÃO 1
1.1 Objetivo da Tese 1
1.2 Relevância e Aplicações 1
1.3 Organização do texto 3
2 CLUSTERIZAÇÃO DE DADOS 4
2.1 Introdução 4
2.2 O problema de Clustering 4
2.3 Definição Formal 6
2.4 Aplicações 7
2.5 Dificuldades para encontrar o Clustering correto 9
2.6 Estruturas de dados 10
2.7 Tipos de dados 12
2.8 Medidas de similaridade 13
2.8.1 Variáveis escaladas em intervalos 14
2.8.2 Variáveis binárias 17
2.8.3 Variáveis nominais 19
2.8.4 Variáveis ordinais 19
2.8.5 Variáveis escaladas por proporção 20
2.8.6 Combinações dos diversos tipos de variáveis 20
2.9 Métodos de Clustering 21
2.9.1 Métodos por particionamento 23 vii 2.9.1.1 Técnica baseada em centróide: o método k-means 25
2.9.1.2 Técnica baseada em objeto representativo: o método k-medoids 28
2.9.1.3 Métodos de particionamento em grandes bases de dados: do k-medoids para CLARANS 31
2.9.2 Métodos hierárquicos 35
2.9.2.1 BIRCH: Balanced Iterative Reducing and Clustering Using
Hierarchies 40
2.9.2.2 CURE: Clustering Using REpresentatives 46
2.9.2.3 ROCK: Um algoritmo de Clustering robusto para atributos categóricos 49
2.9.3 Métodos baseados em densidade 51
2.9.3.1 DBSCAN: Um método de Clustering baseado em densidade e baseado em regiões conectadas com densidade suficientemente alta 53
2.9.3.2 OPTICS: Ordering Points To Identify the Clustering
Structure 57
2.9.3.3 DENCLUE: Clustering baseado em funções de distribuição de densidade 59
2.9.4 Métodos baseados em grades 61
2.9.4.1 STING: STatistical INformation Grid 62
2.9.4.2 WaveCluster: Clustering usando transformação Wavelet 64
2.9.4.3 CLIQUE: Clustering de espaços de alta dimensão 67
2.9.5 Métodos baseados em modelos 71
2.9.5.1 Abordagem estatística 71
2.9.5.2 Abordagem por rede neural 74
3 ESTRATÉGIA IMPLEMENTADA 77
3.1 Introdução 77
3.2 Pequena introdução aos Algoritmos Genéticos 77
3.2.1 Algoritmos