O que é agrupamento k-means?

É um dos métodos de agrupamento mais populares utilizados em aprendizado de máquina. Ao contrário do aprendizado supervisionado, os dados de treinamento que esse algoritmo utiliza não são rotulados, o que significa que os pontos de dados não têm estrutura de classificação definida.

Embora existam vários tipos de algoritmos de agrupamento, incluindo exclusivos, sobrepostos, hierárquicos e probabilísticos, o algoritmo de agrupamento k-means é um exemplo de um método de agrupamento exclusivo ou "hard".Essa forma de agrupamento estipula que um ponto de dados pode existir em apenas um cluster.Esse tipo de análise de cluster é comumente utilizado em ciência de dados para segmentação de mercado, agrupamento de documentos, segmentação de imagens e compactação de imagens.O algoritmo k-means é um método amplamente utilizado na análise de clusters porque é eficiente, eficaz e simples.

O K-means é um algoritmo de agrupamento baseado em centroides iterativo que divide um conjunto de dados em grupos semelhantes com base na distância entre seus centroides. O centroide, ou centro do cluster, é a média ou a mediana de todos os pontos dentro do cluster, dependendo das características dos dados.

O agrupamento K-means é um processo iterativo para minimizar a soma das distâncias entre os pontos de dados e seus centros de agrupamento.

O algoritmo de agrupamento k-means funciona categorizando pontos de dados em agrupamentos utilizando uma medida de distância matemática, geralmente euclidiana, do centro do agrupamento. O objetivo é minimizar a soma das distâncias entre os pontos de dados e seus clusters atribuídos. Os pontos de dados mais próximos de um centroide são agrupados nas mesmas categorias. Um valor de k mais alto, ou o número de clusters, significa clusters menores com mais detalhes, enquanto um valor de k mais baixo resulta em clusters maiores com menos detalhes.

O algoritmo convencional de agrupamento k-means exige algumas etapas. A primeira etapa é inicializar centroides k onde k é igual ao número de clusters escolhidos para um conjunto de dados específico. Essa abordagem utiliza métodos de seleção aleatória ou de amostragem inicial de centroides.

A próxima etapa inclui um processo iterativo de duas etapas baseado no algoritmo de aprendizado de máquina de maximização de expectativas. ¹ A etapa de expectativa atribui cada ponto de dados ao seu centroide mais próximo com base na distância (novamente, geralmente euclidiana). A etapa de maximização calcula a média de todos os pontos para cada agrupamento e reatribui o centro do agrupamento, ou centroide. Esse processo se repete até que as posições dos centroides tenham alcançado convergência ou o número máximo de iterações tenha sido atingido.

O agrupamento K-means é simples, mas sensível às condições iniciais e a valores discrepantes. É importante otimizar a inicialização do centroide e o número de clusters k para obter os clusters mais significativos. Há várias maneiras de avaliar e otimizar os componentes de agrupamento do algoritmo utilizando métricas de avaliação e métodos de amostragem de centroide inicial.

Os clusters de qualidade contêm pelo menos duas propriedades:

1. .
2. Todos os pontos de dados de um cluster devem ser semelhantes.
   
3. Os clusters devem ser distintos uns dos outros.

Essas propriedades são obtidas minimizando-se a distância intracluster e maximizando a distância entre clusters de todos os pontos de dados em um conjunto de dados. Em outras palavras, quanto mais compacto e isolado for um cluster de outros clusters, melhor. O objetivo do algoritmo de agrupamento k-means é minimizar a soma dos erros quadrados (SSE).² O cálculo do SSE da distância euclidiana quadrada de cada ponto até o centroide mais próximo avalia a qualidade das atribuições do agrupamento medindo a variação total dentro de cada agrupamento.

As métricas de avaliação de cluster verificam a qualidade e apresentam diversas perspectivas para analisar os resultados do cluster. Isso ajuda a selecionar o número ideal de clusters e a inicialização do centroide. As seguintes métricas de avaliação são maneiras comuns de medir as distâncias intra e intercluster no agrupamento.

O algoritmo de agrupamento k-means tem como objetivo escolher centroides, ou centros de agrupamento, que minimizem a inércia, uma métrica de avaliação que mede o grau de agrupamento de um conjunto de dados com base em métricas de distância. A inércia é calculada medindo-se a distância entre um ponto de dados e seu centroide, elevando a distância ao quadrado e somando esses quadrados para cada ponto de dados no cluster. A soma ou o valor inercial é a distância intracluster. Quanto menor a soma, melhor, porque significa que os pontos de dados dentro do cluster são compactos ou mais semelhantes.³

