计算机应用   2016, Vol. 36 Issue (12): 3285-3291  DOI: 10.11772/j.issn.1001-9081.2016.12.3285
0

引用本文 

林炀, 江育娥, 林劼. 基于分布式架构的时间序列局部相似检测算法[J]. 计算机应用, 2016, 36(12): 3285-3291.DOI: 10.11772/j.issn.1001-9081.2016.12.3285.
LIN Yang, JIANG Yu'e, LIN Jie. Local similarity detection algorithm for time series based on distributed architecture[J]. JOURNAL OF COMPUTER APPLICATIONS, 2016, 36(12): 3285-3291. DOI: 10.11772/j.issn.1001-9081.2016.12.3285.

基金项目

国家自然科学基金资助项目(61472082);福建省自然科学基金资助项目(2014J01220)

通信作者

林劼(1972-),男,福建三明人,副教授,博士,主要研究方向:数据挖掘, linjie891@163.com

作者简介

林炀(1991-),男,福建福州人,硕士研究生,主要研究方向:时间序列、大数据挖掘;
江育娥(1970-),女,福建古田人,教授,博士,主要研究方向:数据挖掘

文章历史

收稿日期:2016-06-22
修回日期:2016-08-25
基于分布式架构的时间序列局部相似检测算法
林炀, 江育娥, 林劼    
福建师范大学 软件学院, 福州 350108
摘要: 基于动态时间规整算法思想的CrossMatch算法可以用来解决序列间的部分相似问题,但是由于算法时间空间复杂度过高,需要消耗大量的计算资源,因此无法应用于长序列之间的计算。针对以上问题,提出了一个基于分布式平台上的时间序列局部相似性检测算法。将CrossMatch算法实现在了分布式框架上,解决了计算资源不足的问题。首先需要对序列进行切分,分别放置在不同的节点上;其次,各节点分别处理各自序列的相似部分;最后,通过对结果进行汇总并拼接,找出序列间的局部相似。实验结果表明,该算法在准确性上和CrossMatch相近,在时间上也有提升。改进后的分布式算法不仅解决了单机无法处理的长序列计算问题,而且可以通过增加并行计算节点数提高运行速度。
关键词: 动态时间规整    MapReduce    时间序列    局部相似性    并行化    
Local similarity detection algorithm for time series based on distributed architecture
LIN Yang, JIANG Yu'e, LIN Jie     
Faculty of Software, Fujian Normal University, Fuzhou Fujian 350108, China
Abstract: The CrossMatch algorithm based on the idea of Dynamic Time Warping (DTW) can be used to solve the problems of local similarity between time series. However, due to the high complexity of time and space, large amounts of computing resources are required. Thus, it is almost impossible to be used for long sequences. To solve the above mentioned problems, a new algorithm for local similarity detection based on distributed platform was proposed. The proposed algorithm was a distributed solution for CrossMatch. The problem of insufficient computing resources including time and space requirement was solved. Firstly, the series should be splited and distributed on several nodes. Secondly, the local similarity of every node's own series was dealt with. Finally, the results would be merged and assembled in order to find the local similarity of series. The experimental results show that the accuracy between the proposed algorithm and the CrossMatch algorithm is similar, and the proposed algorithm uses less time. The improved distributed algorithm can not only solve the computation problem of long sequence of time series which can not be processed by a single machine, but also improve the running speed by increasing the number of parallel computing nodes.
Key words: Dynamic Time Warping (DTW)    MapReduce    time series    local similarity    parallelization    
0 引言

时间序列是指在一定时间内某一统计指标的数值上下波动所产生的具有前后顺序关系的序列,在金融[1]、手势识别[2]、医学[3]、气象[4]、微博[5]、水文[6]、交通[7]等领域中被经常使用。而在时间序列的挖掘应用中,其中一个重要的部分就是相似度计算[8]。相似度计算直接关系到相似性搜索和聚类的进行,这些方法都可以用来找出时间序列中更深层次的知识。同时相似度计算还是异常点检测、分段等任务的基本工具,因此在时间序列的未来研究方向中,相似度计算有着举足轻重的作用。目前时间序列中常用的相似度计算方法有欧氏距离和动态时间规整(Dynamic Time Warping,DTW)算法。欧氏距离有着计算简单有效的优点,但是在很多情况下会产生相似度的计算误差。而DTW算法的动态规划思想则有效地弥补了欧氏距离的缺陷,同时动态规划思想对于相似度的准确性也有一个很大的提高。自DTW算法被引入到时间序列研究领域后就引起了广泛关注[9],之后又拓展到了多元时间序列的相似性度量[10]。然而,DTW算法本身的时间复杂度和空间复杂度过高,也正是如此DTW算法在计算长序列之间的相似度时会面临很大的困难。

