Executar o algoritmo de clustering

Em machine learning, às vezes você encontra conjuntos de dados que podem ter milhões de exemplos. Algoritmos de ML precisam ser escalonados com eficiência para esses grandes conjuntos de dados. No entanto, muitos algoritmos de clustering não são escalonados porque precisam calcular a semelhança entre todos os pares de pontos. Isso significa que o tempo de execução aumenta como o quadrado do número de pontos, indicado como \(O(n^2)\). Por exemplo, os algoritmos de clustering hierárquicos aglomerativos ou divisivos analisam todos os pares de pontos e têm complexidades de \(O(n^2 log(n))\) e \(O(n^2)\), respectivamente.

O foco deste curso é o k-means, porque ele é escalonado como \(O(nk)\), em que \(k\) é o número de clusters. O k-means agrupa os pontos em \(k\) clusters minimizando as distâncias entre os pontos e o centroide do cluster (como mostrado na Figura 1 abaixo). O centroide de um cluster é a média de todos os pontos dele.

Como mostrado, o k-means encontra clusters circulares. Conceitualmente, isso significa que k-means trata os dados com eficiência como compostos de várias distribuições aproximadamente circulares e tenta encontrar clusters correspondentes a essas distribuições. Na realidade, os dados contêm outliers e podem não se encaixar nesse modelo.

Antes de executar k-means, escolha o número de clusters, \(k\). Inicialmente, começa com um palpite para \(k\). Mais tarde, falaremos sobre como refinar esse número.

Algoritmo de clustering k-means

Para agrupar dados em clusters \(k\) , k-means segue as etapas abaixo:

Figura 1: k-means na inicialização.

Etapa um

O algoritmo escolhe aleatoriamente um centroide para cada cluster. Em nosso exemplo, escolhemos um \(k\) de 3. Portanto, o algoritmo escolhe aleatoriamente três centroides.

Figura 2: clusters iniciais.

Etapa dois

O algoritmo atribui cada ponto ao centroide mais próximo para conseguir \(k\) clusters iniciais.

Figura 3: computação de centroides.

Etapa três

Para cada cluster, o algoritmo recalcula o centroide calculando a média de todos os pontos do cluster. As mudanças nos centroides são mostradas na Figura 3 pelas setas. Como os centroides mudam, o algoritmo reatribui os pontos ao centroide mais próximo. A Figura 4 mostra os novos clusters após a reatribuição.

Figura 4: clusters após a reatribuição.

Etapa quatro

O algoritmo repete o cálculo de centroides e a atribuição de pontos até que os pontos parem de alterar os clusters. Ao agrupar conjuntos de dados grandes, você interrompe o algoritmo antes de alcançar a convergência, usando outros critérios.

Você não precisa entender a matemática por trás do k-means neste curso. No entanto, se estiver curioso, veja abaixo a prova matemática.

Clique no ícone de adição para ver as provas matemáticas

Considerando \(n\) os exemplos atribuídos aos clusters \(k\) , minimize a soma das distâncias dos exemplos para os centroides. Em que:

• \(A_{nk} = 1\) quando o \(n\)exemplo é atribuído ao \(k\)o cluster e 0 caso contrário
• \(\theta_k\) é o centroide do cluster \(k\)

Queremos minimizar a seguinte expressão: $$\min_{A,\theta} \sum_{n=1}^N \sum_{k=1}^{K} A_{nk} ||\theta_k - x_n ||^2$$ sujeita a: $$A_{nk} \in \{0,1\} \forall n,k$$ e $$\sum^{K}_{k=1}A_{nk}=1 \forall n$$ Para minimizar a expressão em relação aos centroides de clusters \(\theta_k\), use a derivada em relação a \(\theta_k\) e equilibre-a a 0. $$f(\theta) = \sum^{N}_{n=1} \sum_{k=1}^{K} A_{nk} ||\theta_k - x_n||^2$$ $$\frac{\partial f}{\partial \theta_k} = 2 \sum_{n=1}^{N} A_{nk}(\theta_k - x_n) = 0$$ $$\implies \sum_{n=1}^{N} A_{nk}\theta_{k} = \sum^N_{n=1} A_{nk}x_{n}$$ $$\theta_k \sum_{n=1}^{N} A_{nk} = \sum_{n=1}^{N} A_{nk} x_n$$ $$\theta_k = \frac{\sum^N_{n=1} A_{nk} x_n}{\sum^N_{n=1} A_{nk}}$$ O numerador é a soma de todas as distâncias de exemplo de centroide no cluster. O denominador é o número de exemplos no cluster. Assim, o centroide do cluster\(\theta_k\) é a média das distâncias de exemplo-centroide no cluster. Então, ele foi provado.

Como as posições centroide são escolhidas inicialmente aleatoriamente, k-means pode retornar resultados significativamente diferentes em execuções sucessivas. Para resolver esse problema, execute k-means várias vezes e escolha o resultado com as melhores métricas de qualidade. Falaremos sobre as métricas de qualidade mais adiante neste curso. Você precisará de uma versão avançada da k-means para escolher melhores posições centrais.

Experimento:usando este simulador k-means da Stanford, tente executar o k-means várias vezes e verifique se consegue resultados diferentes.

Termos-chave:

• centroide