Agrupamiento dinámico de deformación de tiempo

¿Cuál sería el enfoque para usar Dynamic Time Warping (DTW) para realizar la agrupación de series de tiempo?

He leído sobre DTW como una forma de encontrar similitudes entre dos series de tiempo, mientras que podrían cambiarse en el tiempo. ¿Puedo usar este método como una medida de similitud para el algoritmo de agrupamiento como k-means?

No , no utilizar k-medias para la serie de tiempo.

DTW no se minimiza por la media; Es posible que k-means no converja e incluso si converge no producirá un resultado muy bueno. La media es un estimador de mínimos cuadrados en las coordenadas. Minimiza la varianza, no las distancias arbitrarias, y k-means está diseñado para minimizar la varianza, no las distancias arbitrarias .

Suponga que tiene dos series de tiempo. Dos ondas sinusoidales, de la misma frecuencia, y un período de muestreo bastante largo; pero están compensados ​​por . Dado que DTW realiza deformaciones de tiempo, puede alinearlas para que coincidan perfectamente, excepto para el principio y el final. DTW asignará una distancia bastante pequeña a estas dos series. Sin embargo, si calcula la media de las dos series, será un 0 plano: se cancelan. La media no hace una deformación dinámica del tiempo y pierde todo el valor que obtuvo DTW. En tales datos, k-means puede no converger , y los resultados no tendrán sentido. Las medias K solo deberían usarse con varianza (= Euclidiana al cuadrado), o algunos casos que son equivalentes (como el coseno, en datos normalizados L2, donde la similitud del coseno es2 $\pi$lo mismo que distancia euclidiana al cuadrado)$2 -$

En su lugar, calcule una matriz de distancia usando DTW, luego ejecute la agrupación jerárquica como un enlace simple. A diferencia de k-means, la serie puede incluso tener una longitud diferente.

Sí, puede usar el enfoque DTW para la clasificación y agrupamiento de series de tiempo . He compilado los siguientes recursos , que se centran en este mismo tema (recientemente he respondido una pregunta similar, pero no en este sitio, así que estoy copiando los contenidos aquí para conveniencia de todos):

• Clasificación / agrupación de series de tiempo UCR : página principal , página de software y documento correspondiente
• Clasificación de series temporales y agrupamiento con Python : una publicación de blog
• Capital Bikeshare: Time Series Clustering : otra publicación de blog
• Clasificación y agrupación de series temporales : cuaderno de ipython
• Dynamic Time Warping usando rpy y Python : otra publicación de blog
• Serie temporal de minería con billones de puntos: deformación dinámica del tiempo a escala : otra publicación de blog
• Análisis de series de tiempo y minería en R (para agregar R a la mezcla): otra publicación de blog
• Y, finalmente, dos herramientas que implementan / soportan DTW , para colmo: paquete R y módulo Python

Petitjean et al. Han propuesto un método reciente de DTW Barycenter Averaging (DBA) . para promediar series de tiempo. En otro artículo demostraron empírica y teóricamente cómo puede usarse para agrupar series de tiempo con k-medias. Los autores proporcionan una implementación en GitHub ( enlace al código ).

1 F. Petitjean, G. Forestier, GI Webb, AE Nicholson, Y. Chen y E. Keogh, "El promedio dinámico de deformación del tiempo de series temporales permite una clasificación más rápida y precisa", 2014 Conferencia Internacional IEEE sobre Minería de Datos, Shenzhen, 2014 .

2 F. Petitjean, P. Gançarski, Resumiendo un conjunto de series de tiempo promediando: desde la secuencia de Steiner hasta la alineación múltiple compacta, Ciencias de la Computación Teórica, Volumen 414, Número 1, 2012

Dynamic Time Warp compara los puntos de datos realizados, que pueden o no funcionar. Un enfoque más riguroso es comparar la distribución de las series de tiempo mediante una métrica llamada distancia telescópica .

Lo bueno de esta métrica es que el cálculo empírico se realiza ajustando una serie de clasificadores binarios como SVM.

Para una breve explicación, vea esto .

Para la agrupación de series de tiempo, se ha demostrado que supera a DTW; ver Tabla 1 en el documento original [1].

[1] Ryabko, D. y Mary, J. (2013). Una métrica basada en clasificación binaria entre distribuciones de series de tiempo y su uso en problemas estadísticos y de aprendizaje. The Journal of Machine Learning Research, 14 (1), 2837-2856.

Sí. Un enfoque ingenuo y potencialmente lento podría ser,

1. Crea todas tus combinaciones de clúster. k es para el recuento de clúster yn es para el número de series El número de artículos devueltos debe ser n! / k! / (n-k)!. Estos serían algo así como centros potenciales.
2. Para cada serie, calcule distancias a través de DTW para cada centro en cada grupo de grupos y asígnelo al mínimo.
3. Para cada grupo de grupos, calcule la distancia total dentro de grupos individuales.
4. Elige el mínimo.

Usé esto para un pequeño proyecto. Aquí está mi repositorio sobre Time Series Clustering y mi otra respuesta sobre esto.