Ajustar datos lineales por partes

18

¿Cuál es una forma sólida de ajustar datos lineales pero ruidosos por partes?

Estoy midiendo una señal, que consta de varios segmentos casi lineales. Me gustaría ajustar atómicamente varias líneas a los datos para detectar las transiciones.

El conjunto de datos consta de unos pocos miles de puntos, con 1-10 segmentos y sé el número de segmentos.

Este es un ejemplo de lo que me gustaría hacer automáticamente.

ingrese la descripción de la imagen aquí

P3trus
fuente
No creo que esta pregunta pueda responderse razonablemente a menos que nos diga con qué precisión desea conocer la ubicación de los puntos de ruptura, cuál es su estimación aproximada para la longitud más corta de un segmento lineal y cuántas muestras hay en un típico región de transición Si las etiquetas del eje horizontal en su figura son números de muestra, entonces, con dos transiciones en el intervalo de a x [ 0 ] , la tarea es más difícil que si los segmentos en línea recta fueran de mayor duración (en muestras) x[5]x[0]
Dilip Sarwate
@DilipSarwate Actualicé la pregunta con los requisitos (por cierto, el xaxis es el campo magnético en Tesla)
P3trus
Puede probar esta caja de herramientas si está trabajando con la caja de herramientas de ajuste de curvas
Rhei

Respuestas:

12

Intenté dos enfoques, ingenuamente (usando solo 3 segmentos). Seguramente habría métodos más sofisticados por ahí.

    RANSAC, se supone que es un mecanismo de ajuste robusto. Es fácil detener el algoritmo después de varios segmentos. Sin embargo, puede ser difícil imponer la continuidad entre segmentos, como parece requerido en su aplicación, al menos con una implementación simple. Como prueba de concepto, creé una imagen de los puntos de datos para poder utilizar el motor RANSAC disponible en , la función de detección de línea de Mathematica.ImageLines

ingrese la descripción de la imagen aquí

    Ajuste un modelo lineal por partes utilizando un minimizador de uso general. Es fácil imponer la continuidad de los segmentos. Curiosamente, las pruebas de residuos y otras propiedades pueden proporcionar suficiente información para determinar automáticamente el número de segmentos, aunque no lo he probado. Así es como se ve en Mathematica:

ingrese la descripción de la imagen aquí

Matthias Odisio
fuente
Parece una gran respuesta. Gracias por contribuir
Jason R
7

x[n]

  • x[n]y[n]

    y[n]={1,if |(x[n+1]x[n])(x[n]x[n1])|<ϵ,0,otherwise.
    ϵx[n1],x[n],x[n+1](n1,x[n1])(n,x[n])(n,x[n])(n+1,x[n+1])
  • Si es una serie de diez o más corridas largas de s separadas por corridas de s con ocasionales extraviados s aquí y allá para estropear la belleza, relájese, está en el camino correcto. De lo contrario, si hay muy pocas ejecuciones o demasiadas ejecuciones de s, repita el paso anterior con un diferente .y[n]1011ϵ

  • Utilice el ajuste de curva lineal de menor error cuadrático medio para ajustar líneas rectas a los puntos identificados por como pertenecientes al mismo segmento de línea recta. Ahora tiene diez puntos de ajuste de líneas rectas, por ejemplo, la línea A ajusta los puntos a ; la línea B ajusta los puntos a , la línea C ajusta los puntos a , y así sucesivamente. Extienda A hacia la derecha y B hacia la izquierda para averiguar dónde se cruzan; extienda B hacia la derecha y C hacia la izquierda para averiguar dónde se cruzan, etc. Felicitaciones, ahora tiene un modelo lineal continuo y por partes para sus datos.x [ 3 ] x [ 88 ] x [ 94 ] x [ 120 ] x [ 129 ] y[n]x[3]x[88]x[94]x[120]x[129]

Dilip Sarwate
fuente
¡Robaron totalmente mi respuesta! =)
Phonon
Idea interesante, pero lamentablemente debido al ruido en la señal, no obtengo buenos resultados.
P3trus
1
Esa expresión cuyo magnitute se compara con épsilon es en realidad una aproximación a la segunda derivada de los datos. Hay otras formas de calcular esto utilizando más de tres puntos que no responden tanto al ruido. Busque Savitzky-Golay.
DarenW
4