A segunda propriedade é medida com o índice de Dunn. O índice de Dunn representa a relação entre a distância mínima intercluster e a distância máxima intracluster. Clusters com uma alta distância intercluster indicam melhor qualidade porque significa que os clusters são o mais diferentes possível um do outro.⁴

A otimização é importante ao utilizar k-means para ter os melhores resultados de agrupamento.

O algoritmo k-means não é determinístico devido à sua etapa de inicialização aleatória. Esse método implica que, se o algoritmo for executado duas vezes em dados idênticos, as atribuições de cluster poderão ser diferentes. Para obter resultados ideais de agrupamento, a seleção adequada dos centroides iniciais e o número ideal de agrupamentos melhoram a precisão e a velocidade do algoritmo k-means.

Cada cluster é representado por um centroide, um ponto de dados que representa o centro do cluster. K-means agrupa pontos de dados semelhantes em clusters, minimizando a distância entre os pontos de dados em um cluster com seu centroide ou valor de k-means. O objetivo principal do algoritmo k-means é minimizar as distâncias totais entre os pontos e seu centroide de cluster atribuído. O algoritmo opera iterativamente e a seleção inicial da partição pode afetar muito os clusters resultantes.

A inicialização aleatória corre o risco de produzir resultados incoerentes. Há métodos de inicialização de centroide para mitigar esses riscos. Um estudo da NUS Computing explica e compara métodos como o popular k-means++ com a inicialização aleatória.⁵

K-means++ é um algoritmo k-means que otimiza a seleção do centroide ou centroides do cluster. Desenvolvido pelos pesquisadores Arthur e Vassilvitskii, o k-means++ melhora a qualidade da atribuição final do cluster.⁶

O primeiro passo para a inicialização com o método k-means++ é escolher um centroide do conjunto de dados. Para cada centroide subsequente, calcule a distância de cada ponto de dados a partir do centro de agrupamento mais próximo. O centroide subsequente é selecionado considerando a probabilidade de que um ponto esteja a uma distância proporcional do centroide mais próximo escolhido anteriormente. O processo executa iterações até que o número escolhido de centros de cluster tenha sido inicializado.

Veja a seguir um tutorial do IBM Developer que utiliza o método k-means++ para inicialização.

Em um cenário ideal, o algoritmo k-means itera até que o número ideal de clusters seja alcançado. O número máximo de iterações é atingido quando os centroides atingem a convergência.

Um método para alcançar o número ideal de clusters é o método de ajuste. O método cotovelo é um método gráfico para encontrar o número ideal de agrupamentos dentro de um algoritmo de agrupamento de k-means. Ele mede a distância euclidiana entre cada ponto de dados e seu centro de cluster e escolhe o número de clusters com base em onde a mudança em "soma dos quadrados dentro do cluster" (WCSS) se nivela. Esse valor representa a variância total dentro de cada agrupamento, que é plotada em relação ao número de agrupamentos.⁷

A primeira etapa do método de talentos é calcular o WCSS para cada cluster (k). Em seguida, o valor de WCSS é plotado sobre o eixo de y e o número de clusters é plotado no eixo de x. À medida que o número de clusters aumentar, os pontos do gráfico devem formar um padrão uniforme. Desse padrão resulta uma faixa para o número ideal de agrupamentos.⁸ Ao decidir sobre o número de clusters, considere os custos computacionais. Quanto maior for o número de clusters, mais poder de processamento será necessário, especialmente com grandes conjuntos de dados.

Esse método não é necessariamente o melhor, especialmente para conjuntos de dados com alta dimensionalidade ou formato irregular. Outro método para escolher o número ideal de clusters é a análise de silhueta.⁹

O algoritmo de agrupamento k-means é utilizado em quase todos os domínios e setores. Geralmente é aplicado a dados de aprendizado de máquina com poucas dimensões, são numéricos e podem ser facilmente fracionados.

Os pesquisadores integraram o agrupamento k-means com métodos de deep learning, como CNNs e RNNs, para melhorar o desempenho de várias tarefas de aprendizado de máquina, como visão computacional, PLN e muitos outros domínios. Veja aqui uma lista de aplicações comuns de clustering k-means:

Segmentação de clientes: prática de dividir os clientes de uma empresa em grupos com base em características comuns que refletem semelhança. Essa estratégia possibilita que as empresas direcionem clusters ou grupos específicos de clientes para campanhas publicitárias específicas.

