Memecahkan sistem persamaan dengan data jarang

11

Saya mencoba menyelesaikan serangkaian persamaan yang memiliki 40 variabel independen (x1, ..., x40) dan satu variabel dependen (y). Jumlah total persamaan (jumlah baris) adalah ~ 300, dan saya ingin menyelesaikan set 40 koefisien yang meminimalkan total jumlah kesalahan kuadrat antara y dan nilai prediksi.

Masalah saya adalah bahwa matriks sangat jarang dan saya tidak tahu cara terbaik untuk menyelesaikan sistem persamaan dengan data jarang. Contoh dataset ditunjukkan di bawah ini:

   y    x1  x2 x3 x4 x5 x6 ... x40
87169   14  0  1  0  0  2  ... 0 
46449   0   0  4  0  1  4  ... 12
846449  0   0  0  0  0  3  ... 0
....

Saat ini saya menggunakan Algoritma Genetika untuk menyelesaikan ini dan hasilnya keluar dengan faktor sekitar dua perbedaan antara yang diamati dan yang diharapkan.

Adakah yang bisa menyarankan metode atau teknik yang berbeda yang mampu memecahkan satu set persamaan dengan data jarang.

machine-learning regression algorithms genetic mike1886
sumber
2
Mengetik dalam judul: spare => jarang.
Aleksandr Blekh

Jawaban:

11

Jika saya mengerti Anda dengan benar, ini adalah kasus regresi linier berganda dengan data jarang ( regresi jarang ). Dengan asumsi itu, saya harap Anda akan menemukan sumber daya berikut bermanfaat.

1) slide kuliah NCSU tentang regresi sparse dengan ikhtisar algoritma, catatan, formula, grafik, dan referensi literatur: http://www.stat.ncsu.edu/people/zhou/courses/st810/notes/lect23sparse.pdf

2) Rekosistem menawarkan banyak paket , berguna untuk analisis regresi yang jarang, termasuk:

3) Posting blog dengan contoh solusi regresi sparse , berdasarkan SparseM: http://aleph-nought.blogspot.com/2012/03/multiple-linear-regress-with-sparse.html

4) Posting blog tentang menggunakan matriks jarang dalam R , yang mencakup primer tentang penggunaan glmnet: http://www.johnmyleswhite.com/notebook/2011/10/10/31/using-sparse-matrices-in-r

5) Lebih banyak contoh dan beberapa diskusi mengenai topik tersebut dapat ditemukan di StackOverflow : /programming/3169371/large-scale-regress-in-r-with-a-sparse-feature-matrix

UPDATE (berdasarkan komentar Anda):

Jika Anda mencoba untuk memecahkan masalah LP dengan kendala, Anda mungkin menemukan makalah teoretis ini berguna: http://web.stanford.edu/group/SOL/papers/gmsw84.pdf .

Juga, periksa limSolve paket R : http://cran.r-project.org/web/packages/limSolve . Dan, secara umum, periksa paket di CRAN Task View "Optimasi dan Pemrograman Matematika" : http://cran.r-project.org/web/views/Optimization.html .

Akhirnya, periksa buku "Menggunakan R untuk Analisis Numerik dalam Sains dan Teknik" (oleh Victor A. Bloomfield). Ini memiliki bagian tentang penyelesaian sistem persamaan, diwakili oleh matriks jarang (bagian 5.7, halaman 99-104), yang mencakup contoh-contoh, berdasarkan pada beberapa paket yang disebutkan di atas: http://books.google.com/books? id = 9ph_AwAAQBAJ & pg = PA99 & lpg = PA99 & dq = r + limsolve + jarang + matrix & source = bl & ots = PHDE8nXljQ & sig = sPi4n5Wk0M02ywkubq7R7KD_b04 & hl = id & sa = X & ei = FZjiU-ioIcjmsATGkYDAAg & ved = 0CDUQ6AEwAw # v = onepage & q = r% 20limsolve% 20sparse% 20matrix & f = false .

Aleksandr Blekh
sumber
3
Terima kasih atas jawaban yang bagus! Saya ragu-ragu untuk mengklasifikasikan masalah ini sebagai regresi yang jarang karena saya tidak benar-benar mencoba untuk memodelkan dan memprediksi tetapi lebih tepatnya memecahkan satu set koefisien. Alasan saya menggunakan Algoritma Genetika adalah karena saya juga dapat menggunakan batasan pada persamaan. Jika tidak ada jawaban lain yang datang saya akan dengan senang hati menerima ini.
mike1886
1
@ mike1886: Dengan senang hati! Saya telah memperbarui jawaban saya, berdasarkan komentar Anda. Semoga ini bisa membantu.
Aleksandr Blekh
7

Jawaban Aleksandr sepenuhnya benar.

Namun, cara mengajukan pertanyaan menyiratkan bahwa ini adalah pertanyaan regresi kuadrat biasa sederhana: meminimalkan jumlah residu kuadrat antara variabel dependen dan kombinasi linear dari prediktor.

Sekarang, sementara mungkin ada banyak nol dalam matriks desain Anda, sistem Anda dengan demikian tidak terlalu besar: 300 pengamatan pada 40 prediktor tidak lebih dari ukuran sedang. Anda dapat menjalankan regresi seperti itu menggunakan R tanpa ada upaya khusus untuk data yang jarang. Cukup gunakan lm()perintah (untuk "model linier"). Gunakan ?lmuntuk melihat halaman bantuan. Dan perhatikan bahwa lmsecara default akan diam-diam menambahkan kolom yang konstan ke matriks desain Anda (intersep) - termasuk a -1di sisi kanan rumus Anda untuk menekan ini. Secara keseluruhan, dengan asumsi semua data Anda (dan tidak ada yang lain) dalam keadaan data.frameterpanggil foo, Anda dapat melakukan ini:

model <- lm(y~.-1,data=foo)

Dan kemudian Anda dapat melihat estimasi parameter dll seperti ini:

summary(model)
residuals(model)

Jika sistem Anda jauh lebih besar, katakanlah pada urutan 10.000 pengamatan dan ratusan prediktor, melihat pemecah jarang seperti jawaban Aleksandr mungkin mulai masuk akal.

Akhirnya, dalam komentar Anda untuk jawaban Aleksandr , Anda menyebutkan kendala pada persamaan Anda. Jika itu sebenarnya masalah utama Anda, ada cara untuk menghitung kuadrat terkecil yang dibatasi dalam R. Saya pribadi suka pcls()dalam mgcvpaket. Mungkin Anda ingin mengedit pertanyaan Anda untuk memasukkan jenis kendala (kendala kotak, kendala nonnegativitas, kendala integral, kendala linier, ...) yang Anda hadapi?

Stephan Kolassa
sumber
1
Stephan, aku menghargai kata-kata baikmu! Putuskan jawaban Anda yang bagus. Anda mungkin tertarik dengan pembaruan yang saya buat untuk jawaban saya, berdasarkan komentar dari penulis pertanyaan.
Aleksandr Blekh