Нанести PCA на очень большую разреженную матрицу

16

Я делаю задачу классификации текста с помощью R и получаю матрицу терминов документа размером 22490 на 120 000 (только 4 миллиона ненулевых записей, менее 1% записей). Теперь я хочу уменьшить размерность, используя PCA (анализ основных компонентов). К сожалению, R не может обработать эту огромную матрицу, поэтому я храню эту разреженную матрицу в файле в «Matrix Market Format», надеясь использовать некоторые другие методы для создания PCA.

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

Я хочу рассчитать все ПК (120 000) и выбрать только первые N ПК, на которые приходится 90% отклонений . Очевидно, что в этом случае я должен задавать порог априори, чтобы установить очень малые значения дисперсии равными 0 (в ковариационной матрице), в противном случае ковариационная матрица не будет разреженной, и ее размер будет 120 000 на 120 000, что невозможно справиться с одной машиной. Кроме того, нагрузки (собственные векторы) будут очень большими и должны храниться в разреженном формате.

Большое спасибо за любую помощь!

Примечание: я использую машину с 24 ГБ оперативной памяти и 8 процессорных ядер.

machine-learning Энсом Ходдер
источник
Насколько разреженной является матрица? Как вы используете полученный SVD? Если вам нужна только часть этого, вы, вероятно, можете приблизить его гораздо дешевле.
Арнольд Ноймайер
@ArnoldNeumaier Извините, я забыл добавить разреженную информацию. Я обновил пост вместе с моей полной идеей.
Энсом Ходдер
каждый из предложенных в ответах SLEPc, mahout и irlba пока кажется подходящим для вашей проблемы.
Арнольд Ноймайер
1
Почему вы хотите вычислить все 120 КБ? Похоже, вы просто хотите, чтобы те составляли 90% дисперсии, что должно быть намного дешевле для вычисления.
Джед Браун
@JedBrown Эй, Джед, ты совершенно прав! Меня интересуют только те, на кого приходится 90% дисперсии, а также соответствующие собственные векторы (для последующего преобразования тестового набора данных). Не могли бы вы дать мне знать ваши более дешевые методы ?
Ensom Hodder

Ответы:

4

Я предлагаю пакет irlba - он дает практически те же результаты, что и svd, но вы можете определить меньшее число особых значений, для которых нужно найти решение. Пример использования разреженных матриц для решения приза Netflix можно найти здесь: http://bigcomputing.blogspot.de/2011/05/bryan-lewiss-vignette-on-irlba-for-svd.html.

Марк в коробке
источник
Спасибо за ваши комментарии. Фактически, я смотрел это видео, а также вчера попробовал пакет irlba , но казалось, что его можно использовать только для вычисления нескольких единичных значений. Однако, как указано в сообщении, я хочу рассчитать ВСЕ единичные значения (120 000), чтобы выбрать подходящее количество компьютеров в соответствии с отклонениями, которые они учитывают. В этом случае, я думаю, irlba больше не подходит.
Ensom Hodder
Можете ли вы использовать результаты SVD аналогично PCA? Вам не нужно центрировать данные ДО выполнения SVD, чтобы выполнить PCA?
Зак
@Zach - SVD является основным алгоритмом PCA (см. Prcomp - stat.ethz.ch/R-manual/R-patched/library/stats/html/prcomp.html ). Центрирование данных также является стандартной процедурой, прежде чем подвергать PCA, хотя в зависимости от вашего вопроса есть множество вариантов (например, могут также применяться различные типы масштабирования).
Марк в коробке
Насколько велика сделка, если я не центрирую данные перед SVD? У меня есть разреженная матрица, которая помещается в память, но центрирование сделает ее плотной и слишком большой, чтобы поместиться в память.
Зак
@ Зак - Это действительно зависит от того, как вы хотите связать свои образцы друг с другом. Если вы не можете работать с центрированными данными из-за ограничений памяти, то, я думаю, решение за вас принято. Как правило, при центрировании данных PCA работает на ковариационной матрице выборок, а при центрировании и масштабировании данных PCA работает на корреляционной матрице. Для получения более подробной информации об этих решениях вы можете задать вопрос на stats.stackexchange.com или поискать существующие ответы, касающиеся PCA.
Марк в коробке
8

Я предлагаю использовать SLEPc для вычисления частичного SVD. Подробности см. В главе 4 Руководства пользователя и на страницах справки SVD .

Джед браун
источник
1
Так как он хочет PCA, он должен центрировать данные перед вычислением SVD. Это разрушит разреженность. Есть ли способ, которым SLEPc приспосабливается к этому?
dranxo
3
Это просто редкий + низкий ранг. SLEPc не нуждается в матричных элементах, только в линейном операторе, который может быть применен в качестве разреженной матрицы плюс коррекция.
Джед Браун
2

Я голосую за mahout, который также хорош для других задач НЛП / ТА и реализует карту / уменьшить.

danas.zuokas
источник
Да, вы правы, mahout точно в моей дорожной карте. Но я предпочитаю создавать прототип с некоторыми «простыми» (я полагаю) методами заранее.
Ensom Hodder
1

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

  • за техническими отчетами Матфея Брэнда 1 и 2 довольно легко следить
  • Магистерская диссертация Криса Бейкера , его программное обеспечение IncPACK и его более поздняя статья о методе инкрементального SVD
  • Связка и Nielsen опубликовала ранний известный документ
  • Документы Холла об обновлении задач на собственные значения 1 и 2
  • Последовательный анализ Кархунена-Лоэва, выполненный Леви и др., Который в основном совпадает

Все эти подходы сводятся к следующему:

  • начать с небольшого набора данных
  • рассчитать SVD как-то (этот шаг тривиален для матрицы с одним столбцом)
  • повторите до конца:
    • добавить новый набор данных
    • использовать существующие SVD и обновлять правила для расчета SVD нового набора данных

N

Джефф Оксберри
источник
0

Вы все еще можете использовать R.

Revolution Rэто сборка R, которая обрабатывает наборы данных, которые больше, чем RAM. Используйте функцию princomp.

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

Вы можете скачать полнофункциональную академическую версию бесплатно, поставив флажок «Я академик».

Контанго
источник