Como mencionado anteriormente, muitos algoritmos de clustering não são dimensionados para os conjuntos de dados usados em machine learning, que geralmente têm milhões de exemplos. Por exemplo: algoritmos de agrupamento hierárquico aglomerativo ou divisivo 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 é escalonado como \(O(nk)\), em que \(k\) é o número de clusters escolhidos pelo usuário. Esse algoritmo agrupa pontos \(k\) os clusters minimizam as distâncias entre cada ponto e o respectivo o centroide do cluster (veja a Figura 1).
Como resultado, k-means tratam efetivamente os dados como compostos de um número aproximadamente distribuições circulares e tenta encontrar clusters correspondentes a essas distribuições de dados. Mas dados reais contêm outliers e clusters baseados em densidade e podem não corresponder às suposições de k-means.
Algoritmo de clustering k-means
O algoritmo segue estas etapas:
Forneça um palpite inicial para \(k\), que poderá ser revisado mais tarde. Para isso exemplo, escolhemos \(k = 3\).
Escolha aleatoriamente \(k\) centróides.
Figura 1: k-means na inicialização. Atribua cada ponto ao centroide mais próximo para obter \(k\) clusters iniciais.
Figura 2: clusters iniciais. Para cada cluster, calcule um novo centroide tomando a posição média de todos os pontos do cluster. As setas na Figura 4 mostram a mudança posições centroides.
Figura 3: centroides recalculados. Reatribua cada ponto ao novo centroide mais próximo.
Figura 4: clusters após a reatribuição. Repita as etapas 4 e 5, recalculando centroides e associações de cluster, até os pontos de dados não mudam mais os clusters. 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 inicialmente aleatoriamente, k-means pode retornar resultados significativamente diferentes em execuções sucessivas. Para resolver isso, problema, execute k-means várias vezes e escolha o resultado com a melhor qualidade métricas. Descreveremos as métricas de qualidade posteriormente neste curso. Você vai precisar de um versão avançada de k-means para escolher melhores posições iniciais do centroide.
Não é necessário ter um conhecimento profundo da matemática, mas quem está curioso, k-means é um caso especial da algoritmo de maximização da expectativa. Consulte notas de aula sobre o tema da UPenn.