CN103136327A - 一种基于局部特征聚类的时间序列符号化方法 - Google Patents

Abstract

本发明提供一种基于局部特征聚类的时间序列符号化方法，包括：读取原始时间序列的步骤；调用滑动窗口程序利用滑动窗口将所述原始时间序列分割为多个子时间序列的步骤；将所述原始时间序列的每个子时间序列采用多个斜率表示的步骤；采用K均值聚类算法实现所述子时间序列聚类的步骤；以及对于每个聚类结果赋予相应的符号标识的步骤。本发明能够很好的降维以及保留了时间序列的形态特性，有利于对时间序列的进一步研究，进而解决了现有技术中直接在原始时间序列上进行相似性查询、分类、聚类、模式挖掘等工作，会造成存储和计算效率低下，而且会影响算法的准确性和可靠性等问题。

Description

一种基于局部特征聚类的时间序列符号化方法

技术领域

本发明涉及数据挖掘领域，特别是涉及一种基于局部特征聚类的时间序列符号化方法。 

背景技术

在数据挖掘领域，时间序列数据是一类重要的数据对象，在科学研究、商业应用、交通控制、工业生产中普遍存在。通过对时间序列进行分析研究，可以揭示事物运动、变化和发展的内在规律，对人们正确的认识事物并据此做出科学的决策具有重要的现实意义。由于时间序列数据具有高维度，大量噪声干扰以及非稳态等特性，因此直接在原始时间序列上进行相似性查询、分类、聚类、模式挖掘等工作，不但会造成存储和计算效率低下而且会影响算法的准确性和可靠性从而难以获得满意的结果。因此，在进行时间序列数据挖掘之前，需要对时间序列数据进行处理。许多研究者提出了时间序列的模式表示，其中时间序列符号化表示是一种重要的方法。 

时间序列的符号化的基本思想通过一些离散化方法将时间序列的连续实数值或者一段时间内的时间序列波形映射到有限的符号表上，将时间序列转换为有限符号的有序集合，即把时间序列用符号集S＝{s₁,s₂,...,s_|S|}表示出来，其中|S|是符号集的大小（符号个数）。 

发明内容

鉴于以上所述现有技术的缺点，本发明的目的在于提供一种基于局部特征聚类的时间序列符号化方法，用于解决现有技术中直接在原始时间序列上进行相似性查询、分类、聚类、模式挖掘等工作，会造成存储和计算效率低下，而且会影响算法的准确性和可靠性的问题。 

为实现上述目的及其他相关目的，本发明提供一种基于局部特征聚类的时间序列符号化方法，所述时间序列符号化方法包括：读取原始时间序列的步骤；调用滑动窗口程序利用滑动窗口将所述原始时间序列分割为多个子时间序列的步骤；将所述原始时间序列的每个子时间序列采用多个斜率表示的步骤；采用K均值聚类算法实现所述子时间序列聚类的步骤；以及对于每个聚类结果赋予相应的符号标识的步骤。 

优选地，所述调用滑动窗口程序利用滑动窗口将所述原始时间序列分割为多个子时间序列的分割模式M_seg定义如下： 

M_seg＝{(b₀,e₀),(b₁,e₁),...(b_k,e_k)}； 

其中，b_i为子序列起始时间，e_i为子序列结束时间。 

优选地，于利用滑动窗口将所述原始时间序列分割为多个子时间序列的步骤中，基于上述分割模式进行分割具体为： 

设定大小为W的滑动窗口，并设定原始时间序列为X； 

将所述原始时间序列X＝<x₀＝(x₀,t₀),x₁＝(x₁,t₁),...,x_n＝(x_n,t_n)>分段为多个子时间序列；将分段的所述多个子时间序列表示为个子时间序列S₀，S₁……，

优选地，所述的将所述原始时间序列的每个子时间序列采用多个斜率表示的步骤中，将多个子时间序列S₀，S₁……，

分别用SlopeNum个斜率表示，则各该子时间序列为： 

S₀＝(sp_0,0,sp_0,1,...,sp_0,SlopeNum)；……

优选地，所述的将原始时间序列的每个子时间序列采用多个斜率表示的步骤中，所述子时间序列的模式表示为t′，表示如下： 

t′＝{(sp_0,0,sp_0,1，...,sp_0,SlopeNum),..., 

(sp_k,0,sp_k,1,...,sp_k,SlopeNum)}； 

其中，(sp_i,0,sp_i,1,...,sp_i,SlopeNum)为第i个子时间序列的模式表示，sp_i,j第i个子时间序列的第j个斜率。 

优选地，采用K均值聚类算法实现所述子时间序列聚类的步骤以及对于每个聚类结果赋予相应的符号标识的步骤具体为对所述原始时间序列的分段子时间序列S₀，S₁，...，