(Años después) las funciones lineales por partes son splines de grado 1, que se les puede decir a la mayoría de los ajustadores de splines que hagan. scipy.interpolate.UnivariateSpline, por ejemplo, se puede ejecutar con k=1 un parámetro de suavizado s, con el que tendrá que jugar: consulte scipy-interpolation-with-univariate-splines .
En Matlab, vea cómo elegir nudos .

Agregado: encontrar nudos óptimos no es fácil, porque puede haber muchos óptimos locales. En cambio, le das a UnivariateSpline un objetivo s, suma de error ^ 2, y dejas que determine el número de nudos. Después del ajuste, get_residual()obtendrá la suma real del error ^ 2 y get_knots()los nudos. Un pequeño cambio spuede cambiar mucho los nudos, especialmente en ruido alto - ymmv.
El gráfico muestra ajustes a una función aleatoria por partes lineal + ruido para varios s.

Para ajustar constantes por partes, consulte Detección de pasos . ¿Se puede usar para pw lineal? No se comenzar diferenciando datos ruidosos aumentará el ruido, incorrecto.

Serían bienvenidas otras funciones de prueba y / o enlaces a documentos o códigos. Un par de enlaces:
regresión lineal por partes con nudos como parámetros
Las splines lineales son muy sensibles al lugar donde se colocan los nudos
knot-selection-for-cubic-regression-splines
Este es un problema complicado y la mayoría de las personas simplemente seleccionan los nudos por prueba y error.
Un enfoque que está creciendo en popularidad es utilizar splines de regresión penalizadas.


Agregado en marzo de 2014: la programación dinámica es un método general para problemas con subproblemas anidados como este:

optimal k lines
    = optimal k - 1 lines up to some x
    + cost of the last line x to the end
over x  (all x in theory, nearby x in practice)

La programación dinámica es muy inteligente, pero ¿puede vencer a la fuerza bruta + heurística para esta tarea?
Vea las excelentes notas del curso de Erik Demaine en MIT 6.006 Introducción a los algoritmos y
también la regresión lineal segmentada de Google y el
síndrome de John Henry.


ingrese la descripción de la imagen aquí

denis
fuente
El problema, al menos con scipy, es el posicionamiento de los nudos. scipy usa nudos equidistantes.
P3trus
@ P3trus, sí, para empezar, pero luego pueden moverse; vea la trama. De todos modos, tiene como objetivo el error total, no los nudos.
denis
@ P3trus ¿Has intentado usar el método de splines de regresión multivariante que selecciona automáticamente los puntos de interrupción de forma iterativa? cs.rtu.lv/jekabsons/regression.html
Atul Ingle
@Atul Ingle, la selección de punto de ruptura / nudo de afaik es el mismo problema, desde cualquier ajustador de spline. Si conoce diferentes algoritmos para eso de personas de R / regresión, ¿podría publicar un enlace por favor?
denis
¿Está buscando paquetes en R / Matlab que hagan splines de regresión adaptativa? Aquí: cran.r-project.org/web/packages/earth/index.html cran.r-project.org/web/packages/mda/index.html y también ARESLab en Matlab para el que ya publiqué el enlace.
Atul Ingle
0

Tome la derivada y busque áreas de valor casi constante. Debería crear el algoritmo para buscar aquellas áreas con un nivel ideal de pendiente +/- y eso le daría la pendiente de la línea para esa sección. Es posible que desee realizar un suavizado, como una media deslizante, antes de hacer la clasificación seccional. El siguiente paso sería obtener la intersección y, que debería ser trivial en ese punto.

porten
fuente
La derivada puede ser muy ruidosa. No creo que lo recomendaría.
robert bristow-johnson
0

Usar un filtro de tendencia l1 es otra idea:

Papel

Ejemplo en línea

SeanVN
fuente
1
¡Tu respuesta es demasiado corta para ser constructiva! Por favor considere hacer un esfuerzo para expandirlo de una manera pedagógica.
sansuiso