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

Question

Использование Scikit-learn (v 0.15.2) для неотрицательной матричной факторизации на большой разреженной матрице (менее 1% значений> 0). Я хочу найти факторы, минимизируя ошибки только при ненулевых значениях матрицы (т. Е. Не вычисляя ошибки для записей, которые равны нулю), и в пользу разреженности. Я не уверен, что что-то не так с тем, что я пытаюсь. NMF и проект ProjectGradientNMF для scikit-learn успешно работали для меня раньше. Но, похоже, когда размер матрицы увеличивается, факторизация ужасно медленная.

Я говорю о матрицах с> 10^10 ячейками. Для матрицы с ячейками ~ 10^7 я считаю время выполнения хорошим.

Параметры, которые я использовал, следующие: nmf_model = NMF(n_components = 100, init='nndsvd', random_state=0, tol = 0.01, sparseness='data').

Когда я попробовал несколько разные параметры (измените на init=random), я получаю следующее предупреждение. После предупреждения выполнение сценария останавливается.

/lib/python2.7/site-packages/sklearn/decomposition/nmf.py:252: UserWarning: Iteration limit reached in nls subproblem. 
    warnings.warn("Iteration limit reached in nls subproblem.") 

Есть ли способ сделать это быстрее и решить вышеуказанную проблему? Я попытался использовать numpy разреженную матрицу (столбцы и строки-разреженные), но удивительно - это медленнее в тесте, который я сделал с меньшей матрицей (~ 10^7 ячеек).

Учитывая, что нужно было бы запускать множество итераций такой факторизации (выбрать идеальное число факторов и k-кратное перекрестное подтверждение), более быстрый способ решить эту проблему весьма желателен.

Я также открыт для предложений пакета/инструментов, которые не основаны на sklearn или Pyhon. Я понимаю, что вопросы о выборе пакета/инструмента не поощряются, но для такого конкретного случая использования, зная, какие методы могут использовать другие в полевых условиях, очень полезно.

Answer 1

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

Матричная факторизация на очень большой матрице всегда будет медленной из-за характера проблемы.

Предложения: Сокращение n_components до < 20 ускорит его. Однако единственное реальное улучшение скорости будет достигнуто за счет ограничения размера матрицы. С такой матрицей, как вы описали, можно подумать, что вы пытаетесь разложить матрицу частотных выражений. Если это так, вы можете попытаться использовать функции векторизации в scikit-learn, чтобы ограничить размер матрицы. Большинство из них имеют параметр max_features. Пример:

vectorizer = TfidfVectorizer(
    max_features=10000, 
    ngram_range=(1,2)) 
tfidf = vectorizer.fit_transform(data) 

Это значительно ускорит решение проблемы.

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

Answer 2

Вы можете взглянуть на эту статью, которая обсуждается более поздние методы на NMF: http://www.cc.gatech.edu/~hpark/papers/nmf_blockpivot.pdf

Идея заключается в том, чтобы работать только на ненулевых элементов для факторизации, которая уменьшает время вычислений, особенно когда матрица/матрицы, участвующих/очень редки.

Кроме того, один из авторов из той же статьи создал реализации NMF на github, включая те, которые упомянуты в их статье.Вот ссылка: https://github.com/kimjingu/nonnegfac-python

Надеюсь, что это поможет.