Das Zuordnungsproblem, eine numplige Funktion?

Question

Da sich ein assignment problem in Form einer einzigen Matrix darstellen lässt, bin ich am wandern, wenn numpy eine Funktion hat, eine solche Matrix zu lösen. Bis jetzt habe ich keine gefunden. Vielleicht weiß einer von euch, ob numpy/scipy eine Aufgaben-Problemlösungs-Funktion hat?

Edit: In der Zwischenzeit habe ich eine Python (nicht numpy/scipy) Implementierung bei http://www.clapper.org/software/python/munkres/ gefunden. Ich nehme an, dass eine numplige/scipy Implementierung viel schneller sein könnte, oder?

Answer 1

Nein, NumPy enthält keine solche Funktion. Kombinatorische Optimierung liegt außerhalb des Umfangs von NumPy. Es kann möglich sein, es mit einem der Optimierer in scipy.optimize zu tun, aber ich habe das Gefühl, dass die Einschränkungen möglicherweise nicht die richtige Form haben.

NetworkX enthält wahrscheinlich auch Algorithmen für Zuordnungsprobleme.

Answer 2

Es gibt eine Implementierung des Munkres' algorithm als ein Python-Erweiterungsmodul, das numpy Unterstützung hat. Ich habe es erfolgreich auf meinem alten Laptop verwendet. Es funktioniert jedoch nicht auf meiner neuen Maschine - ich nehme an, es gibt ein Problem mit "neuen" numpy Versionen (oder 64bit arch).

Answer 3

Es gibt jetzt eine numpige Implementierung des Munkres-Algorithmus in scikit-learn unter sklearn/utils/linear_assignment_.py seine einzige Abhängigkeit ist numpy. Ich habe es mit ungefähr 20x20 Matrizen versucht, und es scheint ungefähr 4 mal so schnell zu sein wie das, das in der Frage verbunden ist. cProfiler zeigt 2.517 Sekunden vs 9.821 Sekunden für 100 Iterationen.

Answer 4

Ich hatte gehofft, dass die neuere scipy.optimize.linear_sum_assignment schnellste wäre, aber (vielleicht nicht überraschend) die Cython library (die nicht pip Unterstützung hat) ist deutlich schneller, zumindest für meinen Anwendungsfall:

$ python -m timeit -s 'from scipy.optimize import linear_sum_assignment; import numpy as np; np.random.seed(0); c = np.random.rand(20,30)' 'a,b = linear_sum_assignment(c)' 
100 loops, best of 3: 3.43 msec per loop 
$ python -m timeit -s 'from munkres import munkres; import numpy as np; np.random.seed(0); c = np.random.rand(20,30)' 'a = munkres(c)' 
10000 loops, best of 3: 139 usec per loop 
$ python -m timeit -s 'from scipy.optimize import linear_sum_assignment; import numpy as np; np.random.seed(0);' 'c = np.random.rand(20,30); a,b = linear_sum_assignment(c)' 
100 loops, best of 3: 3.01 msec per loop 
$ python -m timeit -s 'from munkres import munkres; import numpy as np; np.random.seed(0)' 'c = np.random.rand(20,30); a = munkres(c)' 
10000 loops, best of 3: 127 usec per loop 

I sah ähnliche Ergebnisse für Größen zwischen 2x2 und 100x120 (10-40x schneller).

Answer 5

Noch eine schnelle Implementierung, wie bereits von @Matthew angedeutet: scipy.optimize hat eine Funktion namens linear_sum_assignment. Aus der Dokumentation:

Die verwendete Methode ist der ungarische Algorithmus, der auch als Munkres- oder Kuhn-Munkres-Algorithmus bekannt ist.

https://docs.scipy.org/doc/scipy-0.18.1/reference/generated/scipy.optimize.linear_sum_assignment.html