在时间序列数据库中查找给定时间序列的近似序列的方法

摘要

本发明属于数据挖掘技术领域，具体为一种在海量时间序列数据库中查找给定时间序列的近似序列的方法。该方法包括：采用树状索引的结点表示方式；根据索引的算法框架，逐条构建索引；选择最优策略进行结点分裂；最后基于DSTree索引进行查询，海量时间序列数据库中查找给定时间序列的近似序列。本发明提出的索引方法，根据时间序列的数据分布情况调整索引子序列长度和维度，新的索引表示方式也满足提供距离上界的需求，大幅提高查询效率。

说明书

技术领域

本发明属于数据挖掘技术领域，具体涉及在海量时间序列数据库中查找给定时间序列的近似序列的方法。 

背景技术

近似时间序列查询是数据挖掘中的热点问题，对于在数据库中的海量时间序列，如何迅速准确地找出与给定序列最为近似的时间序列，在交通网络、传感器网络、金融分析等场合具有重要意义。在数据库中对时间序列构建索引，能够对时间序列进行有效的降维和查询剪枝，从而准确迅速地执行查询。

构建索引的基本思路包括两方面，一方面是以类似空间数据库多维索引的方式，通过对时间序列的每一维的取值空间进行划分，来减少搜索空间。另一方面是对时间序列数据采取降维操作，从而减少存储空间。从这两方面思路着手，目前已有PAA，APCA，SAX，iSAX等算法对时间序列进行压缩存储。PAA（Piecewise Aggregate Approximation）算法将时间序列分成等长的子序列，对于每一段子序列以子序列的平均值代替整段子序列，从而达到降维的目的。APCA（Adaptive Piecewise Constant Approximation）算法于PAA算法相近，区别在于APCA算法所划分的子序列并非等长的子序列，它根据数据的波动情况自适应性地调整子序列的长度。结合高斯分布的统计学理论，SAX算法在PAA算法的基础上将时间序列每一维的取值空间划分成若干块区域，以指定的符号代替落在这一区域的所有平均值。长时间序列经过SAX转换后变成一条短符号序列，便于近似距离比较。iSAX算法在SAX中引入树这一索引中常用的重要数据结构，并将SAX算法中的符号改为二进制数值，以实现划分区域的分裂和索引的扩展。

在SAX和iSAX算法中，每一段子序列的长度都事先确定，空间区域也严格地按照高斯分布划分。在事实数据中，常常会出现高低起伏时急时缓，固定长度加上平均值的简单划分模式无法很好地反映数据的真实情况，导致近似查询中出现较大的误差甚至错误。

在已有的包括SAX和iSAX的索引算法中，索引都仅能提供索引序列与原序列距离的下界，以保证查询结果集的完备性，但尚未有索引在给出距离下界的同时能给出上界，以保证算法的效率。本发明将提出构建一个自适应的时间序列索引方法，根据时间序列的数据分布情况调整索引子序列长度和维度，新的索引表示方式也满足提供距离上界的需求，大幅提高查询效率。

发明内容

本发明的目的是解决海量时间序列近似查询的问题，提供一种在海量时间序列数据库中查找给定时间序列的近似序列的方法。

本发明提供的在海量时间序列数据库中查找给定时间序列的近似序列的方法，主要着眼于对海量时间序列建立一个有效的自适应的索引，以降低算法的复杂度，提升计算效率。具体内容如下：

 1、采用树状索引的结点表示方式，具体为：

对于时间序列X，将它分成不相交的m段：                                                ，每一段X_i以的形式表示，i=1,2,…m。其中表示本段序列X_i的时间末端，表示本段序列X_i的平均值，表示本段序列的标准差。对于时间序列Y，按照对于时间序列X同样分法，分为m段:（Y₁,Y₂,…,Y_m）, 每一段Y_i以与X_i同样的形式表示，i=1,2,…m。记每一段X_i和Y_i的长度为n_i，根据这种时间序列表示方式可以得出：

同样长度的两段时间序列X，Y之间距离平方上界为：     (1)

同样长度的两段时间序列X，Y之间距离平方下界为：             (2)；

每个索引结点表示一系列时间序列的集合，在近似查询的过程中，需要计算待查时间序列与索引结点，也就是序列集合的距离上、下界，以减少计算量。用UB表示序列值的上界，LB表示序列值的下界。UB可分解为两部分:UB_m和UB_s，其中UB_m表示和均值相关的部分，UB_s表示和标准差相关的部分。对于同样长度的查询时间序列Q，均值记为m_Q，标准差记为s_Q。被查询集合中的均值最大值为m_u，最小值为m_l；标准差最大值为s_u，最小值为s_l。那么可以得到下面两张上、下界计算表：

