时间序列数据的SWAB分割算法

Question

我试图了解如何对一组时间序列数据（每日股票价格，温度等）进行细分，并且遇到了一本书，该书解释了如何进行SWAB（滑动窗口和自下而上）细分算法，但我不太了解。这种分割是超声算法的一部分。以下文本来自“多媒体数据挖掘和分析：颠覆性创新”。

SWAB分段算法获得四个参数-输入文件（时间序列数据），输出文件（分段数据），最大误差和标称属性的指示。在对不同大小的时间序列使用不同的分段数值进行大量实验后，我们选择了合适的默认分段数，如下所示。少于100个观测值的时间序列的时间序列大小的25–50％，具有100–200个观测值的时间序列的时间序列大小的20–35％，具有200个以上观测值的时间序列的时间序列大小的15–25％。如果用户出于某种原因对使用默认值不感兴趣，则可以输入自己的段数作为算法的参数。从最小和最大误差的默认值开始，我们第一次运行分段算法，并在给定的时间序列中获得了最少的分段数（最大误差越大，找到的分段越少）。然后，我们通过将基数除以2的幂来减小最大误差（从而增加找到的段的数量），以缩小误差的上限和下限（类似于二进制搜索）。每次使用当前最大误差运行分割算法后，我们都会测试该值是否为最佳分段数提供更好的近似值，因此为最佳最大误差提供更好的上下限。如果是这样，我们将对此值进行适当的限制。开始时，仅上限受到影响。但是，一旦我们发现下界提供的细分比最佳细分更多，我们将继续通过较小的步骤寻找最佳段数：下一个最大误差是当前上限和下限之间的平均值。根据我们对许多不同时间序列数据库的经验，通常在3-4次迭代中可以找到最佳的最大误差。收敛速度取决于输入时间序列数据库本身。如果算法在20次迭代中仍未收敛，我们将停止搜索，并使用在20次迭代中找到的片段继续下一个超声步骤。收敛速度取决于输入时间序列数据库本身。如果算法在20次迭代中仍未收敛，我们将停止搜索，并使用在20次迭代中找到的片段继续下一个超声步骤。收敛速度取决于输入时间序列数据库本身。如果算法在20次迭代中仍未收敛，我们将停止搜索，并使用在20次迭代中找到的片段继续下一个超声步骤。

因此，例如，如果我有150个观测值的时间序列数据（对应于20-35％的默认分段数），我需要采取哪些确切的步骤来对数据进行分段？

非常感谢您的任何帮助。

Answer 1

确切的步骤

以下是该方法的简要描述：

滑动窗口算法的工作原理是将潜在段的左侧点锚定在时间序列的第一个数据点，然后尝试通过增加较长的段来将数据近似到右侧。在某个点 i ，潜在分段的误差大于用户指定的阈值，因此从锚点到 i -1 的子序列被转换为分段。锚点移动到位置 i，重复该过程，直到整个时间序列转换为分段线性近似。

基于此，该算法的伪代码如下。请参阅我在代码中的注释，了解到底发生了什么。

//function takes a set of points T and a max error
function Sliding_Window(T, max_error)
  anchor = 1;
  while (not finished segmenting time series) {
    i=2;

    //keep making subsets of progressively larger size
    //until the error of the subset is greater than the max error
    //t[anchor: anchor + i] represents the elements of the set
    //from index (anchor) to index (anchor + i)
    //this could be an implemented as an array
    while (calculate_error(T[anchor: anchor+i]) < max_error) { 
      i=i+1;
    }

    //add the newly found segment to the set of all segments
    Seg_TS = concat(Seg_TS, create_segment(T[anchor: anchor + (i-1)]);

    //and increment the anchor in preparation for creating a new segment
    anchor = anchor + i;
  }
}

“错误”的定义

您似乎不清楚的一件事是在这种情况下“错误”的含义。下面的段落很好地解释了这一点：

所有分段算法还需要某种方法来评估潜在分段的拟合质量。与线性回归结合使用的常用度量是平方和或残差。这是通过获取最佳拟合线和实际数据点之间的所有垂直差异、将它们平方然后将它们加在一起来计算的。另一种常用的拟合优度度量是最佳拟合线与垂直方向上最远的数据点之间的距离。

换句话说，这里可以用不止一种方法来表示“错误”。统计中常用的两个参数是平方和和最大垂直距离。理论上，您甚至可以为此编写自己的函数，只要它返回一个数字，该数字以某种方式指示该段代表给定点集的程度。

有关平方和方法的更多信息如下： https: //en.wikipedia.org/wiki/Residual_sum_of_squares

如果您想自己实现它，一些伪代码可能如下所示：

function calculateSegmentErrorUsingSumOfSquares() {
  int sum = 0;
  for each (point in set_approximated_by_segment) {
    int difference = point.y_coordinate - approximation_segment.y_at_x(point.x_coordinate)
    sum = sum + (difference * difference)
  }
  return sum
}

请注意，您使用的任何方法都可能有一定的优点和缺点。有关更多信息和参考，请参阅下面 Jason 的评论，但关键点是：确保您选择的任何错误函数都能很好地响应您期望的数据类型。

来源

https://www.cs.rutgers.edu/~pazzani/Publications/survey.pdf