Minimieren Sie die Anzahl der Punkte in einer stückweisen linearen Annäherung

Question

Minimieren Sie die Anzahl der Punkte in einer stückweisen linearen Annäherung

Algorithmen
Rückschritt
Mathematik
Optimierung
Annäherung
maschinelles Lernen

Eric Leibenguth

Ich habe $m$ Datenpunkte $(x_i,y_i)$ in einem bestimmten Intervall. Ich möchte eine stückweise lineare Funktion finden $f(x)$ die sich diesen annähern $m$ Punkte mit einer Mindestpunktzahl $n$ so dass mein Näherungsfehler unterhalb einer Toleranz liegt $\epsilon$ .

Mein $m$ Punkte:

Die Funktion $f$ ist eine stückweise lineare Funktion, die mit definiert ist $n$ Punkte $(x_a^{i},y_a^{i})$ . Für $n=4$ , es würde so aussehen:

Näherungsfehler:

\frac{1}{M} \sum_{1 \leq ich \leq M} (j_{ich} - F (X_{ich}))^{2} \leq ϵ

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

Um dieses Problem zu lösen, muss ich etwas finden $n$ , eine Möglichkeit, den optimalen Punktesatz zu erhalten $(x_a^{i},y_a^{i})$ . Ich kann versuchen, meinen Näherungsfehler mit Gradientenabstieg zu minimieren, aber die Funktion ist nicht konvex, sodass sie möglicherweise nicht zum globalen Optimum konvergiert.

Wenn ich den vorherigen Schritt löse, kann ich den Algorithmus einfach einfach ablaufen lassen $n=1,2,3,...$ und höre auf, wenn mein Näherungsfehler unterschritten wird $\epsilon$

Ich höre mich nach einem ziemlich häufigen Problem an, für das es vielleicht schon eine Lösung gibt. Kennen Sie einen oder können Sie einen Lösungsansatz für dieses Problem vorschlagen?

Benutzer856

Der Douglas-Peucker-Algorithmus kann verwendet werden, um eine solche Näherung zu finden

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

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

Benutzer856

Damit umgehen

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

$\sum_i (y_i-f(x_i))^2$ Stattdessen könnten Sie einen vollständigen Graphen auf Knoten betrachten

{1, 2, \dots, m}

$\{1,2,\ldots,m\}$ ; jede Kante zuordnen

(i, j)

$(i,j)$ Kosten

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$ , Wo

f_{i j}

$f_{ij}$ ist die lineare Näherung zwischen

(x_{i}, y_{i})

$(x_i,y_i)$ Und

(x_{j}, k_{j})

$(x_j,k_j)$ ; dann finden Sie den kürzesten Weg von

1

$1$ Zu

m

$m$ nur verwenden

n - 1

$n-1$ Kanten.

Eric Leibenguth

@Rahul, danke! Ich denke, der Douglas-Peucker-Algorithmus könnte tatsächlich eine geeignete Lösung für mein Problem sein. Ich mag auch sehr Ihren graphbasierten Ansatz für den quadratischen Fehler. Beachten Sie, dass bei beiden Ansätzen ein Nachteil darin besteht, dass die

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

$(x_a^{i},y_a^{i})$ werden unter den ausgewählt

(x_{i}, y_{i})

$(x_{i},y_{i})$ , was vielleicht nicht optimal ist. Ich denke auch, dass ich die Douglas-Peucker-Lösung verwenden könnte, um einen Gradientenabstiegsalgorithmus zu initialisieren, der viel näher am globalen Optimum liegt ...

Anton Scherwood

Mir scheint, dass Douglas-Peucker durch genaue Anpassung an bestimmte Eingabepunkte keine besseren Lösungen findet, die alle Punkte verfehlen (wie in der Abbildung von OP).

LinAlg

Dies kann als gemischtes ganzzahliges Optimierungsproblem formuliert werden, das begrenzt gelöst werden kann

