Vantagens e desvantagens do k-means

K-means é útil e eficiente em muitos contextos de machine learning, mas tem com alguns pontos fracos distintos.

Vantagens do k-means

Relativamente simples de implementar.

Escalonamento para grandes conjuntos de dados.

Sempre converge.

Permite a inicialização com estado salvo das posições dos centroides.

Se adapta perfeitamente a novos exemplos.

Pode ser generalizado para clusters de diferentes formas e tamanhos, como aglomerados elípticos.

Generalização de k-means

A implementação direta de k-means pode ter dificuldades com agrupamentos de densidades e tamanhos diferentes. O lado esquerdo da Figura 1 mostra os clusters que devemos ver, enquanto o lado direito mostra os clusters propostos por k-means.

Figura 1: exemplo de k-means não generalizado.

Para um melhor desempenho em clusters desequilibrados, como os mostrados na Figura 1, é possível generalizar, ou seja, adaptar, k-means. A Figura 2 mostra três conjuntos de dados agrupados com duas generalizações diferentes. O primeiro conjunto de dados mostra k-means sem generalização, enquanto o segundo e o terceiro permitem que os clusters variam em largura.

Figura 2: clustering k-means com e sem generalização.

Este curso não aborda como generalizar k-means, mas os interessados deverá ver Clustering – Mistura gaussiana k-means de ML de Carlos Guestrin da Universidade Carnegie Mellon.

Desvantagens do k-means

\(k\) deve ser escolhido manualmente.

Os resultados dependem dos valores iniciais.

Para valores baixos de \(k\), reduza essa dependência executando k-means vários vezes com valores iniciais diferentes e escolher o melhor resultado. Como \(k\) aumenta, você precisa de propagação k-means para escolher centroides Para uma discussão completa sobre propagação de k-means, consulte "Uma comparação Estudo de métodos de inicialização eficientes para o clustering K-means Algorithm", por M. Emre Celebi, Hassan A. Kingravi e Patricio A. Vela

Dificuldade para agrupar dados de tamanhos variados e densidades sem generalização.

Dificuldade para o clustering de outliers.

Os centroides podem ser arrastados por outliers ou os outliers podem ter seu próprio cluster em vez de serem ignoradas. Considere remover ou cortar os outliers antes clustering de dados.

Dificuldade de escalonamento com o número de dimensões.

À medida que o número de dimensões nos dados aumenta, uma similaridade com base na distância medida converge para um valor constante entre quaisquer exemplos fornecidos. Reduzir dimensionalidade usando PCA com os dados dos atributos ou usando clustering espectral para modificar o clustering algoritmo.

Maldição de dimensionalidade e clustering espectral

Nestes três gráficos, observe como, conforme as dimensões aumentam, o desvio padrão na distância entre os exemplos diminui em relação à distância média entre exemplos. Isso ou convergência significa que k-means se torna menos eficaz na distinção entre à medida que a dimensionalidade dos dados aumenta. Isso é chamado de a maldição da dimensionalidade.

Figura 3: uma demonstração da maldição da dimensionalidade. Cada gráfico mostra as distâncias entre 200 pontos aleatórios em pares.

É possível evitar essa queda no desempenho com o clustering espectral, adiciona etapas de pré-clustering ao algoritmo. Para executar dados espectrais clustering:

1. Usar PCA para reduzir a dimensionalidade dos dados de atributos.
2. Projete todos os pontos de dados no subespaço de dimensão inferior.
3. Agrupe os dados nesse subespaço usando o algoritmo de sua escolha.

Consulte Tutorial sobre espectral Clustering (em inglês) por Ulrike von Luxburg para mais informações sobre espectral clustering de dados.

Termos-chave:

• clustering espectral