Aula 14: Clusterização 2 - Métodos Hierárquicos

Question 1

Clusters podem ser conjuntos disjuntos ou…

Answer 1

…ou podem ser organizados de maneira hierárquica.
Ex.: taxonomia, geografia, astronomia ou biologia.

Question 2

Abordagens para a clusterização hierárquica

Answer 2

Aglomerativa (Single Linkage): Agrupa os primeiros pares que estão próximos de si.

Divisiva (Complete Linkage): Desagrupa os primeiros pares que estão distantes de si

Question 3

Formalização da clusterização aglomerativa

Answer 3

Considerando a sequência de partições dos N pontos para os clusters, temos que:

• A primeira partição contém N clusters, cada um com um ponto
• A segunda partição contém N-1 clusters (um cluster com dois pontos e o restante com somente um)
• A k-ésima partição contém N-k+1 clusters

Question 4

O que é necessário para a implementação da clusterização aglomerativa

Answer 4

Para implementar a clusterização aglomerativa precisa-se de duas coisas:

1. A métrica de distância (Euclidiana ou índice Jaccard)
2. Critério de aglomeração que pode ser a distância média entre os centróides dos clusters, combinação de dois clusters com o par mais próximo de elementos externos (single linkage) ou a combinação de dois clusters com os elementos mais distantes entre si (complete linkage)

Question 5

Clusterização de matrizes N x d

Answer 5

Organizando um conjunto de N pontos de dimensão d em uma matriz N x d, então pode-se aplicar dois procedimentos de clusterização hierárquicos.

• Primeiro se clusteriza os N ponto de dados (linhas);
• Então é aplicado a clusterização hierárquica na matriz transposta, ou seja, nessa clusterização temos d pontos, cada um com dimensionalidade N.

O resultado obtido é melhor visualizado através de um mapa de calor.

Question 6

Clusterização Divisiva

Answer 6

É uma abordagem Top-Down ao invés de Bottom-Up.
Durante as iterações é necessário encontrar a melhor partição entre os clusters.

Question 7

Complexidade temporal dos diferentes métodos

Answer 7

k-means: O(N²)

Clusterização aglomerativa: O(N³), muito lento para datasets grandes

Clusterização divisiva: O(2^N) (sem heurísticas). Uma possível heurística seria rodar k-means, com k=2 no cluster para dividir em duas partes disjuntas.

Question 8

Algumas observações sobre clusterização

Answer 8

• O procedimento de clusterização é dependente do contexto;
• Não há uma escolha correta de hiperparâmetros;
• Scaling features podem afetar os clusters.