O que é agrupamento k-means?

É um dos métodos de agrupamento mais populares usados em aprendizado de máquina. Diferentemente 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 uma 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 opera 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 Categories. 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 requer 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 cluster e reatribui o centro do cluster, 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 aos 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. Todos os pontos de dados em um cluster devem ser semelhantes.
   
2. Os clusters devem ser distintos uns dos outros.

Essas propriedades são obtidas minimizando 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 dos clusters medindo a variação total dentro de cada cluster.

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 dos clusters, 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 interclusters e a distância máxima intracluster. Clusters com uma alta distância interclusters 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 obter 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 inconsistentes. 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.⁵

O k-means++ é um algoritmo k-means que otimiza a seleção do(s) centroide(s) do cluster inicial. Desenvolvido pelos pesquisadores Arthur e Vassilvitskii, o k-means++ melhora a qualidade da atribuição final dos clusters.⁶

O primeiro passo para a inicialização utilizando 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.

Idealmente, 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 clusters dentro de um algoritmo de agrupamento 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 cluster, que é plotada em relação ao número de clusters.⁷

A primeira etapa do método de cotovelo é calcular o WCSS para cada cluster (k). Em seguida, o valor de WCSS é plotado ao longo do eixo y, e o número de clusters é plotado no eixo x. À medida que o número de clusters aumenta, os pontos do gráfico devem formar um padrão consistente. Desse padrão, resulta um intervalo para o número ideal de clusters.⁸ Ao decidir sobre o número de clusters, considere os custos computacionais. Quanto maior o número de clusters, mais poder de processamento é 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 que têm poucas dimensões, são numéricos e podem ser facilmente fracionados.

Os pesquisadores integraram o agrupamento k-means a métodos de deep learning, como CNNs e RNNs, para melhorar o desempenho de várias tarefas de aprendizado de máquina, como computer vision, NLP e muitos outros domínios. Veja a seguir uma lista de aplicações comuns de agrupamento 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 da Watson Discover para criar um classificador de documentos.

Segmentação de imagens: uma técnica de computer vision que divide uma imagem digital em conjuntos distintos de pixels. Essa pesquisa mergulha em como os modelos k-means são usados para ajudar a identificar bondaries 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 k-means são usadas para criar recomendações de produtos para empresas de comércio eletrônico.¹¹

Para ter uma experiência prática de aprendizado, consulte o tutorial que explica os fundamentos da execução do agrupamento cluster k-means no Python usando o IBM Watson Studio no watsonx.ai.

Este tutorial utiliza um módulo da biblioteca scikit-learn (sklearn) que executa o agrupamento k-means. O módulo inclui técnicas de otimização integradas que são 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 disponíveisk-means++andrandom. Também inclui 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:

importar pandas como pd 
 importar sklearn
 importar matplotlib.pyplot as plt
 importar Seaborn as sns
 importar numpy

 a partir de sklearn.cluster importar KMeans
 de sklearn.datasets importar make_blobs de sklearn.decomposition importar PCA
 de sklearn.preprocessing importar StandardScaler

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

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

Rápido: o agrupamento k-means é 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 clusters 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 escalá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, ele é mais escalável e adequado para grandes conjuntos de dados em comparação com outros métodos.

Alguns desafios comuns associados ao agrupamento k-means são:

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 tem um desempenho ruim quando o conjunto de dados contém muitas variações ou é altamente dimensional. Dados que não se alinham a certas suposições do conjunto de dados podem fazer com que o k-means produza clusters de baixa qualidade.¹³ Por exemplo, clusters de tamanhos desiguais podem distorcer os centroides em direção a clusters maiores, levando a viés e classificação incorreta entre clusters menores. Para resolver esse problema, o k-means pode ser generalizado utilizando modelos probabilísticos como o nó de mistura gaussiana.

Impacto significativo do valor discrepante: os valores discrepantes têm um impacto significativo nos resultados do agrupamento k-means. Os diferentes 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 torna propenso a sobreajuste incluir esses valores discrepantes.