El autor cree que este es un método de agrupación de series temporales eficiente, de alta precisión y independiente del dominio.
Creo que tiene un mejor efecto de agrupación que los métodos tradicionales. En comparación con el método DTW, el efecto es ligeramente peor, pero mucho más rápido. Después de todo, en principio, la forma K solo considera el estiramiento longitudinal y la traslación transversal, mientras que DTW también considera el estiramiento transversal.
El principio de K-Shape es similar al de K-means. La diferencia es que se mejora el método de cálculo de la distancia y se optimiza el método de cálculo del centroide. Por un lado, admite escalado de amplitud e invariancia de traducción. Por otro lado, tiene una alta eficiencia computacional y no requiere configuración manual de parámetros, lo que facilita la expansión a más campos.
El algoritmo de distancia se utiliza para calcular la diferencia entre dos conjuntos de datos de series de tiempo. El problema central es cómo lidiar con la deformación de los datos de series de tiempo. Los datos del electrocardiograma que se muestran en la Figura 1 de este artículo se dividen en dos categorías: A/B:
Entre ellas, las características de la categoría A son: aumento -> disminución -> aumento, mientras que las características de categoría B son: Caer -> levantarse. La imagen inferior derecha de la Figura 1 es el efecto de modelado ideal, que reconoce el mismo patrón e ignora las diferencias en amplitud y fase. La gente también prefiere utilizar este método para calcular la distancia y muchas veces incluso piensa que el método de cálculo de la distancia es más importante que el método de agrupación. En general, los métodos que admiten el escalamiento de amplitud y la invariancia de traducción son computacionalmente costosos y difíciles de modelar grandes cantidades de datos.
El algoritmo de distancia convencional antes de K-Shape es el siguiente:
K-Shape calcula la distancia entre dos series de tiempo mediante el método de correlación cruzada. Supongamos que hay dos series de tiempo, X e Y, con longitudes de secuencia m. Para lograr la invariancia de traducción y la invariancia de Y, dibuje X paso a paso y calcule la diferencia entre X e Y en cada paso.
Como se muestra en la figura anterior, si el área verde es Y y el área blanca es X, entonces cada línea s (paso) avanza un paso, la longitud de la secuencia es m=4, s∈( -3, 3 )***7 valores, w es la posibilidad de todos los movimientos 2m-1=7 veces, w-m = s =
Defina el coeficiente de correlación cruzada CC:
Utilice R para calcular cada similitud de un paso entre X e Y, calculando el producto escalar de la posición superior (existente tanto en X como en Y). Finalmente, R es la suma de los productos escalares de las áreas efectivas (los parches de cada par se suman). Se puede decir que cuanto mayor es R, más similares son las dos secuencias.
Debido a que la amplitud de cada subsecuencia es diferente y el número de bloques es diferente, existen tres métodos de normalización. El tercero utiliza el método de correlación cruzada, que tiene el mejor efecto.
El efecto de normalización se muestra en la siguiente figura:
La figura (a) solo usa la normalización z para normalizar la amplitud sin traducción. Se puede ver que no hay traducción (superficie). hacia arriba) la alineación funciona mejor. Se puede ver en (b), (c) y (d): (d) El tercer método se utiliza para el gráfico. El valor de similitud es mayor en el punto medio (cuando s = 0), es decir, cuando. uno frente al otro, su similitud máxima, consistente con el efecto presentado en (a). Tanto (b) como (c) creen que la situación más similar ocurre en la derecha, lo que obviamente no es correcto.
Este artículo define la distancia basada en forma SBD (Distancia basada en forma). Cuantos más bloques se superpongan, más parecida a una CC se verá la forma. Compare los valores de similitud de todas las posiciones posibles, tome el máximo (CC) más similar y luego use 1-max (CC) para obtener el SBD, es decir, cuanto más similar sea la forma, menor será la distancia SBD y el valor NCC normalizado está entre .
Se puede ver que cuando la secuencia es más larga, la complejidad temporal del método anterior es mayor, y cuando la secuencia es más larga, la cantidad de cálculo será mayor. En respuesta a este problema, el autor propuso utilizar la transformada de Fourier para transformar la secuencia del dominio del tiempo al dominio de la frecuencia y luego compararla para ahorrar la cantidad de cálculo.
Después de definir la distancia, necesitamos ajustar el algoritmo del centroide según la lógica de la distancia.
Como se puede ver en la Figura 4, el centroide de los datos de la serie temporal también es una línea de cambio de serie temporal. La línea azul en la figura utiliza el método de promedio (calcula el valor promedio de cada punto) para calcular. el centroide; debido a desalineación, picos y valles. Se dibuja como una línea recta, por lo que la dirección de la forma no se puede expresar con precisión.
K-Shape utiliza un método basado en SBD para calcular el centroide.
El objetivo de esta fórmula es encontrar μk* y maximizar la similitud NCC entre el centro de masa μk y cada secuencia xi en el grupo Pk.
Algoritmo 1: Primero use la función SBD() para calcular dist e y', donde dist es la distancia entre las series de tiempo x e y, e y' es el subsegmento en y que mejor coincide con x. Este Este método se utiliza para resolver el problema de la desalineación de las crestas y valles de las olas para que se cancelen entre sí.
Luego usa el método basado en álgebra lineal para expandir la Fórmula 13 a la Fórmula 15:
Finalmente, se puede simplificar usando la fórmula del cociente de Rayleigh:
Rayleigh cociente R Una propiedad importante de (M, x) es que el valor máximo de R es igual al valor propio máximo de la matriz M, y el valor mínimo es igual al valor propio mínimo de la matriz M. En este momento, no Tengo que pensar demasiado en x en R (M, x) (es decir, Reino Unido en esta pregunta). La ecuación 13 se simplifica al siguiente algoritmo:
Algoritmo 2: ShapeExtraction() calcula un centroide C' más razonable en función del centroide C actual del grupo y todos los puntos X del grupo.
Línea 2: recorre todos los puntos X(i) del grupo.
Línea 3: Calcula la distancia dist entre cada punto y el centroide y el segmento de recta X' que es más similar al centroide.
Línea 4: Agrega el fragmento más similar a X'
Línea 5: Transpone X' y multiplica por X para generar una matriz cuadrada (cuadrado de >
Línea 6: Cree una matriz Q para la regularización.
Línea 7: Generar matriz m después de la regularización.
Línea 8: Obtenga el vector propio cuando la matriz M corresponde al valor propio máximo para lograr la extracción de características de X'
(La explicación anterior es una comprensión personal, no necesariamente correcta, como referencia solo)
El método de agrupamiento final se implementa mediante iteración, y cada iteración se divide en dos pasos: el primer paso es recalcular el centroide y el segundo paso es recalcular cada secuencia de acuerdo con la distancia desde el nuevo centroide. Asignar a diferentes grupos; iterar hasta que las etiquetas ya no cambien.
Algoritmo 3: todo el proceso de agrupación se implementa mediante k-Shape();
donde x son todas las secuencias, k es el número de grupos e IDX es la etiqueta.
Línea 3: Continuar la iteración hasta que la etiqueta sea estable y el número de iteraciones no exceda 100.
Línea 4-10: Vuelva a calcular el centroide c de cada grupo en función de los elementos del grupo.
Líneas 11-17: Calcula la distancia entre cada secuencia y cada centroide y asígnala a un nuevo grupo (nueva etiqueta).
El tiempo necesario para cada iteración del algoritmo en forma de K es:
o(máximo {n k m log(m), n m^2, k m^3})
donde n es el número de instancias, k es el número de grupos y m es la longitud de la secuencia. Se puede ver que la mayor parte del costo computacional de este algoritmo depende de la longitud de la serie temporal m. Pero esta longitud suele ser mucho menor que el número de series temporales, por lo que la dependencia de m no es un cuello de botella. En el raro caso de que m sea muy grande, se puede utilizar la segmentación o la reducción de dimensionalidad para reducir eficazmente la longitud de la secuencia.
La Figura 5 compara los efectos de los modelos en forma de K, ED y DTW. Se puede ver que en la mayoría de los casos, SBD es mejor que ED y, en algunos casos, SBD es mejor que DTW. Pero SBD es mejor que DTW porque es más rápido.