k-means

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
NoFonti.svg
Este artigo ou se(c)ção cita uma ou mais fontes fiáveis e independentes, mas ela(s) não cobre(m) todo o texto (desde novembro de 2012).
Por favor, melhore este artigo providenciando mais fontes fiáveis e independentes e inserindo-as em notas de rodapé ou no corpo do texto, conforme o livro de estilo.
Encontre fontes: Googlenotícias, livros, acadêmicoYahoo!Bing. Veja como referenciar e citar as fontes.

Em mineração de dados, agrupamento k-means é um método de Clustering que objetiva particionar n observaçoes dentre k clusters onde cada observação pertence ao cluster 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[editar | editar código-fonte]

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]

Referências[editar | editar código-fonte]

  1. MacQueen, J. B. (1967). "Some Methods for classification and Analysis of Multivariate Observations" in Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability. {{{booktitle}}} 1: 281–297, University of California Press. Página visitada em 2012-11-14. 
  2. Steinhaus, H. (1957). "Sur la division des corps matériels en parties" (em Francês). Bull. Acad. Polon. Sci. 4 (12): 801–804.
  3. 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". IEEE Transactions on Information Theory 28 (2): 129–137. DOI:10.1109/TIT.1982.1056489.
  4. E.W. Forgy. (1965). "Cluster analysis of multivariate data: efficiency versus interpretability of classifications". Biometrics 21: 768-769.
  5. J.A. Hartigan. Clustering algorithms. [S.l.]: John Wiley & Sons, Inc., 1975.
Ícone de esboço Este artigo sobre Informática é um esboço. Você pode ajudar a Wikipédia expandindo-o.