K-means: quantas iterações em situações práticas?

10

Como não tenho experiência no setor de mineração de dados ou big data, gostaria de ouvi-lo compartilhar alguma experiência.

As pessoas realmente executam k-means, PAM, CLARA etc. em um conjunto de dados realmente grande? Ou eles apenas escolhem aleatoriamente uma amostra? Se eles coletassem apenas uma amostra do conjunto de dados, o resultado seria confiável se o conjunto de dados não fosse normalmente distribuído?

Em situações práticas ao executar esses algoritmos, podemos dizer quantas iterações seriam necessárias normalmente até ocorrer a convergência? Ou o número de iterações sempre aumenta com o tamanho dos dados?

Estou perguntando isso porque estou pensando em desenvolver uma abordagem para finalizar os algoritmos iterativos antes da convergência, e ainda assim os resultados ainda são aceitáveis. Acho que vale a pena tentar se o número de iterações for, digamos, mais de 1.000, para que possamos economizar algum tempo e custo computacional. O que você acha?

foo
fonte
number of iterations always grow with the data sizeNão necessariamente.
ttnphns
Existem vários critérios para interromper as iterações no K-means. Curiosamente, simplesmente definir o número de iterações para um valor fixo (digamos, 10 ou 20) é uma das maneiras razoáveis. O K-means é dedicado a ser um método rápido, portanto, se você deseja que um critério de convergência seja verificado após cada iteração, esse critério deve ser fácil / rápido para calcular.
ttnphns
11
Existe alguma maneira "científica" de determinar o número máximo de iterações a serem executadas?
foo
Seu último comentário é uma boa pergunta. Honestamente, eu não sei. talvez outras pessoas atendam.
ttnphns

Respostas:

6
  1. K-significa é barato. Você pode executá-lo para muitas iterações.

  2. Existem algoritmos ruins (o padrão) e bons. Para bons algoritmos, as iterações posteriores custam muito menos que 1% da primeira iteração.

  3. Existem implementações realmente lentas. Não os use.

  4. K-significa em dados "grandes" não existe. Porque ele funciona apenas em dados vetoriais de baixa dimensão. Você não excederá a memória de um servidor moderno com esses dados. sim, existem dados maiores - mas você não pode usar o k-means em, digamos, um mês de dados do Twitter, porque não fornecerá nada útil.

Com uma boa implementação, em um servidor moderno, o maior conjunto de dados que você pode encontrar onde k-means ainda oferece um resultado útil provavelmente precisa de menos de 1 minuto para calcular até a convergência. Então, por que se preocupar em pensar em um limite de iteração?

Possui QUIT - Anony-Mousse
fonte
11
Aceita. Neste artigo ( K-Means escalável por recuperação classificada ), os autores afirmaram que K-means converge após 20-50 iterações em todas as situações práticas, mesmo em conjuntos de dados de alta dimensão durante o teste. Além do K-means, você conhece algum algoritmo que leva um grande número de iterações até a convergência?
foo
Talvez treinando um SVM? Eu acredito que é iterativo, tentando encontrar o melhor (e menor, já que a previsão depende disso!) Conjunto de vetores de suporte.
QuIT - Anony-Mousse
A solução óbvia para executar o k-means em conjuntos de dados de alta dimensão é executar o PCA ou outro método de redução de dimensionalidade primeiro e depois executar o k-means
nico