性能问题，基于亲和矩阵的聚类，特征值

Question

我正在尝试在一张图片上使用谱聚类。首先，我计算了亲和力矩阵，然后想要获取特征向量。但是，对于一个7056x7056的矩阵，调用eig()函数的时间太长了。有没有什么建议可以提高这个过程的效率？也许我应该使用不同形式的亲和力？

import matplotlib.pyplot as plt
import numpy as np

Img = plt.imread("twoObj.bmp")
Img2 = Img.flatten()
(n,) = Img2.shape
A = np.subtract.outer(Img2, Img2)
V,D = np.linalg.eig(A)

Answer 1

来自 scipy.sparse 的 linalg 模块有三个函数，通常在这种情况下会很有帮助（即使你的矩阵不是稀疏的）。总的来说，这些函数背后的解决方案技术更适合处理更大的矩阵（也就是说，这些函数实际上是调用了不同的 Fortran 程序，比如 ARPACK 和 SEEUPD 等）。

还有一个理由让你去看看 scipy.sparse 中类似的函数。如果算法不需要去寻找所有的特征向量和特征值，那么可以节省大量的计算资源（其实你几乎从来不需要所有的特征向量和特征值，尤其是对于你特定的使用场景）。scipy.sparse.linalg 中的特征值函数让你可以 明确控制 这一点。特别是，scipy.sparse.linalg 中的 eigs 函数接受一个参数 "k"，这个参数就是你想要的特征值的数量。

Answer 2

首先，关于你是怎么构建你的矩阵 A 的，它会是一个反对称矩阵（也叫做斜对称矩阵），而且它的秩（也就是矩阵的一个重要特性）很可能是2。

也许你应该只考虑与两个最大特征值对应的特征向量。不过，这些特征值很可能是复杂的。

无论如何，使用 svd（奇异值分解）可能会更简单一些。

请随时详细说明一下你想要达到的目标。

Answer 3

一个快速简单的优化方法是使用 np.linalg.eigh。如果你只想要特征值，可以用 np.linalg.eigvalsh。

因为你有一个对称矩阵（假设你取了绝对值），你可以“告诉”numpy使用更高效的算法。

import numpy as np
x = np.random.random(1000)
A = np.subtract.outer(x, x)
A = np.abs(A)
w, v = np.linalg.eigh(A)

比较一下时间，eigh 大约需要 5.3 秒，而 eig 则需要大约 23.4 秒。

np.linalg.eig 等的性能会很大程度上依赖于numpy所链接的库。使用一个经过高度优化的blas库（比如ATLAS或英特尔的MKL）会有显著的差别，尤其是在这种情况下。

另外，根据numpy的构建方式（例如，是否有Fortran编译器可用），scipy.linalg.eigh 等可能会更快。还有一种可能是scipy和numpy可能链接了不同的blas库，尽管这种情况不太常见。