Tes untuk pemisahan linear

Apakah ada cara untuk menguji keterpisahan linear dari dataset dua kelas dalam dimensi tinggi? Vektor fitur saya panjangnya 40.

Saya tahu saya selalu dapat menjalankan percobaan regresi logistik dan menentukan hitrate vs false alarm rate untuk menyimpulkan apakah kedua kelas terpisah secara linear atau tidak, tetapi akan lebih baik untuk mengetahui apakah sudah ada prosedur standar untuk melakukan itu.

machine-learning classification Nik
sumber

lihat di sini:

user603

Ini berguna untuk merencanakan separabiity: x = titik kesalahan klasifikasi

normal-to-separating-plane, y = kerugian kumulatif (x). (Untuk plot contoh, coba pertanyaan baru dengan tag svm dan visualisasi data.)

\cdot

$\cdot$

denis

Bagaimana dengan 3 kelas masalah? Apakah semua masalah 3+ kelas bersifat non-linear?

Rosy

Jawaban:

Yah, mesin dukungan vektor (SVM) mungkin, apa yang Anda cari. Sebagai contoh, SVM dengan kernel RBF linier, fitur peta ke ruang dimensi yang lebih tinggi dan mencoba untuk memisahkan kelas dengan hyperplane linier. Ini adalah video SVM pendek yang bagus menggambarkan ide itu.

Anda dapat membungkus SVM dengan metode pencarian untuk pemilihan fitur (model pembungkus) dan mencoba untuk melihat apakah salah satu fitur Anda dapat secara linear memisahkan kelas yang Anda miliki.

Ada banyak alat menarik untuk menggunakan SVM termasuk LIBSVM , MSVMPack dan Scikit-learn SVM .

soufanom
sumber

+1. Hampir seolah-olah Nik menggambarkan SVM, tidak pernah mendengarnya. Dalam R, Anda bisa menggunakan (misterius bernama) e1071paket ini svmdengan kernel="linear"dan melihat prediksi dibandingkan yang sebenarnya.

Wayne

Saya tahu tentang SVM. Hanya saja saya tidak tahu saya bisa menggunakannya untuk menguji keterpisahan linear tanpa benar-benar mengklasifikasikan setiap sampel.

Nik

@Wayne: Nik sebenarnya tidak meminta SVM. Saya menjelaskan dalam jawaban saya mengapa ini bukan solusi untuk masalahnya.

Raffael

" Kernel RBF linear " tidak ada.

Marc Claesen

Tentu saja ! Yang dimaksud adalah kernel RBF yang memetakan data ke dalam ruang yang terpisah secara linear.

soufanom

Secara komputasi cara yang paling efektif untuk memutuskan apakah dua set titik dapat dipisahkan secara linear adalah dengan menerapkan pemrograman linier . GLTK sangat cocok untuk tujuan itu dan hampir setiap bahasa tingkat tinggi menawarkan antarmuka untuk itu - R , Python, Oktaf, Julia, dll.

Sehubungan dengan jawaban yang menyarankan penggunaan SVM :

Menggunakan SVM adalah solusi sub-optimal untuk memverifikasi keterpisahan linear karena dua alasan:

SVM adalah pengklasifikasi margin lunak. Itu berarti kernel linear SVM mungkin puas dengan pesawat pemisah yang tidak memisahkan sempurna meskipun itu mungkin benar-benar mungkin. Jika Anda kemudian memeriksa tingkat kesalahan itu tidak akan 0 dan Anda akan salah menyimpulkan bahwa dua set tidak dapat dipisahkan secara linear. Masalah ini dapat dilemahkan dengan memilih koefisien biaya C yang sangat tinggi - tetapi hal ini muncul dengan biaya komputasi yang sangat tinggi.
SVM adalah pengklasifikasi margin maksimum. Itu berarti algoritme akan berusaha menemukan bidang pemisah yang memisahkan kedua kelas sambil berusaha menjauhi keduanya sejauh mungkin. Sekali lagi ini adalah fitur yang meningkatkan upaya komputasi yang tidak perlu karena menghitung sesuatu yang tidak relevan untuk menjawab pertanyaan keterpisahan linear.

Katakanlah Anda memiliki satu set poin A dan B:

masukkan deskripsi gambar di sini

Maka Anda harus meminimalkan 0 untuk kondisi berikut:

(A di bawah ini adalah matriks, bukan set poin dari atas)

masukkan deskripsi gambar di sini

"Meminimalkan 0" secara efektif berarti Anda tidak perlu benar-benar mengoptimalkan fungsi objektif karena ini tidak perlu untuk mengetahui apakah set dapat dipisahkan secara linear.

Pada akhirnya ( masukkan deskripsi gambar di sini ) adalah mendefinisikan bidang yang memisahkan.

masukkan deskripsi gambar di sini

Jika Anda tertarik pada contoh kerja dalam R atau rincian matematika, lalu lihat ini .

Raffael
sumber

SVM adalah pengklasifikasi margin lunak ... kecuali bila Anda menggunakan SVM hard margin. Yang mengatakan, menggunakan SVM akan seperti menembak lalat dengan meriam.

Marc Claesen

itu benar - meskipun banyak (atau mungkin sebagian besar) perpustakaan SVM tidak menawarkan pilihan ini

Raffael

C

$C$

Linear Perceptron dijamin untuk menemukan solusi jika ada. Pendekatan ini tidak efisien untuk dimensi besar. Secara komputasi cara yang paling efektif untuk memutuskan apakah dua set titik terpisah secara linear adalah dengan menerapkan pemrograman linier seperti yang disebutkan oleh @Raffael.

Solusi cepat adalah menyelesaikan perceptron. Kode dengan contoh untuk dipecahkan menggunakan Perceptron di Matlab ada di sini

Rishi Dua
sumber