识别数据元素之间的关联和演变模式的系统和方法

摘要

本发明提供了一种用于识别多元时序列数据的数据元素之间的关联和演变模式的系统，所述系统包括：预处理单元，被配置为对采集到的数据进行预处理，得到处理后的数据序列；关联发现单元，被配置为使用Granger因果图模型从预处理后的数据中发现多元时序列数据的数据元素之间的关联，得到因果图序列；以及演变模式发现单元，被配置为对得到的因果图序列进行聚合，从而发现因果关系的演变模式。还提供了一种用于识别多元时序列数据的数据元素之间的关联和演变模式的方法。采用本发明，能够有效地识别多元时序列数据的数据元素之间的因果关系以及演变模式，而且因果关系的识别会更加准确。

说明书

技术领域

本申请涉及数据分析领域，具体涉及一种用于识别多元时序列数据的数据元素之间的关联和演变模式的系统和方法。

背景技术

识别多元时序列数据的数据元素之间的关联和演变模式是一个复杂的过程，因为各个时序列数据数据元素会随时间和空间动态变化。现有的识别方法通常根据经验将时间序列划分成固定时长的片断，或根据先验知识手动设定参数。

例如，非专利文献1(“LearningSpatial-TemporalVaryingGraphswithApplicationstoClimateDataAnalysis”，XiChen，AAAI，2010)提出了一种基于马可夫随机条件场(MarkovRandomField)的动态关系图模式识别方法。该方法主要包括以下步骤：

首先进行数据预处理，该数据包括在不同时间和地点收集的可吸入颗粒物、一氧化碳(CO)、温度和湿度。这些数据都使用相同的时间尺度的收集，用同一个特征空间xST表示。因为假定因果关系在同一个季节是相似的，所以时间序列被划分成4个等长的时间段，分别对应一年的四个季节。相应地，特征空间xST也被划分为4个子输入空间。然后，采用基于马可夫随机条件场的方法来学习每一个子输入空间中特征的动态关系。最后，将针对每个季节学习出的关系图作为最终结果输出。

图10示出了该方法的一个应用示例。如图10所示，数据序列中的每一个样本包括PM2.5、一氧化碳(CO)、温度和湿度数据。经过基于马可夫随机条件场(MRF)的动态关系图模式识别后，获得4种关系图(见图10下部)。

然而，上述方法存在以下问题：仅能够挖掘时间序列中的静态关联关系，而且需要手动划分时间序列以求得不同时间段的关联。此外，不能获得时间序列中时变的关联关系。

发明内容

图模型能表示随机变量之间的条件依赖性，可以用于挖掘随机变量之间的关联关系。特别是，Granger因果图模型是一种非常有效的分析方法。然而，它主要适用于分析平稳的时间序列。如何在时间和空间域均具有非平稳特征的过程中发现主要影响因素间的因果关联关系，是非常具有挑战性的。

本发明提出一种基于迭代学习Granger因果关联图的系统和方法，能自动识别多元时序列数据的数据元素间关联关系及演变模式。另外，在时间序列的划分中，本发明优化了不同数据元素的时长及时间滞后约束，从而提升了因果关系发现的准确度。

根据本发明的第一方面，提供了一种用于识别多元时序列数据的数据元素之间的关联和演变模式的系统，所述系统包括：预处理单元，被配置为对采集到的数据进行预处理，得到处理后的数据序列；关联发现单元，被配置为使用Granger因果图模型从预处理后的数据中发现多元时序列数据的数据元素之间的关联，得到因果图序列；以及演变模式发现单元，被配置为对得到的因果图序列进行聚合，从而发现因果关系的演变模式。

在一个实施例中，预处理单元被配置为：将数据归一化为具有相同时间尺度的数据序列；对归一化的数据序列进行平稳化处理；以及基于时长和时间滞后约束，将平稳化处理后的数据序列转化为样本序列。

