性能问题，使用关联矩阵聚类，特征值

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

一个快速而简单的优化是使用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或Intel的MKL)可以产生非常显著的差异，特别是在这种情况下。

另外，根据numpy的构建方式(例如是否有fortran编译器)，scipy.linalg.eigh等可能更快。也有可能scipy和numpy会链接到不同的blas库，尽管这种可能性很小。

Answer 2

首先，根据您构建矩阵A的方式。它将是一个反对称(也就是偏对称)矩阵，它的秩将(很可能)是2。

也许你应该只取两个最大特征值对应的特征向量。然而特征值很可能是复数。

无论如何，使用svd(奇异值分解)实际上会更直接。

请随意详细说明你的目标

Answer 3

scipy的线性模块。sparse 有三个函数，您经常在这种情况下使用它们(即使您的矩阵不是稀疏的)。总而言之，支持这些函数的解决方案技术更适合于更大矩阵的计算(即，这些函数封装了不同的底层fortran例程，其中包括ARPACK, SEEUPD)。

这是查看scipy.sparse中的类似函数的另一个原因。如果算法没有强制查找所有特征向量/特征值(您几乎不需要，并且对于您的特定用途当然不需要)，则可以节省大量的计算工作。在scipy.sparse. linear中的特征值函数给了你显式的控制。特别地，scipy.sparse.linalg中的eigs函数接受一个参数"k"，该参数是您想要的特征值/特征值的数量。

Answer 4

根据著名数学家和LAPACK贡献者I.S. Dhillon的一篇论文，谱聚类问题可以转化为所谓的核k-均值问题。这可以将计算减少1000倍。他们已经在德克萨斯大学网站上的一个自由软件发布版中实现了该算法。我还没试过，但看起来像真的。当然，与大型特征向量计算相比，SYSTEM()调用的开销微不足道。