Programmiertechnik max finden zwei arrays

[Felixx]

Hallo,

ich stehe vor folgendem Problem: ich have zwei DatenArrays mit Werten. Diese sieht man in der Graphik unten. Nennen wir sie mal Blau und Rot.

Jetzt möchte ich folgendes schaffen:

die DatenWerte von Blau sollen so weit nach verschoben werden, dass sie möglichst komplett unter dem Daten von Rot stehen, d.h. die blaue Linie sollte nach Möglichkeit unterhalb der roten Linie sein. Ziel ist es, dass der Unterschied zwischen rot und blau minimal ist.

Wie kann ich das bewerkstelligen?

Ich dachte irgendwie an in das blaue Array an Beginn des Arrays eine 0 einfügen und dann zu die einzelnen Positionen der beiden Arrays vergleichen und schauen, wie groß der Abstand wird, dann wieder eine 0 einfügen usw.

Aber das kommt mir irgendwie sehr ineffektiv vor. Wir würde man das am Besten machen? Falls die Frage nach der Funktion aufkommt, die die Werte generiert: es gibt sie nicht. Die Werte werden von Messfühlern aufgezeichnet.

Ich würde mich freuen, wenn mir jmd n Tipp oder Anregung geben kann, wie ich realisieren kann. Programmiersprache ist zunächst einmal egal. Da man das da quasi dann in jede Sprache portieren kann.

Vielen Dank für eure Hilfe 😉

[JürgenB]

Hallo,

ich glaube, hier könnte die Kreuzkorrelation das Mittel der Wahl sein.

Gruß
Jürgen

[Rolf b]

Wenn ich mir die diskrete Kreuzkorrelation in der Wikipedia angucke, wird da einfach das Produkt der Messwerte zu den Zeitpunkten t und t+δ aufsummiert, um ein Maß für die Korrelation zu bekommen. Allerdings kann nicht sagen, wirklich verstanden zu haben, was mir der Artikel und sein Umfeld sagen wollen, da ist zu viel an Fachbegriffen und Hintergrundtheorie als bekannt vorausgesetzt.

Wie auch immer - es sieht so aus als würde die Kreuzkorrelation ein Maß für die Übereinstimmung liefern, und man muss den Kreuzkorrelationswert maximieren, um die beste Überdeckung zu finden. Das bedeutet, mehrere Verschiebungen auszuprobieren und die beste auszuwählen - und bei einem Messbereich von 1000 Punkten klingt das sehr aufwändig. Du kannst nicht alle möglichen Verschiebungen ausprobieren.

Gunnars Vorschlag mit dem Median ist mir nicht ganz klar - du hast Messwerte zu bestimmten Zeitpunkten, und der Median der Zeitintervalle wäre im Wesentlichen die Mitte des Intervalls. Der Median der gemessenen Werte hilft Dir meiner Meinung nach nicht. Was Dir aber helfen dürfte, wäre eine Vorab-Analyse, in welchen Intervallen $rot und $blau von null verschieden sind. Die Differenz vom Mittelpunkt dieser beiden Intervalle nimmst Du als Ausgangswert für δ. In dem von Dir gelieferten Bild wäre diese Differenz bereits 0 - hast Du da schon normiert? Oder sind deine Messungen so geartet, dass das immer der Fall ist?

Wieauchimmer - Wenn Du zwei Arrays hast mit je X Einträgen, die den Messwert zum Zeitpunkt $$t_i$$ beschreiben, dann kannst Du Dir eine Funktion schreiben, die die Kreuzkorrelation der beiden Tabellen mit einer gegebenen Verschiebung bestimmt. Grundannahme für die folgende Funktion ist, dass $rot und $blau den gleichen count haben (sprich: über das gleiche Intervall aufgezeichnet wurden)

