Support Vector Machines di R

Dalam machine learning, support vector machines adalah model pembelajaran terawasi dengan algoritma terkait yang menganalisis data untuk klasifikasi dan regresi. Namun, SVM paling sering digunakan untuk masalah klasifikasi. Dalam tutorial ini, kita akan mencoba memahami secara tingkat tinggi cara kerja SVM lalu mengimplementasikannya dengan R. Saya akan fokus membangun intuisi alih-alih ketelitian matematis. Artinya, kita akan melewati sebanyak mungkin bagian matematika dan membangun intuisi yang kuat tentang prinsip kerjanya.

Algoritma Support Vector Machines

Data Linear

Dasar-dasar Support Vector Machines dan cara kerjanya paling mudah dipahami dengan contoh sederhana. Bayangkan kita memiliki dua label: merah dan biru, dan data kita memiliki dua fitur: x dan y. Kita menginginkan sebuah pengklasifikasi yang, diberikan pasangan koordinat (x,y), menghasilkan apakah itu merah atau biru. Kita plot data pelatihan yang sudah diberi label pada bidang:

Sebuah support vector machine mengambil titik-titik data ini dan menghasilkan hyperplane (yang dalam dua dimensi hanyalah garis) yang memisahkan label sebaik mungkin. Garis ini adalah batas keputusan: apa pun yang jatuh di satu sisi akan kita klasifikasikan sebagai biru, dan yang jatuh di sisi lain sebagai merah.

Lalu, apa sebenarnya hyperplane terbaik? Bagi SVM, hyperplane terbaik adalah yang memaksimalkan margin dari kedua label. Dengan kata lain: hyperplane (ingat, dalam kasus ini adalah garis) yang jaraknya terhadap elemen terdekat dari masing-masing label paling besar.

Data Non-Linear

Contoh di atas mudah karena jelas datanya terpisah secara linear — kita bisa menggambar garis lurus untuk memisahkan merah dan biru. Sayangnya, biasanya tidak sesederhana itu. Perhatikan kasus berikut:

Cukup jelas bahwa tidak ada batas keputusan linear (satu garis lurus yang memisahkan kedua label). Namun, vektor-vektornya sangat terpisah dengan jelas, dan tampak seolah-olah seharusnya mudah untuk memisahkannya.

Jadi begini yang akan kita lakukan: kita akan menambah dimensi ketiga. Sejauh ini, kita memiliki dua dimensi: $x$ dan $y$. Kita membuat dimensi z baru, dan kita tetapkan ia dihitung dengan cara tertentu yang menguntungkan kita: $z = x² + y²$ (Anda akan menyadari bahwa ini adalah persamaan lingkaran).

Ini akan memberi kita ruang tiga dimensi. Jika kita mengambil irisan ruang itu, tampilannya seperti ini:

Apa yang bisa SVM lakukan dengan ini? Mari kita lihat:

Bagus! Perhatikan bahwa karena sekarang kita berada dalam tiga dimensi, hyperplane adalah sebuah bidang yang sejajar dengan sumbu $x$ pada nilai $z$ tertentu (misalnya $z = 1$).

Yang tersisa adalah memetakannya kembali ke dua dimensi:

Dan selesai! Batas keputusan kita adalah keliling lingkaran berjari-jari 1, yang memisahkan kedua label menggunakan SVM.

Kernel Trick

Pada contoh di atas, kita menemukan cara mengklasifikasikan data non-linear dengan cerdik memetakan ruang kita ke dimensi yang lebih tinggi. Namun, ternyata menghitung transformasi ini bisa sangat mahal secara komputasional: bisa ada banyak dimensi baru, masing-masing mungkin melibatkan perhitungan yang rumit. Melakukan ini untuk setiap vektor dalam dataset bisa memakan banyak kerja, jadi akan bagus jika kita dapat menemukan solusi yang lebih murah.

Ini triknya: SVM tidak membutuhkan vektor aktual untuk bekerja, melainkan hanya membutuhkan hasil kali titik (dot product) antar vektor. Ini berarti kita dapat menghindari perhitungan mahal dari dimensi-dimensi baru! Berikut yang kita lakukan sebagai gantinya:

• Bayangkan ruang baru yang kita inginkan:

