Kniffliges Statistik-Problem (Distanzmaße)

[YanniH]

Tach Leute,

ich hänge an einer etwas kniffligen Aufgabe und hoffe auf Eure Unterstützung.

Ich habe 1-N Objekte mit X Variablen als Ausprägung, z.B.:

[Auto] wird durch folgende Attribute charakterisiert:
{Farbe, Leistung, Gewicht, Zylinder}

Die Anzahl der Objekte nimmt mit der Zeit immer mehr zu; ich rede hier nicht von einigen Tausend sondern später mehrere (hundert) Millionen bis Milliarden Entries, wobei die Merkmalsausprägungen konstant von der Anzahl bleiben und metrisch skaliert sind (jeweils von 0 bis 9).

Nun müssen nachts per Batch entsprechende Ähnlichkeitsmaße berechnet werden; hierzu wird die Minkowski-Metrik mit r = 2 (eukl. Distanz) benutzt (s. http://www.statistics4u.com/fundstat_germ/cc_distance_meas.html)

So, programmatisch habe ich das ganze bereits umgesetzt, d.h. für eine Anzahl von n = 100 oder n = 10000 funktioniert das ganze einwandfrei.

Das Problem liegt jetzt natürlich darin, dass die Matrix der Distanzmaße N X N Zeilen bzw. Spalten groß wird, da diese Matrix symmetrisch ist.

Ich hab das mal vesucht auf die Spitze zu treiben: Auf einem 32 Bit-System allokiert Java für mich 1,5 GB Arbeitsspeicher.

Jede Spalte in der Matrix (32-buchstabiger hash-Wert (MD5)) nimmt jetzt 32 Byte ein; da die Matrix symmetrisch ist also 64 Byte und für die Ähnlichkeiten habe ich mal maximal 4 Byte angenommen; heißt pro Spalte und Zeile fallen 68 Byte an.

Wenn mir im Speicher 1610612736 Bytes (1,5 GB) zur Verfügung stehen und ich davon ausgehe, dass meine Matrix nach der Virtual Machine (ich arbeite in Java, aber auch in C++ wäre das Problem ähnlich, natürlich mit leichten oder größeren Verschiebungen) vllt. 1,45 GB nutzen kann, stehen mir 1556925644,80 Byte zur Verfügung.

So, das ergibt maximal eine 228.959.653 x 228959653 Matrix (eventueller programmatischer Overhead nicht mit einberechnet).

Das sind Pi mal Daumen max. 228 Millionen Einträge; Abgesehen von einer miesen Performance müßte ich dazu in der Lage sein, deutlich mehr Distanzmaße zu speichern.

Wie würdet ihr das regeln? Gibt es dafür sowas wie best practices?

Danke schonmal vorab und einen schönen Samstag abend!

 

[sumpfmonsterjunior]

Muss denn die komplette Matrix permanent im Speicher verfügbar sein?
Falls nicht könntest Du sie in einer Datenbank abspeichern (zb sqlite) und dann den Zugriff auf die Werte per Abfrage holen.

Gruß, SMJ

 

[YanniH]

Das ist das Problem: Die Matrix ist ein Ditributed Object und wird verteilt aufgerufen - und nur einmal pro Nacht geupdated bzw. beim Systemstart erstellt.

Aber eine Clusterung der Matrix ist zwar denkbar, aber natürlich auch sehr aufwändig :/ was ich vermeiden will.

 

[quarx]

Und diese Matrix enthält nur diese Distanzmaße? Warum muss sie überhaupt aufgestellt werden? Clusteranalyse?

 

[tomsie]

Und wenn sie symmetrisch ist, kannst du dir einiges sparen. Einfach die get- und set-Methoden entsprechend anpassen

 

[YanniH]

Nein, keine Cluster. Oha, ich glaube da könnte ich ins Buch der Rekorde mit kommen
Es werden Bestimmte Produkte charakterisiert - automatisch.
Ein Projekt an der Uni (Wirtschaftsinformatik) zur automatischen Produktkategorisierung; problem ist eben, dass der Testdatensatz mit der Zeit mitwächst

Klar, dass ich bei der symmetrischen Matrix einige Werte spare. hab jetzt die Nacht durchgemacht und eine serialisierte Form gewählt die jeweils unserialisiert wird, wenn entsprechende daten benötigt werden; Läuft sogar echt performant, obwohl es nen ganz guten Overhead beim unserialisieren gibt. Ich werd den algorithmus nochmalin C++ implementieren, da dürfte es deutliche Geschwindigkeitsvorteile geben )

 

