Schnelle nicht-negative Matrixfaktorisierung auf Large-Sparse-Matrix

Verwendung von Scikit-learn (v 0.15.2) zur nicht-negativen Matrixfaktorisierung auf einer großen dünn besetzten Matrix (weniger als 1% Werte> 0). Ich möchte Faktoren finden, indem Fehler nur auf Nicht-Null-Werten der Matrix minimiert werden (d. H. Fehler für Einträge, die Null sind, nicht berechnet werden) und Sparsity begünstigen. Ich bin mir nicht sicher, ob etwas nicht stimmt mit dem, was ich versuche. Das NMF und ProjectedGradientNMF des scikit-learn-Pakets haben sich für mich schon gut bewährt. Aber es scheint, dass wenn die Matrixgröße zunimmt, die Faktorisierung schrecklich langsam ist.Schnelle nicht-negative Matrixfaktorisierung auf Large-Sparse-Matrix

Ich spreche von Matrizen mit> 10^10 Zellen. Für eine Matrix mit ~ 10^7 Zellen finde ich die Ausführungszeit gut.

Die Parameter, die ich verwendet habe, sind wie folgt: nmf_model = NMF(n_components = 100, init='nndsvd', random_state=0, tol = 0.01, sparseness='data').

Als ich etwas andere Parameter versuchte (ändere zu init=random), erhalte ich die folgende Warnung. Nach der Warnung wird die Ausführung des Skripts angehalten.

/lib/python2.7/site-packages/sklearn/decomposition/nmf.py:252: UserWarning: Iteration limit reached in nls subproblem. 
    warnings.warn("Iteration limit reached in nls subproblem.")

Gibt es eine Möglichkeit, dies schneller zu machen und das obige Problem zu lösen? Ich habe versucht, numpige Sparse-Matrix zu verwenden (spalten- und reihenweise), aber überraschend - es ist langsamer auf dem Test, den ich mit einer kleineren Matrix (~ 10^7 Zellen) gemacht habe.

In Anbetracht dessen, dass man mehrere Iterationen einer solchen Faktorisierung durchführen müsste (um eine ideale Anzahl von Faktoren und eine k-fache Kreuzvalidierung zu wählen), ist ein schnellerer Weg zur Lösung dieses Problems sehr wünschenswert.

Ich bin auch offen für Vorschläge von Paket/Tools, die nicht auf Sklearn oder Pyhon basiert. Ich verstehe, dass Fragen zu Paket-/Werkzeugauswahl nicht erwünscht sind, aber für einen solchen speziellen Anwendungsfall wäre es sehr hilfreich zu wissen, welche Techniken andere in diesem Bereich anwenden.

Quelle

2015-07-22 vpk

Vielleicht könnten uns ein paar Worte darüber, worum es geht, bessere Antworten geben.

Matrix Faktorisierung auf einer sehr großen Matrix wird aufgrund der Art des Problems immer langsam sein.

Vorschläge: Reduzieren n_components zu < 20 wird es etwas beschleunigen. Die einzige wirkliche Verbesserung der Geschwindigkeit wird jedoch erreicht, indem die Größe der Matrix begrenzt wird. Mit einer Matrix wie Sie beschreiben, könnte man denken, dass Sie versuchen, eine Term-Frequenz-Matrix zu faktorisieren. Wenn dies der Fall ist, könnten Sie versuchen, die Vektorisierungsfunktionen in scikit-learn zu verwenden, um die Größe der Matrix zu begrenzen. Die meisten von ihnen haben einen max_features Parameter. Beispiel:

vectorizer = TfidfVectorizer(
    max_features=10000, 
    ngram_range=(1,2)) 
tfidf = vectorizer.fit_transform(data)

Dies wird die Problemlösung erheblich beschleunigen.

Sollte ich komplett falsch liegen und dies ist kein Problem mit der Häufigkeit von Termen, würde ich immer noch nach Möglichkeiten suchen, die anfängliche Matrix zu begrenzen, die Sie zu zerlegen versuchen.

Quelle

2015-07-23 13:14:23 wonderkid2

Ist die NMF-Methode der Scipy nur für die Berechnung von Nicht-Null-Einträgen der Matrix fehlerhaft? Null Einträge bedeuten fehlende Werte. Wird die Regularisierung verwendet, um die Lösung zu spärlich zu machen? Ich habe die Details in der Dokumentation nicht gefunden. Vielleicht müssen Sie den Code eingraben. Ein allgemeiner Anwendungsfall, der auch Term-Frequency beinhaltet, aber auch Dinge wie Items-Tags. Diese Matrix ist sehr spärlich. Ihre Lösung klingt gut, aber wenn die Matrix riesig ist, ist sie immer noch nicht skalierbar. Nehmen wir an, ich möchte Artikel ermitteln, die weniger als 2 Mal getaggt wurden, oder Tags, die weniger als 5 Items enthalten. Wie man sie alle ausfiltert? – vpk

Ich nehme an, du meinst scikits NMF-Methode und nicht scipy's? Wie der Algorithmus mit Sparsity umgeht, kann durch den Parameter 'Spärlichkeit' eingestellt werden. Es ist in der Dokumentation. Für die letzten beiden Fälle sehe ich nicht, warum Sie NMF dafür verwenden würden. Ich würde denken, dass es dafür geeignetere Werkzeuge gibt. – wonderkid2

Ja, Scikit. Über welche anderen Tools sprechen Sie? – vpk

Sie können einen Blick auf diesen Artikel in Anspruch nehmen wollen, die neueren Techniken auf NMF diskutiert: http://www.cc.gatech.edu/~hpark/papers/nmf_blockpivot.pdf

Die Idee ist, nur auf die Nicht-Null-Einträge für Faktorisierung zu arbeiten, die insbesondere Rechenzeit reduziert, wenn die Matrix/Matrizen beteiligt ist/sind sehr spärlich.

Auch einer der Autoren aus dem gleichen Artikel erstellt NMF-Implementierungen auf GitHub einschließlich der in ihrem Artikel erwähnt.Hier ist der Link: https://github.com/kimjingu/nonnegfac-python

Hoffe, dass hilft.

Quelle

2015-12-14 13:33:34 jtitusj

Schnelle nicht-negative Matrixfaktorisierung auf Large-Sparse-Matrix

Antwort

Verwandte Themen