• Tentukan seperti apa dot product di ruang tersebut:

• Perintahkan SVM untuk menjalankan tugasnya, tetapi menggunakan dot product baru — kita menyebutnya fungsi kernel.

Ini dikenal sebagai kernel trick, yang memperluas ruang fitur untuk mengakomodasi batas non-linear antar kelas. Jenis kernel umum yang digunakan untuk memisahkan data non-linear adalah kernel polinomial, kernel radial basis, dan kernel linear (yang sama dengan support vector classifier). Sederhananya, kernel-kernel ini mentransformasikan data kita agar sebuah hyperplane linear dapat dilewatkan sehingga data kita dapat diklasifikasikan.

Kelebihan dan Kekurangan

Sekarang mari kita lihat beberapa kelebihan dan kekurangan SVM:

Kelebihan

• Dimensionalitas Tinggi: SVM efektif di ruang berdimensi tinggi, yang sangat relevan untuk klasifikasi dokumen dan analisis sentimen di mana dimensionalitas bisa sangat besar.

• Efisiensi Memori: Karena hanya sebagian dari titik pelatihan yang digunakan dalam proses pengambilan keputusan saat menetapkan anggota baru, hanya titik-titik ini yang perlu disimpan di memori (dan dihitung) ketika membuat keputusan.

• Fleksibilitas: Pemisahan kelas sering kali sangat non-linear. Kemampuan menerapkan kernel baru memberikan fleksibilitas besar pada batas keputusan, sehingga meningkatkan kinerja klasifikasi.

Kekurangan

• Pemilihan Parameter Kernel: SVM sangat sensitif terhadap pemilihan parameter kernel. Dalam situasi di mana jumlah fitur untuk setiap objek melebihi jumlah sampel data pelatihan, SVM dapat berkinerja buruk. Secara intuitif, ini terjadi ketika ruang fitur berdimensi tinggi jauh lebih besar daripada jumlah sampel. Maka jumlah support vector yang efektif menjadi lebih sedikit untuk menopang hyperplane linear yang optimal, sehingga kinerja klasifikasi menurun saat sampel baru yang belum terlihat ditambahkan.

• Tidak Probabilistik: Karena pengklasifikasi bekerja dengan menempatkan objek di atas dan di bawah sebuah hyperplane pengklasifikasi, tidak ada interpretasi probabilistik langsung untuk keanggotaan grup. Namun, salah satu metrik potensial untuk menentukan "keefektifan" klasifikasi adalah seberapa jauh titik baru tersebut dari batas keputusan.

Support Vector Machines di R

Klasifikator SVM Linear

Pertama, mari kita buat beberapa data dalam 2 dimensi, dan buat agak terpisah. Setelah menetapkan random seed, Anda membuat matriks x, terdistribusi normal dengan 20 observasi dalam 2 kelas pada 2 variabel. Lalu Anda membuat variabel y, yang akan bernilai -1 atau 1, dengan 10 di setiap kelas. Untuk y = 1, Anda menggeser mean dari 0 menjadi 1 pada masing-masing koordinat. Terakhir, Anda dapat memplot data dan memberi kode warna pada titik sesuai responsnya. Karakter plotting 19 memberi Anda titik besar yang terlihat jelas berkode biru atau merah sesuai apakah responsnya 1 atau -1.

set.seed(10111)
x = matrix(rnorm(40), 20, 2)
y = rep(c(-1, 1), c(10, 10))
x[y == 1,] = x[y == 1,] + 1
plot(x, col = y + 3, pch = 19)Didukung oleh

Sekarang muat paket e1071 yang berisi fungsi svm (ingat untuk memasang paketnya jika Anda belum melakukannya).

library(e1071)Didukung oleh

Sekarang Anda membuat sebuah dataframe dari data, mengubah y menjadi variabel faktor. Setelah itu, Anda memanggil svm pada dataframe ini, menggunakan y sebagai variabel respons dan variabel lainnya sebagai prediktor. Dataframe akan membongkar matriks x menjadi 2 kolom bernama x1 dan x2. Anda memberi tahu SVM bahwa kernel-nya linear, parameter penyetelan cost adalah 10, dan scale sama dengan false. Dalam contoh ini, Anda memintanya untuk tidak menstandarkan variabel.

