Algoritmo para segmentación de datos de secuencia

Tengo una gran secuencia de vectores de longitud N. Necesito un algoritmo de aprendizaje no supervisado para dividir estos vectores en segmentos M.

Por ejemplo:

K-means no es adecuado, porque pone elementos similares de diferentes ubicaciones en un solo clúster.

Actualizar:

Los datos reales se ven así:

Aquí, veo 3 grupos: [0..50], [50..200], [200..250]

Actualización 2:

Usé k-means modificado y obtuve este resultado aceptable:

Fronteras de los racimos: [0, 38, 195, 246]

Consulte mi comentario anterior y esta es mi respuesta de acuerdo con lo que entendí de su pregunta:

Como ha indicado correctamente, no necesita la agrupación sino la segmentación . De hecho, está buscando puntos de cambio en su serie de tiempo. La respuesta realmente depende de la complejidad de sus datos. Si los datos son tan simples como el ejemplo anterior, puede usar la diferencia de vectores que se sobrepasa en los puntos cambiantes y establecer un umbral para detectar esos puntos como se muestra a continuación: Como puede ver, por ejemplo, un umbral de 20 (es decir$dx<-20$ y $dx>20$) detectará los puntos. Por supuesto, para datos reales necesita investigar más para encontrar los umbrales.

Preprocesamiento

Tenga en cuenta que existe una compensación entre la ubicación precisa del punto de cambio y el número exacto de segmentos, es decir, si utiliza los datos originales, encontrará los puntos de cambio exactos, pero todo el método es sensible al ruido, pero si suaviza Puede que sus señales primero no encuentren los cambios exactos, pero el efecto de ruido será mucho menor, como se muestra en las siguientes figuras:

Conclusión

Mi sugerencia es suavizar sus señales primero e ir por un método de agrupación simple (por ejemplo, usando GMM s) para encontrar una estimación precisa del número de segmentos en las señales. Dada esta información, puede comenzar a encontrar puntos de cambio restringidos por el número de segmentos que encontró en la parte anterior.

Espero que todo haya ayudado :)

¡Buena suerte!

ACTUALIZAR

Afortunadamente, sus datos son bastante sencillos y limpios. Recomiendo encarecidamente los algoritmos de reducción de dimensionalidad (por ejemplo, PCA simple ). Supongo que revela la estructura interna de sus grupos. Una vez que aplique PCA a los datos, puede usar k-significa mucho más fácil y más preciso.

Una solución seria (!)

De acuerdo con sus datos, veo que la distribución generativa de los diferentes segmentos es diferente, lo que es una gran oportunidad para segmentar sus series de tiempo. Vea esto (original , archivo , otra fuente ), que es probablemente la mejor y más avanzada solución a su problema. La idea principal detrás de este documento es que si diferentes segmentos de una serie de tiempo son generados por diferentes distribuciones subyacentes, puede encontrar esas distribuciones, establecerlas como la verdad fundamental para su enfoque de agrupación y encontrar agrupaciones.

Por ejemplo, suponga un video largo en el que los primeros 10 minutos alguien está andando en bicicleta, en los segundos 10 minutos está corriendo y en el tercero está sentado. Puede agrupar estos tres segmentos (actividades) diferentes utilizando este enfoque.

Se sabe que la agrupación de K-means da mínimos locales, dependiendo de su inicialización inicial de los centros de agrupación.

Sin embargo, creo que la segmentación k-means puede resolverse globalmente, ya que no permutamos nada para encontrar la solución.

Puedo ver en sus comentarios que finalmente logró llegar a una segmentación. ¿Podría darnos su opinión, por favor? ¿Es su solución la mejor solución? ¿O te conformaste con una solución lo suficientemente buena?

Solo como una sugerencia: puede intentar usar el algoritmo DBSCAN, ya que a menudo funciona mucho mejor que K-means para la agrupación

De lo contrario, si desea probar algo nuevo para la agrupación y aprender algunas cosas interesantes, le sugiero que pruebe un análisis de datos topológicos a través de diagramas persistentes. Voy a dejarte aquí una bonita introducción fácil :)

https://towardsdatascience.com/persistent-homology-with-examples-1974d4b9c3d0