Outras familias de clusterização

Jacques Wainer

Clusterização hierárquica

aglutinativa: variações na definição de linkage
- single
- average
- complete
- Wald
divisiva

ir agrupando as 2 “coisas” mais próximas entre si.
“coisas” podem ser dados e e clusters
mas é preciso definir qual a distancia de um cluster a um dado e a distancia entre dois clusters - essa é a função de linkage

single: a distancia de 2 clusters é a menor distancia entre pontos de um para os pontos do outro
complete: a distancia entre 2 clusters é a maior distancia entre os pontos de um para os pontos do outro
average: a distancia é a média das distancias entre os pontos de um e do outro
Ward - distancia quadratica dos pontos ao centro do cluster

Uma representação grafica dos pontos (e clusters) sendo agregados em clusteres maiores, até a ultima etapa onde cria-se o cluster final com todos os dados
representado como uma arvore com a raiz no topo
a barra horizontal indica que 2 clusters (ou pontos) formaram um cluster, e a altura da barra indica a distancia entre os dois subclusters originais
http://stats.stackexchange.com/questions/82326/how-to-interpret-the-dendrogram-of-a-hierarchical-cluster-analysis
outros formatos: horizontal http://stackoverflow.com/questions/14118033/horizontal-dendrogram-in-r-with-labels polar http://stats.stackexchange.com/questions/4062/how-to-plot-a-fan-polar-dendrogram-in-r

Normalmente o dendograma por si só não nos da informação útil.
usa-se o dendograma para definir onde “vai ser cortado”, que define o numero de clusters: figura em https://scikit-learn.org/stable/auto_examples/cluster/plot_agglomerative_dendrogram.html

Função hclust http://www.rdocumentation.org/packages/stats/functions/hclust faz o dendograma. Note que a função recebe uma matrix de distancia e não os dados. method= define o linkage
plot plota o dendograma (2 versões, hang=-1)
cutree corta o dendograma em k clusters e retorna o clustering dos dados
rect.hclust http://www.rdocumentation.org/packages/stats/functions/rect.hclust.html desenha no dendograma retângulos nos clusteres finais (dado o k)

Use um k-means com k=2 para dividir o conjunto todo em 2 grupos.
pegue o cluster com maior diametro (= maior distancia entre 2 membros do cluster) e divida-o usando o 2-means
repita o processo ate que so reste um dado em cada cluster.
parece ser usado em processamento de texto.
implementado pela função diana http://www.rdocumentation.org/packages/cluster/functions/diana em R. (A função pode usar o k-medoides em vez do k-means)
não há algoritmo divisivo em sklearn.

Cluster são regiões de alta densidade de dados separados por regiões de baixa densidade
um ponto é denso se num raio Eps existem pelo menos MinPts dados. Os pontos dentro do raio Eps são chamados de vizinhança
um ponto é fronteiriço se ele pertence a vizinhança de um ponto denso mas ele proprio não é denso.
um ponto é um outlier caso contrario.
https://en.wikipedia.org/wiki/DBSCAN
https://www.datanovia.com/en/lessons/dbscan-density-based-clustering-essentials/

encontre um ponto denso sem cor: ele iniciar um cluster novo
pontos densos propagam seu cluster para os vizinhos,
pontos fronteiriços recebem uma indicação de cluster mas nao propagam
outliers nao recebem indicação de cluster
- https://www.datanovia.com/en/lessons/dbscan-density-based-clustering-essentials/
DBscan define o numero de clusters automaticamente, nao é completo (nem todos os pontos pertencem a um cluster),
mas tem 2 parametros que precisam de ajuste (em vez de um para o k-means) Eps e MinPts

determinar para cada ponto a distancia do k-ezimo vizinho mais próximo.
varios lugares recomendam k=4 ou k=5 - esse será o MinPts.
plote a distancia ordenada do k-esimo vizinho mais proximo de cada dado. Deve haver um cotovelo a partir do qual a distancia do k-esimo vizinho aumenta - essa distancia sera o Eps
exemplo https://www.datanovia.com/en/lessons/dbscan-density-based-clustering-essentials/
a intuição é que a maioria dos pontos são densos e portanto o MinPts-ezimo vizinho deve ser menor que o Eps (já que ele é denso)

Função dbscan do pacote dbscan
ha também oa função dbscan do pacote fpc (usando na aula anterior).
o pacote dbscan tem a função kNNdist(x, k, ...) e kNNdistplot(x, k = 4, ...) para plotar as distancias do k-ezimo vizinho.
sklearn: https://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html#sklearn.cluster.DBSCAN

DENCLUE

divida cada dimensão i em n_i 1-células (1d-células) normalmente equi-espaçadas
haverá n = \Pi_i^d n_i d-dimensional células (hiper-retângulos).
defina qual o numero de dados X em uma d-célula que indica que há uma concentração de dados (média por d-célula é N/n.
para cada dimensão selecione as 1-células que contem pelo menos X dados. Para pares de 1-células, selecione as 2-células que contem pelo menos X dados, e assim por diante.
no final voce terá um conjunto de d-células cada uma com pelo menos X dados. Normalmente junta-se as d-células que são adjacentes.
variações do algoritmos trabalham com células de multiplas resoluções
não sei como escolher o X.

Ensembles são muito usados em modelos preditivos, geralmente com muito sucesso
São um conjunto de classificadores da mesma familia (mas treinados com dados levemente diferentes) ou de familias diversas (usualmente treinados nos mesmos dados)
cada membro do ensemble faz uma previsão, e essas previsões são agregadas (maioria, maioria ponderada, um algoritmo de aprendizado para combinar as previsões, etc)
a mesma ideia para clusterizadores.
https://en.wikipedia.org/wiki/Consensus_clustering

Por exemplo vários k-means

Como combinar os resultados (exemplo):

por exemplo, para cada par de dados podemos medir a proporção de vezes que eles estão num mesmo cluster - uma nova representação relacional entre os dados
ou criar um grafo bipartido de dados e clusters (dos vários clusterizadores) e particionar este grafo