medidas internas - usando apenas os dados originais
medidas externas - usando informação extra sobre os dados, em particular a classe “certa” a que eles pertencem.
medidas externas fazem sentido quando se voce tem a classe de alguns dados e usa-se isso para ajustar os grupos. Se voce tem a classe de todos os dados, então use um classificador.
coesão dentro de um grupo (intra-grupo): os pontos dentro de um mesmo grupo devem estar próximos entre si.
separação dos diferentes grupos (inter-grupo) os grupos devem estar distantes entre si.
varias definições e intuições sobre o que são distancia intra cluster e distantcia inter-clusters, e como agrega-las.
DI = \frac{\min inter_{ij}}{\max intra_k}
onde {inter}_{ij} é alguma medida de distancia entre grupos i e j e {intra}_k é alguma medida de distancia dentro de um grupo k
Coesão implica em um intra pequeno e separação um inter gande, portanto valores maiores de indice de Dunn são preferíveis
Medidas {inter}_{ij}
distancia entre os centros dos grupos
menor distancia entre os pontos de i e de j
a média das distancias entre pontos de i e j
Medidas {intra}_k
soma das distancias do centro aos pontos de k
maior distancia ente dois pontos de k
média das distancias entre pontos de k
Dunn provavelmente nao funciona para clusterização por densidade https://hpccsystems.com/blog/DBSCAN
Para cada ponto i
a(i) é a distancia de i até o centro do seu cluster
b(i) é a distancia média de i até os dados do cluster mais próximo
s(i) = \frac{b(i) - a(i)}{\max[a(i),b(i)]} é a silueta do dado
a silhueta é a média dos s(i) para todos os dados
-1 \le s(i) \le 1
s(i) \approx 1 significa a(i) << b(i) - portanto silhuetas altas são preferiveis
Há mutas outras medidas internas de qualidade da clusterização,
Os criterios que se baseiam em uma visão que a distancia intra deve ser pequena e a inter grande são criterios pensados para o k-means onde os grupos são convexos, e isso nao é necessariamente verdade para clusterização pro densidade
Outras métricas:
sklearn: https://scikit-learn.org/stable/modules/classes.html#module-sklearn.metrics.cluster
Se os (ou alguns dos) dados clusterizados pertencem a classes já conhecidas, mas não usadas na clusterização, então essa informação pode ser usada para avaliar a qualidade da clusterização
um criterio é a concordancia, ou seja os grupos devem corresponder as classes externas
um criterio é pureza ou seja cada grupo deve conter dados de apenas uma classe externa. Note que pode haver mais grupos/cluster do que classes, mas cada grupo deve ser puro em relação a uma classe
A maioria dos indices externos se baseaim em 4 conjuntos:
SS (same-same) os pares de dados que pertencem ao mesmo cluster (clusterização) e a mesma classe (informação externa/verdade)
SD (same-different) os pares que pertencem a um mesmo cluster mas a classes diferentes
DS cluster diferentes mas mesma classe
DD cluster e classes diferentes
para concordancia, SS e DD são bons. Para pureza SS, DS e DD são bons.
Indice Rand = \frac{|SS| + |DD|}{|SS|+|SD|+|DS|+|DD|}
Indice de Jaccard = \frac{|SS|}{|SS|+|SD|+|DS|}
Indice de Fowlkes e Mallows (entre 0 e 1)
Hubert normalizado (entre -1 e 1)
Rand corrigido (entre -1 e 1 e 0 signfica que as concordancias são devido ao acaso).
Mutual information (Normalized MF e Adjusted MF) https://scikit-learn.org/stable/modules/clustering.html 2.3.10.2
Métricas externas servem para comparar 2 clusterizacoes diferentes (se uma delas é a verdade entao é uma metrica externa, ou as 2 podem ser diferentes clusterizacoes).
em R pacote fpc https://rdrr.io/cran/fpc/man/cluster.stats.html
a ideia é usar uma metrica (interna ou externa) e variar o k até achar um maximo (ou mínimo).
uma medida que é usada é a soma das distancias quadadas dos pontos ate o centro do cluster deles.
infelizmente isso é mais teórico que prático
algumas metricas decrescem (ou crescem) sistematicamente como o k e ai voce deve procurar uma descontinuidade na curva geral https://www.significancemagazine.com/culture/69-the-joy-of-clustering
usando varias metricas https://statsandr.com/blog/clustering-analysis-k-means-and-hierarchical-clustering-by-hand-and-in-r/
Função kmeansrun http://www.rdocumentation.org/packages/fpc/functions/kmeansruns em R a busca acima, mas para apenas 2 metricas silhueta/asw e Calinski-Harabasz
2 truques para big data:
rode o k-means numa amostra (pequena) dos dados. Isto gera os centros, classifique os dados restantes pela proximidade dos centros. Se a amostra é grande o suficiente, os centros das amostras não é muito diferente do centro de todos os dados
batch vs online
para todos os dados:
compute a atribuiçao
para todos os dados:
compute o centroVersão online:
para todos os dados
compute a atribuicao
ande com o centro um pouquinho em direcao ao dadobig data: escolha os dados aleatoriamente - stocastic gradient descent
stream learning: use o dado assim que ele chega e nunca mais - online learning
https://en.wikipedia.org/wiki/Fuzzy_clustering
cada ponto pertence a um grupo com “intensidade” proporcional ao inverso de uma potencia da distancia (normalizado, para que as intensidades somem 1 no final)
fuzzy c-means tem um parametro extra (m fuzzyfication) relacionado com a potencia da distancia. m grande torna os intensidade de cada ponto mais ou menos parecida, e portanto os grupos tem grande interseção.
m=1 faz a intensidade ser 1 para o grupo mais perto e 0 para os outros, portanto o k-means tradicional.
m=2 é normalmente usado.
o centro é a media ponderada (pela intensidade) dos pontos.
Nas variações anteriores, a noção de distancia se mantem. E se tivermos uma definição de distancia que depende do grupo (ou melhor dos dados do grupo)?
distancia de Mahalanobis - distancia dividido pelo desvio padrao dos dados naquela direção (aproximadamente) ver figura em http://www.ece.stonybrook.edu/~pmilder/memocode14/
isto resolveria o problema de clusters “mais compactos” - figura 2 em http://stats.stackexchange.com/questions/133656/how-to-understand-the-drawbacks-of-k-means
GMM (Gaussian MIxture Models) além de incluir a noção de distancia de Mahalanobis, inclui também a noção de graus de pertencimento.
cada grupo é modelado como uma gaussiana (mutlidimensional). O centro é a média da gaussiana
a matriz de covariança é o equivalente para varias dimensões do desvio padrao da gaussiana.
Gaussianas em 2D são elispoides onde a matriz de covariancia indica quao não esferico o elispoide e a direção do raio maior.
cada ponto tem um grau de pertencer a cada grupo dado pela probabilidade (normalizada) do ponto na gaussiana correspondente.
o novo centro e a nova matriz de covariancia são calculados pela media ponderada (pelo grau) de todos os pontos.
ver figura em http://pypr.sourceforge.net/mog.html
Varios pacotes implementam variações do GMM. O mais simples é o Mclust do pacote mclust http://www.rdocumentation.org/packages/mclust/functions/Mclust
Em python https://scikit-learn.org/stable/modules/generated/sklearn.mixture.GaussianMixture.html
Implementações do GMM permitem restrições no formato das gaussianas
sem restriçoes (full)
todas gaussianas no mesmo formato (tied) - mesma matriz de covariancia
todas sao esfericas (spherical) - mesmo raio
mesmo tamanho (volume) no Mclust
gaussianas nao estao rodadas (cada atributo é independente) (diag - a matriz de covariancia é diagonal)
Determina o k automaticamente - voce define o k maximo e o algoritmo define internamente o k - o algoritmo junta gaussianas quando vale a pena.
Todos esses algoritmos se baseiam num procedimento geral de otimização (minimização ou maximização) chamado Expectation Maximization
encontre os valores de \theta que minimizam ou maximizam algo
https://en.wikipedia.org/wiki/Expectation%E2%80%93maximization_algorithm