k means algorithm

algoritmo k-means

Esta é uma implementação Python do algoritmo k-means, incluindo método de cotovelo e método de silhueta para selecionar K ideal

K-means é um algoritmo de cluster popular usado para particionar dados em K clusters. Ele funciona atribuindo iterativamente cada ponto de dados ao centróide do cluster mais próximo e, em seguida, recalculando o centróide de cada cluster com base nos pontos de dados atribuídos a ele. O processo é repetido até a convergência.

Algoritmo

• Selecione aleatoriamente K centróides iniciais do cluster a partir dos pontos de dados.
• Atribua cada ponto de dados ao centróide do cluster mais próximo.
• Recalcule o centróide de cada cluster com base nos pontos de dados atribuídos a ele.
• Repita as etapas 2 a 3 até a convergência (ou seja, quando as atribuições do cluster não mudarem mais).

Função Objetivo

O objetivo do k-means é minimizar a soma das distâncias quadradas entre cada ponto de dados e seu centróide de cluster atribuído. A função objetivo pode ser escrita como: $$J = soma_{j=1}^K soma_{i=1}^N||x_i^j - mu_j||^2$$ onde $x_i^j$ é o i-th ponto de dados dentro do cluster j , μj é o centróide do cluster j e N é o número total de pontos de dados.

Método do cotovelo

O método Elbow é uma heurística usada para determinar o número ideal de clusters no cluster K-Means. O método representa graficamente a soma das distâncias quadradas entre cada observação e seu centróide atribuído em função do número de clusters. O ponto "cotovelo" no gráfico indica o número de clusters onde a adição de clusters adicionais não resulta em redução significativa na soma das distâncias quadradas.

O método Elbow pode ser resumido nas seguintes etapas:

• Execute o clustering K-Means para um intervalo de valores k
• Calcule a soma das distâncias quadradas para cada valor k
• Trace a soma das distâncias quadradas em função de k
• Identifique o ponto “cotovelo” no gráfico

Método de silhueta

O método Silhouette é outra heurística usada para determinar o número ideal de clusters no agrupamento K-Means. O método mede a qualidade da atribuição de cluster de cada observação calculando seu coeficiente de silhueta. O coeficiente de silhueta varia de -1 a 1, onde um valor de 1 indica que a observação está bem agrupada e um valor de -1 indica que a observação está classificada incorretamente. A fórmula para calcular o coeficiente de silhueta para um ponto de dados i é: $$s(i) = frac{(b(i) - a(i))}{max(a(i), b(i))}$$ onde a(i) é a distância média entre i e todos os outros pontos de dados em seu cluster, e b(i) é a distância média mínima entre i e todos os outros clusters (ou seja, o cluster com o próximo centróide mais próximo). O coeficiente de silhueta para todo o agrupamento é a média dos coeficientes de silhueta para todos os pontos de dados.

O método Silhouette pode ser resumido nas seguintes etapas:

• Execute o clustering K-Means para um intervalo de valores k
• Para cada observação, calcule o coeficiente de silhueta
• Calcule o coeficiente médio da silhueta para cada valor k
• Trace o coeficiente médio da silhueta em função de k
• Identifique o valor k com o coeficiente de silhueta médio mais alto