function korreliere($rot, $blau, $delta)
{
   // Negatives Delta: $rot und $blau vertauschen und mit -$delta arbeiten.
   if ($delta < 0)
      return korreliere($blau, $rot, -$delta);

   // Zugriff erfolgt bei $blau auf Position $i+$delta, deshalb $delta positionen vor dem Ende von
   // $blau aufhören. Wenn $rot um mehr als $delta Werte kürzer ist als $blau (sollte nicht seinm
   // aber sicher ist sicher), noch früher aufhören.
   $bMax = min(count($rot), count($blau) - $delta);

   $corr = 0;
   // Kreuzkorrelation mit Verschiebung $delta bestimmmen
   for ($i=0; $i<$bMax; $i++)
      $corr += $rot[$i]*$blau[$i+$delta];

   return $corr;
}

Nun fängst Du an zu probieren. Erstmal mit großen Verschiebungen und dann näherst Du Dich an. Von oben hast Du ein Basis-Delta (oder Du nimmst 0).

Ich würde einen Wert $span festlegen, der eine Zweierpotenz darstellt und etwa ein Viertel deiner Messintervalle darstellt. Dann bestimmst Du die Kreuzkorrelationen für $delta = $basisDelta-2*$span, $basisDelta-$span, $basisDelta, $basisDelta+$span und $basisDelta+2*$span und hältst fest, für welches $delta die größte Korrelation herausgekommen ist. Das ist dein neues Basis-Delta.

Nun halbierst Du $span und wiederholst die Nummer, bis $span eine bestimmte Schwelle unterschreitet. Das kann 1 sein, aber eventuell kannst Du schon vorher aufhören, wenn Dir eine Näherung genügt.

Bei 1000 Messpunkten könntest Du also mit $span=256 starten, halbierst Dich über 128, 64, 32, 16, 8, 4 und 2 bis zur 1 hinunter (9 Span-Werte) und berechnest pro Stufe 5 Korrelationen. Insgesamt 45 Korrelationsberechnungen, und du hast einen Delta-Raum von -512 bis +512 abgetastet.

Um die Korrelationsberechnung zu beschleunigen, kannst Du auch mit einer vergröberten Auflösung arbeiten. Du bestimmst den Mittelwert von je 8 Messwerten (oder 4 oder 16) und erzeugst so zwei Arrays $grobrot und $grobblau, die deutlich kleiner sind. D.h. die Korrelationsschleife ist kürzer, und der $span beginnt bei einer kleineren Zweierpotenz (mit dem Effekt, dass Du weniger Halbierungsstufen hast).

Das Delta, dass du am Ende herausbekommst, musst Du dann natürlich mit deiner Aggregationsstufe wieder multiplizieren. Vielleicht reicht das schon völlig hin. Wenn nicht, machst Du noch eine Fein-Überlappung mit den Ausgangsarrays, kannst aber jetzt mit einem viel kleineren $span beginnen.

Rolf

[Gunnar Bittersmann]

@@Rolf b

Gunnars Vorschlag mit dem Median ist mir nicht ganz klar - du hast Messwerte zu bestimmten Zeitpunkten, und der Median der Zeitintervalle wäre im Wesentlichen die Mitte des Intervalls.

Nein. Der Median Md ist^[1] die Stelle (hier: der Zeitpunkt), die die Fläche unter der Kurve in zwei Hälften teilt. D.h. wenn du dort eine vertikale Linie ziehst, ist die Fläche unter der Kurve links von der Linie (von −∞ bis Md) gleich der Fläche unter der Kurve rechts von der Linie (von Md bis +∞).

Wenn du die Mediane für Rot und Blau bestimmst und dann Blau so verschiebst, dass diese vertikalen Linien zusammenfallen, dann sollte das schon ganz gut passen.

LLAP 🖖

---

1. bei einer stetigen Verteilung ↩︎

[Rolf b]

Ach, dieser Median :)

Okay, das ist bestimmt ein guter Ansatz.

Rolf

[Gunnar Bittersmann]

@@Felixx

Ziel ist es, dass der Unterschied zwischen rot und blau minimal ist.

Wie kann ich das bewerkstelligen?