采用K均值算法进行聚类，符号集大小为|S|，分段序列被分为|S|类，将每一类赋予相应的符号表示，以完成时间序列的符号化表示。 

如上所述，本发明的基于局部特征聚类的时间序列符号化方法，具有以下有益效果在于能够很好的降维以及保留了时间序列的形态特性，有利于对时间序列的进一步研究，进而解决了现有技术中直接在原始时间序列上进行相似性查询、分类、聚类、模式挖掘等工作，会造成存储和计算效率低下，而且会影响算法的准确性和可靠性等问题。 

附图说明

图1显示为本发明的基于局部特征聚类的时间序列符号化方法流程图。 

图2显示为时间序列的符号表示示意图。 

图3a及图3b显示为不同符号集大小的结果示意图。 

图4a至图4c显示为不同迭代次数的结果示意图。 

图5a及图5b显示为不同滑动窗口的结果示意图。 

图6a及图6b显示为不同斜率个数的结果示意图。 

图7a显示为原始时间序列示意图。 

图7b显示为利用本发明的LFSA方法进行时间序列符号化的示意图。 

图7c显示为时间序列标准化之后的示意图。 

图7d显示为经典的时间序列符号化方法SAX方法进行时间序列符号化的示意图。 

具体实施方式

以下通过特定的具体实例说明本发明的实施方式，本领域技术人员可由本说明书所揭露的内容轻易地了解本发明的其他优点与功效。本发明还可以通过另外不同的具体实施方式加以实施或应用，本说明书中的各项细节也可以基于不同观点与应用，在没有背离本发明的精神下进行各种修饰或改变。 

针对时间序列的特性，本发明结合滑动窗口以及斜率的思想，提出了一种新的时间序列符号化的算法，即基于局部特征的符号化算法(Symbolic Algorithm Based On Local FeaturesLFSA)。该算法首先利用滑动窗口将时间序列进行分割表示，然后利用斜率表示每个分割段，再利用聚类算法实现时间序列的聚类，最后给每个分类一个符号标识。实验表明，该方法能够很好的降维以及保留了时间序列的形态特性，有利于对时间序列的进一步研究，具体详述如下： 

本发明提供一种基于局部特征聚类的时间序列符号化方法，所述时间序列符号化方法包括以下步骤： 

首先执行步骤S1，读取原始时间序列；于具体的实施例中，计算机读取预存在本地或远端服务器中存储的原始时间序列。 

然后执行步骤S2，计算机调用其内部滑动窗口程序利用滑动窗口将所述原始时间序列分割为多个子时间序列；于具体的实施例中，所述调用滑动窗口程序利用滑动窗口将所述原始时间序列分割为多个子时间序列的分割模式定义如下： 

M_seg＝{(b₀,e₀),(b₁,e₁)，...(b_k,e_k)}； 

其中，b_i为子序列起始时间，e_i为子序列结束时间。 

具体地，于上述利用滑动窗口将所述原始时间序列分割为多个子时间序列的步骤中，基于上述分割模式进行分割具体为： 

设定大小为W的滑动窗口，并设定原始时间序列为X； 

将所述原始时间序列X＝<x₀＝(x₀,t₀),x₁＝(x₁,t₁),...,x_n＝(x_n,t_n)>分段为多个子时间序列；将分段的所述多个子时间序列表示为

个子时间序列S₀，S₁……，

接着执行步骤S3，将所述原始时间序列的每个子时间序列采用多个斜率表示；于具体的实施例中，优选地，所述的将所述原始时间序列的每个子时间序列采用多个斜率表示的步骤中，将多个子时间序列S₀，S₁……，

分别用SlopeNum个斜率表示，则各该子时间序列为： 

S₀＝(sp_0,0,sp_0,1,...,sp_0,SlopeNum)；……

具体地，所述的将原始时间序列的每个子时间序列采用多个斜率表示的步骤中，所述子时间序列的模式表示为t′，表示如下： 

t′＝{(SP_0,0,SP_0,1,...,SP_0,SlopeNum),..., 

(sp_k,0,sp_k,1,...,sp_k,SlopeNum)}； 

其中，(sp_i,0,sp_i,1,...,sp_i,SlopeNum)为第i个子时间序列的模式表示，sp_i,j第i个子时间序列的第j个斜率。 

然后执行步骤S4，采用K均值聚类算法实现所述子时间序列聚类；于具体的实施例中，采用K均值聚类算法实现所述子时间序列聚类的步骤以及对于每个聚类结果赋予相应的符号标识的步骤具体为对所述原始时间序列的分段子时间序列S₀，S₁，...，

采用K均值算法进行聚类。 

