Bagaimana cara melakukan SVD dan PCA dengan data besar?

Saya memiliki sejumlah besar data (sekitar 8GB). Saya ingin menggunakan pembelajaran mesin untuk menganalisisnya. Jadi, saya pikir saya harus menggunakan SVD kemudian PCA untuk mengurangi dimensi data untuk efisiensi. Namun, MATLAB dan Oktaf tidak dapat memuat set data besar tersebut.

Alat apa yang dapat saya gunakan untuk melakukan SVD dengan data dalam jumlah besar?

Pertama-tama, pengurangan dimensi digunakan ketika Anda memiliki banyak dimensi covariated dan ingin mengurangi ukuran masalah dengan memutar titik data menjadi basis ortogonal baru dan hanya mengambil sumbu dengan varian terbesar. Dengan 8 variabel (kolom), ruang Anda sudah berdimensi rendah, mengurangi jumlah variabel lebih lanjut tidak mungkin menyelesaikan masalah teknis dengan ukuran memori, tetapi mungkin banyak mempengaruhi kualitas dataset. Dalam kasus nyata Anda, lebih menjanjikan untuk melihat pembelajaran onlinemetode. Secara kasar, alih-alih bekerja dengan seluruh dataset, metode ini mengambil sebagian kecil dari mereka (sering disebut sebagai "mini-batch") sekaligus dan membangun model secara bertahap. (Saya pribadi suka mengartikan kata "online" sebagai referensi ke beberapa sumber data yang sangat panjang dari Internet seperti umpan Twitter, di mana Anda tidak dapat memuat seluruh dataset sekaligus).

Tetapi bagaimana jika Anda benar-benar ingin menerapkan teknik pengurangan dimensionalitas seperti PCA ke dataset yang tidak sesuai dengan memori? Biasanya dataset disajikan sebagai matriks data X ukuran n x m , di mana n adalah jumlah pengamatan (baris) dan m adalah sejumlah variabel (kolom). Biasanya masalah dengan memori hanya berasal dari salah satu dari dua angka ini.

Terlalu banyak pengamatan (n >> m)

Ketika Anda memiliki terlalu banyak pengamatan , tetapi jumlah variabel dari kecil hingga sedang, Anda dapat membuat matriks kovarians secara bertahap . Memang, PCA khas terdiri dari membangun matriks kovarians ukuran m x m dan menerapkan dekomposisi nilai singular untuk itu. Dengan m = 1000 variabel tipe float64, matriks kovarians memiliki ukuran 1000 * 1000 * 8 ~ 8Mb, yang mudah masuk ke dalam memori dan dapat digunakan dengan SVD. Jadi, Anda hanya perlu membangun matriks kovarians tanpa memuat seluruh dataset ke dalam memori - tugas yang cukup mudah dikerjakan .

Atau, Anda dapat memilih sampel representatif kecil dari dataset Anda dan memperkirakan matriks kovarians . Matriks ini akan memiliki semua properti yang sama seperti normal, hanya sedikit kurang akurat.

Terlalu banyak variabel (n << m)

Di sisi lain, kadang-kadang, ketika Anda memiliki terlalu banyak variabel , matriks kovarians itu sendiri tidak akan masuk ke dalam memori. Misalnya jika Anda bekerja dengan gambar 640x480, setiap pengamatan memiliki 640 * 480 = 307200 variabel, yang menghasilkan matriks kovarians 703Gb! Jelas bukan itu yang ingin Anda simpan di memori komputer Anda, atau bahkan di memori cluster Anda. Jadi kita perlu mengurangi dimensi tanpa membangun matriks kovarians sama sekali.

Metode favorit saya untuk melakukannya adalah Proyeksi Acak . Singkatnya, jika Anda memiliki dataset X ukuran n x m , Anda dapat mengalikannya dengan beberapa matriks acak R yang jarang berukuran m x k (dengan k << m ) dan mendapatkan matriks X baru dari ukuran yang jauh lebih kecil n x k dengan kira-kira properti yang sama seperti yang asli. Mengapa ini berhasil? Nah, Anda harus tahu bahwa PCA bertujuan untuk menemukan set sumbu ortogonal (komponen utama) dan memproyeksikan data Anda ke pertama kdari mereka. Ternyata vektor acak jarang hampir ortogonal dan dengan demikian juga dapat digunakan sebagai dasar baru.