Case00

Case0

表1. 时间序列与时间序列集合距离上、下界计算表

 2、索引构建与结点分裂 

海量时间序列插入数据库时，利用索引构建算法逐条构建树结构索引以便查询。其关键点在于结点分裂策略和如何选择最优策略进行结点分裂。结点分裂有三种策略：根据平均值纵向分裂、根据标准差纵向分裂以及根据时间跨度横向分裂。我们定义一个统一的参照值B衡量不同分裂策略的优劣，选择最优分裂策略。

3、基于DSTree索引的查询

DSTree索引支持两类查询，一类是传统的近似时间序列查询，返回与指定时间序列最接近的序列；另一类是距离直方图查询，返回数据库中时间序列与指定序列距离大小的分布直方图。在传统的近似查询中，都需要且能够根据子序列长度、区域划分方式等参数预先将指定的被查序列转化为索引再执行查询操作。DSTree索引上的两类查询与传统查询的一点不同是在被查序列是在查询的过程中随着树的遍历深度加深逐步转化，而不是查询初始预先转化完成。

在近似时间序列查询中，首先将待查序列Q插入索引树中，找到对应的结点N，计算N与Q的距离下办，得到目前最近的序列BSF。根据其他各叶子结点所包含信息计算出各结点与Q距离的上、下界，据此，排除那些没有可能包含近似序列的结点。将剩下的结点放入队列pq中逐个验证，并在验证的过程中不断更新BSF，以此持续对结点集合进行剪枝，当队列pq为空时，BSF就是算法得出的最终结果，也就是数据库中与待查序列距离最近的序列。

相比于近似序列查找，距离直方图的计算较为容易。对索引树进行广度遍历，由各结点所包含的上、下界和结点大小信息可以估算出距离落在各个区间的时间序列数量。

根据上面描述，本发明的在海量时间序列数据库中查找给定时间序列的近似序列的方法具体步骤分为两个部分：一、构建树结构索引，二、基于DSTree索引的查询。

第一部分是构建树结构索引，即在海量时间序列插入数据库时，利用索引构建算法逐条构建树结构索引。构建索引的算法步骤如下：

    （1）对于新插入的时间序列X和索引结点N（初始值为根结点），首先计算X的平均值和标准差m_Q、s_Q，更新索引结点N的平均值和标准差上下界m_u、m_l、s_u、s_l；

    （2）如果索引结点N是叶结点，将时间序列X放入索引结点N指向的文件F中，并执行步骤（3）-步骤（5），否则跳过步骤（3）-步骤（5）直接执行步骤（6）；

    （3）如果索引结点N中时间序列数量超过指定的阈值th，选择一个最优结点分裂策略SP；

    （4）把索引结点N设为非叶子结点，新建两叶子结点作为N的子结点；

    （5）将索引结点N结点对应的F文件中的时间序列逐条插入到子结点中；

    （6）判断时间序列X属于索引结点N的哪个子结点，将X插入对应的子结点。 

算法步骤（3)中所涉及的结点分裂策略有3种，分别如下：

    （a）根据平均值纵向分裂。假设选中将要分裂的索引结点N所指向的时间序列平均值的取值范围为，其中，分别表示平均值上、下界。那么将N分裂为两个新结点，它们所指向的时间序列的平均值取值范围分别为，。

（b）根据标准差纵向分裂。假设选中将要分裂的索引结点N所指向的时间序列方差的取值范围为，其中，分别表示标准差上、下界。那么将N分裂为两个新结点，它们所指向的时间序列的标准差取值范围分别为，。

（c）根据时间跨度横向分裂。假设选中将要分裂的索引结点N所指向的时间序列的时间取值范围为，其中表示时间第i段时间序列中最后一个点的时刻。那么将N分裂为两个部分和，它们所指向的时间序列的时间取值范围分别为，。再在和中选择一个进行根据平均值纵向分裂值域计算，得到划分区间,再依据对N进行划分。假设被选中的平均值取值范围为，则分别为，，以此对N进行划分。

对于3种分裂策略，最优策略SP的选择依据是：

(a)定义结点计算指标：，其中分别表示本索引所指向的时间序列的平均值上、界，表示标准差上界。

(b)对于结点N的三种分裂策略，用表示分裂后结点，分别计算：         选择B值最大的策略对N进行分裂。

