Dies ist ein Artikel, den ich versucht habe, die nicht negative Matrixfaktor-Zerlegung (NMF), die ich vor etwa einem Jahr verstanden habe, erneut zu implementieren und zu bestätigen. Support Vector Machine (SVM) und Deep Learning sind heutzutage sehr beliebt, aber ich möchte vorstellen, dass es auch eine solche Methode gibt ... Ich habe es zum ersten Mal seit einiger Zeit in C ++ und Python 2.7 implementiert.
[Aktualisiert am 05.02.2020]
Ich habe ein Modell für die Echtzeit-Trennung von Schallquellen mithilfe von NMF erstellt. Hier
[Aktualisiert am 23. März 2018]
Einige Texte wurden überarbeitet. Außerdem haben wir es auch in Julia implementiert, also habe ich den Link dort gepostet.
Mac OS X 10.11.6 Elcapitan
Python 2.7.11 (Ich muss bald auf 3 System upgraden ...)
numpy 1.11.1
cmake 3.6.2
NMF ist ein Algorithmus, der eine Elementmatrix V mit nicht negativem Wert (> = 0) durch das Produkt zweier anderer nicht negativer Wertmatrizen W und H approximiert. Dieser Algorithmus selbst wird als Merkmalsextraktions-, Verarbeitungs- und Clustering-Methode verwendet.
Aufgrund seines nicht negativen Wertes gibt es auch einen, der das Leistungsspektrum bei der akustischen Signalverarbeitung verwendet, und er wird auch verwendet, um die Aussprachezeit des Tons eines bestimmten Instruments aus dem Spektrogramm zu ermitteln.
Die NMF-Formel für die Matrix unter i * j lautet
k \in R \\
V \approx WH\\
V \in R^{i \times j}\\
W \in R^{i \times k} \qquad H \in R^{k \times j}
Es wird.
Da der Inhalt der Eingangsmatrix V bekannt ist, der Inhalt von W und H jedoch unbekannt ist, minimiert NMF den Abstand zwischen V und WH.
Ein bekannter (und einfacher) Algorithmus in NMF ist der Multiplikator-Aktualisierungsalgorithmus. Wie oben erwähnt, muss der Abstand (Fehler) zwischen X und WH definiert und minimiert werden. Es gibt drei Arten von Entfernungen, die in NMF verwendet werden und die ich kenne.
D_{EUC}(V, WH) = (V-WH)^2
D_{KL}(V, WH) = V log \frac{V}{WH} - V + WH
https://en.wikipedia.org/wiki/Itakura–Saito_distance
D_{IS}(V,WH) = \frac{V}{WH} - log \frac{V}{WH} -1
Es gibt auch eine β-Divergenz, die diese drei Distanzfunktionen ausdrückt. Verwenden Sie diese Algorithmen als Multiplikator-Aktualisierungsalgorithmus. Die Ableitung und Transformation detaillierter Ausdrücke entfällt.
Die Aktualisierungsformel nach der Transformation lautet
H_{n+1} \gets H_{n} \frac{W^{T}_{n}V_{n}}{W^{T}_{n}W_{n}H_{n}}, \qquad W_{n+1} \gets W_{n} \frac{V_{n}H^{T}_{n+1}}{W_{n}H_{n+1}H^{T}_{n+1}}
H_{n+1} \gets H_{n} \frac{W^{T}_{n}\frac{V_{n}}{W_{n}H_{n}}}{W^{T}_{n}}, \qquad W_{n+1} \gets W_{n} \frac{\frac{V_{n}}{W_{n}H_{n+1}}H^{T}_{n+1}}{H^{T}_{n+1}}
H_{n+1} \gets H_{n} \sqrt{\frac{\frac{W_{n}}{W_{n}H_{n}}^{T}\frac{V_{n}}{W_{n}H_{n}}}{\frac{W_{n}}{W_{n}H_{n}}^{T}}}, \qquad W_{n+1} \gets W_{n} \sqrt{\frac{\frac{V_{n}}{W_{n}H_{n+1}}\frac{H_{n+1}}{W_{n}H_{n+1}}^{T}}{\frac{H_{n+1}}{W_{n}H_{n+1}}^{T}}}
Ich fragte mich, ob es so war ... (Ich erinnere mich ein wenig. Es tut mir leid, wenn ich einen Fehler gemacht habe.) Was Sie beachten müssen, ist, dass H in der Formel {n + 1} ist! Wenn Sie dies vergessen, werden Sie in eine Situation geraten, in der es überhaupt nicht konvergiert. Durch Wiederholen dieses Vorgangs wird der Abstand zwischen V und WH verringert. ..
Referenzmaterialien / URL
http://papers.nips.cc/paper/1861-algorithms-for-non-negative-matrix-factorization.pdf http://www.mitpressjournals.org/doi/pdf/10.1162/neco.2008.04-08-771
NMF.py
# coding:utf-8
import numpy as np
class NMF():
"""
Eine Klasse, die eine einfache NMF macht
"""
def setParam(self, k, row, column):
"""
:param k
:param row:Säule
:param column:Linie
:return:
"""
self.__k = k
self.__row = row
self.__column = column
self.__dictionary = np.random.random_sample([self.__row, self.__k])
self.__activation = np.random.random_sample([self.__k, self.__column])
def setDictionary(self, index, data):
"""
Wenn eine Vorlage vorhanden ist, legen Sie die Vorlage fest (Standard ist die Zufallszahl).
:param index:Index der Vorlage(0 <= index < k)
:param data:Vorlagendaten
:return:
"""
if index >= self.__k and len(data) != self.__row:
print "Please NMF.setParam(k,row,column)"
print "k = " + str(self.__k)
print "row = " + str(self.__row)
return
self.__dictionary[:, index] = np.array(data[:self.__row], np.float32)
def setAnalyzData(self, data, k):
"""
Rufen Sie diese Methode ganz am Anfang auf
:param data:Zu zerlegende Daten
:param k
:return:
"""
if len(np.shape(data)) == 1:
self.__data = np.ones([np.shape(data)[0], 1], np.float32)
self.setParam(k, np.shape(data)[0], 1)
else:
self.__data = data
self.setParam(k, np.shape(data)[0], np.shape(data)[1])
def separate_euc_with_template(self,iter=200):
"""
Separate EUC-Spezifikationen mit Vorlagen
:param iter:
:return:
"""
counter = 0
while counter < iter:
approx = np.dot(self.__dictionary , self.__activation)
wh = np.dot(np.transpose(self.__dictionary) , self.__data)
wt = np.dot(np.transpose(self.__dictionary) , approx)
bias = wh/wt
bias[np.isnan(bias)] = 0
self.__activation = self.__activation * bias
counter += 1
return self.__dictionary,self.__activation
def separate_euc_without_template(self,iter=200):
"""
Separate EUC-Spezifikationen ohne Vorlage
:param iter:
:return:
"""
counter = 0
while counter < iter:
approx = np.dot(self.__dictionary , self.__activation)
wh = np.dot(np.transpose(self.__dictionary) , self.__data)
wt = np.dot(np.transpose(self.__dictionary) , approx)
bias = wh/wt
bias[np.isnan(bias)] = 0
self.__activation = self.__activation * bias
approx = np.dot(self.__dictionary,self.__activation)
wh = np.dot(self.__data,np.transpose(self.__activation))
wt = np.dot(approx,np.transpose(self.__activation))
bias = wh/wt
bias[np.isnan(bias)] = 0
self.__dictionary = self.__dictionary * bias
counter += 1
return self.__dictionary,self.__activation
Die Klasse, die NMF selbst ausführt, wird diesmal wie folgt implementiert. Aufgrund der Textmenge werden diesmal nur die EUC-Spezifikationen aufgeführt. Der Code ist ziemlich mühsam, aber wenn Sie nichts dagegen haben ...
Ich habe auch einen Testcode erstellt (einschließlich der Verwendung), also habe ich ihn ausgeführt.
main.py
#coding:utf-8
import numpy as np
"""
Es ist ein Ärger, aber ich muss diese beiden importieren
"""
from NMF import NMF
"""
Testskript
Wie benutzt man
"""
if __name__ == "__main__":
"""
Grundsätzlich ein lästiges k mit einem Konstruktor,row,Sie müssen die Spalte nicht übergeben
Ich habe es gerade richtig gemacht ...
"""
nmf = NMF()
"""
Rufen Sie dies zuerst auf, nachdem Sie den Konstruktor erstellt haben!
Wo k,row,Da die Spalte gesetzt ist, funktioniert setDictionary nur, wenn dies aufgerufen wird!
"""
nmf.setAnalyzData([[1,2,3,4],[2,3,4,5]],k=3)
"""
Stellen Sie hier die Vorlage ein
"""
nmf.setDictionary(0,[0.0,2.0])
nmf.setDictionary(1,[1.0,6.0])
nmf.setDictionary(2,[11.0,10.0])
"""
NMF wurde gestartet
Übergeben Sie den Algorithmus und die Anzahl der wiederholten Aktualisierungen als Argumente
"""
dic,act = nmf.separate_euc_with_template(iter=200)
# dic,act = nmf.separate_euc_without_template(iter=200)
"""
Ergebnisanzeige
"""
print "=========================== Dictionary ==========================="
print dic
print "=========================== Activation ==========================="
print act
"""
Überprüfen Sie, ob es ordnungsgemäß zerlegt werden kann
"""
print "=========================== Approx ==========================="
print np.dot(dic,act)
In diesem Test
V = \begin{pmatrix}
1 & 2 & 3 & 4\\
2 & 3 & 4 & 5
\end{pmatrix}
\qquad k=3
NMF wird an einer Matrix mit solchen Bedingungen durchgeführt. Für diese Matrix wird die von setDictionary () festgelegte Wörterbuchmatrix verwendet.
W = \begin{pmatrix}
0 & 1 & 11 \\
2 & 6 & 10
\end{pmatrix}
Aktualisieren Sie die Anregungsmatrix mit.
Wenn Sie das Skript main.py ausführen ...
$ python main.py
=========================== Dictionary ===========================
[[ 0. 1. 11.]
[ 2. 6. 10.]]
=========================== Activation ===========================
[[ 0.11776982 0.05902263 0.00976704 0.33375605]
[ 0.168019 0.20895539 0.24616295 0.1367387 ]
[ 0.07563464 0.16282224 0.25034882 0.35120557]]
=========================== Approx ===========================
[[ 1. 2. 3. 4.]
[ 2. 3. 4. 5.]]
Richtig wurde die Anregungsmatrix aktualisiert, so dass der Abstand zwischen V und WH 0 wurde.
Dieses Mal habe ich es weggelassen, einschließlich der KL / IS-Version, die auf GitHub verfügbar ist. Darüber hinaus wird auch die C ++ - Version des Quellcodes (die Struktur entspricht fast der Python-Version) veröffentlicht, die diesmal weggelassen wird. Klicken Sie hier für die Python-Version (https://github.com/T-Sumida/Simple_NMF) Klicken Sie hier für die C ++ - Version (https://github.com/T-Sumida/NMF_for_cpp) Julia Version ist hier
Es war eine gute Rezension, das zu schreiben und zu formulieren, was ich vor ungefähr einem Jahr zum ersten Mal seit einiger Zeit studiert habe.
Wie ich am Anfang schrieb, ziehen DNN usw. heutzutage Aufmerksamkeit auf sich, aber es gibt auch einen so einfachen Algorithmus! Ich hoffe es wird eine Einführung sein.
Das nächste Mal möchte ich anhand dieses Beispiels ein praktisches Beispiel vorstellen.
Recommended Posts