Dan, tentu saja, Anda tidak perlu melipatgandakan seluruh dataset X dengan R - Anda dapat menerjemahkan setiap observasi x menjadi basis baru secara terpisah atau dalam mini-batch.

Ada juga algoritma yang agak mirip disebut Random SVD . Saya tidak punya pengalaman nyata dengan itu, tetapi Anda dapat menemukan kode contoh dengan penjelasan di sini .

Sebagai garis bawah, inilah daftar periksa singkat untuk pengurangan dimensionalitas dataset besar:

1. Jika Anda belum memiliki banyak dimensi (variabel), cukup gunakan algoritma pembelajaran online.
2. Jika ada banyak pengamatan, tetapi sejumlah moderat variabel (matriks kovarians cocok dengan memori), buat matriks secara bertahap dan gunakan SVD normal.
3. Jika jumlah variabel terlalu tinggi, gunakan algoritma tambahan.

Jangan repot-repot.

Aturan pemrograman pertama - yang juga berlaku untuk ilmu data: membuat semuanya bekerja pada masalah tes kecil.

jadi ambil sampel acak data Anda dari katakanlah 100.000 baris. coba berbagai algoritme, dll. begitu semuanya berhasil sesuai keinginan Anda, Anda dapat mencoba kumpulan data yang lebih besar (dan lebih besar) - dan melihat bagaimana kesalahan pengujian berkurang saat Anda menambahkan lebih banyak data.

Selanjutnya Anda tidak ingin menerapkan svd hanya 8 kolom: Anda menerapkannya ketika Anda memiliki banyak kolom.

PCA biasanya diimplementasikan dengan menghitung SVD pada matriks kovarians.

Mengomputasi matriks kovarians adalah tugas paralel yang memalukan , sehingga ia menskala linier dengan jumlah catatan, dan sepele untuk didistribusikan pada banyak mesin!

Cukup lakukan satu melewati data Anda untuk menghitung sarana. Kemudian lulus kedua untuk menghitung matriks kovarians. Ini dapat dilakukan dengan pengurangan peta dengan mudah - pada dasarnya itu sama dengan menghitung sarana lagi. Jumlah istilah seperti dalam kovarian sepele untuk diparalelkan! Anda mungkin hanya perlu memperhatikan angka ketika menjumlahkan banyak nilai dengan skala yang sama.

Keadaan menjadi berbeda ketika Anda memiliki sejumlah besar variabel . Tetapi pada sistem 8 GB, Anda harus dapat menjalankan PCA pada memori hingga 20.000 dimensi dengan perpustakaan BLAS. Tetapi kemudian Anda mungkin mengalami masalah bahwa PCA tidak lagi dapat diandalkan lagi, karena PCA memiliki tingkat kebebasan yang terlalu banyak. Dengan kata lain: itu cocok dengan mudah. Saya telah melihat rekomendasi memiliki setidaknya 10 * d * d catatan (atau apakah itu d ^ 3). Jadi untuk 10.000 dimensi, Anda harus memiliki setidaknya satu miliar catatan (dari 10.000 dimensi ... itu banyak!) Agar hasilnya dapat diandalkan secara statistik.

Meskipun Anda mungkin dapat menemukan beberapa alat yang akan memungkinkan Anda melakukannya pada satu mesin, Anda masuk ke kisaran di mana masuk akal untuk mempertimbangkan alat "data besar" seperti Spark, terutama jika Anda berpikir kumpulan data Anda mungkin tumbuh. Spark memiliki komponen yang disebut MLlib yang mendukung PCA dan SVD. Dokumentasi memiliki contoh .

Kami menerapkan SVD ke kumpulan data yang lebih besar menggunakan PySpark. Kami juga membandingkan konsistensi di berbagai paket. Inilah tautannya.

Saya akan merekomendasikan python jika Anda malas mengevaluasi file Anda akan memiliki jejak memori sangat kecil, dan numpy / scipy memberi Anda akses ke semua alat yang Octave / Matlab akan lakukan.