Vantagens e desvantagens do k-means

O K-means é útil e eficiente em muitos contextos de aprendizado de máquina, mas tem alguns pontos fracos distintos.

Vantagens do k-means

É relativamente simples de implementar.

Escala para grandes conjuntos de dados.

Sempre converge.

Permite o aquecimento das posições dos centroides.

Se adapta facilmente a novos exemplos.

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

Como generalizar k-means

Uma implementação simples de k-means pode ter problemas com clusters de densidades e tamanhos diferentes. O lado esquerdo da Figura 1 mostra os clusters que esperamos encontrar, enquanto o lado direito mostra os clusters propostos pelo k-means.

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

Para melhorar a performance em clusters desequilibrados, como os mostrados na Figura 1, é possível generalizar, ou seja, adaptar, o k-means. A Figura 2 mostra três conjuntos de dados diferentes 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 variem na largura.

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

Este curso não aborda como generalizar o k-means, mas os interessados devem consultar Clustering – k-means Gaussian mixture models de Carlos Guestrin, da Carnegie Mellon University.

Desvantagens do k-means

$k$ precisa ser escolhido manualmente.

Os resultados dependem dos valores iniciais.

Para $k$baixo, é possível reduzir essa dependência executando o k-means várias vezes com valores iniciais diferentes e escolhendo o melhor resultado. À medida que $k$ aumenta, é necessário gerar pontos de partida de k-means para escolher melhores centroides iniciais. Para uma discussão completa sobre a geração de pontos de partida de k-means, consulte "A Comparative Study of Efficient Initialization Methods for the K-means Clustering Algorithm", de M. Emre Celebi, Hassan A. Kingravi e Patricio A. Vela.

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

Dificuldade em agrupar valores discrepantes.

Os centroides podem ser arrastados por valores discrepantes, ou valores discrepantes podem ter um cluster próprio, em vez de serem ignorados. Considere remover ou cortar pontos fora da curva antes de agrupar.

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

À medida que o número de dimensões nos dados aumenta, uma medida de similaridade baseada em distância converge para um valor constante entre os exemplos fornecidos. Reduza a dimensionalidade usando PCA nos dados de recursos ou usando clustering espectral para modificar o algoritmo de clustering.

Maldição da dimensionalidade e clusteramento espectral

Observe como, à medida que as dimensões aumentam, a variação padrão na distância entre os exemplos diminui em relação à distância média entre os exemplos. Essa convergência significa que o k-means se torna menos eficaz para distinguir entre exemplos à medida que a dimensionalidade dos dados aumenta. Isso é chamado de maldição da dimensionalidade.

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

É possível evitar essa diminuição no desempenho com o agrupamento espectral, que adiciona etapas de pré-agrupamento ao algoritmo. Para realizar a clusterização espectral:

1. Reduza a dimensionalidade dos dados de atributos usando o PCA.
2. Projete todos os pontos de dados no subespaço de menor dimensão.
3. Agrupe os dados nesse subespaço usando o algoritmo escolhido.

Consulte A Tutorial on Spectral Clustering (em inglês) de Ulrike von Luxburg para mais informações sobre o agrupamento espectral.

Termos-chave:

• Clustering espectral