caracterizar os dados como membros de grupos.
os grupos devem “fazer sentido”
em alguns casos “representantes” dos grupos passam a ser “arquetipos”/prototipos dos dados.
em KDD: entender os “representantes dos grupos”
em processos automáticos: pertencer a um grupo é uma forma de classificar o dado e essa classe é usada nos processamentos seguintes
nas próximas aulas falaremos apenas de dados vetoriais (pontos no espaço).
completo vs parcial: todos os dados pertencerão a um (ou mais grupos) ou apenas parte dos dados serão agrupados. Desta forma dados anômalos não influenciam na definição dos grupos.
particionamento vs intersecção (overlapping): os dados são membros de apenas um grupo ou podem ser membros simultaneamente de mais de um grupo
um nivel vs multi-nivel/hierarquico: os grupos estão todos no mesmo nível ou podem conter outros grupos.
baseado em centroides: descobrir o “centro” de cada grupo. Baseado em distancia - cada ponto pertence ao grupo (grupos) cujo centro é mais proximo(s). https://www.geeksforgeeks.org/ml-k-means-algorithm/
baseado em densidade: grupos sao regiões de alta densidade de pontos separados por regiões de baixa densidade https://hpccsystems.com/blog/DBSCAN
baseado em grids - regiões retangulares com alta densidade https://www.researchgate.net/publication/267565989_Automating_Discovery_of_Innovative_Design_Principles_through_Optimization/figures?lo=1
baseado em distribuições probabilísticas: modela-se os dados como sendo gerado por diferentes distribuições probabilísticas (cada uma um grupo). (mas isso também é baseado em centroides e distancias) https://fallfordata.com/soft-clustering-with-gaussian-mixture-models-gmm/
outras
Algoritmo iterativo: dividir os dados em k grupos (vc precisa definir o k)
criar os centros dos grupos aleatoriamente (inicialização)
atribuir cada dado ao grupo cujo centro esta mais próximo
se não houve mudança de atribuição desde a volta passada, terminar
recomputar o centro do grupo como sendo a média dos dados que pertencem ao grupo
voltar ao item 2
http://www.onmyphd.com/?p=k-means.clustering
pode-se mostrar que o algoritmo k-means a cada passo encontra uma melhor solução para o problema de encontrar centros que minimizam o quadrado da distancia entre o centro e os dados daquele grupo
como um algoritmo iterativo ele pode ficar preso em soluções “ruins” mas que nao podem ser “localmente” melhoradas (minimo local)
mínimos locais dependem da inicialização
várias inicializações: centros aleatórios, partição aleatória, centros como dados,
kmeans++ (primeiro centro aleatório, segundo dados como centro com probabilidade proporcional a distancia, etc).
k-means é um algoritmo completo (todos os pontos são classificados), de particionamento (pontos só pertencem a um grupo) e um nível (não há subgrupos dentro de super-grupos
os grupos em k-means são convexos (sem “entradas”), talvez estendendo-se ao infinito em alguma direção (mas os dados não estão no infinito)
kmeans em R http://www.rdocumentation.org/packages/stats/functions/kmeans
KMeans em sklearn https://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html
deve-se fazer uma padronização dos atributos numéricos que não tem a mesma medida ou o “mesmo sentido”
deve-se converter os atributos categóricos em múltiplos atributos 0/1 seguindo o “one-hot enconding”
há algum debate se deve-se padronizar os atributos 0/1 derivados da conversão dos atributos categóricos originais
http://stats.stackexchange.com/questions/133656/how-to-understand-the-drawbacks-of-k-means
kmeans acha grupos “convexos” justificativa para clusterização por densidade/proximidade
kmeans não se dá bem com grupos de tamanho e densidade muito diferentes
kmeans acaba agrupando dados mesmo que eles não tenham estrutura de grupos
para muitos grupos, há uma maior probabilidade de minimos locais
os grupos do kmeans tem “o mesmo raio” http://www.onmyphd.com/?p=k-means.clustering terceiro exemplo.
próxima aula - métricas de qualidade dos grupos - teste para vários k e escolha o melhor.
k-means original
Gerar os centros iniciais, e
atribuir cada dado ao grupo cujo centro esta mais próximo
recomputar o centro do grupo como sendo a média dos dados que pertencem ao grupo
Mudanças no passo 2 acima:
k-medianas: computa-se o centro como sendo a mediana dos dado do grupo.
k-medianas é menos sensivel a outliers: pontos anomalos não puxam o centro para eles.
implementação em R http://www.rdocumentation.org/packages/flexclust/functions/kcca
implementação em python https://gist.github.com/mblondel/1451300 ou https://pyclustering.github.io/docs/0.9.1/html/df/d68/classpyclustering_1_1cluster_1_1kmedians_1_1kmedians.html
K-medoids - também chamado de PAM (partition around mediods)
o centro é o dado do grupo cuja soma das distancias aos elementos do grupo é a menor
k-medoids é o unico algoritmo da familia do k-means que funciona para dados relacionais (grafos) - os centros não são “pontos novos” do espaço mas sim um dos dados “velhos”.
implementação em R http://www.rdocumentation.org/packages/cluster/functions/pam
sklearn-extra https://scikit-learn-extra.readthedocs.io/en/stable/generated/sklearn_extra.cluster.KMedoids.html