python - 使用 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 值时，结果会有很大差异。我可以理解，当某些条目接近于零时，可能会出现一些不准确的情况，但当我使用较大的 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(假设 float 存储，并且没有开销)大约为 1 GB。它可能需要一个工作副本(诸如 scipy.exp 之类的方法可能会生成矩阵的副本；并且可能具有 double )和一些开销，这就是您最终使用 3 GB 的原因...

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