Kecerdasan Buatan Lanjut

Topic 4_Support Vector Machine (SVM)

Dr. Rini Sovia, [Link], [Link]
Teknik Informatika_Universitas Putra Indonesia YPTK Padang
 Support Vector Machine (SVM)
 Support Vector Machine (SVM) adalah algoritma supervised yang berupa klasifikasi dengan
cara membagi data menjadi dua kelas menggunakan garis vektor yang disebut hyperplane
(Octaviani, et al., 2014).

 SVM merupakan salah satu metode dalam pembelajaran terawasi atau disebut supervised
learning yang biasanya digunakan untuk klasifikasi (seperti Support Vector Classification) dan
regresi (Support Vector Regression).

 Support Vector Machine (SVM) pertama kali diperkenalkan oleh Vapnik pada tahun 1992
sebagai rangkaian harmonis konsep-konsep unggulan dalam bidang pattern recognition.

 Dalam pemodelan klasifikasi, SVM memiliki konsep yang lebih matang dan lebih jelas secara
matematis dibandingkan dengan teknik-teknik klasifikasi lainnya. SVM juga dapat mengatasi
masalah klasifikasi dan regresi dengan linear maupun non linear
 Bagaimana SVM Bekerja ?
 SVM bekerja atas prinsip Structural Risk Minimization (SRM) dengan tujuan
menemukan hyperplane terbaik yang memisahkan dua buah class pada input
space.
 Hyperplane adalah sebuah fungsi yang dapat digunakan untuk pemisah antar kelas.
Dengan kata lain, SVM merupakan sebuah teknik yang menggunakan 2 titik (2
vektor), yang selanjutnya 2 titik ini akan membentuk garis pembatas. Garis/sisi
pembatas yang dibentuk dari dua buah vektor ini disebut dengan hyperplane.
 Konsep SVM dapat dijelaskan secara sederhana sebagai usaha mencari hyperplane
terbaik yang berfungsi sebagai pemisah dua buah kelas pada input space.
Pattern yang merupakan anggota dari dua buah kelas : +1 dan -1 dan berbagi
alternative garis pemisah (discrimination boundaries). Margin adalah jarak antara
hyperplane tersebut dengan pattern terdekat dari masing-masing
kelas. Pattern yang paling dekat ini disebut sebagai support vector.
 Karakteristik Support Vector Machine (SVM)

 SVM memerlukan proses pelatihan dengan menyimpan hasil support vector yang didapatkan untuk
digunakan Kembali pada saat pengujian.

 SVM memberikan model yang sama dan solusi yang sama dengan memaksimalkan margin.

 SVM dapat memisahkan data yang didistribusikan kelasnya bersifat linier dan non linear

 SVM tidak dipengaruhi oleh dimensi data yang tinggi, sehingga tidak perlu proses reduksi dimensi.

 Memory yang digunakan SVM dipengaruhi oleh banyaknya data, bukan besarnya dimensi.
 Model/Kernel Support Vector Machine (SVM)

 Kernel Linier digunakan Ketika data yang akan diklasifikasikan dapat tepisah dengan sebuah
garis/hyperplane
 Kernel Non-Linier digunakan Ketika data hanya dapat dipisahkan dengan garis lengkung atau
sebuah bidang ruang dimensi tinggi (Kernel No. 2 S/D Kernel No. 7s)
Visualisasi Kernel Support Vector Machine (SVM)
Visualisasi Hyperplane SVM

Gambar Hyperplane yang memisahkan dua kelas positif (+1) dan negatif(-1)

 Hyperplane yang ditemukan SVM diilustrasikan seperti Gambar Diatas posisinya berada ditengah-tengah antara dua kelas,
artinya jarak antara hyperplane dengan objek-objek data berbeda dengan kelas yang berdekatan (terluar) yang diberi tanda
bulat kosong dan positif.
 Dalam SVM objek data terluar yang paling dekat dengan hyperplane disebut support vector. Objek yang disebut support
vector paling sulit diklasifikasikan dikarenakan posisi yang hampir tumpang tindih (overlap) dengan kelas lain. Mengingat
sifatnya yang kritis, hanya support vector inilah yang diperhitungkan untuk menemukan hyperplane yang paling optimal
oleh SVM.
 Untuk menentukan decision boundary (DB), yaitu suatu model linear atau hyperplane y(x) dengan parameter w dan b,
SVM menggunakan konsep margin yang didefiniskan sebagai jarak terdekat antara DB dengan sembarang data training.
 Bentuk Umum Support Vector Machine (SVM)
 Support Vector Machine (SVM) menggunakan model linear sebagai decision boundary dengan
