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.
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
editarO 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]
Referências
editar- ↑ MacQueen, J. B. (1967). Some Methods for classification and Analysis of Multivariate Observations. Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability. 1. University of California Press. pp. 281–297. MR 0214227. Zbl 0214.46201. Consultado em 14 de novembro de 2012
- ↑ Steinhaus, H. (1957). «Sur la division des corps matériels en parties». Bull. Acad. Polon. Sci. (em francês). 4 (12): 801–804. MR 0090073. Zbl 0079.16403
- ↑ Lloyd, S. P. (1957). «Least square quantization in PCM». Bell Telephone Laboratories Paper Published in journal much later: Lloyd., S. P. (1982). «Least squares quantization in PCM» (PDF). IEEE Transactions on Information Theory. 28 (2): 129–137. doi:10.1109/TIT.1982.1056489. Consultado em 15 de abril de 2009
- ↑ E.W. Forgy (1965). «Cluster analysis of multivariate data: efficiency versus interpretability of classifications». Biometrics. 21: 768-769
- ↑ J.A. Hartigan (1975). Clustering algorithms. [S.l.]: John Wiley & Sons, Inc.
