时间序列数据上的SWAB分段算法

Question

时间序列数据上的SWAB分段算法

algorithmtime-seriesanalyticsdata-analysis

5

我正在尝试理解如何对一组时间序列数据（例如每日股票价格、温度等）进行分段，并找到了一本介绍如何使用SWAB（滑动窗口和自下而上）分割算法的书，但我并不完全理解它。这种分割是声音化算法的一部分。以下文字来自《多媒体数据挖掘与分析：颠覆性创新》。

SWAB分割算法有四个参数——输入文件（时间序列数据）、输出文件（分割数据）、最大误差和标称属性指示。在对不同大小的时间序列进行多次实验并尝试不同数量的分段值后，我们选择了适当的默认分段数，如下所示。对于少于100个观测值的时间序列，占时间序列大小的25-50％；对于具有100-200个观测值的时间序列，占时间序列大小的20-35％；对于具有超过200个观测值的时间序列，占时间序列大小的15-25％。如果用户出于任何原因不想使用默认值，则可以将自己的分段数作为算法的参数输入。

从默认的最小和最大误差值开始，我们首先运行分割算法并得到给定时间序列的最小分段数（最大误差越高，发现的分段数就越少）。然后，我们减小最大误差（从而增加找到的分段数），尝试通过将基数除以2的幂来缩小上下界误差范围（就像在二进制搜索中一样）。每次在当前的最大误差下运行分割算法后，我们测试该值是否为最佳分段数提供了更好的近似值，因此是最佳最大误差的更好上限或下限。如果是这样，我们将适当的界限推进到此值。一开始，只有上限受到影响。但是，一旦我们找到了提供比最优解更多分段的下限，我们将继续通过较小的步骤寻找最佳分段数：下一个最大误差是当前上下界的平均值。根据我们对许多不同时间序列数据库的经验，通常在3-4次迭代内找到最佳最大误差。收敛速度取决于输入时间序列数据库本身。如果算法在20次迭代内没有收敛，则停止搜索并继续使用第20次迭代找到的分段进行下一步声音化处理。

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

非常感谢您的帮助。

- charliekelly

1

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - Jason

是的，这也是我不理解的事情之一。你有任何想法吗？感谢你的帮助！@Jason - charliekelly

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- nhouser9 · Accepted Answer

具体步骤

以下是方法的简要描述：

滑动窗口算法通过将潜在段的左端点锚定在时间序列的第一个数据点上，然后尝试使用越来越长的段向右逼近数据。在某个点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;
  }
}

"Error"的定义

您似乎不清楚此上下文中“error”的含义。以下段落很好地解释了它：

所有分割算法都需要一些方法来评估潜在分割的拟合质量。与线性回归一起常用的度量是平方和，或者残差误差。这是通过取最佳拟合线与实际数据点之间的所有垂直差异，将它们平方，然后将它们加在一起计算得出的。另一个常用的适合度量是最佳拟合线与垂直方向上最远的数据点之间的距离。

换句话说，在这里表示“错误”的方法不止一种。在统计学中常用的两种方法是平方和和最大垂直距离。理论上，只要返回一个某种方式表明分割如何代表给定点集的数字，就可以编写自己的函数。

关于平方和方法的更多信息，请参见此处：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