Wieviel Rechenaufwand willst du betreiben? Brauchst du wirklich den optimalen Wert für die Verschiebung oder reicht dir ein guter Wert?

Wenn gut gut genug ist, könnte es reichen, die Mediane für beide Datenmengen zu bestimmen und dann um deren Differenz zu verschieben.

alls die Frage nach der Funktion aufkommt, die die Werte generiert: es gibt sie nicht. Die Werte werden von Messfühlern aufgezeichnet.

Doch, wenn du jedem Zeitpunkt genau einen Messwert zuordnest, dann ist das eine Funktion.

LLAP 🖖

[Felixx]

Hi,

ein "guter" Wert würde reichen. Es muss nicht der optimale Wert sein.

LG

[JürgenB]

Hallo,

dann würde ich es mal mit dem Median probieren. Ein Sortierer ist entweder schon Teil der Programmiersprache oder du findest ihn im Internet.

Zum Rechenaufwand: Die Kreuzkorrelation skaliert mit dem Quadrat der Anzahl n der Messwerte. Der Rechenaufwand beim Sortieren skaliert zwischen Quadrat und n mal log(n), also etwas günstiger.

Gruß
Jürgen

[Felixx]

irgendwie steh ich immer noch auf dem Schlauch.

Wie meint ihr das mit dem Median & Sortieren?

Die Reihenfolge der Werte ist stets fest. Ich kann nur die komplette Datenreihe blau nach rechts oder links schieben;

(Sprache wird R Studio werden)

[TS]

Hello,

Die Reihenfolge der Werte ist stets fest. Ich kann nur die komplette Datenreihe blau nach rechts oder links schieben;

definiere bitte "Schieben".

Meinst Du damit, dass Du nur einen absoluten Betrag auf die X-Größe addieren/subtrahieren darfst, oder darf die Kurve auch geschert werden dabei? Das würde passieren, wenn die Bodenpunkte (Y=0) der Kurven stehen bleiben würden und nur die Punkte mit Y>0 um unterschiedliche Werte in X-Richtung verschoben werden dürften. Sowas macht man technisch z. B. bei der Abstimmung von Schwingkreisen.

Liebe Grüße
Tom S.

[Felixx]

Hallo,

ich meinte folgendes damit:

Die Werte für Y aus der blauen Datenreihe werden um eine gewisse Anzahl von X-Werten nach rechts verschoben:#

Beispiel: vorher: x1 -> 2 x2 -> 3 x3 -> 4 … nach der "Schiebung" x1 -> 0 x2 -> 2 x3 -> 3 x4 -> 4 ...

[Gunnar Bittersmann]

@@Felixx

irgendwie steh ich immer noch auf dem Schlauch.

Wie meint ihr das mit dem Median & Sortieren?

So wie es in der Wikipedia steht.

Die Reihenfolge der Werte ist stets fest.

Das soll heißen, die Werte sind bereits (zeitlich) geordnet? Dann erübrigt sich das Sortieren.

(Sprache wird R Studio werden)

Sollte mich wundern, wenn R nicht schon eine Funktion für den Median bereitstellen würde. Kurz nachgeschaut: ja (Quantilsfunktion).

LLAP 🖖

[Gunnar Bittersmann]

@@JürgenB

Zum Rechenaufwand: Die Kreuzkorrelation skaliert mit dem Quadrat der Anzahl n der Messwerte.

Aber damit hast du erstmal nur den Wert Rₓᵧ(τ) für ein bestimmtes τ. Dasjenige τ zu finden, für das Rₓᵧ(τ) maximal wird, dürfte etwas aufwändiger werden.

LLAP 🖖

[JürgenB]

Hallo Gunnar,

ich würde die Kreuzkorrelationsfunktion für alle Verschiebungen berechnen. Das Maximum dieser Funktion ist dann die Stelle, an der die beiden Messreihen sich am „ähnlichsten“ sind. Um diesen Wert würde ich dann eine der beiden Reihen verschieben.

