通过在 m 行的数据集上应用一次 PCA 与 IncrementalPCA 对 x 批大小为 m/x 的潜在加速?

数据挖掘 机器学习 scikit-学习 主成分分析 降维
2022-01-23 19:36:34

我一直在努力尝试对高维、大容量数据集(有很多行和列 - 大约 100,000 - 1M 行和 ~500 列)执行降维。

虽然我的数据集的大小(m 是行数,n 是列数)不会阻止应用 PCA,但 PCA 可能需要相当多的时间来训练和转换数据。

我想知道是否将数据集分成 x 个批次(每个批次大小相等 m/x 行),然后将 IncrementalPCA() 部分拟合到每个 x 批次中,是否比尝试拟合传统 PCA 更快( ) 针对大小为 m 行的整个数据集?

我相信 PCA 的运行时间是 O(m * n 2 ) + O(n 3 ),因此在这种情况下,IncrementalPCA 只需将内部因子除以 m/x 并将外部的两项乘以 x,因此会导致更高的总体时间复杂度和更慢的性能,总体 x * O(m/x * n 2 ) + x * O(n 3 ) = O(m * n 2 ) + x * O(n 3 )。所以,天真地似乎这个想法行不通。

但是,有人可以提供更多分析,说明使用带有 IncrementalPCA 的小批量进行这种加速是否仍然可行?我怀疑我的推理可能不完整。

我一直在尝试的另一种方法是随机分层抽样,这似乎更标准,但我正在尝试结合各种优化来实现更快的运行时间。

1个回答

增量 PCA 通常只会减少算法的内存占用。所以当你的完整数据集不适合内存时使用它。时间复杂度保持不变。

如果您想加快计算速度,可以查看随机矩阵分解。例如,Sklearn 使用关键字实现它,在该关键字svd_solver='randomized'中,您只近似最终将保留的奇异值。