使用numpy或cython进行高效的成对DTW计算

您所在的位置：网站首页 › 电脑安装numpy › 使用numpy或cython进行高效的成对DTW计算

使用numpy或cython进行高效的成对DTW计算

#使用numpy或cython进行高效的成对DTW计算| 来源: 网络整理| 查看: 265

我试图计算numpy数组中包含的多个时间序列之间的成对距离.请参阅下面的代码

print(type(sales)) print(sales.shape) (687, 157)

因此,sales包含长度为157的687个时间序列.使用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

所以,那里有一个cyd版本的fastdtw.安装时,我没有收到任何错误.即使是现在,当我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)

代码仍然像以前一样缓慢.

1> ead..：

TL; DR

您fastdtw不赞成安装快速的cpp版本，而无声地退回到纯Python版本，这很慢。

您需要修复fastdtw-package 的安装。

整个计算都在中完成fastdtw，因此您无法真正从外部加速计算。而且并行化和python并不是一件容易的事（还好吗？）。

该fastdtw文档说它需要O(n)进行比较的操作，因此对于整个测试集，它需要大约一个数量级的10^9操作，如果使用例如C语言进行编程，则应在几秒钟内完成。您所看到的性能离它很近。

如果我们看一下所看到的代码fastdtw，有两个版本：cython / cpp-version，它是快速的并通过cython导入，而回退的是纯Python版本。如果未预先设置快速版本，则将使用慢速python版本。

因此，运行您的计算，将其中断Ctr+C，您将看到自己在python代码中。您还可以转到您的lib文件夹，看看里面只有纯Python版本。

因此，您安装快速fastdtw 版本失败。实际上，我认为wheel-package很烂，至少在我的版本中，仅存在纯python代码。

该怎么办？

获取源代码，例如通过 git clone https://github.com/slaypni/fastdtw

进入fstdtw文件夹并运行python setup.py build

当心错误。我的是

致命错误：numpy / npy_math.h：没有此类文件或目录

修理它。

对我而言，解决方法是更改的以下行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倍左右。`

2> 小智..：

说实话，fastdtw一点都不快

from cdtw import pydtw from dtaidistance import dtw from fastdtw import fastdtw from scipy.spatial.distance import euclidean s1=np.array([1,2,3,4],dtype=np.double) s2=np.array([4,3,2,1],dtype=np.double) %timeit dtw.distance_fast(s1, s2) 4.1 µs ± 28.6 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) %timeit d2 = pydtw.dtw(s1,s2,pydtw.Settings(step = 'p0sym', window = 'palival', param = 2.0, norm = False, compute_path = True)).get_dist() 45.6 µs ± 3.39 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) %timeit d3,_=fastdtw(s1, s2, dist=euclidean) 901 µs ± 9.95 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

fastdtw比dtaidistancelib 慢219倍，比lib慢20倍cdtw

考虑改变。这是dtaidistancegit：

https://github.com/wannesm/dtaidistance

要安装，只需：

pip install dtaidistance

【本文地址】

使用numpy或cython进行高效的成对DTW计算

使用numpy或cython进行高效的成对DTW计算

今日新闻

推荐新闻