Aber deine Idee mit dem Median sollte Felixx zuerst ausprobieren.

Gruß
Jürgen

[Rolf b]

Eure Median-Idee begreife ich nicht. Wenn sie funktioniert, kann man damit eine erste Näherung finden und dann meinen Halbierungsalgorithmus von oben nachschalten - aber funktionieren muss sie erstmal.

t     rot(t)    blau(t)

0       0          2
1       6          7
2      12         16
3      15         11
4      17          4
5      11          1
6       7          0

Was wäre euer Median (=mittlerer Wert) und was fängt man dann damit an?

Rolf

[Gunnar Bittersmann]

@@Rolf b

t     rot(t)    blau(t)

0       0          2
1       6          7
2      12         16
3      15         11
4      17          4
5      11          1
6       7          0

Was wäre euer Median (=mittlerer Wert) und was fängt man dann damit an?

Für Rot: 4, für Blau 2. Also Blau um 4 − 2 = 2 nach rechts schieben.

LLAP 🖖

[Rolf b]

Zum Rechenaufwand: Die Kreuzkorrelation skaliert mit dem Quadrat der Anzahl n der Messwerte. Der Rechenaufwand beim Sortieren skaliert zwischen Quadrat und n mal log(n), also etwas günstiger.

Wieso? Für ein $$\tau$$ hast Du genau eine Schleife, ohne Schachtelung. Ich würde sagen, dass EIN Korrelationswert in $$O(n)$$ berechenbar ist. $$O(n^2)$$ hast Du, wenn Du die Korrelationen für alle möglichen Verschiebungen bestimmen willst (unter Vernachlässigung des Umstandes, dass wegen endlich langer Arrays die Laufzeit für eine Korrelationsberechnung um so kürzer wird, je größer das Delta ist) - deshalb ja auch mein Vorschlag mit der $span-Halbierung, dann kommst Du wieder bei $$O(n \cdot \log n)$$ heraus.

Rolf

[JürgenB]

Hallo Rolf,

ob deine Optimierung mit der Intervallhalbierung funktioniert, kann ich ohne Tests weder bestätigen noch widerlegen. Aber Felixx soll erst mal prüfen, welches Verfahren die bessere Lösung liefert, danach kommt dann das Optimieren.

Gruß
Jürgen

[Felixx]

Hi,

so ich hab es erst mal "zu Fuß" gemacht, dh ich verschiebe in einer Schleife die blauen Werte und vergleiche darin, wie viele Werte unterhalb von rot liegen. Das funktioniert soweit.

Jetzt werde ich mal versuchen mich an die Optimierung zu machen ...

[JürgenB]

Hallo,

du solltest dir auf jeden Fall überlegen, wie du den „optimalen Überlapp“ der beiden Messreihen bewertest, was aus dem „warum wird das gemacht“ folgen sollte. Ich denke, der Rest ergibt sich dann.

Gruß
Jürgen

[Rolf b]

D.h. du verwendest andere Kriterien für "blaue Kurve liegt gut", als hier unterstellt wurden. Dein Vorgehen sucht keine maximale Übereinstimmung, sondern möglichst viele Punkte der blauen Kurve, die unterhalb der roten Kurve liegen.

Das kann zu merkwürdigen Ergebnissen führen.

• ein schmaler blauer Blipp hat ein Intervall, innerhalb dessen er unter einen roten BLOPP passt
• ein breiter, flacher blauer Fladen, der doppelt so breit ist wie ein roter Zuckerhut, kann sich mit seinem rechten Ausläufer komplett unter die rote Kurve schieben, aber mit seinem Maximum noch lange nicht unter dem Zuckerhut liegen. Das wird optisch nicht das sein, was Du willst.

Da Du aber auf die Randbedingungen, die für deine Messwerte gelten, nicht eingegangen bist, kann ich nicht sagen ob das für deinen Anwendungsfall von Bedeutung ist.

Qapla’!
Rolf