Анализ основных компонентов (PCA) на огромном разреженном наборе данных

У меня около 1000 векторов x_i размерности 50000, но они очень разреженные; каждый имеет только около 50-100 ненулевых элементов. Я хочу сделать PCA в этом наборе данных (в MATLAB), чтобы уменьшить ненужную чрезвычайную размерность данных.

К сожалению, я не знаю, как это сделать без промежуточной полной матрицы из-за необходимости вычитать средства из всех примеров. И, конечно же, матрица размером 1000x50000 слишком велика, чтобы вписаться в память (по какой-то причине, когда я пытаюсь ее повредить). Matlab, встроенный в princomp, разбивает мой компьютер, когда я пытаюсь его использовать.

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

Ответ 1

Вам не нужно формировать полную матрицу данных, чтобы вычесть средства, или вычислить матрицу ковариации. Просто вычислите матрицу ковариации 1000x1000 итеративно (проведите по векторам данных). Как только вы сформируете матрицу ковариации, вы можете неявно вычитать средства с помощью центрирования матрицы ковариации. См. Раздел в конце этой статьи на PCA ядра, объясняя, как центрировать матрицу ядра. Просто рассмотрим матрицу ядра в основном так же, как и ковариационную матрицу.

Ответ 2

Для вычисления PCA упомянутого набора данных алгоритм просто должен работать с матрицей ковариации 1000x1000. Полагаю, это не должно быть большой проблемой для большинства реализаций PCA. Если вы используете компьютер с Windows 7, вы можете попробовать использовать 64-битную реализацию СПС. Я не уверен, что Matlab поддерживает 64-битный PCA, но приложение, такое как VisuMap, может легко обрабатывать эти случаи.

Ответ 3

Работает следующая стратегия:

[~,~,PC] = svds(X,k);
mu = mean(X);
S = sparse(size(X,1),k);
for i=1:size(X,1)
    S(i,:) = (X(i,:)-mu)*PC;
end

Прямые сингулярные векторы X являются собственными векторами cov(X,1) и, следовательно, главными компонентами X. Вычисляя основные компоненты за один раз, а не сразу, вы можете избежать переполнения памяти, которые приходят с переходом от разреженного к полному. Просто не забудьте сделать k<<p, и все будет в порядке.

Ответ 4

Вам не нужно использовать princomp. Этот ответ объяснит, как вы это сделаете с помощью eig. Замените eig на eigs.

Ответ 5

Во-первых, вам не нужна матрица ковариации, чтобы вычесть среднее значение.

Затем, чтобы вычислить ПК, см. ответы на question.

Ответ 6

Для верхнего ПК см. итеративный PCA; это накапливает суммы в 50 тыс. плотных. 50 тыс. Разреженных, должны работать.
Для второго - вычесть первый на ходу, то есть использовать (X - U1 d1 Vt1) без создания экземпляра. (Randomized PCA делает это в Python scikit-learn, Matlab dunno.)