n

$n$

Antworten (4)

Minimieren Sie die Anzahl der Punkte in einer stückweisen linearen Annäherung

Der Douglas-Peucker-Algorithmus kann verwendet werden, um eine solche Näherung zu finden $\max_i(y_i-f(x_i))\le\epsilon$ stattdessen.
Damit umgehen $\sum_i (y_i-f(x_i))^2$ Stattdessen könnten Sie einen vollständigen Graphen auf Knoten betrachten $\{1,2,\ldots,m\}$ ; jede Kante zuordnen $(i,j)$ Kosten $w_{ij}=\sum_{i<k<j} (y_k-f_{ij}(x_k))^2$ , Wo $f_{ij}$ ist die lineare Näherung zwischen $(x_i,y_i)$ Und $(x_j,k_j)$ ; dann finden Sie den kürzesten Weg von $1$ Zu $m$ nur verwenden $n-1$ Kanten.
@Rahul, danke! Ich denke, der Douglas-Peucker-Algorithmus könnte tatsächlich eine geeignete Lösung für mein Problem sein. Ich mag auch sehr Ihren graphbasierten Ansatz für den quadratischen Fehler. Beachten Sie, dass bei beiden Ansätzen ein Nachteil darin besteht, dass die $(x_a^{i},y_a^{i})$ werden unter den ausgewählt $(x_{i},y_{i})$ , was vielleicht nicht optimal ist. Ich denke auch, dass ich die Douglas-Peucker-Lösung verwenden könnte, um einen Gradientenabstiegsalgorithmus zu initialisieren, der viel näher am globalen Optimum liegt ...
Mir scheint, dass Douglas-Peucker durch genaue Anpassung an bestimmte Eingabepunkte keine besseren Lösungen findet, die alle Punkte verfehlen (wie in der Abbildung von OP).
Dies kann als gemischtes ganzzahliges Optimierungsproblem formuliert werden, das begrenzt gelöst werden kann $n$

G-Fahrerhaus · Answer 1

Ich würde das Problem folgendermaßen angehen.

Nehmen Sie das Intervall, das die ersten drei Punkte enthält. Berechnen Sie den Korrelationskoeffizienten $\rho$ .
- Wenn $\rho$ nicht gut genug ist, nehmen Sie nur die ersten beiden Punkte, markieren Sie sie als im 1. Intervall und untersuchen Sie die nächsten drei. - elf $\rho$ ziemlich gut ist, fügen Sie einen vierten Punkt hinzu und berechnen Sie den Koeffizienten neu; weiter bis $\rho$ bleibt gut;
Wiederholen Sie dies, bis Sie alle Punkte in zusammenhängende Intervalle mit guter Korrelation aufgeteilt haben.

Sie müssen nur überlegen, was Sie mit den Punkten an der Grenze der Intervalle tun:
- Sie können die Intervalle unzusammenhängend halten;
- oder man nimmt den letzten Punkt in die Berechnung der Korrelation für den nächsten wieder mit und überlappt so die Intervalle.

Anton Scherwood · Answer 2

Hier ist der Weg, der mir offensichtlich erscheint; Vielleicht weist jemand Weiser darauf hin, wie es ineffizient ist oder an perversem Input scheitert.

Betrachten Sie den zweidimensionalen Raum linearer Funktionen. Jeder Eingabepunkt definiert mit seinen Toleranzen ein Band akzeptabler Linien. Ein Schnittpunkt solcher Bänder ist ein konvexes Polygon.

Beginnen Sie also links, stapeln Sie die Beschränkungen, bis dieses Polygon verschwindet, und gehen Sie dann um eins zurück. Ihre erste Linie wird durch einen Punkt irgendwo in diesem Polygon dargestellt; Sie können auch seinen Schwerpunkt oder den Durchschnitt seiner Ecken verwenden.