Classificação de documentos: um procedimento para alocar várias classes ou categorias aos documentos. Esse método é utilizado por muitas organizações para moderar o conteúdo. Confira esta documentação do Watson Discover para criar um classificador de documentos.

Segmentação de imagem: técnica de visão computacional que divide uma imagem digital em conjuntos distintos de pixels. Esta pesquisa mergulha em como os modelos k-means são utilizados para ajudar a identificar limites em imagens médicas.¹⁰

Mecanismos de recomendação: aplicações em toda a web utilizam mecanismos de recomendação. A análise de componentes principais e as técnicas de agrupamento de k-means são utilizadas para criar recomendações de produtos para empresas de comércio eletrônico.¹¹

Para uma experiência prática de aprendizado, confira o tutorial que explica os fundamentos da execução de clusters k-means em Python utilizando o IBM Watson Studio em watsonx.ai.

Este tutorial utiliza um módulo da biblioteca scikit-learn (sklearn) que executa o agrupamento k-means. O módulo contém técnicas de otimização integradas manipuladas por seus parâmetros de classe. A classe do módulo tem a seguinte aparência:

class sklearn.cluster.KMeans(n_clusters=8, *, init='k-means++', n_init='auto', max_iter=300, tol=0.0001, verbose=0, random_state=None, copy_x=True, algorithm='lloyd')12

Os parâmetros incluem o número de clusters a serem formados e o número de centroides a serem gerados (n_clusters). Há dois métodos de inicialização availablek-means++andrandom. Contém também atributos para definir o número máximo de iterações. Cada iteração começa particionando o conjunto de dados no valor do n_clustersparameter.

Estas bibliotecas são utilizadas para gerar um conjunto de dados de teste e fazer agrupamentos:

import pandas as pd 
import sklearn
import matplotlib.pyplot as plt
import seaborn as sns
import numpy

from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.decomposition import PCA
from sklearn.preprocessing import StandardScaler

Alguns benefícios comuns do agrupamento k-means em aplicativos de aprendizado de máquina:

Simples: o agrupamento K-means é simples de entender e colocar em prática. É a técnica de aprendizado de máquina não supervisionado mais popular.

Rápido: o agrupamento K-means foi projetado com uma abordagem iterativa computacionalmente simples. O algoritmo de agrupamento k-means é mais rápido que o agrupamento hierárquico, que envolve a construção de uma estrutura de agrupamentos em forma de árvore e exige o cálculo da distância em pares entre todos os pontos de dados.

Escalável: o K-means também é facilmente dimensionável para grandes conjuntos de dados e generaliza para clusters de diferentes formas e tamanhos, o que é ideal para a análise de clusters. Como o algoritmo é tão eficiente computacionalmente, é mais escalável e adequado para grandes conjuntos de dados quando comparado com outros métodos.

Alguns desafios comuns associados ao agrupamento k-means:

Dependência dos parâmetros de entrada: o agrupamento de K-means depende de parâmetros de entrada definidos corretamente. Inicializar o centroide e o número de clusters adequados é impecável para obter resultados de cluster significativos. Uma inicialização incorreta do centroide pode levar a um maior tempo de execução e atribuições de cluster de baixa qualidade. Muitas pesquisas foram feitas para melhorar o procedimento de inicialização do centroide para obter melhores resultados de agrupamento e tempo de convergência mais rápido.

Possível baixo desempenho em determinados conjuntos de dados: o K-means tem um desempenho eficaz quando o conjunto de dados contém clusters de tamanho semelhante e não há valores discrepantes ou variações de densidade notáveis. O K-means apresenta desempenho ruim quando o conjunto de dados contém muitas variações ou é altamente dimensional. Dados que não se alinham a determinadas suposições do conjunto de dados podem fazer com que o k-means produza clusters de baixa qualidade.¹³ Por exemplo, aglomerados de tamanhos desiguais podem inclinar os centroides em direção aos aglomerados maiores, levando a um viés e classificação incorreto entre os aglomerados menores. Para resolver esse problema, as médias k podem ser generalizadas com modelos probabilísticos como o Nodo de Mistura Gaussiana.

Impacto significativo do valor discrepante: os valores discrepantes têm impacto considerável nos resultados do agrupamento k-means. Os diversos agrupamentos devem estar distantes, mas não tão distantes a ponto de distorcer os pontos de dados. É importante considerar as suposições de dados antes de aplicar k-means. O K-means é especialmente sensível aos valores discrepantes, uma vez que visa determinar centroides calculando a média de valores com um cluster. Essa sensibilidade o torna propenso à inclusão desses valores discrepantes no overfitting.