Como mencionado anteriormente, muitos algoritmos de agrupamento não são dimensionados para os conjuntos de dados usados no aprendizado de máquina, que geralmente têm milhões de exemplos. Por exemplo, algoritmos de agrupamento hierárquico agglomerativo ou divisor analisam todos os pares de pontos e têm complexidades de \(O(n^2 log(n))\) e \(O(n^2)\), respectivamente.
Este curso se concentra em k-means porque ele é dimensionado como \(O(nk)\), em que \(k\)é o número de clusters escolhidos pelo usuário. Esse algoritmo agrupa pontos em clusters\(k\) minimizando as distâncias entre cada ponto e o centroide do cluster (consulte a Figura 1).
Como resultado, o k-means trata os dados como compostos de várias distribuições aproximadamente circulares e tenta encontrar clusters correspondentes a essas distribuições. No entanto, os dados reais contêm valores discrepantes e clusters baseados em densidade e podem não corresponder às suposições subjacentes ao k-means.
Algoritmo de clusterização k-means
O algoritmo segue estas etapas:
Forneça uma estimativa inicial para \(k\), que pode ser revisada mais tarde. Neste exemplo, escolhemos \(k = 3\).
Escolha aleatoriamente \(k\) centroides.
Figura 1: k-means na inicialização. Atribua cada ponto ao centroide mais próximo para receber \(k\) clusters iniciais.
Figura 2: clusters iniciais. Para cada cluster, calcule um novo centroido usando a posição média de todos os pontos no cluster. As setas na Figura 4 mostram a mudança nas posições do centroide.
Figura 3: Centroides recalculados. Reatribua cada ponto ao novo centroid mais próximo.
Figura 4: clusters após a reatribuição. Repita as etapas 4 e 5, recalcule os centroides e a associação ao cluster até que os pontos não mudem mais de cluster. No caso de grandes conjuntos de dados, é possível interromper o algoritmo antes da convergência com base em outros critérios.
Como as posições do centroide são escolhidas aleatoriamente, o k-means pode retornar resultados significativamente diferentes em execuções sucessivas. Para resolver esse problema, execute o k-means várias vezes e escolha o resultado com as métricas de melhor qualidade. Vamos descrever as métricas de qualidade mais adiante neste curso. Você vai precisar de uma versão avançada do k-means para escolher melhores posições iniciais do centroid.
Embora não seja necessário entender a matemática, para quem tem curiosidade, o k-means é um caso especial do algoritmo de maximização de expectativa. Consulte as notas da aula sobre o assunto da UPenn.