dat = data.frame(x, y = as.factor(y))
svmfit = svm(y ~ ., data = dat, kernel = "linear", cost = 10, scale = FALSE)
print(svmfit)Didukung oleh

Mencetak svmfit akan menampilkan ringkasannya. Anda dapat melihat bahwa jumlah support vector adalah 6 — yaitu titik-titik yang dekat dengan batas atau berada di sisi batas yang salah.

Ada fungsi plot untuk SVM yang menampilkan batas keputusan, seperti yang Anda lihat di bawah. Tampaknya tidak banyak kendali atas warnanya. Ini tidak lazim karena menempatkan x2 pada sumbu horizontal dan x1 pada sumbu vertikal.

plot(svmfit, dat)Didukung oleh

Mari coba buat plot Anda sendiri. Hal pertama yang dilakukan adalah membuat kisi nilai atau lattice untuk x1 dan x2 yang mencakup seluruh domain pada lattice yang cukup rapat. Untuk melakukannya, Anda membuat fungsi bernama make.grid. Fungsi ini menerima matriks data x, serta argumen n yaitu jumlah titik di setiap arah. Di sini Anda akan meminta kisi 75 x 75.

Di dalam fungsi ini, Anda menggunakan apply function untuk mendapatkan rentang setiap variabel dalam x. Lalu untuk x1 dan x2, Anda menggunakan fungsi seq untuk berjalan dari nilai terendah ke nilai tertinggi guna membuat kisi sepanjang n. Saat ini, Anda memiliki x1 dan x2, masing-masing dengan 75 nilai berjarak seragam pada tiap koordinat. Terakhir, Anda menggunakan fungsi expand.grid, yang mengambil x1 dan x2 dan membentuk lattice.

make.grid = function(x, n = 75) {
  grange = apply(x, 2, range)
  x1 = seq(from = grange[1,1], to = grange[2,1], length = n)
  x2 = seq(from = grange[1,2], to = grange[2,2], length = n)
  expand.grid(X1 = x1, X2 = x2)
}Didukung oleh

Sekarang Anda dapat menerapkan fungsi make.grid pada x. Mari lihat beberapa nilai awal lattice dari 1 sampai 10.

xgrid = make.grid(x)
xgrid[1:10,]Didukung oleh

Seperti yang terlihat, kisi berjalan melalui koordinat pertama terlebih dahulu, sambil menahan koordinat kedua tetap.

Setelah membuat lattice, Anda akan membuat prediksi di setiap titik pada lattice. Dengan data baru xgrid, Anda menggunakan predict dan menamai respons ygrid. Lalu Anda memplot dan memberi kode warna pada titik sesuai klasifikasinya sehingga batas keputusan terlihat jelas. Mari juga letakkan titik-titik asli pada plot ini menggunakan fungsi points.

svmfit memiliki komponen bernama index yang memberi tahu mana saja titik support. Anda sertakan titik-titik tersebut pada plot dengan menggunakan fungsi points lagi.

ygrid = predict(svmfit, xgrid)
plot(xgrid, col = c("red","blue")[as.numeric(ygrid)], pch = 20, cex = .2)
points(x, col = y + 3, pch = 19)
points(x[svmfit$index,], pch = 5, cex = 2)Didukung oleh

Seperti yang terlihat pada plot, titik-titik dalam kotak berada dekat batas keputusan dan berperan penting dalam menentukan batas tersebut.

Sayangnya, fungsi svm tidak terlalu ramah, karena Anda harus melakukan sedikit usaha untuk mendapatkan kembali koefisien linear. Alasannya mungkin karena ini hanya masuk akal untuk kernel linear, sementara fungsinya lebih umum. Jadi mari gunakan rumus untuk mengekstrak koefisien dengan lebih efisien. Anda mengekstrak beta dan beta0, yaitu koefisien linear.

beta = drop(t(svmfit$coefs)%*%x[svmfit$index,])
beta0 = svmfit$rhoDidukung oleh

Sekarang Anda bisa memplot ulang titik-titik pada kisi, lalu menambahkan kembali titik-titiknya (termasuk titik support vector). Kemudian Anda dapat menggunakan koefisien untuk menggambar batas keputusan menggunakan persamaan sederhana berbentuk:

