Очень большая и очень редкая факторизация неотрицательной матрицы

Question

У меня очень большая и тоже разреженная матрица (531K x 315K), общее количество ячеек составляет ~167 млрд. Ненулевые значения только 1 с. Общее количество ненулевых значений составляет около 45К. Существует ли эффективный пакет NMF для решения моей проблемы? Я знаю, что есть несколько пакетов для этого, и они работают хорошо только для небольшого размера матрицы данных. Любая идея помогает. Заранее спасибо.

Answer 1

scikit-learn справится с этим легко!

Код:

from time import perf_counter as pc
import numpy as np
import scipy.sparse as sps
from sklearn.decomposition import NMF

""" Create sparse data """
nnz_i, nnz_j, nnz_val = np.random.choice(531000, size=45000), \
                        np.random.choice(315000, size=45000), \
                        np.random.random(size=45000)
X =  sps.csr_matrix((nnz_val, (nnz_i, nnz_j)), shape=(531000, 315000))
print('X-shape: ', X.shape, ' X nnzs: ', X.nnz)
print('type(X): ', type(X))
# <class 'scipy.sparse.csr.csr_matrix'> #                          !!!!!!!!!!

""" NMF """
model = NMF(n_components=50, init='random', random_state=0, verbose=True)

start_time = pc()
W = model.fit_transform(X)
end_time = pc()

print('Used (secs): ', end_time - start_time)
print(model.reconstruction_err_)
print(model.n_iter_)

Выход:

X-shape:  (531000, 315000)  X nnzs:  45000
type(X):  <class 'scipy.sparse.csr.csr_matrix'>
violation: 1.0
violation: 0.2318929397542804
violation: 0.11045394409727402
violation: 0.08104138988253409
...
violation: 9.659665625799714e-05
Converged at iteration 71
Used (secs):  247.94092973091756
122.27109041
70

Примечания:

• Убедитесь, что вы используете разреженные матрицы в качестве входных данных или вы не можете использовать разреженность
• Я использую версию 0.19.1, поэтому используется решатель мультипликативного обновления (>= 0.19)
  • Но старый решатель на основе CD должен справиться и с этим!
• Выше используется < 800 МБ памяти

Дополнительные ограничения

Как уже упоминалось в комментариях, OP хочет добавить дополнительные ограничения, хотя формально они не указываются.

Для этого потребуется совершенно новая реализация некоторой процедуры оптимизации, в том числе теоретической работы (в зависимости от ограничений).

В качестве альтернативы это может быть решено с помощью универсальных решателей выпуклого программирования. Например, сформулировано cvxpy и решено SCS. Конечно, нужно также выполнить процедуру чередующейся минимизации (так как проблема соединения невыпукла), и она будет масштабироваться хуже, чем эта специализированная реализация sklearn. Но это может работать для данных ОП.