[quarx]

Gib doch mal ein paar mathematische Details, noch ist mir gar nicht klar, was Du da überhaupt zu rechnen hast.

 

[tjp]

Wie würdet ihr das regeln? Gibt es dafür sowas wie best practices?

Datenbank für die Daten aufbauen, und darüber die Auswertung machen. Wenn das nicht geht 64Bit C++ Applikation schreiben und passenden Rechner nehmen. Es gibt Modelle mit 4TB linearem RAM am Markt. Das wird für Euch zu teuer, aber eine Workstation mit 32GB o.ä. sollte möglich sein.

 

[below]

Datenbank für die Daten aufbauen, und darüber die Auswertung machen. Wenn das nicht geht 64Bit C++ Applikation schreiben und passenden Rechner nehmen. Es gibt Modelle mit 4TB linearem RAM am Markt. Das wird für Euch zu teuer, aber eine Workstation mit 32GB o.ä. sollte möglich sein.

Richtig! Bei einem solchen Problem sollte man sich Gedanken über die Wahl der Waffen machen.

Java ist möglicherweise einfach nicht das richtige Werkzeug, um eine solche Aufgabe anzugehen.

Alex

 

[quarx]

Vielleicht sollte man auch, bevor man zu den Werkzeugen greift, erstmal das Problem auf Vereinfachungs- und Optimierungsmöglichkeiten untersuchen...

 

[below]

Selbstverständlich. Java ist nun wirklich nicht meine Spezialität, aber mir haben schon Leute, die sich angeblich damit auskennen, gesagt, das gerade für solche Probleme Java schlecht skalierbar sei.

Alex

 

[Tafkas]

Wieso muss eigentlich jeder Artikel mit jedem betrachtet werden. Kannst du evtl. noch ein paar Infos hier einstreuen?

 

[YanniH]

Ui, jetzt gehts ans Eingemachte

Also, der Algorithmus wurde ursprünglich in Java entwckelt wurde jetzt aber von mir nach C++ portiert, da sich java einfach als zu speicherhungrig herausstellte.

Zu dem, was wir machen wollen:

Wir möchten Gütemaße für den Fit von Distanz- bzw. Ähnlichkeitsmaße entwickeln.

So gehen wir vor:

Wir haben Produkte - egal welche. Können Wasserhähne aber auch Notebooks (MacBook Air? ) sein. Jede Produktgruppe hat entsprechende Eigenschaften, so z.B.:

Wasserhahn {Legierung, Preis, Norm, Mischbatterie} und Notebook {CPU, Speicher, HDD, Diagonale} etc.

(Die folgenden Ausführungen weichen jetzt evtl estwas von dem ab, was ich oben beschrieb - es hat sich eben Fallbedingt etwas geändert)

Nun möchten wir anhand bestimmter Kriterien folgendes herausfinden: Wenn ein Kunde einen 130i als Auto fährt (und ihm dieser Wagen gefällt), welche Fahrzeuge würden ihm noch gefallen bzw. bei einem späteren Einkauf zusagen?

Um die Frage zu beantworten benötigst du eine Zahl, die ausgibt:

Toyota Corolla Verso hat eine Ähnlichkeit von 0,2 (sehr wenig)
Ein BMW 125i hat eine Ähnlichkeit von 0,8 (recht hoch)
...
.
.

Damit du dann aber später jedes Fahrzeug mit jedem vergleichen kannst, müssen Ähnlichkeiten zwischen jedem Fahrzeug berechnet werden ( kart. Produkt sozusagen).

Hierzu benutzen wir jetzt zum einen die Minkowski-Metrik und zum anderen den Q-Korrelationskoeffizienten, da wir aus den beiden Werten zusammen ein neues Gütemaß erstellen wollen (was auch Ziel des projektes ist), um den Fit der Berechnungen zu ableiten zu können.

So haben wir's jetzt gelöst: Wir haben die Matrix in 1000 X 1000er-Matrizen aufgeteilt und lassen diese separat berechnen, schmeissen diese Dann in eine Datenbank und wenn die Gesamtmatrix durchlaufen werden muss, dann wird per lazy loading und eagerly unloading der Datenbestand in den Speicher geholt und danach wieder gelöscht.

War nen hartes Wochenende, aber es scheint recht gut z ufunktionieren und das Gütemaß scheint auch gut zu funktionieren