Aula 3 Clusterização

2COP229
Inteligência Computacional
Aula 3
Clusterização
[email protected]
2COP229
Inteligência Computacional
Sumário (Clusterização)
- Introdução
- Aprendizado Não Supervisionado
- Aprendizado Supervisionado
- Introdução: Clusterização
- Etapas para o processo de Clusterização
- Distância e Medidas de Similaridade
- Complexidade dos Algoritmos de Clusterização
- Quantos Clusters?
- Prática: K-means.
[email protected]
2COP229
Inteligência Computacional
Introdução
Qual o seu propósito?
1) Predizer valores baseados no passado? Inferir
conhecimento e padrão? Computar novos valores
baseados em um ou mais atributos?
R: Regressão
2) Dividir amostras em classes? Utilizar uma base já
rotulada para avaliação?
R: Classificação
3) Dividir amostras em subgrupos que compartilham
características?
R: Clustering
[email protected]
2COP229
Inteligência Computacional
Aprendizado Não Supervisionado
[email protected]
2COP229
Inteligência Computacional
Aprendizado Não Supervisionado
- Não é oferecido ao modelo os resultados “esperados”;
- Os próprios dados são utilizados como entrada e as
propriedades estatísticas de distribuição são utilizadas;
- Significância de Clustering e Rótulo;
- O processo de rotulação pode ser realizado mesmo sendo
aplicado em apenas um grupo pequeno de objetos para
representar as classes desejadas;
- Decisão Posterior;
- Explorar os dados para encontrar estruturas intrínsecas
[email protected]
2COP229
Inteligência Computacional
Aprendizado Supervisionado
- Dados para “treinamento” incluem entrada e saída desejada;
- O processo de aprendizado esta voltado aos resultados
esperados e exemplos adequados;
- Os processos de treinamento, validação e teste é crucial;
- Os métodos normalmente são rápidos e precisos;
- São capazes de generalizar os resultados com base nos
rótulos;
- É capaz de descobrir padrões em uma base e predizer
valores em instâncias de dados futuras.
[email protected]
2COP229
Inteligência Computacional
Aprendizado Não Supervisionado
[email protected]
2COP229
Inteligência Computacional
Introdução: Clusterização
- Classificação não supervisionada;
- Divisão entre grupos (clusters, subsets, categories);
- Definição, sendo:
padrões
características
[email protected]
2COP229
Inteligência Computacional
Introdução: Clusterização
Hard Clustering
Hierarchical Clustering
[email protected]
2COP229
Inteligência Computacional
Introdução: Clusterização
Hierarchical Clustering
Grau de Pertinência
de cada cluster
Grau de Pertinência
em cada N
[email protected]
2COP229
Inteligência Computacional
Etapas para o processo de Clusterização
[email protected]
2COP229
Inteligência Computacional
Etapas para o processo de Clusterização
- Seleção ou extração de características:
Distinguir características de um grupo de candidatos e
utilizar características para gerar novas;
Esta abordagem é útil para evitar ruídos e facilitar a
interpretação das informações.
- Algoritmo de clusterização ou seleção:
Determinar a medida de proximidade ou função;
A função de proximidade afeta diretamente o agrupamento;
Não existe um algoritmo universal para clusterização, cada
problema exige uma solução;
[email protected]
2COP229
Inteligência Computacional
Etapas para o processo de Clusterização
- Validação de agrupamento
Dado um conjunto qualquer algoritmo de clusterização irá
retornar uma divisão (existindo ou não);
Cada abordagem retornará um agrupamento diferente;
O grau de confiança do agrupamento formado é a métrica
utilizada, avaliando: índices externos, índices internos e
índices relativos.
- Interpretação dos resultados:
Tem como objetivo promover significado e conhecimento
sobre os dados originais.
[email protected]
2COP229
Inteligência Computacional
Distância e Medidas de Similaridade
- Minkowski Distance: Métrica, invariante para translação e
rotação para n = 2 (Euclidean Distance). Características com
valores grandes e muita variação tendem a dominar outras
características. Abordagens: Fuzzy c-means.
[email protected]
2COP229
Inteligência Computacional
Distância e Medidas de Similaridade
- Euclidean Distance: Métrica mais utilizada. É um caso
especial da Minkowski para n=2. Tende a formar clusters
hiperesféricos. Abordagens: K-means
[email protected]
2COP229
Inteligência Computacional
Distância e Medidas de Similaridade
hiperesférico
hiperbólico
plano
[email protected]
2COP229
Inteligência Computacional
Distância e Medidas de Similaridade
- City-Block Distance: Caso especial da Minkowski com n=1,
tende a agrupar de formas hiperretangulares. Aplicações com
Fuzzy ART.
[email protected]
2COP229
Inteligência Computacional
Distância e Medidas de Similaridade
[email protected]
2COP229
Inteligência Computacional
Distância e Medidas de Similaridade
- Sup Distance: Caso especial da Minkowski com n=ꝏ, com
aplicações com Fuzzy c-means.
[email protected]
2COP229
Inteligência Computacional
Distância e Medidas de Similaridade
- Mahalanobis Distance: S é calculado baseado em todos os
objetos, tendendo ao formato hiperelipsoidal. Quando as
características não estão correlacionadas a distância fica
equivalente ao quadrado da Euclidean Distance. Aplicações
com Ellipsoidal ART e Hyperrellipsoidal Clustering algorithm.
Computacionalmente caro.
[email protected]
2COP229
Inteligência Computacional
Distância e Medidas de Similaridade
- Pearson Correlation: Não é métrico. Derivado do Coeficiente
de Correlação. Incapaz de reconhecer a diferença de
magnitude entre duas variáveis.
[email protected]
2COP229
Inteligência Computacional
Distância e Medidas de Similaridade
- Point Symmetry Distance: Não é métrico. Computa a
distância entre um objeto e uma referência. Abordagem: SBKM
(Symmetry-based K-means)
[email protected]
2COP229
Inteligência Computacional
Distância e Medidas de Similaridade
- Cosine Distance: Independente do comprimento do vetor de
características. Invariante a rotação, mas não a transformações
lineares. Utilizado em agrupamento de documentos.
[email protected]
2COP229
Inteligência Computacional
Distância e Medidas de Similaridade
- Point Symmetry Distance: Não é métrico. Computa a
distância entre um objeto e uma referência. Abordagem: SBKM
(Symmetry-based K-means)
[email protected]
2COP229
Inteligência Computacional
Distância e Medidas de Similaridade
- Symmetry:
- Positivity:
- Triangle Inequality:
- Reflexivity:
[email protected]
2COP229
Inteligência Computacional
Algoritmos de Clusterização
- K-means:
- Fuzzy c-means:
- Hierarchical Clustering:
- CLARA:
[email protected]
2COP229
Inteligência Computacional
Algoritmos de Clusterização
- BIRCH:
- DBSCAN:
- WaveCluster: Linear para o número de objetos e quadrática
com o número de dimensões.
- CLIQUE:
- OptiGrid:
[email protected]
2COP229
Inteligência Computacional
Quantos Clusters?
- Para a maioria das abordagens o usuário deve determinar a
quantidade de clusters (K) baseando-se na experiência os
circunstâncias do processo.
- Ténicas:
1) Visualização dos grupos;
2) Índices de certeza (regras de parada);
3) Otimização e critérios probabilísticos;
4) Heurísticas;
[email protected]
2COP229
Inteligência Computacional
Prática: K-means
Problem: Cluster the following eight points (with (x, y) representing locations) into three
clusters A1(2, 10) A2(2, 5) A3(8, 4) A4(5, 8) A5(7, 5) A6(6, 4) A7(1, 2) A8(4, 9).
Initial cluster centers are: A1(2, 10), A4(5, 8) and A7(1, 2). The distance function
between two points a=(x1, y1) and b=(x2, y2) is defined as:
ρ(a, b) = |x2 – x1| + |y2 – y1| .
Use k-means algorithm to find the three cluster centers after the second iteration.
[email protected]
2COP229
Inteligência Computacional
Referências:
Silva, IN da, Danilo Hernane Spatti, and Rogério Andrade Flauzino. "Redes neurais
artificiais para engenharia e ciências aplicadas." São Paulo: Artliber (2010).
Konar, A. “Computational Intelligence: Principles, Techniques and Applications” (2005)
Jensen, R. Shen, Q. “Computational Intelligence and Feature Selection” (2008)
[email protected]