Die nicht-negative Matrixfaktorisierung (NMF oder NNMF), auch als nicht-negative Matrixapproximation bezeichnet, ist eine Gruppe von Algorithmen in der multivariaten Analyse und der linearen Algebra. Das Ziel besteht darin, eine gegebene Matrix V in zwei Matrizen zu faktorisieren, die üblicherweise als W und H bezeichnet werden, sodass alle drei Matrizen ausschließlich nicht-negative Elemente enthalten. Diese Einschränkung erleichtert die Inspektion und Interpretation der resultierenden Faktoren und passt zu Anwendungen, bei denen die Daten selbst inhärent nicht-negativ sind, wie etwa Audiospektrogramme oder Messungen der Muskelaktivität. Da eine exakte Faktorisierung im Allgemeinen nicht möglich ist, berechnen NMF-Methoden numerisch eine Näherungslösung.
NMF findet Anwendungen in verschiedenen Bereichen, darunter Astronomie, Computersehen, Dokument-Clustering, Imputation fehlender Daten, Chemometrie, Audiosignalverarbeitung, Empfehlungssysteme und Bioinformatik. Ihr Reiz liegt in der Fähigkeit, teilebasierte Darstellungen zu erzeugen, bei denen die ursprünglichen Daten als additive Kombinationen einer kleinen Menge gelernter Komponenten ausgedrückt werden.
Geschichte
Das Konzept der nicht-negativen Faktorisierung hat seine Wurzeln in der Chemometrie, wo es lange als „Self Modeling Curve Resolution“ bekannt war. In diesem Rahmen werden die Vektoren in der rechten Faktormatrix als kontinuierliche Kurven und nicht als diskrete Vektoren behandelt. In den 1990er Jahren entwickelte eine finnische Forschungsgruppe verwandte Methoden unter dem Namen „Positive Matrix Factorization“. Der Ansatz erlangte breitere Anerkennung als nicht-negative Matrixfaktorisierung, nachdem Daniel D. Lee und H. Sebastian Seung seine Eigenschaften untersuchten und 1999 und 2001 einfache und effektive Algorithmen für zwei Arten der Faktorisierung veröffentlichten. Ihre Arbeit hob die Interpretierbarkeit der resultierenden Faktoren hervor und weckte breites Interesse an der Methode.
Hintergrund
Gegeben eine Matrix V der Größe m × n, versucht NMF, diese als Produkt zweier Matrizen zu approximieren: V ≈ W H, wobei W die Größe m × p und H die Größe p × n hat. Der Rang p wird typischerweise so gewählt, dass er deutlich kleiner als sowohl m als auch n ist, sodass die Faktorisierung die ursprünglichen Daten in eine Darstellung mit niedrigerer Dimension komprimiert. Die Matrixmultiplikation kann spaltenweise verstanden werden: Jeder Spaltenvektor von V ist eine Linearkombination der Spaltenvektoren von W, wobei die Koeffizienten durch die entsprechende Spalte von H gegeben sind.
Zum Beispiel könnte V in einer Text-Mining-Anwendung 10.000 Zeilen für Wörter und 500 Spalten für Dokumente haben. Wenn der Algorithmus aufgefordert wird, 10 Merkmale zu finden, wird W die Größe 10.000 × 10 und H die Größe 10 × 500 haben. Jede Spalte des Produkts W H ist dann eine Linearkombination der 10 Merkmalsvektoren in W, gewichtet mit den Einträgen in der entsprechenden Spalte von H. Jeder Merkmalsvektor in W kann als Dokument-Archetyp interpretiert werden, wobei die Zellwerte die Bedeutung jedes Wortes in diesem Merkmal angeben. Ebenso gibt jede Spalte von H die Gewichte dieser Merkmale für ein bestimmtes Dokument an, wodurch die Rekonstruktion des ursprünglichen Dokuments als gewichtete Summe der Archetypen ermöglicht wird.
Clustering-Eigenschaft
NMF besitzt eine inhärente Clustering-Eigenschaft. Bei der Approximation von V durch W H clustert der Algorithmus automatisch die Spalten der Eingabedaten. Die Approximation wird durch Minimierung einer Fehlerfunktion erreicht, oft der Frobenius-Norm der Differenz zwischen V und W H, unter den Nicht-Negativitätsbeschränkungen für W und H. Wenn eine zusätzliche Orthogonalitätsbeschränkung für H auferlegt wird (d. h. H Hᵀ = I), wird die Minimierung mathematisch äquivalent zum K-Means-Clustering. In diesem Fall geben die Einträge von H direkt die Clusterzugehörigkeit an: Für eine gegebene Spalte j identifiziert der größte Eintrag H_kj das Cluster, zu dem der Datenpunkt v_j gehört. Diese Eigenschaft macht NMF zu einem nützlichen Werkzeug für unüberwachtes Lernen und explorative Datenanalyse.
Algorithmen und Berechnung
Es wurden mehrere Algorithmen zur Berechnung von NMF entwickelt. Der am weitesten verbreitete ist die von Lee und Seung eingeführte multiplikative Aktualisierungsregel, die W und H iterativ aktualisiert, während die Nicht-Negativität erhalten bleibt. Andere Ansätze umfassen alternierende kleinste Quadrate, projizierte Gradientenmethoden und Varianten, die Sparsity- oder Glattheitsbeschränkungen einbeziehen. Die Wahl des Algorithmus hängt oft von der Größe der Daten, der gewünschten Genauigkeit und der spezifischen Anwendung ab. Da das Problem nicht-konvex ist, können Lösungen von der Initialisierung abhängen, und mehrere Läufe mit unterschiedlichen Startpunkten werden manchmal verwendet, um ein stabiles Ergebnis zu erzielen.
Anwendungen
NMF wird in einer Vielzahl von Bereichen angewendet. In der Audiosignalverarbeitung wird sie verwendet, um Spektrogramme in spektrale Komponenten zu zerlegen, was Quellentrennung oder Musiktranskription ermöglicht. Beim Dokument-Clustering und der Themenmodellierung identifiziert NMF latente Themen als Mengen von Wörtern, wobei jedes Dokument als Mischung von Themen dargestellt wird. In der Bioinformatik hilft sie bei der Analyse von Genexpressionsdaten, indem sie Muster koexprimierter Gene identifiziert. In Empfehlungssystemen kann NMF Benutzer-Artikel-Bewertungsmatrizen faktorisieren, um latente Faktoren aufzudecken, die Benutzerpräferenzen vorhersagen. Darüber hinaus wurde NMF im Computersehen zur Gesichtsmerkmal-Extraktion und in der Chemometrie zur Auflösung überlappender spektraler Signale eingesetzt.