时间序列压缩与插值

Question

我有一个算法，但它非常慢。由于我的算法/问题非常简单，我预计这种算法可能已经存在（且速度快），并且可能还有一个名称。在开始开发更快的算法之前，我想先在这里询问一下（我不想重新发明轮子）。

问题很简单：我有一个实验的时间序列，它非常大（约5GB）。事实上，大多数数据点都位于一条线上，例如：

(t=0.0, y=0.0), ... , (t=1.0, y=0.5), ... , (t=2.0, y=1.0)

可以通过用一条直线插值第一个和最后一个点来简化这个问题。原则上，我可以测试一个区间内的点是否可以在某个误差范围内用一条直线逼近，并抛弃其中的点（我不需要无损压缩）。

我的当前算法如下：

1. 我有一个区间[a,b]内的点，并在第一个和最后一个点之间创建一个线性插值（称为f）。 2. 然后，在每个时间序列点处计算误差Abs(f(t) - y)，并选择具有最大误差的点（称为tmax）。 3. 将区间[a,b]分裂成[a,tmax]和[tmax,b]。 4. 在子区间上重复我的算法，直到达到容差或区间仅包含一个或两个点。返回区间边界。

这个算法在逼近信号方面表现出色，但速度非常慢。正如我所说的，我相信已经存在一些可以做同样事情或解决我的问题的方法。

如果有任何不清楚的地方，请随时问我。

- Bomel

---

你认为什么叫做“真的很慢”？一分钟还是一小时？ - user1196549

你可以考虑计算相邻点之间的斜率，并按照相似的斜率进行分组，作为初步压缩步骤或主要算法。 - user1196549

@YvesDaoust 我不是算法复杂度方面的专家，但有个朋友告诉我这是O(n^2)，如果n很大，它需要几秒钟（我正在多个文件上执行此操作）。由于时间会变化，因此很难估计时间。我需要一些至少与n成线性比例的东西。将类似斜率分组的想法听起来不错，我会等待其他答案，然后考虑如何实现它。 - Bomel

相邻点的y值是否相似？你是否期望与最大误差点接近的点也具有较高的误差？ - Dave

@Dave 你说的“类似”是什么意思？是的，实验的数据点应该是“连续”的（连续的意思是：不会跳跃），因此如果 $y_i$ 有很大的误差，$y_{i+1}$ 和 $y_{i-1}$ 也应该有很大的误差。 - Bomel

Answer 1

看起来你想要使用Swinging Door压缩算法。它的基本原理是利用一对门的心理形象，快速吸收数据点到一个范围内，该范围可以用一条直线近似表示。在工业自动化中处理时间序列时，这种算法经常出现。在这个领域，人们往往会快速地收集大量数据，并需要在进行其他计算之前即时汇总数据。

我不会解释它，因为有很多好的解释和源代码。以下是一些链接： PostgreSQL中的Swinging Door Python中的Swinging Door

- btilly

---

一个后续问题：这样的东西在二维中是否也存在，并使用双线性插值？ - Bomel