第二部分是基于DSTree索引的查询，即索引构建完成后，利用3中所介绍的查询算法在海量时间序列数据库中查找给定时间序列的近似序列。具体而言，对于待查的时间序列Q，先以第一部分的插入索引算法计算得出距离Q最近的索引结点N₀，由对照表1得出Q与N₀之间的均值和标准差上下界、、和，取和之和为Q与N₀之间距离平方的下界，开方可得距离下界初始值BSF。接下来从根结点root开始自顶向下广度优先遍历索引树，对于树中的一个结点N，若N与Q的距离下界大于BSF，则忽略N及其所有子孙结点。若N与Q距离下界小于BSF，更新BSF，遍历N的所有子结点。对于遍历过程中小于BSF的叶子结点N_leaf，将其中包含的每一条序列取出与Q直接计算距离，用最小距离更新BSF。索引遍历结束是BSF的值为最小距离，所对应的序列即最近似序列。

附图说明

图1是在人工合成的随机游走数据上构建索引的相关信息，各图的横坐标均为时间序列的长度。其中，（a）图纵坐标表示结点数量，各算法的结点数量都基本保持不变，本发明算法结点数量少于iSAX2.0算法。（b）图纵坐标表示索引大小，索引总大小由单条索引大小和子序列数量共同决定，本发明算法单条索引保存了平均值和标准差，因此单条索引较大。但是得益于结点分裂算法使得子序列数量较少，算法总索引大小与“PAA-16”和“iSAX-16”算法近似。（c）图纵坐标表示平均每结点的序列数,反映了硬盘扫描效率和树的平衡度。（d）图纵坐标表示子序列长度,反映了算法动态划分的稳定性和扩展性。

图2是在真实数据集上构建索引的相关信息。（a）、（b）、（c）、（d）4幅图像反映了在合成数据实验，即图1中体现出的相同算法性质。

图3是合成数据集上索引错误率（左图）和剪枝能力（右图）。错误率,其中表示近似查询最近距离，Dist表示真实最近距离。剪枝能力P是剪枝后的序列数量于总序列数量的比值。图3反映了本发明算法在合成数据集上具有较低的错误率和很强的剪枝能力。

图4是真实数据集上索引错误率和剪枝能力。图4所用的测算公式与图3相同，图4反映了本发明算法在真实数据集上也具有较低的错误率（左图）和很强的剪枝能力（右图）。 

具体实施方式

接下来以序列集{(3,3,3,3), (2,2,2,2), (3,3,4,4)}为例说明索引构建过程，假设结点阈值为2。索引构建过程如下：

1. 建立根结点root；

2. 插入第一条数据(3,3,3,3)，root为空，放在root中，root的平均值值域更新为[3,3]，标准差值域更新为[0,0]；

3. 插入第二条数据(2,2,2,2)，root有两条数据，未超过阈值，平均值值域更新为[2,3]，标准差值域更新为[0,0]；

4. 插入第三条数据(3,3,4,4)，root平均值值域更新为[2,3.5]，标准差值域更新为[0,0.5]，结点中序列数超过阈值，考虑结点分裂，=2.5；

5. 考虑按平均值分裂的情况：两结点为{(2,2,2,2)}，{(3,3,3,3),(3,3,4,4)}，=0，=0.5，B=2.25；

6. 考虑按标准差分裂的情况：两结点为{(2,2,2,2)，(3,3,3,3)}，{(3,3,4,4)}，=1，=0.25，B=1.775；

7. 考虑横向分裂的情况：先分为两部分{(2,2)，(3,3) }，{(2,2)，(3,3)，(4,4)}，以前面部分划分区域，得到两个平均值值域[2,3]，(3,4]。以此为根据对N进行分裂得到{(2,2,2,2)}，{(3,3,3,3),(3,3,4,4)}，=0，=0.5，B=2.25；

8. 选择B值最大的分裂方式即按平均值分裂策略对root进行分裂为两个结点N₁{(2,2,2,2)}，N₂{(3,3,3,3),(3,3,4,4)}。

在上述索引基础上以查询序列Q(3,3,2,4)的近似序列为例说明近似序列的查询方法：

1.按索引构建的方法自顶向下在树型索引中找到(3,3,2,4)对应的结点，为结点N₂ {(3,3,3,3),(3,3,4,4)}；

2. 根据公式(1)，(2)和表1计算序列Q(3,3,2,4)与N₂的距离下界为minLB=0.172；

3.  将root结点加入队列pq；

4.  将root结点从队列中取出，计算与序列Q的距离下界为LB_root=0.172，不大于minLB，且root结点非叶子结点，得到它的子结点N₁，N₂；

5. 计算N₁，N₂与Q的距离下界，分别为LB_N1=1.5，LB_N2=0.172，均不小于minLB，故不放入队列pq中；

6. 检查队列pq为空，索引遍历结束，当前距离下界对应结点为N₂，取其中的所有序列{(3,3,3,3)，(4,4,4,4)}与Q计算实际距离，得到最近序列为(3,3,3,3)，查询完成。