Dari persamaan tersebut, Anda harus menentukan kemiringan dan intersep untuk batas keputusan. Lalu Anda bisa menggunakan fungsi abline dengan dua argumen tersebut. Dua pemanggilan abline berikutnya merepresentasikan margin atas dan margin bawah dari batas keputusan, masing-masing.

plot(xgrid, col = c("red", "blue")[as.numeric(ygrid)], pch = 20, cex = .2)
points(x, col = y + 3, pch = 19)
points(x[svmfit$index,], pch = 5, cex = 2)
abline(beta0 / beta[2], -beta[1] / beta[2])
abline((beta0 - 1) / beta[2], -beta[1] / beta[2], lty = 2)
abline((beta0 + 1) / beta[2], -beta[1] / beta[2], lty = 2)Didukung oleh

Anda dapat melihat dengan jelas bahwa beberapa titik support tepat berada di margin, sementara sebagian lainnya berada di dalam margin.

Klasifikator SVM Non-Linear

Itu tadi SVM linear pada bagian sebelumnya. Sekarang mari beralih ke versi non-linear dari SVM. Anda akan melihat contoh dari buku Elements of Statistical Learning, yang memiliki contoh kanonik dalam 2 dimensi di mana batas keputusannya non-linear. Anda akan menggunakan kernel support vector machine untuk mencoba mempelajari batas tersebut.

Pertama, Anda mengambil data untuk contoh itu dari buku dengan mengunduhnya langsung dari URL ini, yaitu laman tempat data berada. Datanya merupakan campuran dan hasil simulasi. Lalu Anda dapat memeriksa nama kolomnya.

load(file = "ESL.mixture.rda")
names(ESL.mixture)Didukung oleh

Untuk saat ini, data pelatihannya adalah x dan y. Anda sudah membuat x dan y pada contoh sebelumnya. Maka, mari hapus dulu agar Anda dapat melampirkan data baru ini.

rm(x, y)
attach(ESL.mixture)Didukung oleh

Data ini juga berdimensi 2. Mari plot untuk melihat dengan jelas.

plot(x, col = y + 1)Didukung oleh

Data tampak cukup tumpang tindih, tetapi Anda bisa melihat ada sesuatu yang khas dalam strukturnya. Sekarang, mari buat data frame dengan respons y, dan ubah menjadi faktor. Setelah itu, Anda dapat memasang SVM dengan kernel radial dan cost sebesar 5.

dat = data.frame(y = factor(y), x)
fit = svm(factor(y) ~ ., data = dat, scale = FALSE, kernel = "radial", cost = 5)Didukung oleh

Saatnya membuat kisi dan melakukan prediksi. Data ini sebenarnya sudah disertai titik-titik kisi. Jika Anda melihat ringkasan nama-nama dalam list, ada 2 variabel px1 dan px2, yaitu kisi nilai untuk masing-masing variabel. Anda dapat menggunakan expand.grid untuk membuat kisi nilai. Lalu Anda memprediksi klasifikasi di setiap nilai pada kisi.

xgrid = expand.grid(X1 = px1, X2 = px2)
ygrid = predict(fit, xgrid)Didukung oleh

Terakhir, Anda memplot titik-titik dan memberi warna sesuai batas keputusan. Anda dapat melihat bahwa batas keputusan bersifat non-linear. Anda juga bisa menambahkan titik data pada plot untuk melihat di mana posisinya.

plot(xgrid, col = as.numeric(ygrid), pch = 20, cex = .2)
points(x, col = y + 1, pch = 19)Didukung oleh

Batas keputusan, dalam banyak hal, mengikuti distribusi data, tetapi dengan cara yang sangat non-linear.

Mari lihat apakah Anda bisa memperbaiki plot ini sedikit lagi dan membuat fungsi predict menghasilkan estimasi fungsi aktual di setiap titik kisi. Secara khusus, Anda ingin menambahkan kurva yang memberikan batas keputusan dengan memanfaatkan fungsi contour. Pada data frame, juga ada variabel bernama prob, yaitu probabilitas sebenarnya dari kelas 1 untuk data ini, pada titik-titik kisi. Jika Anda plot kontur 0,5-nya, itu akan memberikan Bayes Decision Boundary, yaitu yang terbaik yang bisa dicapai.