Machen Sie es dann erneut, beginnend mit dem letzten Punkt, der von der ersten Zeile "bedeckt" wird. Dein $(x_a^2,y_a^2)$ ist natürlich der Schnittpunkt der ersten beiden Lösungsgeraden.

Es könnte interessant sein zu sehen, ob das Starten von rechts zu einem anderen Ergebnis führt.

(Meine ästhetische Präferenz wäre, alle maximal kompatiblen Untersequenzen zu verwenden, aber das ist nicht meine Frage.)

Bearbeiten: Dies ist die Hauptidee des folgenden Papiers und wird hier diskutiert

Kann dieses Konzept auf stückweise Polynome vom Grad n mit k stetigen Ableitungen erweitert werden?

Benutzer251257 · Answer 3

Es ist nicht einfach, weil die stückweise lineare Funktion nicht differenzierbar von den Unterbrechungspunkten abhängt (sie ist jedoch stetig). Und die Sache wird hässlich, wenn Sie die Anzahl der Pausen variieren.

Es ist viel einfacher, die beste Näherung für feste Unterbrechungen zu berechnen . Somit würde eine einfache Heuristik wie folgt aussehen:

Beginnen Sie mit der linearen besten Näherung $f_0$ auf sagen $[a,b]$ (das sind nur zwei Pausen). Wenn der Fehler ausreichend klein ist, stoppe.
Andernfalls fügen Sie eine Pause hinzu $c$ (zum Beispiel in der Mitte) und berechnen Sie die beste Annäherung $f_1$ . Wenn der Fehler ausreichend klein ist, stoppe.
Andernfalls vergleichen Sie den Fehler von $f_1$ An $[a,c]$ Und $[c,b]$ . Wählen Sie beispielsweise das Teilintervall mit dem größeren Fehler $[a,c]$ , und fügen Sie einen neuen Einbruch hinzu $[a,c]$ . Berechnen Sie die beste Näherung $f_2$ . Wenn der Fehler ausreichend klein ist, stoppe.
Ansonsten ... und so weiter

N74 · Answer 4

Ich weiß nicht, ob es auf ein Minimum konvergiert, aber ich habe einmal eine Funktion zum "Umwandeln" von GPS-Punkten in eine Straße erstellt.

Dazu habe ich einen rechteckigen Bereich genommen, dessen Seite das Doppelte der Toleranzkumulationspunkte ist, solange das Rechteck alle enthalten könnte. An diesem Punkt begann ich mit einem anderen Rechteck, das zumindest den letzten Punkt des vorherigen Rechtecks enthielt.

Minimieren Sie die Anzahl der Punkte in einer stückweisen linearen Annäherung

Eric Leibenguth

Benutzer856

Benutzer856

Eric Leibenguth

Anton Scherwood

LinAlg

Antworten (4)

G-Fahrerhaus

Anton Scherwood

Anton Scherwood

Benutzer251257

N74

Finden Sie den kleinsten Kreis, der alle Punkte mit ihren x,yx,yx,y-Koordinaten umschließt?

Am besten passendes Ellipsoid

So finden Sie die Steigung bestimmter Linien, die mit zufälligen Punkten übereinstimmen

Variation von TSP - Knoten erneut besuchen

Algorithmuskomplexität - For-Schleife innerhalb einer While-Schleife; um den Faktor 2 abnehmen

Wie gehen Sie vor, wenn Sie das Quadrat vervollständigen?

Anwendungen des Exponentialintegrals?

Beweis der geschlossenen Approximation der Rekursionsrelation Xk=kXk−1Xk=kXk−1X_k=\frac{k}{X_{k-1}}

Wie hoch ist die zeitliche Komplexität, wenn bbb-Einträge ohne Ersatz von nnn-Einträgen einheitlich abgetastet werden?

Konstruieren einer Menge von Zahlen, so dass alle 3-Element-Partitionen unterschiedliche Teilmengensummen haben