论文阅读：Streaming pattern discovery in multiple time-series

VLDB 发表时间：2005 作者：Spiros Papadimitriou
在2005年提出的该方法具有很强的先进性，可以利用该思想对模型进行改进和验证。是一篇非常值得学习的文章

abstract

In this paper, we introduce SPIRIT (Streaming Pattern discovery in multIple Time-series). Given n numerical data streams, all of whose values we observe at each time tick t, SPIRIT can incrementally find correlations and hidden variables, which summarise the key trends in the entire stream collection. It can do this quickly, with no buffering of stream values and without comparing pairs of streams. Moreover, it is anytime, single pass, and it dynamically detects changes. The discovered trends can also be used to immediately spot potential anomalies, to do efficient forecasting and, more generally, to dramatically simplify further data processing. Our experimental evaluation and case studies show that SPIRIT can incrementally capture correlations and discover trends, efficiently and effectively.

1.这篇文章提出了SPIRIT多时间序列中流模式的发现，从时间间隔为t的n个数据流，找到相关性和隐藏变量（提取流数据中的关键信息）。
2.该方法具有快速、不需要缓存、不需要对照流的优点，同时可以在任何时候、动态的检测变化。
3.该方法可以立刻检测异常点，进行高效的预测，简化下一步的数据处理。
4.并通过实验验证了该方法捕获相关性和发现趋势越来越有效。

背景：

流数据是非常常见的数据形式，他们都有两个共同点，1）数据量大刷新频率高，实时处理缓慢2）用户或者应用不能得到及时的数据反馈。流数据的处理已经有一些基础模型，并在实际中应用。流数据管理系统对预测模型和行惯性分析是十分重要的，流数据中很多变量是相关的，用很少的隐藏变量处理表示流数据的是十分重要的，该文章提出用少数变量表示整个流数据特征的方法。

该方法主要有两个作用：

1.发现流数据的模式，用隐藏变量表示流数据的变化规律。
2.自动确定隐藏变量个数。

该方法对数据的要求：

1.流数据
2.数据根据流数的多少进行线性变化（不能是平方或者非线性）
3.It is adaptive, and fully automatic.（个人理解应该是动态变化的）

解决问题：

对多个流数据进行自动特征提取，用k个变量表征多个流数据的规律。可以用作异常检测和预测。

实现该方法的主要步骤：

1.计算隐藏变量
1）主成分分析获得 $w_t$
2）根据 $w_t$ 计算隐藏变量 $y_i$
3）根据隐藏变量计算重构误差 $e$
4）根据误差 $e$ 更新 $w_t$ 和 $y_i$
2.计算隐藏变量的个数 $k$
1）根据输入 $x_t$ 的平方和计算 $E_{t+1}$
2）计算 $k$ 个隐藏变量下的 $E_{(k)}$
3）根据 $E_{t+1}$ 、 $E_{k}$ 和两个阈值调整 $k$ 的大小
其中 $w_t$ 、 $y_i$ 、 $e$ 、 $E_{t+1}$ 、 $E_{k}$ 给出了详细的计算步骤。

实验结果：

论文用了三种数据集验证该方法的有效性，并对精度进行分析。

结论：

该方法有效地实现了在流数据中寻找模式、相关性和隐藏变量，并具有以下特性：

发现多个流之间的潜在相关性，获得隐藏变量，并通过一些隐藏变量提供流集合的非常紧凑的表示。
自动估计要隐藏变量的数量k。
无论是在数据库大小（即时间刻度t的数量）还是在流的数量n上，它的扩展都非常好。因此，它适用于大量的传感器/数据源。
计算要求低：只需O(nk)浮点运算，无矩阵变换和奇异值分解（SVD）
它可以很自然地与任何预测方法相结合，因此很容易进行预测，并处理缺失值。