O Agrupamento K-Means é um método de quantização vetorial, originalmente proveniente do processamento de sinais, que particiona um conjunto de observações em k agrupamentos, onde cada observação pertence ao agrupamento com a média mais próxima, conhecida como centróide do agrupamento. Isso resulta em uma partição do espaço de dados em células de Voronoi. O algoritmo é amplamente utilizado em aprendizado de máquina para tarefas como segmentação de clientes, compressão de imagens e reconhecimento de padrões, sendo uma técnica fundamental em inteligência artificial e análise de dados.
O objetivo do k-means é minimizar a soma dos quadrados dentro do agrupamento (WCSS), que é a soma das distâncias euclidianas ao quadrado entre cada ponto e seu centróide. Isso equivale a minimizar os desvios quadráticos pareados dos pontos dentro do mesmo agrupamento. No entanto, o k-means minimiza distâncias euclidianas ao quadrado, não distâncias euclidianas regulares; estas últimas exigiriam resolver o problema de Weber, mais difícil. Para a minimização da distância euclidiana, alternativas como k-medians ou k-medoids são mais apropriadas.
O problema de encontrar o agrupamento k-means ótimo é computacionalmente difícil (NP-difícil), mas algoritmos heurísticos eficientes convergem rapidamente para um ótimo local. A abordagem mais comum é o algoritmo de Lloyd, que iterativamente atribui pontos ao centróide mais próximo e então atualiza os centróides para a média dos pontos atribuídos. Esse refinamento iterativo é semelhante ao algoritmo de maximização de expectativa usado para modelos de mistura gaussiana, mas o k-means tende a encontrar agrupamentos de extensão espacial comparável, enquanto as misturas gaussianas permitem formas diferentes.
Algoritmo e Implementação
O algoritmo k-means padrão começa com um conjunto inicial de k centróides, que podem ser escolhidos aleatoriamente ou usando métodos como k-means++ para melhorar a convergência. O algoritmo repete duas etapas até a convergência: atribuição, onde cada observação é atribuída ao agrupamento com o centróide mais próximo, e atualização, onde cada centróide é recalculado como a média de todos os pontos em seu agrupamento. A convergência é tipicamente detectada quando as atribuições não mudam mais ou quando a melhoria do WCSS cai abaixo de um limiar.
Existem várias variantes, incluindo o k-means de mini-lote para grandes conjuntos de dados e o k-means esférico para dados de texto. A escolha de k é frequentemente determinada usando o método do cotovelo, análise de silhueta ou estatística de lacuna. A complexidade de tempo do algoritmo é aproximadamente O(nkd*i), onde n é o número de observações, d é a dimensionalidade e i é o número de iterações.
Relação com Outros Métodos
O k-means é um algoritmo não supervisionado, o que significa que não requer dados rotulados. Ele tem uma relação frouxa com o classificador de k-vizinhos mais próximos (k-NN), uma técnica supervisionada. Aplicar o classificador de 1-vizinho mais próximo aos centros de agrupamento obtidos pelo k-means classifica novos dados em agrupamentos existentes; isso é conhecido como classificador de centróide mais próximo ou algoritmo de Rocchio. Essa conexão destaca como o agrupamento não supervisionado pode apoiar tarefas supervisionadas.
O k-means também está relacionado aos modelos de mistura gaussiana (GMMs). Ambos usam centros de agrupamento para modelar dados, mas os GMMs permitem que os agrupamentos tenham formas e tamanhos diferentes, enquanto o k-means assume agrupamentos esféricos de variância semelhante. Consequentemente, o k-means é mais simples e rápido, mas menos flexível.
Aplicações e Limitações
O k-means é usado em muitos domínios. Em Amazon Web Services e Google Cloud, é uma ferramenta comum para analisar o comportamento do usuário e otimizar a alocação de recursos. Em visão computacional, é usado para segmentação de imagens e quantização de cores. Em marketing, segmenta clientes com base em padrões de compra. O algoritmo também é um bloco de construção para métodos mais complexos, como extração de características em aprendizado profundo e pré-processamento de dados em IA generativa.
No entanto, o k-means tem limitações. Ele requer que o número de agrupamentos k seja especificado antecipadamente, o que nem sempre é conhecido. É sensível à seleção inicial do centróide, embora o k-means++ mitigue isso. Assume que os agrupamentos são convexos e isotrópicos, o que pode não se aplicar a dados do mundo real. Valores atípicos podem distorcer os centróides, e o algoritmo pode convergir para ótimos locais. Apesar desses problemas, sua simplicidade e eficiência o tornam uma escolha popular.
Contexto Histórico e Desenvolvimento
O algoritmo k-means foi proposto pela primeira vez por Hugo Steinhaus em 1956 e posteriormente refinado por Stuart Lloyd em 1957 nos Laboratórios Bell (embora não publicado até 1982). O nome "k-means" foi cunhado por James MacQueen em 1967. Desde então, inúmeras melhorias foram desenvolvidas, incluindo o k-means++ para melhor inicialização e a variante de mini-lote para escalabilidade. O algoritmo continua sendo um pilar nos currículos de aprendizado de máquina e é implementado em bibliotecas importantes como scikit-learn e TensorFlow.