Clustering ~ 100.000 kurze Strings in Python

Ich möchte ~ 100.000 kurze Strings durch etwas wie q-Gramm Abstand oder einfache "Bag Abstand" oder vielleicht Levenshtein Abstand in Python Cluster. Ich plante, eine Entfernungsmatrix auszufüllen (100.000 wähle 2 Vergleiche) und mache dann ein hierarchisches Clustering mit pyCluster. Aber ich stoße in einige Speicherprobleme, bevor ich überhaupt vom Boden abhebe. Zum Beispiel ist die Distanzmatrix zu groß für numpy.Clustering ~ 100.000 kurze Strings in Python

aa = numpy.zeros((100000, 100000)) 
ValueError: array is too big.

Scheint dies eine vernünftige Sache zu tun? Oder bin ich zu Gedächtnisproblemen in dieser Aufgabe verdammt? Danke für Ihre Hilfe.

Quelle

2010-11-22 135498

10 Milliarden ist eine große Zahl. – nmichaels

Ich denke an eine Annäherung an dieses lustige Problem, aber ich vermisse einige Informationen. Bitte erläutern Sie etwas genauer, was genau Sie erreichen möchten, warum und welche möglichen Annahmen/Einschränkungen. Hier sind zwei besondere Fragen. 1) Können Sie Replikatfolgen in Ihrer Analyse haben? 2) Brauchen Sie wirklich alle 2-mal-2-Distanzen oder sagen Sie, dass nur ein Teil der kleineren Distanzen für eine gegebene Saite ausreichen würde? Prost. – Morlock

100.000 * 100.000 * 32Bits = 40 GBytes, das wäre viel RAM, also ja, müssen Sie einen anderen Weg finden. (Und selbst wenn Sie diese Daten in den Speicher einbauen könnten, würde die Berechnung zu lange dauern.)

Eine häufige und einfache Verknüpfung besteht darin, eine kleine zufällige Teilmenge der Daten zu clustern, und nachdem Sie die Cluster dieser Teilmenge gefunden haben, Lege einfach die restlichen Punkte in die Cluster, wo sie am besten passen.

Quelle

2010-11-22 02:35:31 tom10

Hat Ihr Computer nicht 4096 GB Arbeitsspeicher? –

Danke für die Berechnungen. Ja, der derzeitige Ansatz scheint unmöglich. – 135498

Entschuldigung, hier nur zwei Jahre später: Da die Distanzmatrix symmetrisch ist, wären es 20 GB. –

10 Milliarden Elemente ist eine furchtbare Menge. Ich weiß es nicht von q-Gramm, aber wenn diese Matrix spärlich ist, könnten Sie ein 200.000-ish Element dict verwenden.

Quelle

2010-11-22 02:38:28 nmichaels

Ich habe über Sparse-Matrizen gelesen.Unklar, wenn die Daten spärlich sind, wie du sagst ... Ich müsste mehr testen. Auch unklar (für mich), ob pyCluster mit dünn besetzten Matrizen umgehen kann. Danke für deinen Rat. – 135498

Was möchten Sie mit den Daten machen? Das ist eine ziemlich wichtige Frage, denke ich. –

Eine solche Matrix wäre im Prinzip nicht spärlich. Ein Problem beim Erstellen einer solchen dünn besetzten Matrix besteht darin, wie Sie bestimmen, ob ein Matrixelement ausgewertet werden soll oder nicht. – cyborg

Benötigen Sie die Matrix? Ich nehme an, Sie möchten eine Matrix für die Geschwindigkeit verwenden?

Ich habe einen k-Means-Cluster-Algorithmus (und nicht einen hierarchischen Cluster-Algorithmus) und berechnet die Knotenabstände nach Bedarf. Wahrscheinlich nur für schnelle Entfernungsmetriken geeignet. Und Sie haben mehr Daten als ich - aber Sie sind an Speicherbeschränkungen gebunden.

Quelle

2010-11-23 18:20:46 winwaed

Ja, so etwas scheint die Lösung zu sein. Vielen Dank. – 135498

ein Verfahren in Machine Learning ist Embedding genannt, die nach einer Lösung suchen, für dieses Problem im Prinzip O (n + m) Speicher statt O (n * m) mit (n = 10^5 Elemente, m = 10^5 Funktionen). Leider kenne ich keinen verfügbaren Quellcode, der in O (m + n) implementiert ist. Siehe:

Euklidische Einbettung von Co-Vorkommensdaten. Amir Globerson, Gal Chechik, Fernando Pereira und Naftali Tishby. Journal of Machine Learning Forschung, JMLR, 8 (Okt), 2007. pdf/ Matlab code
Es könnten auch andere Lösungen sein. Ich denke, dass Sie diese Frage in einem Forum von Machine Learning-Leuten stellen sollten, z. B. https://stats.stackexchange.com/ oder noch spezifischer für die Sprachverarbeitung: http://metaoptimize.com/qa/.

Quelle

2011-10-09 18:18:34 cyborg

Clustering ~ 100.000 kurze Strings in Python

Antwort

Verwandte Themen