bentuk umum sbb:

y(x) = WT φ(x) + b

 dimana x adalah vektor input, w adalah parameter bobot, φ(x) adalah fungsi basis, dan b adalah
suatu bias
Hyperplane
 Bentuk model linear yang paling sederhana untuk
decision boundary adalah:
y(x) = wT x + w0

 Dimana x adalah vektor input, w adalah vektor bobot

dan w0 adalah bias.
 Sehingga, decision boundary adalah y(x)=0, yaitu
suatu hyperplane berdimensi (D-1)
 Suatu vektor input x akan diklasifikasikan ke kelas 1
(R1 ) jika y(x)≥0, dan kelas 2 (R2 ) jika y(x)<0
Sifat-Sifat Hyperplane

 Jika XA dan XB terletak pada decision boundary

(DS), maka y(XA )=y(XB )=0 atau WT (XA - XB
)=0, sehingga W tegak lurus terhadap semua
vektor di DS.
 Dengan kata lain w menentukan orientasi dari DS
• Jarak titik awal ke DS adalah -w0 /||w||. Dengan
kata lain W0 menentukan lokasi DS. • Jarak
sembarang vektor x ke DS dan searah w adalah
y(x)/||w||
Memaksimalkan Margin (Decision Boundary)

 Untuk menentukan decision boundary (DB), yaitu suatu

model linear atau hyperplane y(x) dengan parameter w dan
b, SVM menggunakan konsep margin yang didefiniskan
sebagai jarak terdekat antara DB dengan sembarang data
training
 Dengan memaksimumkan margin, maka akan didapat suatu
DB tertentu

Kenapa margin Maksimum??

 Berdasarkan intuisi, margin maksimum adalah pilihan yang
aman karena jika terjadi sedikit kesalahan pada data maka
akan memberikan kemungkinan terkecil terjadi kesalahan
klasifikasi.

 Berdasarkan teori, yang merupakan basis dari metode SVM,

maksimum margin akan memberikan kapabilitas
generalisasi terbaik (VC theory, 1960-1990)
Memaksimalkan Margin (Decision Boundary)
 Solusi langsung dari masalah optimasi
sebelumnya akan sangat kompleks, sehingga perlu
dikonversi ke masalah yang ekivalen yang lebih
mudah diselesaikan
 Salah satu metode adalah menggunakan bentuk
kanonik dari DB, yaitu:

 untuk data yang terdekat ke DB. Selanjutnya,

semua data pembelajaran akan memenuhi kondisi
berikut ini:
Proses Klasifikasi Memiliki 2 Proses, Yaitu :

1. Proses training : pada proses training digunakan training set yang telah
diketahui label-labelnya untuk membangun model atau fungsi.

2. Proses testing : untuk mengetahui keakuratan model atau fungsi yang

akan dibangun pada proses training, maka digunakan data yang disebut
dengan testing set untuk memprediksi label-labelnya (Venkateswarlu,
Babu, & Ramana, 2011).
Contoh kasus SVM Linear
x1 x2 Kelas (Y)
1 1 1
1 -1 -1
-1 1 -1
-1 -1 -1

Bentuk Visualisasi Data

1.5

[VALUE] 1 1

0.5
Pada Visualisasi terdapat 2 kelas
0
-1.5 -1 -0.5 0 0.5 1 1.5 yaitu kelas bernilai Positif dan
-0.5
kelas Bernilai Negatif.

-1 -1 -1

-1.5
Dikarenakan terdapat dua fitur yaitu X1 dan X2 maka bobot atau W juga terdiri atas 2
yaitu ( W1 dan W2)
Syarat :
 𝑦𝑖 (w. 𝑥𝑖 +b) ≥ 1 ⅈ = 1,2,3, … . , N
 𝑦𝑖 (𝑤1 𝑥1 + 𝑤2 𝑥2 +b) ≥ 1

Sehingga persamaan menjadi :

 W1 + 𝑊2 + 𝑏 ≥ 1, 𝑢𝑛𝑡𝑢𝑘 𝑦1 = 1, 𝑥1 = 1, 𝑥2 = 1
 −W1 + 𝑊2 − 𝑏 ≥ 1, 𝑢𝑛𝑡𝑢𝑘 𝑦2 = −1, 𝑥1 = 1, 𝑥2 = −1
 W1 − 𝑊2 − 𝑏 ≥ 1, 𝑢𝑛𝑡𝑢𝑘 𝑦3 = −1, 𝑥1 = −1, 𝑥2 = 1
 W1 + 𝑊2 − 𝑏 ≥ 1, 𝑢𝑛𝑡𝑢𝑘 𝑦4 = −1, 𝑥1 = −1, 𝑥2 = −1
 Proses Pencarian Nilai persamaan
 Menjumlahkan persamaan (1) dan (2) :  Subtitusi W1 dan W2 dari persamaan 1
