Para uma tarefa, fui solicitado a fornecer uma prova de que k-means converge em um número finito de etapas.
Isto é o que eu escrevi:
A seguir, é uma coleção de todos os centros de cluster. Definir uma “energia” função
A função de energia é não-negativo. Vemos que as etapas (2) e (3) do algoritmo reduzem a energia. Como a energia é limitada por baixo e constantemente reduzida, ela deve convergir para um mínimo local. A iteração pode ser interrompida quando muda a uma taxa abaixo de um determinado limite.
A etapa 2 refere-se à etapa que rotula cada ponto de dados pelo centro de cluster mais próximo e a etapa 3 é a etapa em que os centros são atualizados com uma média.
Isso não é suficiente para provar a convergência em um número finito de etapas. A energia pode continuar diminuindo, mas não descarta a possibilidade de que os pontos centrais possam pular sem alterar muito a energia. Em outras palavras, pode haver múltiplos mínimos de energia e o algoritmo pode pular entre eles, não?
mathematical-statistics
k-means
jkabrg
fonte
fonte
Respostas:
Em primeiro lugar, há, no máximo, maneiras para particionar N pontos de dados em k aglomerados; cada uma dessas partições pode ser chamada de "clustering". Este é um número grande, mas finito. Para cada iteração do algoritmo, produzimos um novo clustering baseado apenas no clustering antigo. Notar quekN N k
Como o algoritmo itera uma função cujo domínio é um conjunto finito, a iteração deve finalmente entrar em um ciclo. O ciclo não pode ter duração maior que porque, caso contrário, por (2) você teria algum cluster que tem um custo menor do que ele próprio, o que é impossível. Portanto, o ciclo deve ter duração exatamente 1 . Portanto, k-means converge em um número finito de iterações.1 1
fonte
Para adicionar algo: se o algoritmo converge ou não também depende do seu critério de parada. Se você parar o algoritmo depois que as atribuições do cluster não forem mais alteradas, poderá realmente provar que o algoritmo não converge necessariamente (desde que a atribuição do cluster não tenha um desempate determinístico no caso de vários centróides terem a mesma distância).
Aqui você tem 8 pontos de dados (pontos) e dois centróides (cruzes vermelhas). Agora, os pontos de dados verdes têm a mesma distância do centróide esquerdo e direito. O mesmo vale para os pontos de dados azuis. Vamos supor que a função de atribuição não seja determinística neste caso. Além disso, assumimos que, na iteração 1, os pontos verdes são atribuídos ao cluster esquerdo e os pontos azuis são atribuídos ao cluster direito. Então atualizamos os centróides. Acontece que eles de fato ficam no mesmo local. (este é um cálculo fácil. Para o centróide esquerdo, você calcula a média das coordenadas dos dois pontos pretos esquerdos e dos dois pontos verdes -> (0, 0,5). O mesmo para o centróide direito).
Então, na iteração 2, a situação parece novamente a mesma, mas agora assumimos que nossa função de atribuição não determinística (em caso de empate) atribui os pontos verdes ao cluster direito e os pontos azuis ao cluster esquerdo. Novamente, os centróides não mudam.
A iteração 3 é novamente a mesma que a iteração 1. Portanto, temos um caso em que as atribuições de cluster mudam continuamente e o algoritmo (com esse critério de parada) não converge.
fonte