Ide dibalik Support Vector Machine

Cara Kerja

Support Vector Machine (SVM) diperkenalkan Vapnik di 1992 sebagai teknik klasifikasi yang efisien untuk masalah nonlinier. SVM berbeda dengan teknik klasifikasi di era 1980-an seperti decision tree dan ANN, yang secara konsep seringkali terjebak pada optimum lokal. Penerapan metode ini bisa digunakan untuk kasus face detection, pengkategorian text, pengelompokan gambar dan di bidang bioninformatika.

Misalkan kita mempunyai scatter plot data observasi seperti di bawah ini. Jika ada suatu data baru masuk, Bagaimana cara kita membedakan data tersebut termasuk kategori Muffin atau Cupcake ?

Cara paling mudah untuk membedakan suatu data baru masuk dalam kelas Muffin atau Cupcake adalah dengan menarik suatu garis lurus yang seolah-olah akan menjadi pemisah antara kedua kelas tersebut. Akan ada banyak kemungkinan garis yang memisahkan kedua kelas tersebut seperti yang ditunjukkan gambar di bawah ini. Garis manakah yang paling tepat ?

Inilah ide dibalik metode Support Vector Machine yaitu menemukan suatu garis (a.k.a hyperplane) yang akan menjadi pemisah terbaik untuk kategori/kelas tersebut. Pemisah yang terbaik adalah yang memisahkan kedua kelas selebar mungkin/sejauh mungkin.

Sehingga prinsip kerja Support Vector Machine (SVM) adalah menemukan hyperplane sedemikian hingga margin antara kedua kelas adalah yang terbesar (find the widest range), seperti yang ditunjukkan gambar di bawah ini

Margin merupakan jarak antara dua kelas (dihitung dari titik terluar masing-masing kelas). Garis putus-putus menunjukkan batas terluar masing masing kelas. Garis lurus yang berada di tengah garis putus-putus adalah garis pemisah terbaik. Hal ini karena garis tersebut membuat margin kedua kelas mmenjadi maximum. Titik terluar dari masing-masing kelas disebut dengan support vector.

Baca Juga : Ide dibalik k-NN

Apakah SVM hanya untuk linear classifier ?

Pada dasarnya SVM merupakan linear classifier, namun pada tahap selanjutnya telah dikembangkan menjadi non-linear classifer. Idenya adalah menggunakan kernel trick pada ruang berdimensi tinggi. Pada umumnya terdapat empat jenis fungsi kernel yang digunakan yaitu

  1. Kernel linier
  2. Kernel polnomial
  3. Kernel Gaussian (a.k.a radial basis function, RBF)
  4. Kernel Sigmoid

Apakah SVM hanya untuk data berkategori biner ?

Awalnya SVM hanya bisa mengklasifikasikan objek ke dalam dua kelas, artinya SVM adalah biner classifier. Namun pada tahap selanjutnya SVM bisa dikembangkan sehingga mampu mengatasi kasus lebih dari dua kategori.

Pendekatan pertama adalah menggabungkan semua data dari semua kelas kemudian menyatakannya dalam bentuk permasalah optimasi. Namun, pendekatan ini, komputasinya akan rumit. Sehingga umumnya menggunakan pendekatan kedua yaitu membandingkan beberapa SVM biner.

  1. One-against all
    dia termasuk kelas ini atau bukan adalah ide dibalik metode ini. Misalkan kita punya variabel X, Y, dan Z. Maka kita akan membuat 3 model SVM biner seperti berikut
    SVM model 1 : kategori ->  X, bukan X
    SVM model 2 : kategori ->  Y, bukan Y
    SVM model 3 : kategori ->  Z, bukan Z
  2. One-against one
    Pada pendekatan ini kita akan menggunakan sistem voting untuk mengklasifikan data. Misalkan kita punya variabel X, Y, Z. Kali ini kita akan membuat k(k-1)/2 model SVM biner. Sehingga dengan tiga kategori kita akan membuat 3(3-1)/2=3 buah SVM biner.
    SVM model 1 : kategori -> X, Y
    SVM model 2 : kategori -> X, Z
    SVM model 3 : kategori -> Y, Z
    kelas yang paling sering muncul adalah yang menang.
  3. Directed Acyclic Graph Support Vector Machine
    Metode ini mirip dengan metode one-against one, sehingga kita akan tetap perlu membuat k(k-1)/2 model SVM biner. Perbedaannya, pada metode ini dibuat sistem gugur. Artinya kelas yang sudah kalah tidak di ikut sertakan lagi. Hal ini mirip dengan pertandingan sepak bola di liga champions di tahap 16 besar ke babak final. Tim yang bertanding dapat diibaratkan sebagai kategori.

Referrence

 

Leave a Reply

Your email address will not be published.

Related posts