使用 sklearn 和大亲和力矩阵进行谱聚类

Question

我正在尝试使用 scikit-learn 提供的谱聚类方法来聚合数据集的行（仅 16000）。 在我预先计算亲和力矩阵（一个 16000x16000 浮点矩阵）后，我的问题出现了，它分配了 3 GB 的大小（我最多可以达到 8 GB），使用 argpack 求解器对该矩阵调用的方法需要更多的内存并且CPU在尝试将内容换入内存和换出内存时损失了太多时间，导致计算速度减慢至极点。 我也尝试在该方法之前调用垃圾收集器，但没有成功：

import gc
gc.collect()

我怎样才能得到正在发生的事情的精确方案？ 这是一个已知的问题？ python 中是否有任何替代方案可以立即执行谱聚类？

如果需要，我可以发布一个最小的工作示例。

更新 我对 lobpcg 求解器的看法是错误的，一开始它似乎使用了我所有的内存，但后来它稳定在 5Gb 左右，并且该过程继续进行，但又出现了另一个问题。 看起来计算会导致一些数值不准确，最终会产生 Nans 或类似这样的错误（当亲和力矩阵发生一点变化时，出现的错误会发生变化，见下文）：

File "/usr/local/lib/python3.4/dist-packages/sklearn/cluster/spectral.py", line 255, in spectral_clustering
eigen_tol=eigen_tol, drop_first=False)
File "/usr/local/lib/python3.4/dist-packages/sklearn/manifold/spectral_embedding_.py", line 303, in spectral_embedding
largest=False, maxiter=2000)
File "/usr/local/lib/python3.4/dist-packages/scipy/sparse/linalg/eigen/lobpcg/lobpcg.py", line 449, in lobpcg
assert np.allclose(gramA.T, gramA)
AssertionError

我的亲和力度量是高斯核

exp(-((X_1 - x_2)^2/2*sigma^2))

，当尝试不同的西格玛值时，结果变化很大。我可以理解，当某些条目接近于零时，可能会出现一些不准确的情况，但当我使用较大的 sigma 值 (= 5.0) 时，情况并非如此，而是让它们更接近 1.0。

现在我假设我遗漏了一些要点，或者我在这个过程中做错了什么，所以我以新的目标更新这个问题。

作为参考，这就是我计算亲和力矩阵的方法：

 pairwise_dists = \
      scipy.spatial.distance.squareform(
           scipy.spatial.distance.pdist(data_slice,'sqeuclidean'))
 similarity_matrix = scipy.exp(-pairwise_dists /(2 * self._sigma ** 2))

其中

data_slice

是一个 numpy 数组，其行是我的实例，

self._sigma

存储高斯 sigma 参数。

Answer 1

谱聚类计算相异矩阵的特征向量。

这个矩阵的大小为 O(n^2)，因此几乎任何实现都需要 O(n^2) 内存。

16000x16000x4（假设浮动存储，并且没有开销）

is 大约 1 GB。它可能需要一个工作副本（诸如 scipy.exp

 之类的方法可能会生成矩阵的副本；并且可能具有双精度）和一些开销，这就是您最终使用 3 GB 的原因...

该算法不适用于大数据，就像任何其他需要 O(n^2) 内存的算法一样。选择不同的算法；也许可以使用索引结构来加速。或者减少数据集大小，例如通过采样。