K-means

Em mineração de dados, agrupamento k-means é um método de segregar em torno de centros (centroides) diversos dados, criando o que analogamente na química chamamos de clustering que gera o efeito de particionar n observações dentre k grupos onde cada observação pertence ao grupo mais próximo da média. Isso resulta em uma divisão do espaço de dados em um Diagrama de Voronoi.

Uma partição dos dados em 3 grupos.

O problema é computacionalmente difícil (NP-difícil), no entanto, existem algoritmos heurísticos eficientes que são comumente empregados e convergem rapidamente para um local optimum. Estes são geralmente semelhantes ao algoritmo de maximização da expectativa para misturas de distribuições gaussianas através de uma abordagem de refinamento iterativo utilizado por ambos os algoritmos. Além disso, ambos usam os centros de clusters para modelar dados, no entanto, a clusterização k-means tende a encontrar clusters de extensão espacial comparáveis enquanto o mecanismo de maximização da expectativa permite ter diferentes formas.

História

O termo "k-means" foi empregado primeiramente por James MacQueen em 1967,^[1] embora a ideia remonta a Hugo Steinhaus em 1957.^[2] O "Standard algorithm" foi proposto primeiramente por Stuart Lloyd em 1957 como uma técnica para modulação por código de pulso, embora não tenha sido publicada fora dos laboratórios Bell até 1982.^[3] Em 1965, E.W.Forgy publicou essencialmente o mesmo método, é por isso que é por vezes referido também como Lloyd-Forgy.^[4] Uma versão mais eficiente foi proposta e publicada em Fortran por Hartigan e Wong, no período entre 1975 e 1979.^[5]