# K-means O algoritmo recebe um número k de clusters a serem criados à partir de uma base de dados. O objetivo do algoritmo é encontrar um centro para cada cluster. Este centro é utilizado para determinar os pontos pertencentes a cada cluster, a partir de uma distância (euclidiana, no nosso caso). **Desvantagens:** sensível à outliers. ## Inicialização Define as médias iniciais para os centros de cluster, que serão modificadas ao decorrer da execução do algoritmo. ### Forgy Escolhe pontos aleatórios nos dados, e os definem como centros de cluster **Desvantagens:** os pontos aleatórios podem ser outliers, o que afeta a qualidade dos clusters e faz com que a convergência das médias seja mais demorada. ### Kmeans++ Escolhe o primeiro ponto de forma aleatória e os demais pontos usando probabilidade, sendo que quanto mais distante dos demais pontos já escolhidos maior a probabilidade de ser escolhido. Entaão ele escolhe o ponto mais distante dos já escolhidos até que sejam escolhidos k pontos. ## Atualizar Médias O centro de um cluster é definido por um ponto de n dimensões. Estes pontos, chamados de médias dos clusters são armazenados em uma lista de pontos. Por exemplo: ``` medias = [ [1, 2, 6, -10, 600] #Centro do cluster 0 [5, 0, -1, 40, 302] #Centro do cluster 1 [7, -2, 7, 25, -12] #Centro do cluster 2 ] ``` K-means é um algoritmo iterativo, que se aproxima de um máximo local a cada iteração. Este processo é realizado ao atualizar os centros de cada cluster. - As médias são inicializadas, como discutido acima. - Primeiramente, o algoritmo atribui os pontos do dataset ao seu cluster mais próximo, isso é obtido ao comparar a distancia euclidiana entre estes pontos e as médias de cada cluster. - Após este passo, uma nova média para cada cluster é calculada, levando em consideração os novos pontos inseridos naquele cluster. - O processo se repete até que a média não mude muito de valor a cada iteração. Se a média das distâncias entre as médias antigas e as novas médias for menor que um certo threshold, o algoritmo termina e o cluster é retornado. ## Encontrando um valor para k É preciso definir o número de clusters antes de se executar o algoritmo. Para definir esta quantidade _k_ ideal, utilizamos dois métodos. ### Elbow Method O método Elbow testa o k-means para um certo intervalo de valores k calculando para cada iteração a função de custo J que queremos minimizar. Ao plotar um gráfico de número de cluster por função de custo J(sum of squared distance (SSE) entre os pontos do dataset que pertencem ao custer e o centro desse cluster), o número de cluster que deve ser escolhio é o que está no ponto em que a curva mais se parece com um cotovelo. ### Silhouette Method O método da silhueta faz o uso do _silhouette coefficient_. ```silhouette coefficient: s(i) = (a(i) - b(i))/max(a(i),b(i))``` Este coeficiente é calculado para cada ponto, e indica: - A distância média entre este ponto e os demais pontos de seu cluster. - A distância média entre este ponto e os pontos do cluster mais próximo. O K-means é executado para _k_ com valores de 2 até 10, e a média do _silhouette coefficient_ de todos os pontos, para cada _k_, é apresentada em um gráfico. O _k_ que possui o maior valor neste gráfico deve ser escolhido. Sabemos que este _k_ possui: - Os clusters mais densos. - Os clusters mais afastados de outros clusters.