W1 + 𝑊2 + 𝑏 ≥ 1
−W1 + 𝑊2 − 𝑏 ≥ 1
W1 + 𝑊2 + 𝑏 ≥ 1
____________________+
2 W2 =2 1+1+𝑏 =1
Maka W2 = 1
2+𝑏 =1
 Menjumlahkan persamaan (1) dan (3) : 𝑏=1-2
W1 + 𝑊2 + 𝑏 ≥ 1 𝑏 = −1
W1 − 𝑊2 − 𝑏 ≥ 1
________________+
2W1 = 2
Maka b=-1
Maka W1 = 1
 Pengujian dengan Data Testing

 Untuk melakukan klasifikasi terhadap data uji, maka diperoleh dengan

sebuah fungsi F(x) = 𝑥1 + 𝑥2 -1
 Sementara untuk menentuka kelas menggunakan sign(f(x))

𝑥1 𝑥2 Kelas ( sign(𝑥1 + 𝑥2 -1 ))
1 4 Sign(1+4-1) = +1
-2 6 Sign(-2+6-1)= +1
-2 2 Sign(-2+2-1)= -1
-5 3 Sign(-5+3-1)= -1
-7 2 Sign (-7+2-1)= -1
 Contoh Kasus : Klasifikasi Kinerja Karyawan
X1 (Inovativ) X2 X3 (Disiplin) Kinerja
(Tanggung
Jawab)
7 9 9 Baik
5 4 5 Kurang Baik
6,5 4 5 Kurang Baik
7 8 8 Baik
4 8 9 Baik

 Berdasarkan Data Tabel Diatas Sehingga Didapatkan Persamaan

Sebagai Berikut :
7𝑊1 + 9𝑊2 + 9𝑊3 + 𝑏 ≥ 1
−5𝑊1 − 4𝑊2 − 5𝑊3 − 𝑏 ≥ 1
−6,5𝑊1 − 4𝑊2 − 5𝑊3 − 𝑏 ≥ 1
7𝑊1 + 8𝑊2 + 8𝑊3 + 𝑏 ≥ 1
4𝑊1 + 8𝑊2 + 9𝑊3 + 𝑏 ≥ 1
 Menjumlahkan Persamaan (1) dan (2)  Menjumlahkan Persamaan (3) dan (4)

7𝑊1 + 9𝑊2 + 9𝑊3 + 𝑏 ≥ 1 −6,5𝑊1 − 4𝑊2 − 5𝑊3 − 𝑏 ≥ 1

−5𝑊1 − 4𝑊2 − 5𝑊3 − 𝑏 ≥ 1 7𝑊1 + 8𝑊2 + 8𝑊3 + 𝑏 ≥ 1
----------------------------------------- + ------------------------------------------------ +
2𝑊1 + 5𝑊2 + 4𝑊3 = 2 ---> (6) 0,5𝑊1 + 4𝑊2 + 3𝑊3 = 2 ---> (8)

 Menjumlahkan Persamaan (2) dan (3)  Menjumlahkan Persamaan (4) dan (5)

−5𝑊1 − 4𝑊2 − 5𝑊3 − 𝑏 ≥ 1 7𝑊1 + 8𝑊2 + 8𝑊3 + 𝑏 ≥ 1

−6,5𝑊1 − 4𝑊2 − 5𝑊3 − 𝑏 ≥ 1 4𝑊1 + 8𝑊2 + 9𝑊3 + 𝑏 ≥ 1
------------------------------------------------ + --------------------------------------------- +
−11,5𝑊1 − 8𝑊2 − 10𝑊3 − 2𝑏 = 2 ---> (7) 11𝑊1 + 16𝑊2 + 17𝑊3 + 2𝑏 = 2 ---> (9)
 Eliminasi W3 Dari Persamaan (6) dan (7)  Eliminasi W3 Dari Persamaan (8) dan (9)
