Vantagens da k-means
Relativamente simples de implementar.
Escalona para grandes conjuntos de dados.
Garante a convergência.
Faça uma inicialização a quente das posições de centroides.
Adapta-se facilmente a novos exemplos.
Generaliza a clusters de diferentes formas e tamanhos, como clusters elípticos.
Generalização da k-means
O que acontece quando os clusters têm diferentes densidades e tamanhos? Veja a Figura 1. Compare os clusters intuitivos no lado esquerdo com os clusters encontrados por k-means no lado direito. A comparação mostra como a k-means pode encontrar determinados conjuntos de dados.
Para agrupar clusters desequilibrados naturalmente, como os mostrados na Figura 1, é possível adaptar (generalizar) k-means. Na Figura 2, as linhas mostram os limites de clusters após a generalização de k-means como:
- Gráfico com esquerda: sem generalização, resultando em um limite de cluster não intuitivo
- Gráfico de centro: permita larguras de cluster diferentes, resultando em clusters mais intuitivos de diferentes tamanhos.
- Gráfico direito: além de diferentes larguras de cluster, permita larguras diferentes por dimensão, resultando em elípticos em vez de clusters esféricos, melhorando o resultado.
Embora este curso não se aprofunde em como generalizar k-means, lembre-se de que a facilidade de modificação de k-means é outro motivo pelo qual ele é eficiente. Para informações sobre como generalizar k-means, consulte Clustering: K-means modelos gaussianos gaussianos de Carlos Guestrin, da Carnegie Mellon University.
Desvantagens da k-means
Escolha \(k\) manualmente.
Use o gráfico "Perda vs. clusters" para encontrar o ideal (k), conforme discutido em Interpretar resultados.
Como depender de valores iniciais.
Para um \(k\)baixo, é possível reduzir essa dependência executando k-means várias vezes com diferentes valores iniciais e escolhendo o melhor resultado. À medida que \(k\) aumenta, você precisa de versões avançadas de k-means para escolher valores melhores dos centroides iniciais (chamados de propagação de k-means). Para ver uma discussão completa sobre propagação de k-means, consulte Um estudo comparativo de métodos de inicialização eficientes para o algoritmo de clustering k-means de M. Emre Celebi, Hassan A. Kingravi, Patricio A. Vela.
Como agrupar dados de diferentes tamanhos e densidades.
A k-means tem problemas para agrupar dados em que os clusters têm tamanhos e densidades variados. Para agrupar esses dados, você precisa generalizar k-means, conforme descrito na seção Vantagens.
Outliers de clustering.
Os centroides podem ser arrastados por outliers, ou os outliers podem obter seu próprio cluster em vez de serem ignorados. Considere remover ou cortar outliers antes do clustering.
Escalonamento com número de dimensões.
Conforme o número de dimensões aumenta, uma medida de semelhança baseada em distância converge para um valor constante entre qualquer exemplo. Reduza a dimensionalidade usando PCA nos dados do recurso ou usando "clustering espectral" para modificar o algoritmo de clustering, como explicado abaixo.
Curse de dimensionalidade e clustering espectral
Esses gráficos mostram como a proporção do desvio padrão em relação à média da distância entre exemplos diminui à medida que o número de dimensões aumenta. Essa convergência significa que k-means se torna menos eficaz para distinguir entre exemplos. Essa consequência negativa dos dados de alta dimensão é chamada de palavrões de dimensionalidade.
O clustering espectral evita a maldição da dimensionalidade adicionando uma etapa de pré-clustering ao seu algoritmo:
- Reduza a dimensionalidade dos dados do recurso usando o PCA.
- Projete todos os pontos de dados no subespaço de menor dimensão.
- Agrupe os dados nesse subespaço usando o algoritmo escolhido.
Portanto, o clustering espectral não é um algoritmo de clustering separado, mas uma etapa de pré-clustering que pode ser usada com qualquer algoritmo de clustering. Os detalhes do clustering espectral são complicados. Consulte A Tutorial on Spectral Clustering (link em inglês) de Ulrike von Luxburg.