Clustering(k-means, SOM e hierárquicos)

André Tavares da Silvaandre.silva@udesc.br

(Capítulo 10 de Duda e Hart)

Roteiro

• Clustering– Introdução e tipos

• Agrupamentos hierárquicos– AGNES, DIANA e Dendogram

• K-means (k-médias)

• Modelo Mistura de Gaussianas e EM

• SOM (Self-Organizing Maps)

Clustering

• Nos casos onde não são conhecidos os rótulos das classes ou mesmo a quantidade de classes, algoritmos de agrupamento (clustering) são utilizados para classificação.

• Clustering:– Dado um conjunto de objetos, colocar os mesmos em

grupos baseados na similaridade entre eles

– Usado para encontrar padrões inesperados nos dados

– É um problema inerentemente não definido claramente

Clustering

Como agrupar esses elementos?

Família Simpson Masculino Feminino

Possibilidades:Possibilidades:

Empregados da Escola

Tipos de clustering

• Algoritmos de Particionamento: separam um espaço de acordo com algum critério(k-means, SOM,...).

• Algoritmos hierárquicos: Além da partição espacial, também podem conter subgrupos,ou seja, alguns grupos podem ainda ser subdivididos (multidão→pessoa→mão→dedos→...).

Agrupamento hierárquico

• Usam matriz de distância como critério de agrupamento. Necessita de um critério de parada para sair da recursão.

• AGNES (Agglomerative Nesting)– Inicialmente cada objeto é um cluster (folha da

árvore);

– Os nós são agrupados pela menor distância (similaridade) recursivamente;

– Os critérios de parada definidos pelo usuário são: distância mínima, distância máxima, distância média e distância central.

– No topo da árvore (raiz), todos os elementos estarão em um mesmo cluster.

Agrupamento hierárquico

• DIANA (Divisive Analysis)– Inverso do AGNES

– Inicia com a raiz contendo todos os objetos;

– recursivamente divide os agrupamentos;– Os nós folhas conterão apenas um objeto.

Agrupamento hierárquico

0

1

2

3

4

5

6

7

8

9

10

0 1 2 3 4 5 6 7 8 9 10

0

1

2

3

4

5

6

7

8

9

10

0 1 2 3 4 5 6 7 8 9 10

0

1

2

3

4

5

6

7

8

9

10

0 1 2 3 4 5 6 7 8 9 10

• Dendrogram– Os objetos (dados,imagens,...) são decompostos em

vários níveis de particionamento (árvores de clusters), chamados de dendrograma.

– Um agrupamento é obtido cortando o dendrogram em um nível preestabelecido

– Em seguida, os componentes ligados formam um novo aglomerado.

– Muito usado na Biologia Computacional (ver imagem “hominidae”).

Agrupamento hierárquico

Algoritmo k-means

1. Decidir um valor para k.

2. Inicializa os k centros de clusters (protótipos) aleatoriamente (ou algum critério predefinido).

3. Decidir a classe (rótulo) dos objetos em Z de acordo com o protótipo mais próximo.

4. Estimar novamente a posição dos protótipos pelo centro do agrupamento, assumindo que a classificação está correta.

5. Enquanto os objetos mudarem de rótulo, volta ao passo 3.

Exemplo do algoritmo k-means

0

1

2

3

4

5

6

7

8

9

10

0 1 2 3 4 5 6 7 8 9 10

0

1

2

3

4

5

6

7

8

9

10

0 1 2 3 4 5 6 7 8 9 10

0

1

2

3

4

5

6

7

8

9

10

0 1 2 3 4 5 6 7 8 9 10

0

1

2

3

4

5

6

7

8

9

10

0 1 2 3 4 5 6 7 8 9 10

Considerações sobre k-means

• Relativamente eficiente O(tkn), onde n é o número de objetos em Z, k é o número de clusters e t é o número de iterações.

• Frequentemente cai em um mínimo local. Métodos como simulated annealing e algoritmos genéticos são usados para encontrar um mínimo melhor (melhor agrupamento).

Considerações sobre k-means

• Aplicado somente a dados numéricos.

• Sensível a dados ruidosos e outliers.

• Não adequado para descobrir agrupamentos em formas não convexas (distribuições não esféricas).

• É preciso definir o valor de k a priori.

