使用numpy或cython進行有效的成對DTW計算

Question

我試圖計算包含在numpy數組中的多個時間序列之間的成對距離。請參考下面

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

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

所以，sales包含687時間序列長度157使用pdist來計算時間序列之間的DTW距離的代碼。

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) 

---編輯：試圖做它沒有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])) 

---編輯：並行內的循環-----

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)) 

所有的方法都很慢。平行方法大約需要12分鐘。有人可以請建議一種有效的方法嗎？

---編輯：依照下列答案中提到的步驟---

這裏是lib文件夾的樣子：

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 

因此，存在的一個fastdtw版本用Cy​​thon那裏。安裝時，我沒有收到任何錯誤。即使是現在，當我在我的程序執行過程中按下CTRL-C，我可以看到，純Python版本正在使用（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) 

的代碼仍然緩慢像以前一樣。

Answer 1

TL; DR

你fastdtw到地方自然落下安裝快速CPP-版本，靜靜回落到一個純Python版本，這是緩慢的。

您需要修復fastdtw -package的安裝。

---

整個計算在fastdtw完成的，所以你不能真正從外面加快速度。並行化和Python並不是一件容易的事情（但？）。

的fastdtw文件說，它需要一個比較約O(n)操作，讓你的整個測試設定的，它需要大約10^9操作的幅度，應在大約幾秒鐘內完成，如果編程的目的，例如，C.你看到的表現遠不及它。

如果我們看看code of fastdtw，我們看到，有兩個版本：cython/cpp-version，它通過cython快速導入並慢速回退到純python版本。如果沒有預設快速版本，則會靜默使用慢蟒版本。

因此運行你的計算，用Ctr+C中斷它，你會看到，你在Python代碼中的某處。你也可以去你的lib文件夾，看看裏面只有純python版本。

因此，您安裝的快速fastdtw版本失敗。實際上，我認爲wheel-package是拙劣的，至少對於我的版本來說，目前只有純Python代碼。

怎麼辦？

1. 獲取源代碼，例如通過git clone https://github.com/slaypni/fastdtw
2. 進入fstdtw文件夾並運行python setup.py build
3. 注意錯誤。礦是

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

修復它。

對我來說，修復是改變以下行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++"] 
    )] 

重複3 + 4。直到成功

運行python setup.py install

現在你的程序應該是快了約100倍。 `