Por que começos diferentes dão grupos diferentes?

Lloyd diminui de modo monótono a função objetivo, mas só até um mínimo local de um problema não convexo. Centróides iniciais diferentes caem em «armadilhas» diferentes — por isso costuma-se fazer vários recomeços ou uma inicialização mais esperta (k-means++).

O particionamento globalmente ótimo é garantido?

Não: mesmo no plano a otimização global exata das k-médias é NP-difícil no pior caso. As iterações de Lloyd são um método heurístico rápido, que em nuvens «lisas» em geral funciona bem.

E se um grupo esvaziar?

No código de produção costuma-se reinicializar o centróide (por exemplo, no ponto mais longe). Aqui o grupo vazio conserva o centróide antigo, para não perder o rótulo no meio do passo; na atribuição seguinte a composição pode mudar.

Agrupamento k-médias

Pontos no plano, número de grupos k e centróides iniciais. Passo de Lloyd: atribuição ao centro mais próximo e deslocamento do centróide ao baricentro. A demonstração é uma mistura de gaussianas; soma dos quadrados intra-grupo.

Sobre o modelo

O agrupamento k-médias divide um conjunto finito de pontos em k grupos, minimizando a soma dos quadrados das distâncias euclidianas aos centróides. Aqui entra o algoritmo clássico de Lloyd: com k centros fixos, alternam-se o passo de atribuição (cada ponto → centróide mais próximo, células de Voronoi) e o passo de atualização (centróide ← média dos seus pontos). Num passo completo a soma dos quadrados intra-grupo não cresce: a atribuição é ótima com centros fixos, a média é o ótimo com rótulos fixos. Os centróides iniciais são k pontos distintos dos dados, escolhidos por embaralhamento com semente controlada; a demonstração gera uma mistura de gaussianas. Um grupo vazio conserva o centróide anterior — recurso didático, sem a lógica completa do k-means++.

Para quem: Análise de dados: aprendizado não supervisionado, diagrama de Voronoi, minimização alternada.

Conceitos-chave

agrupamento k-médias
algoritmo de Lloyd
centróide
célula de Voronoi
soma dos quadrados intra-grupo
mistura de gaussianas
mínimo local
grupo vazio

Como funciona

Algoritmo de Lloyd: passo de atribuição — cada ponto ao mais próximo dos k centróides; passo de atualização — o centróide vai ao baricentro dos seus pontos. O começo são k pontos aleatórios dos dados; a demonstração é uma mistura de gaussianas. A soma dos quadrados intra-grupo não cresce num passo completo.

Perguntas frequentes

Por que começos diferentes dão grupos diferentes?: Lloyd diminui de modo monótono a função objetivo, mas só até um mínimo local de um problema não convexo. Centróides iniciais diferentes caem em «armadilhas» diferentes — por isso costuma-se fazer vários recomeços ou uma inicialização mais esperta (k-means++).
O particionamento globalmente ótimo é garantido?: Não: mesmo no plano a otimização global exata das k-médias é NP-difícil no pior caso. As iterações de Lloyd são um método heurístico rápido, que em nuvens «lisas» em geral funciona bem.
E se um grupo esvaziar?: No código de produção costuma-se reinicializar o centróide (por exemplo, no ponto mais longe). Aqui o grupo vazio conserva o centróide antigo, para não perder o rótulo no meio do passo; na atribuição seguinte a composição pode mudar.

Continue com temas próximos desta categoria — ou todos os 85 em «Visualização matemática».

Toda a categoria →

NovoEscola

Regressão linear: MQO, ridge, lasso e R²

Abrir o simulador

Pontos no plano e o modelo y = β₀ + β₁x: MQO usual, ridge (penalização L₂ na inclinação) ou lasso (penalização L₁). O deslocamento Δy no ponto de maior |x| é um valor atípico de grande alavancagem; comparam-se SSE e R².

NovoEscola

Envoltória convexa

Abrir o simulador

Pontos no plano: varredura de Graham com animação passo a passo ou QuickHull; comparação dos conjuntos de vértices.

NovoEscola

DBSCAN

Abrir o simulador

Raio ε e limiar minPts: núcleo, fronteira e ruído. Grupos de forma qualquer, sem k prefixado; em torno dos núcleos pode-se mostrar circunferências de raio ε.

NovoEscola

Triangulação de Delaunay e diagrama de Voronoi

Abrir o simulador

Triangulação de Bowyer–Watson e diagrama de Voronoi dual: o clique acrescenta sítios, o arraste os desloca.

NovoEscola

Mínimos quadrados

Abrir o simulador

Pontos ruidosos e a reta y = ax + b que minimiza a soma dos quadrados dos resíduos verticais. Mude a inclinação, o intercepto e o ruído — aparecem os resíduos e a soma dos quadrados dos erros.

NovoUniversidade / pesquisa

Filtro adaptativo LMS

Abrir o simulador

Canal primário p = s + v, em que v é um FIR desconhecido do ruído branco de referência x[n]. FIR adaptativo de L taps com LMS ou NLMS: o erro e = p − wᵀx tende ao sinal útil s.

Agrupamento k-médias

Sobre o modelo

Como funciona

Perguntas frequentes

Simuladores relacionados

Regressão linear: MQO, ridge, lasso e R²

Envoltória convexa

DBSCAN

Triangulação de Delaunay e diagrama de Voronoi

Mínimos quadrados

Filtro adaptativo LMS

Agrupamento k-médias

Sobre o modelo

Como funciona

Perguntas frequentes