Considerações sobre k-means

• Aplicado somente a dados numéricos.

• Sensível a dados ruidosos e outliers.

• Não adequado para descobrir agrupamentos em formas não convexas (distribuições não esféricas).

• É preciso definir o valor de k a priori.

Testar diferentes valores de k e testar qualgera maior “separabilidade” entre classese/ou maior “compactabilidade” interclasses.

Considerações sobre k-means

• Aplicado somente a dados numéricos.

• Sensível a dados ruidosos e outliers.

• Não adequado para descobrir agrupamentos em formas não convexas (distribuições não esféricas).

• É preciso definir o valor de k a priori.

Modelo de Misturas

• Caso o modelo seja conhecido, assume-se que os dados sejam gerados usando o seguinte procedimento:

• 1. Pegar um dos k componentes de acordo com P(Z

k). Este procedimento seleciona uma classe

rotulada Zk.

• 2. Gerar uma nuvem de pontos pela amostragem de p(x|Z

k).

Modelo de Misturas

• Resulta na distribuição de probabilidade de um ponto p(x):

onde p(x|Zk) é qualquer distribuição (gaussiana,

poisson, exponencial,...).

p( x)=∑k =1

K

P (Z k ) p ( x∣Z k )

Modelo Mistura de Gaussianas (MMG)• O modelo mais comum de modelo de mistura é

o de gaussianas – MMG.

• Modelo do cluster: distribuição normal (média, covariância).

• Assume-se que as medidas sejam iguais para todos os clusters.

• Probabilidade máxima: média é a de todas as amostras.

Modelo Mistura de Gaussianas (MMG)• Mas:

– quais pontos pertencem a uma mesma amostra?– para estimar a probabilidade é preciso de um

modelo (problema do ovo e da galinha).– para resolver o problema, podemos usar o

algoritmo EM (Expectation Maximization), que é capaz de encontrar um ótimo local da função de máxima verossimilhança de uma mistura de Gaussianas.

Algoritmo EM• O EM possui duas etapas iterativas:

• Expectation Step: Nessa etapa ele calcula a probabilidade de cada ponto pertencer a cada Gaussiana. Além disso, é calculada uma nova estimativa da função de verossimilhança utilizando a equação:

j

jijkikki cdwcdwcdP ) |Pr() |Pr() (

N

cdw i

ki

k

) Pr(

Algoritmo EM

• Maximation step: Nessa etapa, as componentes da mistura são maximizadas (estimativa dos parâmetros do modelo)

m

ik

ji

kiik cdP

cdPd

m 1 ) (

) (1

Iteração 1

Ponto médio dos clusters são estimados aleatoriamente

Iteração 2

Iteração 5

Iteração 25

Considerações sobre EM

• Parâmetro k é definido a priori.

• Converge para um mínimo local.

• k-means é um caso especial(hiperesferas em vez de hiperelipsóides).

SOM(Self-Organizing Maps - Mapas Auto-Organizáves)

• Assim como k-means, o número de clusters deve ser definido a priori;

• Diferente do k-means, no SOM há uma ordenação topológica dos clusters.

SOM

Definir número de clusters: 6

SOM

Posicionar uma grade com seis nós

SOM

P

Um padrão P é selecionado aleatoriamente

SOM

NP

O nó NP mais próximo a P é selecionado

P

SOM

A posição do nó NP é ajustada

P

NP

SOM

O padrão Q é selecionado aleatoriamente

Q

NQ

SOM

A posição do nó NQ é ajustada

Q

NQ

SOM

Repetir até que o critério de parada seja satisfeito

Considerações sobre SOM

• Número k de clusters é definido a priori

• Não-determinístico – inicializações aleatórias dos pesos

• Define a ordenação topológica dos aglomerados

• Resultado depende de muitos parâmetros: inicializações de pesos, taxa de aprendizado, taxa de vizinha, número de iterações...

Outros modelos

• Uso de Análise de Componentes Principais

• Agrupamento dinâmico– Variação do k-means (k-medoids,...)

• Algoritmo de agrupamento baseado em árvore geradadora mínima (minimal Spanning trees)

• Self-Organizing Tree algorithm

• Mapas de Kohonen

• Nearest Neighbor Clustering (não confundir com Knn)