在一个实施例中，预处理单元被配置为：对时长和时间滞后约束进行优化，以提升因果关系发现的准确度。

在一个实施例中，关联发现单元被配置为采用因果图迭代学习过程来识别多元时序列数据的数据元素之间的关联以得到因果图序列。因果图迭代学习过程包括以下操作：(1)将数据序列划分为预定数目的段，得到每一段序列的因果图；(2)计算整个序列中的每个样本与得到的因果图的拟合误差，将每个样本重新划归到与其拟合误差最小的因果图所对应的样本段中；(3)针对新的样本，更新因果图，并合并相似的因果图和对应的样本段；(4)比较因果图是否发生变化；以及(5)如果因果图没有发生变化，则结束所述因果图迭代学习过程；否则，返回操作(2)继续执行。

在一个实施例中，关联发现单元被配置为：基于因果图中各个时序列数据元素的权重计算欧氏距离，由此来确定相似的因果图。

根据本发明的第二方面，提供了一种用于识别多元时序列数据的数据元素之间的关联和演变模式的方法，所述方法包括：对采集到的数据进行预处理，得到处理后的数据序列；使用Granger因果图模型从预处理后的数据中发现多元时序列数据的数据元素之间的关联，得到因果图序列；以及对得到的因果图序列进行聚合，从而发现因果关系的演变模式。

在一个实施例中，预处理包括：将数据归一化为具有相同时间尺度的数据序列；对归一化的数据序列进行平稳化处理；以及基于时长和时间滞后约束，将平稳化处理后的数据序列转化为样本序列。

在一个实施例中，对时长和时间滞后约束进行优化，以提升因果关系发现的准确度。

在一个实施例中，采用因果图迭代学习过程来识别多元时序列数据的数据元素之间的关联以得到因果图序列。因果图迭代学习过程包括以下操作：(1)将数据序列划分为预定数目的段，得到每一段序列的因果图；(2)计算整个序列中的每个样本与得到的因果图的拟合误差，将每个样本重新划归到与其拟合误差最小的因果图所对应的样本段中；(3)针对新的样本，更新因果图，并合并相似的因果图和对应的样本段；(4)比较因果图是否发生变化；以及(5)如果因果图没有发生变化，则结束所述因果图迭代学习过程；否则，返回操作(2)继续执行。

在一个实施例中，基于因果图中各个时序列数据元素的权重计算欧氏距离，由此来确定相似的因果图。

采用本发明，能够有效地识别多元时序列数据的数据元素之间的因果关系以及演变模式，而且因果关系的识别会更加准确。

附图说明

通过下文结合附图的详细描述，本发明的上述和其它特征将会变得更加明显，其中：

图1是示出了根据本发明一个实施例的用于识别多元时序列数据的数据元素之间的关联和演变模式的系统的框图。

图2是示出了根据本发明一个实施例的用于将数据序列划分为预定数目的段的示意图。

图3是示出了根据本发明一个实施例的用于重新划分每个样本的示意图。

图4是示出了根据本发明一个实施例的用于合并相似的因果图和对应的样本段的示意图。

图5是示出了根据本发明一个实施例的用于比较因果图是否发生变化的示意图。

图6是示出了根据本发明一个实施例的因果关系演变模式的示意图。

图7是示出了根据本发明一个实施例的用于识别多元时序列数据的数据元素之间的关联和演变模式的方法的流程图。

图8(a)-8(b)是示出了根据本发明另一个实施例的用于对时长和时间滞后约束进行优化的示意图。

图9是示出了通过采用图8(a)-8(b)的优化所得到的数据序列的示意图。

图10是示出了根据现有的基于马可夫随机条件场的动态关系图模式识别方法而得到的因果图的示意图。

具体实施方式

下面，通过结合附图对本发明的具体实施例的描述，本发明的原理和实现将会变得明显。应当注意的是，本发明不应局限于下文所述的具体实施例。另外，为了简便起见，省略了与本发明无关的公知技术的详细描述。

