Algorithmen zur Abhängigkeitserkennung

Wissenschaft Informatik
#1

Hallo,

ich suche einen Algorithmus der folgendes bewerkstelligen kann.

Ausgangsposition:

5 Arrays (a - e) von Werten (beispielshaft 5)
diese Arrays beinhalten reine Zahlenwerte. Jeweils ca. 500 Einträge.

Nun würde ich gerne prüfen welche Arrays im Zusammenhang stehen.
Steigt a steigt auch b oder steigt b steigt auch e.
Genau so mit fallend.
Oder gegengesetzt. steigt a fällt c usw.

wichtig wäre mir die laufzeit.
Da ich jedem mit jedem vergleichen will/muss geht das bei 5 noch aber wenn ich strattdessen 50 Arrays habe wird es kritisch.

Hat jdm Vorschläge ?

Meine Ideen:
Zur einzelnen Wertprüfung zwischen 2 Arrays
Ich denke zur Zeit daran nicht die 500 Werte einzeln zu nehmen sondern sagen wir 50 zusammenzufassen und den Mittelwert zu bilden.
Und daraus einen Trend.
Dann ist der vergleich von 2 Array auf nur 10 vergleiche beschränkt.
Aber das wäre zu ungenau. In einem Array schwankt ein der Wert im anderen ist er konstant.
Der Trend ist bei beiden gleich.

Irgendwie fällt mir nichts richtiges ein außer wirklich jeden Wert mit jedem Wert zu vergleichen und das für jedes Array mit jedem Anderen.

Laufzeit wäre:

  • 50! Arrayvergleich
  • pro Arrayvergleich 500 Wertvergleiche
    macht = O = 50! * 500
    Und das ist definitv zu viel !

(Ok - worst case - so viel werden es nicht da der wertvergleich abgebrochen wird wenn gemerkt wird das es nicht abhängig ist.)

mfg
Martin

#2

Moien

Nun würde ich gerne prüfen welche Arrays im Zusammenhang
stehen.

Definiere diese Zusammenhänge nochmal genauer.

Steigt a steigt auch b oder steigt b steigt auch e.

Über alle x Array getrennt laufen und feststellen ob die monoton steigen/fallen. Die x Resultate vergleichen. Dabei ist dann die Anzahl der Werte in den Arrays egal.

cu

#3

Servus,

Moien

Nun würde ich gerne prüfen welche Arrays im Zusammenhang
stehen.

Definiere diese Zusammenhänge nochmal genauer.

Aus Messungen werden Array erstellt.
Sensor 1 bis Sensor 5.
Die holen ihre Werte.
Es entsteht für jeder Sensor ein Array mit Werten.

Jetzt möchte ich wissen ob Sensoren gleiches Verhlten zeigen bzw von einem Faktor beeinflußt werden.
Z.B. Temp steigt.
Dann steigen im Array 1 die Werte an und im Array 2.
Damit sind die beiden „Anhängig“ bzw zeigen gleiches Verhalten.
Die anderen 3 Array ändern ihre Werte nicht. Fallen raus.

Hoffe ich habe es einigermaßen verständlich erklärt.

Steigt a steigt auch b oder steigt b steigt auch e.

Über alle x Array getrennt laufen und feststellen ob die
monoton steigen/fallen. Die x Resultate vergleichen. Dabei ist
dann die Anzahl der Werte in den Arrays egal.

naja kann sein das 2 monoton steigend sind aber zu unterschiedlichen zeiten.
Bsp. Zeit gemessen 10 sec.
In Array 1 steigen die werte zwischen 0 und 5 sec und in Array 2 von 5 bis 10 sec.
Beide sind monoton steigend aber leider nicht gleichzeitig.
Das wäre auch wichtig.

cu

Ganz Problematisch ist auch wenn ein Wert steigt dann gleich bleibt und dann fällt.
Aber der Fall kann unberücksichtigt bleiben vorerst.

Der häufigste Fall ist ein Wert steigt und bleibt dann gleich.

Evt noch ein Bsp.
Sensor 1 - Array von 0 - bis 150 bleibt dann gleich
Sensor 2 - Array von 0 - bis 300 bleibt dann gleich
Sensor 3 - Array konstant 30
Sensor 4 - Array konstant 300
Sensor 5 - Array von 100 - 5 bleibt dann gleich

