时间序列数据中的模式检测

Question

我有一个表示时间序列的数据框架，例如：

时间戳：1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|17|18|19|20|21|22|23|24|25|26|27|28...

价值：0|0|3|6|3|3|6|3|3|6 |3 |0 |0 |0 |1 |3 |7 |0 |0 |1 |3 |7 |1 |3 |7 |3 |6 |3 ...

目标是对不同的模式(可以是随机位置)进行分类，并对值进行标记。这意味着找到模式：

1. 3-6-3
2. 1-3-7

并将数据帧扩展到

时间戳：1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|17|18|19|20|21|22|23|24|25|26|27|28...

价值：0|0|3|6|3|3|6|3|3|6 |3 |0 |0 |0 |1 |3 |7 |0 |0 |1 |3 |7 |1 |3 |7 |3 |6 |3 ...

标签：c|c|a|a|a|a|a|a|a|a |a |c |c |c |b |b |b |c |c |b |b |b |b |b |b |a |a |a ...

请注意，这种模式没有相同的长度。

问题是可以使用什么样的算法来解决这个无监督的学习问题，也许还可以使用哪些库/框架来实现这样的任务。

提前感谢！

Answer 1

我的回答是关于模式匹配的问题。在成功匹配后，以下算法给出匹配序列的起始和位置作为输出。然后，您可以使用这些信息作为标签，如您在您的问题中所描述的。

我推荐本文中介绍的SPRING算法：

时间翘曲距离下的流监测(Sakurai，Faloutsos，Yamamuro) http://www.cs.cmu.edu/~christos/PUBLICATIONS/ICDE07-spring.pdf

算法的核心是DTW距离(动态时间翘曲)，得到的距离是DTW距离。DTW的唯一区别是优化，因为“流”(您正在寻找匹配的顺序)的每个位置都是匹配的可能起点，而不是计算每个起点的总距离矩阵的DTW。您提供了一个模板、一个阈值和一个流(这一概念是为从datastream中匹配而开发的，但是您可以通过简单的循环将该算法应用到数据帧上)。

注意：

• 门槛的选择并非微不足道，可能会带来重大挑战--但这将是另一个问题。(阈值= 0，如果您只想匹配完全相同的序列，则阈值>0，如果您也想匹配相似的序列)
• 如果要查找多个模板/目标模式，则必须创建SPRING类的几个实例，每个实例用于一个目标模式。

下面的代码是我的(杂乱的)实现，它缺少很多东西(比如类定义等等)。然而，它是有效的，并且应该帮助你找到答案。

我的实施情况如下：

#HERE DEFINE 
#1)template consisting of numerical data points 
#2)stream consisting of numerical data points
template = [1, 2, 0, 1, 2]
stream = [1, 1, 0, 1, 2, 3, 1, 0, 1, 2, 1, 1, 1, 2 ,7 ,4 ,5]

#the threshold for the matching process has to be chosen by the user - yet in reality the choice of threshold is a non-trivial problem regarding the quality of the matching process
#Getting Epsilon from the user 
epsilon = input("Please define epsilon: ")
epsilon = float(epsilon)

#SPRING
#1.Requirements
n = len(template)
D_recent = [float("inf")]*(n)
D_now=[0]*(n)
S_recent=[0]*(n)
S_now=[0]*(n)
d_rep=float("inf")
J_s=float("inf")
J_e=float("inf")
check=0

#check/output
matches=[]

#calculation of accumulated distance for each incoming value
def accdist_calc (incoming_value, template,Distance_new, Distance_recent):
    for i in range (len(template)):
        if i == 0:
            Distance_new[i] = abs(incoming_value-template[i])
        else:
            Distance_new[i] = abs(incoming_value-template[i])+min(Distance_new[i-1], Distance_recent[i], Distance_recent[i-1])
    return Distance_new

#deduce starting point for each incoming value
def startingpoint_calc (template_length, starting_point_recent, starting_point_new, Distance_new, Distance_recent):
    for i in range (template_length):
            if i == 0:
                #here j+1 instead of j, because of the programm counting from 0 instead of from 1
                starting_point_new[i] = j+1
            else:
                if Distance_new[i-1] == min(Distance_new[i-1], Distance_recent[i], Distance_recent[i-1]):
                    starting_point_new[i] = starting_point_new[i-1]                    
                elif Distance_recent[i] == min(Distance_new[i-1], Distance_recent[i], Distance_recent[i-1]):
                    starting_point_new[i] = starting_point_recent[i]                    
                elif Distance_recent[i-1] == min(Distance_new[i-1], Distance_recent[i], Distance_recent[i-1]):
                    starting_point_new[i] = starting_point_recent[i-1]                    
    return starting_point_new     

#2.Calculation for each incoming point x.t - simulated here by simply calculating along the given static list
for j in range (len(stream)):

    x = stream[j]    
    accdist_calc (x,template,D_now,D_recent)
    startingpoint_calc (n, S_recent, S_now, D_now, D_recent) 

    #Report any matching subsequence
    if D_now[n-1] <= epsilon:
        if D_now[n-1] <= d_rep:
            d_rep = D_now[n-1]
            J_s = S_now[n-1]            
            J_e = j+1
            print "REPORT: Distance "+str(d_rep)+" with a starting point of "+str(J_s)+" and ending at "+str(J_e)              

    #Identify optimal subsequence
    for i in range (n):
        if D_now[i] >= d_rep or S_now[i] > J_e:
            check = check+1
    if check == n:
        print "MATCH: Distance "+str(d_rep)+" with a starting point of "+str(J_s)+" and ending at "+str(J_e)
        matches.append(str(d_rep)+","+str(J_s)+","+str(J_e))
        d_rep = float("inf")
        J_s = float("inf")
        J_e = float("inf")
        check = 0 
    else:
        check = 0

    #define the recently calculated distance vector as "old" distance
    for i in range (n):
        D_recent[i] = D_now[i]
        S_recent[i] = S_now[i]