图1是示出了根据本发明一个实施例的用于识别多元时序列数据的数据元素之间的关联和演变模式的系统的框图。如图1所示，系统10包括预处理单元110、关联发现单元120和演变模式发现单元130。下面，结合图2-6详细描述图1所示的系统10中的各个单元的操作。

实施例1

预处理单元110对采集到的数据进行预处理，得到处理后的数据序列。在本实施例中，采集的数据例如可以包括气象数据和空气质量数据，并且优选地还包括交通数据、人口密度数据和污染源数据中的至少一项。

在本实施例中，预处理单元110所执行的预处理可以包括以下方面：

(1)将采集的数据归一化为具有相同时间尺度的数据序列。

(2)对归一化的数据序列进行平稳化处理。例如，如果时间序列是非平稳的，可以将其进行差分处理使之平稳化。

(3)基于时长和时间滞后约束，将平稳化处理后的数据序列转化为样本序列。例如，各数据元素的转化参数可以是时长及时间滞后约束。可以根据经验或先验知识来设置转化参数。

关联发现单元120使用Granger因果图模型从预处理后的数据中发现多元时序列数据的数据元素之间的关联，得到因果图序列。优选地，关联发现单元120采用因果图迭代学习过程来识别多元时序列数据的数据元素之间的关联以得到因果图序列。具体说来：

关联发现单元120首先将数据序列划分为预定数目的段，得到每一段序列的因果图。例如，关联发现单元120随机进行采样，将时间序列划分为K段，其中，K是基于经验知识而预先设定的正整数。接着，关联发现单元120学习每一段时间序列的Granger因果关系，从而得到K个因果图。图2是示出了根据本发明一个实施例的用于将数据序列划分为预定数目的段的示意图。在图2所示的示例中，关联发现单元120将数据序列分为5个(K＝5)数据段，并相应地得到了5个因果图。

然后，关联发现单元120计算整个序列中的每个样本与得到的因果图的拟合误差，将每个样本重新划归到与其拟合误差最小的因果图所对应的样本段中。图3是示出了根据本发明一个实施例的用于重新划分每个样本的示意图。关联发现单元120计算整个时间序列中每个样本与N个因果图的拟合误差。每个样本将被重新划归到与其拟合误差最小(即最小|Y-Wixi＝1k)的因果图所对应的样本段中。这样，重新安排整个样本序列成为一个更新的N段。N最初等于K(即，此时N等于5)，然后随着操作的进行可能变得更小(见下文描述)。要注意的是，随着样本划分的改变，Granger因果图也可能发生变化并需要重新计算。

针对新的样本，关联发现单元120更新因果图，并合并相似的因果图和对应的样本段。优选地，关联发现单元120基于因果图中各个时序列数据元素的权重计算欧氏距离，由此来确定相似的因果图，如下式所示：

相似性度量

$>D_{i,j}=\frac{\sqrt{{({{\beta }^i}_1-{{\beta }^j}_1)}^2+{({{\beta }^i}_2-{{\beta }^j}_2)}^2+{({{\beta }^i}_3-{{\beta }^j}_3)}^2}}{3}$>若D_i，j＜μ，图i和j相似

其中μ可以根据需要取预定值。

图4是示出了根据本发明一个实施例的用于合并相似的因果图和对应的样本段的示意图。在图4所示的示例中，由于因果图3和因果图4是相似的，因此关联发现单元120将其合并为新的因果图6。此时，N变为4。

然后，关联发现单元120比较因果图是否发生变化。如果因果图没有发生变化，则关联发现单元120认为因果图迭代收敛，并结束此因果图迭代学习过程。否则，关联发现单元120重新计算每个样本的拟合误差并将每个样本重新划归到与其拟合误差最小的因果图所对应的样本段中，并且运行下一轮计算。图5是示出了根据本发明一个实施例的用于比较因果图是否发生变化的示意图。如图5所示，当因果图1、2、5、6不再发生变化时，关联发现单元120认为因果图迭代收敛，并结束此因果图迭代学习过程。