Aussagen wären:
Sensor 1 und 2 zeigen selbes verhalten (zeitgleich steigend)
Sensor 3 und 4 zeigen selbes verhalten (konstant)
Sensor 5 zeigt Verhalten mit 1 und 2 (zeitgleich sinkend)

ich glaube heute mach ich nix mehr.
mein schädel brummt.

#4

Idee !!!
Ganz neu:

jedes Array Codieren. :smile:

Jedes Element statt dem Wert, ein Zahlwert(Code) der angibt ob der Wert gestiegen oder gefallen oder konstant ist.

Bsp.
Array tmp = new (0,0,2,2,30,35,40,60,80,80,80)
dann wäre die codierung: 0,0,1,0,1,1,1,1,1,0,0
und das 2te Array
Array tmp2 = new (0,0,20,20,300,305,400,600,800,800,800)
dann wäre die codierung: 0,0,1,0,1,1,1,1,1,0,0

gleiches verhalten !

Array tmp3 = new (0,0,20,20,20,20,20,20)
dann wäre die codierung: 0,0,1,0,0,0,0,0,0
Array tmp4 = new (20,20,10,0,0,0,30,30)
dann wäre die codierung: 0,0,-1,-1,0,0,1,0

dann käme es auf den reinen vergleich der codes an.

Wie findet Ihr das ?

#5

boing
ok viel vereinfacht das nicht.

ich muß durch jedes array und durch jeden wert.

und dann habe ich 50 codes die wieder jeder mit jedem verglichen werden muß.
und jetzt bräuchte man wieder einen algo. der schnell vergleicht.

ich glaub das war evt doch nicht so gut aber ich habe meinen beitrag trotzdem mal drin gelassen und nicht gleich gelöscht.

mfg
Martin

#6

Moien

Definiere diese Zusammenhänge nochmal genauer.

Aus Messungen werden Array erstellt.
Sensor 1 bis Sensor 5.
Die holen ihre Werte.
Es entsteht für jeder Sensor ein Array mit Werten.

D.h. der Wert für den Zeitpunkt x steht immer an der Stelle array[x]? Dann musst du schonmal die ersten Werte nicht mit den letzten Werten aus dem Array vergleichen.

  1. Punkt bei Messwerten: glätten. Messfehler müssen raus. Also B-Spline durchlegen oder Mittelwerte bilden oder kreativ mit Interpolation arbeiten. Und mit Hysteresen arbeiten. Nicht auf den Rohdaten arbeiten sonst werden Messreihen wie

29.95, 30.01, 29.99, 29.97, 30.00, 29.99,…

alles über den Haufen werfen.

Dann ein Suchfenster festlegen. Nur wenn die Werte in 2 Arrays über einen Zeitraum von x Werten steigen macht eine Aussage Sinn. Diese Fenster mit http://de.wikipedia.org/wiki/Korrelation resp. http://de.wikipedia.org/wiki/Kreuzkorrelation auswerten.

cu

#7

Jetzt möchte ich wissen ob Sensoren gleiches Verhlten zeigen
bzw von einem Faktor beeinflußt werden.
Z.B. Temp steigt.
Dann steigen im Array 1 die Werte an und im Array 2.

Hallo,

was du suchst ist Korrelations-Berechnung. Such mal unter dem Stichwort weiter, es müsste eine ganze Theorie dazu geben und wahrscheinlich auch Software.

Gruss Reinhard

#8

Kovarianz Matrix
Hi,

hierzu berechnet man eine Kovarianzmatrix. Stell Dir N Punkte in je M Arrays als eine Punktwolke in einem M-Dimensionalen Koordinatensystem vor. Ist die Punkwolke „ungleichmäßig“ geformt, so gibt es Korrelationen, dh. die Werte eines Arrays hängen statistisch von den Werten eines anderen Arrays ab. Die Kovarianzmatrix enthält die paarweisen Korrelationen jedes Arrays mit jedem anderem Array. Die Varianz eines Arrays ist ein Diagonalelement, die Varianz „zwischen“ zwei Arrays ist dann an entsprechend anderer Stelle in der Matrix.

Genaueres auch zB kugeln unter „principal component analysis“ und „Korrelationsanalyse“.

// Kovarianzmatrixberechnung:
double mean[dimensions];
double stddev[dimensions];
double cov_mat[dimensions][dimensions];

for (m=0; m