Minimizar el número de puntos en una aproximación lineal por partes

Question

Minimizar el número de puntos en una aproximación lineal por partes

algoritmos
regresión
Matemáticas
mejoramiento
aproximación
aprendizaje automático

Eric Leibenguth

Tengo $m$ puntos de datos $(x_i,y_i)$ en un intervalo dado. Me gustaría encontrar una función lineal por partes $f(x)$ que se aproximan a estos $m$ puntos con un número mínimo de puntos $n$ para que mi error de aproximación esté por debajo de una tolerancia $\epsilon$ .

Mi $m$ puntos:

La función $f$ es una función lineal por partes definida con $n$ puntos $(x_a^{i},y_a^{i})$ . Para $n=4$ , se vería como:

Error de aproximación:

\frac{1}{metro} \sum_{1 \leq i \leq metro} (y_{i} - F (X_{i}))^{2} \leq ϵ

$\frac{1}{m} \sum_{1\le i\le m}(y_i-f(x_i))^2 \leq\epsilon$

Para resolver ese problema necesito encontrar, para un dado $n$ , una forma de obtener el conjunto óptimo de puntos $(x_a^{i},y_a^{i})$ . Puedo intentar minimizar mi error de aproximación con el descenso de gradiente, pero la función no es convexa, por lo que es posible que no converja al óptimo global.

Si resuelvo el paso anterior, simplemente puedo ejecutar el algoritmo desde $n=1,2,3,...$ y detenerme cuando mi error de aproximación caiga por debajo $\epsilon$

Suena como un problema bastante común que quizás ya tiene una solución. ¿Conoce uno o puede proponer un enfoque para ese problema?

usuario856

El algoritmo de Douglas-Peucker se puede usar para encontrar una aproximación tal que

max_{i} (y_{i} - f (x_{i})) \leq ϵ

$\max_i(y_i-f(x_i))\le\epsilon$ en cambio.

usuario856

Lidiar con

\sum_{i} (y_{i} - f (x_{i}))^{2}

$\sum_i (y_i-f(x_i))^2$ en cambio, podría considerar un gráfico completo en vértices

{1, 2, \dots, m}

$\{1,2,\ldots,m\}$ ; asignar cada borde

(i, j)

$(i,j)$ Un coste

w_{i j} = \sum_{i < k < j} (y_{k} - f_{i j} (x_{k}))^{2}

$w_{ij}=\sum_{i<k<j} (y_k-f_{ij}(x_k))^2$ , dónde

f_{i j}

$f_{ij}$ es la aproximación lineal entre

(x_{i}, y_{i})

$(x_i,y_i)$ y

(x_{j}, k_{j})

$(x_j,k_j)$ ; luego encuentre el camino más corto desde

1

$1$ a

m

$m$ usando solo

n - 1

$n-1$ bordes

Eric Leibenguth

@Raul, Gracias! Creo que el algoritmo de Douglas-Peucker podría ser una solución adecuada para mi problema. También me gusta mucho su enfoque basado en gráficos para el error cuadrático. Tenga en cuenta que en ambos enfoques un inconveniente es que el

(x_{a}^{i}, y_{a}^{i})

$(x_a^{i},y_a^{i})$ se eligen entre los

(x_{i}, y_{i})

$(x_{i},y_{i})$ , que podría no ser óptimo. También estoy pensando que podría usar la solución de Douglas-Peucker para inicializar un algoritmo de descenso de gradiente mucho más cerca del óptimo global...

anton sherwood

Me parece que Douglas-Peucker, al ajustarse exactamente a ciertos puntos de entrada, no logra encontrar mejores soluciones que pierdan todos los puntos (como en la ilustración de OP).

LinAlg

esto se puede expresar como un problema de optimización de enteros mixtos, que se puede resolver para

n

$n$

Respuestas (4)

Minimizar el número de puntos en una aproximación lineal por partes

El algoritmo de Douglas-Peucker se puede usar para encontrar una aproximación tal que $\max_i(y_i-f(x_i))\le\epsilon$ en cambio.
Lidiar con $\sum_i (y_i-f(x_i))^2$ en cambio, podría considerar un gráfico completo en vértices $\{1,2,\ldots,m\}$ ; asignar cada borde $(i,j)$ Un coste $w_{ij}=\sum_{i<k<j} (y_k-f_{ij}(x_k))^2$ , dónde $f_{ij}$ es la aproximación lineal entre $(x_i,y_i)$ y $(x_j,k_j)$ ; luego encuentre el camino más corto desde $1$ a $m$ usando solo $n-1$ bordes
@Raul, Gracias! Creo que el algoritmo de Douglas-Peucker podría ser una solución adecuada para mi problema. También me gusta mucho su enfoque basado en gráficos para el error cuadrático. Tenga en cuenta que en ambos enfoques un inconveniente es que el $(x_a^{i},y_a^{i})$ se eligen entre los $(x_{i},y_{i})$ , que podría no ser óptimo. También estoy pensando que podría usar la solución de Douglas-Peucker para inicializar un algoritmo de descenso de gradiente mucho más cerca del óptimo global...
Me parece que Douglas-Peucker, al ajustarse exactamente a ciertos puntos de entrada, no logra encontrar mejores soluciones que pierdan todos los puntos (como en la ilustración de OP).
esto se puede expresar como un problema de optimización de enteros mixtos, que se puede resolver para $n$