演变模式发现单元130对得到的因果图序列进行聚合，从而发现因果关系的演变模式。图6是示出了根据本发明一个实施例的因果关系演变模式的示意图。如图6所示，演变模式发现单元130发现序列模式“1221”经常出现。

图7是示出了根据本发明一个实施例的用于识别多元时序列数据的数据元素之间的关联和演变模式的方法的流程图。如图7所示，方法70在步骤S710处开始。

在步骤S720，对采集到的数据进行预处理，得到处理后的数据序列。例如，采集的数据可以包括气象数据和空气质量数据，并且优选地还包括交通数据、人口密度数据和污染源数据中的至少一项。

优选地，预处理可以包括：将数据归一化为具有相同时间尺度的数据序列；对归一化的数据序列进行平稳化处理；以及基于时长和时间滞后约束，将平稳化处理后的数据序列转化为样本序列。更优选地，可以对时长和时间滞后约束进行优化，以提升因果关系发现的准确度。

在步骤S730，使用Granger因果图模型从预处理后的数据中发现多元时序列数据的数据元素之间的关联，得到因果图序列。例如，可以采用因果图迭代学习过程来识别多元时序列数据的数据元素之间的关联以得到因果图序列，该因果图迭代学习过程包括以下操作：

(1)将数据序列划分为预定数目的段，得到每一段序列的因果图。

(2)计算整个序列中的每个样本与得到的因果图的拟合误差，将每个样本重新划归到与其拟合误差最小的因果图所对应的样本段中。

(3)针对新的样本，更新因果图，并合并相似的因果图和对应的样本段。优选地，可以基于因果图中各个时序列数据元素的权重计算欧氏距离，由此来确定相似的因果图。

(4)比较因果图是否发生变化。

(5)如果因果图没有发生变化，则结束所述因果图迭代学习过程；否则，返回操作(2)继续执行。

在步骤S740，对得到的因果图序列进行聚合，从而发现因果关系的演变模式。

最后，方法70在步骤S750处结束。

采用本实施例，能够有效地识别多元时序列数据的数据元素之间的因果关系以及演变模式。

实施例2

本实施例2与实施例1的区别在于：对时长和时间滞后约束进行优化，以提升因果关系发现的准确度。该操作可以由图1中所示的预处理单元110来实现。下面，结合图1和图8-9来详细描述实施例2的具体细节。

首先，根据经验知识设定L＞T，即在范围[1，L]上选取一个最优的时间片段[t1，t2]。例如，可以设L＝10。

然后，用如下公式得到β：

$>\beta =\underset{\beta }{\arg \min }{\Sigma }_{t=1}^{t=N}{(y_t-{\Sigma }_{i=t-L}^{i=t-1}{\beta }_{t-i}{x}_i)}^2+{\Sigma }_{j=1}^{j=L}{\lambda }_1{\left|\right|{\beta }_j\left|\right|}_1+{\Sigma }_{j=2}^{j=L}{\lambda }_2{\left|\right|{\beta }_j-{\beta }_{j-1}\left|\right|}_1---\left(1\right)$>

该公式中包括两个函数惩罚项，前一个是稀疏惩罚项，后一个是保证连续性的惩罚项。该公式中各参数的含义如下：

-N是样本的个数，可以看作是Y序列的长度。

-L是预设值，即，在[1，L]时间范围中，选择一个最优的时间片段[t1，t2]。

-{Yt，X[t-t1，t-t2]}是一个样本。

-λ₁，λ₂是可调参数，一般取值为10^k(k＝-1，-2，-3，-4，-5，-6)。

-||β||₁表示的是β的L1范数。

-p范数：||x||p＝(|x1|^p+|x2|^p+...+|xn|^p)^{1/p}，L1范数就是绝对值相加，又称曼哈顿距离。