最后执行步骤S5，对于每个聚类结果赋予相应的符号标识。于具体的实施例中，对所述 原始时间序列的分段子时间序列S₀，S₁，...，采用K均值算法进行聚类，符号集大小为|S|，分段序列被分为|S|类，将每一类赋予相应的符号表示，以完成时间序列的符号化表示。 

为进一步阐述本发明的原理及功效，请参阅图2至图7d，首先，我们任意抽取一条时间序列，利用我们的符号化方法，将该时间序列表示为符号序列，取滑动窗口大小W为4，迭代次数I为20次，每个分段采用2个斜率表示，字符集大小为4，得到结果如图2所示。图2显示为时间序列的符号表示示意图，在图2中，原始时间序列被表示为了“abcadcccacbcddd”这样一个字符串序列。 

利用符号化算法(LFSA)方法，原始时间序列被表示为了“abcadcccacbcddd”这样一个字符串序列，因此该方法能够实现时间序列的降维。通过观察图2，我们可以大致看出每个符号代表了一种局部特征，因此我们提出的SFSA方法不仅能够有效的降低原始时间序列的维度，而且能够保留原始时间序列的形态模式信息。 

通过前面的阐述，LFSA方法的参数主要有滑动窗口的大小W、迭代次数I、斜率个数SlopeNum以及符号集大小|S|。我们从实验数据集中任取时间序列，分别在不同的参数情况下，结果如图3a至6b所示。 

请参阅图3a及图3b，显示为不同符号集大小的结果示意图，图3a中，W＝4，I＝40，SlopeNum＝2，|S|＝4；图3b中，W＝4，I＝40，SlopeNum＝2，|S|＝6。 

如图所示，通过图3a与图3b比较我们可以发现，在其他参数相同的情况下，符号集的大小影响了符号序列所表示的原始时间序列的细致程序，符号集越大，符号序列所能表征的原始时间序列局部特征越细致，同一个符号表示的分段更准确；反之亦然。但是在这里存在一个问题，符号集过大影响了降维的效果，所以符号集的大小应该根据实际的情况来设定。 

请参阅图4a至图4c，显示为不同迭代次数的结果示意图，图4a中，W＝4，I＝1，SlopeNum＝2，|S|＝4；图4b中，W＝4，I＝5，SlopeNum＝2，|S|＝4；图4c中，W＝4，I＝40，SlopeNum＝2，|S|＝4。 

如图所示，由图4a、图4b、图4c三图可知，随着迭代次数的增加，符号序列表示的准确率逐渐提高，每一个符号表示分段近似度逐渐变高，但是，当迭代次数的增加到一定程度后，符号序列将不会改变，这是由于在对分段进行聚类的时候采用了K均值聚类算法，而聚类算法存在结果向局部最优靠近的特点，所以会出现这样的现象。另外，迭代次数的增多同 时影响着算法的运行效率，我们可以从上面知道迭代次数达到一定的值后，结果将不再变化，所以迭代次数并不是越大越好。 

请参阅图5a及图5b，显示为不同滑动窗口的结果示意图，图5a中，W＝4，I＝40，SlopeNum＝2，|S|＝4；图5b中，W＝6，I＝40，SlopeNum＝2，|S|＝4。 

如图所示，通过对比图5a与图5b我们可以发现，在其他参数不变的情况下，滑动窗口的大小影响了算法的准确性及压缩率。滑动窗口增大，压缩率变高，但是相应的准确率下降。反之，滑动窗口减小，压缩率降低，准确率变高。 

请参阅图6a及图6b，显示为不同斜率个数的结果示意图，图6a中，W＝6，I＝40，SlopeNum＝2，|S|＝4；图6b中，W＝6，I＝40，SlopeNum＝3，|S|＝4。 

如图所示，由图6a与图6b分析可知，每个分段用较多的斜率表示，该算法的准确率提高了，即具有相同或相似的原始分段能够用更准确的符号表示。但是，该算法过多的斜率表示分段将导致算法复杂性提高，运行效率降低，因此在准确率和效率之间，应该根据实际设置该参数。 

综合分析上述内容，由于SFSA算法采用了K均值的聚类算法对原始时间序列的分段进行聚类，因此迭代次数I以及符号集大小|S|是影响算法性能的主要指标。滑动窗口大小W以及斜率个数SlopeNum是影响算法准确性及压缩率的主要指标。 

为了说明本发明的优点，我们选取经典的时间序列符号化方法(Symbolic AggregateApproximation,SAX)方法与本文提出的方法进行对比实验，首先我们比较任选的一条时间序列。SFSA方法设置W＝4，I＝40，SlopeNum＝2，|S|＝6和SAX方法设置W＝4，|S＝6|，结果如图7a至图7d所示。图7a显示为原始时间序列示意图；图7b显示为利用本发明的LFSA方法进行时间序列符号化的示意图；图7c显示为时间序列标准化之后的示意图；图7d显示为经典的时间序列符号化方法SAX方法进行时间序列符号化的示意图。 

