Memory Fehler beim Berechnen paarweise Entfernungen in scipy

Question

Ich versuche, hierarchische Clustering auf meine Datenmenge anwenden, die aus 14039 Vektoren von Benutzern besteht. Jeder Vektor hat 10 Merkmale, wobei jedes Merkmal im Wesentlichen die Häufigkeit der von diesem Benutzer getaggten Tags ist. Ich benutze Scipy API für Clustering. Jetzt muss ich paarweise Abstände zwischen diesen 14039 Benutzern berechnen und diese Abstandsmatrix an die Verknüpfungsfunktion übergeben.

import scipy.cluster.hierarchy as sch 
    Y = sch.distance.pdist(allUserVector,'cosine') 
    set_printoptions(threshold='nan') 
    print Y 

Aber mein Programm gibt mir Memory, während die Matrix selbst Abstandsberechnungs

File "/usr/lib/pymodules/python2.7/numpy/core/numeric.py", line 1424, in array_str 
    return array2string(a, max_line_width, precision, suppress_small, ' ', "", str) 
    File "/usr/lib/pymodules/python2.7/numpy/core/arrayprint.py", line 306, in array2string 
    separator, prefix) 
    File "/usr/lib/pymodules/python2.7/numpy/core/arrayprint.py", line 210, in _array2string 
    format_function = FloatFormat(data, precision, suppress_small) 
    File "/usr/lib/pymodules/python2.7/numpy/core/arrayprint.py", line 392, in __init__ 
    self.fillFormat(data) 
    File "/usr/lib/pymodules/python2.7/numpy/core/arrayprint.py", line 399, in fillFormat 
    non_zero = absolute(data.compress(not_equal(data, 0) & ~special)) 
MemoryError 

Jede Idee, wie dieses Problem beheben? Ist mein Datensatz zu groß? Aber ich denke, Clustering 14k Benutzer sollte nicht zu viel, dass es Speicherfehler verursachen sollte. Ich betreibe es auf i3 und 4 Gb Ram. Ich muss auch DBScan-Clustering anwenden, aber auch das benötigt eine Abstandsmatrix als Eingabe.

Alle Vorschläge geschätzt.

Edit: Ich bekomme den Fehler nur, wenn ich Y. Irgendwelche Ideen warum?

Answer 1

Nun, hierarchische Clustering macht nicht viel Sinn für große Datensätze. Es ist meiner Meinung nach meistens ein Lehrbuchbeispiel. Das Problem mit hierarchischem Clustering ist, dass es nicht wirklich vernünftige Cluster aufbaut. Es baut ein Dendrogramm auf, aber mit 14000 Objekten wird das Dendrogramm ziemlich unbrauchbar. Und sehr wenige Implementierungen von hierarchischem Clustering haben nicht-triviale Methoden, um sinnvolle Cluster aus dem Dendrogramm zu extrahieren. Außerdem ist das hierarchische Clustering im Allgemeinen von Komplexität O(n^3), wodurch es für große Datasets wirklich schlecht skaliert wird.

DBSCAN technisch macht nicht brauchen eine Abstandsmatrix. In der Tat, wenn Sie eine Distanzmatrix verwenden, wird es langsam sein, da die Berechnung der Abstandsmatrix bereits O(n^2) ist.Und selbst dann können Sie die Speicherkosten von DBSCAN fürsichern, indem Sie die Entfernungen im laufenden Betrieb auf Kosten der zweifachen Rechenentfernungen berechnen. DBSCAN besucht jeden Punkt einmal, so dass die Verwendung einer Abstandsmatrix mit Ausnahme des Symmetriegewinns praktisch keinen Vorteil bringt. Und technisch gesehen könnten Sie einige nette Caching-Tricks machen, um dies sogar zu reduzieren, da DBSCAN auch nur wissen muss, welche Objekte unterhalb der Epsilon-Schwelle liegen. Wenn das Epsilon vernünftig gewählt wird, wird die Verwaltung der Nachbarsätze im laufenden Betrieb wesentlich weniger Speicher als O(n^2) bei den gleichen CPU-Kosten für die Berechnung der Abstandsmatrix benötigen.

Jede wirklich gute Implementierung von DBSCAN (es ist buchstabiert Großbuchstaben, BTW, wie es eine Abkürzung, kein Scan ist) sollte jedoch Unterstützung für Indexstrukturen und dann in O(n log n) Runtime laufen.

Auf http://elki.dbs.ifi.lmu.de/wiki/Benchmarking führen sie DBSCAN auf einem 110250 Objektdatensatz und 8 Dimensionen, und die nicht indizierte Variante dauert 1446 Sekunden, die mit Index nur 219. Das ist etwa 7-mal schneller, einschließlich Indexaufbau. (Es ist jedoch nicht Python) Ähnlich ist OPTICS 5 mal schneller mit dem Index. Und ihre Implementierung in meinen Experimenten war rund 6x schneller als WEKA und verbraucht viel weniger Speicher. Ihr hierarchisches Single-Link-Clustering ist ebenfalls eine optimierte O(n^2) Implementierung. Eigentlich der einzige, den ich bisher gesehen habe, ist nicht der naive O(n^3) Matrix-Editing-Ansatz. Wenn Sie bereit sind, über Python hinauszugehen, könnte das eine gute Wahl sein.

Answer 2

Es ist möglich, dass Ihnen wirklich der Arbeitsspeicher knapp wird. Das Finden paarweiser Abstände zwischen N Objekten bedeutet das Speichern von N^2 Distanzen. In deinem Fall wird N^2 14039^2 = 1,97 * 10^8 sein. Wenn wir davon ausgehen, dass jede Entfernung nur vier Bytes benötigt (was mit ziemlicher Sicherheit nicht der Fall ist, da sie in einer Art von Datenstruktur gehalten werden müssen, die einen nicht konstanten Overhead haben kann), ergibt dies 800 Megabyte. Das ist eine Menge Speicher für den Interpreter. 32-Bit-Architekturen erlauben nur bis zu 2 GB Prozessspeicher, und nur Ihre Rohdaten benötigen etwa 50% davon. Mit dem Overhead der Datenstruktur könnte man die Nutzung viel höher betrachten - ich kann nicht sagen wie viel, weil ich das Speichermodell hinter SciPy/numpy nicht kenne.

Ich würde versuchen, Ihre Datensätze in kleinere Sätze zu brechen oder nicht die vollständige Distanzmatrix zu konstruieren. Sie können es in handhabbarere Stücke zerlegen (sagen wir 14 Teilmengen von ungefähr 1000 Elementen) und den nächsten Nachbarn zwischen jedem Stück und allen Vektoren machen - dann schauen Sie sich an, eine beliebige Größenordnung weniger in den Speicher zu laden einmal (14000 * 1000, 14 mal statt 14000 * 14000 mal).

Bearbeiten: Agf ist völlig richtig in beiden Punkten: Ich habe Ihre Bearbeitung verpasst, und das Problem kommt wahrscheinlich, wenn es versucht, die riesige Zeichenfolge, die Ihre Matrix darstellt zu konstruieren. Wenn Fließkommawerte gedruckt werden und angenommen wird, dass 10 Zeichen pro Element gedruckt werden und die Zeichenfolge mit einem Byte pro Zeichen gespeichert wird, werden genau 2 GB Speicherverbrauch nur für die Zeichenfolge angezeigt.