基于矩阵恢复的时间序列缺失值填补技术

利用矩阵恢复进行时间序列缺失值填补处理时间序列中的缺失值并非易事。在《使用Python进行现代时间序列预测》一书中作者探讨了几种技术从正确看待缺失值到一些处理缺失数据的算法技术如季节性插值。最初这部分内容本应更长并包含一些基于矩阵恢复的高级技术这些技术在相关数据集中非常有用。例如能否利用其他相关时间序列的信息来智能地填补空缺但由于书籍篇幅已过大作者不得不删减了部分内容。本文将重现书中被删减的部分。文中使用的代码和实现已包含在相关的GitHub代码库中代码示例所使用的数据也与书中的相同。矩阵恢复技术矩阵恢复技术广泛应用于推荐系统旨在补全用户-物品交互矩阵以便向用户推荐更合适的物品。但这些技术同样适用于其他领域其中之一就是填补数据集中的缺失值。这类方法不是孤立地看待每个时间序列而是依赖一组相关的时间序列来填充缺失数据。其核心思想是假设存在一个能够忠实代表原始大矩阵信息的低秩矩阵然后尝试找到这个矩阵。补充信息矩阵的秩是其最大线性无关的列向量或行向量的数量。根据定义它始终小于或等于矩阵的列数或行数。如果矩阵中的任何一列或行是其他列或行的线性组合则称该矩阵不是满秩的。通过对矩阵进行奇异值分解并计算非零特征值的数量也可以求出矩阵的秩。可以将此问题形式化为一个学习问题学习一个矩阵Z最小化rank(Z) 约束于 ‖X-Z‖₂ ≤σ其中σ是控制训练误差容限的正则化参数。但直接最小化秩是难以处理的因此有许多替代方法或启发式算法来解决这个优化问题。由于需要一组相关的时间序列来执行基于矩阵恢复的技术我们准备一个包含所有时间序列的数据块不同的时间序列构成数据框的不同列。all_ts_dfpd.pivot_table(exp_block_df,indextimestamp,columnsLCLid,valuesenergy_consumption)# 将窗口内的数据设为空all_ts_df.loc[window,MAC000193]np.nan接下来将介绍几种矩阵恢复技术矩阵分解让我们通过推荐系统的例子来理解这个概念然后将直觉扩展到时间序列。在推荐系统中用户-物品矩阵是一个行表示用户、列表示物品的矩阵。在用户和物品的交汇处是该用户对该物品的评分。假设有m个用户和n个物品就得到一个m×n的交互矩阵R。我们假设每个用户和物品都可以用一组k个属性来表示其中k远小于矩阵的原始大小。这是因为矩阵的列和行之间存在主要的关联性。尽管我们相信每个人对电影的品味都是独特的但我们仍然可以与其他喜欢相同内容的用户分组。同样物品也可以根据它们之间的相似性进行分组。因此通过矩阵分解我们将用户-物品矩阵分解为两个矩阵U和V使得R≈U×Vᵀ。矩阵U称为用户潜在因子矩阵矩阵V称为物品潜在因子矩阵。现在将注意力转向一组相关的时间序列。假设有n个时间序列每个有m个时间步得到一个m×n的交互矩阵X。与用户-物品矩阵类似该矩阵也存在主要关联性即存在一组较小的模式可以描述整个矩阵。某些时间序列会有相似的行为例如具有固定的趋势或强季节性。并且某些时间步也会共享共同的模式例如因公共假期或周末导致的能源消耗增加。因此当对此类矩阵应用矩阵分解时得到的是两个矩阵U和V使得X≈U×Vᵀ。矩阵U包含与时间方面相关的潜在因子矩阵V包含特定于单个时间序列的潜在因子。下图直观地展示了此过程。图 2.11一组相关时间序列的矩阵分解那么如何得到这些矩阵呢这时就需要梯度下降法。可以利用观测值上的损失函数L1、L2 或任何其他回归损失借助梯度下降来学习这些矩阵。一旦得到这些矩阵就可以通过将两者相乘来恢复缺失数据。在下面的练习中将使用 Python 库fancyimpute。它实现了许多矩阵恢复技术并提供了类似于 scikit-learn 的 API。fromfancyimputeimportMatrixFactorization recovered_matrix_mfMatrixFactorization(rank50).fit_transform(all_ts_df.values)矩阵的秩是一个超参数需要通过良好的交叉验证设置来寻找。在本文的练习中仅使用人工创建的时间序列缺口作为测试集进行简单的网格搜索。下图展示了恢复效果。图 2.12使用矩阵分解进行填补可以看到填补的时间序列中捕获了季节性特征但平均绝对误差MAE略高。截断奇异值分解和迭代奇异值分解计算分解矩阵的另一种方法是使用奇异值分解。SVD 是一种将任何实数矩阵分解为奇异矩阵和奇异值的技术。SVD 可以用以下等式表示其中X是原始矩阵U是左奇异矩阵V是右奇异矩阵Σ是包含r个奇异值的对角矩阵。XU×Σ×VᵀΣ中的奇异值按降序排列最大值位于对角线顶部向下移动时减小。U和Vᵀ的维度使得矩阵乘法能够恢复原始矩阵。下图直观地描述了 SVD图 2.13奇异值分解如果听过主成分分析PCA这个过程与它有很强的联系。奇异值可以被认为类似于从 PCA 中得到的特征值。执行 SVD 的方法有很多但这超出了本文的范围。像 numpy 和 scipy 这样的流行库提供了可以用于此目的的实现。虽然这看起来很直接但存在一个问题SVD 无法在不完整的矩阵上工作。因此如果存在缺失值需要在进行 SVD 之前用某些值填充。但这违背了初衷不是吗一种方法是用零、均值或某种近似值填充执行 SVD然后使用得到的矩阵恢复数据中的缺失值。但这会导致最终得到的结果正是最初用来填充缺失值的近似值。这就是截断 SVDTruncated SVD的作用所在。截断 SVD 假设我们不需要所有奇异值来重构矩阵。相反它选择k个最高的奇异值并仅使用它们来重构矩阵。当使用k个奇异值时也只会使用U和Vᵀ的前k列来执行恢复原始矩阵X所需的矩阵乘法。下图说明了这个过程。图 2.14截断奇异值分解这使得能够提取数据中的关键模式并利用它们来重构缺失数据。因此在重构矩阵时可以忽略最初用于填充初始矩阵的近似值而倾向于数据中的主导模式。接下来看看实际效果。这种恢复技术已在关联的 GitHub 代码库的src/imputation/matrix_recovery.py中实现。可以像下面这样使用它。fromsrc.imputation.truncated_svdimportTruncatedSVDImputation recovered_matrix_tsvdTruncatedSVDImputation(rank2,init_fill_methodzero,min_value0).fit_transform(all_ts_df.values)下图展示了填补效果。图 2.15使用截断奇异值分解进行填补季节性模式已被捕获但第一天的下午 6 点峰值略有偏差。可以看到 MAE 也不理想。迭代 SVDIterative SVD是另一种启发式方法旨在克服 SVD 之前因初始填充缺失值而产生的不准确性。在迭代 SVD 中多次执行这种截断 SVD每次迭代都用估算的值替换缺失值。首先用零、均值或其他近似值填充缺失值然后运行截断 SVD 来恢复缺失值。接着用新的估算值替换之前的近似值再次运行截断 SVD。此过程持续进行直到达到最大迭代次数或收敛标准。fancyimpute中已经实现了此方法接下来将使用它。fromfancyimputeimportIterativeSVD recovered_matrix_isvdIterativeSVD(rank2,max_iters1000,svd_algorithmarpack,min_value0).fit_transform(all_ts_df.values)这里的关键超参数是秩rank与矩阵分解类似需要通过良好的交叉验证框架来寻找。如果处理的矩阵非常大传递参数svd_algorithm randomized可以执行随机 SVD这是一种更快的 SVD 近似算法。下图展示了此技术的效果图 2.16使用迭代奇异值分解进行填补捕获的模式与简单的截断 SVD 几乎相同MAE 也相似。Soft ImputeSoft Impute 是另一种以 SVD 为核心的技术。2010 年Rahul Mazumder 等人发表了一篇名为《用于学习大型不完全矩阵的谱正则化算法》的论文。这是一种类似于迭代 SVD 的启发式方法但不是每次迭代使用固定的秩而是使用阈值技术来选择要使用的重要奇异值。有一个称为 shrinkage value 的参数它决定了每次迭代中奇异值被“收缩”的程度。fancyimpute实现了此算法可以直接使用。具体做法如下。recovered_matrix_siSoftImpute(shrinkage_value70,max_iters1000,min_value0).fit_transform(all_ts_df.values)与调整秩不同这里的关键超参数是shrinkage_value。默认情况下实现使用最大奇异值的 1/50 作为shrinkage_value。但可以定义自己的网格并在该网格中搜索最佳值。为此只需查看前 10 个奇异值并根据这些值定义一个范围。fromsklearn.utils.extmathimportrandomized_svd# 快速将 X_filled 分解为秩为1的SVD_,s,_randomized_svd(all_ts_df.fillna(0).values,10,n_iter5)print(f奇异值为:{s})奇异值为:[449.19968819226.76815429108.13701595104.1627405293.0436504984.5594148775.9677355273.7264456667.7400566464.71221699]在此案例中将网格定义为 [60, 70, 80, 90, 100, 150, 250]发现shrinkage_value70时重构误差最低并在恢复算法中使用该 shrinkage value。下图展示了效果图 2.17使用 Soft Impute 进行填补可以看到它在捕捉午夜和清晨的低值方面稍好一些因此 MAE 也更低。质心恢复质心分解Centroid Decomposition是 SVD 的一种近似方法。它计算质心值、载荷向量、相关性向量分别近似 SVD 的奇异值、右奇异矩阵和左奇异矩阵。对于一个m×n的矩阵X其质心分解形式为XL×R其中L是m×n矩阵R是n×n矩阵。但与截断 SVD 类似在质心分解中在重构原始矩阵时也会将结果矩阵截断为k个分量。传统的质心分解方法是暴力驱动的对于大型矩阵而言其空间和时间复杂度都过高。Khayati, M. 等人提出了一种可扩展的算法来计算质心分解该算法可用于矩阵恢复。此恢复技术已在关联的 GitHub 代码库的src/imputation/matrix_recovery.py中实现。可以像下面这样使用它。fromsrc.imputation.cdrecimportCentroidRecovery recovered_matrix_cdrecCentroidRecovery(truncation5,max_iters100,init_fill_methodinterpolate,min_value0,early_stoppingTrue).fit_transform(all_ts_df.values)这里的关键参数再次类似于秩truncation。它决定了在生成分解矩阵时强制进行多大的降维。与之前一样通过带有强交叉验证设置的网格搜索来找到它。下图展示了其效果图 2.17使用质心分解进行填补参考文献Mazumder, Rahul Hastie, Trevor Tibshirani, Robert. (2010). 用于学习大型不完全矩阵的谱正则化算法. Journal of machine learning research : JMLR. 11. 2287-2322. – https://www.jmlr.org/papers/v11/mazumder10a.htmlKhayati, M., Cudré-Mauroux, P. Böhlen, M.H. 高、低互相关时间序列中缺失块的可扩展恢复. Knowl Inf Syst 62, 2257–2280 (2020). https://doi.org/10.1007/s10115-019-01421-7延伸阅读矩阵分解 – https://developers.google.com/machine-learning/recommendation/collaborative/matrix奇异值分解 – https://gregorygundersen.com/blog/2018/12/10/svd/随机 SVD – https://www.youtube.com/watch?vfJ2EyvR85roMourad Khayati, Alberto Lerner, Zakhar Tymchenko, and Philippe Cudré-Mauroux. 2020. 关注缺口时间序列中缺失值填补技术的实验评估. Proc. VLDB Endow. 13, 5 (2020年1月), 768–782. http://www.vldb.org/pvldb/vol13/p768-khayati.pdf《使用Python进行现代时间序列预测》FINISHED更多精彩内容 请关注我的个人公众号 公众号办公AI智能小助手或者 我的个人博客 https://blog.qife122.com/对网络安全、黑客技术感兴趣的朋友可以关注我的安全公众号网络安全技术点滴分享