2𝑊1 + 5𝑊2 + 4𝑊3 = 2 (-10) 0,5𝑊1 + 4𝑊2 + 3𝑊3 = 2 (17)
−11,5𝑊1 − 8𝑊2 − 10𝑊3 − 2𝑏 = 2 (4) 11𝑊1 + 16𝑊2 + 17𝑊3 + 2𝑏 = 2 (3)
--------------------------------------------------------------- ----------------------------------------------------------
−20𝑊1 − 50𝑊2 − 40𝑊3 = −20 8,5𝑊1 + 68𝑊2 + 51𝑊3 = 34
−46𝑊1 − 32𝑊2 − 40𝑊3 − 8𝑏 = 8 33𝑊1 + 48𝑊2 + 51𝑊3 + 6𝑏 = 6
------------------------------------------------------ _ ----------------------------------------- _
26𝑊1 − 18𝑊2 − 8𝑏 = −28 ---> (10) −24,5𝑊1 + 20𝑊2 + 6𝑏 = 28 ---> (12)

 Eliminasi W3 Dari Persamaan (7) dan (8)  Eliminasi W2 Dari Persamaan (10) dan (11)

−11,5𝑊1 − 8𝑊2 − 10𝑊3 − 2𝑏 = 2 (3) 26𝑊1 − 18𝑊2 − 8𝑏 = −28 (16)

0,5𝑊1 + 4𝑊2 + 3𝑊3 = 2 (-10) −29,5𝑊1 + 16𝑊2 − 6𝑏 = 26 (-18)
--------------------------------------------------- -----------------------------------------------------------
−34,5𝑊1 − 24𝑊2 − 30𝑊3 − 6𝑏 = 6 416𝑊1 − 288𝑊2 − 128𝑏 = −448
−5𝑊1 − 40𝑊2 − 30𝑊3 = −20 531𝑊1 − 228𝑊2 + 108𝑏 = −468
---------------------------------------------------- _ ------------------------------------------------ _
−29,5𝑊1 + 16𝑊2 − 6𝑏 = 26 ---> (11) 947𝑊1 − 236𝑏 = 20 ---> (13)
 Eliminasi W2 Dari Persamaan (11) dan (12)  Eliminasi b Dari Persamaan (13) dan (14)

−29,5𝑊1 + 16𝑊2 − 6𝑏 = 26 (20) 947𝑊1 − 236𝑏 = 20 (-216)

−24,5𝑊1 + 20𝑊2 + 6𝑏 = 28 (16) −198𝑊1 − 216𝑏 = 72 (-236)
-------------------------------------------------------- ------------------------------------------------
−590𝑊1 + 320𝑊2 − 120𝑏 = 520 −24840𝑊1 + 50976𝑏 = −4320
−392𝑊1 + 320𝑊2 + 96𝑏 = 448 46728𝑊1 + 50976𝑏 = −16992
--------------------------------------------_ ---------------------------------------------- _
−198𝑊1 − 216𝑏 = 72 ---> (14) −71568𝑊1 = 21312
12672
𝑊1 = −
71568
𝑊1 = −0,17
 Subtitusi W1 Dari Persamaan (14)  Subtitusi W1 dan b Dari Persamaan (12)

−198𝑊1 − 216𝑏 = 72 −24,5𝑊1 + 20𝑊2 + 6𝑏 = 28

−198 −0,17 − 216𝑏 = 72 (−24,5(−0,17)) + 20𝑊2 + (6 0,17 ) = 28

33,66 − 216𝑏 = 72 4,16 + 20𝑊2 + 1,02 = 28

−216𝑏 = 72 − 33,66 5,18 + 20𝑊2 = 28

−216𝑏 = −38,34 20𝑊2 = 28 − 5,18

−38,34 20𝑊2 = 22,82

𝑏=
−216 22,82
𝑊2 =
𝑏 = 0,17 20
𝑊2 = 1,41
 Subtitusi W1, W2 dan b Dari Persamaan (9)

11𝑊1 + 16𝑊2 + 17𝑊3 + 2𝑏 = 2

(11(−0,17)) + (16 1,41 ) + 17𝑊3 + (2 0,17 ) = 2
(−1,87) + (22,56) + 17𝑊3 + (0,34) = 2
21,03 + 17𝑊3 = 2
17𝑊3 = 2 − 21,03
17𝑊3 = −19,03
− 19.03
𝑊3 =
17
𝑊3 = −1,11

𝑦 = 𝑦𝑖 (𝑤1 𝑥1 + 𝑤2 𝑥2 + 𝑤3 𝑥3 +b)
y = (-0,17 𝑥1 )+(1,41 𝑥2 )+(-1,11 𝑥3 ) + 0,17
Latihan :
Data Karyawan sebagai berikut ini :
lakukan perhitungan dengan menggunakan persamaan linear untuk mendapatkan nilai bobot (W) dan
Bias (b), Kemudian ujikan apakah kinerja sudah sesuai yang diprediksi oleh Model SVM

Tanggung
Inovatif Jawab Disiplin Kinerja
2 4 6 Kurang baik
7 7 8 Baik
9 5 5 Baik
5 9 10 Baik
6 3 6 Kurang baik