Apakah PCA skala besar bahkan mungkin?

10

Cara klasik analisis komponen utama '(PCA) adalah untuk melakukannya pada input data matriks yang kolom memiliki rata-rata nol (maka PCA dapat "memaksimalkan varians"). Ini dapat dicapai dengan mudah dengan memusatkan kolom. Namun, ketika matriks input jarang, matriks tengah sekarang akan lebih jarang, dan - jika matriks sangat besar - dengan demikian tidak akan masuk ke dalam memori lagi. Apakah ada solusi algoritmik untuk masalah penyimpanan?

pca algorithms dimensionality-reduction large-data sparse Roy
sumber
5
Sekalipun matriks data lengkap tidak cocok dengan memori, bisa jadi kovarians atau matriks Gram cocok dengan memori. Itu sudah cukup untuk melakukan PCA. Apa ukuran matriks data input yang Anda pikirkan? Lihat juga stats.stackexchange.com/questions/35185 .
amoeba
1
@amoeba: Saya melihat sampel 500K (baris) dan 300 ribu fitur (kolom)
Roy
Mengenai perangkat lunak, Apache Spark memilikinya spark.apache.org/docs/latest/… untuk memastikan implementasi berkaitan dengan data di luar memori
Tim

Jawaban:

11

Ya itu mungkin.

Jika matriks data tidak sesuai dengan RAM, itu belum akhir dunia: ada algoritma yang efisien yang dapat bekerja dengan data yang disimpan di hard drive. Lihat misalnya PCA acak seperti yang dijelaskan dalam Halko et al., 2010, Suatu algoritma untuk analisis komponen utama dari kumpulan data besar .

Dalam Bagian 6.2 penulis menyebutkan bahwa mereka mencoba algoritme mereka pada 400k kali 100k matriks data dan itu

Algoritma dari makalah ini membutuhkan 12,3 jam untuk memproses semua 150 GB dari set data yang disimpan dalam disk, menggunakan komputer laptop dengan 1,5 GB RAM [...].

Perhatikan bahwa ini adalah di masa lalu dari hard drive magnetik; hari ini ada solid state drive yang jauh lebih cepat, jadi saya kira algoritma yang sama akan bekerja jauh lebih cepat.

Lihat juga utas lama ini untuk diskusi lebih lanjut tentang PCA acak: Algoritma PCA terbaik untuk sejumlah besar fitur (> 10K)? dan ulasan besar 2011 ini oleh Halko et al .: Menemukan Struktur dengan Keacakan: Algoritma Probabilistik untuk Membangun Dekomposisi Matriks Perkiraan .

amuba
sumber