Проблемы производительности, кластеризация с использованием аффинной матрицы, собственные значения

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 (например, был ли доступен компилятор фортрана) scipy.linalg.eigh и т. Д. Может быть быстрее. Также существует вероятность, что scipy и numpy могут быть связаны с различными библиотеками blas, хотя это довольно маловероятно.

Answer 2

Модуль linalg из scipy.sparse имеет три функции, которые вам часто помогают в подобных ситуациях (даже если ваша матрица не разрежена).В итоге, методы решения, которые обеспечивают эти функции, лучше подходят для вычислений с гораздо более крупными матрицами (то есть эти функции обертывают различные базовые подпрограммы Фортрана, среди них ARPACK, SEEUPD.)

Вот еще одна причина, чтобы взглянуть нааналогичные функции в scipy.sparse.Значительное количество вычислительных усилий экономится, если алгоритм не вынужден искать все собственные векторы / собственные значения (которые вам почти никогда не нужны, и, конечно, не нужны для вашего конкретного использования).Функции собственных значений в scipy.sparse.linalg дают вам явный контроль над этим.В частности, функция eigs в scipy.sparse.linalg принимает параметр «k», который представляет собой количество требуемых собственных значений / собственных значений.

Answer 3

Прежде всего, исходя из того, как вы построили свою матрицу A.Это будет антисимметричная (или кососимметричная) матрица, и ее ранг будет (очень вероятно) 2.

Возможно, вам следует брать только собственные векторы, соответствующие двум наибольшим собственным значениям.Однако, вероятно, что собственные значения являются сложными.

В любом случае, возможно, что работа с svd (разложение по сингулярным значениям) будет на самом деле более простой.

Пожалуйста, не стесняйтесь уточнять, к чему вы стремитесь.

Answer 4

Согласно статье выдающегося математика и автора LAPACK И.С. Диллон, проблемы спектральной кластеризации можно преобразовать в так называемые проблемы ядра с k-средними. Это может сократить вычисления в 1000 раз. Они внедрили алгоритм в бесплатное программное обеспечение выпуск на веб-сайте Техасского университета. Я еще не пробовал, но это похоже на реальную вещь. Конечно, издержки вызова SYSTEM () ничто по сравнению с вычислением большого собственного вектора.