Pertama, Anda memprediksi fit Anda pada kisi. Anda menetapkan decision values sama dengan TRUE karena Anda ingin mendapatkan fungsi aktualnya, bukan hanya klasifikasinya. Fungsi ini mengembalikan atribut dari nilai yang diklasifikasikan, jadi Anda harus mengambil atribut tersebut. Lalu Anda akses yang bernama decision.

Berikutnya, Anda dapat mengikuti langkah yang sama seperti di atas untuk membuat kisi, membuat prediksi, dan memplot titik-titik.

Kemudian, saatnya menggunakan fungsi contour. Fungsi ini membutuhkan 2 urutan kisi, sebuah fungsi, dan 2 argumen level dan add. Anda menginginkan fungsi dalam bentuk matriks, dengan dimensi px1 dan px2 (masing-masing 69 dan 99). Anda atur level sama dengan 0 dan tambahkan ke plot. Hasilnya, Anda dapat melihat kontur mengikuti batas keputusan, cara yang nyaman untuk memplot batas keputusan non-linear dalam 2 dimensi.

Terakhir, Anda sertakan kebenaran, yaitu kontur probabilitas. Itu adalah kontur 0,5, yang akan menjadi batas keputusan dalam hal probabilitas (dikenal juga sebagai Bayes Decision Boundary).

func = predict(fit, xgrid, decision.values = TRUE)
func = attributes(func)$decision

xgrid = expand.grid(X1 = px1, X2 = px2)
ygrid = predict(fit, xgrid)
plot(xgrid, col = as.numeric(ygrid), pch = 20, cex = .2)
points(x, col = y + 1, pch = 19)

contour(px1, px2, matrix(func, 69, 99), level = 0, add = TRUE)
contour(px1, px2, matrix(func, 69, 99), level = 0.5, add = TRUE, col = "blue", lwd = 2)Didukung oleh

Hasilnya, Anda dapat melihat SVM non-linear Anda cukup mendekati Bayes Decision Boundary.

Kesimpulan

Untuk merangkum, Support Vector Machines adalah subkelas pengklasifikasi terawasi yang berupaya membagi ruang fitur menjadi dua atau lebih kelompok. Mereka mencapainya dengan mencari cara optimal untuk memisahkan kelompok tersebut berdasarkan label kelas yang diketahui:

• Pada kasus yang lebih sederhana, "batas" pemisahan bersifat linear, menghasilkan kelompok yang dipisah oleh garis (atau bidang) dalam ruang berdimensi tinggi.
• Pada kasus yang lebih rumit (di mana kelompok tidak terpisah rapi oleh garis atau bidang), SVM mampu melakukan pemartisian non-linear. Ini dicapai melalui fungsi kernel.
• Pada akhirnya, ini membuat SVM menjadi pengklasifikasi yang sangat canggih dan kapabel, namun dengan konsekuensi biasa bahwa mereka rentan terhadap overfitting.

Secara pribadi, saya pikir SVM adalah pengklasifikasi yang hebat untuk situasi tertentu ketika kelompoknya jelas terpisah. SVM juga bekerja sangat baik ketika data Anda terpisah secara non-linear. Anda bisa mentransformasikan data agar menjadi terpisah secara linear, atau Anda bisa membiarkan SVM mengonversi data dan memisahkan kedua kelas secara linear langsung. Ini salah satu alasan utama menggunakan SVM. Anda tidak perlu mentransformasikan data non-linear sendiri. Kekurangannya adalah sifat "kotak hitam" dari fungsi-fungsi ini. Penggunaan kernel untuk memisahkan data non-linear membuatnya sulit (jika bukan tidak mungkin) untuk ditafsirkan. Memahaminya akan memberi Anda alternatif terhadap GLM dan decision tree untuk klasifikasi. Saya harap tutorial ini memberi Anda pandangan yang lebih luas tentang panorama SVM dan memungkinkan Anda memahami mesin ini dengan lebih baik.

Jika Anda ingin mempelajari lebih lanjut tentang R, ikuti kursus Machine Learning Toolbox dari DataCamp.

Lihat juga Tutorial Support Vector Machines dengan Scikit-learn kami.