Ранее я спрашивал об этом в StackOverflow, но кажется, что это может быть более уместным, учитывая, что он не получил никаких ответов по SO. Это своего рода на пересечении статистики и программирования.
Мне нужно написать код для PCA (Анализ основных компонентов). Я просмотрел известные алгоритмы и реализовал этот , который, насколько я могу судить, эквивалентен алгоритму NIPALS. Он хорошо работает для нахождения первых 2-3 главных компонентов, но затем кажется, что они очень медленно сходятся (порядка сотен и тысяч итераций). Вот детали того, что мне нужно:
Алгоритм должен быть эффективен при работе с огромным количеством функций (порядка 10 000–20 000) и размерами выборки порядка нескольких сотен.
Он должен быть разумно реализуемым без приличной библиотеки линейной алгебры / матрицы, поскольку целевым языком является D, у которого его еще нет, и даже если бы он был, я бы предпочел не добавлять его в качестве зависимости к рассматриваемому проекту. ,
Как примечание: в одном и том же наборе данных R, кажется, находит все основные компоненты очень быстро, но использует разложение по сингулярным значениям, которое я не хочу сам кодировать.
Ответы:
Я реализовал рандомизированный SVD, как указано в "Halko, N., Martinsson, PG, Shkolnisky, Y. & Tygert, M. (2010). Алгоритм анализа главных компонентов больших наборов данных. Препринт Arxiv arXiv: 1007.5510, 0526. Получено 1 апреля 2011 г. с сайта http://arxiv.org/abs/1007.5510 . " Если вы хотите получить усеченный SVD, он действительно работает намного быстрее, чем svd-варианты в MATLAB. Вы можете получить его здесь:
Чтобы проверить это, просто создайте изображение в той же папке (как большая матрица, вы можете создать матрицу самостоятельно)
Когда я запускаю его на своем рабочем столе для изображения размером 635 * 483, я получаю
Как видите, при низких значениях
k
это более чем в 10 раз быстрее, чем при использовании Matlab SVD. Кстати, вам может понадобиться следующая простая функция для тестовой функции:Я не добавил метод PCA, поскольку его легко реализовать с использованием SVD. Вы можете проверить эту ссылку, чтобы увидеть их отношения.
источник
Вы могли бы попытаться использовать несколько вариантов.
1- штрафная матричная декомпозиция . Вы применяете некоторые штрафные ограничения к вам и v, чтобы получить некоторую разреженность. Быстрый алгоритм, который был использован на данных геномики
Смотрите Уиттен Тибширани. У них также есть R-pkg. «Наказанная матричная декомпозиция с приложениями для разреженных главных компонентов и канонического корреляционного анализа».
2- Рандомизированная СВД . Поскольку SVD является основным алгоритмом, может быть желательно найти очень быстрое приближение, особенно для исследовательского анализа. Используя рандомизированный SVD, вы можете делать PCA на огромных наборах данных.
См. Martinsson, Rokhlin, Tygert "Рандомизированный алгоритм разложения матриц". У Тигерта есть код для очень быстрой реализации PCA.
Ниже приведена простая реализация рандомизированного СВД в R.
источник
Похоже, вы хотите использовать алгоритм Ланцоша . Если это не удастся, вы можете проконсультироваться с Голубом и Ван Лоаном. Однажды я написал код SVD (в SML всех языков) из их текста, и он работал достаточно хорошо.
источник
Я бы предложил попробовать ядро PCA, которое имеет временную / пространственную сложность, зависящую от количества примеров (N), а не от числа функций (P), что, я думаю, будет более подходящим в ваших настройках (P >> N)). Ядро PCA в основном работает с матрицей ядра NxN (матрицей сходства между точками данных), а не с ковариационной матрицей PxP, с которой может быть трудно иметь дело для больших P. Еще одна хорошая вещь в ядре PCA заключается в том, что он может изучать нелинейные проекции а также если вы используете его с подходящим ядром. Смотрите эту статью о ядре PCA .
источник
Кажется, я вспоминаю, что можно выполнить PCA путем вычисления собственного разложения X ^ TX, а не XX ^ T, а затем преобразовать, чтобы получить ПК. Однако я не могу вспомнить подробности, но это в (превосходной) книге Джоллиффа, и я посмотрю ее, когда буду рядом на работе. Я бы транслитерал подпрограммы линейной алгебры, например, из численных методов в C, а не использовал бы любой другой алгоритм.
источник
Существует также метод начальной загрузки Фишера и др. , Разработанный для нескольких сотен образцов высокой размерности.
Основная идея метода сформулирована как «повторная выборка - преобразование низкой размерности». Таким образом, если у вас есть небольшое (несколько сотен) количество высокоразмерных выборок, то вы не можете получить больше основных компонентов, чем количество ваших выборок. Таким образом, имеет смысл рассматривать выборки как экономную основу, проецировать данные на линейное подпространство, охватываемое этими векторами, и вычислять PCA в этом меньшем подпространстве. Они также предоставляют более подробную информацию о том, как справиться со случаем, когда не все образцы могут быть сохранены в памяти.
источник
См. Статью Сэма Роуиса « Алгоритмы EM для PCA и SPCA» .
источник