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

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
3. 0

并扩展数据框为：

时间戳：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 ... 请注意，这种模式没有相同的长度。

问题是可以使用哪些算法来解决这个无监督学习问题，另外，可能还有什么库/框架可以用于实现这样一个任务。

先感谢您！

- user6188360

---

你已经看过哪些算法了？ - Joey Ciechanowicz

我读到了一些关于自组织映射(Self organizing maps)、隐马尔可夫模型(Hidden Markov Models)和长短时记忆(LSTMs)的内容，但是我仍然不确定它们是否适用于时间序列模式识别。 - user6188360

你应该将这个加入到你的问题中，这样其他用户就可以更了解你已经尝试或查看了什么信息。 - Joey Ciechanowicz

有些人将时间序列中的模式称为Shapelet。也许这对你的研究有所帮助。http://alumni.cs.ucr.edu/~lexiangy/Shapelet/kdd2009shapelet.pdf - hellomichibye

Answer 1

我的回答涉及模式匹配的问题。在成功匹配后，以下算法将输出匹配序列的起始位置和位置。您可以使用此信息进行标注，如您在问题中描述的那样。

我建议使用 SPRING 算法，该算法在以下论文中介绍：

流监控下的时间扭曲距离（Sakurai、Faloutsos、Yamamuro） http://www.cs.cmu.edu/~christos/PUBLICATIONS/ICDE07-spring.pdf 该算法的核心是 DTW 距离（动态时间扭曲），并且生成的距离是 DTW 距离。与 DTW 不同之处在于，每个“流”（您正在寻找匹配的序列）的每个位置都是可能的匹配起点 - 与 DTW 相反，它为每个起始点计算总距离矩阵。您需要提供一个模板、一个阈值和一个流（该概念是为从数据流匹配而开发的，但您可以通过简单地循环遍历来将算法应用于您的数据框架）

注意：

• 选择阈值并非易事，可能会带来重大挑战 - 但这将是另一个问题。(阈值= 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] 

- Nikolas Rieble