algoritmo k-means ++ e valores discrepantes

8

É sabido que o algoritmo k-means sofre na presença de outliers. O k-means ++ é um método eficaz para a initalização do centro de cluster. Eu estava analisando o PPT pelos fundadores do método, Sergei Vassilvitskii e David Arthur http://theory.stanford.edu/~sergei/slides/BATS-Means.pdf (slide 28), que mostra que a inicialização do centro de cluster é não afetado por outlier como visto abaixo.insira a descrição da imagem aqui

De acordo com o método k-means ++, é mais provável que os pontos mais distantes sejam os centros iniciais. Dessa maneira, o ponto externo (o ponto mais à direita) também deve ser um centróide inicial do cluster. Qual é a explicação para a figura?

prashanth
fonte

Respostas:

2

Sim, é mais provável que o outlier seja escolhido. Mas também existem muitos outros inliers, a chance de escolher um deles também é substancial. Digamos que você tenha um valor externo 10 vezes maior, então é 100x mais provável que seja piquete do que um interno. Se você possui 100 inliers, as chances são de cerca de 50% e se você tiver 1000 inliers, a chance de escolher o outlier é de cerca de 10%.

Mas apesar de tudo, eu diria que o k-means ++ provavelmente tem mais probabilidade de selecionar valores discrepantes como centros iniciais (no exemplo acima, o aleatório o selecionaria em 1% ou 0,1%) e, portanto, provavelmente mais sensível a discordantes (e de fato , muitas pessoas relatam pouca melhora com o k-means ++). No entanto, não faz muita diferença: qualquer método k-means é afetado, porque todos otimizam o mesmo objetivo. E a soma dos quadrados é um objetivo sensível aos valores discrepantes, independentemente de como você otimizar. Por causa do problema estar no objetivo, escolher o outlier como centro pode produzir um resultado "melhor" . O ideal global pode ser assim!

Possui QUIT - Anony-Mousse
fonte
1

Isso parece ser explicado no slide 27.

Eles propõem a escolha aleatória do primeiro centróide de cluster, de acordo com o K-médio clássico. Mas o segundo é escolhido de forma diferente. Observamos cada ponto x e atribuímos a ele um peso igual à distância entre x e o primeiro centróide escolhido, elevado a um poder alfa. Alpha pode levar vários valores interessantes.

Se alfa for 0, temos o algoritmo k-means clássico, porque todos os pontos têm peso 1, então todos têm a mesma probabilidade de serem escolhidos.

Se alfa é infinito (ou, na prática, um número muito grande), temos o método de ponto mais distante, onde o ponto mais distante tem um peso muito grande, o que torna muito provável que seja escolhido. Como visto nos slides 24-26, isso o torna sensível a valores discrepantes.

Eles propõem definir alfa como 2. Isso fornece uma boa probabilidade de escolher pontos mais distantes do primeiro centróide escolhido, mas não escolher automaticamente o mais distante. Isso fornece ao método, k-means ++, a boa propriedade de ser menos sensível a outliers.

ociule
fonte
stackoverflow.com/questions/5466323/… fornece uma ilustração do algoritmo k-means ++. Aqui vemos que alfa = 2 é para a ponderação D ^ 2, onde é tomado o quadrado da distância de um ponto ao centróide mais próximo, o que é bem explicado no artigo original. ilpubs.stanford.edu:8090/778/1/2006-13.pdf . Mas, mesmo no caso de alfa = 2, deve-se considerar o ponto externo como o centróide inicial.
prashanth