Schnellste paarweisen Distanz-Metrik in python

Ich habe ein 1D array von zahlen, und Sie möchten berechnen Sie alle paarweisen euklidischen Distanzen. Ich habe eine Methode (Dank SO), dies zu tun, mit Ausstrahlung, aber es ist ineffizient, weil es berechnet jede Strecke zweimal. Und es nicht gut zu skalieren.

Hier ist ein Beispiel, die gibt mir was ich will, mit ein array von 1000 zahlen.

import numpy as np
import random
r = np.array([random.randrange(1, 1000) for _ in range(0, 1000)])
dists = np.abs(r - r[:, None])

Was ist die Schnellste Implementierung in scipy/numpy/scikit-learn, die ich verwenden können, um dies zu tun, da es skaliert werden muss, um Situationen, in denen die 1D-array hat >10k Werte.

Hinweis: die matrix ist symmetrisch, so dass ich vermute, dass es möglich ist, zumindest ein 2x speedup durch die Auseinandersetzung, die, ich weiß nur nicht, wie.

Es gibt eine Funktion dafür: scipy.spatial.distance.pdist. Ich weiß nicht, ob dies ist die Schnellste option, da es braucht, um Prüfungen für mehrdimensionale Daten, nicht-euklidischen Normen, und andere Dinge, aber es ist gebaut.
Wie schnell brauchen Sie dazu? Es ist nie zu skalieren besser als O(n^2), da Sie zum Auffüllen n^2 Einträge ausgegeben. Ihre bestehende Lösung ist O(n^2), und es scheint nicht zu viel Raum für wichtige Optimierungen.
Dies scheint scale zu >10k Werte gut genug schon, wenn ich es versuche. Denken Sie daran, dass Sie brauchen, um füllen Sie 100 Millionen Einträge ausgegeben. Das ist fast ein halbes gigabyte der paarweisen Distanzen.
Abgeordnete für @user2357112 und @askewchan, aber stellen Sie sicher, dass Ihre numpy kompiliert wird mit BLAS-oder MKL, die Sie herunterladen, direkt von sourceforge ist wahrscheinlich nicht.
Ich glaube nicht... Wenn Sie Folgen Sie den source-code, in der end dieser wird die Funktion immer aufgerufen. Es gibt nicht nur keine Lust auf Optimierung, aber für 1D-Vektoren es ist die Quadratur und die Quadratwurzel zur Berechnung des absoluten Wertes. Wahrscheinlich schlimmer als die OP-code für seinen speziellen Anwendungsfall.
Wenn ich mich nicht Irre, scipy immer kompiliert mit BLAS, es ist nicht optional, wie bei numpy.
Ah, ich stehe korrigiert. Vielen Dank für die eigentlich auf der Suche it up 🙂
Auf der anderen Seite, aufrufen pdist mit 'cityblock' für die Metrik sollte den trick tun.
Haben Sie diesen thread? stackoverflow.com/questions/17527340/... Dort hatte ich ein ähnliches problem, wenn die arrays groß, Sie haben, um den Missbrauch Speicher-layout zu bekommen Beschleunigungen
scipy.spatial.distance nur Anrufe BLAS für eine begrenzte Anzahl von Fällen, und nur nach einigen Operationen, weil BLAS hat keine Distanz-Funktionen. Es ist nicht schneller, für die OP ' s Anwendungsfall.
Du hast Recht @larsmans, als Jaime hat das auch gesagt. Ich habe gelöscht, den Kommentar.
stört es Sie geben einen link, die Frage, auf die Sie sich beziehen? Was die post SO?
sorry - das war so lange her, dass ich mich nicht erinnern, was original-post-it war. Aber ich weiß, es war irgendwo auf SO!

InformationsquelleAutor roblanf | 2013-11-29

19

Weder die anderen Antworten ganz die Frage beantwortet - 1 wurde in Cython, wurde man langsamer. Aber beide sehr nützliche Hinweise. Folgen Sie schlägt vor, dass scipy.spatial.distance.pdist ist der Weg zu gehen.

Hier einige code:
```
import numpy as np
import random
import sklearn.metrics.pairwise
import scipy.spatial.distance

r = np.array([random.randrange(1, 1000) for _ in range(0, 1000)])
c = r[:, None]

def option1(r):
    dists = np.abs(r - r[:, None])

def option2(r):
    dists = scipy.spatial.distance.pdist(r, 'cityblock')

def option3(r):
    dists = sklearn.metrics.pairwise.manhattan_distances(r)
```
Timing mit IPython:
```
In [36]: timeit option1(r)
100 loops, best of 3: 5.31 ms per loop

In [37]: timeit option2(c)
1000 loops, best of 3: 1.84 ms per loop

In [38]: timeit option3(c)
100 loops, best of 3: 11.5 ms per loop
```
Ich habe nicht versucht, die Cython-Umsetzung (ich kann es nicht verwenden für dieses Projekt), aber ein Vergleich meiner Ergebnisse zu den anderen Antworten, dass Tat, es sieht aus wie scipy.spatial.distance.pdist ist etwa ein Drittel langsamer als die Cython-Umsetzung (unter Berücksichtigung der verschiedenen Maschinen durch benchmarking auf der np.abs-Lösung).
- Ich nehme an, dies ist so schnell wie: scikit-learn.org/stable/modules/generated/... ? die version in sklearn?
InformationsquelleAutor roblanf

Hier ist eine Cython-Implementierung, gibt mehr als 3X Verbesserung der Geschwindigkeit für dieses Beispiel auf meinem computer. Das timing sollte überprüft werden, für größere arrays hart, weil die BLAS-Routinen können wahrscheinlich viel besser skalieren als dieser eher naiv-code.

Ich weiß, Sie bat um etwas in scipy/numpy/scikit-learn, aber vielleicht eröffnen sich neue Möglichkeiten für Sie:

Datei my_cython.pyx:

import numpy as np
cimport numpy as np
import cython

cdef extern from "math.h":
    double abs(double t)

@cython.wraparound(False)
@cython.boundscheck(False)
def pairwise_distance(np.ndarray[np.double_t, ndim=1] r):
    cdef int i, j, c, size
    cdef np.ndarray[np.double_t, ndim=1] ans
    size = sum(range(1, r.shape[0]+1))
    ans = np.empty(size, dtype=r.dtype)
    c = -1
    for i in range(r.shape[0]):
        for j in range(i, r.shape[0]):
            c += 1
            ans[c] = abs(r[i] - r[j])
    return ans

Die Antwort ist ein 1-D array mit allen nicht-wiederkehrende Auswertungen.

Importieren in Python:

import numpy as np
import random

import pyximport; pyximport.install()
from my_cython import pairwise_distance

r = np.array([random.randrange(1, 1000) for _ in range(0, 1000)], dtype=float)

def solOP(r):
    return np.abs(r - r[:, None])

Timing mit IPython:

In [2]: timeit solOP(r)
100 loops, best of 3: 7.38 ms per loop

In [3]: timeit pairwise_distance(r)
1000 loops, best of 3: 1.77 ms per loop

Sicherlich meintest du fabs -- abs ist int Variante.

InformationsquelleAutor Saullo G. P. Castro

3

Mit der Hälfte der Speicher, aber 6 mal langsamer als np.abs(r - r[:, None]):
```
triu = np.triu_indices(r.shape[0],1)
dists2 = abs(r[triu[1]]-r[triu[0]])
```
InformationsquelleAutor cyborg

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.