-||β_j||是一个Lasso约束，用来约束β的稀疏性。

由于要选择的是一个时间片段，所以要约束β系数的连续性，即相邻时间的系数β值是相等的，||β_j-β_j-1||用来实现这样的约束。

根据以上公式(1)，可以得到一个长度为L的β向量：

β＝[β₁，β₂，...，β_L]

要选取的最优时间片段就是使β为最大的一个时间片段，可以使用如下公式(2)来计算最优时间片段：

$>\{\mathrm{lag},T\}=\underset{\{\mathrm{lag},T\}}{\arg \max \frac{1}{T}}\underset{i=\mathrm{lag}}{\overset{i=\mathrm{lag}+T-1}{\Sigma }}{\beta }_i---\left(2\right)$>

图8(a)-8(b)是示出了根据本发明另一个实施例的用于对时长和时间滞后约束进行优化的示意图。例如，假设Y代表PM2.5，而一氧化碳CO、温度和交通流量分别作为白变量X，且N＝10。根据以上的公式(1)和公式(2)，预处理单元110可以计算得到一氧化碳CO、温度和交通流量的时长T及时间滞后约束lag分别为例如(3，1)、(2，1)和(2，2)，如图8(b)所示。

预处理单元110可以将多维数据时间序列转化为样本序列，如图9所示。这样，关联发现单元120可以使用Granger因果图模型从预处理后的数据中发现多元时序列数据的数据元素之间的关联，得到因果图序列。相应地，演变模式发现单元130对得到的因果图序列进行聚合，从而发现因果关系的演变模式。

采用本实施例，因果关系的识别会更加准确。这样，能够更好地识别多元时序列数据的数据元素之间的因果关系以及演变模式。

需要注意的是，尽管上述实施例涉及空气污染因素之间的因果关系以及演变模式的识别，然而本发明不限于此。本领域技术人员在阅读了说明书的教导后，可以将本发明的原理同样地用于识别其他多元时序列数据的数据元素之间的因果关系以及演变模式。

应该理解，本发明的上述实施例可以通过软件、硬件或者软件和硬件两者的结合来实现。例如，上述实施例中的系统内的各种组件可以通过多种器件来实现，这些器件包括但不限于：模拟电路、数字电路、通用处理器、数字信号处理(DSP)电路、可编程处理器、专用集成电路(ASIC)、现场可编程门阵列(FPGA)、可编程逻辑器件(CPLD)，等等。

另外，本领域的技术人员可以理解，本发明实施例中描述的初始参数可以存储在本地数据库中，也可以存储在分布式数据库中或者可以存储在远程数据库中。

此外，这里所公开的本发明的实施例可以在计算机程序产品上实现。更具体地，该计算机程序产品是如下的一种产品：具有计算机可读介质，计算机可读介质上编码有计算机程序逻辑，当在计算设备上执行时，该计算机程序逻辑提供相关的操作以实现本发明的上述技术方案。当在计算系统的至少一个处理器上执行时，计算机程序逻辑使得处理器执行本发明实施例所述的操作(方法)。本发明的这种设置典型地提供为设置或编码在例如光介质(例如CD-ROM)、软盘或硬盘等的计算机可读介质上的软件、代码和/或其他数据结构、或者诸如一个或多个ROM或RAM或PROM芯片上的固件或微代码的其他介质、或一个或多个模块中的可下载的软件图像、共享数据库等。软件或固件或这种配置可安装在计算设备上，以使得计算设备中的一个或多个处理器执行本发明实施例所描述的技术方案。

尽管以上已经结合本发明的优选实施例示出了本发明，但是本领域的技术人员将会理解，在不脱离本发明的精神和范围的情况下，可以对本发明进行各种修改、替换和改变。因此，本发明不应由上述实施例来限定，而应由所附权利要求及其等价物来限定。