Efektywne obliczanie parami DTW przy użyciu numpy lub cython

Question

Próbuję obliczyć odległości parami między wieloma szeregami czasowymi zawartymi w tablicy numpy. Proszę zobaczyć poniższy kod

print(type(sales)) 
print(sales.shape) 

<class 'numpy.ndarray'> 
(687, 157) 

Więc sales zawiera 687 szeregów czasowych o długości 157. Korzystanie pdist do obliczenia odległości pomiędzy Detroit szeregów czasowych.

import fastdtw 
import scipy.spatial.distance as sd 

def my_fastdtw(sales1, sales2): 
    return fastdtw.fastdtw(sales1,sales2)[0] 

distance_matrix = sd.pdist(sales, my_fastdtw) 

--- EDIT: Próbowałem to robić bez pdist() -----

distance_matrix = [] 
m = len(sales)  
for i in range(0, m - 1): 
    for j in range(i + 1, m): 
     distance_matrix.append(fastdtw.fastdtw(sales[i], sales[j])) 

--- EDIT: parallelizing wewnętrzna pętla for -----

from joblib import Parallel, delayed 
import multiprocessing 
import fastdtw 

num_cores = multiprocessing.cpu_count() - 1 
N = 687 

def my_fastdtw(sales1, sales2): 
    return fastdtw.fastdtw(sales1,sales2)[0] 

results = [[] for i in range(N)] 
for i in range(0, N- 1): 
    results[i] = Parallel(n_jobs=num_cores)(delayed(my_fastdtw) (sales[i],sales[j]) for j in range(i + 1, N)) 

Wszystkie metody są bardzo powolne. Metoda równoległa trwa około 12 minut. Czy ktoś może zaproponować skuteczny sposób?

--- EDIT: Następujące kroki opisane w poniższej odpowiedzi ---

Oto jak folder lib wygląda następująco:

VirtualBox:~/anaconda3/lib/python3.6/site-packages/fastdtw-0.3.2-py3.6- linux-x86_64.egg/fastdtw$ ls 
_fastdtw.cpython-36m-x86_64-linux-gnu.so fastdtw.py __pycache__ 
_fastdtw.py        __init__.py 

Tak, istnieje wersja z fastdtw w Cython tam. Podczas instalacji nie otrzymałem żadnych błędów. Nawet teraz, kiedy wciśnięty CTRL-C podczas mojego wykonywania programu, widzę, że czysta wersja Pythona jest używany (fastdtw.py):

/home/vishal/anaconda3/lib/python3.6/site-packages/fastdtw/fastdtw.py in fastdtw(x, y, radius, dist) 

/home/vishal/anaconda3/lib/python3.6/site-packages/fastdtw/fastdtw.py in __fastdtw(x, y, radius, dist) 

Kod pozostaje wolna jak przedtem.

Answer 1

TL; DR

Twój fastdtw falled zainstalować szybki CPP-wersję i wraca po cichu do wersji czystej-python, który jest powolny.

Musisz naprawić instalację pakietu fastdtw.

---

Cała kalkulacja jest wykonywana w fastdtw, tak naprawdę nie można przyspieszyć go z zewnątrz. A równoległość i python nie jest już tak łatwą rzeczą (jeszcze?).

Dokumentacja fastdtw mówi, że potrzebuje około O(n) operacji dla porównania, więc na swój cały test-set będzie potrzebować około rzędu 10^9 operacji, która powinna zostać zakończona w ciągu około kilku sekund, jeśli zaprogramowany, na przykład C. Wydajność, którą widzisz, nie jest w pobliżu.

Jeśli spojrzymy na code of fastdtw widzimy, że istnieją dwie wersje: cython/cpp-wersja, która jest szybka i importowana przez cyton i powolny powrót z powrotem w wersji z czystym pythonem. Jeśli szybka wersja nie jest wstępnie ustawiona, wolna wersja pythona jest używana w trybie cichym.

Wykonaj obliczenia, przerywając je za pomocą Ctr+C, a zobaczysz, że jesteś gdzieś w kodzie Pythona. Możesz także przejść do swojego folderu lib i zobaczyć, że jest tylko wersja z czystym pythonem.

Tak więc instalacja szybkiej wersji fastdtw nie powiodła się. Właściwie wydaje mi się, że pakiet wheel jest spartaczony, przynajmniej dla mojej wersji jest tylko czysty kod Pythona.

Co robić?

1. Uzyskaj kod źródłowy, np. poprzez git clone https://github.com/slaypni/fastdtw
2. wchodzić fstdtw folderu i uruchom python setup.py build
3. uważaj na błędy. Kopalnia była

fatal error: numpy/npy_math.h: No such file or directory

4. naprawić.

Dla mnie fix było zmienić następujące linie w setup.py:

import numpy # THIS ADDED 
extensions = [Extension(
     'fastdtw._fastdtw', 
     [os.path.join('fastdtw', '_fastdtw' + ext)], 
     language="c++", 
     include_dirs=[numpy.get_include()], # AND ADDED numpy.get_include() 
     libraries=["stdc++"] 
    )] 

5. 3. Powtórz + 4. aż do pomyślnego
6. metę python setup.py install

Teraz Twój program powinien wynosić około 100 razy szybciej. `