Ciclagem no algoritmo k-means

9

Segundo o wiki, o critério de convergência mais utilizado é "a atribuição não mudou". Eu queria saber se o ciclismo pode ocorrer se usarmos esse critério de convergência? Eu ficaria satisfeito se alguém apontasse uma referência a um artigo que dê um exemplo de ciclismo ou prove que isso é impossível.

clustering algorithms k-means Tomek Tarczynski
fonte
2
Deixe-me enfatizar (uma vez que isso é negligenciado com frequência) que as provas de convergência precisam de distância euclidiana (quadrática) , de modo que a função de distância e a função média otimizem o mesmo critério. Se você usar uma distância diferente (na verdade, você não deve usar uma distância, mas a "menor soma de quadrados"), poderá perder a convergência em k-médias.
Quit - Anony-Mousse 18/03/2013

Respostas:

7

Este artigo parece provar convergência em um número finito de etapas.

Simon Byrne
fonte
11
Exatamente o que eu estava procurando!
Tomek Tarczynski
4

A função objetivo mean diminui estritamente a cada mudança de atribuição, o que implica automaticamente convergência sem ciclagem. Além disso, as partições produzidas em cada etapa de -eans satisfazem uma "propriedade Voronoi", na qual cada ponto é sempre atribuído ao seu centro mais próximo. Isso implica um limite superior no número total de partições possíveis, o que gera um limite superior finito no tempo de terminação para médias.k kkkk

Suresh Venkatasubramanian
fonte
Obrigado, é intuitivo que a função objetivo diminua, mas eu não tinha certeza de que diminui estritamente. Eu queria ter certeza de que não há nenhum caso patológica assim como na programação linear
Tomek Tarczynski
Bem, sim e não. Enquanto converge, pode levar um tempo exponencial, da mesma forma que simplex. Além disso, para ambos os problemas, você pode mostrar que as variantes "suavizadas" convergem em tempo polinomial
Suresh Venkatasubramanian
2

Com precisão finita , o ciclismo pode aparecer.

O ciclismo é frequente na precisão única, excepcional na precisão dupla.

Quando perto de um mínimo local, a função objetivo às vezes pode aumentar um pouco devido a erros de arredondamento. Isso geralmente é inócuo, pois a função do algoritmo diminui novamente e, eventualmente, atinge o mínimo local. Mas, ocasionalmente, o algoritmo inicia uma tarefa visitada anteriormente e inicia o ciclo.

É fácil e seguro observar ciclos em implementações de critérios de parada no mundo real.

François Pays
fonte