Algorithmus gesucht für Reduktion von Messdaten

[Daniel]

Moin,

ich suche nach einem Stichwort. Und zwar suche ich einen Algorithmus, der mir Messdaten glättet.

Ich habe eine Reihe von Messdaten und diese diese bilden eine Art Kurve, die monoton wächst. (Jeder Wert ist also größer oder gleich seinem Vorgänger.) Nun ist mir bei diesen Daten nicht jede einzelne Ausprägung wichtig, ich möchte -bildlich gesprochen- eine "Treppe" darüberlegen. Wichtig sind für mich dann genau die Stellen, an denen einen Treppenstufe beginnt.

Im Anhang ein Beispiel, welches ich durch eine Kombination Mittelwertbildung und Rundung erreicht habe. Die rote Linie repräsentiert die Messdaten, die blaue Linie meine reduzierte Datenmenge. Allerdings kann ich das Ergebnis so qualitativ nicht bewerten und sinnvolles automatisieren erscheint mir auch nicht ganz trivial.

Ich kann unmöglich der erste Mensch sein, der sowas machen will und nun möchte ich wissen, die die Anderen das genannt haben. ;-) Ein Stichwort für einen hier anwendbaren Algorithmus würde mir reichen.

[TheAn00bis]

In der Mathematik ist das Stichwort Interpolation, vielleicht hilft dir das, vielleicht aber auch nicht. ;)

[marabu]

Hallo Daniel,

suchst du eine Trendkurve (lineare Regression) oder ist nicht doch eine differenzielle Wachstumskurve aussagefähiger?

Grüße vom marabu

[alzaimar]

Er will doch die 'Treppen' behalten, da bringt eine Interpolation oder Regression leider gar nichts.

Ich habe es so gelöst:

Ich habe eine Liste von Punkten P.
Jetzt nehme ich aus P irgend einen Punkt P[i] weg.
Über die verbliebene Punkteschar P[1..i-1, i+1..n] kann ich einen kubischen Spline legen. Zwischen den Punkten P[i-1] und P[i+1] (P[i] ist ja weg) liegt ein Spline-Segment. Dieses Spline-Segment ist einfach nur ein Polynom 3.Grades. Es läuft von P[i-1].x bis P[i+1].x und berührt die Punkte p[i-1].y und p[i+1].y....
So... es läuft auch durch P[i].x. Wenn der Y-Wert des Splines an diesem Punkt sehr nahe an P[i].y liegt, dann benötigen wir den Punkt P[i] nicht, denn er wird hinreichend genau durch unsere Splinefunktion beschrieben. Der Punkt P[i] ist also 'überflüssig'.

Super, wir haben nun aus der riesigen Menge P einen Punkt entfernt, ohne dass sich der Graph (egal wie der aussieht) ändert. Das wiederholen wir nun so lange, bis es keinen 'überflüssigen' Punkt mehr gibt.

Auf diese Weise haben wir genau solche Messwertreihen auf die 'relevanten' Punkte reduziert. Bereiche, in denen sich alle Punkte auf einer flatten Kurve befinden, werden einfach weggekürzt. Peaks, Treppen etc., also alles, was wirklich wichtig ist, bleibt dagegen erhalten.

Man kann das Verfahren natürlich optimieren, in dem man sich z.B. nur Segmente mit 6-8 Punkten anschaut, aber damals war ich zu faul dazu, denn das Ergebnis war, wie oben beschrieben, sehr gut und auch relativ fix (auf einem 10Mhz 68000 mit HP-Basic), also sollte das mit einem PC doch wirklich schnell gehen.

Kubische Splines sind sehr einfach zu berechnen (Gleichungssystem erstellen, Gauß rüberlaufen lassen, fertig). Googel mal danach.

[Daniel]

Jo - besten Dank für die Anregungen.
Ich schaue mal, wie ich das alles umsetzen kann.