巨大稀疏数据集上的主成分分析（PCA）

Question

我有大约1000个50000维度的向量x_i，但它们非常稀疏，每个向量只有大约50-100个非零元素。我想在这个数据集上进行PCA（在MATLAB中），以减少数据的不必要的极端维度。

不幸的是，由于需要从所有实例中减去均值，我不知道如何在没有中间完整矩阵的情况下完成此操作。当然，一个1000x50000的矩阵太大了，无法放入内存（实际上会导致我的整个计算机崩溃，原因未知）。当我尝试使用Matlab的内置princomp时，也会导致计算机崩溃。

所以我的问题是：是否有一种方法可以在不需要作为中间步骤的大规模非稀疏矩阵的情况下对此数据进行PCA？

- Sean

---

1000x50000x8 = 381MB。由于MATLAB需要矩阵的连续内存，这并不令人惊讶。 - Jacob

你的电脑崩溃了还是只有MATLAB？只是好奇。 - Jacob

我的整台电脑都得在前面按重置按钮。这真的很奇怪... - Sean

你可以使用Windbg来查找导致计算机崩溃的具体原因。谷歌一下吧。 :) - Don Reba

Answer 1

你不需要形成完整的数据矩阵来减去平均值或计算协方差矩阵。只需迭代计算1000x1000的协方差矩阵（循环遍历数据向量）。一旦你形成了协方差矩阵，你可以通过将协方差矩阵进行中心化来隐式地减去平均值。请参阅这篇关于核PCA的论文结尾部分，其中详细说明了如何对核矩阵进行中心化处理。只需将核矩阵视为协方差矩阵即可。

- flubdub

---

实际上，如果你在MATLAB中使用“稀疏矩阵”类型来表示数据矩阵，你就不需要迭代地计算协方差矩阵。只需确保在此之前不要减去均值，而是将结果的协方差矩阵居中。 - flubdub

Answer 2

以下策略有效：

[~,~,PC] = svds(X,k);
mu = mean(X);
S = sparse(size(X,1),k);
for i=1:size(X,1)
    S(i,:) = (X(i,:)-mu)*PC;
end

< p > X的右奇异向量是cov（X，1）的特征向量，因此是X的主成分。通过逐个计算主成分得分而不是一次性计算所有得分，可以避免从稀疏到完整的内存溢出。只需确保使k<<p，您就应该没问题。

- PikalaxALT

Answer 3

为了计算所提到的数据集的PCA，算法只需要在1000x1000协方差矩阵上进行操作。对于大多数PCA实现来说，这应该不是什么大问题。 如果您正在使用Windows 7电脑，可以尝试使用64位的PCA实现。我不确定Matlab是否支持64位PCA，但像VisuMap这样的应用程序可以轻松处理这些情况。

- James x. Li

Answer 4

你不需要使用princomp。这个答案会解释如何使用eig来实现。将eig替换为eigs。

- Jacob

---

很不幸，那个答案对我没有帮助...我知道如何找到数据集的主成分，只是庞大的大小让我困扰。我不能像X = bsxfun(@minus, meas, mean(meas));那样做，因为它会把我的稀疏矩阵转换成一个完整的矩阵，太大而无法放入内存中。 - Sean

抱歉，我应该说：在我的数据集上调用cov(X)也有同样的问题。 - Sean

@Sean: 这也可能有帮助：MATLAB的内存不足，但实际上不应该 - Amro

Answer 5

首先，您不需要协方差矩阵来减去均值。

然后，要计算主成分，请参见此问题的答案。

- chaohuang

---

我知道，具体来说不是协方差矩阵导致了问题，而是我所知道的任何方法（包括涉及计算协方差矩阵或仅减去平均值并进行SVD等流行方法）都涉及非稀疏矩阵，太大而无法放入内存。不确定您在链接的问题中引用了什么......我正在寻找一种在Matlab中完成此操作的方法或通用的数学答案。 - Sean

Answer 6

对于顶级PC，请参见迭代PCA; 这将累积50k密集和50k稀疏的总和，应该可以工作。
对于第二个，请在运行时减去第一个，即使用（X-U1 d1 Vt1）而不实例化它。
（随机PCA在Python scikit-learn中执行此操作，Matlab不知道。）

- denis