![](https://img.php1.cn/3cd4a/1eebe/cd5/eec57030b649a106.webp)
对于每个对齐位置j,必须对m个贡献进行求和。结果,计算所有锁定步长,对齐的渐近最坏情况复杂度,与时间序列长度m和n_O((n-m + 1)* m)的乘积成正比。即使对于中等大小的查询和流,此数字也可能是巨大的,当以简单的方式执行时,可能使大规模时间序列对齐在计算上难以处理。将针对特殊情况p = 2讨论如何实现以超快的对数线性时间运行的CUDA加速方案。
查看ECG流的较大部分(参见图2)时,可能会发现平均信号值存在时间漂移,也称为基线漂移。通常在连续测量的时间序列中发生,并且可能是由多种外部因素引起的,例如由于心电图中的汗水导致皮肤电导率变化,影响心电图中电极的人体运动,电阻漂移以及温度引起的电压漂移电源变化,记录环境数量时的温度漂移,圣诞节等季节性影响或全球大流行中股价的时间漂移。
![](https://img.php1.cn/3cd4a/1eebe/cd5/bdd1ca32a69bc8b2.webp)
图2:使用欧几里德距离作为滚动相似性度量,在较长的心跳流S(橙色信号)中对齐的短ECG查询Q(蓝色信号)。注意S值的时间漂移。
为相似形状的数据流进行挖掘时,基线漂移是有问题的–在测量轴上具有不同偏移量的两个相似形状可能比具有相似偏移量的两个不相似形状具有更大的距离。简单有效的对策,查询和候选序列引入规范化过程。例如,可以计算查询muQ的平均值,并为n-m + 1个候选序列muS [j]中的每一个计算平均值,消除相应窗口中的偏移量(请参见图3)。下面,将局部均值调整后的滚动欧氏距离mdist称为:
![](https://img.php1.cn/3cd4a/1eebe/cd5/bdd1ca32a69bc8b2.webp)
![](https://img.php1.cn/3cd4a/1eebe/cd5/7cccb7e4b6cb5cb8.webp)
图3:平均值不消失的心跳(左侧蓝色信号)及其均值调整后的变量(右侧橙色信号)。
仔细观察图1和图2,可以进一步看出幅度的时间变化。蓝色查询中值的范围明显小于图1中橙色候选序列的幅度。在挖掘形状时,标度的时间漂移可能导致无意义的匹配。简单的解决方案,分别将值除以查询sigmaQ和比对候选sigmaS [j]的标准偏差来对比例进行归一化。均值和幅度调整称为z归一化,指均值和单位方差均消失的正常随机变量的z得分(参见图4)。相应的滚动度量应称为zdist:
![](https://img.php1.cn/3cd4a/1eebe/cd5/7494af3c1cda418d.webp)
库RapidAligner以大规模并行方式支持CUDA加速计算的上述三个滚动度量sdist,mdist和zdist。将从JupyterLab内看到简单用法。
![](https://img.php1.cn/3cd4a/1eebe/cd5/b428d8f746fb8d47.webp)
图4:心跳具有均值和非单位方差不消失(左侧的蓝色信号)及均值和幅度调整(z归一化)的变量(右侧的橙色信号)。
RapidAligner的实际应用
开始计算数字。将使用讨论的三个指标sdist,mdist和zdist对齐22小时ECG流中的单个心跳。该数据集是屡获殊荣的UCR-Suite网站上列出的实验的一部分。克隆了RapidAligner存储库后,立即将RapidAligner库以及CuPY,NumPy和Matplotlib导入,以用于以后的验证和可视化。
查看原始小区1 + 2.ipynb 与托管的GitHub上
在下一步中,将加载ECG数据。查询的长度相当短,只有421个条目,但流显示了大约2000万个时间滴答。对完整查询(蓝色)和流的初始1000值(橙色)的首次检查显示偏移和幅度的时间漂移。
查看原始小区3 + 4.ipynb 与托管的GitHub上
下面的代码,将使用sdist度量来对齐查询在流中的位置,计算所有20,140,000-421 + 1的距离得分,进行argmin归约以确定最佳对齐位置。对于实验,在DGX A100服务器中选择单个A100 GPU 。需要注意的是,如果只在最佳匹配感兴趣的人们,可以进一步通过采用下限级联,作为证明加速已经快速计算。相反,rapidAligner的sdist调用返回所有位置的对齐分数,允许以后进行处理,例如计算排名匹配的不重叠分区。进一步重复对齐几次,进行可靠的运行时测量。两种计算模式“ fft”和“天真”都非常快,并且返回难以区分的结果:
- “天真”:将所有n-m + 1个对齐候选者(可选)进行归一化,分别以最小的内存占用量进行比较,但渐近计算复杂度为O(n * m)。使用翘曲汇总的统计信息和累加方案,该模式仍然相当快。
- “ fft”:如果m> log_2(n),可以利用卷积定理来显着加快计算速度,从而导致O(n * log n)运行时,但占用的内存更大。计算模式完全独立于查询的长度,建议使用大输入量。较高的内存使用量,主要是由计算速度快但位置不当的原语引起的,例如CUDA加速的快速傅立叶变换和前缀扫描。
查看原始Cell5.ipynb 主办了由GitHub上
查询和流(主题)都以双精度形式存储为普通NumPy数组在CPU上。结果,测得的运行时间包括CPU和GPU之间昂贵的内存传输。RapidAligner允许与所有CUDA阵列接口兼容框架(例如PyTorch,CuPy,Numba,RAPIDS和Jax)进行无缝互操作。可以进一步减少在快速GPU RAM中缓存数据时的运行时间,以避免CPU和GPU之间不必要的内存移动。即使在短查询条件下,基于傅立叶的模式,胜过简单的模式
查看原始Cell6.ipynb 主办了由GitHub上
这相当于单个GPU上每秒高达25亿次的完全对齐。仅使用驻留在GPU上的输入数据来报告运行时。sdist产生的匹配已经是不错的匹配,检查均值调整是否可以改善结果:
查看原始Cell7.ipynb 主办了由GitHub上
正如预期的那样,平均调整返回了更好的匹配,考虑的候选对象沿测量轴的相对偏移没有消失。对于2000万个对齐位置,执行时间保持在10 ms的低水平。这相当于每秒20亿次完全对齐。仍然可以使用zdist改善幅度失配:
查看原始Cell8.ipynb 主办了由GitHub上
Etvoilà,z归一化的欧几里得距离,揭示了数据库中的doppelgänger,与查询几乎没有区别。在每秒超过16亿次对齐中,性能仍然很高。傅里叶模式的一个惊人特性,运行时间实际上独立于查询长度,对于固定的流长度和变化的查询大小,运行时间是恒定的。当对齐非常长的查询时,变得很方便。
结论
在较长的时间序列数据流中寻找形状是一项计算量大的任务,通常作为独立例程或作为子例程嵌入高级算法中,例如用于异常检测。具有空前的内存带宽的大型并行加速器(例如NVIDIA A100 GPU)非常适合解决这一挑战。quickAligner是轻量级的库,每秒处理数十亿个比对,同时支持候选序列的通用归一化模式。可以进一步采用高度优化的FFT例程cuFFT和前缀扫描CUB从CUDA-X软件堆栈中获取数据,提供与查询长度无关的对齐模式。源代码和笔记本可在NVIDIA RapidAligner下公开获得。