Agrupación continua

9

Así que tengo un problema al que me enfrento con respecto a la agrupación con datos en vivo y de transmisión continua. Como tengo un conjunto de datos cada vez mayor, no estoy seguro de cuál es la mejor manera de ejecutar clustering eficiente y efectivo. He encontrado algunas posibles soluciones, que incluyen:

  1. Establecer un límite en la cantidad de puntos de datos para permitir, por lo tanto, cada vez que se alcanza el límite a medida que llega otro punto de datos, se elimina el punto más antiguo. Esencialmente, esto sugeriría que los datos más antiguos ya no son lo suficientemente relevantes para que nos importe lo que estamos perdiendo al descartarlos.

  2. Una vez que haya suficientes datos para hacer un buen agrupamiento, considere esto "la configuración" y, a medida que surjan nuevos puntos, en lugar de volver a agrupar todos los datos, descubra qué centro de clúster está más cerca del nuevo punto y agréguelo a eso. El beneficio aquí es que podría evitar tener que volver a agruparse en cada punto nuevo y no tendría que almacenar todos los demás puntos, solo los centros de clúster, considerando que esta agrupación es "lo suficientemente buena". La desventaja es que volver a ejecutar el algoritmo con todos los puntos de datos desde el principio puede ser más preciso.

Si bien esas son algunas de las posibles soluciones que tuve en mi cerebro, me gustaría saber si existen técnicas más conocidas para enfrentar este problema. Me imagino que sitios como Google tuvieron que lidiar con esto de alguna manera (y espero que "agregar más ram, servidores y procesadores" o "expandir continuamente sus centros de datos" no sean las únicas respuestas disponibles).

Suresh Venkat
fuente

Respuestas:

9

Hay una buena cantidad de trabajo en la agrupación de secuencias (que es ligeramente diferente a los métodos en línea, pero es esencialmente lo que desea). La referencia anterior de Guha et al es muy buena, y para una perspectiva más general sobre qué tipos de técnicas funcionan y qué métodos se han utilizado en el pasado (tanto heurísticos como precisos), es posible que desee ver mi encuesta en la agrupación en las corrientes .

Suresh Venkat
fuente
7

También puede echar un vistazo a las notas de la Lección 14 y la Lección 15 de mi curso sobre algoritmos de flujo de datos.

Piotr
fuente
4

Me gusta la encuesta de Suresh anterior, y resume diferentes enfoques en la agrupación de secuencias. No solicitó esto, pero es posible en algunos casos, el problema es que los datos distribuidos son vistos por servidores distribuidos, uno tiene que mantener una agrupación en el centro y no tener que mover muchos datos. Ver aquí .

yo también
fuente
bienvenido, Muthu!
Suresh Venkat