通过分析图7c与图7d可知，SAX方法采用PAA的近似表示方法，采用平均值来表示每个分段，忽略了原始时间序列的原有的局部特征信息，只能近似的描述时间序列大致特征以；本文提出的方法能够有效降维，同时考虑到了原始时间序列的局部特征，利用斜率来表示分段，能够尽可能的保留原始时间序列的信息，该方法使得每个符号代表了原始时间序列的一个形态模式，使得结果更加准确。因此，本文提出的SFSA方法能够包含更多的原始时间序列的信息，该方法比SAX方法提供了更为全面的描述信息，为后续的进一步的时间序列 数据挖掘提供了可靠的保证。 

综上所述，本发明的基于局部特征聚类的时间序列符号化方法，具有以下有益效果在于能够很好的降维以及保留了时间序列的形态特性，有利于对时间序列的进一步研究，进而解决了现有技术中直接在原始时间序列上进行相似性查询、分类、聚类、模式挖掘等工作，会造成存储和计算效率低下，而且会影响算法的准确性和可靠性等问题。所以，本发明有效克服了现有技术中的种种缺点而具高度产业利用价值。 

上述实施例仅例示性说明本发明的原理及其功效，而非用于限制本发明。任何熟悉此技术的人士皆可在不违背本发明的精神及范畴下，对上述实施例进行修饰或改变。因此，举凡所属技术领域中具有通常知识者在未脱离本发明所揭示的精神与技术思想下所完成的一切等效修饰或改变，仍应由本发明的权利要求所涵盖。 

Claims (6)

1.一种基于局部特征聚类的时间序列符号化方法，其特征在于，所述时间序列符号化方法包括：

读取原始时间序列的步骤；

调用滑动窗口程序利用滑动窗口将所述原始时间序列分割为多个子时间序列的步骤；

将所述原始时间序列的每个子时间序列采用多个斜率表示的步骤；

采用K均值聚类算法实现所述子时间序列聚类的步骤；以及

对于每个聚类结果赋予相应的符号标识的步骤。

2.根据权利要求1所述的基于局部特征聚类的时间序列符号化方法，其特征在于：所述调用滑动窗口程序利用滑动窗口将所述原始时间序列分割为多个子时间序列的分割模式M_seg定义如下：

M_seg＝{(b₀,e₀),(b₁,e₁),...(b_k,e_k)}；

其中，b_i为子序列起始时间，e_i为子序列结束时间。

3.根据权利要求2所述的基于局部特征聚类的时间序列符号化方法，其特征在于：于利用滑动窗口将所述原始时间序列分割为多个子时间序列的步骤中，基于上述分割模式进行分割具体为：

设定大小为W的滑动窗口，并设定原始时间序列为X；

将所述原始时间序列X＝<x₀＝(x₀,t₀),x₁＝(x₁,t₁),...,x_n＝(x_n,t_n)>分段为多个子时间序列；

将分段的所述多个子时间序列表示为个子时间序列S₀，S₁……，

4.根据权利要求3所述的基于局部特征聚类的时间序列符号化方法，其特征在于：所述的将所述原始时间序列的每个子时间序列采用多个斜率表示的步骤中，将多个子时间序列S₀，S₁……，分别用SlopeNum个斜率表示，则各该子时间序列为：S₀＝(sp_0,0,sp_0,1,...,sp_0,SlopeNum)；……

5.根据权利要求4所述的基于局部特征聚类的时间序列符号化方法，其特征在于：所述的将原始时间序列的每个子时间序列采用多个斜率表示的步骤中，所述子时间序列的模式表示为t′，表示如下：

t′＝{(sp_0,0,sp_0,1，...,sp_0,SlopeNum),...,

(sp_k,0,sp_k,1，...,sp_k,SlopeNum)}；

其中，(sp_i,0,sp_i,1,...,sp_i,SlopeNum)为第i个子时间序列的模式表示，sp_i,j第i个子时间序列的第j个斜率。

6.根据权利要求5所述的基于局部特征聚类的时间序列符号化方法，其特征在于：采用K均值聚类算法实现所述子时间序列聚类的步骤以及对于每个聚类结果赋予相应的符号标识的步骤具体为对所述原始时间序列的分段子时间序列S₀，S₁，...，

采用K均值算法进行聚类，符号集大小为|S|，分段序列被分为|S|类，将每一类赋予相应的符号表示，以完成时间序列的符号化表示。

Images