传统的欧氏距离和DTW算法只能计算两条完整序列间的相似度,如果想要找出两条序列内部最为相似的片段时,这两种算法都无能为力。而文献[11]提出了一种基于DTW算法动态规划思想找出两条序列内部的局部相似算法,同时作者为算法提供了详细的实现方案和改进的CrossMatch算法[12],该算法给上述时间序列的相似片段发现问题提供了新的解决方案,同时也继承了动态规划思想所带来的准确性。然而,该算法也同样拥有和动态规划思想相同的缺点,因此仍然存在时间复杂度和空间复杂度过高的问题。在文献[12]中通过给CrossMatch算法添加了一个区域限制来减少矩阵中需要计算的范围,以此降低时间和空间复杂度,但是因此势必会带来一个未计算部分的相似子序列无法被找到的问题,相似片段发现的精度会受到影响。

针对以上CrossMatch算法在相似片段发现中会碰到的问题,本文提出了一种基于CrossMatch算法的并行化处理方式。通过对CrossMatch实行分布式的处理过程,来让整个集群承担矩阵处理的时间复杂度和空间复杂度,在保持动态规划思想准确性的前提下解决长序列的相似子序列片段发现问题。本文实验通过运行时间、平均DTW值、最大和最小DTW值几个衡量指标和CrossMatch算法进行对比,实验结果表明改良后的方法在时间和内存占用上比原算法更好。

1 相关工作 1.1 DTW算法

假设现有两条长度分别为m和n的序列x和y,那么DTW算法首先会生成一个m×n大小的矩阵,来动态地表示序列中所有点和点的累计距离,矩阵中的各点依照式(1)计算:

$d(i,j)=\left\{ \begin{align} & {{({{x}_{i}}-{{y}_{j}})}^{2}}+ \\ & \min \left\{ d(i,j-1),d(i-1,j),d(i-1,j-1) \right\}, \\ & \text{ (}0<i<=m,0<j<=n) \\ & 0,\text{ (}i\text{=0, }j\text{=0)} \\ & \infty ,\text{ (}i\text{=0, }j\ne 0\text{ }\!\!\gg\!\!\text{ }\!\!\grave{\mathrm{o}}\!\!\text{ }i\ne 0,\text{ }j\text{=0)} \\ \end{align} \right.$ (1)

在矩阵中,d(m,n)处的值即为两条序列间的DTW值,而两条序列的DTW值越小,相似程度就越大。

传统DTW算法在需要找出回溯路径的情况下,需要O(mn)的空间复杂度和时间复杂度,这在处理长序列的时候会面临很大的时间和空间上的困难,因此许多学者都对DTW算法作出了不同的改进,其中包括在DTW算法中引入下界函数[13]、加入区域限制[14-15]、引入粗粒度的递归方案[16]、提前终止计算方法[17]等。近年来又有基于DTW算法的MapReduce并行化处理方案[18]被提出,在牺牲了一些精确度的情况下使得DTW算法得以在分布式平台上运行,给DTW算法处理长序列问题提供了一种新的解决方式。

1.2 CrossMatch算法

CrossMatch算法的基本思想借用了DTW算法的动态规划思想,与DTW算法在实现上的不同之处是,DTW算法中矩阵的当前点是通过前置点的最小值来完成矩阵的计算,而CrossMatch算法中的矩阵则是通过取最大值来完成,数值越大则意味着越相似。相对于DTW算法中的矩阵,CrossMatch算法中的矩阵被称为评分矩阵,如式(2)计算:

$d(i,j)=\left\{ \begin{align} & \max \text{ }\{\text{ }0,\varepsilon {{b}_{v}}-{{({{x}_{i}}-{{y}_{j}})}^{2}}+ \\ & v(i,j-1),\varepsilon {{b}_{h}}-{{({{x}_{i}}-{{y}_{j}})}^{2}} \\ & +v(i-1,j)\varepsilon {{b}_{d}}-{{({{x}_{i}}-{{y}_{j}})}^{2}}+v(i-1,j-1)\text{ }\}\text{ } \\ & \text{(}0<i<=m,0<j<=n) \\ & 0,\text{ (}i\text{=0, }j\text{=0)} \\ & \infty ,\text{ (}i\text{=0, }j\ne 0\text{或}i\ne 0,\text{ }j\text{=0)} \\ \end{align} \right.$ (2)

式中:ε为自己设定的阈值,可以根据不同的序列和判定的严谨程度手动设置大小:ε值越大,找到的序列相似片段就越多,然而同时相似程度也越低;而ε值小的情况下所找到的相似片段就少,但是也更为相似。bv、bh和bd的值分别代表着当前点(xi,yj)、下方(xi,yj-1)、左侧(xi-1,yj)和左下方(xi-1,yj-1)对当前点的影响,可以根据自己的使用需要来调整,根据文献[12]的推荐一般bv和bh为0.5,bd为1。

同时,为了让回溯操作更方便,CrossMatch算法除了评分矩阵外,还使用了一个新的位置矩阵来保存评分矩阵中每个点的回溯起点。位置矩阵如式(3)所示:

$s(i,j)=\left\{ \begin{align} & s(i,j-1)\text{ , }(v(i,j-1)\ne 0\wedge v(i,j) \\ & =\varepsilon {{b}_{v}}-{{({{x}_{i}}-{{y}_{j}})}^{2}}+v(i,j-1)) \\ & s(i-1,j)\text{ , }(v(i-1,j)\ne 0\wedge v(i,j) \\ & =\varepsilon {{b}_{h}}-{{({{x}_{i}}-{{y}_{j}})}^{2}}+v(i-1,j)) \\ & s(i-1,j-1)\text{ },\text{ }(v(i-1,j-1)\ne 0\wedge \\ & v(i,j)=\varepsilon {{b}_{d}}-{{({{x}_{i}}-{{y}_{j}})}^{2}}+v(i-1,j-1)) \\ & (i,j)\text{ , }其他 \\ \end{align} \right.$ (3)

通过以上操作建立起两个矩阵后,还需要设置一个阈值lmin,如果在评分矩阵中某点(xi,yj)处的值大于ε乘以lmin,则将该点作为序列x和y之间有可能的相似片段终点,同时在位置矩阵中找出坐标(xi,yj)处所存储的值(xi2,yj2),这个值即为片段起点。之后需要对待定的终点进行确定,如果在评分矩阵中还有其他路径同样是以(xi2,yj2)作为起点的,则需要比较该路径的终点坐标(xi3,yj3)和(xi,yj)两点在评分矩阵中的数值,取值更大的点坐标作为路径终点,直到没有其他路径以(xi2,yj2)作为起点为止,最后得到的起点和终点坐标就是有可能的相似片段的起点和终点。将所有有可能的相似片段长度分别和长度阈值lmin进行对比,如果长度大于lmin,则作为最终的相似片段结果输出。

由于在动态规划的基本思想上和DTW算法相同,因此CrossMatch算法也同样存在着时间复杂度和空间复杂度过高的问题。在文献[12]中并没有对最后的路径进行回溯,因此每次计算都只使用一个二维数组来保存当前位置和前一行或列的计算值,空间复杂度就因此减少为了O(min(m,n))。然而时间复杂度仍然没有改进,依然是O(mn),这在处理长序列的情况下会耗费过多的时间。同时在需要进行路径回溯的情况下,CrossMatch算法的复杂度和DTW算法相同,需要O(mn)的时间复杂度和空间复杂度。因此需要一种算法,在不需要回溯时能以较低的时间复杂度找出两条时间序列的局部相似,而在需要回溯时又能同时降低时间复杂度和空间复杂度,还能够拥有和无区域限制时的CrossMatch算法相近的效果。

2 分布式CrossMatch算法

针对CrossMatch算法很难处理长序列的情况,本文提出一种基于并行化的CrossMatch(Distributed CrossMatch,DCM) 算法,同时将这种并行化方法实现在Hadoop的MapReduce框架上,解决长序列计算矩阵时消耗过多时间复杂度和空间复杂度的问题。算法首先需要对被测序列进行切割并分配到集群中的不同节点上;其次在各节点内对各自的序列片段并行的建立矩阵,找出符合条件的片段相似路径;最后将所有节点上的路径进行汇总并按一定的条件进行拼接和筛选,得到的结果即为符合的相似路径。下面介绍详细的算法过程。

2.1 时间序列的分割

由于改进后的算法是用于集群中分布式运行,因此需要先对序列进行一些分割处理。现假设集群中有k个节点,首先需要将序列x分割为k份,每一份的长度并没有特别的要求,本论文实验方案采用的是平均分为k份。将分割后的片段按顺序从头到尾标记为1,2,…,k,将标记编号和分割好的序列片段分别放置到集群中的每一个节点上。对于序列y则不进行处理,只需将序列y直接放置到集群中的每一个节点上。

2.2 DCM算法并行化矩阵计算 2.2.1 评分矩阵

DCM并行化算法的矩阵计算在每个节点上并不完全相同,首先需要每个节点对各自所放置的x序列片段进行判断,如果该片段为x序列的第一个切割分段,则按照CrossMatch算法的式(2)进行评分矩阵计算,否则对评分矩阵的第一列按照式(4)进行评分矩阵计算,对矩阵的其他部分仍然按照式(2)计算。

$d(i,j)=\left\{ \begin{align} & \max \left\{ 0,\varepsilon {{b}_{v}}-{{({{x}_{i}}-{{y}_{j}})}^{2}},\varepsilon {{b}_{h}}-{{({{x}_{i}}-{{y}_{j}})}^{2}}, \right. \\ & \left. \varepsilon {{b}_{d}}-{{({{x}_{i}}-{{y}_{j}})}^{2}} \right\}\text{,(}0<j<=n) \\ & 0,\text{ (}j\text{=0)} \\ \end{align} \right.$ (4)

不同x序列分段公式上最大的不同在于评分矩阵第一列的计算上,对分割后非首段的x序列的矩阵第一列,DCM算法并没有按照CrossMatch算法的对之前计算好的值向后进行累加的办法。因为在分布式的计算完成之后,还需要对分布计算得到的矩阵中的片段进行重新拼接,因此使用累加的方法会导致在分段处的拼接无法进行。进行改进后的公式在保留了序列间相似特征的情况下,还能在拼接时的某些情况让路径很方便地连接起来,拼接详细过程会在后文阐述。

2.2.2 位置矩阵

CrossMatch算法被提出时就采用了一个新提出的位置矩阵来记录每个点的起始坐标,因此不需要回溯操作,可以直接地确定每个相似路径的起点;同时不进行回溯还可以将空间复杂度从O(mn)降为O(min(m,n)),这样可以解决很多机器内存不足的问题。但是这种不使用回溯操作的方法无法得到相似路径中点和点之间的相似对应关系,而在很多时候,需要通过回溯来确定路径是否有出现异常的情况。为了发挥出分布式处理的优势,选择保留完整的评分矩阵,允许评分矩阵进行回溯操作。同时为了能快速地找出路径的起点,仍然保留了位置矩阵。同需要O(mn)空间复杂度的评分矩阵不同,位置矩阵不需要回溯操作,因此每次只需要两行或两列来保存当前正在计算的点起始位置,空间复杂度为O(min(m,n))。节点上的位置矩阵的具体实现方式如式(3)。

2.2.3 路径筛选

各节点中的上述矩阵计算完成之后,与CrossMatch算法不同,各节点还需要从各自的矩阵中找出一些符合条件的路径,以用于之后的拼接操作。首先设置两个阈值p和r:p为下文中对每个分段需要重新计算的列数,需要根据自己的节点性能和序列长度来决定;r为下文中一种路径筛选方式中需要设置的百分比数值,设置得越小所能找到的路径越多,但是需要占用更多的网络传输和时间空间资源。从每个矩阵中找出符合以下三种条件的路径:

case1 评分矩阵内值大于lmin乘以ε的坐标,作为路径的终点,同时在位置矩阵中查找相同坐标处的值,作为路径的起点。

case2 评分矩阵内值大于lmin乘以ε乘以r的坐标,作为路径的终点,同时在位置矩阵中查找相同坐标处的值,如果该值的横坐标xi符合(0<xi<p),则将该值作为路径的起点。

case3 评分矩阵内最后一列的值大于0的坐标,作为路径的终点,同时在位置矩阵中查找相同坐标处的值,作为路径的起点。

上述的case1规则实际就和CrossMatch算法相同,找出的路径是各个节点序列片段的相似路径,而case2和case3的作用是用于之后能够对所有节点上的路径进行拼接。在所有节点都找出以上三种条件的路径之后,需要保存路径的起点、终点和终点位置处的评分矩阵和位置矩阵的数值,并通过网络传输到汇总节点上。考虑到网络传输数据对运行效率的影响,我们没有对所有节点上的评分矩阵和位置矩阵进行汇总。由于后续的拼接操作在某些情况下有需要这两个矩阵部分内容的时候,因此我们选择对每个节点上的矩阵最后一列进行汇总,在汇总的节点上对每一个矩阵的前p列进行重新计算,具体过程会在后文阐述。

2.3 路径拼接

在汇总后的节点上,路径需要经过两次拼接,第一次是对每两个相邻矩阵的路径都进行一次拼接,假设x序列现有k个分段,则第一次拼接要对k个矩阵中的路径进行k-1次拼接,拼接后得到的路径最长可以跨越两个矩阵。第二次拼接则是对第一次拼接后的结果进行汇总并完成最终的拼接,拼接后得到的路径最长可以跨越k个矩阵。

2.3.1 相邻矩阵路径拼接

为了拼接需要,首先需要使用之前传输好的评分矩阵和位置矩阵的最后一列,对除了x序列第一个分段所在节点以外的其他每个节点上矩阵的前p列进行重新计算。不传输已经计算好的矩阵原因有三个:一是因为网络传输速度的限制,如果对所有矩阵都进行传输会浪费很多的时间和带宽资源;二是因为内存空间的限制,在汇总后的节点上储存所有矩阵可能会导致内存空间的不足;三是因为重新计算后的结果和每个节点单独计算的结果实际上并不相同,由于重新计算依靠的是矩阵最后一列对下一个矩阵的前p列进行计算,使用的是式(2),而之前分布式各节点计算好的矩阵大多所使用的公式为式(4),因此重新计算后的矩阵前p列的值更贴近于原CrossMatch算法。

在矩阵的重新计算完成后,接下来需要对之前汇总的路径进行拼接和重新筛选。首先需要对每一条路径的情况进行判断,尚未判断的路径需要放置在汇总节点的待判定路径中。对所有待判定路径按以下几种情况进行一一判断,假设当前判定路径中的路径为路径A和路径B,则判断是否符合表 1中的情况。

表 1 路径拼接情况判别表

情况1 如果有两条路径A和B符合情况1,则将路径A的起点和路径B的终点进行拼接,形成一条新的路径,将路径B的起点设为新路径的起点,将路径A的终点设为新路径的终点。同时还要记录下路径A的起点坐标作为拼接点坐标,以用于后面的汇总拼接。将路径A和路径B的终点评分矩阵处数值相加作为新路径的终点数值。如图 1中的①所示,同时在汇总节点上删除路径A和路径B,并将拼接好的新路径放置到待判定路径中。

图 1 拼接示意图

情况2 如果有一条路径A符合情况2,则将坐标(xi2,yj2)设为新路径的起点,将路径A的终点设为新路径的终点。同时还要记录下(xi,yj)坐标作为拼接点坐标,以用于后面的汇总拼接。将路径A的终点评分矩阵处数值与重新计算后的(xi,yj)处评分矩阵数值相加作为新路径的终点数值。如图 1中的②所示,同时在汇总节点上删除路径A,并将拼接好的新路径放置到待判定路径中。

情况3 如果待判定路径A不符合情况2且没有情况1中可以拼接的路径B,则对路径A进行以下判断:如果路径未经过拼接且路径终点坐标处的评分矩阵数值大于等于lmin乘以ε,且路径长度大于lmin,则将该路径保存并输出,同时将该路径从汇总节点中的待判定路径里删除。如果路径未经过拼接且终点坐标处的评分矩阵数值小于lmin乘以ε或者路径长度小于lmin,则将该路径从待判定路径里删除。如果路径有按照表 1的情况拼接过,则将该路径保存并输出。

2.3.2 路径的汇总拼接

在得到路径的两两拼接结果后,需要对路径进行最终的结果汇总,并完成最后的拼接。将所有汇总的路径都放置到待判定路径中,对于相邻矩阵路径拼接中的两个分段编号为t-1和t矩阵中的路径A,与分段编号为t和t+1矩阵中的路径B,拼接条件如下:

情况1 若A和B都在相邻矩阵路径拼接中有进行过拼接,且B的起点坐标与A的拼接点坐标相同,则将A的起点作为新路径的起点,B的终点作为新路径的终点,将路径A和路径B的终点评分矩阵处数值相加作为新路径的终点数值,同时将路径A和B从待判定路径中删除,将新路径加入到待判定路径中。

情况2 若A和B都没有在相邻矩阵路径拼接中有过拼接,且A与B的起点终点坐标完全相同,则只保留路径A,从待判定路径中删除路径B。

情况3 若A在相邻矩阵路径拼接中有进行过拼接,而B没有拼接过,且B的起点坐标与A的拼接点坐标相同,则只保留路径A,从待判定路径中删除路径B。

情况4 若A在相邻矩阵路径拼接中没有进行过拼接,而B有拼接过,且B的起点坐标与A的起点坐标相同,则只保留路径B,从待判定路径中删除路径A。

情况5 若待判定路径A没有上述情况中可以拼接的待判定路径B,判断如果路径终点坐标处的评分矩阵数值大于等于lmin乘以ε,且路径长度大于lmin,则将该路径作为序列x和序列y的最终局部相似结果输出,并从待判定路径中将A删除。否则就只将A从待判定路径中删除。

上述的情况1~4中,A和B在矩阵t中都有相同的路径,因此需要对路径做一个拼接或者删除重复的操作。汇总拼接的过程并不需要对矩阵的前p列进行重新计算,因此消耗的资源相比相邻矩阵路径拼接更少。最终经过情况5所筛选出来的路径即为序列x和序列y的最终局部相似。

由于依靠集群分担了计算矩阵的任务,因此在处理长序列时最困难的矩阵计算部分的时间复杂度降为O(mn/k),各节点上的空间复杂度也只需要O(mn/k),这样在处理长序列时的时间和空间问题就得到了缓解。同时随着节点数k的上升,复杂度可以不断地降低,因此在大集群处理长时间序列问题时可以有效地解决单机所遇到的时间和空间问题。

下面给出一个CrossMatch算法和DCM算法找出局部相似片段时的例子,图 2是两种算法对同一序列生成的不同评分矩阵,其中ε为14,lmin为2,r为0.5,p为3。在CrossMatch算法的评分矩阵中,矩阵中的深色部分代表着最后发现的相似路径,可以看到相似路径在坐标的(2,1)到(5,4)之间。而在DCM算法中,浅灰色和深色部分为符合2.2.3 节中三种case的路径,而较浅色部分是最后被表 1中的情况3淘汰掉的不符合条件的路径,深色部分是拼接操作后保留下来的符合条件的相似路径。可以看到节点1中的深色部分和节点2中的深色部分符合表 1中的情况1拼接,而在拼接操作后,节点1的(3,2)点处数值26加上节点2的(2,4)点的数值24后的结果为50,因此最终路径终点处数值为50,这也和CrossMatch算法的(5,4)点处的数值49非常接近。同时在拼接后,DCM算法找出的符合条件的路径和CrossMatch算法相同,都为x序列的2~5段与y序列的1~4段。

图 2 两种算法的评分矩阵对比示意图
3 DCM算法的MapReduce实现

MapReduce框架能够有效地处理海量数据所带来的时间复杂度和空间复杂度问题。在MapReduce框架中,通常分为map和reduce两个阶段。DCM算法的MapReduce实现具体流程如图 3

图 3 DCM算法的MapReduce流程

算法有两个MapReduce,在第一个MapReduce阶段,map的所有操作都在集群中的各个节点处单独执行,主要是进行并行化矩阵的计算。map的输入数据是两条经过处理后的待测时间序列,例如在集群中的节点t中,输入数据就为x的序列片段xt和序列y。按照2.2节中的方法,通过在不同节点上并行计算出各自节点的评分矩阵和位置矩阵,再筛选出符合条件的路径。假设序列x被切割为了k个分段,每个节点所处理的x序列分段编号为i,则按以下条件给予输出的key和value值:

情况1 i=1,则map的输出key为1,输出value为矩阵最后一列与经过2.2.3 节中的三个case筛选出的路径。

情况2 1<i<k,则map的输出key为i-1和i,key为i-1,对应的value为经过2.2.3 节中的三个case筛选出的路径;key为i,对应的value为矩阵最后一列与经过2.2.3节中的三个case筛选出的路径。

情况3 i=k,则map的输出key为k,value为经过2.2.3 节中的三个case筛选出的路径。

通过上述key的选择可以将两两相邻的矩阵结果汇总到同一个节点上,每个key只处理两个矩阵的拼接过程。对于k个x分段,会产生k-1个key值。

reduce阶段主要是在每个reduce节点汇总map的输出数据并进行处理。按照2.3.1节中的方法,首先通过汇总的矩阵最后一列重新计算下一个矩阵的前p列,之后再对所有待判定路径进行筛选和拼接。第一个MapReduce(MR)的输入输出情况如表 2所示。

表 2 第一个MR输入输出示意表

在第二个MapReduce阶段只有一个map而没有reduce,map起到的是最终汇总作用。在将上一个reduce的所有结果进行汇总后,对所有路径进行最后的拼接。拼接的规则按照2.3.2节中的方法,

由2.3.2节中的算法描述中可以看出,第二次的map是对所有路径进行一个最后的拼接和筛选,因此需要将map的数量设置为1个节点,这样才能将所有的路径都进行一次最后的汇总拼接。第二个MapReduce的输入输出情况如表 3所示。

表 3 第二个MR输入输出示意表

使用两个MapReduce的原因是出于计算资源上的考虑,如果在reduce中对所有路径就进行拼接的话,在长序列情况下会出现计算资源不足的问题。因此将重新计算和拼接的过程先交给不同的reduce节点处理,这样处理后的路径在第二个map汇总时只需要很简单的判断就可以对路径进行最后的拼接,这种方法可以解决计算资源的问题。同时reduce阶段的拼接只是对于跨越了两个矩阵的路径进行拼接,而在第二个map的拼接则会对跨越了两个以上矩阵的路径进行拼接。

算法的map阶段和reduce阶段对路径的操作过程可以从图 4中的例子看出。对于两条时间序列S和Q,首先将序列S切分为S1、S2、S3三条序列,并放置在三个map节点上,在这次map中每个节点会找出各自序列的局部相似。由于x被分为了3个分段,因此map的结果会产生两个key值。在两个不同key上的reduce会在各自节点上进行相似路径的拼接,例如图中S1的末端和S2的起点都对应着Q上的同一部分,因此将S1和S2的首尾拼接起来,而S2和S3没有路径可以拼接,因此经过2.3.1 节中的情况3筛选后保留了下来。第二个map中对reduce的所有路径进行汇总,同时可以看到S2和Q与S′和Q的相似路径中有一部分重复了,因此按照2.3.2节中的情况3对S2中的相似路径进行了删除。最终的局部相似结果就如图中第二个map处所示。

图 4 DCM算法的MapReduce例子
4 实验及结果分析 4.1 数据集

本文的数据集采用和文献[12]相同的数据集,其中包含由不连续的正弦波和白噪声组成的RandomSines数据集,还有现实中采集的数据集。对于实验中的所有数据都将p设为5,r设为0.5,lmin和ε用和文献[12]中相同的数值,lmin设为序列长度的15%,数据集中各序列的ε为:RandomSines为1.0E-4,Automobile为8.5E+4,Web为4.0E+4,Sunspots为3.0E+2。

4.2 实验环境

本文的算法是应用Java在Hadoop集群上实现的,集群中的每个节点CPU使用Intel Core 3.20 GHz,内存为8 GB,操作系统为64位centos7,使用hadoop-2.5.2 和1.7.0_71版jdk。集群中的节点数量为4个,同时4个节点都为datanode,在4个节点中选取其中一个既作为datanode也作为namenode。

4.3 实验结果评估

实验对相同数据集使用了CrossMatch算法和DCM算法来进行评估,对两种算法所找出的相似子序列分别计算其DTW值,通过DTW值及其相关指标来衡量CrossMatch算法和DCM算法所找出的路径的相似度。实验结果如表 4~7所示。

表 4 CrossMatch找出子序列DTW值和子序列数比较
表 5 DCM找出子序列DTW值和子序列数比较(2节点)
表 6 DCM找出子序列DTW值和子序列数比较(3节点)
表 7 DCM找出子序列DTW值和子序列数比较表(4节点)

表 4~7中可以看出,在与传统CrossMatch算法比较时,新的分布式算法能够找出的相似路径条数不会少于CrossMatch算法,一部分数据在节点增多时还能找出更多的路径。同时除了Web数据集的四个节点情况外,DCM算法的路径平均DTW值都相比CrossMatch算法找出的路径更小,而Web数据集的四个节点所计算出的DTW值和CrossMatch算法的DTW值十分接近,这表明分布式算法所找出的路径和CrossMatch算法所找出的路径具有大致相同的效果,同时在某些情况下,DCM找出的路径能够比CrossMatch算法找出的更为相似。而在各数据路径的最大和最小DTW值上,可以看到大部分情况下DCM找出的路径最大和最小DTW值都至少和CrossMatch算法相近或是更小,这也表明DCM所找出的路径相似度相对更加稳定。

图 5是DCM算法和CrossMatch算法运行在测试数据集上的时间对比,从图中可以看出,DCM中的每组数据所用时间都随着节点数的增加而减少,这是因为节点数越多,就有更多的计算资源来分担算法中矩阵处理时的时间复杂度。而和CrossMatch算法相比,DCM在不同节点的情况下所用的时间都少于CrossMatch算法,而且随着序列长度的上升,DCM的所用时间增幅也明显小于CrossMatch算法。这是因为在长序列的情况下,单机的物理内存已经不足以处理长序列,因此调用了额外的虚拟内存来计算,所以在序列长度增加的时候单机所用的时间也有了明显的增长。实验结果表明改进算法在所用时间和内存不足的问题上都优于CrossMatch算法。

图 5 时间比较图
5 结语

在时间序列相似度的比较上,如果能解决高时间复杂度和空间复杂度的问题,DTW算法的动态规划思想目前仍然能获得很好的效果。本文提出的DCM算法在沿用了动态规划思想的前提下,解决了处理长序列时的时间和空间问题,同时在准确性上还有略微提高。但是DCM算法目前在几个阈值的选取上还没有一个可以严格确定的标准,在尝试批量处理多组时间序列以找出它们中的相似片段时遇到了困难,同时本文的分布式方法如果使用回溯操作会较为麻烦,这些都是未来需要改进的方面。

参考文献
[1] 张炜, 范年柏, 汪文佳. 基于自适应遗传算法的股票预测模型研究[J]. 计算机工程与应用, 2015, 51 (4) : 254-259. ( ZHANG W, FAN N B, WANG W J. Stock prediction model research based on improved adaptive genetic algorithm[J]. Computer Engineering and Applications, 2015, 51 (4) : 254-259. )
[2] 周治平, 苗敏敏. 改进的马氏距离动态时间规整手势认证方法[J]. 计算机应用, 2015, 35 (5) : 1467-1470. ( ZHOU Z P, MIAO M M. Dynamic time warping gesture authentication algorithm based on improved Mahalanobis distance[J]. Journal of Computer Applications, 2015, 35 (5) : 1467-1470. )
[3] 纪丽珍, 李鹏, 李林, 等. 冠心病患者心脏电-机械活动时间序列的熵分析[J]. 计算机工程与应用, 2016, 52 (10) : 265-270. ( JI L Z, LI P, LI L, et al. Analysis of cardiac electro-mechanical time-series in patients with coronary artery disease based on entropy[J]. Computer Engineering and Applications, 2016, 52 (10) : 265-270. )
[4] TEMME C, EBINGHAUS R, EINAX J W, et al. Time series analysis of long-term data sets of atmospheric mercury concentrations[J]. Analytical and Bioanalytical Chemistry, 2004, 380 (3) : 493-501. doi: 10.1007/s00216-004-2715-x
[5] 苑卫国, 刘云. 微博用户特征量增长规律研究[J]. 计算机研究与发展, 2015, 52 (2) : 522-532. ( YUAN W G, LIU Y. Growth law of user characteristics in microblog[J]. Journal of Computer Research and Development, 2015, 52 (2) : 522-532. )
[6] 程习锋, 万定生, 王亚明. 水文时间序列相似性查询优化算法[J]. 计算机工程与设计, 2013, 34 (11) : 4046-4050. ( CHENG X F, WAN D S, WANG Y M. Similarity search optimization algorithm in hydrological time series[J]. Computer Engineering and Design, 2013, 34 (11) : 4046-4050. )
[7] 唐毅, 刘卫宁, 孙棣华, 等. 改进时间序列模型在高速公路短时交通流量预测中的应用[J]. 计算机应用研究, 2015, 32 (1) : 146-149. ( TANG Y, LIU W N, SUN D H, et al. Application of improved time series model in forecasting of short-term traffic flow for freeway[J]. Application Research of Computers, 2015, 32 (1) : 146-149. )
[8] KEOGH E, KASETTY S. On the need for time series data mining benchmarks:a survey and empirical demonstration[J]. Data Mining and Knowledge Discovery, 2003, 7 (4) : 349-371. doi: 10.1023/A:1024988512476
[9] BERNDT D J, CLIFFORD J. Finding patterns in time series:a dynamic programming approach[M]. Menlo Park, CA: American Association for Artificial Intelligence, 1996 : 229 -248.
[10] 李正欣, 张凤鸣, 李克武, 等. 一种支持DTW距离的多元时间序列索引结构[J]. 软件学报, 2014, 25 (3) : 560-575. ( LI Z X, ZHANG F M, LI K W, et al. Index structure for multivariate time series under DTW distance metric[J]. Journal of Software, 2014, 25 (3) : 560-575. )
[11] TOYODA M, SAKURAI Y. Discovery of cross-similarity in data streams[C]//Proceedings of the 2010 IEEE 26th International Conference on Data Engineering. Piscataway, NJ:IEEE, 2010:101-104.
[12] TOYODA M, SAKURAI Y, ISHIKAWA Y. Pattern discovery in data streams under the time warping distance[J]. The VLDB Journal, 2013, 22 (3) : 295-318. doi: 10.1007/s00778-012-0289-3
[13] KEOGH E, RATANAMAHATANA C A. Exact indexing of dynamic time warping[J]. Knowledge and information systems, 2005, 7 (3) : 358-386. doi: 10.1007/s10115-004-0154-9
[14] SAKOE H, CHIBA S. Dynamic programming algorithm optimization for spoken word recognition[J]. IEEE Transactions on Acoustics, Speech and Signal Processing, 1978, 26 (1) : 43-49. doi: 10.1109/TASSP.1978.1163055
[15] ITAKURA F. Minimum prediction residual principle applied to speech recognition[J]. IEEE Transactions on Acoustics, Speech and Signal Processing, 1975, 23 (1) : 67-72. doi: 10.1109/TASSP.1975.1162641
[16] SALVADOR S, CHAN P. Toward accurate dynamic time warping in linear time and space[J]. Intelligent Data Analysis, 2007, 11 (5) : 561-580.
[17] KIM M S, KIM S W, SHIN M. Optimization of subsequence matching under time warping in time-series databases[C]//SAC'05:Proceedings of the 2005 ACM Symposium on Applied Computing. New York:ACM, 2005:581-586.
[18] HONG Y, SHUQIANG Y, SHAODONG M, et al. A novel parallel scheme for fast similarity search in large time series[J]. China Communications, 2015, 12 (2) : 129-140. doi: 10.1109/CC.2015.7084408