¿Soluciones para la identificación continua del clúster en línea?

Permítame mostrarle un ejemplo de una hipotética aplicación de agrupación en línea:

En el momento n, los puntos 1,2,3,4 se asignan al grupo azul A y los puntos b, 5,6,7 se asignan al grupo rojo B.

En el momento n + 1 se introduce un nuevo punto a que se asigna al grupo azul A pero también hace que el punto b también se asigne al grupo azul A.

Al final, los puntos 1, 2, 3, 4, a, b pertenecen a A y los puntos 5, 6, 7 a B. Esto me parece razonable.

Lo que parece simple a primera vista es realmente un poco complicado: mantener identificadores a través de los pasos de tiempo. Permítanme intentar aclarar este punto con un ejemplo más limítrofe:

El punto verde hará que dos puntos azules y dos rojos se fusionen en un grupo que arbitrariamente decidí colorear de azul: ¡tenga en cuenta que este es mi pensamiento heurístico humano en el trabajo!

Una computadora para tomar esta decisión tendrá que usar reglas. Por ejemplo, cuando los puntos se fusionan en un clúster, la identidad del clúster está determinada por la mayoría. En este caso, enfrentaríamos un empate: tanto el azul como el rojo podrían ser opciones válidas para el nuevo clúster (aquí de color azul).

Imagine un quinto punto rojo cerca del verde. Entonces, la mayoría sería roja (3 rojas versus 2 azules), por lo que el rojo sería una buena opción para el nuevo grupo, pero esto contradiría la elección aún más clara de rojo para el grupo más a la derecha, ya que esas han sido rojas y probablemente deberían permanecer así. .

Me parece sospechoso pensar en esto. Al final del día, supongo que no hay reglas perfectas para esto, más bien heurísticas que optimizan algunos criterios de estabilidad.

Esto finalmente lleva a mis preguntas:

1. ¿Este "problema" tiene un nombre al que se pueda hacer referencia?
2. ¿Hay soluciones "estándar" para esto y ...
3. ... ¿hay quizás un paquete R para eso?

Herencia razonable de identidades de clúster en clustering repetitivo

Dilema de estabilidad-plasticidad, tasas de aprendizaje y algoritmos de olvido:

Primero, permítanme decir que esta es una gran pregunta y es el tipo de cosas que provocan pensamiento que realmente mejora la comprensión de los algoritmos de ML.

1. ¿Este "problema" tiene un nombre al que se pueda hacer referencia?

Esto generalmente se conoce como "estabilidad". Lo curioso es que la estabilidad es en realidad un concepto útil en la agrupación regular, es decir, no en línea. La "estabilidad" del algoritmo a menudo se elige como criterio de selección para determinar si se ha seleccionado el número correcto de grupos. Más específicamente, el problema de estabilidad de agrupación en línea que ha descrito se conoce como el stability-plasticity dilemma.

2. ¿Hay soluciones "estándar" para esto y ...

Primero, la respuesta general es que muchos algoritmos de agrupación en línea son sorprendentemente estables cuando han sido bien entrenados con una gran cohorte de datos iniciales. Sin embargo, sigue siendo un problema si realmente desea precisar las identidades de los puntos del clúster al tiempo que permite que el algoritmo reaccione a los nuevos datos. El truco de su punto se aborda brevemente en Introducción al aprendizaje automático de Ethem Alpaydin. En la página 319 deriva el algoritmo k-means en línea a través de la aplicación del descenso de gradiente estocástico, pero menciona que stability-plasticity dilemmasurge cuando se elige un valor para la tasa de aprendizaje. Una tasa de aprendizaje pequeña da como resultado la estabilidad, pero el sistema pierde adaptabilidad mientras que a medida que una tasa de aprendizaje más grande gana adaptabilidad, pero pierde la estabilidad del grupo.

Creo que el mejor camino a seguir es elegir una implementación de agrupación en línea que le permita controlar el algoritmo de descenso de gradiente estocástico y luego elegir la velocidad de aprendizaje para maximizar la estabilidad y la adaptabilidad lo mejor que pueda utilizando un procedimiento de validación cruzada de sonido.

Otro método que he visto empleado es algún tipo de algoritmo de olvido, por ejemplo, olvidar puntos más antiguos a medida que el flujo de datos madura. Esto permite un sistema bastante estable en escalas de tiempo rápidas y permite la evolución en escalas de tiempo más lentas. Adaptive Resonance Theoryfue creado para tratar de resolver el stability-plasticity dilemma. Puede encontrar este artículo interesante.

No estoy lo suficientemente versado en R como para sugerir un algoritmo, pero le sugiero que busque un mini-batch k-meansalgoritmo que le permita controlar la velocidad de aprendizaje en su algoritmo de descenso de gradiente estocástico.

¡Espero que esto ayude!