K-significa: ¿Cuántas iteraciones en situaciones prácticas?

10

No tengo experiencia en la industria de minería de datos o big data, por lo que me encantaría escucharlo compartir alguna experiencia.

¿Las personas realmente ejecutan k-means, PAM, CLARA, etc. en un conjunto de datos realmente grande? ¿O simplemente seleccionan una muestra al azar? Si solo toman una muestra del conjunto de datos, ¿el resultado sería confiable si el conjunto de datos no se distribuye normalmente?

En situaciones prácticas cuando se ejecutan estos algoritmos, ¿podemos decir cuántas iteraciones se necesitarían normalmente hasta que se produzca la convergencia? ¿O el número de iteraciones siempre crece con el tamaño de los datos?

Pregunto esto porque estoy pensando en desarrollar un enfoque para terminar los algoritmos iterativos antes de la convergencia, y sin embargo, los resultados aún son aceptables. Creo que vale la pena probar si el número de iteraciones es, digamos más de 1,000, para que podamos ahorrar algo de costo y tiempo computacional. ¿Qué piensas?

clustering data-mining k-means convergence large-data foo
fuente
number of iterations always grow with the data sizeNo necesariamente.
ttnphns
Existen varios criterios para detener las iteraciones en K-means. Curiosamente, simplemente establecer el número de iteraciones en un valor fijo (por ejemplo, 10 o 20) es una de las formas razonables. K-means está dedicado a ser un método rápido, por lo tanto, si desea verificar un criterio de convergencia después de cada iteración, ese criterio debe ser fácil / rápido de calcular.
ttnphns
1
¿Hay alguna forma "científica" de determinar el número máximo de iteraciones a ejecutar?
foo
Tu último comentario es una buena pregunta. Honestamente, no lo se. tal vez otras personas lo respondan.
ttnphns

Respuestas:

6

  1. K-means es barato. Puede permitirse ejecutarlo durante muchas iteraciones.

  2. Hay malos algoritmos (el estándar) y buenos algoritmos. Para buenos algoritmos, las iteraciones posteriores a menudo cuestan mucho menos del 1% de la primera iteración.

  3. Hay implementaciones realmente lentas. No los uses.

  4. K-means en datos "grandes" no existe. Porque solo funciona en datos vectoriales de baja dimensión. No excederá la memoria de un servidor moderno con tales datos. sí, existen datos más grandes, pero no puede usar k-means en digamos un mes de datos de Twitter, porque no le dará nada útil.

Con una buena implementación, en un servidor moderno, el conjunto de datos más grande que puede encontrar donde k-means todavía da un resultado útil probablemente necesite menos de 1 minuto para calcular hasta la convergencia. Entonces, ¿por qué molestarse en pensar en un límite de iteración?

HA SALIDO - Anony-Mousse
fuente
1
De acuerdo. En este documento ( K-medias escalables por recuperación clasificada ), los autores declararon que K-means converge después de 20-50 iteraciones en todas las situaciones prácticas, incluso en conjuntos de datos de alta dimensión mientras lo probaban. Entonces, aparte de K-means, ¿conoces algún algoritmo que requiera una gran cantidad de iteraciones hasta la convergencia?
foo
¿Quizás entrenando un SVM? Creo que es iterativo, tratando de encontrar el mejor (¡y el más pequeño, ya que la predicción depende de esto!) Conjunto de vectores de soporte.
HA SALIDO - Anony-Mousse
La solución obvia para ejecutar k-means en conjuntos de datos de alta dimensión es ejecutar PCA u otro método de reducción de dimensionalidad primero, luego ejecutar k-means
nico