Cabina G · Answer 1

Yo abordaría el problema de la siguiente manera.

Tome el intervalo que contiene los tres primeros puntos. Calcule el coeficiente de correlación $\rho$ .
- si $\rho$ no es lo suficientemente bueno, tome solo los dos primeros puntos, márquelos como si estuvieran en el primer intervalo y pase a examinar los siguientes tres. - elif $\rho$ es bastante bueno, agregue un cuarto punto y vuelva a calcular el coeficiente; continuar hasta $\rho$ sigue siendo bueno;
Repita hasta dividir todos los puntos en intervalos contiguos con buena correlación.

Solo tiene que considerar qué hacer con los puntos en el borde de los intervalos:
- puede mantener los intervalos separados;
- o puede retomar el último punto en el cálculo de la correlación para el siguiente, superponiendo así los intervalos.

anton sherwood · Answer 2

Esta es la forma que me parece obvia; tal vez alguien más sabio señalará cómo es ineficiente o falla en la entrada perversa.

Considere el espacio bidimensional de funciones lineales. Cada punto de entrada, con sus tolerancias, define una banda de líneas aceptables. Una intersección de tales bandas es un polígono convexo.

Por lo tanto, comenzando por la izquierda, acumule las restricciones hasta que este polígono desaparezca y luego retroceda en uno. Su primera línea está representada por un punto en cualquier parte de este polígono; también puede usar su centroide, o el promedio de sus esquinas.

Luego hazlo de nuevo, comenzando con el último punto "cubierto" por la primera línea. Su $(x_a^2,y_a^2)$ es, por supuesto, la intersección de las dos primeras líneas de solución.

Podría ser interesante ver si comenzar desde la derecha da un resultado diferente.

(Mi preferencia estética sería usar todas las subsecuencias máximas compatibles, pero no es mi pregunta).

Editar: Esta es la idea principal del siguiente documento y se discute aquí

¿Se puede extender este concepto a polinomios por partes de grado n con k derivadas continuas?

usuario251257 · Answer 3

No es simple porque la función lineal por partes depende de los puntos de ruptura de una manera no diferenciable (sin embargo, es continua). Y las cosas se ponen feas si varías el número de descansos.

Es mucho más sencillo calcular la mejor aproximación para roturas fijas . Por lo tanto, una heurística simple sería la siguiente:

Comience con la mejor aproximación lineal $f_0$ en decir $[a,b]$ (Eso es sólo dos descansos). Si el error es suficientemente pequeño, deténgase.
De lo contrario, agregue un descanso $c$ (por ejemplo, en el medio) y calcule la mejor aproximación $f_1$ . Si el error es suficientemente pequeño, deténgase.
De lo contrario, compare el error de $f_1$ en $[a,c]$ y $[c,b]$ . Elija el subintervalo con el mayor error, digamos $[a,c]$ y agregue una nueva ruptura en $[a,c]$ . Calcule la mejor aproximación $f_2$ . Si el error es suficientemente pequeño, deténgase.
De lo contrario, ... y así sucesivamente

N74 · Answer 4

No sé si converge al mínimo, pero una vez hice una función para "convertir" puntos GPS en una carretera.

Para ello tomé una región rectangular cuyo lado es el doble de la tolerancia acumulando puntos siempre que el rectángulo pudiera contenerlos a todos. En este punto comencé con otro rectángulo que contenía al menos el último punto del rectángulo anterior.

Minimizar el número de puntos en una aproximación lineal por partes

Eric Leibenguth

usuario856

usuario856

Eric Leibenguth

anton sherwood

LinAlg

Respuestas (4)

Cabina G

anton sherwood

anton sherwood

usuario251257

N74

¿Encontrar el círculo más pequeño que encierra todos los puntos dadas sus coordenadas x, yx, yx, y?

Elipsoide de mejor ajuste

Cómo encontrar la pendiente de ciertas líneas que coinciden con puntos aleatorios

Variación de TSP - Nodos de revisión

Complejidad del algoritmo: bucle for dentro del bucle while; decreciendo por el factor 2

¿Cómo te acercas al completar el cuadrado?

¿Aplicaciones de la Integral Exponencial?

Demostrando la aproximación de forma cerrada de la relación de recurrencia Xk=kXk−1Xk=kXk−1X_k=\frac{k}{X_{k-1}}

¿Cuál es la complejidad del tiempo cuando se muestrean uniformemente las entradas bbb sin reemplazo de las entradas nnn?

Construir un conjunto de números para que las particiones de los 3 elementos tengan diferentes sumas de subconjuntos