Python中的滚动窗口PCA

Question

我想知道是否有人知道如何实现滚动/移动窗口PCA，以便在添加和删除测量值时重用计算出的PCA。

这个想法是，我在很长的时间内拥有大量的数据（测量值），我希望在数据集的开头和每一步都有一个移动的窗口（例如200天），包括第二天的测量结果，而没有最后一次测量结果，因此我的窗口始终是200天。但是，我不想每次都简单地重新计算PCA。

是否有可能使算法比仅针对每个窗口单独计算PCA效率更高？预先感谢！

Answer 1

完整的答案取决于很多因素。我将介绍我认为最重要的因素，希望这些信息足以为您指明正确的方向。

首先，直接回答您的问题，是的，有可能使算法比简单地为每个窗口单独计算PCA更为有效。

改进朴素的PCA算法（低维输入）

作为问题的第一步，让我们假设您在不进行归一化的情况下进行了朴素的PCA计算（即，您将使数据保持孤独，计算协方差矩阵，并找到该矩阵的特征值/特征向量）。 >

[面对我们要计算其PCA的输入矩阵X时，朴素算法首先计算协方差矩阵W = X.T @ X。一旦计算出对于200个元素的某个窗口，就可以通过删除原始元素对协方差的贡献，廉价地从原始数据集中添加或删除考虑中的元素。

"""
W:   shape (p, p)
row: shape (1, p)
"""

def add_row(W, row):
  return W + (row.T @ row)

def remove_row(W, row):
  return W - (row.T @ row)
您对滑动窗口的描述等同于删除一行并添加新的一行，因此我们可以使用O（p ^ 2）计算而不是典型的矩阵乘法O（np ^ 2）快速计算新的协方差矩阵将需要（此问题的n == 200）。

协方差矩阵不是最终答案，我们仍然需要找到主成分。如果您自己没有手动滚动特征求解器，那么就没有很多事情要做–您每次都要为新的特征值和特征向量支付费用。

但是，如果您正在编写自己的本征求解器，则大多数此类方法都将接受开始输入并进行迭代，直到达到某种终止条件（通常为最大迭代次数，或者如果误差变得足够小，以先达到者为准）。交换单个数据点不可能大幅度地改变主要成分，因此对于典型数据，人们可能希望将现有特征值/特征向量重新用作特征求解器的输入将使您终止的迭代次数比开始时少得多来自随机输入，从而提供额外的加速。

改进无协方差算法（高维输入）

通常（也许总是？），无协方差的PCA算法具有某种迭代的求解器（非常类似于特征求解器，但是它们具有一些计算捷径，可以在不明确实现协方差矩阵的情况下找到特征值/特征向量。

任何此类方法可能都有其他技巧，可让您将某些信息从一个窗口保存到下一个窗口，但是通常人们希望您可以通过简单地重用现有的主要组件来减少迭代总数使用随机输入启动求解器（非常类似于上面的本征求解器情况）。

带有普通算法的窗口归一化

假设您正在规范化每个窗口以使其每一列的平均值为0（在PCA中很常见），那么在修改协方差矩阵时，您将需要做一些额外的工作。

首先，我假设您已经具有一种滚动机制，用于跟踪需要从一个窗口到下一个窗口应用的任何差异。如果没有，请考虑以下内容：

"""
We're lazy and don't want to handle a change in sample
size, so only work with row swaps -- good enough for
a sliding window.
old_row: shape (1, p)
new_row: shape (1, p)
"""

def replaced_row_mean_adjustment(old_row, new_row):
  return (new_row - old_row)/200.  # whatever your window size is
对协方差矩阵的影响还算不错，但是无论如何我都会在这里放一些代码。

"""
W:      shape (p, p)
center: shape (1, p)
  exactly equal to the mean diff vector we referenced above
X:      shape (200, p)
  exactly equal to the window you're examining after any
  previous mean centering has been applied, but before the
  current centering has happened. Note that we only use
  its row and column sums, so you could get away with
  a rolling computation for those instead, but that's
  a little more code, and I want to leave at least some
  of the problem for you to work on
"""

def update_covariance(W, center, X):
  result = W
  result -= center.T @ np.sum(X, axis=0).reshape(1, -1)
  result -= np.sum(X, axis=1).reshape(-1, 1) @ center
  result += 200 * center.T @ center  # or whatever your window size is
  return result
在PCA中也经常将标度缩放为1。这也很容易适应。

"""
Updates the covariance matrix assuming you're modifing a window
of data X with shape (200, p) by multiplying each column by
its corresponding element in v. A rolling algorithm to compute
v isn't covered here, but it shouldn't be hard to figure out.

W: shape (p, p)
v: shape (1, p)
"""

def update_covariance(W, v):
  return W * (v.T @ v)  # Note that this is element-wise multiplication of W
具有无协方差算法的窗口归一化

您在此处可获得的技巧会因所使用的算法而有很大差异，但是我首先尝试的一般策略是使用滚动算法来跟踪每个算法的均值和标准差当前窗口的列，并修改迭代求解器以将其考虑在内（即，给定一个要在缩放后的窗口Y上进行迭代的窗口X，将Y = a * X + b替换为您选择的迭代算法，并象征性地简化，以期产生带有少量额外固定成本的版本。

与之前一样，您将希望重用找到的所有主要组件，而不是对每个窗口使用随机初始化矢量。