1. Diese Seite verwendet Cookies. Wenn du dich weiterhin auf dieser Seite aufhältst, akzeptierst du unseren Einsatz von Cookies. Weitere Informationen

Kniffliges Statistik-Problem (Distanzmaße)

Dieses Thema im Forum "OS X-Developer" wurde erstellt von YanniH, 13.09.08.

  1. YanniH

    YanniH Auralia

    Dabei seit:
    20.04.08
    Beiträge:
    202
    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!
     
  2. sumpfmonsterjunior

    sumpfmonsterjunior Morgenduft

    Dabei seit:
    17.03.05
    Beiträge:
    167
    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
     
  3. YanniH

    YanniH Auralia

    Dabei seit:
    20.04.08
    Beiträge:
    202
    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.
     
  4. quarx

    quarx Hadelner Sommerprinz

    Dabei seit:
    17.04.05
    Beiträge:
    8.541
    Und diese Matrix enthält nur diese Distanzmaße? Warum muss sie überhaupt aufgestellt werden? Clusteranalyse?
     
  5. tomsie

    tomsie Bismarckapfel

    Dabei seit:
    25.11.06
    Beiträge:
    76
    Und wenn sie symmetrisch ist, kannst du dir einiges sparen. Einfach die get- und set-Methoden entsprechend anpassen ;)
     
  6. YanniH

    YanniH Auralia

    Dabei seit:
    20.04.08
    Beiträge:
    202
    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 :oops:)
     
  7. quarx

    quarx Hadelner Sommerprinz

    Dabei seit:
    17.04.05
    Beiträge:
    8.541
    Gib doch mal ein paar mathematische Details, noch ist mir gar nicht klar, was Du da überhaupt zu rechnen hast.
     
  8. tjp

    tjp Baldwins roter Pepping

    Dabei seit:
    07.07.04
    Beiträge:
    3.252
    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.
     
  9. below

    below Kalterer Böhmer

    Dabei seit:
    08.10.06
    Beiträge:
    2.865
    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
     
  10. quarx

    quarx Hadelner Sommerprinz

    Dabei seit:
    17.04.05
    Beiträge:
    8.541
    Vielleicht sollte man auch, bevor man zu den Werkzeugen greift, erstmal das Problem auf Vereinfachungs- und Optimierungsmöglichkeiten untersuchen...
     
  11. below

    below Kalterer Böhmer

    Dabei seit:
    08.10.06
    Beiträge:
    2.865
    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
     
  12. Tafkas

    Tafkas Rheinischer Krummstiel

    Dabei seit:
    25.11.06
    Beiträge:
    381
    Wieso muss eigentlich jeder Artikel mit jedem betrachtet werden. Kannst du evtl. noch ein paar Infos hier einstreuen?
     
  13. YanniH

    YanniH Auralia

    Dabei seit:
    20.04.08
    Beiträge:
    202
    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 :)
     
    #13 YanniH, 15.09.08
    Zuletzt bearbeitet: 15.09.08

Diese Seite empfehlen